E2011: Theoretical fundamentals of computer science
Topic 2: Boolean algebra
Vlad Popovici, Ph.D.
Fac. of Science - RECETOX
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 2 / 27
Outline
1 Introduction
2 Fundamentals of Boolean algebra
3 Other operators
4 From truth table to functions and circuits
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 3 / 27
Introduction: ”0/1”
Babbage’s punched cards
Basic relay device
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 4 / 27
George Boole (1815-1864)
1844: ”On a general method in
analysis”; gold prize in mathematics
from Royal Society
logical system: ”An Investigation of the
Laws of Thought on Which are Founded
the Mathematical Theories of Logic and
Probabilities” −→ ”algebra of logic”
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 5 / 27
Victor Shestakov (1907-1987)
Moscow State University (1934)
theory of electric switches based
on Boolean logic
algebraic logic model for 2-, 3-,
4-poles switches
Claude Shannon (1916-2001)
”father of information theory”
MIT
thesis on theory of electrical
circuits based on Boolean
algebra
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 6 / 27
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 7 / 27
Fundamentals
binary logic: ”tertium non datur”: law of excluded middle
symbolism: 0: FALSE, 1: TRUE
variables: stand for one of the two possible values, are usually
represented by letters (or strings)
operators: nary functions of variables, usually unary or binary
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 8 / 27
variables: X, Y
negation: NOT, ¬X
conjunction: AND, X ∧ Y
disjunction: OR, X ∨ Y
X
Y
NOT X
X
X
X
X AND Y
Y
X
X OR Y
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 9 / 27
Equivalence with sets and number operations
negation: ¬X ≡ X ≡ C(X)
0
0
1
1
X
C(X)
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 10 / 27
Equivalence with sets and number operations
conjunction:
X ∧ Y ≡ X · Y ≡ X ∩ Y
X YX AND Y
0
0
0
0
0
0
0
1
1
1
1
1
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 11 / 27
Equivalence with sets and number operations
disjunction:
X ∨ Y ≡ X + Y ≡ X ∪ Y
X YX OR Y
0
0
0
0
0
1
1
1
1
1
1
1
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 12 / 27
Example:
X
Y
X OR Y
5v
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 13 / 27
commutative law:
X ∧ Y = Y ∧ X or X · Y = Y · X
X ∨ Y = Y ∨ X or X + Y = Y + X
in the following we will use the usual algebraic notation, and skip ·
when not necessary
associative law:
(XY )Z = X(YZ)
(X + Y ) + Z = X + (Y + Z)
distributive law
X(Y + Z) = XY + XZ
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 14 / 27
Example:
X(Y + Z) = XY + XZ
X
Y
Y
Z Y+Z
X(Y+Z)
Z
X
XY
XZ
XY + XZ
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 15 / 27
Truth tables for functions (and circuits)
Each logic function is fully described by enumerating all possible inputs
and corresponding outputs (2n values for n distinct inputs/variables).
NOT
X X
0 1
1 0
AND
X Y X · Y
0 0 0
0 1 0
1 0 0
1 1 1
OR
X Y X + Y
0 0 0
0 1 1
1 0 1
1 1 1
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 16 / 27
Fundamental laws and theorems
X = X
OR operations:
X + 0 = X
X + 1 = 1
X + X = X (idempotence)
X + X = 1
AND operations:
X · 0 = 0
X · 1 = X
X · X = X (idempotence)
X · X = 0
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 17 / 27
Fundamental laws and theorems
dual of distributive law:
X + YZ = (X + Y )(X + Z)
Proof:
(X + Y )(X + Z) = XX + XZ + YX + YZ
= X + XZ + YX + YZ ∵ XX = X
= X(1 + Z) + YX + YZ
= X + YX + YZ ∵ 1 + Z = 1
= X(1 + Y ) + YZ
= X + YZ ∵ 1 + Y = 1
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 18 / 27
Fundamental laws and theorems
dual of distributive law:
X + YZ = (X + Y )(X + Z)
Proof (by brute force approach - truth table):
X Y Z X + Y X + Z YZ (X + Y )(X + Z) X + YZ
0 0 0 0 0 0 0 0
0 0 1 0 1 0 0 0
0 1 0 1 0 0 0 0
0 1 1 1 1 0 1 1
1 0 0 1 1 0 1 1
1 0 1 1 1 0 1 1
1 1 0 1 1 1 1 1
1 1 1 1 1 1 1 1
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 19 / 27
Fundamental laws and theorems
absorption law:
X + XY = X
X(X + Y ) = X
identity theorem:
X + XY = X + Y
X(X + Y ) = XY
De Morgan’s theorem:
X + Y = XY
XY = X + Y
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 20 / 27
Other operators
XOR
”exclusive OR”
X Y X ⊕ Y
0 0 0
0 1 1
1 0 1
1 1 0
NAND
”negated-AND”
X Y XY
0 0 1
0 1 1
1 0 1
1 1 0
NOR
”negated-OR”
X Y X + Y
0 0 1
0 1 0
1 0 0
1 1 0
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 21 / 27
Truth table −→ function −→ circuit
Consider the following truth table:
X Y Z F(X, Y , Z)
0 0 0 1
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 1
1 1 1 0
What is the corresponding logic function?
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 22 / 27
Method
Write the function as a sum of products (i.e. disjunction of conjunctions):
for each ”1” in the function column, take the sum (OR) of the
corresponding fundamental product (ANDs). Then simplify the expression.
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 23 / 27
X Y Z F(X, Y , Z) products
0 0 0 1 X · Y · Z
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 1 X · Y · Z
1 0 1 0
1 1 0 1 X · Y · Z
1 1 1 0
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 24 / 27
X Y Z F(X, Y , Z) products
0 0 0 1 X · Y · Z
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 1 X · Y · Z
1 0 1 0
1 1 0 1 X · Y · Z
1 1 1 0
F(X, Y , Z) = X · Y · Z + X · Y · Z + X · Y · Z
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 24 / 27
Implementation:
F(X, Y , Z) = X · Y · Z + X · Y · Z + X · Y · Z
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 25 / 27
Simplification:
F(X, Y , Z) = X · Y · Z + X · Y · Z + X · Y · Z
= (X + X)Y · Z + X · Y · Z
= Y · Z + X · Y · Z
= Z(Y + XY )
= Z(X + Y )
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 26 / 27
Questions?
Vlad Popovici, Ph.D. (Fac. of Science - RECETOX)E2011: Theoretical fundamentals of computer science Topic 2: Boolean algebra 27 / 27