Logic Synthesis and

Verification
Jie-Hong Roland Jiang
江介宏

Department of Electrical Engineering

National Taiwan University

Fall 2024

1
Boolean Algebra

2
Boolean Algebra
Reading

F. M. Brown. Boolean Reasoning: The

Logic of Boolean Equations. Dover, 2003.
(Chapters 1-3)

3
Boolean Algebra
Outline
 Definitions
 Examples
 Properties
 Boolean formulae and Boolean functions

4
Boolean Algebra
 A Boolean algebra is an algebraic structure
(B, +, ⋅, 0, 1)
 B is a set, called the carrier
 + and ⋅ are binary operations defined on B
 0 and 1 are distinct members of B

that satisfies the following postulates (axioms):

1. Commutative laws
2. Distributive laws
3. Identities
4. Complements

5
Postulates of Boolean Algebra
(B, +, ⋅, 0, 1)
1. B is closed under + and ⋅
∀a,b ∈B, a + b∈B and a ⋅ b∈B
2. Commutative laws: ∀a,b ∈B
a+ b=b+ a
a⋅ b=b⋅ a
3. Distributive laws: ∀a,b,c ∈B
a + (b ⋅ c) = (a + b) ⋅ (a + c)
a ⋅ (b + c) = a ⋅ b + a ⋅ c
4. Identities: ∀a ∈B
0 + a=a
1⋅ a=a
5. Complements: ∀a ∈B, ∃ a′∈B s.t.
a + a′ = 1
a ⋅ a′ = 0
Verify that a′ is unique in (B, +, ⋅, 0, 1).

6
Instances of Boolean Algebra
Switching algebra (two-element Boolean
algebra)
The algebra of classes (subsets of a set)
Arithmetic Boolean algebra
The algebra of propositional functions

7
Instance 1: Switching Algebra
 A switching algebra is a two-element Boolean
Algebra ({0,1}, +, ⋅, 0, 1) consisting of:
 the set B = {0, 1}
 two binary operations AND(⋅) and OR(+)
 one unary operation NOT(′)
where

OR 0 1 AND 0 1 NOT -
0 0 1 0 0 0 0 1
1 1 1 1 0 1 1 0

8
Switching Algebra
 Just one of many other Boolean algebras
 (Ex: verify that the algebra satisfies all the postulates.)

 An exclusive property (not hold for all Boolean

algebras) for two-element Boolean algebra:
x + y = 1 iff x=1 or y=1
x ⋅ y = 0 iff x=0 or y=0

OR 0 1 AND 0 1 NOT -
0 0 1 0 0 0 0 1
1 1 1 1 0 1 1 0

9
Instance 2: Algebra of Classes
 Subsets of a set
B ↔ 2S
+↔ ∪
⋅↔∩
0↔φ
1↔S
 S is a universal set (S ≠ φ). Each subset of S is
called a class of S.
 If S = {a,b}, then B = {φ, {a}, {b}, {a, b}}
 B (= 2S) is closed under ∪ and ∩

10
Algebra of Classes
 Commutative laws: ∀S1,S2∈2S
S1 ∪ S2 = S2 ∪ S1
S1 ∩ S2 = S2 ∩ S1
 Distributive laws: ∀S1,S2,S3 ∈2S
S1 ∪ (S2 ∩ S3) = (S1 ∪ S2 ) ∩ (S1 ∪ S3)
S1 ∩ (S2 ∪ S3) = (S1 ∩ S2 ) ∪ (S1 ∩ S3)
 Identities: ∀S1∈2S
S1 ∪ φ = S1
S1 ∩ S = S1
 Complements: ∀S1 ∈2S, ∃S1′∈2S, S1′=S\S1 s.t.
S1 ∪ S1′ = S
S1 ∩ S1′ = φ

11
Algebra of Classes
 Stone Representation Theorem:
Every finite Boolean algebra is isomorphic to the
Boolean algebra of subsets of some finite set S
Therefore, for all finite Boolean algebra, |B| can only be 2k for
some k ≥ 1.
 The theorem proves that finite class algebras are
