Lecture 3

Dr. Nabil M. Eldakhly

Faculty of Computers and Information –
Department of CS-
CS-SAMS
&
The French University in Egypt (UFE)
Boolean Algebra &
Logic Gates
 Outline

1. Binary Logic
2. Algebras
3. Basic Definitions
4. Boolean Algebra
5. Algebraic Manipulation
6. Complement of a Function
 Outline

1. Binary Logic
2. Algebras
3. Basic Definitions
4. Boolean Algebra
5. Algebraic Manipulation
6. Complement of a Function
 Boolean Algebra & Logic Gates-
Binary Logic- Definition

Binary logic consists of binary variables and a set of logical

operations.

The variables are designated by letters of the alphabet, such as

A, B, C, x, y, z, etc, with each variable having two and only two
distinct possible values: 1 and 0,
 Boolean Algebra & Logic Gates-
Binary Logic- Basic Logical Operations-
AND, OR, & NOT
 Boolean Algebra & Logic Gates-
Binary Logic (Cont.)-
Truth Table, Boolean Expression, & Logic Gates

AND OR NOT
x y z x y z x z
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

z=x•y=xy z=x+y z = x = x’
 Boolean Algebra & Logic Gates-
Binary Logic (Cont.)- Switching Circuits

AND OR
 Boolean Algebra & Logic Gates-
Binary Logic (Cont.)-
Graphic Symbols & Input-Output Signals of Logic Gates

Symbols For Digital Logic Circuits

Input-output Signals For Gates

 Boolean Algebra & Logic Gates-
Binary Logic (Cont.)-
Graphic Symbols & Input-Output Signals of Logic Gates (Cont.)

Gates With Multiple Inputs

 Outline

1. Binary Logic
2. Algebras
3. Basic Definitions
4. Boolean Algebra
5. Algebraic Manipulation
6. Complement of a Function
 Boolean Algebra & Logic Gates-
Algebras

What is an algebra?
– Mathematical system consisting of
• Set of elements
• Set of operators
• Axioms or postulates

Why is it important?
– Defines rules of “calculations”
 Boolean Algebra & Logic Gates-
Algebras (Cont.)

Example: arithmetic on natural numbers

– Set of elements: N = {1,2,3,4,…}
– Operator: +, –, *
– Axioms: associativity, distributivity, closure, identity elements, etc.
Note: operators with two inputs are called binary
– Does not mean they are restricted to binary numbers!
– Operator(s) with one input are called unary
 Outline

1. Binary Logic
2. Algebras
3. Basic Definitions
4. Boolean Algebra
5. Algebraic Manipulation
6. Complement of a Function
 Boolean Algebra & Logic Gates-
Basic Definition- Set

A set is collection of having the same property.

– S: set, x and y: element or event
– For example:
• S = {1, 2, 3, 4}
o If x = 2, then x ∈ S
o If y = 5, then y ∉ S
 Boolean Algebra & Logic Gates-
Basic Definition- Binary Operator

A binary operator defines on a set S of elements is a rule that assigns,

to each pair of elements from S, a unique element from S.

– For example:
• Given a set S, consider a*b = c and * is a binary operator.
– If (a, b) through * get c and a, b, c ∈ S, then * is a binary operator
of S.

– On the other hand, if * is NOT a binary operator of S and a, b ∈S,

then c ∉ S.
 Boolean Algebra & Logic Gates-
Basic Definition- Common Postulates-
Closure

1. Closure: a set S is closed with respect to (w.r.t.) a binary operator if,

for every pair of elements of S, the binary operator specifies a rule
for obtaining a unique element of S.
– For example, natural numbers N={1,2,3,...} is closed w.r.t. the
binary operator + by the rule of arithmetic addition, since, for any
a, b ∈N, there is a unique c ∈N such that a + b = c
– But operator ( – ) is NOT closed for N, because 2-3 = -1 and 2, 3
∈N, but (-1)∉N.
 Boolean Algebra & Logic Gates-
Basic Definition- Common Postulates-
Association, Commutative, & Distribution Laws

2. Associative law: a binary operator * on a set S is said to be

associative whenever
(x * y) * z = x * (y * z) for all x, y, z ∈S
(x + y) + z = x + (y + z)
3. Commutative law: a binary operator * on a set S is said to be
commutative whenever
x * y = y * x for all x, y ∈S
x+y=y+x
4. Distributive law: if * and • are two binary operators on a set S, * is
said to be distributive over • whenever
x * (y • z) = (x * y) • (x * z)
 Boolean Algebra & Logic Gates-
