Difference between revisions of "Boolean Algebra"

From TRCCompSci - AQA Computer Science
Jump to: navigation, search
(Redundancy Law)
(Law 1 :)
Line 96: Line 96:
 
==Redundancy Law==
 
==Redundancy Law==
 
===Law 1 :===
 
===Law 1 :===
<math> A + \overline{A} B = A + B </math>
+
<math> A + (\overline{A}. B) = A + B </math>
  
 
Proof :  
 
Proof :  
Line 106: Line 106:
  
 
<hr>
 
<hr>
 +
 
===Law 2:===
 
===Law 2:===
 
<math> A.(\overline{A} + B) = A.B</math>
 
<math> A.(\overline{A} + B) = A.B</math>

Revision as of 12:57, 21 January 2020

Boolean Algebra Precedence

the order of precedence for boolean algebra is:

  1. Brackets
  2. Not
  3. And
  4. Or

Boolean Identities

Using AND

[math] A.1 = A [/math]

This equation means that the output is determined by the value of A. So if A =0, The output is 0, and vice versa.

[math] 0.A = 0 [/math]

Because there is a 0 in this equation, the output of this will always be 0 regardless of the value of A.

[math] A.A = A[/math]

The output is determined by A alone in this equation. This can be simplified to just "A".

[math] A.\overline{A}=0 [/math]

Here the output will be 0, regardless of A's value. A would have to be 1 and 0 for the output to be 1. This means we can simplify this to just 0.

Using OR

[math] 0+A = A [/math]

0 or A can be simplified as just A.

[math] 1+A = 1 [/math]

1 or A can be simplified as just 1.

[math] A+A=A[/math]

A or A can be simplified as just A.

[math] \overline{A}+A=1[/math]

NOT A or A can be simplified as just 1.

Boolean Laws

Commutative Law

The Commutative Law is where equations are the same no matter what way around the letters are written. For example

[math] A+B = B+A [/math]

or

[math] A.B = B.A [/math]

Associate Law

If all of the symbols are the same it doesn't matter which order the equation is evaluated.

[math] A+(B+C) = B + (A+C) [/math]

[math] A+(B+C) = B + (A+C) [/math]

[math] A+(B+C) = C + (A+B) [/math]

So:

[math] A.(B.C) = B . (A.C) [/math]

[math] A.(B.C) = B . (A.C) [/math]

[math] A.(B.C) = C . (A.B) [/math]

Distributive Law

The distributive law is these two equations.

[math] A.(B+C) = A.B + A.C [/math]

[math] A+(B.C) = (A+B).(A+C) [/math]

This is essentially factorising or expanding the brackets, but you can also remove the common factor:

[math] A.B + A.C = A.(B+C)[/math]

[math] A+B.A+C = A+(B.C) [/math]

You can also remove the common factor if you only have 1 term on one side:

[math] A.(A + B) = (0+A) . (A + B) [/math]

[math] A+(A . B) = (1.A) + (A . B) [/math]

if the symbol inside the brackets is a '+' you can add '+0' or if the symbol inside the brackets is '.' you can add '.1'.

Redundancy Law

Law 1 :

[math] A + (\overline{A}. B) = A + B [/math]

Proof :

[math]= A + \overline{A} B \\ = (A + \overline{A})(A + B) \\ = 1 . (A + B) \\ = A + B [/math]


Law 2:

[math] A.(\overline{A} + B) = A.B[/math]

Proof :

[math]= A.(\overline{A} + B) \\ = A.\overline{A} + A.B \\ = 0 + A.B \\ = A.B [/math]


Law 3:

[math] A.(A + B) = A[/math]

Proof using distributive law:

[math] A.(A + B) = (0+A) . (A + B) [/math]

So: [math] A + (0 . B) [/math]

So: [math] A + 0 = A [/math]


Law 4:

[math] A+(A . B) = A[/math]

Proof using distributive law:

[math] A+(A . B) = (1 . A) + (A . B) [/math]

So: [math] A . (1 + B) [/math]

So: [math] A . 1 = A [/math]

Identity Law

This is also in the identities section:

[math] A.A = A [/math]