not specialized (i.e. no exclusive properties, e.g.
x + y = 1 iff x=1 or y=1 in two-element Boolean
algebra)
 Can reason in terms of specific and easily “visualizable”
concepts (union, intersection, empty set, universal set)
rather than abstract operations (+, ⋅,0,1)

12
Instance 3: Arithmetic Boolean Algebra
 (Dn, lcm, gcd, 1, n)
n: product of distinct prime numbers
Dn: set of all divisors of n
lcm: least common multiple
gcd: greatest common divisor
1: integer 1 (not the Boolean 1-element)
 n = 30 = 2 x 3 x 5
 Dn = {1, 2, 3, 5, 6, 10, 15, 30}
 If we look at Dn as {φ, {2}, {3}, {5}, {2, 3}, {2,
5}, {3, 5}, {2, 3, 5}}, it is easy to see that
arithmetic Boolean algebra is isomorphic to the
algebra of classes.
 See Stone Representation Theorem

13
Instance 4: Algebra of Propositional
Functions
(P, ∨, ∧, □, ■)
P: the set of propositional functions of n given
variables
∨: disjunction symbol (OR)
∧: conjunction symbol (AND)
□: formula that is always false (contradiction)
■: formula that is always true (tautology)

14
Lessons from Abstraction
Abstract mathematical objects in terms of
simple rules
A systematic way of characterizing various
seemingly unrelated mathematical objects
Abstraction trims off immaterial details
and simplifies problem formulation

15
Properties of Boolean Algebras
 For arbitrary elements a, b, and c in Boolean algebra
1. Associativity 5. Involution
a + (b + c) = (a + b) + c (a′)′ = a
a ⋅ (b ⋅ c) = (a ⋅ b) ⋅ c 6. De Morgan's Laws
2. Idempotence (a + b)′ = a′ ⋅ b′
a+a=a (a ⋅ b)′ = a′ + b′
a⋅a=a 7.
3. a + a′ ⋅ b = a + b
a+1=1 a ⋅(a′ + b) = a ⋅ b
a⋅0=0 8. Consensus
4. Absorption a ⋅ b + a′ ⋅ c + b ⋅ c =
a + (a ⋅ b) = a a ⋅ b + a′ ⋅ c
a ⋅ (a + b) = a (a + b) ⋅(a′ +c) ⋅(b + c) =
(a + b) ⋅(a′ + c)
16
Principle of Duality
Every identity on Boolean algebra is
transformed into another identity if the
following are interchanged
 the operations + and ⋅,
 the elements 0 and 1

Example:
a + 1 = 1
a ⋅ 0 = 0

17
Postulates for Boolean Algebra
(Revisited in View of Duality)
Duality in (B, +, ⋅, 0, 1)
1. B is closed under + and ⋅
∀a,b ∈B, a + b∈B and a ⋅ b∈B
2. Commutative Laws: ∀a,b ∈B
a+ b=b+ a
a⋅ b=b⋅ a
3. Distributive laws: ∀a,b,c ∈B
a + (b ⋅ c) = (a + b) ⋅ (a + c)
a ⋅ (b + c) = a ⋅ b + a ⋅ c
4. Identities: ∀a ∈B
0 + a=a
1⋅ a=a
5. Complements: ∀a ∈B, ∃ a′∈B s.t.
a + a′ = 1
a ⋅ a′ = 0

18
Two Propositions
1. Let a and b be members of a Boolean algebra. Then
a = 0 and b = 0 iff a + b = 0
a = 1 and b = 1 iff ab = 1

c.f. The following two propositions are only true for two-element
Boolean algebra (not other Boolean algebra)
x+y =1 iff x=1 or y=1
xy=0 iff x=0 or y=0

Why?

2. Let a and b be members of a Boolean algebra. Then

a = b iff a′b + ab′ = 0

19
Boolean Formulas and
Boolean Functions

20
Boolean Formulas and Boolean
Functions
Outline:
 Definition of Boolean formulas
 Definition of Boolean functions
 Boole's expansion theorem
 The minterm canonical form

21
n-variable Boolean Formulas
 Given a Boolean algebra B and n symbols x1 ,…, xn the set
