Boolean Algebra

And Logic Gates

Boolean Algebra
3 And Logic Gates NOTES

The Chapter Covers :

n Introduction
n Boolean Algebra
n Binary Valued Quantities
n And Operator
n OR Operator
n NOT Operator
n Basic Postulates of Boolean Algebra
n Therorems of Boolean Algebra
n De Morgan's Theorems
n Reducing Boolean Expression by their Simplifications
n Proving the Equations of Boolean Expressions By Truth Table
n Principle of Duality
n Standard Forms
n Basic Logic Gates
n Use of Logic Gates in Circuits
n Karnaugh Maps

Introduction
______________________________________________________________________________________

Boolean Algebra is the algebraic structure of Abstract Algebra in which required properties
of set operations and logic operations. Expecially it contains intersection, union and comple-
ment set operations and AND,OR and NOT logic operations. Logic gates act on signals
which express true or false. Logic gates help in building a circuit. This chapter deals with
the concerned topics in detail.
45
Fundamentals of Boolean Algebra
______________________________________________________________________________________
Computers &
Information Technology Let us know what Boolean Algebra is. It is a part of Algebra.
It was invented by an British Mathematician Jeorge Boole. Boolean logic is a
It is used to simplify the electronic digital circuits. With its complete system of logical
NOTES
help, one writes expressions for complex Circuits and these processes. It was named
are turned into simple expressions through some simple after an English
rules. These simple expressions remove complexities from mathematician, George
the circuits. The main principle of Boolean algebra is that Boole. He was the first
an equation has either True or False value. Digit 1 or letter to explain the algebraic
T express truth while digit 0 or letter F, express False. system of logic in mid
19th century. Boolean
According to Boolean Algebra there are two probabilities logic is extremely useful
for a statement. First it is True or Second it is False. in electronic computer
Boolean algebra has only two possible values True or hardware and software.
False. That is why it's also called Two state Algebra. Let
us analyze the following statements carefully.
n The capital of India is New Delhi.
n 2 and 2 add up to 5.
n The sun rises in the east.
Here statements 1 and 3 are True, while statement 2 is False. Here different logics
have been supplied in the statements. Therefore the True and False conditions of the
statements are called Logical Values. The Logical values True and False are called
Logical constant.
By adding two statements, we can frame a new statement and this new statement
again will have logical constants as its value. Such as-
______________________________________________________________________________________

"The moon revolves round the earth." AND

"The earth moves round the sun."
______________________________________________________________________________________

Here "AND" has linked two statements. If these two added statements are true, then the
entire statement will be true. If any of the statements added by AND is False, the entire
statement will be False. such as-
______________________________________________________________________________________

"The capital of India is Jaipur AND Jaipur is a city in Rajasthan."

______________________________________________________________________________________

Here the entire statement is not True as the capital of India is not Jaipur. Boolean Algebra
turns set of statements into symbols and expressions. These symbols and Expressions are
manipulated on the basis of some rules.

Binar y Valued Quantities

______________________________________________________________________________________

You know that in Binary Number System two digits 1 and 0 are used. In Boolean Algebra,
the values of the statements True and False are expressed by 1 and 0 respectively. 1 and
0 are called Binary Valued Quantities. It means the values of Boolean algebraic expressions
1 and 0 are called Binary Values Quantities. Where 1 stands for True and 0 stands for
False. Claude Shannon and other mathematicians used the symbolic logics of Boolean
Algebra for the analysis of switching circuits at Bell Laboratories in 1938. Switch is a device
made to continue or discontinue electric transmission in an electric circuit. If the switch
is ON, then the current flows in the circuit and if it is OFF, the current flow stops. The
circuit interconnecting such switches is called switching circuit. A switch is ON or OFF in
46 two conditions. When it is ON it allows the flow of current and if it is OFF the current
flow halts. (See figure 3.1)
 Boolean Algebra
(a) Open
And Logic Gates
(b) Close

Figure 3.1 : Current Flow NOTES

