Chapter 3 Combinational Circuits

Boolean Algebra

• A branch of mathematics and it can be used to describe the manipulation and processing of binary information.
• Boolean algebra is algebra for the manipulation of ojects that can take only two values: True & False
• Normally we will interpret the digital value 0 as false and digital value 1 as true.
• A Boolean algebra have two binary operation which is commonly denoted by + and ·,besides that it is a unary operation, usually denoted by ¯ or ~ or '.
•  x + x' = 1 and x·x' = 0

Truth Table

• A truth table shows how a logic circuit's output responds to various combinations of the inputs, using logic 1 for true and logic 0 for false. 
• The output can be achieved by a combination of logic gates.

Basic Logic Gates

• Basic logic diagram is a graphical representation of a logic circuit that shows the wiring and connections of each individual logic gate, represented by a specific graphical symbol,that implements the logic circuit.
• There are many types of logic gates but we are here just show few logic gates.

Multi input Logic Gate

Combination of AND gates

Boolean Expression

	AND Form	OR Form
Identity Law	A.1=A	A+0=A
Zero and One Law	A.0=0	A+ 1=1
Inverse Law	A.A’=0	A+A’=1
Idempotent Law	A.A=A	A+A=A
Commutative Law	A.B=B.A	A+B=B+A
Associative Law	A.(B.C)=(A.B).C	A+(B+C)=(A+B)+C
Distributive Law	A+(B.C)=(A+B).(A+C)	A.(B+C)=(A.B)+(A.C)
Absorption Law	A(A+B)=A	A+A.B=A A+A’B=A+B
DeMorgan’s Law	(A.B)’=A’+B’	(A+B)’=A’.B’
Double Complement Law	(X’)’=X

For example:
Simplify the following Boolean expression

1. XY′Z′+XY′Z′W+XZ′

= XY'Z'(1+W)+XZ'
= XY'Z'+XZ'                        (because (1+W)=1)
= XZ'(Y'+1)                      
= XZ'                                  (because (Y'+1)=1)

2.(X+Y)(Y+Z)(X'+Z)
= (XY+XZ+YY+YZ)(X'+Z)
= XX'Y+XX'Z+X'YY+X'YZ+XYZ+XZZ+YYZ+YZZ
= X'Y+X'YZ+XYZ+XZ+YZ+YZ                 (because XX'=0,YY=Y,andZZ=Z)
= X'Y(1+Z)+XZ(Y+1)+YZ                        (because YZ+YZ=YZ)
= X'Y+XZ                                              (because 1+Z=1 and Y+1+1)

Boolean Equation Forms
All boolean equation can be divided into 2 forms which is:
a) Sum of product(SOP)
eg:
1. F = A+AB+ABC'
2. F = X+YZ+XZ
3. F = XY+YZ+X'Z

b) Product of sum(POS)
eg:
1. F = (A+B)(B+C)(C+D)
2. F = (X'+Y')(X+Z')(Y+Z)

De Morgan's Law

 A * B = A + B

Proof:

x ∈ (A ∩ B)' 
x ∉ A ∩ B
x ∉ A or x ∉ B
x ∈ A' or x ∈ B' 
x ∈ A' ∪ B' 
(A ∩ B)' = A' ∪ B'
Therefore, (A.B)'= A'+B' 


A + B = A * B

Proof:

x ∈ (A ∪ B)' 
x ∉ A ∪ B
x ∉ A and x ∉ B
x ∈ A'  and x ∈ B' 
x ∈ A' ∩ B' 
(A ∪ B)' = A' ∩ B' 
Therefore, (A + B)' = A' * B'