Digital Engineering

Boolean Algebra and Logic Gates

 Describing Circuit Functionality: Inverter
● Basic logic functions have symbols
● The same functionality can be
represented with a truth table
● Truth table completely specifies outputs for all input
combinations
● This is an inverter Truth Table

● An input of 0 is inverted to a 1 A Y
● An input of 1 is inverted to a 0 0 1

1 0
A Y
Input Output
Symbol

11/10/2021 Digital Engineering 2

 The AND Gate
● This is an AND gate Truth Table

● If the two input signals A B Y

are asserted (i.e. high) the 0 0 0
output will also be asserted. 0 1 0
Otherwise, the output will 1 0 0
be deasserted (i.e. low) 1 1 1

A A B
Y
B

11/10/2021 Digital Engineering 3

 The OR Gate
● This is an OR gate A B Y
● If either of the two 0 0 0
input signals is
0 1 1
asserted, or both of
1 0 1
them are, the output
1 1 1
will be asserted
A

A
Y B
B

11/10/2021 Digital Engineering 4

 The NAND Gate
● The NAND gate is a combination of an AND gate
followed by an inverter
● NAND(A, B) → (A AND B)’

A B Y
A 0 0 1
Y
B 0 1 1
1 0 1
Y=A.B 1 1 0

11/10/2021 Digital Engineering 5

 The Universal Property of NAND
 You can implement any function using: NOT, AND, and OR.
They represent a logically complete set.
 You can use only NAND gates to implement the above three gates.
Therefore, NAND alone is a logically complete set.

NOT X X

X X.Y
AND Y

X
OR X+Y
Y

11/10/2021 Digital Engineering 6

 The NOR Gate
● A NOR gate is a combination of an OR gate followed
by an inverter
● NOR(A , B) → (A+B)’

A B Y

0 0 1
A
Y 0 1 0
B
1 0 0

Y=A+B 1 1 0

11/10/2021 Digital Engineering 7

 The Universal Property of NOR
 Similarly, you can use only NOR gates to implement NOT, AND, and
OR. Therefore, NOR alone is a logically complete set.

NOT X X

X
AND
X.Y
Y

OR X X+Y
Y

11/10/2021 Digital Engineering 8

 Exclusive-OR and Exclusive-NOR Circuits
Exclusive-OR (XOR) produces a HIGH output whenever
the two inputs are at opposite levels

11/10/2021 Digital Engineering 9

 Exclusive-NOR Circuits
Exclusive-NOR (XNOR) produces a HIGH output
whenever the two inputs are at the same level

11/10/2021 Digital Engineering 10

 XOR Function
XOR function can also be implemented with AND/OR
gates (also NANDs)

11/10/2021 Digital Engineering 11

 XOR Function
● Even function – even number of inputs are 1
● Odd function – odd number of inputs are 1

11/10/2021 Digital Engineering 12

 Describing Circuit Functionality: Waveforms
● Waveforms provide another approach for
representing functionality
● Values are either high (logic 1) or low (logic 0)
● Can you create a truth table from the waveforms?

AND Gate

x y f
0 0 0
0 1 0
1 0 0
1 1 1

11/10/2021 Digital Engineering 13

 Consider Three-input Gates
3 Input OR Gate

11/10/2021 Digital Engineering 14

 Boolean Algebra
● Useful for identifying and minimizing circuit
functionality
● Identity elements
 a+0=a
 a• 1=a
● 0 is the identity element for the + operation
● 1 is the identity element for the • operation
● The Complement: for every element ‘a’, there exists a
unique element called a’ (or ā) (complement of a) such
that :
 a + a’ = 1
 a • a’ = 0