In the statements of Boolean algebra these complex circuits are expressed. These
expressions are simplified by the Basic Postulates of Boolean Algetra. The simple circuits
can be prepared based on these simplified expressions which increases the efficiency
of the circuits and saves time.

AND operator
______________________________________________________________________________________

Focus on the circuit given in the following picture. It has two switches S1 and S2 connected
to a battery and a bulb. The two situations possible for the flow of electric current in the
bulb are as follows -

Switch S1 Switch S2

Bulb B

Current Flow

Figure 3.2 : AND Operator

Situation 1 S1 = Open and S2 = Open, current will not flow in the bul B.
Situation 2 S1 = Open and S2 = Closed, current will not flow in the bul B.
Situation 3 S1 = Closed and S2 = Open, current will not flow in the bul B.
Situation 4 S1 = Closed and S2 = Closed, There will be current flow in the bul B.
These results can be expressed in table 3.1 in a tabular form :

S1 S2 B Truth table is a kind of

Closed Closed Current Flow mathematical table
No No No which is used to deter-
No Yes No mine whether an ex-
Yes No No pression is true or false
Yes Yes Yes in the logic

Table 3.1 : The results of AND operator

You know that a logic has only two possible values Yes or No. If Yes is replaced by 1 and
No is replaced by 0, the simple form of Table 3.1 is obtained as table 3.2.

S1 S2 B
Closed Closed Current Flow
0 0 0
0 1 0
1 0 0
1 1 1
47
Table 3.2 : The results of AND operator
Fundamentals of Table 2, expresses a simple statement the value of B will be True while S1 and S2 are
Computers & True. This statement can be written mathematically like this -
Information Technology B = S1 AND S2
When a new statement is prepared by adding two statements it is called a compound
NOTES statement. The above said compound statement is added with AND. Here AND is an
operator which adds two logics. AND operator is called Logical AND.
A Table which expresses all the possibilities of a switching circuit as Binary Valued Quantity
1 and 0 is called Truth Table. Table 3.2 is an example of a Truth Table. Here B is affected
with S1 and S2 conditions. If S1 and S2 conditions are taken as Input the output is seen on
the Bulb B. In the truth table the effect of all the possible inputs on the switching circuits
is seen on the output. For AND two inputs a and b and output c have been given in Truth
Table 3...

a b c
0 0 0
0 1 0
1 0 0
1 1 1
Table 3.3 : Truth Table for AND

OR Operator
______________________________________________________________________________________
Switch S1
Let's focus on switching circuit in the
following picture in which two switches
→
S1 and S2 have been connected parallelly
and electric bulb B and battery have →
been added in a series. Switch S2

Figure 3.3

For this circuit the following situations of electric transmission are possible -
Situation 1. S1 = Open or (OR) S2 = Open
There is no current flowing in bulb B.
S1
Situation 2. S1 = open (OR) S2 = closed there →
is current flow on bulb B.
S2
→
Situation 3. S1 = closed (OR) S2 = open Current flow

There is current flow in bulb B. Figure 3.4

Situation 4- S1 = closed (OR) S2 = closed

The current flows in bulb B.

Current flow
S1

S2

48
Figure 3.5
For the situations, the truth table for the switching circuit will be as follows : Boolean Algebra
And Logic Gates
S1 S2 B
0 0 0
0 1 1 NOTES
1 0 1
1 1 1
Table 3.4

It is clear from the table given above that if any of S1 or S2 or (OR) both are closed, the
current will flow in the bulb. It can be written mathematically in the following way-
B = S1 OR S2
Here OR works as a logic operator in the compound statement. That is why it is called
logical OR. Similarly, if the Inputs are a and b, then in their switching circuit, the truth
table affecting the 0 output will be as follows :

a b 0
0 0 0
0 1 1
1 0 1
1 1 1
Table 3.5

NOT Operator
______________________________________________________________________________________

Let's focus on the switching circuit given below. Here a switch S has been connected in
such a way that it will open only when current flows in the bulb otherwise if it is closed,
there will be no current flow in the bulb.

Battery B bulb
S1, switch

