MODULE 2
Logic Gates and Boolean Algebra
MODULE 2
Objectives:
1. To understand basic concepts about Logic Gates and Boolean
Algebra
2. To be able to solve problems regarding Boolean Algebra
Logic Gates
3. To be able to create simpler Boolean and Logic Expressions
I
NTRODUCTION
Boolean algebra is a proper way to express and represent digital logic
equations and its logical design. Boolean algebra may be defined with a set
of elements, set of operators, and a number of assumptions and postulates.
George Boole, an Irish mathematician invented the Boolean algebra format,
rules and techniques around 1854. Boolean logic is the algebra of two binary
values. These values are 0 and 1. 0 refer for FALSE and 1 refer for TRUE.
With the dawn of modern electronics and digital systems, Boolean algebra
became the basic foundation to design digital logic circuits and machines.
LOGIC GATES AND BOOLEAN ALGEBRA Page 1
MODULE 2
B
ASIC LOGICAL OPERATORS
Logic Gates implement logic functions, these are the following:
AND GATE
The AND function gives a high output if all the inputs are high. A
dot is used to designate its operation.
Symbol& Equation: Truth table:
x x•y x y AND
y
0 0 0
0 1 0
1 0 0
1 1 1
LOGIC GATES AND BOOLEAN ALGEBRA Page 2
MODULE 2
OR GATE
The OR function states that if any input is high then the output
will be high. A plus sign used to designate its operation.
Symbol & Equation: Truth Table:
x x+y x y OR
y
0 0 0
0 1 1
1 0 1
1 1 1
LOGIC GATES AND BOOLEAN ALGEBRA Page 3
MODULE 2
NOT GATE
The NOT function states that the output is the complement
(inverted) of the input. If the input is A, the output will be Ā.
Symbol & Equation: Truth Table:
x x
x NOT
0 1
1 0
BUFFER GATE
The buffer function states that the input is similar/equivalent
to the output.
Symbol & Equation: Truth Table:
x Buffer
x x 0 0
1 1
LOGIC GATES AND BOOLEAN ALGEBRA Page 4
MODULE 2
NAND GATE
The NAND function states that it is “NOT AND” meaning it is
equivalent to the AND gate followed by NOT. If any or all of the inputs
is low, then the output will be high.
Symbol & Equation: Truth Table:
x x•y
y x y NAND
0 0 1
0 1 1
1 0 1
1 1 0
LOGIC GATES AND BOOLEAN ALGEBRA Page 5
MODULE 2
NOR GATE
The NOR function states that it is “NOT OR” meaning an OR gate
followed by a NOT gate. If any or all of the input is high, then the output
will be low.
Symbol & Equation: Truth Table:
x x+y x y NOR
y
0 0 1
0 1 0
1 0 0
1 1 0
LOGIC GATES AND BOOLEAN ALGEBRA Page 6
MODULE 2
EXCLUSIVE OR GATE
The XOR function states that any of its input is high but not
both, the output will be high. An enclosed plus sign used to designate
its
Symbol & Equation: Truth Table:
x x y XOR
xÅ y
y xy+xy 0 0 0
0 1 1
1 0 1
1 1 0
LOGIC GATES AND BOOLEAN ALGEBRA Page 7
MODULE 2
EXCLUSIVE NOR GATE
The XNOR function states that when all inputs are the same, the
output will be high. Equivalent to the XOR followed by a NOT gate.
Symbol & Equation: Truth Table:
x xÅ y xy+xy x y XNOR
y x y 0 0 1
0 1 0
1 0 0
1 1 1
LOGIC GATES AND BOOLEAN ALGEBRA Page 8
MODULE 2
B
ASIC PROPERTIES AND THEOREMS OF BOOLEAN ALGEBRA
THE COMMUTATIVE LAW
The expression can be taken in any order without changing its result.
A+B=B+A and A(B) = B(A)
THE ASSOCIATIVE LAW
The variables of the expression can be presented in any order without
changing the meaning of the expression.
A+ (B + C) = (A + B) + C and A (BC) = (AB) C
LOGIC GATES AND BOOLEAN ALGEBRA Page 9
MODULE 2
THE DISTRIBUTIVE LAW
Variables can be factored out of Boolean algebra terms and
expressions in much the same way as in classical algebra.
A(B + C) = AB + AC
DE MORGAN’S THEOREM
DeMorgan’s Theorem states that equivalent forms of NAND and
NOR expressions exist just like the equivalents for NAND and
for NOR gates.
Using De Morgan's Theorem, an OR gate with the inputs inverted is
the same as an AND gate with the output inverted (both forms are called a
NAND gate.) Using the De Morgan's Theorem for the NOR equivalent
gates, an AND gate with the inputs inverted is the same as an OR gate
with the output inverted (both forms are called a NOR gate.) The OR
and AND versions of NAND and NOR gates can be substituted for one
another.
_ _ ___ _ _
_____
A+B=AB and AB=A+B
LOGIC GATES AND BOOLEAN ALGEBRA Page 10
MODULE 2
TWO-VALUED BOOLEAN ALGEBRA
It is a set of two elements with rules of binary operators (+), (.) and
('). These binary operators represent OR, AND and NOT operations.
OTHER IMPORTANT THEOREMS
They followed the rules of gates covered in the previous pages.
• Theorem 1(a): A + A = A
A + A = (A + A).1 by postulate 2(b)
= (A + A) .( A + A′) by postulate 5
= A + A.A′
=A+0 by postulate 4
=A by postulate 2(a)
• Theorem 1(b): A . A = A
A . A = (A . A) + 0 by postulate 2(a)
= (A . A) + ( A . A′) by postulate 5
= A (A + A′)
LOGIC GATES AND BOOLEAN ALGEBRA Page 11
MODULE 2
=A.1 by postulate 4
=A by postulate 2(b)
• Theorem 2(a): A + 1 = 1
• Theorem 2(b): A . 0 = 0
• Theorem 3(a): A + A.B = A
A + A.B = A . 1 + A.B by postulate 2(b)
= A ( 1 + B) by postulate 4(a)
=A.1 by postulate 2(a)
=A by postulate 2(b)
• Theorem 3(b): A ( A + B ) = A by duality
The following is the complete list of postulates and theorems useful for
two-valuedBoolean algebra.
LOGIC GATES AND BOOLEAN ALGEBRA Page 12
MODULE 2
LOGIC GATES AND BOOLEAN ALGEBRA Page 13
