Chapter-3

BOOLEAN ALGEBRA

➢ Introduction:
• An algebra that deals with binary number system is called “Boolean Algebra”.
• It is very powerful in designing logic circuits used by the processor of computer system.
• The logic gates are the building blocks of all the circuits in a computer.
• Boolean algebra derives its name from the mathematician George Boole (1815-1864) who is
considered the “Father of symbolic logic”.
• Boolean algebra deals with truth table TRUE and FALSE.
• It is also called as “Switching Algebra”.

➢ Binary Valued Quantities – Variable and Constants:

• A variable used in Boolean algebra or Boolean equation can have only one of two variables.
The two values are FALSE (0) and TRUE (1)
• A Sentence which can be determined to be TRUE or FALSE are called logical statements or
Truth functions and the results TRUE or FALSE is called Truth values.
• The variables which can store the truth values are called logical variables or binary valued
variables. These can store one of the two values 1 or 0.
• The decision which results into either YES (TRUE or 1) or NO (FALSE or 0) is called Binary
decision.

➢ Truth Table:
• A truth table is a mathematical table used in logic to computer functional values of logical
expressions.
• A truth table is a table whose columns are statements and whose rows are possible scenarios.
• Example: Consider the logical expression
Logical Statement: Meals = “Ram prefer rice and roti for the meal”
Y = A AND B (Logical Variables: Y, A, B, Logical Operator AND)
Ram Prefer Rice Ram Prefer Roti Meals
FALSE FALSE FALSE
FALSE TRUE FALSE
TRUE FALSE FALSE
TRUE TRUE TRUE
 • If result of any logical statement or expression is always TRUE or 1, it is called Tautology and
if the result is always FALSE or 0, it is called Fallacy.

➢ Logical Operators:
• There are three logical operator, NOT, OR and AND.
• These operators are now used in computer construction known as switching circuits.

➢ NOT Operator:
• The Not operator is a unary operator. This operator operates on single variable.
• The operation performed by Not operator is called complementation.
• The symbol we use for it is bar.
• 𝐗̅̅ means complementation of X
• If X=1, ̅X = 0 If X=0, ̅X = 1
• The Truth table and the Venn diagram for the NOT operator is:
X ̅X
1 0
0 1

➢ OR Operator:
• The OR operator is a binary operator. This operator operates on two variables.
• The operation performed by OR operator is called logical addition.
• The symbol we use for it is ‘+’.
• Example: X + Y can be read as X OR Y
• The Truth table and the Venn diagram for the NOT operator is:
X Y X+Y
0 0 0
0 1 1
1 0 1
1 1 1

➢ AND Operator:
• The AND operator is a binary operator. This operator operates on two variables.
• The operation performed by AND operator is called logical multiplication.
• The symbol we use for it is ‘.’.
• Example: X . Y can be read as X AND Y
 • The Truth table and the Venn diagram for the NOT operator is:
X Y X.Y
0 0 0
0 1 0
1 0 0
1 1 1

➢ Evaluation of Boolean Expression using Truth Table:

• To create a truth table, follow the steps given below.
• Step 1: Determine the number of variables, for n variables create a table with 2n rows.
o For two variables i.e. X, Y then truth table will need 22 or 4 rows.
o For three variables i.e. X, Y, Z, then truth table will need 23 or 8 rows.
• Step 2: List the variables and every combination of 1 (TRUE) and 0 (FALSE) for the given
variables
• Step 3: Create a new column for each term of the statement or argument.
• Step 4: If two statements have the same truth values, then they are equivalent.

➢ Example: Consider the following Boolean Expression F=X+ 𝐘̅̅’

• Step 1: This expression as two variables X and Y, then 22 or 4 rows.
• Step 2: List the variables and every combination of X and Y.
• Step 3: Create a new column 𝐘̅̅ of the statement, and then fill the truth values of Y in that
column.
• Step 4: The final column contain the values of X+ 𝐘̅̅’.
X Y Y’ X+ 𝐘̅̅’
0 0 1 1
0 1 0 0
1 0 1 1
1 1 0 1