Basic Definition- Common Postulates-
Identity Element & Inverse

5. Identity element: a set S is said to have an identity element with

respect to a binary operator * on S if there exists an element e ∈ S
with the property that
e * x = x * e = x for every x∈S.
0+x = x+0 =x for every x∈I . I = {…, -3, -2, -1, 0, 1, 2, 3, …}.
1*x = x*1 =x for every x∈I.
6. Inverse: a set having the identity element e with respect to the binary
operator to have an inverse whenever, for every x ∈ S, there exists an
element y ∈ S such that x * y = e.
• The operator + over I, with e = 0, the inverse of an element a is
(-a), since a+(-a) = 0.
 Outline

1. Binary Logic
2. Algebras
3. Basic Definitions
4. Boolean Algebra
5. Algebraic Manipulation
6. Complement of a Function
 Boolean Algebra & Logic Gates-
Boolean Algebra- George Boole (Father of BA)

• He came up with a type of linguistic algebra, the

three most basic operations of which were (and still
are) AND, OR and NOT. It was these three functions
that formed the basis of his premise, and were the
only operations necessary to perform comparisons
or basic mathematical functions.
• 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, George Boole (1815 - 1864)
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
 Boolean Algebra & Logic Gates-
Boolean Algebra (Cont.)-
Axiomatic Definition of Boolean Algebra (Cont.)-
Axioms: (1) Closure Property & (2) Identity Element

A two-valued Boolean algebra is defined on a set of 2 elements B =

{0,1} with 3 binary operators OR (+), AND ( • ), and NOT ( ' ).
– Closure Property. The result of each operation is an element of B. It
is closure w.r.t. operator ( + ) and operator ( • )
– Identity element.
1) 1 for AND because x • 1 = 1 • x = x.

2) 0 for OR because x + 0 = 0 + x = x.
 Boolean Algebra & Logic Gates-
Boolean Algebra (Cont.)-
Axiomatic Definition of Boolean Algebra (Cont.)-
Axiom (3): Commutative Property

x + y = y + x and x • y = y • x
– From the symmetry of the tables.

x y x+y y+x x ．y y．x

0 0 0 0 0 0

0 1 1 1 0 0

1 0 1 1 0 0

1 1 1 1 1 1
 Boolean Algebra & Logic Gates-
Boolean Algebra (Cont.)-
Axiomatic Definition of Boolean Algebra (Cont.)-
Axiom (4): Distributive Property

x •(y + z) = (x • y)+(x • z) and x+(y • z) = (x + y) • (x + z)

• To show that this is true, we need to show that for any value of binary
variables x, y, and z, x • (y + z) will have the same value as (x • y) + (x • z).

x y z y+z x．(y+z) x ．y x．z (x．y) + (x．z)

0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 1 0 1 0 0 0 0
0 1 1 1 0 0 0 0
1 0 0 0 0 0 0 0
1 0 1 1 1 0 1 1
1 1 0 1 1 1 0 1
1 1 1 1 1 1 1 1
 Boolean Algebra & Logic Gates-
Boolean Algebra (Cont.)-
Axiomatic Definition of Boolean Algebra (Cont.)-
Axioms: (5) Distributive Property & (6) Cardinality Bound

– Complement Element. For every x ∈ B, there exists a complement

element x' ∈ B such that:
a) x + x' = 1: 0 + 0' = 0 + 1 = 1 and 1 + 1' = 1 + 0 = 1
b) x • x' = 0: 0 • 0' = 0 • 1 = 0 and 1 • 1' = 1 • 0 = 0

– Cardinality Bound. There are at least two elements x, y ∈ B such

that x ≠ y. 0 ≠ 1
 Boolean Algebra & Logic Gates-
Boolean Algebra (Cont.)-
Huntington Postulates & Theorems of Boolean Algebra

Post. 1: Closure Property. The result of each operation is an element of B.

Post. 2: Identity Element. (a) x + 0 = x (b) x·1 = x
‫ل‬0‫د‬234‫ ا‬60789
Post. 3: Commutative Property. (a) x + y = y + x (b) x • y = y • x
Post. 4: Distributive Property. (a) x(y + z) = x y + x z (b) x + y z = (x + y)(x + z)
Post. 5: Complement Element.
For every x ∈ B, there exists a complement element x' ∈ B such that:
(a) x + x’ = 1 (b) x • x’ = 0
Post. 6: Cardinality Bound.
There are at least 2 elements x, y ∈ S such that x ≠ y. (e.g., 0 ≠ 1)

