10/18/2023

Functions
• Computers take inputs and produce outputs, just like functions in
math!
An expression is A function table is
finite but not unique unique but infinite
f(x,y) = 2x + y x y f(x,y)
=x+x+y 0 0 0
= 2(x + y/2) … … …
2 2 6
= ... … … …
23 41 87
… … …

• Logical functions can be expressed in two ways:

• A finite, but non-unique Boolean expression.
• A truth table, which will turn out to be unique and finite.
5

Basic Boolean operations

• There are three basic operations for logical values.

Operation: AND (product) OR (sum) of NOT (complement)

of two inputs two inputs on one input

Expression: xy, or xy x+y x’ or 𝑥̅

Result: x y xy x y x+y x x’
0 0 0 0 0 0 0 1
0 1 0 0 1 1 1 0
1 0 0 1 0 1
1 1 1 1 1 1

3
 10/18/2023

Advance Boolean operations

• There are three advance operations for logical values.

Operation: NAND NOR XOR

of two inputs of two inputs of two inputs

Expression:
(xy)’, or
(x + y)’ or 𝑥 + 𝑦 xy
(xy)’, or 𝑥𝑦
Result: x y (xy)’ x y (x+y)’ x y xy

0 0 1 0 0 1 0 0 0
0 1 1 0 1 0 0 1 1
1 0 1 1 0 0 1 0 1
1 1 0 1 1 0 1 1 0

More than Two Inputs

(b) Boolean Operators Extended to More than Two Inputs (A, B, . . .)

Operation Expression Output = 1 if

AND A•B•… All of the set {A, B, …} are 1.
OR A+B+… Any of the set {A, B, …} are 1.
NAND A  B… Any of the set {A, B, …} are 0.
NOR A + B+ … All of the set {A, B, …} are 0.
XOR AB… The set {A, B, …} contains an
odd number of ones.

4
 10/18/2023

The Inverter (NOT gate) INPUT OUTPUT

X X’ X X’

LOW(0) HIGH(1)

HIGH(1) LOW(0)

Example waveforms:

X
X’

The inverter performs the Boolean NOT operation. When the input is
LOW, the output is HIGH; when the input is HIGH, the output is LOW.

The AND gate

A X=A.B
B

The AND gate produces a HIGH output when all inputs are HIGH;
otherwise, the output is LOW. For a 2-input gate, the truth table is
Example waveforms:
A B X
A
0 0 0
B 0 1 0
1 0 0
X 1 1 1

9
 10/18/2023

The OR gate A X
B

The OR gate produces a HIGH output if any input is HIGH; if all inputs
are LOW, the output is LOW. For a 2-input gate, the truth table is

Example waveforms: A B X
A
0 0 0
B
0 1 1
1 0 1
X 1 1 1

Logic Gates
Logic Gates

AND GATE OR GATE

1 AND 0 = 0 1 OR 0 = 1
20

10
 10/18/2023

Logic Gates
Logic Gates
• Another very useful gate is the exclusive OR (XOR)
gate.
• The output of the XOR operation is true only when
the values of the inputs differ.

Note the special symbol 

for the XOR operation.

21

Logic Gates
Logic Gates

XOR GATE XOR GATE

1 XOR 0 = 1 1 XOR 1 = 0
22

11
 10/18/2023

Logic Gates
Logic Gates
• NAND and NOR are
two very important
gates. Their
symbols and truth
tables are shown at
the right.

23

Logic Gates
Logic Gates
• NAND and NOR are
known as universal
gates because they are
inexpensive to
manufacture, and any
Boolean function can be
constructed using only
NAND or only NOR
gates.
• NAND and NOR gates
require only 2 transistors
• AND and OR gates
need 3 transistors!

24

12
 10/18/2023

NOR Gate: An universal gate

Logic Gates
Logic Gates
• Gates can have multiple inputs and more than one
output.
• A second output can be provided for the complement
of the operation.
• We’ll see more of this later.

26

13
 10/18/2023

Digital Components
Logic Gates and Circuit
• The main thing to remember is that combinations of
gates implement Boolean functions.
• Any Boolean function can be converted into a circuit in a
relatively straightforward way.
• The circuit below implements the Boolean function:

27

Engineering Design Process

14
 10/18/2023

Formal definition of Boolean algebra

