www.knowpythonbytes.blogspot.

com

Mrs. Payal Bhattacharjee

PGT(C.Sc.)
K V No. I Kanchrapara
 XI Computer Science
UNIT-1
Chapter-3
Boolean Algebra
• Introduction to Boolean Algebra
• Logical Operators NOT, AND, OR, and Boolean Logic
• Principle of Duality
• Basic Postulates of Boolean Algebra
• DeMorgan’s Theorem
• Universal Gates (NAND, NOR) , XOR
• Truth Tables
• Logic Gates/Circuits
 What is Boolean algebra?
Who introduced it?
In 1854, Mathematician George Bool introduced a systematic
treatment of logic and develop for this program and algebraic
system called BOOLEAN ALGEBRA.
In 1938, Sennon demonstrated that the properties of by-
stable switching circuits can be represented by this algebra and
called it switching algebra.
By what it is made of???
A Switching Algebra or Boolean Algebra is an algebraic
system consisting of the set {0,1} the binary operations ‘OR’ &
‘AND’ denoted the symbol ‘+’ and ‘.’ respectively and unary
operation called NOT denoted by prime(’)/not/bar symbol.
Boolean Algebra uses a set of Laws and Rules to define the
operation of a digital logic circuit.
LOGICAL OPERATORS
• Boolean algebra also deals with functions which have their values in the set {0,
1}. The basic operations of Boolean algebra are as follows:
• Conjunction ( AND operation)
• Disjunction ( OR operation)
• Negation ( Not operation)

TRUTH TABLE:
• A Truth Table is a table which represents all the possible input combinations of
logical variables along with all the possible results/output of the given
combinations of values.

LOGIC GATES:
• Logic gates are the basic building blocks of any digital system. It is an
electronic circuit having one or more than one input and only one output. The
relationship between the input and the output is based on a certain logic.
Based on this, logic gates are named as AND gate, OR gate, NOT gate etc.
 AND Operator
Operation performed by AND operator is called
Logical Multiplication. Thus X.Y means X AND Y.
0.0=0
0.1=0
1.0=0
1.1=1
The Symbol and Truth table of AND gate
X Y F= ( X.Y)
X
F 0 0 0
Y
0 1 0
1 0 0
1 1 1
 OR Operator
Operation performed by OR operator is called
Logical Addition. Thus X+Y means X OR Y.
0+0=0
0+1=1
1+0=1
1+1=1
The Symbol and Truth table of OR gate
X Y F=(X+Y)
X 0 0 0
F
Y 0 1 1
1 0 1
1 1 1
 NOT Operator
This operator operates on single variable and
operation performed by NOT operator is called
complementation. Thus X’ means complement of X.
0’=1
1’=0
The Symbol and Truth table of NOT gate
X X’
X X’ 0 1
1 0
 What is Basic Postulates Of Boolean
Algebra?
Boolean algebra, consists of fundamental laws that are used to build
a workable, cohesive framework upon which are based the theorem of
Boolean algebra. These fundamental laws are known as Basic
Postulates Of Boolean Algebra.
POSTULATES

i. If X!=0 then X=1; If ii. OR relations

X!=1 then X=0 0+0=0
0+1=1
1+0=1
1+1=1
iii. AND relations iv. NOT relations
0.0=0 0’=1
0.1=0 1’=0
1.0=0
1.1=1
 What is the Principle Of Duality?
This principle states that starting with a Boolean relation,
another Boolean relation can be derived by:
1. Changing each OR sign(+) to an AND sign(.)
2. Changing each AND sign(.) to an OR sign(+)
3. Replacing each 0 by 1 and each 1 by 0.
Example:-
If X.Y=1 then its dual will be X+Y=0
, where X & Y belongs to 0,1.
Example:-
If (X+Z)(Y+1)=1 then its dual will be X.Z+Y.0=0
, where X & Y belongs to 0,1.
NOTE:-
The derived relation using duality principle is called
Dual Of Original Expression.
1.Properties of 0 and 1
a) 0+X=X 0 X R=X
0 0 0 0
X
X 0 1 1