➢ Exercise Problems:
1. Prepare a table of combination for the following Boolean algebra expressions.
a) X’ Y’ + X ’ Y b) XYZ ‘ + X’Y’ Z
2. Verify using truth table for the following Boolean algebra.
a) X + XY = X
➢ Boolean Postulates:
• The fundamental laws of Boolean algebra are called as the postulates of Boolean algebra.
• These postulates for Boolean algebra originate from the three basic logic functions AND, OR
and NOT.
• Properties of 0 and 1:
I. If X ≠ 0 then X = 1, and If X ≠1 then X = 0
II. OR relation ( Logical Addition)
a. 0 + 0 = 0 c. 1 + 0 = 1
b. 0 + 1 = 1 d. 1 + 1 = 1
III. AND relation ( Logical Multiplication)
a. 0 . 0 = 0 c. 1 . 0 = 0
b. 0 . 1 = 0 d. 1 . 1 = 1
IV. Complement Rules
̅=1
a. 0 ̅=0
b. 1
➢ Principle of Duality Theorem:
• This is very important principle used in Boolean algebra.
• Principle of Duality states that;
o Changing each OR sign (+) to an AND sign (.)
o Changing each AND sign (.) to an OR sign (+)
o Replacing each 0 by 1 and each 1 by 0.
• The derived relation using duality principle is called dual of original expression.
• Example: Take postulate II, related to logical addition:
1) 0 + 0 = 0 2) 0 + 1 = 1 3) 1 + 0 = 1 4) 1 + 1 = 1
2. Now working according to above relations, + is changed to . and 0’s replaced by 1’s
a) 1 . 1 = 1 b) 1 . 0 = 0 c) 0 . 1 = 0 d) 0 . 0 = 0
• which are nothing but same as that of postulate III related to logical multiplication.
• So 1, 2, 3, 4, are the duals of a, b, c, d.
• Example: Find the duals for the following Boolean Expression
Sl No Boolean Expression Duals
1 X+0=X X.1=X
2 X+1=1 X.0=0
3 X . ̅X = 0 X + ̅X = 1
4 X . ( Y + Z) X + ( Y . Z)
5 X + X.Y = X + Y X.(X + Y) = X.Y
➢ Boolean Theorems:
• Boolean Theorem can be proved by substituting all possible values of the variable that are 0
and 1.
• This technique of proving theorem is called Proof by perfect induction.
Sl No Theorem Sl No Theorem
Properties of 0 and 1 Associative Law
1 0+X=X 12 X .(Y.Z) = (X.Y).Z
2 1+X=1 13 (X+Y).Z = X+(Y.Z)
3 0.X=0 Distributive Law
4 1.X=X 14 X.(Y+Z) = X.Y + X.Z
Indempotence Law 15 X+Y.Z = (X+Y).(X+Z)
5 X+X=X Absorption Law
6 X.X=X 16 X + XY = X
Complementary Law 17 X(X+Y) = X
7 X + ̅X = 1 18 XY + X ̅Y = X
8 X . ̅X = 0 19 (X+Y)(X+̅Y)= X
Involution Law 20 X+̅XY = X+Y
9 "
X=X 21 X(̅X+Y) = XY
Commutative Law
10 X+Y=Y+X
11 X.Y=Y.X
➢ Theorem 1: 0+X=X
Proof: If X = 0 Proof: If X = 1 Using Truth Table
then LHS =0+X then LHS =0+X
0 X 0+X
=0+0 =0+1
0 0 0
=0 =1
0 1 1
= RHS = RHS