• The axioms below must always be true
• The magenta axioms deal with the complement operation
• Blue axioms (especially 15) are different from regular
algebra
1. x+0=x 2. x1=x
3. x+1=1 4. x0=0
5. x+x=x 6. xx=x
7. x + x’ = 1 8. x  x’ = 0
9. (x’)’ = x
10. x+y=y+x 11. xy = yx Commutative
12. x + (y + z) = (x + y) + z 13. x(yz) = (xy)z Associative
14. x(y + z) = xy + xz 15. x + yz = (x + y)(x + z) Distributive
16. (x + y)’ = x’y’ 17. (xy)’ = x’ + y’ DeMorgan’s
31

Are these axioms for real?

• We can show that these axioms are valid, given the definitions of
AND, OR and NOT
x y xy x y x+y x x’
0 0 0 0 0 0 0 1
0 1 0 0 1 1 1 0
1 0 0 1 0 1
1 1 1 1 1 1

• The first 11 axioms are easy to see from these truth tables alone.
For example, x + x’ = 1 because of the middle two lines below
(where y = x’)

32

16
 10/18/2023

Let’s compare the resulting circuits

• Here are two different
but equivalent
circuits.
• In general, the one
with fewer gates is
“better”:
• It costs less to
build
• It requires less
power
• But we had to do
some work to find
the second form
35

Some more laws

• Here are some more useful laws.
1. x + xy = x 4. x(x + y) = x
2. xy + xy’ = x 5. (x + y)(x + y’) = x
3. x + x’y = x + y 6. x(x’ + y) = xy

• We can prove these laws by either

• Making truth tables:
x y x’ x’y x + x’y x y x+y
0 0 0 0 0
0 1 0 1 1
1 0 1 0 1
1 1 1 1 1
• Using the axioms:
x + x’y = (x + x’)(x + y) [ Distributive ]
= 1  (x + y) [ x + x’ = 1 ]
=x+y [ Axiom 3 ]
36

18
 10/18/2023

Simplification
• 1. Simplification the following expressions:
• F=C + BC

• F=(A + B) (A + C)

• F= ABC+ AB’C + ABC’

• 2. Draw a network to realize the following by using two OR gates and
two AND gates

F  (V + W + X )(V + X + Y )(V + Z )

Solution of Problem 1.3

F = ABC+ ABC + AB’C + ABC’ = AC(B+B’) + AB(C+C’) = AC + AB

Solution of problem 2
L.H.S.=(V+X+W)(V+X+Y)(V+Z)
=[(V+X)+W(V+X)+Y(V+X)+WY](V+Z)
=[(V+X)(1+W+Y)+WY](V+Z)
=(V+X+WY)(V+Z)
This can be implemented by two OR gates and two
AND gate.
38

19
 10/18/2023

Simplification
• Sum-of-Product
• Minterm

• Product-of-Sum
• Maxterm

• KARNAUGH MAP MINIMIZATION

Minterms
• Consider variables A and B
• Assume that they are somehow combined with AND
operator
• There are 4 possible combinations
AB, A' B, AB ' , A' B '
• Each of those terms is called a minterm (standard product)
• In general, if there are n variables, there are 2
minterms- exactly equal number of rows in truth table

40

20
 10/18/2023

Exercise
• List the minterms for 3 variables

A B C Minterm Designation
0 0 0 A ' B ' C' m0

0 0 1 A'B'C m1

0 1 0 A ' B C' m2

0 1 1 A'B C m3

1 0 0 A B ' C' m4

1 0 1 A B'C m5

1 1 0 A B C' m6

1 1 1 A B C m7

41

Maxterms
• Consider variables A and B
• Assume that they are somehow combined with OR
operator
• There are 4 possible combinations
A + B, A' + B, A + B' , A' + B '

• Each of those terms is called a maxterm (standard sums)

• In general, if there are n variables, there are 2
maxterms - exactly equal number of rows in truth table

42

21
 10/18/2023

Exercise
• List the maxterm for 3 variables

A B C Maxterm Designation
0 0 0 A+B+C M0

0 0 1 A+B+C' M1

0 1 0 A+B'+C M2

0 1 1 A+B'+C' M3

1 0 0 A'+B+C M4

1 0 1 A'+B+C' M5

1 1 0 A'+B'+C M6

1 1 1 A'+B'+C' M7

Sum-of-Products
• When two or more product terms are summed by Boolean
addition, the resulting expression is a sum-of-product (SOP).
• An SOP expression can contain a single variable term.
• In an SOP expression, a single overbar (complement) cannot
extend over more than one variable.

𝐴𝐵 + 𝐶𝐷 𝐸 + 𝐴𝐶 𝐸 YES
𝐴𝐵𝐶 + 𝐴𝐵 𝐶 + 𝐴𝐵𝐶 YES
(𝐴 + 𝐵)𝐶𝐷 + 𝐸𝐹 NO
𝐴 + 𝐵 + 𝐶 + 𝐷 𝐸 + (𝐴𝐶) NO