of all Boolean formulas on the n symbols is defined by:
1. The elements of B are Boolean formulas.
2. The variable symbols x1 ,…, xn are Boolean formulas.
3. If g and h are Boolean formulas, then so are
 (g) + (h)
 (g) ⋅ (h)
 (g)′
4. A string is a Boolean formula if and only if it is obtained by
finitely many applications of rules 1, 2, and 3.
 There are infinitely many n-variable Boolean formulas.

22
n-variable Boolean Functions
 A Boolean function is a mapping that can be described by a
Boolean formula.
 Given an n-variable Boolean formula F, the corresponding
n-variable function f : Bn B is defined as follows:
1. If F = b ∈ B, then the formula represents the constant function
defined by
f(x1,…,xn) = b ∀([x1],…,[xn ]) ∈ Bn

2. If F = xi , then the formula represents the projection function

defined by
f(x1,…,xn) = xi ∀([x1],…,[xn ]) ∈ Bn

where [xk] denotes a valuation of variable xk

23
n-variable Boolean Functions
3. If the formula is of type either G + H, GH, or G′, then
the corresponding n-variable function is defined as
follows
(g + h)(x1,…,xn) = g(x1,…,xn) + h(x1,…,xn)
(g ⋅ h)(x1,…,xn) = g(x1,…,xn) ⋅ h(x1,…,xn)
(g′)(x1,…,xn) = g(x1,…,xn)′

for ∀ ([x1],…,[xn]) ∈ Bn

 The number of n-variable Boolean functions

over a finite Boolean algebra B is finite.

24
Example
x y f
 B = {0, 1, a, a′}
0 0 a
 Variable symbols: 0 1 0
0 a′ a
{x, y}
0 a 0
 2-variable Boolean 1 0 1
formula: 1 1 a’
1 a′ 1
e.g., a′ x + a y′ 1 a a’
 2-variable Boolean a 0 a
function: f : B2  B a 1 0
a a′ a
 Domain B2={(0,0), a a 0
(0,1), …, (a,a)} a′ 0 1
a′ 1 a’
a′ a′ 1
a′ a a’ 25
Boole's Expansion Theorem
Theorem 1 If f : Bn  B is a Boolean
function, then
f(x1,…,xn) = x′1 f(0,…,xn) + x1 f(1,…,xn)
for ∀ ([x1],…,[xn ]) ∈ Bn
Proof. Case analysis of Boolean functions under
the construction rules. Apply postulates of
Boolean algebra.

The theorem holds not only for two-

element Boolean algebra (c.f. Shannon
expansion)
26
Minterm Canonical Form
Theorem 2 A function f : Bn  B is Boolean if and
only if it can be expressed in the minterm
canonical form
f (X ) = ∑ f ( A) ⋅ X A
A∈{0 ,1}n

where X= (x1 ,…,xn ) ∈ Bn, A = (a1,…,an) ∈ {0,1}n,

and XA ≡ x1a1⋅ x2a2 ⋅⋅⋅ xnan (with x0 ≡ x′ and x1 ≡ x )
Proof.

(⇒) Follows from Boole's expansion theorem.

(⇐) Examine the construction rules of Boolean functions.

27
Example
f is not Boolean!
Proof. If f is Boolean, f can be x f(x)
expressed by f(x) = x f(1) + x′ f(0)
= x + a x′ from the minterm 0 a
canonical form. However, 1 1
substituting x = a in the previous
expression yields: f(a) = a + a a′ a′ a′
=a≠1 a 1

28
Why Study General Boolean Algebra?
General algebras can't be avoided
f = x y + x z′ + x′ z
 Two-element view: x, y, z ∈ {0,1} and f ∈{0,1}
 General algebra view: f as a member of the
Boolean algebra of 3-variable Boolean
functions

29
Why Study General Boolean Algebra?
 General algebras are useful
 Two-element view: Truth tables include only 0 and 1.
 General algebra view: Truth tables contain any elements
of B.

J K Q Q+
J K Q+
0 0 0 0
0 0 Q
0 0 1 1
0 1 0
0 1 0 0
1 0 1
0 1 1 0
1 1 Q′
.. .. .. ..

30