Boolean Algebra

Introduction
• Developed by English Mathematician George

Boole in between 1815 - 1864.
• It is described as an algebra of logic or an
algebra of two values i.e True or False.
• The term logic means a statement having
binary decisions i.e True/Yes or False/No.
Application of Boolean algebra
• It is used to perform the logical operations in digital computer.
• In digital computer True represent by ‘1’ (high voltage) and
False represent by ‘0’ (low voltage)
• Logical operations are performed by logical operators. The
fundamental logical operators are:
1. AND (conjunction)
2. OR (disjunction)
3. NOT (negation/complement)
AND operator
• It performs logical multiplication and denoted by (.)
dot.
X Y X.Y
0 0 0
0 1 0
1 0 0
1 1 1
OR operator
• It performs logical addition and denoted by (+) plus.
X Y X+Y
0 0 0
0 1 1
1 0 1
1 1 1
NOT operator
• It performs logical negation and denoted by (-) bar.
It operates on single variable.
X X (means complement of x)
0 1
1 0
Truth Table
• Truth table is a table that contains all possible values
of logical variables/statements in a Boolean
expression.
No. of possible combinations = 2n, where n=number of

variables used in a Boolean expression.
Truth Table
• The truth table for XY + Z is as follows:
Dec X Y Z X.Y X.Y+Z
0 0 0 0 0 0
1 0 0 1 0 1
2 0 1 0 0 0
3 0 1 1 0 1
4 1 0 0 0 0
5 1 0 1 0 1
6 1 1 0 1 1
7 1 1 1 1 1
Tautology & Fallacy
• If the output of Booean expression is always True or 1
is called Tautology.
• If the output of Boolean expression is always False or 0
is called Fallacy.
P P’ output (P + P’) output (P . P’)
0 1 1 0
1 0 1 0
P+P’ is Tautology and P.P’ is Fallacy

Exercise
1. Evaluate the following Boolean expression using
Truth Table.
(a) X’Y’+X’Y (b) X’YZ’+XY’
(c) XY’(Z+YZ’)+Z’
2. Verify that P+(PQ)’ is a Tautology.

3. Verify that (X+Y)’=X’Y’
Implementation
• Boolean Algebra applied in computers
electronic circuits. These circuits perform
Boolean operations and these are called logic
circuits or logic gates.
Logic Gate
• A gate is an digital circuit which operates on one or more signals and
produce single output.
• Gates are digital circuits because the input and output signals are denoted
by either 1(high voltage) or 0(low voltage).
• Three type of gates are as under:
1. AND gate
2. OR gate
3. NOT gate
AND gate
• The AND gate is an electronic circuit that gives a high output (1) only
if all its inputs are high.
• AND gate takes two or more input signals and produce only one
output signal. Input Input Output
A B AB
0 0 0
0 1 0
1 0 0
1 1 1
OR gate
• The OR gate is an electronic circuit that gives a high
output (1) if one or more of its inputs are high.
• OR gate also takes two or more input signals and
produce only one output signal. Input
A
Input
B
Output
A+B
0 0 0
0 1 1
1 0 1
1 1 1
NOT gate
• The NOT gate is an electronic circuit that gives a high output (1) if its
input is low .
• NOT gate takes only one input signal and produce only one output signal.
• The output of NOT gate is complement of its input.
• It is also called inverter. Input A Output A
0 1
1 0
Principal of Duality
•In Boolean algebras the duality Principle is obtained by interchanging
AND and OR operators and replacing 0's by 1's and 1's by 0's.
Compare the identities on the left side with the identities on the
right.
Example
A+1 = 1 then A.0 = 0
Basic Theorem of Boolean Algebra
T1 : Properties of 0
(a) 0 + A = A
(b) 0 A = 0
T2 : Properties of 1
(a) 1 + A = 1
(b) 1 A = A
T3 : Commutative Law
(a) A + B = B + A
(b) A B = B A
T4 : Associate Law
(a) (A + B) + C = A + (B + C)
(b) (A B) C = A (B C)
T5 : Distributive Law
(a) A (B + C) = A B + A C
(b) A + (B C) = (A + B) (A + C)
(c) A+A’B = A+B
T6 : Indempotence (Identity ) Law
(a) A + A = A
(b) A A = A
T7 : Absorption (Redundance) Law

(a) A + A B = A
(b) A (A + B) = A
T8 : Complementary Law
(a) X+X’=1
(b) X.X’=0
T9 : Involution
(a) x’’ = x
T10 : De Morgan's Theorem
(a) (X+Y)’=X’.Y’
(b) (X.Y)’=X’+Y’
Exercise
Q 1. State & Verify De Morgan's Law by using truth
table and algebraically.
Q 2. State and verify distributive law.
Q 3. Draw a logic diagram for the following
expression:
(a) ab+b’c+c’a’
(b) (a+b).(a+b’).c
Representation of Boolean expression
Boolean expression can be represented by either