44

22
 10/18/2023

Sum-of-Products (SOP)
• Implementation of an SOP Expression simply requires
ORing the outputs of two or more AND gates.

AB ' + CD ' E + AC ' E '

A
B'
C
D'
E
A
C'
E'

Standard SOP expression

• A standard SOP expression is one in which all the variables in the
domain appear in each product term of the expression. In other
words, standard SOP expression only contains minterms.
𝐴𝐵 + 𝐶𝐷 𝐸 + 𝐴𝐶 𝐸 NO
𝐴𝐵𝐶 + 𝐴𝐵 𝐶 + 𝐴𝐵𝐶 YES

• A nonstandard SOP expression is converted into standard form using

Boolean algebra rule: (𝐴 + 𝐴 = 1).

23
 10/18/2023

Example
• Convert the following Boolean expression into standard SOP form:
• 𝐴𝐵 𝐶+ 𝐴 𝐵 + 𝐴𝐵𝐶

• Solution: Domain of the expression 𝐴, 𝐵, 𝐶

• 𝐴 𝐵 = 𝐴 𝐵 𝐶 + 𝐶 = 𝐴 𝐵 𝐶 + 𝐴 𝐵 𝐶′
• => 𝐴𝐵 𝐶+ 𝐴 𝐵 + 𝐴𝐵𝐶 = AB C+ 𝐴 𝐵 𝐶 + 𝐴 𝐵 𝐶 + 𝐴𝐵𝐶
• = ∑ 𝑚 + 𝑚 + 𝑚 + 𝑚 = ∑(0,1,5,6)

Product-of-Sums (POS)
• When two or more sum terms are multiplied, the
resulting expression is a product-of-sum (POS).
• A POS expression can contain a single variable term.
• In a POS expression, a single overbar (complement)
cannot extend over more than one variable.

( A + B ' )(C + D ' + E )( A + C ' + E ' ) YES

AB 'C ( D ' + E ) YES

( A + B)(C + D) + EF NO
48

24
 10/18/2023

Product-of-Sums (POS)
• Implementation of a POS Expression simply requires
ANDing the outputs of two or more OR gates.

( A + B ' )(C + D ' + E )( A + C ' + E ' )

A
B'
C
D'
E
A
C'
E'

49

Standard POS expression

• A standard POS expression is one in which all the variables in the
domain appear in each sum term of the expression. In other words,
standard SOP expression only contains maxterms.
(𝐴 + 𝐵 )(𝐶 + 𝐷 + 𝐸)(𝐴 + 𝐶 + 𝐸 ) NO
(𝐴 + 𝐵 + 𝐶)(𝐴 + 𝐵 + 𝐶)(𝐴 + 𝐵 + 𝐶 ) YES

• How we convert into standard POS expression ? A nonstandard SOP

expression is converted into standard form using Boolean algebra
rule: 𝐴 + BC = (A + B)(A + C).

25
 10/18/2023

Example
• Convert the following Boolean expression into standard POS form:
• (𝐴 + 𝐵 + 𝐶 )(𝐵 + 𝐶)(𝐴 + 𝐵 + 𝐶 )
• Solution: Domain of expression is A,B,C
• 𝐵 + 𝐶 = AA + B + C = (A + B + C)(A + B + C)

• => (𝐴 + 𝐵 + 𝐶 )(𝐵 + 𝐶)(𝐴 + 𝐵 + 𝐶 )= 𝐴 + 𝐵 + 𝐶 𝐴 + 𝐵 + 𝐶 (A +

B + C) A + B + C = ∏ 𝑀 + 𝑀 + 𝑀 + 𝑀 = ∏(2,3,4,6)

Equivalent Logic Expressions

• All Boolean expressions, regardless of their form, can be converted
into either of two standard forms: the SOP form or the POS form
• Standardization makes the evaluation, simplification, and
implementation of Boolean expressions much more systematic and
easier.

• Two equivalent logic expressions can be derived from Truth Table:

• SOP
• POS

26
 10/18/2023

Rules for deriving SOP expressions

• Find each row in TT for which output is 1 (rows 1 & 4).

• For those rows, write a minterm of all input variables.

• OR together all minterms found in step 2.

Rules for deriving POS expressions

• Find each row in TT for which output is 0 (rows 2 & 3).

• For those rows, write a maxterm of all input variables.

• AND together all maxterms found in step 2.

27