Theorem 1: Idempotent Law. 60‫@و‬4‫?ون ا‬8B (a) x+x=x (b) x • x = x

Theorem 2: Null Laws (a) x+1=1 (b) x • 0 = 0
Theorem 3: Involution Law. ‫ر‬0‫دو‬34‫?ون ا‬8B (a) ( x’ )’ = x
Theorem 4: Associative Law. (a) (x + y) + z = x + (y + z) (b) x • (y • z) = (x • y) • z
Theorem 5: De Morgan’s Law. (a) (x + y)’ = x’ y’ (b) (x • y)’ = x’ + y’
Theorem 6: Absorption Law. ‫ص‬873DE‫?ون ا‬8B(a) x + x •y = x (b) x • (x + y) = x
Theorem 7: Consensus Theorem (a) x y + x’ z + y z = x y + x’ z
‫وا;ق‬34‫ ا‬60‫?طر‬ (b) (x + y) • (x’ + z) • (y + z) = (x + y) • (x’ + z)
 Boolean Algebra & Logic Gates-
Boolean Algebra (Cont.)-
Duality Principle
The principle of duality is an important concept.
This says that “if an expression is valid in Boolean algebra, the dual of
that expression is also valid”.
To get dual of any expression, Replace:
̶ OR with AND ( + • )
̶ AND with OR (• +)
̶ 1 with 0
̶ 0 with 1
Example: for the identity
AB+ A’C + BC = AB + A’C
The Dual form is:
(A+B).(A’+C).(B+C) = (A+B).(A’+C)
 Boolean Algebra & Logic Gates-
Boolean Algebra (Cont.)- Boolean Theorems
Theorem-1 (Idempotent Law) - (a) x + x = x
Post. 2: (a) x + 0 = x, (b) x·1 = x
Proof that x + x = x Post. 4: (a) x(y + z) = xy + xz,
(b) x + yz = (x + y)(x + z)
x + x = (x + x) • 1 by 2(b) Post. 5: (a) x + x’=1, (b) x·x’ = 0
= (x + x)(x + x’) by 5(a)
= x + xx’ by 4(b)
=x+0 by 5(b)
=x by 2(a)
Q.E.D.

We can now use Theorem 1(a) in future proofs

Q.E.D. An abbreviation of the Latin phrase “Quod Erat Demonstrandum". It literally translates as "which was to be
demonstrated", and is a formal way of ending a mathematical, logical or physical proof.
 Boolean Algebra & Logic Gates-
Boolean Algebra (Cont.)- Boolean Theorems
Theorem-1 (Idempotent Law) - (b) x • x = x
Post. 2: (a) x + 0 = x, (b) x·1 = x
Proof that x • x = x Post. 4: (a) x(y + z) = xy + xz,
(b) x + yz = (x + y)(x + z)
x • x = xx + 0 by 2(a) Post. 5: (a) x + x’=1, (b) x·x’ = 0
= xx + xx’ by 5(b)
= x(x + x’) by 4(a)
=x•1 by 5(a)
=x by 2(b)
Q.E.D.

We can now use Theorem 1(b) in future proofs

 Boolean Algebra & Logic Gates-
Boolean Algebra (Cont.)- Boolean Theorems
Theorem-2- (a) x + 1 = 1
Post. 2: (a) x + 0 = x, (b) x·1 = x
Proof that x + 1 = 1 Post. 4: (a) x(y + z) = xy + xz,
(b) x + yz = (x + y)(x + z)
x + 1 = 1 • (x + 1) by 2(b) Post. 5: (a) x + x’=1, (b) x·x’ = 0

= (x + x’)(x + 1) by 5(a)
= x + x’ 1 by 4(b)
= x + x’ by 2(b)
=1 by 5(a)
Q.E.D.
 Boolean Algebra & Logic Gates-
Boolean Algebra (Cont.)- Boolean Theorems
Theorem-2- (b) x • 0 = 0
Post. 2: (a) x + 0 = x, (b) x·1 = x
Proof that x • 0 = 0 Post. 4: (a) x(y + z) = xy + xz,
x • 0 = 0 + (x • 0) by 2(a) (b) x + yz = (x + y)(x + z)
Post. 5: (a) x + x’=1, (b) x·x’ = 0
= (x • x’) +(x • 0) by 5(b) Th2(a): (a) x + 1 =1
= x(x’ + 0) by 4(a)
= x • x’ by 2(a)
=0 by 5(b)
Q.E.D.
 Boolean Algebra & Logic Gates-
