•Boolean Algebra
Objectives
• Logic Operations and Gates
• Boolean Algebra
• Boolean Expressions
• Boolean Identities
• Algebraic manipulation (simplification)
• Complement of a Function
Logical Operations
Three basic logical operations can be applied to binary
variables:
AND: Z = X.Y or Z = XY
The AND operation works as follows: If both X and Y have
a value of 1, the output Z will be 1 else Z will be 0
OR: Z = X + Y
The OR operation implies: If either X or Y have a value of
1, the output Z will be 1
NOT: Z = X
If the value of X is a 0, Z is a 1, and if X = 1, Z= 0
Don’t confuse binary logic and binary arithmetic !
AND Operation
A truth table of a logical operation is a table of all possible
combinations of input variable values, and the corresponding value of
the output
The truth table for the AND logical operation:
AND
X Y Z = X.Y
0 0 0
Similar to
0 1 0 multiplication
1 0 0
1 1 1
AND Gate
The electronic device that performs the AND operation is
called the AND gate
X
Z
Y
An AND gate with two input variables X, Y and one output Z
Note: The output of the AND gate Z is a 1 if and only if all
the inputs are 1 else it is 0
3-input AND gate
Truth Table for a 3 input AND gate
W W X Y Z
X Z 0 0 0 0
Y 0 0 1 0
0 1 0 0
0 1 1 0
Note: For an n-input logic gate,
the size of the truth table is 2n 1 0 0 0
1 0 1 0
1 1 0 0
1 1 1 1
OR Operation
The truth table for the OR logical operation
OR
X Y Z = X +Y
0 0 0
0 1 1
Similar to
1 0 1
addition
1 1 1
OR Gate
The electronic device that performs the AND operation is
called the AND gate
X
Z
Y
An OR gate with two input variables X, Y and one output Z
Note: The output of the OR gate Z is a 1 if either of the two
inputs X, Y are 1
OR Gate – 3 Input
Truth Table for a 3 input OR gate
W W X Y Z=W+X+Y
X Z 0 0 0 0
Y 0 0 1 1
0 1 0 1
0 1 1 1
Note: For an n-input logic gate,
the size of the truth table is 2n 1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
NOT Operation
•NOT is a unary operator, meaning there can only be 1 input
•The NOT operation can be represented as follows: Z= X’ or
Z=X
•X is also referred to as the complement of Z.
•The NOT gate is also known as the Inverter
NOT
X Z
X Z=X
0 1
1 0
Timing Diagram
A graphical
representation
time
Of the truth table!
time
time
time
time
Logical Operations and Gates (Summary)
src: Mano’s Textbook
Boolean Algebra
• Digital circuits are hardware components for processing
(manipulation) of binary input
• They are built of transistors and interconnections in
semiconductor devices called integrated circuits
• A basic circuit is called a logic gate; its function can be
represented mathematically.
• What is inside the gate is not of concern to the
system/computer designer (Only its function)
• Binary logic (Boolean Algebra) is a mathematical system
to analyze and design digital circuits
– George Boole (introduced mathematical theory
of logic in1854)
Boolean Algebra
Regular Algebra Boolean Algebra
Numbers
Integers 1 (True, High)
Values Real numbers 0 (False, Low)
Complex Numbers
Operators +, -, x, /, … etc AND ( . )
OR (+)
NOT ( ‘, )
Variables may be given any name such as A, B, X etc..
Boolean Expression
F (X, Y) = XY + Y’
variable
operator literals
• A Boolean expression is made of Boolean variables and constants
combined with logical operators: AND, OR and NOT
• A literal is each instance of a variable or constant.
• Boolean expressions are fully defined by their truth tables
• A Boolean expression can be represented using interconnected logic
gates
– Literals correspond to the input signals to the gates
– Constants (1 or 0) can also be input signals
– Operators of the expression are converted to logic gates
• Example: a’bd + bcd + ac’ + a’d’ (4 variables, 10 literals, ?? gates)
Operator Precedence
• Given a Boolean expression, the order of operations
depends on the precedence rules given by:
1. Parenthesis Highest Priority
2. NOT
3. AND
4. OR Lowest Priority
• Example: XY + WZ will be evaluated as:
1. XY
2. WZ
3. XY + WZ
Example
F = X . ( Y’ + Z)
This function has three inputs X, Y, Z and the output is
given by F
As can be seen, the gates needed to construct this circuit
are: 2 input AND, 2 input OR and NOT
X
Y Y’ F
Z
Example (Cont.)
A Boolean function can be represented with a truth table
F = X . ( Y’ + Z)
X Y Z Y’ Y’ + Z F=X.(Y’+Z)
0 0 0 1 1 0
0 0 1 1 1 0
0 1 0 0 0 0
0 1 1 0 1 0
1 0 0 1 1 1
1 0 1 1 1 1
1 1 0 0 0 0
1 1 1 0 1 1
Identities of Boolean Algebra
src: Mano’s Textbook
Proof of x+1=1
Theorem 2(a): x + 1 = 1 Huntington postulates:
x + 1 = 1．(x + 1) by 2(b) Post. 2: (a) x+0=x, (b) x·1=x
=(x + x')(x + 1) 5(a) Post. 3: (a) x+y=y+x, (b) x·y=y·x
Post. 4: (a) x(y+z) = xy+xz,
= x + x' 1 4(b) (b) x+yz = (x+y)(x+z)
= x + x' 2(b) Post. 5: (a) x+x’=1, (b) x·x’=0
=1 5(a) Th. 1: (a) x+x=x
Theorem 2(b): x．0 = 0 by duality
Theorem 3: (x')' = x
Postulate 5 defines the complement of x, x + x' = 1 and x x' = 0
The complement of x' is x is also (x')'
October 13, 2022
20
Absorption Property (Covering)
Huntington postulates:
Theorem 6(a): x + xy = x
x + xy = x.1 + xy by 2(b) Post. 2: (a) x+0=x, (b) x·1=x
= x (1 + y) 4(a) Post. 3: (a) x+y=y+x, (b) x·y=y·x
= x (y + 1) 3(a) Post. 4: (a) x(y+z) = xy+xz,
= x．1 Th 2(a) (b) x+yz = (x+y)(x+z)
=x 2(b) Post. 5: (a) x+x’=1, (b) x·x’=0
Th. 1: (a) x+x=x
Theorem 6(b): x (x + y) = x by duality
By means of truth table (another way to proof )
x y xy x+xy
0 0 0 0
0 1 0 0
1 0 0 1
1 1 1 1
October 13, 2022
21
DeMorgan’s Theorem
Theorem 5(a): (x + y)’ = x’y’
Theorem 5(b): (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
October 13, 2022
22
Consensus Theorem
• Y and Z are associated
with X and X’ in the
first two terms and
appear together in the third.
• YZ is redundant and can be
1. xy + x’z + yz = xy + x’z eliminated.
2. (x+y)•(x’+z)•(y+z) = (x+y)•(x’+z) -- (dual)
Proof:
xy + x’z + yz = xy + x’z + (x+x’)yz
= xy + x’z + xyz + x’yz
= (xy + xyz) + (x’z + x’zy)
= xy + x’z
October 13, 2022
23
Duality Principle
• The principle of duality states that: given a Boolean Algebra identity, its
dual is obtained by replacing all 1’s with 0’s and 0’s with 1’s, all AND
operators with OR, and all OR operators with AND
• The dual of an identity is also an identity
AND Identities: Replacing OR Identities (Dual):
X.1 = X 1 with 0 X+0=X
X.0 = 0 0 with 1 X+1=1
X.X = X + with . X+X=X
X.X = 0 . with + X+X=1
Another Important Identity: X = X
DeMorgan’s Theorem
X Y X Y
X Y X Y
use truth
tables to
prove that
two Boolean
expressions
are equal !
Extended DeMorgan’s Theorem: X1 + X2 + …. +Xn = X1.X2…..Xn
X1 X2 …. Xn = X1 + X2+….+Xn
Why Boolean Algebra?
• Boolean algebra identities and properties help reduce the
size of expressions
• In effect, smaller sized expressions will require fewer
logic gates for building the circuit
• As a result, less cost will be incurred for building simpler
circuits
• The speed of simpler circuits is also high
Algebraic Manipulation
Ability to use the Boolean identities and properties to reduce
complex equations
Example 1: Prove that X + XY = X • This is called absorption
X + XY = X.(1+Y) = X.1 = X • Y has been absorbed
distributive property
Example 2: Reduce X+X’Y
= (X+X’).(X+Y) = 1.(X+Y) = X+Y
Algebraic Manipulation (Example)
F = X’YZ + X’YZ’ + XZ
= X’Y(Z+Z’) + XZ (id 14)
= X’Y.1 + XZ (id 7)
= X’Y + XZ (id 2)
Algebraic Manipulation (Example)
F = X’YZ + X’YZ’ + XZ
= X’Y(Z+Z’) + XZ (id 14)
= X’Y.1 + XZ (id 7)
= X’Y + XZ (id 2)
Algebraic Manipulation (Example)
F = X’YZ + X’YZ’ + XZ
= X’Y(Z+Z’) + XZ (id 14)
= X’Y.1 + XZ (id 7)
= X’Y + XZ (id 2)
Verify !
Example
Reduce F1=(A + B + AB) (AB + AC + BC)
Using DeMorgan’s Theorem,
F1 = (A’.B.(A’+B’)).(A’+B’).(A+C’).(B’+C’)
= (A’.B.A’ + A’.B.B’).(A’+B’)(A+C’) .(B’+C’)
= (A’B + 0).(A’+B’)(A+C’) .(B’+C’)
= (A’BA’ + A’BB’) (A+C’) .(B’+C’)
= (A’B) (A+C’) .(B’+C’)
= (A’BA+A’BC’)(B’+C’)
= (0+A’BC’)(B’+C’)
= (A’BC’B’ + A’BC’C’)
= (0 + A’BC’) = A’BC’
Example
Simplify G = ((A+B+C).(AB+CD)+(ACD))
= ((A+B+C)+(AB.(C+D))).ACD
= (A+B+C).ACD + (AB.(C+D)).ACD
= (ACD+ABCD) + (ABCD+ABCD)
= (ACD +ACD(B+B) + ABCD)
= (ACD + ACD + ABCD)
= (ACD + ABCD)
= (ACD(1+B))
= ACD
Complement of a Function
Truth table
The complement of a function F,
F, is obtained in two ways: A B F F’
0 0 0 1
1. Truth Table: Change 1s to
0s and 0s to 1s 0 1 1 0
1 0 1 0
2. Boolean Expression: Apply
DeMorgan’s Theorem 1 1 0 1
* Be Careful !! Before F = A’B + AB’
you begin, surround all F’ = (A+B’).(A’+B)
AND terms with = AB + A’B’
parentheses (easy to
Short cut: Take the dual and
make a mistake!). complement the literals.
Conclusion
• Boolean Algebra is a mathematical
system to study logic circuits
• Boolean identities and algebraic
manipulation can be used to simplify
Boolean expressions.
• Simplified Boolean expressions result in
simpler circuits.