Difference between revisions of "Boolean Algebra"

From TRCCompSci - AQA Computer Science
Jump to: navigation, search
(Example 13)
(Boolean Laws)
 
(114 intermediate revisions by 17 users not shown)
Line 1: Line 1:
 +
=Boolean Algebra Precedence=
 +
the order of precedence for boolean algebra is:
 +
# Brackets
 +
# Not
 +
# And
 +
# Or
  
Any equation must be within the <nowiki><math> </math></nowiki> tags. For Boolean alegbra the main issue is how to negate a term like:
+
=Boolean Identities=
 +
===TRC Video===
 +
<youtube>https://www.youtube.com/watch?v=ym73-rgnrOQ</youtube>
  
<math> \overline{a}</math> or <math> \overline{\overline{a}+b}</math>
+
https://www.youtube.com/watch?v=ym73-rgnrOQ
  
this can be done by adding the following around any term you wish to negate.:
+
===Using AND===
 
 
<nowiki><math> \overline{} </math></nowiki> 
 
 
 
<math> \overline{a}</math>
 
 
 
is
 
 
 
<nowiki> <math> \overline{a} </math></nowiki>
 
 
 
<math> \overline{\overline{a}+b}</math>
 
 
 
is
 
 
 
<nowiki> <math> \overline{\overline{a}+b} </math></nowiki>.
 
 
 
=Identities=
 
==AND Identities==
 
  
 
<math> A.1 = A </math>
 
<math> A.1 = A </math>
Line 39: Line 30:
 
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.
 
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.
  
==OR Identities==
+
===Using OR===
 
<math> 0+A = A </math>
 
<math> 0+A = A </math>
  
Line 56: Line 47:
 
NOT A or A can be simplified as just 1.
 
NOT A or A can be simplified as just 1.
  
=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 90: 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:===
 
<math> A.(\overline{A} + B) = A.B</math>
 
<math> A.(\overline{A} + B) = A.B</math>
  
Line 118: Line 127:
 
= A.B </math>
 
= A.B </math>
  
==Identity Law==
+
<hr>
This is also in the identities section:
+
===Law 3:===
 +
<math> A.(A + B) = A</math>
  
<math> A.A = A </math>
+
Proof using distributive law:
  
<math> A+A = A </math>
+
<math>
 +
A.(A + B) = (0+A) . (A + B)
 +
</math>
  
==Negation Law==
+
So:
Just like in any other logic negating a negative is a positive so:
+
<math>
 +
A + (0 . B)
 +
</math>
  
<math> \overline{ \overline{A} } = A </math>
+
So:
 
+
<math>
=Equations=
+
A + 0 = A
Solving equations is a matter of applying the laws of boolean algrebra, followed by any of the identities you can find:
+
</math>
 
 
==Example 1==
 
<math> \overline{\overline{A}} . \overline{(B+C)} = A. \overline{B} . \overline{C} </math>
 
<br /><br />
 
<math> \overline{\overline{A}} = A </math>    ''Use Negation Law''
 
<br /><br />
 
<math> \overline{(B+C)} = (\overline{B} . \overline{C}) </math>    ''Use De Morgan's Law''
 
<br /><br />
 
<math> A . (\overline{B} . \overline{C}) = A . \overline{B} . \overline{C} </math>    ''Use Associate Law''
 
 
 
==Example 2==
 
<math> (\overline{A} + A) . (\overline{A} + C) </math>
 
 
 
OR Identity
 
 
 
<math>(\overline{A} + A) = 1</math>
 
 
 
AND Identity
 
 
 
<math>= 1.(\overline{A} + C)</math>
 
 
 
Simplify
 
 
 
<math>= (\overline{A} + C)</math>
 
 
 
==Example 3==
 
<math>(X + Y) . (X + \overline{Y})</math>
 
<br>Distributive:
 
<br><math>X . (Y + \overline{Y})</math>
 
<br>Identity laws:
 
<br><math>Y + \overline{Y} = 1</math>
 
<p><math> X.1 = X</math>
 
 
 
==Example 4==
 
  
Expression Rule(s) Used
+
<hr>
C + BC Original Expression
+
===Law 4:===
C + (B + C) DeMorgan's Law.
+
<math> A+(A . B) = A</math>
(C + C) + B Commutative, Associative Laws.
 
T + B Complement Law.
 
T Identity Law.
 
  
==Example 5==
+
Proof using distributive law:
{| class="wikitable"
 
|-
 
! Simplify: !! AB(A + B)(B + B):
 
|-
 
| Expression || Rule(s) Used
 
|-
 
| AB(A + B)(B + B) || Original Expression
 
|-
 
| AB(A + B) || Complement law, Identity law.
 
|-
 
| (A + B)(A + B) || DeMorgan's Law
 
|-
 
| A + BB || Distributive law. This step uses the fact that or distributes over and. It can look a bit strange since addition does not distribute over multiplication
 
|-
 
| A || Complement, Identity
 
|}
 
  
==Example 6==
 
 
<math>
 