Boolean Algebra (Cont.)- Boolean Theorems
Theorem-3- (Involution Law) ( x’ )’ = x
Post. 2: (a) x + 0 = x, (b) x·1 = x
Proof that (x’)’ = x Post. 4: (a) x(y + z) = xy + xz,
(b) x + yz = (x + y)(x + z)
Post. 5: (a) x + x’=1, (b) x·x’ = 0

• (x‘ )‘ and x are both complement of x

• Uniqueness of the complement (x‘ )‘ = x
 Boolean Algebra & Logic Gates-
Boolean Algebra (Cont.)- Boolean Theorems
Theorem-4- (Association Law)

Proof that: Post. 2: (a) x + 0 = x, (b) x·1 = x

Post. 4: (a) x(y + z) = xy + xz,
(1) (x + y) + z = x + (y + z) (b) x + yz = (x + y)(x + z)
Post. 5: (a) x + x’=1, (b) x·x’ = 0
(2) x • (y • z) = (x • y) • z

Home Assignment

hint: prove that both sides in (1) equal:

[(a+b)+c]·[a+(b+c)]
 Boolean Algebra & Logic Gates-
Boolean Algebra (Cont.)- Boolean Theorems
Theorem-5(a), 5(b)- (De Morgan’s Law)

Prove That:
(1) (x + y)’ = x’y’ , (2) (xy)’ = x’ + y’

By means of truth table

x y x’ y’ x+y (x+y)’ x’y’ xy x’+y' (xy)’

0 0 1 1 0 1 1 0 1 1
0 1 1 0 1 0 0 0 1 1
1 0 0 1 1 0 0 0 1 1
1 1 0 0 1 0 0 1 0 0
 Boolean Algebra & Logic Gates-
Boolean Algebra (Cont.)- Boolean Theorems
Theorem-6- (Absorption Law) (a) x + xy = x
Post. 2: (a) x + 0 = x, (b) x·1 = x
Proof that x + x y = x Post. 3: (a) x+y=y+x, (b) x·y=y·x
Post. 4: (a) x(y + z) = xy + xz,
x + x y= x • 1 + x • y by 2(b) (b) x + yz = (x + y)(x + z)
= x(1 + y) by 4(a) Post. 5: (a) x + x’=1, (b) x·x’ = 0
Th. 2(a): (a) x+1=1
= x(y + 1) by 3(a)
=x•1 by Th 2(a)
=x by 2(b)
Q.E.D.
 Boolean Algebra & Logic Gates-
Boolean Algebra (Cont.)- Boolean Theorems
Theorem-6- (Absorption Law) (b) x(x + y) = x
Post. 2: (a) x + 0 = x, (b) x·1 = x
Post. 3: (a) x+y=y+x, (b) x·y=y·x
Proof that x(x + y) = x Post. 4: (a) x(y + z) = xy + xz,
(b) x + yz = (x + y)(x + z)
Post. 5: (a) x + x’=1, (b) x·x’ = 0
By two methods: Th. 2(a): (a) x+1=1
̶ Duality, OR,
̶ Truth table

x y x+y x(x+y)
0 0 0 0
0 1 1 0
1 0 1 1
1 1 1 1
 Boolean Algebra & Logic Gates-
Boolean Algebra (Cont.)- Boolean Theorems
Theorem-7- (Consensus Theorem)

Prove That:
(1) x y + x’ z + y z = x y + x’ z
(2) (x + y)•(x’ + z)•(y + z) = (x + y) • (x’ + z) (Home Assignment)

Proof: (1) xy + x’z + yz = xy + x’z

xy + x’z + yz = xy + x’z + (x+x’)yz by 5(a)
= xy + x’z + xyz + x’yz by 4(a)
= (xy + xyz) + (x’z + x’zy) by 3(a)
Post. 2: (a) x + 0 = x, (b) x·1 = x
Post. 3: (a) x+y=y+x, (b) x·y=y·x = xy(1 + z) + x’z (1+ y) by 4(a)
Post. 4: (a) x(y + z) = xy + xz,
(b) x + yz = (x + y)(x + z)
= xy(1) + x’z (1) by Th 2(a)
Post. 5: (a) x + x’=1, (b) x·x’ = 0 = xy + x’z by 2(b) QED
Th. 2(a): (a) x+1=1
 Boolean Algebra & Logic Gates-
Boolean Algebra (Cont.)- Operator Precedence

The operator precedence for evaluating Boolean Expression is

– Parentheses
– NOT
– AND
– OR
Examples
– x y' + z
– (x y + z)'
 Boolean Algebra & Logic Gates-