Table 3.6

The following conditions are possible for this switching circuit -

Condition 1. S = open, current flow in the bulb B.
Condition 2. S = closed, no current flow in the bulb B.
The truth table for this switching circuit will be as follows :
S B
0 1
1 0
Here, it is noteworthy that only one switch S has been fitted in this switching circuit. The
current will flow in the bulb only when the switch S is open. Therefore the opposite result
is obtained. It can be written mathematically in the following way :
B = NOT S
Here the NOT operator is called logical NOT. The other names of NOT operator are 49
Negation and Inverse operator.
Fundamentals of If the input is a, all the possibilities of the output are expressed the following way in
Computers & truth table given below :
Information Technology a Result
1 0
NOTES 0 1

If the statement has been expressed by a then if NOT operation is performed upon
it the acquired result is expressed by a'. It means if there is an input a its NOT operation
can be expressed with a'.
a' = NOT a

Basic Postulates of Boolean Algebra

______________________________________________________________________________________

In boolean algebra, to simplify the complex expressions there are some accepted facts and
postulates. These rules are the basis of boolean algebra. By simplifying boolean expressions,
electronic circuits are prepared for an operation. If the boolean expression for an operation
is complex, the electronic circuit prepared on its basis is also complex. Therefore it is
necessary to simplify boolean expressions.
Suppose, S is a set whose elements are boolean amounts, the following postulates will be
accepted.

If a, b, c, 0, 1 are the elements of set S, it means a, b, c, 0, 1 ∈ S.

Rule 1. (i) a + b ∈S
(ii) a . b ∈S
(iii) a' ∈S
(iv) b' ∈S
This rule will also be considered true for more then two elements.
Rule 2. Logical operations OR and AND will be as follows -
a + b = b + a
a . b = b . a
Rule 3. The Distrubutive Rule distrubites 't' on '.' or .' on '+'.
a . (b + c) = a . b + a . c
a + b . c = (a + b) . (a + c)
Rule 4. a + (b + c) = (a + b) + c = a + b + c
a . (b . c) = (a.b).c = a . b . c
Rule 5. a+ 0 = 0 + a = a
a . 1 = 1 . a = a

Rule 6. If a ∈ S, its complement a' ∈ S will be as follows :

a + a' = 1 = a' + a
a . a' = 0 = a' . a
Thus, the set S includes operations of OR, AND and NOT. The above given postulates
50 are also called Huntington's (1904) postulates.
Theorems of Boolean Algebra Boolean Algebra
______________________________________________________________________________________
And Logic Gates
The following theorems are important to solve boolean expressions -
Theorem 1 :
NOTES
A Boolean expression, in which the operations of + or. Operators have been performed
on a single Boolean quality, then its value is equal to the Boolean quality itself, i.e.
it remains unchanged.

If a ∈S- a a
a + a = a
a =
and a . a = a
a a a
Theorem 2 :
Indentity Law : =
If a ∈ S
a + 1 = 1 and 1 + a = 1
a . 0 = 0 and 0 . a = 0
a
Theorem 3 : 1
......
Absorption Law : 1 =