(i) Sum of Product( SOP) form or
(ii) Product of Sum (POS form)
e.g.
AB+AC  SOP
(A+B)(A+C)  POS
In above examples both are in SOP and POS respectively but they are not in Standard SOP and POS.
Canonical form of Boolean Expression (Standard form)
 In standard SOP and POS each term of Boolean

expression must contain all the literals (with and
without bar) that has been used in Boolean
expression.
 If the above condition is satisfied by the Boolean
expression, that expression is called Canonical
form of Boolean expression.
Canonical form of Boolean Expression (Standard form) Contd..
 In Boolean expression AB+AC the literal C is

mission in the 1st term AB and B is mission
in 2nd term AC. That is why AB+AC is not a
Canonical SOP.
Convert AB+AC in Canonical SOP (Standard
SOP)
Sol. AB + AC
AB(C+C’) + AC(B+B’)
Distributive law
ABC+ABC’+ABC+AB’C
ABC+ABC’+AB’C
Convert (A+B)(A+C) in Canonical SOP (Standard
SOP)
Sol. (A+B).(A+C)
((A+B)+(C.C’)) .((A+C)+(B.B’))
Distributive law
(A+B+C).(A+B+C’).(A+B+C)(A+B’+C)
Remove duplicates
(A+B+C).(A+B+C’)(A+B’+C)
Conversion between SOP and POS
Minterm and Maxterm

Individual term of Canonical Sum of Products (SOP) is called
Minterm. In otherwords minterm is a product of all the
literals (with or without bar) within the Boolean expression.
Individual term of Canonical Products of Sum (POS) is called

Maxterm. In otherwords maxterm is a sum of all the literals
(with or without bar) within the Boolean expression.
Minterms & Maxterms for 2 variables (Derivation of
Boolean function from Truth Table)
x y Index Minterm Maxterm
0 0 0 m0 = x’ y’ M0 = x + y
0 1 1 m1 = x’ y M1 = x + y’
1 0 2 m2 = x y’ M2 = x’ + y
1 1 3 m3 = x y M3 = x’ + y’
The minterm mi should evaluate to 1 for each combination
of x and y.
The maxterm is the complement of the minterm
Purpose of the Index
 Minterms and Maxterms are designated with an index
 The index number corresponds to a binary pattern
 The index for the minterm or maxterm, expressed as a binary number, is used
to determine whether the variable is shown in the true or complemented
form
 For Minterms:
 ‘1’ means the variable is “Not Complemented” and
 ‘0’ means the variable is “Complemented”.
 For Maxterms:
 ‘0’ means the variable is “Not Complemented” and
 ‘1’ means the variable is “Complemented”.
Solved Problem
Write SOP form of a Boolean Function F, Which is represented by the following
truth table.
Sum of minterms of entries that evaluate to ‘1’
x y z F Minterm
0 0 0 0
0 0 1 1 m1 = x’ y’ z
0 1 0 0
0 1 1 0 Focus on the
1 0 0 0
1 0 1 0 ‘1’ entries
1 1 0 1 m6 = x y z’
1 1 1 1 m7 = x y z
F = m1 + m6 + m7 = ∑ (1, 6, 7) = x y z + x y z + x y z
Exercise
1. Write POS form of a Boolean Function F, Which is represented by
the following truth table x y z F
0 0 0 1
0 0 1 1
0 1 0 0
0 1 1 0
1 0 0 1
1 0 1 1
1 1 0 0
1 1 1 1
2. Write equivalent canonical Sum of Product expression for the following
Product of Sum Expression: F(X,Y,Z)=Π(1,3,6,7)
Minimization of Boolean Expression
Canonical SOP (Sum of Minterms) and POS (Product of Maxterm) is

the derivation/expansion of Boolean Expression.
Canonical forms are not usually minimal.
Minimization of Boolean expression is needed to simplify the

Boolean expression and thus reduce the circuitry complexity as it uses less
number of gates to produce same output that can by taken by long
canonical expression.

Boolean Algebra

Uploaded by

Copyright:

Available Formats

Boolean Algebra

Uploaded by

Document Information

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

Boolean Algebra

Uploaded by

Copyright:

Available Formats

Introduction

• Developed by English Mathematician George

No. of possible combinations = 2n, where n=number of

P+P’ is Tautology and P.P’ is Fallacy

2. Verify that P+(PQ)’ is a Tautology.

T7 : Absorption (Redundance) Law

Boolean expression can be represented by either

 In standard SOP and POS each term of Boolean

 In Boolean expression AB+AC the literal C is

Minterm and Maxterm

Individual term of Canonical Products of Sum (POS) is called

Canonical SOP (Sum of Minterms) and POS (Product of Maxterm) is

Canonical forms are not usually minimal.

Minimization of Boolean expression is needed to simplify the

You might also like