Boolean Algebra - Binary logic

Truth Tables and symbols

    Using truth tables to represent input and output of a gate
       NOT

       AND/NAND

       OR/NOR

       XOR/XNOR

  Note that the Boolean algebra uses different symbols than other logic
    disciplines.
 

Laws	AND	OR
Identity	1*A=A	0+A=A
Null	0*A=0	1+A=1
Idempotent	A*A=A	A+A=A
Inverse or Complementary	A*!A=0	A+!A=1
Commutative	A*B=B*A	A+B=B+A
Associative	(A*B)*C=A*(B*C)	(A+B)+C=A+(B+C)
Distributive	A+B*C=(A+B)*(A+C)	A*(B+C)=A*B+A*C
De Morgan's	!(A*B)=!A+!B	!A*!B=!(A+B)
Cancellation	!!A=A

General rule:

When given a combination of ANDs, ORs and NOTs, NOTS are applied to following input first, next statements in parens are resolved, next NOTs applied to parens, then ANDs, and finally ORs

(A+B)*(A+C)=A*A+A*C+A*B+B*C - Distribution
A*A+A*C+A*B+B*C = A+A*C+A*B+B*C - Idempotent.
A+A*C+A*B+B*C = 1*A+A*C+A*B+B*C - Identity.
1*A+A*C+A*B+B*C =A*(1+c+B)+B*C - Distribution.
A*(1+C+B) = A*(1)+B*C - Null
1*A+B*C = A+B*C - Identity

If the rule uses two inputs, the rule applies equally to a problem with more than two inputs as long as they are all structured the same.

The following truth tables show that deMorgan's rule works for a three gate statement. !(A+B+C)=!A*!B*!C

A	B	C	!A	!B	!C	(A+B+C)	!(A+B+C)	!A*!B*!C
0	0	0	1	1	1	0	1	1
0	0	1	1	1	0	1	0	0
0	1	0	1	0	1	1	0	0
0	1	1	1	0	0	1	0	0
1	0	0	0	1	1	1	0	0
1	0	1	0	1	0	1	0	0
1	1	0	0	0	1	1	0	0
1	1	1	0	0	0	1	0	0

The absorption rule can be proved by applying the simpler rules.

Absorption Proof

A*(A+B) = A

A*(A+B) = A*A+A*B	Distributive
A*A+A*B = A+A*B	Idempotent
A+A*B = A*1+A*B	Identity
A*1+A*B = A*(1+B)	Distributive
A*(1+B) = A*(1)	Null
A*1 = A	Identity

More complex circuits.

   OR from 4 NANDs   !(!(A*A)*!(B*B)) = A+B




A  B
 |
A*A
|
!(A*A)
|
B*B
|
!(B*B)
|
!(A*A) * !(B*B)
|
!( !(A*A) * !(B*B))

-----
+
-----
+
-------
+
-----
+
--------
+
----------------
+
--------------------

0  0
|
0
|
1
|
0
|
1
|
1
|
0

0  1
|
0
|
1
|
1
|
0
|
0
|
1

1  0
|
1
|
0
|
0
|
1
|
0
|
1

1  1
|
1
|
0
|
1
|
0
|
0
|
1

AND from NORs  !(!(A+A)+!(B+B)) = A*B
  

    
!(!(A+A)+!(B+B)) = !(!A+!B)
Idempotent
    
!(!A+!B) = !(!(A*B))         
DeMorgan
    
!!(A*B)  = A*B               
Cancellation
  

XOR   !(A*B)*(A+B) or !A*B+A*!B
  

  
!(A*B)*(A+B) = (!A+!B)*(A+B)
deMorgan
  
(!A+!B)*(A+B) = !A*A+!B*A+!A*B+!B*B
Distribution
  
!A*A+!B*A+!A*B+!B*B = 0+!B*A+!A*B+0
Inverse
  
0+!B*A+!A*B+0 = !B*A+!A*B
Identity
  

   Both logically and with physical electronic, it is often easier to 
     work with the inverted version of a logic gate.
 
https://www.allaboutcircuits.com/textbook/digital/chpt-7/boolean-algebraic-properties/

Practice problems (Try before looking at answers) :

Click on problem for solution.


C+!(B*C) = 1

!(A*B)*(!A+B) = !A

(A+C)*(A*D+A*!D)+A*C+C = A+C

A*(A+C)+(A+B)(A+!B) = A


Complex circuits