If a, b ∈ S,
a
a + (a . b) = a
=
and a . (a + b) = a
Theorem 4 :
a
a
Complementation Law :
1 =
If a ∈ S,
(i) (a')' = a a a
a
(ii) 0' = 1 b =
1
(iii) 1' = 0
DE MORGAN'S THEOREMS
De Morgan was a friend of George Boole who did research on logical mathematics. He
propounded two following theorems -
Theorem 5 : According to this theorem the value of the complement of the sum of
two boolean quantities is equal to the value of the product of separate
complements of these quantities.
(a + b)' = a' . b'
Theorem 6 : According to this theorem, the value of the complements of the products
of two boolean quantities is equal to the sum of separate complements
of these quantities."
(a . b)' = a' + b'
The following theorems are used to simplify the boolean expressions which also simplifies
the making of electronic circuits based on the expressions and their effect and action 51
Fundamentals of remain the same. For example, there is an expression a + (a . b). The circuit prepared
Computers & on its basis will be as follows-
Information Technology a

a b
NOTES

While, according to theorem-3, a + (a . b) = a, therefore the simplified expression of

a + (a . b) is a, therefore, the circuit prepared on the basis of expression a is as
follows -
a

The action and effect of both the circuits of the above given pictures are same, but the
circuit of the later picture is not more complex as compared the previous one. Therefore,
the circuit of the later figure is used.

Reducing Boolean Expressions by their Simplifications

______________________________________________________________________________________

The boolean expression for an operation may be complex. These complex expressions are
simplified with the help of the postulates and theorems of boolean algebra. It has the
following examples -
Example 1 : Simplify -
a . (a + b)
Solution : a . (a + b) = a . a + a . b
= a + a . b (from theorem 1 a . a = a)
= a (from theorem 3, a + a . b = a)
therefore, a . (a + b) = a
Example 2 : Prove -
a + (b + b') + b = 1
Solution : L. H. S. = a + (b + b') + b
= a + 1 + b (from law 6 b + b' = 1)
= (a + 1) + b
= 1 + b (from theorem 2, a + 1 = 1)
= 1 (from theorem 2, 1 + b = 1)
= R. H. S. (proved).
Example 3 : Prove -
(a + b)' . b' = a' . b'
Solution : L. H. S. = (a + b)' . b'
= a' . b' . b' (from De Morgan (Theorem 5) theorem (a+b)' = a' . b')
= a' . (b' . b' )
= a' . b' (from theorem 1, a . a = a, so b' . b' = b')
= R. H. S. (proved).
52
Example 4 : Prove - Boolean Algebra
(a + a) . a. a + 1 . b = a + b And Logic Gates

Solution : L. H. S. = (a + a) . a . a + 1 . b
= a . a . a + 1 . b (theorem 1, a + a = a) NOTES
= a . (a . a) + 1 . b
= a . a + 1 . b (from theorem 1, a . a = a)
= a + 1.b (from theorem 1)
= a + b (from postulate 5, 1 . b = b)
= R. H. S. (proved)
Example : 5 Prove -
(a + b . c)' = a' . (b' + c')
Solution : L. H. S. = (a + b .c)'
= a' . (b . c) (from De-Morgan's theorem)
= a' . (b' + c') (from De Morgan theorem)
= R. H. S. (proved)
Example 6 : Prove -
a . (b.c) .c' = 0
Solution : L. H. S. = a . (b . c) . c'
= a . b . c . c' (from postulate 4 a. (b.c)=a.b.c)
= a . b . (c . c')
= a . b . 0 (from postulate 6 c . c' = 0)
= a . (b . 0)
= a . 0 (from theorem 2, b . 0 = 0)
= 0 (from theorem 2, a . 0 = 0)
= R. H. S. (proved)
PROVING THE EQUATIONS OF BOOLEAN EXPRESSIONS BY TRUTH TABLE
The truth tables are used to certify the simplified form of complex boolean expressions.
In truth tables, columns are prepared for the LHS and RHS of the equation which is used
to express the simplified form of complex boolean expressions. After this, the equality of
LHS & RHS is checked for all the possible values (1 and 0) of boolean quantities If each
value is equal then, the equation is proved.
Example 7 : Prove the following equation with the help of a truth table :
(a + b)1 = a' . b'
Solution : For this equation we keep all possible values of two boolean variable
quantities and write the columns of the expressions of equations in the
following way-
L.H.S. R.H.S
a b a+b (a + b)' a' b' a'.b'
1 0 1 0 0 1 0
0 1 1 0 1 0 0
1 1 1 0 0 0 0
0 0 0 1 1 1 1 53
Fundamentals of In column 4 and column 7 the elements of each row are same,
Computers & therefore, (a + b)' = a' . b' is proved
Information Technology
L.H.S. R.H.S

NOTES a b c b.c (a+b.c) (a+b.c)' a' b' c' b'+c' a'.(b'+c)'

0 0 0 0 0 1 1 1 1 1 1
0 0 1 0 0 1 1 1 0 1 1
0 1 0 0 0 1 1 0 1 1 1
0 1 1 1 1 0 1 0 0 0 0
1 0 0 0 1 0 0 1 1 1 0
1 0 1 0 1 0 0 1 0 1 0
1 1 0 0 1 0 0 0 1 1 0
1 1 1 1 1 0 0 0 0 0 0

Example 8 : Prove the following equation with the help of truth table :
(a + b.c)' = a' . (b' + c')
Solution : Here, there are equal elements in the rows of column 6 and column 11,
therefore, (a + b .c)' = a' . (b' + c') is proved
Example 9 : Solve the following equation with the help of truth table -
(a')' + (b')' = a + b
Solution :
L.H.S. R.H.S
a b a' b' (a')' (b')' (a') + (b')' a+b
0 0 1 1 0 0 0 0
0 1 1 0 0 1 1 1
1 0 0 1 1 0 1 1
1 1 0 0 1 1 1 1

In the above truth table, the elements of column 7 and column 8 are
same. Therefore (a')' + (b') = a+b is proved.
PRINCIPLE OF DUALITY
Boolean postulates menage the operations of the operators AND and OR, 0 and 1. There
is dual recognition of boolean expressions, which is called duality. It can be obtained the
following way :
l Replacing the . sign with +
l Replacing the + sign with .
l Separating all NOT operators.
For example : The boolean expression a + a' = 1 can be turned into dual boolean
expression a . a' = 0 by following the abovesaid 3 steps.
Likewise dual boolean expression a . (a + b) = a can be turned into a + (a . b) = a.

54
The dual theorem table of some theorems has been displayed below : Boolean Algebra
And Logic Gates
Theorem Dual theorem
a+0=a a.1 = a
a + a' = 1 a. a' = 0 NOTES
a+a=a a.a=a
a.1=1 a.0=a
a + a.b = a a.(a+b) = a
(a')' = a (a')' = a
a.(b+c) = a.b + a.c a + (b.c) = (a+b) . (a+c)
a + a'.b = a + b a . (a' + b) = a . b
(a + b)' = a' . b' (a . b)' = a' + b'
Table 3.6

Standard Forms
______________________________________________________________________________________

A boolean expression can be defined by the following conditions -

n Product : In this condition, one or more boolean variables are Logic gate
added by AND operator. For example : a . b . c is a product processes signals
condition. which denote
true or false.
n Sum : In this condition, one or more boolean variables are
added by OR operator. For example : a+b+c is a sum
condition.
n Sum of Products : It is such a boolean expression whose product conditions are
connected/added by OR operator. For example : a'c + bc' is the sum of products.
n Product of Sums : It is such a boolean expression whose sum conditions are co-
ordinated by AND operator, for example : (a+c).(b+c) is a product of sums.

Basic Logic Gates

______________________________________________________________________________________

Let's start this section with the question 'What is a logic gate ?' this question initiates this
section. In digital computers, all the operations are carried out through signals. These
signals are obtained from the standard blocks of the internal circuit of the computers.
These circuits are called logic gates. If we have to define it in one sentence then, the logic
gates are the base of electronic circuits of the computer.
AND Gate
AND Gate has a digital circuit, which has one or more inputs and only one output. In
the AND gate displayed in the picture below, a and b are inputs and c is output. In Check Your Progress :
this gate, if the values of inputs a and b we true, the output will be true. The truth
1. Define Boolean Algebra ?
table of this gate will be as table 3.7.
2. What do you mean by truth
a a b c = a.b
table.
c=a.b 0 0 0
3. What is sum of product ?
0 1 0
b 4. What is product of sum ?
1 0 0
1 1 1
Fig. 3.7 : AND Gate
Table 3.7 : AND Truth Table 55
Fundamentals of OR Gate
Computers & OR gate is a digital circuit which has one or more inputs and only one output. In
Information Technology the OR gate displayed in the following picture, a and b are inputs, while c is the
output. In this gate, if the value of input a or input b is true, the value of output
NOTES c is true. The truth table of this gate will be as follows :

a a b c = a+b
c=a+b 0 0 0
0 1 1
b
1 0 1
1 1 1
Fig. 3.8 : OR Gate Table 3.8 : OR Truth Table

NOT Gate
NOT gate is a digital circuit which has one input and only one output. In the NOT
gate displayed in the following picture, a is input while c is the output. In this gate,
the complement a' of input a is obtained as output. Therefore if the value of input
a is true the value of output c will be false. The Truth table of NOT gate will be as
follows :

a c = a'
a c = a' 0 1
1 0
Table 3.9 : Truth table for NOT Gate
Fig. 3.9 : NOT Gate

NAND Gate
NAND gate is the combination
of AND and NOT gate is which a
C = (a . b)1
the output of AND gate is
inverted by NOT gate. NAND
gate is expressed through figure b
3.10, while its symbolic
sepresentation is expressed by Fig. 3.10 : The circuit of NAND Gate
figure 3.11.

a
C

Fig. 3.11 : The symbol of NAND Gate

The truth table of NAND gate will be as follows :

a b c = (a.b)'
0 0 1
0 1 1
1 0 1
1 1 0
56
Table 3.10 : The truth table of NAND Gate
NOR Gate Boolean Algebra
It is a set of OR gate and NOT And Logic Gates
a
gate in which the output of OR C = (a + b)1
Gate is inverted by NOT gate.
The circuit of NOR Gate is NOTES
expressed by figure 3.12 while b
its symbolic representation is
Fig. 3.12 : The circuit of NOR GAte
expressed in figure 3.13 :

a
C

Fig. 3.13 : The symbol of NOR Gate

The truth table of NOR Gate is as ofllows :

a b c = (a+b)'
0 0 1
0 1 0
1 0 0
1 1 0
Table 3.11 : The truth table of NOR Gate

XOR Gate (Exclusive OR Gate)

It is a combination of AND, NOR and OR gate in which both outputs obtained from
AND gate and NOR gate are inputs in OR gate and from this OR gate, the output
of the entire combination is obtained.
If any one input is True in this gate then the output is true, but if both the inputs
are true, the output is false.
The circuit of XOR Gate is expressed in figure 3.12, while its symbolic representation
has been expressed in figure 3.13.

To express operations on boolean variables of XOR gate the ⊕ sign is used. The truth
table of XOR gate is as follows :

b
C=(a + b)

Fig. 3.12 : XOR circuit

a
c
b
57
Fig. 3.13 : XOR Gate Symbol
Fundamentals of a b c = a+b
Computers & 0 0 0
Information Technology 0 1 1
1 0 1
NOTES 1 1 0
Table 3.12 : The truth table of XOR Gate

XNOR Gate (Exclusive NOR Gate)

XNOR gate is the inverse of XOR gate. In which there is a combination of a AND
gate and two NOR gates. Output of AND and one NOR one NOR gate are inputs
for the other NOR Gate and from it the output of entire combination is obtained. If
only one input from this gate is true then the output is fales but if both the conditions
of both the inputs are true or false, the output is true. The circuit of XNOR Gate has
been displayed in figure 3.14, while figure 3.15 shows its symbolic representation.

b
C=(a + b)

Output

Fig. 3.14 : The circuit of XNOR Gate

Fig. 3.15 : XNOR Gate symbol

The truth table of XNOR Gate is an follows :

a b c = (a ⊕ b)
0 0 1
0 1 0
1 0 0
1 1 1
Table 3.13 : The truth table of XNOR Gate

Use of Logic Gates in Circuits

______________________________________________________________________________________

We know that circuits are prepared on the basis of boolean algebra and its expressions.
Logic gates are used to create circuit diagrams by applying them in place of boolean
operators (such as- OR, AND, NOT etc.) applied in boolean expressions.

58
Example 10 : There is a boolean expression as follows. Prepare a circuit for it. Boolean Algebra
p = ab' + ab + b And Logic Gates

Solution : It circuit will be as follows :

NOTES
a
b

p=ab' + ab+b
a

b
b

Fig. 5.16 : The circuit prepared as per example 10.

Here if we simplify boolean expressions with postulates and theorems of boolean

algebra, a simpler but equivalent circuit may be created.

ê p = a.b' + a.b + b

ê p = a(b' + b) + b

ê p = a . 1 + b

= a + b

ê p = a + b (is a simplified expression)

Now we can prepare the circuit of the simplified expression a + b as per picture
3.17.

p=a + b

Fig. 3.17 : A circuit based on or simplified expression

Karnaugh Map
______________________________________________________________________________________
Karnaugh Map is
We know that algebric simplification is an art in which expanded and also called Veitch
complex circuits are simplified and shortened. But if the number of diagram
expressions is more, this method may prove erroneous, therefore so
many engineers don' use algebraic simplification method.
Karnaugh Map is a popular way of simplifying boolean expressions. This is a method to
present the truth table in a pictorial way. It was developed by Maurice Karnaugh in Bell 59
Fundamentals of Laboratories. In this method, the truth table is divided into rows and columns in
Computers & sequares and in the squares related to the row number. Every digit of minterm 1 of
Information Technology a truth table is placed in the related square related row1. In the following picture a
karnaugh map for one variable has been displayed. We see in this figure that there
are two squares in it, which have been given numbers 0 and 1 in which 0 stands for
NOTES row 0 of the truth table and 1 refers to the row 1 of truth table. Now, let us consider
the following truth table for variable A and output y. 0 1
A y A

0 1
1 0 = Σ0 Fig. 3.18 : Karnaugh Map for
one variable

The above truth table can be expressed by Σ 0 in AND-OR condition. Here in the truth
table, the row 0 is a Minterm. Now for the row related to 0 a 1 will be placed in the
square 0 of Karnaugh Map which will provide the following map.
0 1
A 1

Thus for the truth table for one variable a karnaugh map is prepared. Karnaugh. Maps for
2, 3 are 4 variables are displayed in figures 3.19, 3.20 & 3.21 respectively. It should be
noted that the number of squares are in no way related to the binary digits in the Map.
If they are converted from complement to uncomplement, the order of deciding the digits
will be 00, 01, 11 and 10.
B BC
A 0 1 A 00 01 11 10
0 0

1 1

Fig. 3.19 : Map of 2 variables Fig. 3.20 : Map of 3 variables

CD
AB 00 01 11 10
00
B
01

11

10

Fig. 3.21 : Map of 4 variables

In this indication of map, '1' indicates that the status of the concerned variable is in the
left corner of the map and it is true, while a '0' means the condition of variable is false.
60
For example, in the first figure the meanings of variables B and C : 00, 01, 11, 10 are
B'C', B'C, BC and BC' respectively.
Summary Boolean Algebra
______________________________________________________________________________________
And Logic Gates
l Boolean algebra is the algebraic structure of abstract algebra which discusses
essential properties of set operations and logic operations.
l Boolean Algebra, a branch of Algebra was invented by a British Mathematician
NOTES
George Boole (1815-1864).
l Boolean Algebra is used to simplify Electonic Digital Circuits.
l According to Boolean Algebra, there are two possibilities for a statement.
l These complex circuits are expressed in the statements of boolean algebra and are
simplified using the postulates of Boolean Algebra.
l When two statements are combined to form a new statement, this new statement
is called compound statement.
l A table which expresses all the possibilities of a switching circuit in the form of
binary valued quantity 1 and 0 is called Truth Table.
l In Boolean Algebra to simplify the complex expression there are some accepted
facts and postulates which are the foundation of boolean algebra.
l De-Morgan was a friend to George Boole who researched on Logical Mathematics.
l According to theorem 5 of De-Morgan the value of the complement of the sum
of two boolean quantities is equal to the sum of semparate complements of these
quantities.
l According to De-Morgan's theorem 6 the value of the complement of the products
of two quantities is equal to the sum of the complements of these quantities
taken separately.
l To certify simplified forms of complex boolean expressions, truth tables are used.
l Boolean postulates operator AND and OR plan the operations of 0 and 1. In it
there is dual identity of boolean expressions which is called duality.
l AND gate is a digital circuit (dual state) which was more than one inputs and only one
output.
l OR gate is a digital circuit which has more than one inputs and only one output.
l NOT gate is a digital circuit which has one input and one output.
l NAND gate is a combination of AND and NOT gate, in which the output of AND
gate is inverted by NOT gate.
l NOR Gate is a set of OR gate and NOT gate in which the output of OR gate
is inverted by NOT gate.
l XOR gate is a combination of AND, NOR and OR gates in which both the outputs
obtained from AND gate and NOR gate are input in the OR gate and this OR
gate gives the output of the entire combination. Any one input being true in this
gate, the output is true, but if both the inputs are true, the output is false.
l XNOR gate is the inverse of XOR gate. It is a combination of one AND gate and
two NOR gates. The outputs obtained from its AND gate and NOR gate are input
in another NOR gate and it gives the output of the entire combination. Any one
input being true in this gate, the output is false but if both the conditions of both
inputs are true, the output is true. Check Your Progress :
l Karnaugh Map is a popular method of simplifying boolean expressions. This is
5. What do you know about or
mode of presenting the truth table in the form of a picture. This technique was
Gate ?
developed by a telecommunication engineer Moris Karnaugh in the Bell laboratories.
Answer of the Check your progress : 6. Write the truth table for
XNoR Gate.
1. Introduction–Boolean Algebra is the algebraic structure of Abstract Algebra in which 7. What is KMap ?
required properties of set operations and logic operations. Expecially it contains intersec-
tion, union and complement set operations and AND,OR and NOT logic operations.
Logic gates act on signals which express true or false. Logic gates help in building a circuit.
2. Truth table is a kind of mathematical table which is used to determine whether an 61
expression is true or false in the logic.
Fundamentals of 3. Sum of Products–It is such a boolean expression whose product conditions are con-
Computers & nected/added by OR operator. For example : a'c + bc' is the sum of products.
Information Technology 4. Product of Sums–It is such a boolean expression whose sum conditions are co-ordinated
by AND operator, for example : (a+c).(b+c) is a product of sums.
NOTES 5. OR gate is a digital circuit which has one or more inputs and only one output. In the
OR gate displayed in the following picture, a and b are inputs, while c is the output.
In this gate, if the value of input a or input b is true, the value of output c is true.
6. The truth table of XNOR Gate is an follows :
a b c = (a ¿ b)
0 0 1
0 1 0
1 0 0
1 1 1
7. Karnaugh Map is a popular method of simplifying boolean expressions. This is mode of
presenting the truth table in the form of a picture. This technique was developed by a
telecommunication engineer Moris Karnaugh in the Bell laboratories.

Exercise
______________________________________________________________________________________

1. Boolean Algebra was named after which mathematician ?

2. Explain Boolean Algebra in your own words ?
3. What are the main principles of Boolean Algebra ?
4. Define switch and switch circuit.
5. What is truth table ?
6. What do you mean by compound statement ?
7. What are the postulates of Huntington ?
8. Explain the postulates of Boolean Algebra.
9. Explain various theorems of Boolean Algebra.
10. Explain the theorems of De-Morgan.
11. Prove the following :
(i) a + (b + b') + b = 1
(ii) (a +b)'-b' = a'.b'
(iii) (a+a).a.a + 1.b = a+5
(iv) a.(b.c).c' = 0
(v) (a+b.c)' = a'.(b' + c')
12. Prove (a+b)' = a'+b' with the help of a truth table.
13. What is the principle of duality ? Explain.
14. What do you mean by Logic Gates ?
15. Explain the following Gates :
(i) AND
(ii) OR
(iii) NAND
(iv) NOR
(v) XOR
(vi) XNOR
16. Prepare the electronic circuit of P = ab' + ab + b.
62
17. Explain the Karnaugh's Map.