<math>
\overline{A.B}(\overline{A} + B)(\overline{B} + B) </math>     Original Expression
+
A+(A . B) = (1 . A) + (A . B)
 +
</math>
  
 +
So:
 
<math>
 
<math>
\overline{AB}(\overline{A} + B) </math> Complement law, Identity law.
+
A . (1 + B)
 +
</math>
  
 +
So:
 
<math>
 
<math>
(\overline{A} + \overline{B})(\overline{A} + B) </math> DeMorgan's Law
+
A . 1 = A
 +
</math>
  
<math>
+
==Identity Law==
\overline{A} + \overline{B}.B </math> Distributive law. This step uses the fact that or distributes over and.
+
This is also in the identities section:
  
<math>
+
<math> A.A = A </math>
\overline{A} </math> Complement, Identity.
 
  
==Example 7==
+
<math> A+A = A </math>
  
 +
==Negation Law==
 +
Just like in any other logic negating a negative is a positive so:
  
SIMPLIFY <math>(A + C)A + AC + C</math>
+
<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===
 +
<youtube>https://www.youtube.com/watch?v=N1r1D__NMGg</youtube>
  
<math>(A + C)A + AC + C</math> Complement, Identity.
+
https://www.youtube.com/watch?v=N1r1D__NMGg
  
 +
===Example 1===
 +
<math>
 +
𝐶+(𝐶.𝐷)
 +
</math>
  
<math>A((A + C) + C) + C</math> Commutative, Distributive.
+
------------------------------------
 
 
 
 
<math>A(A + C) + C</math> Associative, Idempotent.
 
 
 
 
 
<math>AA + AC + C</math> Distributive.
 
 
 
  
<math>A + (A + T)C</math> Idempotent, Identity, Distributive.
+
Take out the common factor C:
  
 +
<math>(C.D)+(C.1)=C.(D+1)</math>,
  
<math>A + C</math> Identity, twice.
+
We know that <math>1+A=1</math>,
  
==Example 8==
+
Therefore, <math>C.1</math>,
  
 +
Use identity <math>A.1=A</math>,
  
===Simplify===
+
Answer = <math>C</math>
<math> (X+Y).(X+\overline{Y}) </math>  
 
  
===solution===
+
------------------------------------
<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>
+
===Example 2===
 +
'''A.(C+A)'''
  
<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>
+
------------------------------------
 +
|Use Distributive Law|
  
<math> X(1) </math>
+
->'''(A.C)+(A.A)'''
  
<math> X </math>
+
|Use Identity|
 +
'''A.A=A'''
  
==Example 9==
+
->'''(A.C)+A'''
<math> (X + Y) . (X + \overline{Y}) </math>
 
  
<math> X + (Y.\overline{Y}) </math> after distributive law applied
+
|This is the same as writing (could straight apply redundancy rule here)|
  
<math> (Y.\overline{Y}) = 0 </math>
+
->'''(A.C)+(A.1)'''
  
<math> X + 0 </math>
+
|Take out the common factor|
  
<math> X </math>
+
->'''A.(C+1)'''
  
<math> (X + Y) . (X + \overline{Y}) = X  </math>
+
|Use Identity|
 +
'''C+1 = 1'''
  
==Example 10==
+
->'''A'''
Simplify:
 
<math> \overline {AB} (\overline {A}+B)(\overline {B}+B) </math>
 
  
<math> \overline {AB} (\overline {A}+B).1 </math>  
+
===Example 3===
 +
<math>
 +
𝐵.(𝐴+\overline{𝐵})
 +
</math>
  
Complement law, Identity law
+
------------------------------------
 +
B.(A+ NOT B)
 +
REDUNDANCY
 +
(A + NOT B)
 +
REDUNDANCY
  
<math> (\overline {A}+\overline {B})(\overline {A}+B) </math>
+
ANSWER = NOT B
  
DeMorgan's law 
+
===Example 4===
<math> \overline {A}+\overline {B}B </math>  
+
<math>
 +
𝑋.(\overline{𝑋}+𝑌)
 +
</math>
  
Distributive law.  
+
------------------------------------
 +
<math>
 +
𝑋.\overline{𝑋} = 0 
 +
</math>
  
<math> \overline {A} </math>
+
<math>
 +
0+𝑌 = 𝑌
 +
</math>
  
==Example 11==
+
===Example 5===
 +
<math>
 +
𝑋.(X+\overline{Y})
 +
</math>
  
==Example 12==
+
------------------------------------
 +
<math>
 +
(0+𝑋).(X+\overline{Y})
 +
</math>
  
==Example 13==
+
<math>
Simplify
+
𝑋+(0.\overline{Y})
 +
</math>
  
<math>\overline{\overline{A} + \overline{(B.A)}}</math>
+
<math>
 +
𝑋+(0)
 +
</math>
  
First, using De Morgan’s Law simplify it to
+
<math>
 +
𝑋
 +
</math>
  
<math> \overline{\overline{A} + \overline{B} + \overline{A}} </math>
+
===Example 8===
 +