➢ Theorem 2: 1+X=1
Proof: If X = 0 Proof: If X = 1 Using Truth Table
then LHS =1+X then LHS =1+X
1 X 1+X
=1+0 =1+1
1 0 1
=1 =1
1 1 1
= RHS = RHS
➢ Theorem 3: 0.X=0
Proof: If X = 0 Proof: If X = 1 Using Truth Table
then LHS =0.X then LHS =0.X
0 X 0.X
=0.0 =0.1
0 0 0
=0 =0
0 1 0
= RHS = RHS

➢ Theorem 4: 1.X=X
Proof: If X = 0 Proof: If X = 1 Using Truth Table
then LHS =1.X then LHS =1.X
1 X 0.X
=1.0 =1.1
1 0 0
=0 =1
1 1 1
= RHS = RHS

➢ Indempotence Law: “This law states that when a variable is combines with itself
using OR or AND operator, the output is the same variable”.

➢ Theorem 5: X+X=X
Proof: If X = 0 Proof: If X = 1 Using Truth Table
then LHS =X+X then LHS =X+X
X X X+X
=0+0 =1+1
0 0 0
=0 =1
1 1 1
= RHS = RHS

➢ Theorem 6: X.X=X
Proof: If X = 1 Using Truth Table
Proof: If X = 0
then LHS =X.X
then LHS =X.X X X X.X
=1.1
=0+0 0 0 0
=1
=0 1 1 1
= RHS
= RHS

➢ Complementary Law: “This law states that when a variable is And ed with its
complement is equal to 0 and a variable is OR ed with its complement is equal to 1”.
➢ Theorem 7: X + 𝐗̅̅’ = 1
Proof: If X = 0 Proof: If X = 1 Using Truth Table
then LHS = X + ̅X then LHS = X + ̅X
X 𝐗̅̅ X + 𝐗̅̅
=0+1 =1+0
0 1 1
=1 =1
1 0 1
= RHS = RHS

➢ Theorem 8: X . 𝐗̅̅’ = 0
Proof: If X = 0 Proof: If X = 1 Using Truth Table
then LHS = X . ̅X then LHS = X . ̅X
X 𝐗̅̅ X . 𝐗̅̅
=0.1 =1.0
0 1 0
=0 =0
1 0 0
= RHS = RHS

➢ Involution Law: “This law states that when a variable is inverted twice is equal to
the original variable”.
➢ Theorem 9: "𝐗̅ = X

Proof: If X = 0, then ̅X = 1 Using Truth Table

Take complement again, then "X = 0 i.e. X X 𝐗̅̅ "
𝐗̅
If X = 1, then ̅X = 0
0 1 0
Take complement again, then "X = 1 i.e. X 1 0 1

➢ Commutative Law: “This law states that the order in which two variable are Or ed
or AND ed make no difference”.

➢ Theorem 10: X+Y=Y+X

Proof: If Y = 0 Proof: If Y = 1 Using Truth Table
then LHS =X+Y then LHS =X+Y
X Y X+Y Y+X
=X+0 =X+1
0 0 0 0
=X =1
0 1 1 1
RHS =Y+X RHS =Y+X
1 0 1 1
=0+X =1+X
1 1 1 1
=X =1
Therefore LHS = RHS Therefore LHS = RHS
➢ Theorem 11: X.Y=Y.X
Proof: If Y = 0 Proof: If Y = 1 Using Truth Table
then LHS =X.Y then LHS =X.Y
X Y X.Y Y.X
=X.0 =X.1
0 0 0 0
=0 =X
0 1 0 0
RHS =Y.X RHS =Y.X
1 0 0 0
=0.X =1.X
1 1 1 1
=0 =X
Therefore LHS = RHS Therefore LHS = RHS

➢ Associative Law: “This law allows the removal of brackets from an expression and
regrouping of the variables”.

➢ Theorem 12: X.(Y.Z) = (X.Y).Z