Boolean Algebra (Cont.)- Boolean Functions

A Boolean function
– Binary variables
– Binary operators OR and AND
– Unary operator NOT
– Parentheses
Examples
– F1= x y z'
– F2 = x + y'z
– F3 = x' y' z + x' y z + x y'
– F4 = x y' + x' z
 Boolean Algebra & Logic Gates-
Boolean Algebra (Cont.)- Boolean Functions (Cont.)

The truth table of 2n entries

x y z F1 F2 F3 F4
0 0 0 0 0 0 0
0 0 1 0 1 1 1
F1 = x y z' 0 1 0 0 0 0 0
F2 = x + y'z
F3 = x' y' z + x' y z + x y' 0 1 1 0 0 1 1
F4 = x y' + x' z 1 0 0 0 1 1 1
1 0 1 0 1 1 1
1 1 0 1 1 0 0
1 1 1 0 1 0 0
Two Boolean expressions may specify the same function
– F3 = F4
Boolean Algebra & Logic Gates-
Boolean Algebra (Cont.)-
Implementation with Logic Gates

F2 = x + y'z

F3 = x' y' z + x' y z + x y'

F4 = x y' + x' z
 Outline

1. Binary Logic
2. Algebras
3. Basic Definitions
4. Boolean Algebra
5. Algebraic Manipulation
6. Complement of a Function
 Boolean Algebra & Logic Gates-
Algebraic Manipulation-
Minimization of Boolean Expressions

To minimize Boolean expressions

– Literal: a primed or unprimed variable (an input to a gate)

– Term: an implementation with a gate

– The minimization of the number of literals and the number of

terms → a circuit with less equipment

– It is a hard problem (no specific rules to follow)

 Boolean Algebra & Logic Gates-
Algebraic Manipulation (Cont.)-
Minimization of Boolean Expressions (Cont.)- Examples

1. x(x'+y) = xx' + xy = 0 + xy = xy
2. x+x'y = (x+x‘)•(x+y) = 1•(x+y) = x+y
3. (x+y)(x+y') = x+xy+xy'+yy' = x(1+y+y') = x
4. xy + x'z + yz = xy + x'z + yz(x+x')
= xy + x'z + yzx + yzx'
= xy(1+z) + x'z(1+y)
= xy +x'z
5. (x+y)(x'+z)(y+z) = (x+y)(x'+z), by duality from function 4.
(by Theorem 7: consensus theorem with duality)
 Outline

1. Binary Logic
2. Algebras
3. Basic Definitions
4. Boolean Algebra
5. Algebraic Manipulation
6. Complement of a Function
 Boolean Algebra & Logic Gates-
Complement of a Function

An interchange of 0's for 1's and 1's for 0's in the value of F
– E.g., By DeMorgan's theorem, Prove that: (A+B+C)' = A'B'C‘
F = (A+B+C)' = (A+X)' let B+C = X
= A'X' by theorem 5(a) (DeMorgan's Law)
= A'(B+C)‘ substitute B+C = X
= A'(B'C') by theorem 5(a) (DeMorgan's Law)
= A'B'C' by theorem 4(b) (Associative Law) x • (y • z) = (x • y) • z

Generalizations: a function is obtained by interchanging AND and OR

operators and complementing each literal.
(A+B+C+D+ ... +F)' = A'B'C'D'... F'
DeMorgan's theorem
Theorem 5(a): (x + y)’ = x’y’
(ABCD ... F)' = A'+ B'+C'+D' ... +F'
Theorem 5(b): (xy)’ = x’ + y’
 Boolean Algebra & Logic Gates-
Complement of a Function (Cont.)- Example-1

F1' = (x'yz' + x'y'z)‘

= (x'yz')' (x'y'z)'
= (x+y'+z) (x+y+z')

F2' = [x(y'z'+yz)]'
= x' + (y'z'+yz)'
= x' + (y'z')' (yz)‘
= x' + (y+z) (y'+z')
= x' + yz‘+y‘z
 Boolean Algebra & Logic Gates-
Complement of a Function (Cont.)- Example-2

A simpler procedure
– Take the dual of the function and complement each literal
1. F1 = x'yz' + x'y‘z
The dual of F1 is (x'+y+z') (x'+y'+z)
Complement each literal: (x+y'+z)(x+y+z') = F1'
2. F2 = x(y’z' + yz)
The dual of F2 is x+(y'+z') (y+z)
Complement each literal: x'+(y+z)(y’+z') = F2'