11/10/2021 Digital Engineering 15
 George Boole (1815 - 1864)
 Father of Boolean algebra
 Boole’s system (detailed in his 'An Investigation of the
Laws of Thought, on Which Are Founded the
Mathematical Theories of Logic and Probabilities', 1854)
was based on a binary approach, processing only two
objects - the yes-no, true-false, on-off, zero-one
approach.
 Surprisingly, given his standing in the academic
community, Boole's idea was either criticized or
completely ignored by the majority of his peers.
 Eventually, one bright student, Claude Shannon
(1916-2001), picked up the idea and ran with it.

11/10/2021 Digital Engineering 16

 © 2006 Pearson Education, Inc., “Digital Fundamentals”, 9/e by Floyd

Laws of Boolean Algebra

 Commutative Law of ORing:
A+B=B+A

 Commutative Law of ANDing:

A.B=B.A

11/10/2021 Digital Engineering 17

 © 2006 Pearson Education, Inc., “Digital Fundamentals”, 9/e by Floyd

Laws of Boolean Algebra (Cont’d)

 Associative Law of ORing:

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

 Associative Law of ANDing:

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

11/10/2021 Digital Engineering 18

 © 2006 Pearson Education, Inc., “Digital Fundamentals”, 9/e by Floyd

Laws of Boolean Algebra (Cont’d)

 Distributive Law:
● Note: To simplify notation, the • operator is frequently omitted.
When two elements are written next to each other, the AND (•)
operator is implied

A(B + C) = AB + AC

11/10/2021 Digital Engineering 19

 © 2006 Pearson Education, Inc., “Digital Fundamentals”, 9/e by Floyd

Rules of Boolean Algebra

11/10/2021 Digital Engineering 20

 © 2006 Pearson Education, Inc., “Digital Fundamentals”, 9/e by Floyd

Rules of Boolean Algebra Cont’d

 Rule 1

OR Truth Table

 Rule 2

OR Truth Table

11/10/2021 Digital Engineering 21

 © 2006 Pearson Education, Inc., “Digital Fundamentals”, 9/e by Floyd

Rules of Boolean Algebra Cont’d

 Rule 3

AND Truth Table

 Rule 4

AND Truth Table

11/10/2021 Digital Engineering 22

 © 2006 Pearson Education, Inc., “Digital Fundamentals”, 9/e by Floyd

Rules of Boolean Algebra Cont’d

 Rule 5

OR Truth Table

 Rule 6

OR Truth Table

11/10/2021 Digital Engineering 23

 © 2006 Pearson Education, Inc., “Digital Fundamentals”, 9/e by Floyd

Rules of Boolean Algebra Cont’d

 Rule 7

AND Truth Table

 Rule 8

AND Truth Table

11/10/2021 Digital Engineering 24

 © 2006 Pearson Education, Inc., “Digital Fundamentals”, 9/e by Floyd

Rules of Boolean Algebra Cont’d

 Rule 9

 Rule 10 (the absorption rule): A + AB = A

11/10/2021 Digital Engineering 25

 © 2006 Pearson Education, Inc., “Digital Fundamentals”, 9/e by Floyd

Rules of Boolean Algebra Cont’d

 Rule 11: A  AB  A  B

 Rule 12: (A + B)(A + C) = A + BC

11/10/2021 Digital Engineering 26

 De Morgan’s Theorems
(by Augustus De Morgan (1806 - 1871), an English mathematician and logician)

A .B  A  B

A  B  A .B

General:
A .B . C .D  A  B  C  D
A  B  C  D  A .B . C .D

11/10/2021 Digital Engineering 27

 De Morgan’s Theorems Example

(A .B  C) (A  B.C) 
(A .B  C)  (A  B.C) 
( A.B . C)  ( A .B.C) 
( A  B). C  A .(B  C) 
A.C  B.C  A.B  A.C 
A.C  B.C  A.B

11/10/2021 Digital Engineering 28

 Copyright © The McGraw-Hill Companies, Inc.

Converting AND to OR
 Using De Morgan’s Theorems, AND can be converted to OR (with some
help from NOT)
 Consider the following gate:

To convert AND to OR
A B A B A B A B (or vice versa),
0 0 1 1 1 0 invert inputs and output.
0 1 1 0 0 1
1 0 0 1 0 1
1 1 0 0 0 1

Same as A+B
11/10/2021 Digital Engineering 29
 © 2006 Pearson Education, Inc., “Digital Fundamentals”, 9/e by Floyd

Standard Forms of Boolean Expressions

 The sum-of-product (SOP) form

Example: X = AB + CD + EF

 The product of sum (POS) form

Example: X = (A + B)(C + D)(E + F)

11/10/2021 Digital Engineering 30

 Sum-of-Products Expression
 A literal is a variable or the complement of a variable.
Examples: X , Y , X , Y

 A product term is a single literal or a logical product of two or more

literals. Examples: Z , W.X.Y , X.Y.Z , W.Y.Z

 A sum-of-products (SOP) expression is a logical sum of product terms.

Example: Z  W.X.Y  X.Y.Z  W.Y.Z 1
Z

 Every SOP expression W

X
can be realized by a Y
two-level circuit X
containing AND Y
Z
gates followed by
an OR gate W
Y
Z

11/10/2021 Digital Engineering 31

 SOP With NANDs
A
 A SOP expression can be
implemented with only B
NAND gates:
C

B
C
D
From De Morgan’s
Theorems
A

B
C

11/10/2021 Digital Engineering 32

 Function Representation Conversion

● Need to transit between a Boolean expression, a

truth table, and a circuit (symbols)
● All three formats are equivalent

Circuit Boolean
Expression

Truth
Table

11/10/2021 Digital Engineering 33

 Minterm
 For each truth-table row a product term can be defined
that evaluates to 1 only when the inputs have the
values listed in that row.
 If the product term contains each input variable exactly
once it is called a minterm
Row A B C Minterm Maxterm
0 0 0 0 A.B.C A + B + C
1 0 0 1 A.B.C A + B + C
2 0 1 0 A.B.C A + B + C
3 0 1 1 A.B.C A + B + C
4 1 0 0 A.B.C A + B + C
5 1 0 1 A.B.C A + B + C
6 1 1 0 A.B.C A + B + C
7 1 1 1 A.B.C A + B + C

11/10/2021 Digital Engineering 34

 From Truth Table to Boolean Expression
 Any logic function can be expressed algebraically by taking the OR
of all those minterms corresponding to the truth-table rows for
which the function produces a 1 output.
 Example: Majority detector.
Row A B C Minterm R
0 0 0 0 A.B.C 0
1 0 0 1 A.B.C 0
R=A.B.C+ A.B.C+ A.B.C+ A.B.C
2 0 1 0 A.B.C 0
3 0 1 1 A.B.C 1
4 1 0 0 A.B.C 0
5 1 0 1 A.B.C 1
6 1 1 0 A.B.C 1
7 1 1 1 A.B.C 1
 Alternate forms:
R = m3 + m5 + m6 + m7
R = ∑ (3, 5, 6, 7)

11/10/2021 Digital Engineering 35

 Converting to a Circuit
● Number of 1’s in truth table output column equals
AND terms for Sum-of-Products (SOP)

x y z G
0 0 0 0
0 0 1 0 ● ●
0 1 0 0 ●
G
0 1 1 1 ●
●
1 0 0 0 ●
1 0 1 0 ●
●
●
1 1 0 1
1 1 1 1

x y z
G = xyz + xyz’ + x’yz
11/10/2021 Digital Engineering 36
 Canonical Form of a Function
 A form is canonical if representation of a function in this
form is unique.

 Examples:
 Truth table representation of a function.
 Sum of minterms representation of a function.

11/10/2021 Digital Engineering 37

 Boolean vs. Ordinary Algebra
 Differences
 Distributivity of + over • holds for Boolean, but not for
ordinary algebra
x+(y • z) = (x+y) • (x+z)

 Boolean algebra does not have inverse elements for

+ or •
Thus, no subtraction or division operators

 Complement is not defined in ordinary algebra

11/10/2021 Digital Engineering 38