b) 1+X=1 1 X R=1
1 1 0 1
1
X 1 1 1
c) 0.X=0
0 X R=0
0
0 0 0 0
X
0 1 0
d) 1.X=X
1 1 X R=X
X
X 1 0 0
1 1 1
2. Indempotence Law
The law states that,
a) X+X=X
X X R=X
X
X 0 0 0
X
i.e.,
1 1 1
0+0=0
1+1=1

b) X.X=X
X
X X R=X
X
X 0 0 0
i.e., 1 1 1
0.0=0
1.1=1
3.Involution Law
The law states that,

(X’)’=X
X’
X (X’)’=X

X X’ (X’)’ = X
0 1 0
1 0 1
4.Complementarity Law
The law states that,
a) X+X’=1
X X’ R=X+X’
X
X+X’=1 0 1 1
X’ i.e.,
0+1=1
1 0 1
1+0=1

b) X.X’=0 X X’ R=X.X’
X 0 1 0
X.X’=0
X’ 1 0 0
i.e.,
0.1=0
1.0=0
5.Commutative Law
The law states that,
a) X+Y=Y+X
X Y
Y R X R

X Y R=X+Y R=Y+X
0 0 0 0
0 1 1 1
1 0 1 1
1 1 1 1
+ is OR
5.Commutative Law
b) X.Y=Y.X
X Y
R R
Y X

X Y R=X.Y R=Y.X
0 0 0 0
0 1 0 0
1 0 0 0
1 1 1 1
. is AND
 6.Associative Law
The law states that,
a) X+(Y+Z)=(X+Y)+Z
X R X X+Y
Y Y R
Z Z
Y+Z

X Y Z Y+Z X+Y R=X+(Y+Z) R=(X+Y)+Z

0 0 0 0 0 0 0
0 0 1 1 0 1 1
0 1 0 1 1 1 1
0 1 1 1 1 1 1
1 0 0 0 1 1 1
1 0 1 1 1 1 1
1 1 0 1 1 1 1
1 1 1 1 1 1 1
 6.Associative Law
The law states that,
b) X (Y.Z)=(X.Y) Z
X R X XY
Y
R
Y
Z YZ Z

X Y Z YZ XY R=X(YZ) R=(XY) Z
0 0 0 0 0 0 0
0 0 1 0 0 0 0
0 1 0 0 0 0 0
0 1 1 1 0 0 0
1 0 0 0 0 0 0
1 0 1 0 0 0 0
1 1 0 0 1 0 0
1 1 1 1 1 1 1
 7. Distributive Law (First)
The law states that,
a) X(Y+Z)=XY+XZ X XY
Y
X R
R
Y
Z Y+Z
Z XZ

X Y Z Y+Z XY XZ R=X(Y+Z) R=XY+XZ

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 0 1 1 1
1 1 0 1 1 0 1 1
1 1 1 1 1 1 1 1
 7. Distributive Law (Second)
The law states that, b)X+YZ=(X+Y).(X+Z)
X X+Y
Y
X R
Y R
Y.Z
Z
Z X+Z
PROOF ( By Algebraic Method)
R.H.S = (X+Y).(X+Z)
(Distributive Law1
=X.(X+Z)+Y.(X+Z) X(Y+Z)=XY+XZ)
= X.X+XZ+XY+YZ
=X+XZ+XY+YZ (Properties of 0 and 1)
=(X.1)+XZ+XY+YZ (Properties of 0 and 1 ,
=X(1+Z+Y) + YZ X=X.1)
=X.1+YZ (Properties of 0 and 1)
=X+YZ = L.H.S Hence Proved
 7. Distributive Law (Third)
The law states that, c) X+X’Y=X+Y
X X
X
R
X’ Y
X’Y
Y

PROOF ( By Algebraic Method)

L.H.S. = X+X’Y
=X.1+X’Y (Properties of 0 and 1)
(Properties of 0 and 1)
=X(1+Y)+X’Y
=X+XY+X’Y
=X+Y(X+X’) (Complementarity Law)
=X+Y.1 (Properties of 0 and 1)
=X+Y
=R.H.S. Hence Proved
 8. Absorption Law
The law states that, a) X+XY=X
X
X