Proof: If Y = 0 Proof: If Y = 1 Using Truth Table
LHS = X.(Y.Z) LHS = X.(Y.Z)
X Y Z XY YZ X.(Y.Z) (X.Y).Z
= X.(0.Z) = X.(1.Z)
0 0 0 0 0 0 0
= X.0 = X.Z
0 0 1 0 0 0 0
=0 = XZ
0 1 0 0 0 0 0
RHS = (X.Y).Z RHS = (X.Y).Z
0 1 1 0 1 0 0
= (X.0).Z = (X.1).Z
1 0 0 0 0 0 0
= 0.Z = X.Z
1 0 1 0 0 0 0
=0 = XZ
1 1 0 1 0 0 0
Therefore LHS = RHS Therefore LHS = RHS
1 1 1 1 1 1 1

➢ Theorem 13: X+(Y+Z) = (X+Y)+Z

Proof: If Y = 0 Proof: If Y = 1 Using Truth Table
LHS = X+(Y+Z) LHS = X+(Y+Z)
X Y Z X+Y Y+Z X+(Y+Z) (X+Y)+Z
= X+(0+Z) = X+(1+Z)
0 0 0 0 0 0 0
= X+Z = X+1 0 0 1 0 1 1 1
=1 0 1 0 1 1 1 1
RHS = (X+Y)+Z RHS = (X+Y)+Z 0 1 1 1 1 1 1
= (X+0)+Z = (X+1).Z 1 0 0 1 0 1 1
= X+Z = 1+Z 1 0 1 1 1 1 1
1 1 0 1 1 1 1
Therefore LHS = RHS =1
1 1 1 1 1 1 1
Therefore LHS = RHS
➢ Distributive Law: “This law allows the multiplying or factoring out an expression”.
➢ Theorem 14: X.(Y+Z) = XY + XZ
Proof: If X = 0 Proof: If X = 1
LHS = X.(Y+Z) LHS = X.(Y+Z)
= 0.(Y+Z) = 1.(Y+Z)
=0 = Y+Z
RHS = XY + XZ RHS = XY + XZ
= 0.Y+0.Z = 1.Y+1.Z
=0 = Y+Z
Therefore LHS = RHS Therefore LHS = RHS

➢ Theorem 15: (𝑋 + 𝑌) (𝑋 + 𝑍) = 𝑋 + 𝑌𝑍
LHS: (𝑋 + 𝑌) (𝑋 + 𝑍) = 𝑋𝑋 + 𝑋𝑍 + 𝑋𝑌 +𝑌𝑍
= 𝑋 + 𝑋𝑍 + 𝑋𝑌 + 𝑌𝑍
= 𝑋(1 + 𝑍) + 𝑋𝑌 + 𝑌𝑍
= 𝑋 + 𝑋𝑌 + 𝑌𝑍
= 𝑋(1 + 𝑌) + 𝑌𝑍
= 𝑋 + 𝑌𝑍
= RHS

➢ Absorption Law: “This law enables a reduction of complicated expression to a

simpler one by absorbing common terms”.
17) X (X+Y) = X 18) XY + X𝐘̅̅ = X
16) X+XY = X
LHS = X (X+Y) LHS = XY + X ̅Y
LHS = X + XY
= XX + XY = X(Y+ ̅Y)
= X (1 + Y)
= X + XY = X.1
=X
= X (1+Y) =X
= RHS
=X = RHS
19) (X+Y) (X+𝐘̅̅)= X
20) X + 𝐗̅̅Y = X+Y 21) X (𝐗̅̅+Y) = XY
LHS = (X+Y) (X+ ̅Y)
LHS = X + ̅X Y LHS = X ( ̅X+Y)
= XX + X ̅Y + XY + Y ̅Y
= (X + ̅X ) (X+Y) = X. ̅X + X.Y
= X + X ̅Y + XY + 0
= 1. (X+Y) = 0 + XY
= X (1 + ̅Y + Y)
= X+Y = XY
= X. 1
= RHS = RHS
=X
➢ DeMorgan’s Theorem:
• DeMorgan’s First Theorem:
o Statement: “When the OR sum of two variables is inverted, this is same as inverting
each variable individually and then AND ing these inverted variables”
o This can be written as 𝐗̅ ̅ ̅ ̅+
̅ 𝐘̅̅ ̅ = 𝐗̅̅. 𝐘̅̅
o We can prove the DeMorgan’s First theorem by using Truth Table is
X Y 𝐗̅̅ 𝐘̅̅ X+Y 𝐗̅ ̅ ̅ ̅+
̅ 𝐘̅̅ ̅ 𝐗̅̅. 𝐘̅̅
0 0 1 1 0 1 1
0 1 1 0 1 0 0
1 0 0 1 1 0 0
1 1 0 0 1 0 0

