Difference between revisions of "Boolean Algebra"

From TRCCompSci - AQA Computer Science
Jump to: navigation, search
(Example 2)
(Boolean Laws)
 
(12 intermediate revisions by the same user not shown)
Line 7: Line 7:
  
 
=Boolean Identities=
 
=Boolean Identities=
 +
===TRC Video===
 +
<youtube>https://www.youtube.com/watch?v=ym73-rgnrOQ</youtube>
 +
 +
https://www.youtube.com/watch?v=ym73-rgnrOQ
 +
 
===Using AND===
 
===Using AND===
  
Line 43: Line 48:
  
 
=Boolean Laws=
 
=Boolean Laws=
 +
===TRC Video===
 +
<youtube>https://www.youtube.com/watch?v=Cdqj4XDsUVY</youtube>
 +
 +
https://www.youtube.com/watch?v=Cdqj4XDsUVY
 +
 
==Commutative Law==
 
==Commutative Law==
 
The Commutative Law is where equations are the same no matter what way around the letters are written. For example
 
The Commutative Law is where equations are the same no matter what way around the letters are written. For example
Line 76: Line 86:
 
<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:
+
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>
  
 
<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'. Doing this will not change the nature of the brackets because 'A' is the same as 'A+0' and is the same as 'A.1'.
  
 
==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 :  
  
<math>= A + \overline{A} B \\
+
<math>= A + (\overline{A}. B) = A + B  \\
 
= (A + \overline{A})(A + B) \\
 
= (A + \overline{A})(A + B) \\
 
= 1 . (A + B) \\
 
= 1 . (A + B) \\
 
= A + B </math>
 
= A + B </math>
 +
 +
<hr>
  
 
===Law 2:===
 
===Law 2:===
Line 103: Line 127:
 
= A.B </math>
 
= A.B </math>
  
 +
<hr>
 
===Law 3:===
 
===Law 3:===
 
<math> A.(A + B) = A</math>
 
<math> A.(A + B) = A</math>
Line 122: Line 147:
 
</math>
 
</math>
  
 +
<hr>
 
===Law 4:===
 
===Law 4:===
 
<math> A+(A . B) = A</math>
 
<math> A+(A . B) = A</math>
Line 155: Line 181:
 
=Solving Boolean Equations=
 
=Solving Boolean Equations=
 
Solving equations is a matter of applying the laws of boolean algrebra, followed by any of the identities you can find:
 
Solving equations is a matter of applying the laws of boolean algrebra, followed by any of the identities you can find:
 +
===TRC Video===
 +
<youtube>https://www.youtube.com/watch?v=N1r1D__NMGg</youtube>
 +
 +
https://www.youtube.com/watch?v=N1r1D__NMGg
  
 
===Example 1===
 
===Example 1===
Line 180: Line 210:
 
'''A.(C+A)'''
 
'''A.(C+A)'''
  
 +
 +
------------------------------------
 
|Use Distributive Law|
 
|Use Distributive Law|
  
Line 207: Line 239:
 
</math>
 
</math>
  
 +
------------------------------------
 
B.(A+ NOT B)
 
B.(A+ NOT B)
 
REDUNDANCY  
 
REDUNDANCY  
Line 219: Line 252:
 
</math>
 
</math>
  
 +
------------------------------------
 
<math>
 
<math>
 
𝑋.\overline{𝑋} = 0   
 
𝑋.\overline{𝑋} = 0   
Line 232: Line 266:
 
</math>
 
</math>
  
 +
------------------------------------
 
<math>
 
<math>
 
(0+𝑋).(X+\overline{Y})
 
(0+𝑋).(X+\overline{Y})
Line 247: Line 282:
 
𝑋
 
𝑋
 
</math>
 
</math>
 
===Example 6===
 
<math>
 
(𝐴.𝐴)+(𝐴.1)+(𝐵.\overline{𝐵})
 
</math>
 
===Example 7===
 
<math>
 
𝐴.(𝐶+𝐵+\overline{𝐴})
 
</math>
 
 
B.C
 
  
 
===Example 8===
 
===Example 8===
Line 263: Line 287:
 
𝐷.𝐸+𝐸.\overline{𝐷}
 
𝐷.𝐸+𝐸.\overline{𝐷}
 
</math>
 
</math>
 +
------------------------------------
 
D.E+E.D
 
D.E+E.D
 
Distributivetive Law
 
Distributivetive Law
Line 269: Line 294:
 
D
 
D
  
===Example 9===
 
<math>
 
𝐴.(𝐴+𝐴).(𝐵+\overline{𝐴})
 
</math>
 
===Example 10===
 
<math>
 
𝐴.𝐷.\overline{𝐵}+𝐴.𝐷.𝐵
 
</math>
 
===Example 11===
 
<math>
 
𝐶.𝐷.(𝐷.𝐵+𝐶)
 
</math>
 
===Example 12===
 
<math>
 
\overline{𝐵}.(𝐷+𝐵)
 
</math>
 
 
===Example 13===
 
===Example 13===
 
<math>
 
<math>
Line 290: Line 299:
 
</math>
 
</math>
  
 +
------------------------------------
 +
Expand the brackets:
 
<math>
 
<math>
(\overline {A}+\overline{B}). (B+1)
+
(\overline {A} . B) + (\overline{B} . B)
 
</math>
 
</math>
  
 +
Not B AND B = 0:
 
<math>
 
<math>
\overline {A}+(B.1)
+
\overline {A}.B) + (0)
 
</math>
 
</math>
  
 +
Something OR 0 is Something:
 
<math>
 
<math>
\overline {A}+B
+
\overline {A}.B
 
</math>
 
</math>
  
Line 306: Line 319:
 
\overline{B} + (A.B)
 
\overline{B} + (A.B)
 
</math>
 
</math>
 +
 +
------------------------------------
 
(B) + (A.B)
 
(B) + (A.B)
 
Distributive Law.
 
Distributive Law.
Line 313: Line 328:
 
= B+A
 
= 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===
 
===Example 19===
 
<math>(X + Y) . (X + \overline{Y})</math>
 
<math>(X + Y) . (X + \overline{Y})</math>
 +
 +
------------------------------------
 
<br>Distributive:  
 
<br>Distributive:  
 
<br><math>X . (Y + \overline{Y})</math>
 
<br><math>X . (Y + \overline{Y})</math>

Latest revision as of 08:10, 23 August 2023

Boolean Algebra Precedence

the order of precedence for boolean algebra is:

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

Boolean Identities

TRC Video

https://www.youtube.com/watch?v=ym73-rgnrOQ

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

TRC Video

https://www.youtube.com/watch?v=Cdqj4XDsUVY

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'. Doing this will not change the nature of the brackets because 'A' is the same as 'A+0' and is the same as 'A.1'.

Redundancy Law

Law 1 :

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

Proof :

[math]= A + (\overline{A}. B) = 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:

TRC Video

https://www.youtube.com/watch?v=N1r1D__NMGg

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 8

[math] 𝐷.𝐸+𝐸.\overline{𝐷} [/math]


D.E+E.D Distributivetive Law D.(E+D) Redundancy Law D

Example 13

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


Expand the brackets: [math] (\overline {A} . B) + (\overline{B} . B) [/math]

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

Something OR 0 is Something: [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 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