Y XY
X Y X.Y X+XY
0 0 0 0
0 1 0 0
1 0 0 1
PROOF ( By Algebraic Method) 1 1 1 1
L.H.S. = X+XY
=X(1+Y) (By Properties of 0 and 1)
=X.1 = X
=R.H.S. Hence Proved
8. Absorption Law
The law states that, b) X(X+Y)=X
X
X

Y X.Y

PROOF ( By Algebraic Method)

L.H.S =X(X+Y) (Distributive Law )
=X.X+X.Y (Indempotence Law)
=X+X.Y
(Properties of 0 and 1),
=X(1+Y) 1+Y=1
=X
=R.H.S Hence Proved
 DeMorgan’s First Theorem
It states that (X+Y)’=X’.Y’
X’
X
X R R
Y
X+Y X+Y X’.Y’
Y
Y’

Let us assume that P=X+Y where P,X,Y are logical

variables. Then, according to complementarity law,
P+P’=1 and P.P’=0.
i.e., if P=X+Y then P’=X’Y’ , so,
P+P’= (X+Y)+X’Y’ must be equal to 1
and P.P’ = (X+Y).(X’Y’) must be equal to 0
NOTE: BOTH THE DEMORGANS THEOREM CAN BE PROVED USING TRUTH TABLE ALSO
Let us prove the first part of 1st theorem,
i.e.,
(X+Y)+(X’Y’)=1

L.H.S.
= (X+Y)+(X’Y’) (Distributive Law: A+BC=(A+B).(A+C) )

= (X+Y+X’).(X+Y+Y’) (Complementarity Law: X+X’=1)

= (1+Y).(X+1) (Properties of 0 and 1)

= 1.1 (Properties of 0 and 1)

=1
Hence First Part Proved
Now, let us prove the second part of 1st
theorem, i.e.,
(X+Y).(X’Y’)=0
L.H.S.
= (X+Y).(X’Y’) (Distributive Law): A+B).C=A.C+A.B
= (XX’Y’)+(YX’Y’) (Associative Law): X.Y=Y.X
= (XX’Y’)+(X’YY’) (Complementarity Law): X.X’=0
= (0.Y’) + (X’.0) (Properties of 0 and 1)
= 0+0 (Properties of 0 and 1)
=0 Hence Second Part Proved
Thus, De-Morgan’s 1st Law proved (X+Y)’=X’.Y’
 DeMorgan’s Second Theorem
It states that, (X.Y)’=X’+Y’
X’
X
X R R
Y
XY XY X’+Y’
Y
Y’

Let us assume that P=X.Y where P,X,Y are logical

variables. Then, according to complementarity law,
P.P’=1 and P.P’=0.
i.e., if P=X.Y then P’=X’+Y’ so, we have to prove
P+P’= XY+(X’+Y’) must be equal to 1
and P.P’= XY.(X’+Y’) must be equal to 0
Let us prove the first part of 2nd theorem, i.e.,
XY+(X’+Y’)=1
L.H.S.
= XY+(X’+Y’) (Distributive Law:
=(X+X’+Y’).(Y+X’+Y’) A+BC=(A+B).(A+C) )
= (X+X’+Y’).(X’+Y+Y’) (Commutative Law): X+Y=Y+X
= (1+Y’). (X’+1) (Properties of 0 and 1): X+1=1
= 1.1
=1 (Properties of 0 and 1): 1.1=1

Hence First Part Proved

Now, let us prove the second part of 2nd
theorem, i.e.,
XY.(X’+Y’)=0
L.H.S.
= (XY).(X’+Y’) (Distributive Law): A+B).C=A.C+A.B
= XY.X’+XY.Y’ (Associative Law): X.Y=Y.X
= X.X’.Y + X.Y.Y’ (Complementarity Law): X.X’=0
= 0.Y + X.0 (Properties of 0 and 1)
= 0+0 (Properties of 0 and 1)
=0
Hence Second Part Proved
Thus, De-Morgan’s 2nd Law proved (XY)’=X’+Y’
 Boolean Algebra Rules
1. 0+X=X Properties of 0
2. 0.X=0
3. 1+X=1 Properties of 1
4. 1.X=X
5. X+X=X Indempotence Law
6. X.X=X
7. (X’)’=X Involution Law
8. X+X’=1 Complementarity Law
9. X.X’=0
 Boolean Algebra Rules
