Difference between revisions of "Boolean Algebra"

From TRCCompSci - AQA Computer Science
Jump to: navigation, search
(AND Identities)
(Boolean Laws)
 
(237 intermediate revisions by 28 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> A.1 = A </math>
  
<math> \overline{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.
  
is
+
<math> 0.A = 0 </math>
  
<nowiki> <math> \overline{a} </math></nowiki>
+
Because there is a 0 in this equation, the output of this will always be 0 regardless of the value of A.
  
<math> \overline{\overline{a}+b}</math>
+
<math> A.A = A</math>
  
is
+
The output is determined by A alone in this equation. This can be simplified to just "A".
  
<nowiki> <math> \overline{\overline{a}+b} </math></nowiki>.
+
<math> A.\overline{A}=0 </math>
  
=Identities=
+
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.
==AND Identities==
 
  
The logic gate AND is represented by the "." symbol. Some examples of an equation containing this operation is:
+
===Using OR===
 +
<math> 0+A = A </math>
  
<math> A.B </math>
+
0 or A can be simplified as just A.
  
This expression means "A AND B = 1".
+
<math> 1+A = 1 </math>
  
<math> \overline{A.B} </math>
+
1 or A can be simplified as just 1.
  
The line above the equation means "NOT", therefore this expression means " NOT A AND B = 1".
+
<math> A+A=A</math>
  
==OR Identities==
+
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===
 +
<youtube>https://www.youtube.com/watch?v=Cdqj4XDsUVY</youtube>
 +
 
 +
https://www.youtube.com/watch?v=Cdqj4XDsUVY
  
=Laws=
 
 
==Commutative Law==
 
==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==
 
==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==
 
==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==
 
==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>
 +
 +
<hr>
 +
 +
===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>
 +
 +
<hr>
 +
===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>
 +
 +
<hr>
 +
===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==
 
==Identity Law==
 +
This is also in the identities section:
 +
 +
<math> A.A = A </math>
 +
 +
<math> A+A = A </math>
  
 
==Negation Law==
 
==Negation Law==
 +
Just like in any other logic negating a negative is a positive so:
 +
 +
<math> \overline{ \overline{A} } = A </math>
  
=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===
 +
<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>
  
==Example 1==
+
------------------------------------
 +
<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
  
==Example 2==
+
<math> X + X.\overline{Y} + Y.X + 0 </math>  Use of <math> X.X = X </math> and <math> Y.\overline{Y} = 0 </math>
  
==Example 3==
+
<math> X + X(\overline{Y}+Y) </math> Taking X out of the brackets
  
==Example 4==
+
<math> X + X(1) </math> Use of <math> Y + \overline{Y} = 1 </math>
  
==Example 5==
+
<math> X(1) </math>
  
==Example 6==
+
<math> X </math>
  
==Example 7==
+
=====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

A.1=A

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

0.A=0

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

A.A=A

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

A.¯A=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.

Using OR

0+A=A

0 or A can be simplified as just A.

1+A=1

1 or A can be simplified as just 1.

A+A=A

A or A can be simplified as just A.

¯A+A=1

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

A+B=B+A

or

A.B=B.A

Associate Law

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

A+(B+C)=B+(A+C)

A+(B+C)=B+(A+C)

A+(B+C)=C+(A+B)

So:

A.(B.C)=B.(A.C)

A.(B.C)=B.(A.C)

A.(B.C)=C.(A.B)

Distributive Law

The distributive law is these two equations.

A.(B+C)=A.B+A.C

A+(B.C)=(A+B).(A+C)

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

A.B+A.C=A.(B+C)

A+B.A+C=A+(B.C)

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

A.(A+B)=(0+A).(A+B)

A+(A.B)=(1.A)+(A.B)

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 :

A+(¯A.B)=A+B

Proof :

=A+(¯A.B)=A+B=(A+¯A)(A+B)=1.(A+B)=A+B


Law 2:

A.(¯A+B)=A.B

Proof :

=A.(¯A+B)=A.¯A+A.B=0+A.B=A.B


Law 3:

A.(A+B)=A

Proof using distributive law:

A.(A+B)=(0+A).(A+B)

So: A+(0.B)

So: A+0=A


Law 4:

A+(A.B)=A

Proof using distributive law:

A+(A.B)=(1.A)+(A.B)

So: A.(1+B)

So: A.1=A

Identity Law

This is also in the identities section:

A.A=A

A+A=A

Negation Law

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

¯¯A=A

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

𝐶+(𝐶.𝐷)


Take out the common factor C:

(C.D)+(C.1)=C.(D+1),

We know that 1+A=1,

Therefore, C.1,

Use identity A.1=A,

Answer = C


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

𝐵.(𝐴+¯𝐵)


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

ANSWER = NOT B

Example 4

𝑋.(¯𝑋+𝑌)


𝑋.¯𝑋=0

0+𝑌=𝑌

Example 5

𝑋.(X+¯Y)


(0+𝑋).(X+¯Y)

𝑋+(0.¯Y)

𝑋+(0)

𝑋

Example 8

𝐷.𝐸+𝐸.¯𝐷


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

Example 13

(¯A+¯B).B


Expand the brackets: (¯A.B)+(¯B.B)

Not B AND B = 0: ¯A.B)+(0)

Something OR 0 is Something: ¯A.B

Example 14

¯B+(A.B)


(B) + (A.B) Distributive Law. (B + A) . (B + B) Not B cancels out. B + A . 1 = B+A


Example 19

(X+Y).(X+¯Y)



Distributive:
X.(Y+¯Y)
Identity laws:
Y+¯Y=1

X.1=X

Alternative

X.X+X.¯Y+Y.X+Y.¯Y Expanding the brackets

X+X.¯Y+Y.X+0 Use of X.X=X and Y.¯Y=0

X+X(¯Y+Y) Taking X out of the brackets

X+X(1) Use of Y+¯Y=1

X(1)

X

End of Page