<math>
 +
𝐷.𝐸+𝐸.\overline{𝐷}
 +
</math>
 +
------------------------------------
 +
D.E+E.D
 +
Distributivetive Law
 +
D.(E+D)
 +
Redundancy Law
 +
D
  
This can then be simplified to
+
===Example 13===
 +
<math>
 +
(\overline {A}+\overline {B}).B
 +
</math>
  
<math> \overline{\overline{A} + \overline{B}}
+
------------------------------------
 +
Expand the brackets:
 +
<math>
 +
(\overline {A} . B) + (\overline{B} . B)
 +
</math>
  
Then using De Morgan’s Law again, you get
+
Not B AND B = 0:
 +
<math>
 +
\overline {A}.B) + (0)
 +
</math>
  
<math> \overline{\overline{A}} + \overline{\overline{B}} </math>
+
Something OR 0 is Something:
 +
<math>
 +
\overline {A}.B
 +
</math>
  
Then there are double negatives, so you end up with
+
===Example 14===
 +
<math>
 +
\overline{B} + (A.B)
 +
</math>
  
<math> A + B </math>
+
------------------------------------
 +
(B) + (A.B)
 +
Distributive Law.
 +
(B + A) . (B + B)
 +
Not B cancels out.
 +
B + A . 1
 +
= B+A
  
==Example 14==
 
'''Simplify:'''
 
<math> X.(\overline{X}+Y) </math>
 
  
<math> (X.\overline{X})+(X.Y) </math> using the Distributive Law
+
===Example 19===
 +
<math>(X + Y) . (X + \overline{Y})</math>
  
<math> 0 + (X.Y) </math> using the identity <math>A.\overline{A}=0</math>
+
------------------------------------
 +
<br>Distributive:
 +
<br><math>X . (Y + \overline{Y})</math>
 +
<br>Identity laws:
 +
<br><math>Y + \overline{Y} = 1</math>
 +
<p><math> X.1 = X</math>
 +
====Alternative====
 +
<math> X.X + X.\overline{Y} + Y.X + Y.\overline{Y} </math> Expanding the brackets
  
<math> X.Y </math> using the identity <math>A+0=A</math>
+
<math> X + X.\overline{Y} + Y.X + 0 </math> Use of <math> X.X = X </math> and <math> Y.\overline{Y} = 0 </math>
  
Fully simplified the equation
+
<math> X + X(\overline{Y}+Y) </math> Taking X out of the brackets
  
==Example 15==
+
<math> X + X(1) </math> Use of <math> Y + \overline{Y} = 1 </math>
Simplify the following:
 
<math> \overline{ \overline{(A.A)}. \overline{(B.B)}} </math>
 
  
Using De Morgan's law we can put the equation into another form:
+
<math> X(1) </math>
  
1. Change All operations,
+
<math> X </math>
 
 
<math> \overline{ \overline{(A+A)}+ \overline{(B+B)}} </math>
 
 
 
2. Negate letters:
 
 
 
<math> \overline{ (A+A)+(B+B) } </math>
 
 
 
3. Negate the whole expression:
 
 
 
<math> (A+A)+(B+B) </math>
 
 
 
Using the identity law, we can then simplify this expression to:
 
 
 
<math> A+B </math>
 
 
 
==Example 16==
 
For this example the Boolean Algebra itself is shown above while the description/the rules used are listed below it:
 
 
 
<Math>\overline{A}(A + B) + (B + AA)(A + \overline{B})</Math>
 
 
 
Original expression
 
 
 
<Math>\overline{A}A + \overline{A}B + (B + A)A + (B + A)\overline{B}</Math>
 
 
 
Idempotent (AA to A), then Distributive, used twice.
 
 
 
<Math>\overline{A}B + (B + A)A + (B + A)\overline{B}</Math>
 
 
 
Complement, then Identity. (Strictly speaking, we also used the Commutative Law for each of these applications.)
 
 
 
<Math>\overline{A}B + BA + AA + B\overline{B} + A\overline{B}</Math>
 
 
 
Distributive, two places.
 
 
 
<Math>\overline{A}B + BA + A + A\overline{B}</Math>
 
 
 
Idempotent (for the A's), then Complement and Identity to remove BB.
 
 
 
<Math>\overline{A}B + AB + AT + A\overline{B}</Math>
 
 
 
Commutative, Identity; setting up for the next step.
 
 
 
<Math>\overline{A}B + A(B + T + \overline{B})</Math>
 
 
 
Distributive.
 
 
 
<Math>\overline{A}B + A</Math>
 
 
 
Identity, twice (depending how you count it).
 
 
 
<Math>A + \overline{A}B</Math>
 
 
 
Commutative.
 
 
 
<Math>(A + \overline{A})(A + B)</Math>
 
 
 
Distributive.
 
 
 
<Math>A + B</Math>
 
 
 
Complement, Identity.
 
  
==Example 16==
+
=====End of Page=====

Latest revision as of 09: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