10. X+Y=Y+X
Commutative Law
11. X.Y=Y.X
12. X+(Y+Z)=(X+Y)+Z
Associative Law
13. (X.Y).Z=X.(Y.Z)
14. X(Y+Z)=XY+XZ
Distributive Law
15. X+YZ=(X+Y).(X+Z)
16. X+XY=X
Absorption Law
17. X(X+Y)=X
18. X+X’Y=X+Y Third Distributive Law
19. (X+Y)’=X’.Y’
Demorgan’s Theorem
20. (X.Y)’=X’+Y’
 NAND Gate
NAND gate is a universal gate which is a
combination of AND with NOT X Y X.Y F= X.Y

X 0 0 0 1
F= X.Y
Y 0 1 0 1
1 0 0 1
2 input NAND Gate
1 1 1 0
X
Y X Y Z X.Y.Z X.Y.Z
0 0 0 0 1
3 input NAND Gate
P 0 0 1 0 1
Q 0 1 0 0 1
R
0 1 1 0 1
4 input NAND Gate 1 0 0 0 1
A
1 0 1 0 1
B 1 1 0 0 1
C
D 1 1 1 1 0
 NOR Gate
NOR gate is a universal gate which is a
combination of OR with NOT X Y X+Y F=X+Y

X 0 0 0 1
F= X+Y
Y 0 1 1 0
1 0 1 0
2 input NOR Gate
1 1 1 0
X
Y F X Y Z X+Y+Z F=X+Y+Z
0 0 0 0 1
3 input NOR Gate
P 0 0 1 1 0
Q 0 1 0 1 0
R F 0 1 1 1 0
4 input NOR Gate 1 0 0 1 0
A
1 0 1 1 0
B 1 1 0 1 0
C F
D 1 1 1 1 0
 XOR Gate
XOR gate produces output 1 for only those input No. of 1’s X Y X + Y
combinations that have ODD number of 1’s Even/Odd
Even 0 0 0
X
Y F=X+Y Odd 0 1 1
Odd 1 0 1
XOR Addition can be summarized as: Even 1 1 0
0 + 0=0 0 + 1=1
No. of 1’s X Y Z F= X + Y + Z
1 + 0=1 1 + 1=0
Even 0 0 0 0
3 input XOR Gate
Odd 0 0 1 1
P
Q Odd 0 1 0 1
R F Even 0 1 1 0

4 input XOR Gate

Odd 1 0 0 1
Even 1 0 1 0
A
B Even 1 1 0 0
C F
D Odd 1 1 1 1
Q) Verify the following expression using Truth Table:

(A’+B’).(A+B) = A’.B + A.B’

Solution :
A B A’ B’ A’+B’ A+B (A’+B’).(A+B) A’.B A.B’ (A’.B)+(A.B’)

0 0 1 1 1 0 0 0 0 0
0 1 1 0 1 1 1 1 0 1
1 0 0 1 1 1 1 0 1 1
1 1 0 0 0 1 0 0 0 0
Since, Column no. 7 and 10 are having same values as per the given
question. Hence, proved.
Q) Draw a logic circuit for the following expression:
F(X,Y,Z) = (X+Y’+Z).(X+Y’+Z’)

Solution:
X X+Y’+Z
Y’
Z
F

X
.
(X+Y’+Z) (X+Y’+Z’)

Y’
Z’ X+Y’+Z’
Q) Write the equivalent Boolean expression for
the following logic circuit:

Solution :
F(A,B,C) = A’B+AB+B’C
Q) Draw a logic circuit for the following expression:
F(A,B,C) = (AB’C)+(C’B)
Using NAND-to-NAND Logic Gate only.

Solution:
A (A.B’.C)
B B’
C F(A,B,C)

C C’
(C’.B)
B (AB’C). (C’B)
De-Morgan’s
Theorem
(applied). = (AB’C)+ (C’B)

NOTE: No need to solve. Directly write the answer. This is done just to prove = (AB’C)+(C’B)
and show.
 REFERENCES

•Wikipedia

•Tutorialspoint

•XII Computer Science by Sumita Arora, Edition:2016

Stay safe. Stay aware. Stay healthy. Stay alert.