Boolean Algebra and Logic
Gates
Truth Table
Truth table is a table that contains all possible
values of logical variables/statements in a
Boolean expression.
No. of possible combination = 2n ,
where n=number of variables used in a
Boolean expression.
Truth table
• Y=X+1 Y=X+Z
X Z Y
X Y 0 0 0
0 1 0 1 1
1 1 1 0 1
1 1 1
Truth Table
Exercise
Evaluate the following Boolean expression
using Truth Table.
(a) X’Y’+X’Y
(b) X’YZ’+XY’
(c) XY’(Z+YZ’)+Z’
Logic Gates
A logic gate is an electronic circuit which
makes logical decisions, the most common
logic gates are AND, OR, NOT gates.
* The NAND and NOR gates are called as the
Universal gates.
* The exclusive OR gates is another logic gate
which can be constructed using basic gates
such as AND, OR, NOT.
Basic Logic Gates
• NOT, AND, and OR Gates
• NAND and NOR Gates
• DeMorgan’s Theorem
• Exclusive-OR (XOR) Gate
• Multiple-input Gates
NOT Gate -- Inverter
NOT X Y
X Y 0 1
1 0
Y = ~X
NOT
• Y = ~X (Verilog)
• Y = !X (ABEL)
• Y = not X (VHDL)
• Y = X’
•Y = X
•Y = X (textook)
• not(Y,X) (Verilog)
NOT
X ~X ~~X = X
X ~X ~~X
0 1 0
1 0 1
AND Gate
AND
X Y Z
X 0 0 0
0 1 0
Z
1 0 0
Y 1 1 1
Z = X & Y
AND
•X & Y (Verilog and ABEL)
• X and Y (VHDL)
V
•X Y
U
•X Y
•X * Y
• XY (textbook)
• and(Z,X,Y) (Verilog)
OR Gate
OR
X Y Z
X 0 0 0
Z 0 1 1
Y 1 0 1
1 1 1
Z = X | Y
OR
•X | Y (Verilog)
•X # Y (ABEL)
• X or Y (VHDL)
•X + Y (textbook)
•X V Y
•X U Y
• or(Z,X,Y) (Verilog)
Draw a logic circuit and truth
table for (A + B)C.
A B C Q
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 0
1 1 1 1
Draw a logic circuit for
Q=A + BC + D.
• ------------
NAND Gate
NAND
X Y Z
X 0 0 1
0 1 1
Z
1 0 1
Y 1 1 0
Z = ~(X & Y)
nand(Z,X,Y)
NAND Gate
NOT-AND
X Y W Z
X 0 0 0 1
W 0 1 0 1
Z
1 0 0 1
Y 1 1 1 0
W = X & Y
Z = ~W = ~(X & Y)
NOR Gate
NOR
X Y Z
X 0 0 1
Z 0 1 0
Y 1 0 0
1 1 0
Z = ~(X | Y)
nor(Z,X,Y)
NOR Gate
NOT-OR
X Y W Z
X 0 0 0 1
W
Z 0 1 1 0
Y 1 0 1 0
1 1 1 0
W = X | Y
Z = ~W = ~(X | Y)
Exclusive-OR Gate
XOR
X Y Z
X
Z 0 0 0
Y
0 1 1
Z = X ^ Y 1 0 1
xor(Z,X,Y)
1 1 0
XOR
•X ^ Y (Verilog)
•X $ Y (ABEL)
•X @ Y
X Y (textbook)
• xor(Z,X,Y) (Verilog)
Exclusive-NOR Gate
XNOR
X Y Z
X
Z 0 0 1
Y
0 1 0
Z = ~(X ^ Y) 1 0 0
Z = X ~^ Y 1 1 1
xnor(Z,X,Y)
XNOR
• X ~^ Y (Verilog)
• !(X $ Y) (ABEL)
•X @ Y
X Y
• xnor(Z,X,Y) (Verilog)
Draw a logic circuit and truth
table for Q=(AB)+(A+B)
Draw a logic circuit for
Q=AB + AC.
Draw a logic circuit for
Q=(A + B)(C + D)C.
• H
Multiple-input Gates
Z1 Z2
Z3 Z4
Multiple-input AND Gate
Z1
Output Z 1 is HIGH only if all inputs are HIGH
An open input will float HIGH
Multiple-input OR Gate
Z2
Output Z 2 is LOW only if all inputs are LOW
Multiple-input NAND Gate
Z3
Output Z 3 is LOW only if all inputs are HIGH
Multiple-input NOR Gate
Z4
Output Z 4 is HIGH only if all inputs are LOW
Basic Theorem of Boolean Algebra
T1 : Properties of 0 (a) 0 + A = A (b) 0 A = 0
T2 : Properties of 1 (a) 1 + A = 1 (b) 1 A = A
T3 : Commutative Law
(a) A + B = B + A
(b) A B = B A
T4 : Associate Law
(a) (A + B) + C = A + (B + C)
(b) (A B) C = A (B C)
T5 : Distributive Law
(a) A (B + C) = A B + A C
(b) A + (B C) = (A + B) (A + C)
(c) A+A’B = A+B
T6 : Indempotence (Identity ) Law
(a) A + A = A (b) A A = A
T7 : Absorption (Redundance) Law
(a) A + A B = A
(b) A (A + B) = A
T8 : Complementary Law
(a) X+X’=1
(b) X.X’=0
T9 : Involution
(a) x = x
• x+0 = x
• x+1=1
• x.1 =x
• x.x=x
• x.x=0
• x+x=1
• x+x=x
Simplify
• These properties (Laws and Theorems) can be used
to simplify equations to their simplest form.
– Simplify F=X’YZ+X’YZ’+XZ
•Reduces to F = X’Y + XZ
Circuit: Before and After
Other examples
• Examples from the text
– 1. X + XY = X·1 + XY = X(1+Y) = X·1 = X
– 2. XY+XY’ = X(Y + Y’) = X·1 = X
– 3. X+X’Y = (X+X’)(X+Y) = 1· (X+Y) = X+Y
Further Examples
• Examples from the text
4. X·
(X+Y)=X·X+X·Y=X+XY=X(1+Y)=X·1=X
–5. (X+Y) ·(X+Y’)=XX+XY’+XY+YY’=
– X+XY’+XY+0=X(1+Y’+Y)=X·1=X
– by a slightly different reduction
–6. X(X’+Y) = XX’+XY = 0 + XY = XY
T10:De Morgan's Theorem
(a) (X+Y)’=X’.Y’
(b) (X.Y)’=X’+Y’
De Morgan’s Theorem-1
(X+Y)’=X’.Y’
~(X & Y) = ~X | ~Y
• NOT all variables
• Change & to | and | to &
• NOT the result
NOR Gate
X X
Z Z
Y Y
Z = ~(X | Y) Z = ~X & ~Y
X Y Z X Y ~X ~Y Z
0 0 1 0 0 1 1 1
0 1 0 0 1 1 0 0
1 0 0 1 0 0 1 0
1 1 0 1 1 0 0 0
De Morgan’s Theorem-2
(X.Y)’=X’+Y’
~(X | Y) = ~X & ~Y
• NOT all variables
• Change & to | and | to &
• NOT the result
NAND Gate
X Z X Z
=
Y Y
Z = ~(X & Y) Z = ~X | ~Y
X Y W Z X Y ~X ~Y Z
0 0 0 1 0 0 1 1 1
0 1 0 1 0 1 1 0 1
1 0 0 1 1 0 0 1 1
1 1 1 0 1 1 0 0 0
De Morgan’s Theorem
• NOT all variables
• Change & to | and | to &
• NOT the result
• --------------------------------------------
• ~X | ~Y = ~(~~X & ~~Y) = ~(X & Y)
• ~(X & Y) = ~~(~X | ~Y) = ~X | ~Y
• ~X & !Y = ~(~~X | ~~Y) = ~(X | Y)
• ~(X | Y) = ~~(~X & ~Y) = ~X & ~Y