DC 02

Digital Circuits License: https://creativecommons.org/licenses/by-nc-nd/4.
0/
Boolean Algebra
George Boole (1815-1864) English mathematician and philosopher.
 Defined on the set B = {0,1} a • b (AND) a + b (OR) Complement

 Binary operators: AND, OR { • , + } b b a a'
0 1 0 1
 Unary operation: Complement (NOT) {'} a a (a)
Another symbol for the NOT operator: a 0 0 0 0 0 1 0 1
1 0 1 1 1 1 1 0
Axioms (Laws):
For any a, b ∈ B •: AND +: OR
1. Closure: a+b∈B a•b∈B
2. Commutative: a+b=b+a a•b=b•a
3. Associative: a + (b + c) = (a + b) + c a • (b • c) = (a • b) • c
4. Identity: a+0=a a•1=a
5. Distributive: a + (b • c) = (a + b) • (a + c) a • (b + c) = (a • b) + (a • c)
6. Inverse: a+a=1 a•a=0
Order of operations (operator precedence) from highest to lowest precedence:
1. Parentheses, 2. NOT (Complementation) (Negation), 3. AND, 4. OR
http://akademi.itu.edu.tr/en/buzluca/ 2.1
http://www.buzluca.info 2011 - 2024 Feza BUZLUCA
Digital Circuits
The Duality principle:

• To obtain the dual of a logic expression: Replace • by +, + by •, 0 by 1, and 1 by 0,
but do not change the variables.
a + b + 0 ... ⇔ a • b • 1 ...
Example: The dual of the expression a + a⋅b is a⋅(a+b) .
Principle: Duals of all proven theorems are also theorems.
• Given a Boolean algebra identity, another identity can be obtained by taking the
dual of both sides of the identity.
Note that in the previous slide, axioms were presented with their duals (in two
columns).
Example:
Absorption theorem (given in the next slide):
If we can prove the theorem a + a⋅b = a, then its dual a⋅(a+b) = a is also true.
General Duality Principle:
f (X1, X2, ..., Xn, 0, 1, +, •) ⇔ fD(X1, X2 ,..., Xn, 1, 0, •, +)
• Duality establishes a relationship between proofs of theorems.
• Duals are not equal.
Digital Circuits
Theorems:
• These theorems are derived from the operations and axioms of Boolean algebra.
• They can be proven using the axioms.
1. Annihilator (or Dominance):

a+1=1 a•0=0
2. Involution: (a')' = a or a = a
3. Idempotency:
a+a+a+….+a = a a•a•a •… •a = a
4. Absorption: (Proof in 2.4)
a + a⋅b = a a⋅(a+b) = a
5. De Morgan's Theorem: Augustus De Morgan, British mathematician and logician (1806 – 1871)
(a + b) = a • b (a • b) = a + b
5. General form of De Morgan's Theorem:
f (X1, X2, ..., Xn, 0 ,1, + , •) = g(X1, X2 ,..., Xn, 1 , 0, •, +)
• It establishes a relationship between AND and OR (• and +).
Digital Circuits
Proving the theorems:

a) Using Axioms
Example:
Theorem: · ·
Proof:
Distributive · · ·
Inverse (Complement) · · 1
Identity · 1 
Example:
Theorem: X+X•Y = X (Absorption)
Proof:
Identity X + X•Y = X•1 + X•Y
Distributive X•1 + X•Y = X • (1 + Y)
Annihilator X • (1 + Y) = X • (1)
Identity X • (1) = X
Digital Circuits
Proving the theorems:
b) Using truth tables
Note that to denote negation (NOT), we can also use the notation A.
Example: De Morgan's Theorem

X Y X Y (X + Y) X • Y
(X + Y) = X • Y
0 0 1 1 1 1
0 1 1 0 0 0
1 0 0 1 0 0
1 1 0 0 0 0
X Y X Y (X • Y) X + Y
(X • Y) = X + Y
0 0 1 1 1 1
0 1 1 0 1 1
1 0 0 1 1 1
1 1 0 0 0 0
Although truth tables may contain many rows, computer programs can fill in
and compare these tables very quickly.
Digital Circuits
Minimizing logic expressions using axioms and theorems:

Minimizing a logic expression means:
• finding the shortest expression
• with the fewest operations and variables
• that generates the same output values as the original expression.
Example:
Z , , = · · · · · · · · Original expression
=
=
=
For simplicity, we usually omit
= the AND operator "·" between
= single-letter literals.
=
=
=
=
=
= Minimized expression
Digital Circuits License: https://creativecommons.org/licenses/by-nc-nd/4.0/
Logic (Boolean) Expressions

• A logic expression is a finite combination of variables, constants, and operators
that are well-formed according to the rules.
• It is represented as E(X), where X= (x1, x2, .... xn) ∈ Bn and each xi ∈ {0,1}.
Bn is the set of vectors
Examples: with n binary variables.
E , , , (The AND operators are not shown)
E , , ̅
E , , , ̅ ̅
• If E1 and E2 are logic expressions, then , , , · , and all possible
combinations are also logic expressions.
Literal:
• In a Boolean expression, each separate occurrence of a variable, either in
normal (uncomplemented) or inverse (complemented) form, is a literal.
For example, the expression E , , ̅ has three variables ( , , ) and
contains four literals ( ̅ ).
However, two of the literals are identical ( appears twice).
Digital Circuits
Normal forms of logic expressions:

• Each logic expression can be written in two special forms.
1. Disjunctive normal form (DNF): ΣΠ
Logic sum of logic products (SOP). OR of ANDs.
Example: ̅
The OR (logic sum) operation is also called logical disjunction.
2. Conjunctive normal form (CNF): ΠΣ
Logic product of logic sums (POS). AND of ORs.
Example: ̅
The AND (logic product) operation is also called logical conjunction.
• Any logic expression can be written in CNF (POS form) and DNF (SOP form).
• Any expression in CNF can be converted to DNF and vice versa (ΣΠ ↔ ΠΣ).
Conventions:
• Write the literals in the terms in alphabetical order: ̅ (not ̅ )
• Write the expression starting with the term that has the fewest (or the most)
literals, and then proceeding in ascending (or descending) order of literals per
term, such as: ̅ ̅ or ̅ ̅
Digital Circuits
Value of a logic expression:
• An expression, E(X), generates for each combination of the input vector

X=(x1, .... xn), a value from the set of B={0,1}.
• These values constitute the truth table for the expression.
Example: E(X) = x1x2 + x3

Truth table for the expression
X= x1 x2 x3 E(X)
0 0 0 0 Set of all input Combinations for which
combinations (X) E(X) generates ‘1’
0 0 1 1 (combinations E(X) covers)
0 1 0 0
0 1 1 1
1 0 0 0 Combinations 000 001
1 0 1 1 for which E(X) 010 011
1 1 0 1 generates ‘0’ 100 101
1 1 1 1 111 110
Digital Circuits
Applying axioms and theorems to expressions

• The axioms and theorems of Boolean algebra defined for binary values are also
valid for expressions due to the closure property.
Remember: According to the closure property, the value generated by an
expression E is a binary value, i.e., E(X) ∈ B = {0,1}
Examples:
• Identity: E(X) + 0 = E(X) E(X) • 1 = E(X)
Example: E a, b, c, d bc ad ab
E a, b, c, d 0 bc ad ab 0 bc ad a 0 b 0
bc ad ab E a, b, c, d √
-----------------------------------------------------------------------------------------------------------------------
E a, b, c, d · 1 bc ad ab · 1 bc1 ad1 ab1

bc ad ab E a, b, c, d √
• Annihilator (or Dominance): E(X) + 1 = 1 E(X) • 0 = 0
E a, b, c, d 1 bc ad ab 1 1√
-----------------------------------------------------------------------------------------------------------------------
E a, b, c, d · 0 bc ad ab · 0 0√
Digital Circuits
"Order Relation" between binary vectors:

To explain some properties of logic expressions, we can define and use the
following two order relations "< " and "≤ ":
1. An order relation "<" between elements of set B = {0,1}: 0 < 1
• Read as "0 precedes 1" or "0 is smaller than 1".
2. A partial order relation " ≤ " between X ∈ Bn vectors can be defined as follows:
• If each component of X1 is smaller than (precedes) or equal to the
component of vector X2 in the corresponding position, then X1 ≤ X2.
Example:
X1=1001 , X2 = 1101 then X1 ≤ X2.
• The partial order relation "≤" may not exist between all vectors.
Example:
X1 = 0011 , X2 = 1001
There is no order relation between X1 and X2.
Neither X1 ≤ X2 nor X2 ≤ X1 is true.
Digital Circuits
A partial order relation between expressions:

• E(X) ≤ F(X) denotes that values of E generated by combinations of input X are always
smaller than (or equal to) all values of F generated by the same input combinations.
Example : Combinations for which

Set of all input F(X) generates ‘1’
x1 x2 x3 E(X) F(X) combinations (X) (combinations F(X) covers)
0 0 0 1 = 1
0 0 1 0 = 0
Combinations
0 1 0 1 = 1
F for which E(X)
0 1 1 0 < 1 001
generates ‘1’
1 0 0 0 < 1 101 011 (combinations
E
1 0 1 0 = 0 100 000 E(X) covers)
1 1 0 0 = 0 110 010
1 1 1 1 = 1 111
• For each input combination where E(X)