[math] A+A = A [/math]

Negation Law

Just like in any other logic negating a negative is a positive so:

[math] \overline{ \overline{A} } = A [/math]

Solving Boolean Equations

Solving equations is a matter of applying the laws of boolean algrebra, followed by any of the identities you can find:

Example 1

[math] 𝐶+(𝐶.𝐷) [/math]


Take out the common factor C:

[math](C.D)+(C.1)=C.(D+1)[/math],

We know that [math]1+A=1[/math],

Therefore, [math]C.1[/math],

Use identity [math]A.1=A[/math],

Answer = [math]C[/math]


Example 2

A.(C+A)

|Use Distributive Law|

->(A.C)+(A.A)

|Use Identity| A.A=A

->(A.C)+A

|This is the same as writing (could straight apply redundancy rule here)|

->(A.C)+(A.1)

|Take out the common factor|

->A.(C+1)

|Use Identity| C+1 = 1

->A

Example 3

[math] 𝐵.(𝐴+\overline{𝐵}) [/math]

B.(A+ NOT B) REDUNDANCY (A + NOT B) REDUNDANCY

ANSWER = NOT B

Example 4

[math] 𝑋.(\overline{𝑋}+𝑌) [/math]

[math] 𝑋.\overline{𝑋} = 0 [/math]

[math] 0+𝑌 = 𝑌 [/math]

Example 5

[math] 𝑋.(X+\overline{Y}) [/math]

[math] (0+𝑋).(X+\overline{Y}) [/math]

[math] 𝑋+(0.\overline{Y}) [/math]

[math] 𝑋+(0) [/math]

[math] 𝑋 [/math]

Example 6

[math] (𝐴.𝐴)+(𝐴.1)+(𝐵.\overline{𝐵}) [/math]

Example 7

[math] 𝐴.(𝐶+𝐵+\overline{𝐴}) [/math]

B.C

Example 8

[math] 𝐷.𝐸+𝐸.\overline{𝐷} [/math] D.E+E.D Distributivetive Law D.(E+D) Redundancy Law D

Example 9

[math] 𝐴.(𝐴+𝐴).(𝐵+\overline{𝐴}) [/math]

Example 10

[math] 𝐴.𝐷.\overline{𝐵}+𝐴.𝐷.𝐵 [/math]

Example 11

[math] 𝐶.𝐷.(𝐷.𝐵+𝐶) [/math]

Example 12

[math] \overline{𝐵}.(𝐷+𝐵) [/math]

Example 13

[math] (\overline {A}+\overline {B}).B [/math]

[math] (\overline {A}+\overline{B}). (B+1) [/math]

[math] \overline {A}+(B.1) [/math]

[math] \overline {A}+B [/math]

Example 14

[math] \overline{B} + (A.B) [/math] (B) + (A.B) Distributive Law. (B + A) . (B + B) Not B cancels out. B + A . 1 = B+A

Example 15

[math] X+(\overline{X}.\overline{Y}) [/math]

Example 16

[math] (\overline{A} . A) + (\overline{A} . C) [/math]

= NOT A

Because the centre symbol is an OR gate and neither of the outputs of the and gates is A therefore by redundancy rule it is NOT A.

Example 17

[math] (\overline{A} + A) . (\overline{A} + C) [/math]

Example 18

[math] X.(\overline{X}+Y) [/math]

Example 19

[math](X + Y) . (X + \overline{Y})[/math]
Distributive:
[math]X . (Y + \overline{Y})[/math]
Identity laws:
[math]Y + \overline{Y} = 1[/math]

[math] X.1 = X[/math]

Alternative

[math] X.X + X.\overline{Y} + Y.X + Y.\overline{Y} [/math] Expanding the brackets

[math] X + X.\overline{Y} + Y.X + 0 [/math] Use of [math] X.X = X [/math] and [math] Y.\overline{Y} = 0 [/math]

[math] X + X(\overline{Y}+Y) [/math] Taking X out of the brackets

[math] X + X(1) [/math] Use of [math] Y + \overline{Y} = 1 [/math]

[math] X(1) [/math]

[math] X [/math]

End of Page