o Compare the column 𝐗̅ ̅ ̅ ̅+

̅ 𝐘̅̅ ̅ and 𝐗̅̅. 𝐘̅̅. Both of these are identical. Hence the DeMorgan’s
first theorem is proved.
• DeMorgan’s Second Theorem:
o Statement: “When the AND product of two variables is inverted, this is same as
inverting each variable individually and then OR ing these inverted variables”
o This can be written as 𝐗̅̅ ̅ . 𝐘̅̅̅ = 𝐗̅̅+𝐘̅̅
o We can prove the DeMorgan’s Second theorem by using Truth Table is:
X Y 𝐗̅̅ 𝐘̅̅ X.Y 𝐗̅̅̅. 𝐘̅̅̅ 𝐗̅̅+𝐘̅̅
0 0 1 1 0 1 1
0 1 1 0 0 1 1
1 0 0 1 0 1 1
1 1 0 0 1 0 0

o Compare the column 𝐗̅̅̅. 𝐘̅̅̅ and 𝐗̅̅+𝐘̅̅. Both of these are identical. Hence the DeMorgan’s
Second theorem is proved.
• Application of DeMorgan’s Theorem:
o It is used in simplification of Boolean expression.
o DeMorgan’s law commonly apply to text searching using Boolean operators AND, OR and
NOT.
o It is useful in the implementation of the basic gates operations with alternative gates.
➢ Simplification of Boolean Expression:
• Simplification of Boolean expression can be achieved by two popular methods:
o Algebraic Manipulation
o Karnaugh Maps
• Algebraic Manipulation:

1) 𝐗̅̅ 𝐘̅̅ Z + 𝐗̅̅ Y Z + X 𝐘̅̅ 2) XYZ + XYZW + XZ

= ̅X ̅Y Z + ̅X Y Z + X ̅Y = XYZ (1 + W) + XZ

= ̅XZ (̅Y + Y) + X ̅Y = XYZ . 1 + XZ

= ̅XZ (1) + X ̅Y = XZ (Y + 1)
= XZ
= ̅XZ + X ̅Y
3) Z(Y+Z)(X+Y+Z)
= (ZY + ZZ) (X+Y+Z) 4) 𝐗̅ + 𝐗̅̅ 𝐘̅ + 𝐘̅̅ + (𝐗̅ + 𝐘̅̅)𝐗̅̅ 𝐘̅

= (ZY + Z) (X+Y+Z) = X + ̅X Y + ̅Y + X ̅X Y + ̅Y ̅X Y
= Z(X+Y+Z) [Theorem 16 X+XY=Z] = X + ̅X Y + ̅Y + 0 + 0
= ZX + ZY + ZZ = (X + ̅X) (X + Y) + ̅Y
= ZX + ZY + Z = 1 (X + Y) + ̅Y
= Z(X+Y+1) = X + Y + ̅Y
= Z(1) =X+1
=Z =1

➢ Exercise Problems: Simplify using Algebraic Manipulation

̅ + B). (A + B)
1) (A
̅B
̅ +A
2) AB + AB
̅ + B C̅+ C
3) B(A+C) + AB
➢ Exercise Problems: Solving using DeMorgan’s Theorem
̅ + C). (B + D)
1) (A
̅ +C
2) AB