generates "1", F(X) also generates "1". If E(X) ≤ F(X),
• This is a special case. The order E(X) implies F(X), E(X)F(X),
relation ≤ may not exist between all F(X) covers E(X).
expressions (see slide 2.15).
Using the order relation to show absorption properties of expressions
• Remember: The theorems given for binary values on slide 2.3 are also valid for
expressions due to the closure property.
Consequently, the absorption theorem given for binary values (a + a⋅b = a and
a⋅(a+b) = a) is also valid for expressions because of the closure property.
• However, the partial order relation ≤ makes it easier to grasp the absorption
properties of expressions.
• Since absorption is an important theorem used to simplify expressions, we will
again illustrate this theorem using the order relation ≤.
• We will consider two cases.
o Case A: Special case: E(X) ≤ F(X) (as in the example on slide 2.12)
o Case B: General case: The order relation ≤ does not exist between E(X) and F(X)
Digital Circuits
Using the order relation to show absorption properties of expressions (cont'd)

CASE A: Special case: E(X) ≤ F(X)
Absorptions: 001 F
1. E(X) + F(X) = F(X) 101 011
E
2. E(X) • F(X) = E(X) 110 100 000
010
Example: 111
Consider the example given on slide 2.12.
Absorption properties (1 and 2) can be seen on the diagram on the right.
Expressions for the functions on slide 2.12:
E , , · · · , F , , · · ·
Absorptions: E(X) F(X)
1. E(X) + F(X) = · · · · · ·
= · · · = F(X)
2. E(X) • F(X) = · · · · · · ·
= · · · = E(X)
Digital Circuits
Using the order relation to show absorption properties of expressions (cont'd)

Case B: General case: The order relation ≤ does not exist between E(X) and F(X)
The following inequalities are always true for
any E and F (as can be seen on the diagram on
F the left):
E E⋅F ≤ E ≤ E+F
E⋅F ≤ F ≤ E+F
• Absorption properties of expressions follow directly from these inequalities
(we can generalize the absorption theorems for Boolean variables and apply
them to expressions due to the closure property):
Absorption Properties of expressions:
·$ dual $
Proof: E(E+F) = EE+EF = E+EF = E(1+F) = E
·$ $ dual $ ·$
Proof: ·$ $ 1 $ $
These properties are used to minimize (simplify) logic expressions.
Digital Circuits
Example (general case):

The order relation (≤) does not exist between the
E(a,b,c,d) = abc′ , F(a,b,c,d) = bd E and F expressions given in this example.
E⋅F = abc′d E+F = abc′ + bd
From the truth table, we observe
abcd E F E⋅F E+F E⋅F ≤ E and E⋅F ≤ F.
0000 0 0 0 0 We can check the absorption properties:
0001 0 0 0 0 ?
E⋅F + E = E
0010 0 0 0 0 ?
0011 0 0 0 0
abc′d + abc′ = abc′ 
0100 0 0 0 0 and
0101 0 1 0 1 ?
E⋅F + F = F
0110 0 0 0 0 ?
0111 0 1 0 1
abc′d + bd = bd 
1000 0 0 0 0 Again, from the truth table, we observe
1001 0 0 0 0 E ≤ E+F and F ≤ E+F.
1010 0 0 0 0
1011 0 0 0 0 We can check the absorption properties:
?
1100 1 0 0 1 E⋅(E + F) = E
1101 1 1 1 1 ?
abc′ (abc′ + bd) = abc′ 
1110 0 0 0 0
1111 0 1 0 1 and We have thus shown the
? absorption properties also
F⋅(E + F) = F
? using a truth table.
bd (abc′ + bd) = bd 
Digital Circuits
The Consensus Theorem (SOP Form)

Biform variable:
Assume that E1 and E2 are two expressions that do not contain the literal x1 :
E1(x2, .... xn) and E2(x2, .... xm)
We can create a new expression by multiplying one term by x1 and the other one by
the complement of x1 ( ).
* *
Here, * is called a biform variable because it appears both positively (as itself: * )
and negatively (as complement: * ) in the expression.
Examples: a) * * , b) * * +
Consensus Term:
• Given a pair of product terms that include a biform variable, the consensus
term (SOP) is formed by multiplying (ANDing) the two original terms together,
leaving out the selected biform variable and its complement.
• The consensus term of with respect to variable x1 is E1E2 .
Example: Consensus of (with respect to a) is %&' .
The Consensus Theorem: The consensus term is redundant and can be eliminated.
( ()
Digital Circuits
The Consensus Theorem (POS Form)

According to the duality principle, the consensus theorem is also valid for
expressions written in product-of-sums (POS) form.
Assume that E1 and E2 are two expressions that do not contain the literal x1:
E1(x2, .... xn) and E2(x2, .... xm)
We can create a new expression by adding x1 to one term and the complement of x1
to the other one.
* *
Here, x1 is a biform variable.
Examples: a) * * , b) * *
The consensus term:
• Given a pair of sums that include a biform variable, the consensus term (POS) is
formed by adding (ORing) the two original terms together, leaving out the
selected biform variable and its complement.
• The consensus term of with respect to the variable x1 is E1 + E2.
Example: Consensus of is: % & '.
The Consensus Theorem: : The consensus term is redundant and can be eliminated.
( ()
Example: Minimization of a logic expression using the consensus theorem
, -, , . - . - . - . - . - .
Consensus (with respect to C)
- . - . - . - . - . - is added
- . - . - . - . - . - Absorption
- . - . - . -
Consensus (with respect to B)
- . - . -. - . - is added
- . - . -. - . - Absorption
-. - . -
Consensus (with respect to B) is added
-. - . - -. Absorption
-. - -.
Consensus (with respect to A) is added
-. - -. . Absorption
- .
Digital Circuits
Logic (Boolean) Functions

• Logic functions are defined on the input set Bn (vectors with n binary variables).
• There are three types of logic functions.
1. Simple (basic) functions: Multiple inputs, single output

y = f(X): Bn → B
∀Xi∈Bn ; ∃! yi ∈B ; y=f(X)
"For any X, there is exactly one y such that f(X) = y."
Example: The truth table for y = f(X)

x1 x2 x3 y
y = f(X) x1 000 1
X∈B3
x2
x3
f y 001
010
1
0
y∈B 011 0
100 1
101 0
110 0
111 1
Digital Circuits
The number of basic logic functions for n binary variables:

( n)
• There are 2 2 possible basic logic functions for n binary variables (inputs).
For example,
there are 16 possible basic logic functions for 2 binary variables (inputs).
x
f z
y
Truth table for 16 possible basic logic functions (F0–F15) for 2 binary variables:
Inputs Functions
X Y F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15
0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
0 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
0 1
X Y Y' X'
X XOR Y X=Y X NAND Y
X AND Y
X OR Y X NOR Y
(X AND Y)'
(X OR Y)'
Digital Circuits
2. General functions: Multiple inputs, multiple outputs
Y = f(X): Bn → Bm , X=(x1, .... xn), Y=(y1, .... ym),
Example: The truth table for Y = f(X)

x1 x2 x3 y1 y2
Y = f(X) x1 y1
000 1 1
X∈B3 x2
x3
f y2 001 1 0
Y∈B2
010 0 0
011 0 0
100 1 1
101 0 1
110 0 1
111 1 0
Digital Circuits
3. Incompletely speciﬁed functions:

A large digital system usually consists of many subcircuits.
Example:
In the following example, the output of logic circuit L1 drives the output of logic
circuit L2.
A
w
x B
L1 L2 F
y
C
z
• Let us assume that the output of L1 does not generate all possible
combinations of values for A, B, and C.
• In particular, we will assume that there are no combinations of values for
w, x, y, and z, which cause A, B, and C to assume values of 001 and 110.
• In other words, L1 never generates the output combinations 001 and 110.
• Hence, when we design L2, it is not necessary to specify values of F for
ABC = 001 or 110 because these combinations of values can never occur as
inputs to L2.
Digital Circuits
3. Incompletely speciﬁed functions (cont'd):

• For example, F might be specified by the following table:
A B C F
0 0 0 1
0 0 1 X Don't care
0 1 0 0
These input combinations 0 1 1 1
can never occur. 1 0 0 0
1 0 1 0
1 1 0 X Don't care
1 1 1 1
• The X’s in the table indicate that we do not care whether the value of 0 or 1
is assigned to F for the combinations ABC = 001 or 110.
• In this example, we do not care what the value of F is because these input
combinations never occur anyway.
• The function F is then incompletely specified.
• The terms - . and - . are referred to as ‘’don’t care’’ terms because we
do not care whether they are present in the function or not.

• When we realize the function, we must specify values for the don’t cares.
• It is desirable to choose values which will help simplify the function.
• For the example on Slide 2.24: Finding expression from
o If we assign the value 0 to both X’s, then truth table
, - . - . - . - . . See 2.32 canonical forms
o If we assign 0 to the first X and 1 to the second, then
, - . - . - . - . - . . -
o If we assign 1 to the first X and 0 to the second, then The third choice of
, - . - . - . - . - . values leads to the
simplest solution.
o If we assign 1 to both X’s, then
, - . - . - . - . - . - . -
• In Section 4, we will see the selection of unspecified (don't care) values and the
simplification of incompletely specified functions in detail.
• Incompletely specified functions can arise in the following cases:
• Certain combinations of inputs cannot occur (as in the above example).
• All input combinations may occur, but the function output is used in such a
way that we do not care whether it is 0 or 1 for certain input combinations.
Digital Circuits

I1 O1
Example: A function that increments BCD numbers
I2 BCD O2
• We will create a general function to increment I4 +1 O4
BCD numbers given on slide 1.12. I8 O8
• This function will have 4 inputs and 4 outputs
because BCD numbers are 4-bit patterns. I8 I4 I2 I1 O8 O4 O2 O1
0 0 0 0 0 0 0 1
• Since BCD numbers are represented using 0 0 0 1 0 0 1 0
binary code words between 0000-1001, 0 0 1 0 0 0 1 1
combinations between 1010-1111 will 0 0 1 1 0 1 0 0
never appear as inputs to this function. 0 1 0 0 0 1 0 1
0 1 0 1 0 1 1 0
• Even if these values are applied to the
0 1 1 0 0 1 1 1
inputs of the function, we do not care 0 1 1 1 1 0 0 0
what the output values are. 1 0 0 0 1 0 0 1
1 0 0 1 0 0 0 0
1 0 1 0 X X X X
For these input combinations, the output values 1 0 1 1 X X X X
of the circuit (function) are not specified. 1 1 0 0 X X X X
1 1 0 1 X X X X
An X or Φ represents a don't care. 1 1 1 0 X X X X
1 1 1 1 X X X X
Digital Circuits
Representation of Logic (Boolean) Functions

• There are different ways of representing (expressing) the same logic function.
• When designing logic circuits, we choose the most suitable representation.
Truth Table Representation :

• We write the output values for all possible input combinations (variables) in a
table.
• We usually write the input columns so that they follow the order of binary
counting.
• Input variables are encoded as binary numbers.
(See examples in 2.20-2.22)
Numbered (Indexed) Representation:

• Input variables are encoded as binary numbers.
• We assign a decimal number for each input combination based on its binary value.
• To represent the function, we list the decimal number of each input combination
for which the function generates "1" (or logic "0“ or ”Φ”).
Digital Circuits
Example: Indexed representation of a completely specified basic logic function:

Truth Table: Numbered (Indexed) Representation:
Row Input Output y = f(x1,x2) = ∪1(0,2) ∪ denotes "union" or "set of".
Num. x1 x2 y
∪1 denotes "set of 1-generating
0 0 0 1
points".
1 0 1 0
2 1 0 1
3 1 1 0 The order of the variables (x1,x2) is important.
It must be the same as in the truth table.
Otherwise, the decimal numbers identifying the
The same function; only combinations will change.
the order of the variables
(x2,x1) is changed.
Row Input Output y = f(x2,x1) = ∪1(0,1)
Num. x2 x1 y
0 0 0 1
1 0 1 1
2 1 0 0 We can represent the same function with “0”-generating
3 1 1 0 combinations. y = f(x ,x ) = ∪ (1,3)
1 2 0
y = f(x1,x2) = ∪1(0,2) = f(x2,x1) = ∪1(0,1) = f(x1,x2) = ∪0(1,3)

Digital Circuits
Example: Representation of a completely specified general logic function :

We apply the numbered representation to all outputs.
Truth Table: Numbered (Indexed) Representation:
Num. x1 x2 y1 y2
0 0 0 1 1 y1 = f(x1,x2) = ∪1(0,2)
1 0 1 0 1 y2 = f(x1,x2) = ∪1(0,1)
2 1 0 1 0
3 1 1 0 0
Representation of the same function with “0”-generating combinations:
y1 = f(x1,x2) = ∪0(1,3)
y2 = f(x1,x2) = ∪0(2,3)
Digital Circuits
Example: Representation of an incompletely specified general logic function:
• In this case, writing only 1-generating or only 0-generating input combinations

is not sufficient.
• We must write at least two of the three groups (1-generating, 0-generating,
don't care).
Truth Table: Numbered (Indexed) Representations:
N x1 x2 y1 y2 y1 = f(x1,x2) = ∪1(0) + ∪0(1,3)

0 0 0 1 1 or y1 = f(x1,x2) = ∪1(0) + ∪Φ(2)
1 0 1 0 Φ
or y1 = f(x1,x2) = ∪0(1,3) + ∪Φ(2)
2 1 0 Φ 0
3 1 1 0 Φ y2 = f(x1,x2) = ∪1(0) + ∪0(2)
or y2 = f(x1,x2) = ∪1(0) + ∪Φ(1,3)
or y2 = f(x1,x2) = ∪0(2) + ∪Φ(1,3)
Algebraic Representation (Expressions) and Canonical Forms

• The word description (requirements) of a real-world logic design problem can
be translated into a truth table.
• Logic expressions of the Boolean functions can be obtained from their truth
tables in canonical forms.
Example:
• Problem (Requirements):
We need to design a car alarm that activates when the door is opened with the
key inserted.
• Abstraction/Coding/Modeling:
o Assume that input variable A represents the phrase ‘’the car door is open’’
and B represents ‘’the key is inserted’’.
o Then, the truth table can specify the action Z to be taken, where Z=1
means that the alarm sounds.
A B Z • Since the given example is simple, we can see from the truth
0 0 0 table that the logic expression is Z = A⋅B .
0 1 0 • However, truth tables of real-world logic design problems are
more complicated.
1 0 0
• To handle a logic design problem, we need to obtain an
1 1 1 algebraic expression for the output function. Z = f (A, B)
Digital Circuits
Canonical Forms:
• There are two types of canonical forms:
o 1st canonical form: SOP (ΣΠ) form. Example: / % & + / % &
The sum of products, each of which corresponds to a "1"-generating
combination.
o 2nd canonical form: POS (ΠΣ) form. Example: / % & / % &)
The product of sums, each of which corresponds to a "0"-generating
combination.
• Expressions for each logic function can be written in either of these forms.
• Expressions in one form can be converted to the other form.
• Canonical forms are also called standard forms.
Digital Circuits
1st Canonical Form: Sum of Products

Truth Table → Expression in SOP form
• The 1st canonical form is the sum of special products called minterms.
• Minterm: For a Boolean function of n variables, a product of n literals in
which each variable appears exactly once (in either true or complemented
form, but not both) is called a minterm.
For example, a function with 3 variables (a, b, c) has 8 minterms:
0 1̅ 2̅, 0 1̅ 2, 0 1 2̅, 0 1 2, 0 1̅ 2̅, 0 1̅ 2, 0 1 2̅, 0 1 2
• Each minterm that appears in the 1st canonical form covers only one row of
the truth table with the output "1".
For example, the minterm 0 1̅ 2̅ can generate "1" only for the input value
0 1 2 = 000.
For all other input combinations, the minterm 0 1̅ 2̅ generates "0".
Summary:
• The 1st canonical form of a function is the sum of minterms.
• In the 1st canonical form, each product (minterm) in the sum corresponds to a
row in the truth table with the output "1".
Digital Circuits
1st Canonical Form (cont’d) :

Finding minterms:
• To find minterms, we locate all rows in the truth table where the output is "1".
• To obtain the individual minterms, we substitute variables (for example, A, B,
or C) for ones (of the inputs) and complements of variables (-, , or .) for
zeros in the truth table.
Example:
"True" (1-generating) combinations: 001 011 101 110 111

Sum of Minterms: F(A,B,C) = - . + - .+ - . + - . + - .
A B C F
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Digital Circuits
The 1st canonical form of the complement of a function:

We can similarly obtain the 1st canonical form of the complement of a function
by considering the "false" (0) rows.
Example:
Obtain the 1st canonical form of the complement of a function F from the
previous example.
1st canonical form of 3:
3 , ,
A B C F ,
0 0 0 0 1
0 0 1 1 0
0 1 0 0 1
0 1 1 1 0
1 0 0 0 1
1 0 1 1 0
1 1 0 1 0
1 1 1 1 0
Digital Circuits
Simplification of expressions in the 1st canonical form:

• Canonical forms are usually not the simplest (optimal) algebraic expression of
the function.
• They can usually be simplified.
Minimization:
, -, , . - . - . - . - . - .
- - - - . - .
- - . - .
. - .
- . .
- .
• A Boolean function may have many possible logic expressions. They produce the
same result given the same inputs.
• Since the minterms in the 1st canonical form are in one-to-one correspondence
with the 1’s of the truth table, the 1st canonical (standard) form expression
for a function is unique.
• A function can have only one expression in the 1st canonical form.
Indexing minterms:
We assign each minterm an index (number) based on the binary encoding of the
variables.
This decimal number represents the row number (Row numbers start at 0).
For example, we assign the index 5 to the minterm - . (101) and designate it m5.
Minterms for 3 variables (A,B,C):

Inputs:
A B C Minterms
0 0 0 - .̅ = m0 Example:
0 0 1 - . = m1
Expression of function F in (2.34) in 1st canonical
0 1 0 - .̅ = m2
form:
0 1 1 - . = m3
1 0 0 - .̅ = m4 F(A, B, C) = Σm(1,3,5,6,7)
1 0 1 - . = m5 = m1 + m3 + m5 + m6 + m7
1 1 0 - .̅ = m6
= - . - . - . - . - .
1 1 1 - . = m7
F = ΣA, B, C (1,3,5,6,7) (Sum of minterms)
Digital Circuits
2nd Canonical Form: Product of Sums

Truth Table → Expression in POS form
• The 2nd canonical form is the product of special sum terms called maxterms.
• Maxterm: For a Boolean function of n variables, a sum of n literals in which
each variable appears exactly once (in either true or complemented form, but
not both) is called a maxterm.
• For example, a function with 3 variables (a, b, c) has 8 maxterms:
0 1 2, 0 1 2̅ , 0 1̅ 2, 0 1̅ 2̅, 0 1 2, 0 1 2̅ , 0 1̅ 2, 0 1̅ 2̅
• Each maxterm has a value of "0" for exactly one combination of values for the
input variables and "1" for all other combinations.
For example, the maxterm 0 1 2 can generate "0" only for the input value
0 1 2 =000.
For all other input combinations, the maxterm 0 1 2 generates "1".
Summary:
• The 2nd canonical form of a function is the product of maxterms.
• In the 2nd canonical form, each sum term (maxterm) in the product
corresponds to a row in the truth table with the output "0".
Digital Circuits
2nd Canonical Form (cont’d):

Finding maxterms:
• To find the maxterms, we locate all rows in the truth table where the output is
"0".
• To obtain the individual maxterms, we substitute variables (for example, A, B,
or C) for zeros (of the inputs) and complements of variables (-, , or .) for
ones in the truth table.
Example:
"False" (0-generating) combinations: 000 010 100
Product of maxterms: F(A,B,C) = (- .) (- .) (- .)
A B C F
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Note that this function F has the same truth table as the function on slide 2.34.
The expressions in the 1st and 2nd canonical forms both correspond to the same
truth table.
Digital Circuits
The 2nd canonical form of the complement of a function:

• We can similarly obtain the 2nd canonical form of the complement of a function
by considering the "true" (1) rows:
Example:
Obtain the 2nd canonical form of the complement of a function F from the
previous example.
2nd canonical form of F:
, -, , . = (- .) (- .) (- .) (- .) (- .)
A B C F
0 0 0 0
0 0 1 1
0 1 0 0
0 1 1 1
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Digital Circuits
Simplification of expressions in the 2nd canonical form:

Canonical forms are usually not the simplest (optimal) algebraic expression of the
function.
They can usually be simplified.
Minimization:
, -, , . - . - . - .
- . 4 - .
- . - .
- . - . . (consensus)
- . .
• A Boolean function may have many possible logic expressions. They produce the
same result given the same inputs.
• Since the maxterms in the 2nd canonical form are in one-to-one
correspondence with the 0’s of the truth table, the 2nd canonical (standard)
form expression for a function is unique.
• A function can have only one expression in the 2nd canonical form.
Digital Circuits
Indexing maxterms:
We assign each maxterm an index (number) based on the binary encoding of the
variables. This is a decimal number that represents the row number (Row numbers
start at 0).
For example, we assign the index 5 to the maxterm 0 1 2̅ (101) and designate it M5.
Maxterms for 3 variables (A,B,C):

Inputs:
A B C Maxterms
0 0 0 - . M0
0 0 1 - .̅ M1 Example:
0 1 0 - . M2 Expression of function F in (2.39) in 2nd canonical
0 1 1 - .̅ M3
form:
1 0 0 - . M4
, -, , . = ΠM(0,2,4)
1 0 1 - .̅ M5
= M0 • M2 • M4
1 1 0 - . M6
= (- .) (- .) (- .)
1 1 1 - .̅ M7
F = ΠA,B,C(0,2,4) product of maxterms.
Conversions Between Canonical Forms

 Converting from 1st (sum of minterms) form to 2nd (product of maxterms) form:
• Replace the minterms with maxterms, and assign them numbers of minterms
that do not appear in the 1st canonical form.
• Example: F(A,B,C) = Σm(1,3,5,6,7) = ΠM(0,2,4)
F(A,B,C) = m1 + m3 + m5 + m6 + m7 = M0 ⋅ M2 ⋅ M4
F A, B, C ABC ABC ABC ABC ABC A B C A B C A B C
 Converting from 2nd (product to maxterms) form to 1st (sum of minterms) form:
• Replace the maxterms with minterms, and assign them numbers of maxterms
that do not appear in the 2nd canonical form.
• Example: F(A,B,C) = ΠM(0,2,4) = Σm(1,3,5,6,7)
 Finding the complement of the function in sum of minterms form:
• Select the minterms that do not appear in the 1st canonical form.
• Example: F(A,B,C) = Σm(1,3,5,6,7)  F(A,B,C) = Σm(0,2,4)
 Finding the complement of the function in the product of maxterms form:
• Select the maxterms that do not appear in the 2nd canonical form.
• Example: F(A,B,C) = ΠM(0,2,4)  F(A,B,C) = ΠM(1,3,5,6,7)
Digital Circuits
Canonical Forms and the De Morgan's Theorem

• Applying De Morgan's law to the complement of the function in the 1st canonical
form generates the expression in the 2nd canonical form.
Example:
Complement of the function in SOP form (Slide 2.35):
F ABC ABC ABC
Applying De Morgan
F ABC ABC ABC
F A B C A B C A B C 2nd canonical form (2.39).
• Applying the De Morgan's theorem to the complement of the function in the 2nd
canonical form generates the expression in the 1st canonical form.
Example:
Complement of the function in POS form (2.40):
F A B C A B C A B C A B C A B C
Applying De Morgan
F A B C A B C A B C A B C A B C
F ABC ABC ABC ABC ABC 1st canonical form (2.34).
Digital Circuits
Graphical Representation
• The input variables (combinations) of a logic function are elements (vectors) of
the set Bn. Example: B3={000, 001, …, 111}
• We can represent these variables as vertices of an n-dimensional hypercube.
• Vertices that correspond to 1-generating combinations are colored (marked).
• The number of inputs of the function determines how many dimensions the
hypercube has.
n-bit input → n-dimensional hypercube
Boolean Cubes: 01 11
0 1 2-dimensional
Y
1-dimensional f(X,Y)
f(X) X 10
00
X
1111
111 0111
3-dimensional 4-dimensional
f(X,Y,Z) Y Z Y f(W,X,Y,Z)
101 Z
W
000 1000
X 0000 X
Digital Circuits
Example: A B F
01 11
F(A,B) 0 0 1
B
0 1 0
1 0 1 00 10
A
1 1 0
Example: A B C F
F(A,B,C) 0 0 0 0 011 111
0 0 1 0
0 1 0 0
0 1 1 1 110
1 0 0 0 B C 101
1 0 1 1
1 1 0 1 000 A
1 1 1 1
• As the number of variables (inputs) increases, drawing a Boolean cube becomes
more difficult.
• Therefore, Boolean cubes are not practical for representing Boolean functions
with many inputs.
• However, they make it easier to visualize some properties (especially adjacent
combinations) of the functions and to explain further topics.
Digital Circuits
Karnaugh Maps
Maurice Karnaugh (1924-2022), American physicist and mathematician
• The Karnaugh map is a tool for representing and simplifying Boolean functions.
• The Boolean variables and related output values are transferred (generally
from a truth table) into a table that is in a matrix form.
Example: F(A,B)
Truth table: Boolean Cube: Karnaugh maps:

Row
Num. A B F F F
11 B A
01 A 0 1 B 0 1
0 0 0 1
B 0 1 0 0 1 1
1 0 1 0 0 1 or 0 2
2 1 0 1 00 10 1 1 0 1 0 0
A 2 3 1 3
3 1 1 0
A: row, B: column A: column, B: row
We can place different

variables in columns or rows.
Digital Circuits
Karnaugh map (cont'd)

• The rows and columns are labeled according to the Gray code property so that
variables in adjacent squares (horizontal and vertical) of the map differ in only
one variable.
Format of the Karnaugh map for a function with 3 inputs: F(A,B,C)
For example, we write here the output value
Gray Code generated for the input combination ABC=010.
F BC F BC
A 00 01 11 10 A
Row
Inputs
0 000 001 011 010 Adjacent squares.

0 1 3 2 numbers in
1 the truth Hamming distance is 1.
100 101 111 110
4 5 7 6 table
Example: Num A B C F
0 0 0 0 0
1 0 0 1 0 F BC
2 0 1 0 0 A 00 01 11 10
3 0 1 1 1 0 0 0 1 0
4 1 0 0 0 0 1 3 2
5 1 0 1 1 1
40 51 7 1 6 1
6 1 1 0 1
7 1 1 1 1
Format of the Karnaugh map of a function with 4 inputs: F(A,B,C,D)
F CD C D
AB 00 01 11 10 Gray Code
00
0 1 3 2
01
Gray Code 4 5 7 6
11
12 13 15 14
10
8 9 11 10
F CD
AB 00 01 11 10
Example: 00 1 0 0 1
Draw the Karnaugh map for the following
function. 01 0 1 0 0
F(A,B,C,D) = ∪1 (0,2,5,8,9,10,11,12,13,14,15)
11 1 1 1 1
10 1 1 1 1
We will use Karnaugh maps to simplify Boolean functions in the coming lectures.

DC 02

Uploaded by

Copyright:

Available Formats

DC 02

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DC 02

Uploaded by

Copyright:

Available Formats

Digital Circuits License: https://creativecommons.org/licenses/by-nc-nd/4.

 Defined on the set B = {0,1} a • b (AND) a + b (OR) Complement

The Duality principle:

1. Annihilator (or Dominance):

Proving the theorems:

Proving the theorems:

b) Using truth tables

Example: De Morgan's Theorem

Minimizing logic expressions using axioms and theorems:

Logic (Boolean) Expressions

Normal forms of logic expressions:

Value of a logic expression:

• An expression, E(X), generates for each combination of the input vector

Example: E(X) = x1x2 + x3

Applying axioms and theorems to expressions

E a, b, c, d · 1 bc ad ab · 1 bc1 ad1 ab1

"Order Relation" between binary vectors:

A partial order relation between expressions:

Example : Combinations for which

• For each input combination where E(X)

Using the order relation to show absorption properties of expressions

Using the order relation to show absorption properties of expressions (cont'd)

Absorptions: E(X) F(X)

Using the order relation to show absorption properties of expressions (cont'd)

Example (general case):

The Consensus Theorem (SOP Form)

The Consensus Theorem (POS Form)

Example: Minimization of a logic expression using the consensus theorem

Logic (Boolean) Functions

1. Simple (basic) functions: Multiple inputs, single output

Example: The truth table for y = f(X)

The number of basic logic functions for n binary variables:

2. General functions: Multiple inputs, multiple outputs

Y = f(X): Bn → Bm , X=(x1, .... xn), Y=(y1, .... ym),

Example: The truth table for Y = f(X)

3. Incompletely speciﬁed functions:

3. Incompletely speciﬁed functions (cont'd):

3. Incompletely speciﬁed functions (cont'd):

3. Incompletely speciﬁed functions (cont'd):

Representation of Logic (Boolean) Functions

Truth Table Representation :

Numbered (Indexed) Representation:

Example: Indexed representation of a completely specified basic logic function:

y = f(x1,x2) = ∪1(0,2) = f(x2,x1) = ∪1(0,1) = f(x1,x2) = ∪0(1,3)

Example: Representation of a completely specified general logic function :

Truth Table: Numbered (Indexed) Representation:

Representation of the same function with “0”-generating combinations:

Example: Representation of an incompletely specified general logic function:

• In this case, writing only 1-generating or only 0-generating input combinations

Truth Table: Numbered (Indexed) Representations:

N x1 x2 y1 y2 y1 = f(x1,x2) = ∪1(0) + ∪0(1,3)

Algebraic Representation (Expressions) and Canonical Forms

1st Canonical Form: Sum of Products

1st Canonical Form (cont’d) :

"True" (1-generating) combinations: 001 011 101 110 111

The 1st canonical form of the complement of a function:

Simplification of expressions in the 1st canonical form:

Minterms for 3 variables (A,B,C):

2nd Canonical Form: Product of Sums