CHAPTER 1

BOOLEAN ALGEBRA AND LOGIC GATES

SYLLABUS

Review of Number Systems – Arithmetic Operations – Binary Codes – Boolean Algebra and
Theorems – Boolean Functions – Simplification of Boolean Functions using Karnaugh Map and
Tabulation Methods – Logic Gates – NAND and NOR Implementations.

Digital electronics have made possible in many systems to minimize the analogous in
the electronic system. Everybody knows and deals with the electronic and electricals with
analog form, where a quantity is described by the amount of voltage, or current etc.,
expressed in a variable. However to minimize the analog function, a large proportion of
electronic equipment, including computers, uses digital electronic and also where the
quantities are described by two states; ON and OFF. These two states can also be
represented by true or false as 1 and 0 respectively. Since many quantities cannot be
represented by two states, more than one binary digit can be used to represent a number.

DIGITAL ELECTRONICS

Digital electronics deals with 0‟s and 1‟s in an electronic device. Digital stands for
„digit‟. Basically it has two states: 1 referred as true and 0 referred as false. Those states
can be implemented with a two valued logic using logic gates.
Digital electronics may also be referred as electronic devices (or) circuits representing
signal by discrete bands of analog levels, rather than by a continuous range.
The general-purpose digital computer is the best-known example of a digital system.
Other examples include telephone switching exchanges, digital voltmeters, frequency
counter and calculators, etc.
General characteristic of a digital system is its manipulation of discrete elements of
information. Such discrete elements may be electric impulses, the decimal digits, the letters
of an alphabet, arithmetic operations, punctuation marks, or any other set of meaningful
symbols.
 1.2 Digital Principles and System Design

Before going to discuss about the techniques used to minimize the logics and about
logic gates, let us see about the number systems.

1.1. NUMBER SYSTEMS

Number systems play an important role in digital computer. A number system is a
mathematical object used to count, label and measure the task performed by the logic
function. Basically we have four ways of numbering a system. They are,
(i) Decimal
(ii) Binary
(iii) Octal
(iv) Hexadecimal
NUMBER BASE CONVERSION
(i) Decimal Number System
The number system which utilizes ten distinct digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9 is
known as decimal number system. The decimal number system has a base, or radix of 10.
Each of the ten decimal digits, 0 through 9, has a place value or weight depending on its
position. The weights are units, tens, hundreds, thousands and so on.
Example: (2652.38)10
These each digits has a respective multiplier of
i.e.,

(ii) Binary Number System

A number system that uses only two digits 0 and 1 is called a binary number system. The
binary system is also called a base two system. The symbol 0 and 1 are known as b its.
The weight or place value of each position can be expressed in terms of power of 2 and
0 1 2
as 2 , 2 , 2 ,  etc.
Example: (11010.011)2
Boolean Algebra and Logic Gates 1.3

(iii) Octal Number System

The octal number system was used extensively by early microcomputer. Sets of 3-bit
binary numbers can be represented by octal numbers and this can be conveniently be used
for entering data in the computer.

A number system that uses eight digits 0, 1, 2, 3, 4, 5, 6 and 7 is called an octal number
system. It has a base of eight.

Example: (765.42)8
These each digits has a respective multiplier of i.e.,

(iv) Hexadecimal Number System

Hexadecimal numbers are used extensively in microprocessor. Most microcomputers

have their memories organised into sets of bytes, each consisting of eight binary digits.

The hexadecimal number system has a base of 16. Thus, it has 16 distinct digit
symbols. It uses the digit 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 plus the A, B, C, D, E and F as 16 digit
symbols.

Example: (A8C.28)16
These each digits has a respective multipliers of
1.4 Digital Principles and System Design

SOME EXAMPLES FOR NUMBER BASE CONVERSION

Example 1.1 Convert the following decimal numbers to Binary, Octal and
Hexadecimal. (i) (455)10 (ii) (256.22)10

Solution:

(a) Decimal to Binary

(i) (455)10 (ii) (256.22)10
The conversion of decimal to any number is Similarly,
by dividing the decimal number with the
respective number system.
The binary has base of 2 so,

If the decimal has a fractional value then

the fractional has to be multiplied with 2
and take the integer as a binary value i.e.,

Hence for (0.22)10 = (0.0011)2

Therefore the answer for
(256.22)10 = (100000000.0011)2
Boolean Algebra and Logic Gates 1.5

(b) Decimal to Octal

(i) (455) (ii) (256.22)10
10
The base of octal is 8, so Similarly,
(256)10 = (400)8

Therefore (455)10 = (707)8 For fractional values

Integer
0.22  8 = 1.76 1
0.76  8 = 6.08 6
0.08  8 = 0.64 0
0.64  8 = 5.12 5
Hence for (0.22)10 = (0.1605)8
Therefore the answer for
(256.22)10 = (400.1605)8
(c) Decimal to Hexadecimal
(i) (455) (ii) (256.22)10
10
The base of hexadecimal is 16, so Similarly,
For (256) = (100)
10 16

Therefore, (455)10 = (1C7)16 For fractional values

Integer
0.22  16 = 3.52 3
0.52  16 = 8.32 8
0.32  16 = 5.12 5
0.12  16 = 1.92 1
For (0.22010 = (0.3851)16
Therefore the answer for
(256.22)10 = (100.3851)16
1.6 Digital Principles and System Design

Example 1.2 Convert the following binary number to decimal, octal and
hexadecimal. (i) (11101)2 ; (ii) (100010.011)2
 Solution:

(a) Binary to Decimal

(i) (11101)2 (ii) (100010.011)2
First take the value (100010) alone.

Therefore (11101)2 = (29)10 For (100010)2 = (34)10

For fractional value (0.011)

Therefore the answer for

(100010.011)2 = (34.375)10
(b) Binary to Octal
(i) (11101) (ii) (100010.011)2
2
The octal number is a set of 3-bit binary Similarly
number. Hence, the above binary number (100010) = (100 010)
is split into 3-bits from right side. For first 3-bit, is 100
11101  011 101

(100)2 = (4)8
Boolean Algebra and Logic Gates 1.7
For first 3-bit is .011 For second 3-bit, is 010

(011)2 = (3)8 (010)2 = (2)8

For second 3-bit is, 101 For fractional value, split the 3-bits from
left side
(101)2  (5)5

Hence (011101)2 = (35)8 (.011)2 = (.3)8

i.e., (011 101)2 Therefore
( 3 5)8 (100010.011)2 = (42.3)8
(c) Binary to Hexadecimal
(i) (11101) (ii) (100010.011)2
2
The hexadecimal is a set of 4-bit binary Similarly.
number. Hence split the binary number 100010 = 0010 0010
into 4-bit from right side. The first and second 4-bit are same.
11101 = 0001 1101
For first 4-bit, is 0001
(0010)2 = (2)16

(0001)2 = (1)16 Hence for (0010 0010)2

(2 2)
16
 1.8 Digital Principles and System Design
For second 4-bit, is 1101 For fractional split the 4-bit from left side
.011 = .0110

(1101)2 = (13)16 = (D)16

Therefore the answer for (.0110)2 = (.6)16
(11101)2 = (1D)16 Therefore the answer for
i.e., (0001 1101)2 (100010.011)2 = (22.6)16
(1 D)16 i.e., (0010 0010 . 0110)2
(2 2 . 6)16

Example 1.3 Convert the following octal number to decimal, binary and
hexadecimal. (i) (35) ; (ii) (42.3)
8 8
 Solution:
(a) Octal to Decimal
(i) (35)8 (ii) (42.3)8
Similarly
Therefore (35)8 = (29)10
(42)8 = (34)10
For fractional value (0.11)

Therefore the answer for

(42.3)8 = (34.375)10
Boolean Algebra and Logic Gates 1.9

(b) Octal to Binary

(i) (35) (ii) (42.3)8
8
The octal number is a set of 3-bit binary Similarly
number. Therefore each digit in an octal
consists of 3-bits of binary values.

4 = 100 2 = 010
Hence (42)8 = (100010)2
3 = 011 5 = 101 For fractional value .3
Therefore the answer for
(35)8 = (011101)2
i.e., (3 5) 3 = 011
011 101
Therefore the answer for

(42.3)8 = (100010.011)2

(c) Octal to hexadecimal

(i) (35) (ii) (42.3)8
8
There is no direct convert between octal to Similarly
hexadecimal and hexadecimal to octal. For (42)8 = (100010)2
So, convert the octal to binary andthen Then 100010 = 0010 0010
2 2
that binary to hexadecimal.
For fractional value
We know that
(.3) = (.011)
8
For (35)8 = (11101)2
Then (0.011) = 0.0110
Then 11101 = 0001 1101
.6
1 13(D)
Therefore the answer is
Therefore the answer for
(42.3) = (22.6)
8 16
(35) = (1D)
8 16
1.10 Digital Principles and System Design

Example 1.4 Convert the following hexadecimal number to decimal, binary and
octal. (i) (1D) , (ii) (22.6)
16, 16

Solution:
(a) Hexadecimal to Decimal
(i) (1D) (ii) (22.6)16
16
Similarly
Therefore the answer for (22)16 = (34)10

(1D)16 = (29)10
For fractional number
(.6)16 = (0.375)10

Therefore the answer for

(22.3)16 = (34.375)10
(b) Hexadecimal to Binary
(i) (1D) (ii) (22.6)16
16
The hexadecimal is a set of 4-bit binary Similarly
number. Therefore each digit in a 22.6 = 2 2. 6
hexadecimal has 4-bits of binary number.   
1D = 1 13 0010 0010 0110
Therefore the answer for
0001 1101
Therefore the answer for (22.6)16 = (00100010.0110)2

(1D)16 = (00011101)2
(c) Hexadecimal to Octal
(i) (1D) (ii) (22.6)16
16
There is no direct conversion between Similarly
hexadecimal to octal. So convert the We know that
hexadecimal to binary and then that binary (22.6)16 = (00100010.0110)2
to octal.
Boolean Algebra and Logic Gates 1.11
We know that also
(1D)16 = (00011101)2 000100010.0110 = 100 010 . 011
also   
4 2 . 3
00011101 = 000 011 101 Therefore the answer for
  
0 3 5 (22.6) = (42.3)
16 8
Therefore the answer for
(1D)16 = (35)8

The following table gives the number with different bases.

Table 1.1. Number with different bases

Decimal Binary Octal Hexadecimal

(Base 10) (Base 2) (Base 8) (Base 16)
00 0000 00 00
01 0001 01 01
02 0010 02 02
03 0011 03 03
04 0100 04 04
05 0101 05 05
06 0110 06 06
07 0111 07 07
08 1000 10 08
09 1001 11 09
10 1010 12 A
11 1011 13 B
12 1100 14 C
13 1101 15 D
14 1110 16 E
15 1111 17 F
16 10000 20 10
17 10001 21 11
 1.12 Digital Principles and System Design

1.2. ARITHMETIC OPERATIONS

Arithmetic operations performs addition, subtraction, multiplication and division of two
or more numbers. Generally in computers and general purpose processors, the arithmetic
operations are done by using binary numbers not by using decimal numbers, so it is
necessary to know binary addition, binary subtraction, binary multiplication and binary
division.
In computers, the arithmetic operations are performed by a arithmetic and logical
operation unit in a CPU. This unit is made of electronic circuit which is capable of doin g
addition of two or more binary digits at a time and the binary addition is sufficient to do
subtraction. Thus a single circuit of a binary adder with suitable shift register can perform
all the arithmetical operations.

1.2.1. BINARY ADDITION

Addition of two binary numbers form four cases as follows:

Rules for Binary Addition

Augend + Addend Carry Sum Result
(A) (B) (C) (S)
0 + 0 0 0 0
0 + 1 0 1 1
1 + 0 0 1 1
1 + 1 1 0 10

Note For 1 + 1 = 10 (Here 0 is the result and 1 is the carry into next position).
 1 + 1 = 10
 1 + 1 + 1 = 11

 1 + 1 + 1 + 1 = 100 (Here 0 is the result and 10 is the carry into next position)

 1 + 1 + 1 + 1 + 1 = 101

Following examples illustrate the binary addition of two numbers.

Example 1.5 Add the binary numbers.
(i) 1101 and 0011 (ii) 1100 and 1111
(iii) 101.01 and 010.11 (iv) 1110.011 and 0101.010
Boolean Algebra and Logic Gates 1.13

Solution:
(i) 1101 and 0011 (ii) 1100 and 1111
Binary Decimal Binary Decimal
Carry  1 1 1 Carry  1
1 1 0 1 13 1 1 00 12
+ 0 011 03 1 1 11 15
   
Sum =1 0 0 0 0 16 1 1 01 1 27
   
(iii) 101.01 and 010.11 (iv) 1110.011 and 0101.010

Binary Decimal Binary Decimal

Carry  1 1 1 1 Carry  1 1
1 01. 0 1 5.25 1 1 1 0.0 1 1 14.375
0 10. 1 1 2.75 0 1 0 1.0 1 0 5.25
   
1 0 00. 0 0 8.00 1 0 01 1.1 01 19.625
   

1.2.2. BINARY SUBTRACTION

Subtraction is the inverse operation of addition. To subtract two numbers, it is
necessary to establish a procedure for subtracting a larger from a small digit.

Rules for Binary Subtraction

Minmend – Subtrahend Difference Borrow
0 0 0 0
0 1 1 1
1 0 1 0
1 1 0 1

Example 1.6 Subtract the binary numbers.

(i) 101 from 111 (ii) 1100 and 1101
(iii) 010.01 from 110.10 (iv) 0100.11 from 1000.11
 1.14 Digital Principles and System Design


Solution:
(i) 101 and 111 (ii) 1100 and 1101
Binary Decimal Binary Decimal
111 7 1101 13
–101 –5 –1100 –12
   
010 2 0001 1
   
(iii) 010.01 from 110.10 (iv) 0100.11 from 1000.11
Binary Decimal Binary Decimal
110.10 6.50 1000.11 8.75
010.01 2.25 0100.11 4.75
   
100.01 4.25 0100.00 4.00
   

1.2.3. BINARY MULTIPLICATION

The multiplication of binary numbers is done in the same manner as the multiplication
of decimal numbers. The basic rules for multiplying binary digits are:
1) 00 =0
2) 01 =0
3) 10 =0
4) 11 =1
Example 1.7 Multiply the binary numbers: 10110 and 1100

Solution:
(i) 10110 and 1100

Solution:
10110
 1100

00000
00000
10110
10110

100001000

Boolean Algebra and Logic Gates 1.15

1.2.4. BINARY DIVISION

The process for dividing one binary number (the dividend) by another (the divisor) is
the same as that which is followed for decimal numbers.
Example 1.8 Divide the binary number: 11001 and 101

Solution:
101
101 11001
101
0101
101
000

1.3. COMPLEMENTS

Complements are used in digital computers for simplifying the subtraction operation
and for logical manipulation. There are two types of complements.
(i) r ‟s complement
(ii) (r – 1)‟s complement
where r is the base of the respective number system.
For binary number (Base = r = 2), we have the following complements.
1. 2‟s complement (r ‟s complement)
2. 1‟s complement ((r – 1)‟s complement)
For decimal numbers (Base = r = 10), we have the following complements.
1. 10‟s complement (r ‟s complement)
2. 9‟s complement ((r – 1)‟s complement)

1.3.1. 1’s COMPLEMENT

The 1‟s complement of given number can be obtained by changing 0 into 1 and 1 into
0.
Example 1.9 Find the 1’s complement of the Binary number.

Solution:
Binary number 1’s complement
0101 1010
00011 11100
1111 1110 0000 0001
 1.16 Digital Principles and System Design

1.3.2. 1’s COMPLEMENT ARITHMETIC

Subtraction of two binary numbers using 1‟s complement can be performed by the
following steps.
(a) To subtract a smaller number from a larger number.
(i) Take 1‟s complement to the smaller number.
(ii) Add the 1‟s complement to the larger number.
(iii) Remove the carry and add carry to the result. This is called end-around carry.

Example 1.10 Subtract the following binary number using 1’s complement method.
(i) 1100 from 1111 (ii) 1010 from 1110

Solution:
(i) 1100 from 1111
Here the smaller number is 1100.
Step 1: Take 1‟s complement to the smaller number.
Binary 1’s complement
1100 0011

Step 2: Add the 1‟s complement to the larger number.

1111
0011

Carry bit  0010

Step 3: Remove the carry and add carry to the result.

Verification:
Binary Decimal
1111  15
1100  – 12
 
 30011
 
Boolean Algebra and Logic Gates 1.17

(ii) 1010 from 1110

Smaller value is 1010.
1‟s complement of 1010 is 0101.

Verification:
Binary Decimal
1110  14
1010  – 10
 
0100  4
 
(b) To subtract a larger number from a smaller number.
(i) Take the 1‟s complement for the larger number.
(ii) Add the 1‟s complement to the smaller number.
(iii) The answer has a opposite sign and is the 1‟s complement of the result. There is
no carry.

Example 1.11 Subtract (i) 1111 from 1100 and (ii) 1110 from 1010

Solution:
(i) 1111 from 1100
Here larger number is 1111  0000 is 1‟s complement form.
1’s complement method Direct subtraction
0000 1100
+ 1100 – 1111
 
+ 1100 – 0011
 

Take 1‟s complement for
1100  – 0011 is the result.
 1.18 Digital Principles and System Design

(ii) 1110 from 1010

1’s complement method Direct subtraction
0001 1010
+ 1010 – 1110
 
1011 – 0100
 

Take 1‟s complement for 1011  – 0100 is the result.

1.3.3. 2’s COMPLEMENT

The 2‟s complement form of a binary number is formed by taking the 1‟s complement
of the number and adding 1 to the least significant bit (LSB) position.
2‟s complement = 1‟s complement + 1

Example 1.12 Take 2’s complement for a binary number 1101 and 1010.

Solution:
(i) 1101
Binary number 1101
1‟s complement 0010
+1

2‟s complement 0011

(ii) 1010
Binary number 1010
1‟s complement 0101
+1

2‟s complement 0110


1.3.4. 2’s COMPLEMENT ARITHMETIC

Arithmetic operation using 2‟s complement is illustrated by the following example.

Example 1.13 Add the following decimal number using binary addition.
(i) 12 + 4 (ii) 12 + (– 4) (iii) (– 12) + 4 (iv) (– 12) + (– 4)
Boolean Algebra and Logic Gates 1.19

Solution:
(i) 12 + 4
Decimal Binary
1
12 1100
4 0100
 
16 10000
 

(ii) 12 + (– 4)
For a signed decimal addition using binary numbers. Follow the following rules.
(i) Take the two number in 8-bit value.
(ii) Take 2‟s complement for a negative signed number.
(iii) Add the positive number and 2‟s complement number.
(iv) Addition will be the result. If the result will be a negative s igned number, then the
result is 2‟s complement of the number.

12  0000 1100
4  0000 0100

For (– 4) take 2‟s complement to the binary value of 4.

0000 0100
1‟s complement  1111 1011
+ 1

2‟s complement  1111 1100 (– 4)

Add 12 + (– 4)

12 00001100
–4 11111100
 
+8 00001000
 
1.20 Digital Principles and System Design
 (iii) (– 12) + (4)
Take 2‟s complement to the 12.
12  00001100
1‟s complement  11110011
+ 1
 
2‟s complement 11110100

– 12 1 1 1 1 0 1 0 0
4 00000100
 
–8 11111000
 
Since the addition was result in negative number, so the produced result will be in 2‟s
complement of 8.
To verify the result, take 2‟s complement of 8.
8 00001000
1‟s complement  1 1 1 1 0 1 1 1
1

2‟s complement  1 1 1 1 1 0 0 0 = (– 8)

The 2‟s complement of 8 and resultant values of ( – 12) + 4 is equal. Hence the
addition was found correct.
(iv) (– 12) + (– 4)
Here both the numbers are negative numbers. Hence take 2‟s complement of 12 and 4.
12  00001100 4  00000100
11110011 11111011
1 1
 
– 12 = 11110100 – 4 = 11111100
 
– 12 11110100
– 4 11111100
 
– 16 11110000
 
Boolean Algebra and Logic Gates 1.21

Since the addition results in negative number, the produced result will be in 2‟s
complement of 16.
To verify the result, take 2‟s complement of 16.
16  00010000
1‟s complement  11101111
1
 
2‟s complement 11110000 = (–16)

The 2‟s complement of 16 and resultant value of (– 12) + (– 4) is equal. Hence the
addition was found correct.

1.3.5. 9’s COMPLEMENTS

The 9‟s complement of a decimal number is found by subtracting each digit in the
number from 9. The 9‟s complement of decimal digit 0 to 9 is shown in the below table.
Decimal digit 9’s complement
0 9
1 8
2 7
3 6
4 5
5 4
6 3
7 2
8 1
9 0

Example 1.14 Find the 9’s complement of the following decimal number.
(i) 8 (ii) 27 (iii) 368 (iv) 4516

Solution: To find 9‟s complement, subtract each decimal digit from the value 9.
(i) 8 (ii) 27
Here only one digit is there. Here two digits are there, so
9 99
–8 – 27
   9‟s complement of 27
1  9‟s complement of 8 72
 
 1.22 Digital Principles and System Design

(iii) 368 (iv) 4516

999 9999
– 368 – 4516
 
631 9‟s complement of 368 5483  9‟s complement of 4516
 

1.3.6. 9’s COMPLEMENT ARITHMETIC

The 9‟s complement can be used to perform the arithmetic operation of the decimal
numbers.

Example 1.15 Perform subtraction of the given decimal number using 9’s
complement.
(i) 5 from 9 (ii) 16 from 25 (iii) 18 from 11

Solution:
(i) 5 from 9

(ii) 16 from 25
Boolean Algebra and Logic Gates 1.23
(iii) 18 from 11
Direct subtraction
99 11
18 – 18
 
81  9‟s complement of 18 – 07
 
11
81

92

Negative sign indicated in 9‟s complement.
99
92

– 07


1.3.7. 10’s COMPLEMENT

The 10‟s complement of a decimal number is obtained by 9‟s complement plus

1. 10‟s complement = 9‟s complement + 1

Example 1.16 Find the 10’s complement of the following decimal number.
(i) 6; (ii) 64; (iii) 562; (iv) 4621

Solution:

(i) 6 (ii) 64
9 99
–6 – 64
 
3 35
+1 +1
 
4  10‟s complement of 6 36  10‟s complement of 64
 
 1.24 Digital Principles and System Design

(ii)562 (iv)4621

999 9999
– 562 4621
 
437 5378
+1 +1
 
438  10‟s complement of 562 5379 10‟s complement of 4621
 

1.3.8. 10’s COMPLEMENT ARITHMETIC

10‟s complement can be used to perform arithmetic operation of the decimal numbers.

Example 1.17 Perform the subtraction of the given decimal number using 10’s
complement.
(i) 6 from 9; (ii) 16 from 25; (iii) 18 from 11

Solution:
(i) 6 from 9
10‟s complement of 6 is 4 Direct subtraction
9 9
+4 6
 
Carry 3 3
 
Discard carry, hence result is 03
(ii) 16 from 25

10‟s complement of 16 is 84 Direct subtraction

25 25
+ 84 16
 
Carry 09 09
 
Discard carry, hence result is 09
 Boolean Algebra and Logic Gates 1.25
(iii) 18 from 11
10‟s complement of 18 is 82 Direct subtraction
11 11
+ 82 – 18
 
93 – 07
 
Result is negative signed number.
Take 10‟s complement of 93.
Negative sign indicate 10‟s complement
99
93

06
+1

– 07

Hence result is – 07.

1.4. BOOLEAN ALGEBRA

1.4.1. POSTULATES OF BOOLEAN ALGEBRA

Boolean algebra may be defined with a set of elements, a set of operations, and a
number of unproved postulates.
Boolean algebra may also be referred as an algebraic structure defined by a set of
element. A set of elements is a collection of objects which is two or more binary numbers,
together with two binary operator „+‟ and „.‟ (dot).
The set of elements, together with two binary operators „+‟ and „.‟ provides the
following postulates.
 The structure is closed with respect to the operator „+‟. i.e., when two binary
elements are operated by a operator „+‟, then the result will be a unique binary
element.
 The structure is closed with respect to the operator „.‟. i.e., when two binary
elements are operated by a operator „.‟, then the result will be a unique binary
element.
 1.26 Digital Principles and System Design

 The element „0‟ is identity element with respect to „+‟.

i.e., A+0 = 0+A= A
 The element „1‟ is identity element with respect to
„.‟. i.e., A . 1 = 1 . A = A
 The structure is,
(i) Commutative with respect to
„+‟ i.e., A + B = B + A
(ii) Commutative with respect to
„.‟ i.e., A  B = B  A
(iii) The operator „.‟ is distributive over „+‟
i.e., A  (B + C) = (A  B) + (A  C)
(iv) The operator „+‟ is distributive over „.‟
i.e., A + (B  C) = (A + B)  (A + C)
–

For every binary element, there exists complement element. For example A is the
– –
complement of A, such that (i) A + A = 1 and (ii) A  A = 0.
 There exists at least two elements A, B are belongs to a set of binary element,
such that A  B.

1.4.2. LAWS OF BOOLEAN ALGEBRA

Similar to an ordinary algebra, the Boolean algebra has the most common law used
to formulate various algebraic structures. There are three basic laws of Boolean algebra.
(i) Commutative Laws
(ii) Associative Laws
(iii) Distributive Law

(i) Commutative Laws

(a) Law 1: A  B = B  A
(b) Law 2: A + B = B + A

(a) Law 1: A  B = B  A
A binary operator „.‟ on a set „x ‟ is said to be commutative whenever
A  B = B  A for all A, B  x
„.‟ represents the multiplication (AND) operation.
 Boolean Algebra and Logic Gates 1.27
i.e.,

A B A B A B BA
0 0 0 0 0 0
=
0 1 0 0 1 0
1 0 0 1 0 0
1 1 1 1 1 1

(b) Law 2: A + B = B + A
A binary operator „+‟ on a set x is said to be commutative whenever,
A + B = B + A for all A, B  x
“+” represent „OR‟ operation
i.e.,
A B A+B A B B+A
0 0 0 0 0 0
=
0 1 1 0 1 1
1 0 1 1 0 1
1 1 1 1 1 1

(ii) Associative Laws

(a) Law 1: A + (B + C) = (A + B) + C
(b) Law 2: (AB) C = A (BC)
(a) Law 1: A + (B + C) = (A + B) + C:
A binary operator „+‟ on a set x is said to be associative whenever,
A + (B + C) = (A + B) + C for all A, B  x
i.e.,
A B C B+C A + (B + C) A B C A+B (A + B) + C
0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 0 0 1 0 1
0 1 0 1 1 0 1 0 1 1
0 1 1 1 1 0 1 1 1 1
=
1 0 0 0 1 1 0 0 1 1
1 0 1 1 1 1 0 1 1 1
1 1 0 1 1 1 1 0 1 1
1 1 1 1 1 1 1 1 1 1
 1.28 Digital Principles and System Design

(b) Law 2: (A  B)  C = A  (B  C)
A binary operator „.‟ on a set „x ‟ is said to be associative whenever
(A  B)  C = A  (B  C) for all A, B  x
i.e.,
A B C AB (A  B)  C A B C BC A  (B  C)
0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 1 0 0
0 1 0 0 0 0 1 0 0 0
=
0 1 1 0 0 0 1 1 1 0
1 0 0 0 0 1 0 0 0 0
1 0 1 0 0 1 0 1 0 0
1 1 0 1 0 1 1 0 0 0
1 1 1 1 1 1 1 1 1 1

(iii) Distributive Law

Law: A  (B + C) = AB + AC
If „+‟ and „‟ are the two binary operators on a set x , then „+‟ is said to be
distributive over „.‟ whenever
A  (B + C) = A  B + A 
C
i.e.,

A B C B+C A  (B + C) A B C AB AC AB + AC

0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 1 0 0 0
0 1 0 1 0 0 1 0 0 0 0
=
0 1 1 1 0 0 1 1 0 0 0
1 0 0 0 0 1 0 0 0 0 0
1 0 1 1 1 1 0 1 0 1 1
1 1 0 1 1 1 1 0 1 0 1
1 1 1 1 1 1 1 1 1 1 1
 It is important to note that the distributive property is often used in reverse, i.e., given
AB + AC. We replace it by its equivalent A(B+C). As in ordinary algebra, this process
is called factoring, we factored A out of the expression AB + AC.
Boolean Algebra and Logic Gates 1.29

1.4.3. DEMORGAN’S THEOREMS

DeMorgan suggested two theorems that form an important part of Boolean algebra.
They are,
 – –
Theorem 1: AB = A + B: The complement of a product is equal to the sum of the
complements. i.e., the complement of „AND‟ operation is equal to the OR operation of the
complements.
– – – –
A B AB AB A B
A B A+B
0 0 0 1 0 0 1 1 1
=
0 1 0 1 0 1 1 0 1
1 0 0 1 1 0 0 1 1
1 1 1 0 1 1 0 0 0
 – –
Theorem 2: A + B = A  B: The complement of a sum is equal to the product of the
complements. i.e., the complement of a „OR‟ operation is equal to the AND operation of
the complements.
– – – –
A B A+B A+B A B
A B A B
0 0 0 1 0 0 1 1 1
=
0 1 1 0 0 1 1 0 0
1 0 1 0 1 0 0 1 0
1 1 1 0 1 1 0 0 0

1.4.4. DUALITY THEOREM

The principle of duality theorem states that, every algebraic expression from the
postulates of Boolean algebra remains valid if the operators and identity elements are
interchanged.

If we apply dual principle for an algebraic expression, simply interchange OR and

AND operators and replace 1‟s by 0‟s and 0‟s by 1‟s.
–
For example: A + A = 1, Here the OR is changed by AND means it replace the 1 by 0.
–
i.e., A  A = 0.
 1.30 Digital Principles and System Design

1.4.5. BASIC THEOREMS

The postulates and law of Boolean algebra forms the following basic theorems.
Theorem 1(a): A + A = A (Idempotency)
i.e., A A A+A = A
0 0 0 0 A+A=A
1 1 1 1
Proof:
A + A = (A + A)  – By postulates (A 1–= A)
1 
= (A + A)  (A + A) (A + A = 1)
–
= A+AA (A –A = A)
= A+0 (A A = 0)
A+A= A
Theorem 1(b): A A = A (Idempotency)
i.e., A A AA = A
0 0 0 0 AA=A
1 1 1 1
Proof:
A = AA+0 – By postulate (A + 0 = A)
A
–
= AA+AA (A  A = 0)
– –
=
A (A + A) A+A=1
= A1 A1=A
= A
Theorem 2(a): A + 1 = 1
A
0+1 = 1 A+1=1
1+1 = 1
Proof:
A + 1 = 1  (A + By postulates (1  A = A)
1)
= A + A–(A + 1) (1 = A + A)
–

= A + A – 1 (A  A = 1)
– – –
= A+A (A 1–= A)

= 1 (A + A = 1)
Theorem 2(b): A 0=0

A
0  0 = 0 A  0 = 0
10 0
=
Boolean Algebra and Logic Gates 1.31

=
Theorem 3: A = A (Involution)
=
A = A (i.e., double the complement of A is A)
A – =
A A=A
0 1 0 =
A=A
1 0 1
Theorem 4(a): A + AB = A (Absorption)
A B AB A + AB
0 0 0 0
0 1 0 0  A + AB = A
1 0 0 1
1 1 1 1

Proof:
A + AB = A  1 + AB By postulates (A  1 = A)
= A (1 + B) By theorem 2(a) (1 + A = 1)
= A1 (A  1 = A)
= A
Theorem 4(b): A (A + B) = A (Absorption)
A B A+B A (A + B)
0 0 0 0
0 1 1 0  A(A + B) = A
1 0 1 1
1 1 1 1
Proof:

A (A + B) = A  A + By theorem 1(b) AA=A

AB
= A + AB By theorem 4(a) A + AB = A
= A
1.32 Digital Principles and System Design
Theorem 5(a): –
A + AB = A + B
Proof:
– –
A + AB = A + AB + AB– By theorem 4(a) A + AB = A
= A + B  (A + A) By postulates –
= A+B1 By postulates A + A = 1
= A+B (B  1 + B)
– – –
A B A+B
A AB A + AB
0 0 1 0 0 0 –
011 1 1 1
 A + AB = A + B
1 0 0 0 1 1
1 1 0 0 1 1
Theorem 5(b): –
A  (A + B) = AB
– – –
A B AA + B A (A + B) AB
0 0 1 1 0 0 –
011 1 0 0
 A (A + B) = AB
1 0 0 0 0 0
1 1 0 1 1 1
Proof:
– – By theorem 4(a) A = A + AB
A  (A + B) = (A + AB)  A + B
= – By postulate B  B = B
AA + AB + ABB
= AB + AB A+A=A
= AB

1.4.6. CONSENSUS
THEOREM
–
In simplification of Boolean expression, an expression of the form AB–+ AC + BC, the
term BC is redundant and can be eliminated to form the equivalent AB + AC. The theorem
used for this simplification is known as consensus theorem and it is stated as
– –
AB + AC + BC = AB + AC
 Boolean Algebra and Logic Gates 1.33
Proof: – – –
AB + AC + BC = AB + AC + (A + A) BC
= – –
AB + AC + AB + AC
= –
AB + AC
Table 1.2. List of Postulates, Laws and Theorem of Boolean Algebra

Postulates (a) (b)

Postulate 2 A+0=A A1=A
Postulate 5 – –
A+A=1 AA=0
Postulate 4 A (B + C) = AB + AC A + BC = (A + B) (A + C)
Postulate 3 A+B=B+A AB = BC
Laws (a) (b)
Commutative Laws A+B=B+A AB = BA
Associative Laws A + (B + C) = (A + B) + C (AB) C = A (BC)
Distributive Law A (B + C) = AB + AC
Theorems (a) (b)
DeMorgan‟s Theorems  – –  – –
AB = A + B A+B=AB
Theorem 1 A+A=A AA=A
Theorem 2 A+1=A A0=0
Theorem 3 = –
A=A
Theorem 4 A + AB = A A (A + B) = A
Theorem 5 – –
A + AB = A + B A  (A + B) = AB

1.5. BOOLEAN EXPRESSION

Boolean algebra is an algebra that deals with binary variables and logic operations. A
Boolean function described by an algebraic expression consists of binary variables.
Example: The Boolean function consists of variable A, B and C can be expressed as
f (A, B, C) = (A + B) C (or) f = (A + B) C
A Boolean function can be represented in a truth table. The number of rows in the truth
n
table is given by 2 where n is the number of variables.
For example, if the function consists of three variable A, B and C, then number of rows
n 3
in truth table = 2 = 2 = 8.
 1.34 Digital Principles and System Design

A Boolean function can be transformed from an algebraic expression into a circuit

diagram composed of logic gates connected in a particular structure. Boolean expressions
are constructed by connecting the Boolean constants and variables with the Boolean
operations. According to the operator „+‟ and „.‟, the Boolean expression is called as
minterm or a standard product and maxterm as standard sum.

1.5.1. MINTERMS

– A binary variable may appear either in its normal form (A) or its complement form
(A). Now consider two binary variables A and B combined with an AND operation. These
– –
two variables may be in two form i.e., A, A, B and B. If these variables are combined with
–– – –
an AND operation, there are four possible combinations: AB, AB, AB, AB. Each of these
four AND terms is called a minterm or a standard product.
Example: Variable A and B are combined with AND operation then AB is called as
minterm. It is denoted by m .

1.5.2. MAXTERMS
In similar to minterms, if the variables are combined with an „OR‟ operation, there are
– – – –
four possible combinations: A + B, A + B, A + B, A + B. Each of these four OR terms is
called a maxterm or a standard sum.
Example: Variable A and B are combined with OR operation, then A + B is called as
maxterm. It is denoted by M.
Minterm and Maxterm for three Binary Variables
Variable = 3; n 3
So 2 = 2 = 8 rows of binary values
A B C Minterms Maxterms
Term Designation Term Designation
–––
0 0 0 ABC m0 A+B+C M0
–– –
0 0 1 ABC m1 A+B+C M1
– – –
0 1 0 ABC m2 A+B+C M2
– – –
0 1 1 ABC m3 A+B+C M3
–– –
1 0 0 ABC m4 A+B+C M4
– – –
1 0 1 ABC m5 A+B+C M5
– – –
1 1 0 ABC m6 A+B+C M6
– – –
1 1 1 ABC m7 A+B+C M7
Boolean Algebra and Logic Gates 1.35

We know that according to Duality principle, if AND is replaced by OR, then the
binary variables also changed i.e., 0 replace 1. The minterm and maxterm also describes
the principles of duality theorem. Thus in minterm, if the binary of A is 0, then it is
–
represented as A and in maxterm if the binary value of A is 0, then it is represented as A.

1.5.3. SUM OF PRODUCT TERMS (SOP)

Sum of product terms is also called as sum of minterms. That means if two or more
minterms are combined with an OR Logic is said to be a sum of product (SOP). A minterm
is a term of two or more variables which are combined with AND Logic. The minterms
whose sum defines the Boolean function are those which give the 1‟s of the function in a
truth table.
– –
For example, consider a function with three minterm: AB, B C, AC. A SOP is a group
of product terms ORed together. The minterm are the product term.

The product terms are summed together with a OR Logic is known as Sum of Product
(SOP).

1.5.4. PRODUCT OF SUM TERMS (POS)

Product of sum terms is also called as Product of Maxterms. That means if two or more
maxterms are combined with an AND Logic is said to be a Product of Sum (POS). A
maxterm is a term of two or more variables which are combined with OR Logic.
– –
For example, consider a function with three maxterms: A + B, B + C, A + C. A POS is
a group of sum terms ANDed together. The maxterms are the sum terms.
 The sum terms are product together with an AND Logic is known as Product of Sum
(POS).
 1.36 Digital Principles and System Design

1.6. STANDARD SOP AND POS FORMS

Standard SOP Form
Standard SOP form means the each of the product term consists of all variable of the
function in either complemented form or uncomplemented form.
For example, take an expression given in SOP (Section 1.5.3). The function has three
variables. A, B, C but the product terms in that expression has only two variable, so it is
not in standard SOP form. Since the standard SOP form consists of all the three variables
either in complemented or uncomplemented form.
i.e.,

Here the function has three variables, these three variables are present in each of the
product terms either in complemented or uncomplemented. Hence this expression is in
standard SOP form.

Standard POS Form

Similarly to standard SOP form, the standard POS form means the each of the sum term
consists of all variable of the function in either complemented or uncomplemented form.
For example, take an expression given in POS (Section 1.5.4). In that the function has
three variables A, B, C but the sum terms has only two variable in each. So it is not in
standard POS form. Since the standard POS form consists of all the three variables either
in complemented or uncomplemented form.
i.e.,
Boolean Algebra and Logic Gates 1.37

Here the function has three variables, these three variables are present in each of the
sum terms either in complemented or uncomplemented form. Hence this expression is in
standard POS form.

1.6.1. CONVERTING SOP TO STANDARD SOP FORM

Sum of product form can be converted to standard sum of product form on the basis of
consensus theorem. i.e., by ANDing the terms in the expression with terms formed by
ORing the variables and its complement which are not present in that term.
For example, f (A, B, C) = AC + BC
st nd
Here in 1 product term B is missing and in 2 product term A is missing. So ANDing
the term in the expression with terms formed by the ORing of variable and its complement
which are not present.
Then the above expression becomes
– –
f (A, B, C) = AC (B + B) + BC (A + A)

Steps to convert SOP to Standard SOP Form

Step 1: Find the missing variable in each product term which is defined by the function.

Step 2: ANDing each product term by ORing the missing variable and its complement.

Step 3: Expand the terms by applying distributive law and reorder it by the variables.
Step 4: Reduce the expression by omitting repeated product terms if any.

Example 1.18 Convert the given expression in standard SOP form:

–
f(A, B, C) = AC + AB

Solution:
Step 1: Find missing variables
In given expression –
f (A, B, C) = AC + AB
C is missing
B is missing

Step 2: AND Product term with ORing the missing variables

– – –
f (A, B, C) = AC  (B + B) + AB  (C + C)
1.38 Digital Principles and System Design
Step 3: Expand the terms and reorder it. – – ––
f (A, B, C) = ACB + ACB + ABC + ABC
– – ––
= ABC + ABC + ABC + ABC
Step 4: Omit repeated product terms –– – – – –
f (A, B, C) = ABC + ABC + ABC [ ABC + ABC = ABC]
Then the standard SOP form is
f (A, B, C) = –– –
ABC + ABC + ABC
–
Example 1.19 Express the Boolean function F(A, B, C) = A + BC in a standard
sum of minterms. (April/May 2011)

Solution: Minterm is a product term. So we have to find sum of product terms.
Step 1: Find the missing variables
In given expression –
f (A, B, C) = A + BC
A is missing
B and C is missing

Step 2: AND Product term with ORing the missing variables and
Step 3: Expand the terms and reorder it – – –
F(A, B, C) = –
A  (B + B)  (C + C) + BC (A + A)
– – – ––
= (AB + AB)  (C + C) + ABC + ABC
– – –– – ––
= ABC + ABC + ABC + ABC + ABC + ABC
Step 4: Omit repeated product terms – –– ––
F(A, B, C) = –
ABC + ABC + ABC + ABC + ABC
– – –
[ ABC + ABC = ABC]
Then the standard SOP form is
F(A, B, C) = – – –– ––
ABC + ABC + ABC + ABC + ABC

EXERCISE PROBLEM
1. Convert the expression in standard SOP form: – – –
f (A, B, C) = AC + AB + BC
[Ans. f (A, B, C) = ABC + ABC + ABC + ABC]
2. Convert the expression in standard SOP form. – – ––
f (A, B, C) = A + ABC
[Ans. f (A, B, C) = ABC + ABC + ABC + ABC]
Boolean Algebra and Logic Gates 1.39

1.6.2. CONVERTING POS TO STANDARD POS FORMS

Steps to convert POS to Standard POS Forms

Step 1: Find the missing variable in each sum terms.
Step 2: ORing each sum terms by ANDing the missing variables and its complement.
Step 3: Expand the terms by applying distributive law and reorder the variables in the
sum terms.
Step 4: Reduce the expression by omitting repeated sum terms.

SOLVED EXAMPLES

Example 1.20 Convert the expression in standard POS form.

f (A, B, C) = (A + C)  B

Solution:
Step 1: Find the missing variables.
In given expression f (A, B, C) = (A + C)  B
A and C is missing
B is missing
Step 2: ORing sum terms by AND the missing variable and its complement.
– – –
f (A, B, C) = (A + C) + (B  B)  B + (A  A) + (C  C)
Step 3: Expand the term and reo rder it.
f (A, B, C) = – – –
(A + C + B)  (A + C + B)  (B + A)  (B + A) + (C 
C)
= – – – – –
(A + C + B)  (A + C + B)  (B + A + C)  (B + A + C)  (B + A + C)  (B + A +
C)
= – – – – –
(A + B + C)  (A + B + C)  (A + B + C)  (A + B + C)  (A + B + (A + B + C)
C) 
Step 4: Omit repeated sum terms.
f (A, B, C) = – – – – –
(A + B + C)  (A + B + C)  (A + B + C)  (A + B + (A + B + C)
C) 
[ (A + B + C)  (A + B + C) = (A + B + C)]
Then the standard POS form is

f (A, B, C) – – – – –
= (A + B + C)  (A + B + C)  (A + B + C)  (A + B + C)  (A + B +
C)
 1.40 Digital Principles and System Design

Example 1.21 Convert the expression in standard POS form.

f(A, B, C) = (A + B)  (A + C)

Solution:
Step 1: Find the missing variables.
f (A, B, C) = (A + B)  (A + C)
B is missing
C is missing
Step 2: ORing sum terms by AND the missing variable and its complements.
– –
f (A, B, C) = (A + B) + (C  C)  (A + C) + (B  B)
Step 3: Expand the terms and reorder it.
– –
f (A, B, C) = (A + B + C)  (A + B + C)  (A + B + C)  (A + B + C)
Step 4: Omit repeated terms.
– –
f (A, B, C) = (A + B + C)  (A + B + C)  (A + B + C)
[ (A + B + C)  (A + B + C) = A + B + C]
Then the standard POS form is
– –
f (A, B, C) = (A + B + C)  (A + B + C)  (A + B + C)

EXERCISE
PROBLEM
1. Convert the given expression in standard POS form.
F(A, B, C) = A  (A + B + C) – – – –

[Ans. F(A, B, C) = (A + B + C) (A + B + C) (A + B + C) (A + B + C)]

1.7. MINIMIZATION OF BOOLEAN EXPRESSION

Since we discussed about the postulates and theorem of Boolean algebra, Boolean
expression can be reduced by those theorems and postulates.

Why we do Minimization of Boolean Expression?

We know that Boolean functions can be realised by logic gates. If the Boolean
expression has more number of variables, we require more number of gates and input
terminals. Therefore, the reduction of Boolean expression is very important as it saves the
hardware requirement and cost of design.
Boolean Algebra and Logic Gates 1.41

EXAMPLES FOR MINIMIZATION OF BOOLEAN EXPRESSION

–
1.
F = A  AB – –
F = (A  A)  B [ A  A = 0]
F = 0B
F =0
2. F = A (A + C)
F = A (A + C)
= AA + AC [ A  A = 1]
= A + AC
= A (1 + C) [ 1 + C = 1]
F = A
 –
3. F = XY + XZ + XZY (XY + Z)
F =  –
XY + XZ + XZY (XY + Z)
=  – – –
XY + XZ + XYZ  XY + XYZ  Z [ X  X = X, Y  Y = 0]
=  –
XY + XZ + XZ (0) + XYZ 
= – – – – –
XY + X + Z + XYZ [DeMorgan theorem AB = A + B]
= – – –  – –
X + Y + Z + XYZ [ XZ = X + Z]
= – – – –
X + XYZ + Y + Z [ A + AB = A + B]
= – – –
X + YZ + Y + Z
= – – – – – – –
X + Y + Z + YZ [ Z + YZ = Z + Y]
= – – –
X+Y+Z+Y
= – – – – –
X+Z+Y+Y [ Y + Y = 1;A + A = 1]
= – – [A + 1 = 1; – –
X+Z+1 X + 1 = 1 + Z = 1]
F =1
– ==
4. Z = AB + AB  (AC)
Z = – ==
AB + AB  (AC) – –
By DeMorgan theorem [ AB = A + B]
Z = – = = =
AB + AB  (A + C) [ A = A]
Z = –
AB + AB  (A + C)
Z = – –
AB + ABA + ABC
 1.42 Digital Principles and System Design
Z = – – [ A  A = A]
AB + AB + ABC
Z = – [ 1 + C = 1]
AB + AB (1 + C)
= –1
AB + AB
= – –
A (B + B) [ B + B = 1]
= A1

Z = A

5. Simply the following three variable expression using Boolean algebra

F = m (1, 4, 6, 7).

Solution:
In the function m denotes the minterms and  denotes the sum, so it is sum of product
terms. Take the variables A, B, C and the values represent in binary numbers.
Therefore ––
1 = 001
= ABC
4 = 100 ––
= ABC
6 = 110 –
= ABC
7 = 111 = ABC
Hence, F = –– – –
ABC + ABC + ABC + ABC
= – – – – –
BC (A + A) + AB (C + C) [ A + A = 1, C + C = 1]
= –
BC  1 + AB  1
F = –
BC + AB

6. Simply the following three variable expression using Boolean algebra

F = M (0, 2, 4, 6).

Solution:
In the function  denotes the product and M denotes the maxterm. Hence it is a
product of sum expression. Let us take this expression in sum of product form to
easily simplify the expression as,
F = M (0, 2, 4, 6)
Boolean Algebra and Logic Gates 1.43
F = m (1, 3, 5, 7)
––
1 – 001 – ABC
–
3 – 011 – ABC
–
5 – 101 – ABC
7 – 111 – ABC
Then, F = –– – –
ABC + ABC + ABC + ABC
= – – – –
AC (B + B) + AC (B + B) [ B + B = 1]
–
= AC + AC
= – –
C (A + A) [ A + A = 1]
F = C

EXERCISE PROBLEMS

1. Minimize the following expression.

(i) ABCD + ABD [Ans. ACD]
(ii) – – [Ans. Y (X + Z)]
XY + XYZ + XYZ + XYZ
(iii) – [Ans. C (A + B)]
AC + C (A + AB)
2. Minimize the given expression using Boolean algebra.
Y = M (3, 5, 7) – ––
[Ans. C + AB]
7. Z = A + AB + ABC + ABCD

Z = A + AB + ABC + ABCD
= A (1 + B + BC + BCD) [ 1 + B = 1]
= A1=A

Z =A

–––––––––––
–––––––
8. Y = (ABC) ( AB ) + CB
Y = ––––––––––––––––
(ABC) (AB) + CB
–––– ====  –

= (ABC) + ( AB ) + BC
= – – – 
(ABC) (A + B) + BC
 1.44 Digital Principles and System Design
= – – – ––  – –
ABCA + ABCB + BC [ A  A = 0, B  B = 0]
= 
0 + 0 + BC
Y = –
BC

9. – – –
F = X (XYZ + XYZ)
F = – – –
X (XYZ + XYZ)
= – – – –
XXYZ + XXYZ [ X  X = 0]
= –
0  YZ + 0  YZ
F =0

–– –– ––
10. F = (X1 + X2) (X1 + X1 X2) + (X2 + X1 X2 )
–– –– ––
F = (X1 + X2) (X1 + X1X2) + (X2 + X1X2)
–– –– –– ––
= X1X1 + X1X1X2 + X2X1 + X2X1X2 + X2 + X1X2
–– –– ––
= 0 + X1X2 + X2X1 + X1X2 + X2 + X1X2
–– –– ––
= X2X1 + X2X1 + X1X2 + X1X2 + X2
–– –– ––
= X2 (X1 + X1) + X1 (X2 + X2) + X2
––
= X2  1 + X 1  1 + X 2
––
F = X2 + X1 + X2

11. ––––––––– ––––––––

Z = A (C + D) + C (A + B)
Z = ––––––––– ––––––––
A (C + D) + C (A + B)
= = –––––– =––––––
A + (C + D) + C (A + B)
= –= – =
A+CD+C+AB
= – –
A + CD + C + AB
= – – –
A + AB + C + CD [ A + AB = A + B]
Z = A+B+C+D
 Boolean Algebra and Logic Gates 1.45
–
Example 1.22 Simplify: XY + XZ + YZ (Nov/Dec 2013)

Solution: Convert the given function into standard SOP form.
F = – – – –
XY [Z + Z] + XZ [Y + Y] + YZ [X + X]
= – – – – –
XYZ + XYZ + XZY + XZY + XYZ + XYZ
= – – – –
XYZ + XYZ + XZY + XZY
= – – –
XY [Z + Z] + XZ [Y + Y]
F = –
XY + XZ

Example 1.23 Simplify the given Boolean expression F = X′ + XY + XZ′ + XY′Z′.

(Nov/Dec 2012)
 F = X′ + XY + XZ′ + XY′Z′
Solution:
F = – – ––
X + XY + XZ + XYZ
F = – – –– –
X + Y + XZ + XYZ [ A + AB = A + B]
F = – – [ A + AB = A]
X + Y + XZ
F = – – – – –
X + XZ + Y = X + Z + Y [ A + AB = A + B]
–
Example 1.24 Simplify Y = (A + B) (A + B).
 Y = –
Solution: (A + B) (A + B)
–
= AA –
+ AB + BA + BB –
–
= AB + AB + B [A  A = 0]
= – –
B [A + A] + B [A + A = 1]
= B+B
= B
–
Example 1.25 Express the Boolean function F = XY + XZ in a product of maxterm
form and also to standard POS.
 –
Solution: F = XY + XZ
1.46 Digital Principles and System Design
– [ X + (YZ) = (X + Y) (X + Z)]
= (XY + X) (XY + Z)
– –
= (X + X) (Y + X) (X + Z) (Y + Z)
F = – –
(X + Y) (X + Z) (Y + Z) [ X + X = 1]
These 3 terms have one variable missing each.
F = – – – –
(X + Y + (Z  Z)) (X + Z + Y  Y) (Y + Z + X  X)
F = – – – – –
(X + Y + Z) (X + Y + Z) (X + Y + Z) (X + Y + Z) (X + Y + Z) (X + Y + Z)
F = – – – –
(X + Y + Z) (X + Y + Z) (X + Y + Z) (X + Y + Z)
– hence
In POS form X = 0, X = 1,
F = – – – –
(X + Y + Z) (X + Y + Z) (X + Y + Z) (X + Y + Z)
= 000 010 100 101
= 0 2 4 5

F =  M (0, 2, 4, 5)

Example 1
.
2
Convert the following SOP expression to an equivalent POS
6

expression. – –– – – – –
ABC + ABC + ABC + ABC + ABC

Solution: The given expression is in standard SOP form.
F = ––– – – – –
ABC + ABC + ABC + ABC + ABC
000 010 011 101 111
0 2 3 5 7
F = m (0, 2, 3, 5, 7)
Therefore the POS is a complement of SOP.
– = (1, 4, 6) = 001 + 100 + 110
F
– = 001 + 100 + 110
F
= = ––––––––––––––
F 001 + 100 + 110
F = ––– ––– ––– –––– ––––– –––––
001 100 110  ( ABC ) ( ABC )  ( ABC )
 
– – – –
F = (A + B + C)  (A + B + C)  (A + B +
C)
Boolean Algebra and Logic Gates 1.47

Example 1.27 F (A, B, C) = (1, 4, 5, 6, 7). Find the product of maxterms.

 F(A, B, C) =  (1, 4, 5, 6, 7)
Solution:
– =  (0, 2, 3)
F(A, B, C)
= ––––––––––––
F(A, B, C) = m0 + m2 + m3
–– –– ––
F(A, B, C) = m  m m = M  M2  M3
0 2 3 0

F(A, B, C) = П M (0, 2, 3)
1.7.1. KARNAUGH MAP MINIMIZATION (K-MAP)
The complexity of the Boolean expression is minimized by mapping the terms. The
map method presented here provides a simple, straight forward procedure for minimizin g
Boolean functions. This method may be regarded as a pictorial form of a truth table. The
map method is also known as the Karnaugh map or K-Map.
A K-Map is a diagram made up of squares, with each square representing one minterm
of the function which is to be minimized. The simplified expressions produced by the map
are always in one of the two standard forms: Sum of Products (SOP) or Product of Sum
(POS).

Minimization of SOP Form

One Variable K-Map

n
A K-Map is made up of squares. Each of the square represent the 2 possible value
that can be formed by n variables.
For one variable K-Map n =1
Then map contains, 2
n = 21 = 2 values or squares

One variable – A and two values 0 and 1.

Fig. 1.1. K-Map structure for one variable
 1.48 Digital Principles and System Design

Two Variable K-Map

It has two variables A, B and n = 2.
n 2
Then, Map contains 2 = 2 = 4 values or square.
It has two variables and 4 squares of values 00, 01, 10, 11.

Fig. 1.2. K-Map structure for two variable

Three Variable K-Map

Similarly, it has three variables A, B, C and n = 3.
n 3
Then, Map contains 2 = 2 = 8 values or squares.
It has three variables and 8 squares.

Fig. 1.3. K-Map structure for three variable

Four Variable K-Map

Variables A, B, C and D and n = 4.
n 4
Then, Map contains 2 = 2 = 16 values or squares.
Boolean Algebra and Logic Gates 1.49
 Fig. 1.4. K-Map structure for four variable

Grouping of Cells for Simplification

Since, we know that the structure of K-Map for the respective variables which are used.
The K-Map is used to simplify the expression in either POS or SOP form. For
simplification, we have pair the adjacent ones as group and take the common factor in that
ones. The adjacent ones should be in pair i.e., we can group two adjacent ones (Pair),
grouping four adjacent ones (Quad) and grouping eight adjacent ones (Octet).

Grouping Two Adjacent Ones (Pair)

In K-Map, if two ones are adjacent to each other, then it is called Pair. The pair can be
simplified by taking the common variable in those cells.
The following Fig.1.5 shows the possible two adjacent ones and its simplification
expression.
For Two Variables
Fig. 1.5.
1.50 Digital Principles and System Design
 From the first Fig.1.5, the–common variable
for the two adjacent– ones is B, so the simplified
expression is F = B. Similarly for second, third
and fourth Fig.1.5.
Two adjacent ones are also possible. Here two
pairs of one are grouped and those two terms are
ORed to form an expression.

Fig. 1.5.

For Three Variable

–
The common factor for the pair is A and C. In
– is common for both ones and in
horizontal A
– and BC is there in that C is the
vertical BC
–  C.
common variable. Hence F = A

Fig. 1.6. (i)

Similarly,

Fig. 1.6. (ii) Fig. 1.6. (iii)

Boolean Algebra and Logic Gates 1.51
 Fig. 1.6. (iv) Fig. 1.6. (v)

Following Pair is not possible

Fig. 1.6. (vi)

For Four Variable K-Map
–
In horizontal AB is the common term for
–
both the ones and in vertical from CD and
CD, – D is the common variable, hence F =
ABD.

Fig. 1.7. (i)

–
F = ABD
1.52 Digital Principles and System Design

––– – – –– –
F = ABD + ABD F = ACD + ABC + ABC + ACD
Fig. 1.7. (ii) Fig. 1.7. (iii)

Grouping Four Adjacent Ones (Quad)

For Three Variable

Fig. 1.8. (i) Fig. 1.8. (ii)

Fig. 1.8. (iii) Fig. 1.8. (iv)
Boolean Algebra and Logic Gates 1.53

For Four Variable

Fig. 1.9. (i) Fig. 1.9. (ii)

Fig. 1.9. (ii) Fig. 1.9. (iv)

Grouping Eight Adjacent Ones (Octet)

Fig. 1.10. (i) Fig. 1.10. (ii)
 1.54 Digital Principles and System Design

Fig. 1.10. (iii) Fig. 1.10. (iv)

Illegal Grouping

Some of the illegal grouping in K-Map are shown below.

Fig. 1.11. (i) Diagonal grouping is illegal Fig. 1.11. (ii) Odd number ones is illegal
Fig. 1.11. (iii) Odd number ones is illegal
Boolean Algebra and Logic Gates 1.55

Guidelines to Plot K-Map

(i) Draw the K-Map structure as per the given instruction.
(ii) Place 1s in those cells corresponding to the given expressions and place 0s in
remaining cells.
(iii) Check for the adjacent ones such as Pair, Quad and Octet.
(iv) Write the simplified expressions for the adjacent ones.
SOLVED EXAMPLES
Example 1.28 Minimize the expression
– –– – –– –––
F = X Y Z + X Y Z + X Y Z + XY Z + X Y Z .
 – –– – –– –––
Solution: F = XYZ + XYZ + XYZ + XYZ + XYZ
= 101 + 001 + 011 + 100 + 000
(i) Draw the structure of K-Map for three variable.

(ii) Place 1s in those cells corresponding to the terms in the given expression.

(iii) Check for adjacent ones

1.56 Digital Principles and System Design

(iv) Simplify the K-Map

– –
F = XZ + Y

Example 1.29 Simplify the following Boolean expression:

–– – – – – – –– – –– – ––
Y(A, B, C, D) = ABCD + ABCD + ABCD + ABCD + ABCD
– – – – –
+ ABCD + ABCD + ABCD

Solution:

–– –– –
Y(ABCD) = AC + AD + BCD

Example 1.30 Simplify the following Boolean expression.

(i) Y(A, B, C, D) = m (1, 2, 5, 6, 8, 9)
 m (1, 2, 5, 6, 8, 9)
Solution:
1 = 0000 = – – – –
ABCD
2 = 0010 = – – –
ABCD
Boolean Algebra and Logic Gates 1.57
5 = 0101 = – –
ABCD
6 = 0110 = – –
ABCD
8 = 1000 = –––
ABCD
9 = 1001 = ––
ABCD

Place the one‟s in those corresponding to the values in the given expression.
 –– –– – –
Y(ABCD) = ABC + ACD + ACD
 1.58 Digital Principles and System Design

Example 1.31 Minimize the following expressions using K-Map.

Y(A, B, C) =  m (0, 1, 2, 3, 4, 5, 6, 7)

Solution: The given expression has three variables, so plot in three variable K-Map
structure.

Y(A, B, C) = m (0, 1, 2, 3, 4, 5, 6, 7)
0 – 000 – – – 4 – 100 – ––
– ABC; ABC
1 – 001 – – 5 – 101 – –
– ABC; ABC
2 – 010 – – 6 – 110 – –
– ABC; ABC
3 – 011 – 7 – 111 – ABC
– ABC;

Place the one‟s in those corresponding to the values in the given expression.
i.e.,
Y(A, B, C) = 1
Boolean Algebra and Logic Gates 1.59

In the above K-Map, there are eight adjacent ones, so octet is possible. For this, there
no common variable, therefore the expression 1.

Example 1.32 Minimize the following expressions using K-Map.

F(A, B, C) = m (0, 2, 4, 6)

Solution:

Place the one‟s in those corresponding to the values in the given expression.

–
Y(A, B, C) = C
Example 1.33 Simplify the following expressions using K-Map.
Y(A, B, C, D) = m (0, 2, 4, 7, 8, 10, 12, 13)

Solution:
Place the one‟s in those corresponding to the values in the given expression.
1.60 Digital Principles and System Design

– – –– ––
Y(A, B, C, D) = ABCD + ABC + BD + CD

Example 1.34 Simplify the following expression using K-Map method.

Y = m (7, 9, 10, 11, 12, 13, 14, 15) (Nov/Dec 2013)

Solution:
Place the one‟s in those corresponding to the
values in the given expression.

Y(A, B, C, D) = AB + AC + AD + BCD

Example 1.35 Simplify the following expression using K-Map method.

F(W, X, Y, Z) =  (0, 1, 2, 4, 5, 6, 8, 9, 12, 13, 14) (April/May 2011)
Boolean Algebra and Logic Gates 1.61


Solution:
 – – –– – – ––
F(A, B, C, D) = C + BD + AD F(W, X, Y, Z) = Y + XZ + WZ
 Example 1.36 Simplify the Boolea n Example 1.37 Minimize the following
Expression using K-Map method. logic function using K-Map.
Y(A, B, C, D) = m (0, 1, 2, 3, 4, 5, 6, 11) Y(A, B, C, D) = m (0, 1, 2, 3, 5, 7, 8, 9, 11,
14)
 
Solution: Solution:
 –– –– – –– – –– – –
Y(A, B, C, D) = AC + AD + BCD Y(A,B,C,D) = AB+AD+BC+BD+ABCD
 1.62 Digital Principles and System Design

EXERCISE PROBLEMS

Simplify the following expression using K-Map.

(i) Y(A, B, C) = m (0, 1, 4, 5) –
[Ans. Y(A, B, C) = B]
(ii) Y(A, B, C) = m (0, 2, 4) –– ––
[Ans. Y(A, B, C) = AC + BC]
(iii) Y(A, B, C, D) = m (1, 2, 5, 6, 8, 9) –– –– – –
[Ans. ACD + ABC + ACD]
(iv) Y(A, B, C, D) = m (0, 1, 2, 3, 4, 7, 8, 9, 10, 11, 12, 14)
– –– – –
[Ans. Y(A, B, C, D) = B + CD + ACD + AD]
(v) – – –
Y(A, B, C, D) = ABC + BCD + BD [Ans. Y(A, B, C, D) = AB + BD + BC]
Note [Hint for (v): Convert the given expression into standard SOP form and p lot K-
Map.]

MINIMIZATION OF POS FORM

We know that POS is the complement form of SOP. Therefore the POS structure of K-
Map can be obtained by taking complement to each terms in rows and columns.

K-Map Structure for SOP – 4 Variables

To get POS structure, take complement for the each terms in row and columns.
–
Y(A, B, C, D)
Boolean Algebra and Logic Gates 1.63

We know that in POS,

– – – –
The variables A, B, C, D = 0 and complementary of the variables A, B, C, D = 1.
 1.64 Digital Principles and System Design

Similarly, for 3-variable K-Map structure in POS form is

Example 1.38 Simplify the Boolean expression using K-Map in POS form.
– – – – – – – –
Y(A, B, C) = (A + B + C) (A + B + C) (A + B + C) (A + B + C)

Solution:
Given: Y(A, B, C) = – – – – – – – –
(A + B + C) (A + B + C) (A + B + C) (A + B + C)
In POS, – – –
A, B, C = 0 and A, B, C = 1.
Y(A, B, C) = (0 + 1 + 0) (1 + 1 + 0) (0 + 1 + 1) (1 + 1 + 1)
= 010 110  011  111
= 2 6 3 7
Y(A, B, C) = П (2, 6, 3, 7)
Place 0s in those cells corresponding to the values in the given expression and in the
remaining cells place 1s.
Boolean Algebra and Logic Gates 1.65

In SOP, we have grouping the adjacent ones, but in POS, we have to group adjacent
zeros, because POS is the complementary function of SOP.
Also place 0‟s in those corresponding to the values in the expression instead of 1‟s.

–
Y(A, B, C) = B

Example 1.39 Simplify the Boolean Expression using K-Map.

– –
Y(A, B, C) = (A + B)  (A + C)

Solution: The given expression is not in the standard POS. So we have to find the
standard POS form.
– –
Y(A, B, C) = (A + B)  (A + C)
In first term, C is missing and in second term B is missing.
Y(A, B, C) = – – – –
(A + B) + C   (A + C) + B  B
C
Y(A, B, C) = – – – – – –
(A + B + C)  (A + B + C)  (A + B + C)  (A + B +
C)
Y(A, B, C) = П (4, 5, 1, 3)

– –
Y(A, B, C) = (A + C)  (A + B)
Example 1.40 Minimize the Boolean expression using K-Map.
Y(A, B, C) = П M (0, 3, 5, 6)
1.66 Digital Principles and System Design


Solution:

Place 0‟s in those corresponding to the values in the given expression.

– – – – – –
Y(A, B, C) = (A + B + C)  (A + B + C)  (A + B + C)  (A + B + C)

Example 1.41 Simplify the Boolean expression using K-Map.

Y(A, B, C, D) = П M (5, 7, 13, 15)

Solution:

Place 0‟s in those corresponding to the values in the given expression.

Boolean Algebra and Logic Gates 1.67

– –
Y(A, B, C, D) = B + D

Example 1.42 Minimize the Boolean expression using K-Map.

Y(A, B, C, D) = П M (0, 1, 4, 5, 6, 8, 9, 10, 13, 14, 15)

Solution:
Place 0‟s in those corresponding to the
values in the given expression.

–
Y(A, B, C, D) = (A + C)  (C + D)  (B + C)
– – – – – – –
 (A + B + D)  (A + C + D)  (B + C +
D)

Example 1.43 Miminize the Boolean expression using K-Map.

Y(A, B, C, D) = П M (0, 1, 2, 3, 8, 9, 10, 11, 12, 13)
1.68 Digital Principles and System Design


Solution:

–
Y(A, B, C, D) = (B)  (A + C)

Example 1.44 Simplify the following expression:

Y(A, B, C, D) = П M (1, 2, 5, 6, 8, 9, 10, 11, 15)

Solution:

– – – – – –
Y(A, B, C, D) = (A + B)  (A + C + D)  (A + C + D)  (A + C + D)

EXERCISE PROBLEM
Simplify the following expression using K-Map in POS form.
(i) Y(A, B, C) = П M (0, 1, 4, 5) [Ans. Y(A, B, C) = B]
(ii) Y(A, B, C) = П M (0, 2, 4, 5) –
[Ans. (A + C)  (A +
B)]
(iii) Y(A, B, C, D) = П M (0, 2, 8, 9, 12, 13, 15) – – – –
[Ans. (A + C) (A + B + D) (A + B + D)]
Boolean Algebra and Logic Gates 1.69
(iv) Y(A, B, C, D) = П M (0, 1, 2, 3, 5, 6, 7, 12, 14)
– – – –
[Ans. (A + B)  (A + D)  (A + C) (A + B + D)]
(v) – –
Y(A, B, C, D) = (A + B + C) (A + B + D) [Ans. (A + B + C) (A + B + D)]

1.7.2. DON’T CARE CONDITION

When the Boolean function is defined in terms of minterms, 1s are entered in the K-
Map corresponding to the input conditions and when the Boolean function is defined in
terms of maxterms, i.e., 0s are entered. If the cells that do not contain 1 are assumed to
contain 0 and vice-versa. This condition is not always true.
In some logic circuit, certain input conditions never occurs, therefore the corresponding
output never appears. In such cases, the output level is not defined, it can be either High or
Low. These output levels are indicated by „ X‟ (cross) and called as Don‟t care condition.
The „X‟ mark in K cell may be assumed to be 1 or 0 depending upon which one leads to a
simpler expression.
„X‟ and „d ‟ – denotes the don‟t care terms.

GUIDELINES FOR GROUPING IN DON’T CARE CONDITION

For SOP Form:

Consider the don‟t care, „X‟ for grouping, if it form Pair, Quad, Octet with the adjacent
1s. Note, do not consider the don‟t care „ X‟ for grouping without adjacent 1s, even
though the X alone form Pair, Quad and Octet, do not consider for grouping.

For POS Form:

Consider the don‟t care, „X‟ for grouping, if it form Pair, Quad, Octet with the adjacent
0s. Note, do not consider the don‟t care, „ X‟ for grouping without adjacent 0s, even
through the X alone form Pair, Quad and Octet, do not consider for grouping.

Example 1.45 Simplify the following expression using K-Map:

Y(A, B, C) = m (0, 1, 3, 5, 6) + d(2, 4) (May/June 2004)

Solution: The given expression, m denotes the expression in the form of SOP and
d denotes the don‟t care variables.
1.70 Digital Principles and System Design

Place 1‟s in those corresponding values

in the m and place „X‟ in those
corresponding values in „d ‟.

– – –
Y(A, B, C) = A + B + C

Example 1.46 Simplify the Boolean expression using K-Map.

Y(A, B, C, D) = m (1, 3, 7, 11, 15) + d (0, 2, 4)

Solution:
Place 1‟s in those corresponding to the
values in m and place „X‟ in those
corresponding to the values in „d ‟.
The don‟t care value corresponding to the
values 4 is not considered for group because it
form Pair with adjacent don‟t care values.

––
Y(A, B, C, D) = CD + AB

Example 1.47 Reduce the following expression:

F(A, B, C, D) = m (0, 7, 8, 9, 10, 12) + d(2, 5, 13)
Boolean Algebra and Logic Gates 1.71


Solution:

–– – –
F(A, B, C, D) = BD + AC + ABD

Example 1.48 Reduce the following expression:

F(A, B, C, D) = m (2, 4, 8, 11, 15) + d(1, 10, 12, 13)

Solution:

–– –– – –
F(A, B, C, D) = ACD + BCD + ACD + BCD

Example 1.49 Simplify the following functions:

Y(A, B, C) = П M (0, 1, 4, 6)  d(2, 3)

Solution: In the given expression, П M denotes the POS form and „d ‟ denotes the don‟t
care condition.
 1.72 Digital Principles and System Design

3-variable K-Map for POS is

Place 0‟s in those corresponding to the values in П M and place „X‟ in those
corresponding to the values in d .

Y(A, B, C) = (A + B)  (C)

Example 1.50 Reduce the given Boolean expression:

Y(A, B, C, D) = П M (4, 5, 7, 8, 12)  d (1, 2, 3, 9, 11, 14)

Solution:
 – – – –
Y(A, B, C, D) = (A + C + D)  (A + B + C)  (A + B +
D)
Boolean Algebra and Logic Gates 1.73

Example 1.51 Simplify the Boolean expression using K-Map. f(A,

B, C, D) = П M (1, 3, 4, 5, 9, 10, 11)  d(6, 8)

Solution:

– – –
f (A, B, C, D) = (A + B)  (B + D)  (A + B + C)

Example 1.52 Simplify the Boolean expression using K-Map. f(W,

X, Y, Z) = П M (0, 7, 8, 9, 10, 12)  d(2, 5, 13)

Solution:

– – –
f (W, X, Y, Z) = (W + X + Z)  (W + Y)  (X + Z)

EXERCISE PROBLEM
Simplify the Boolean function. –
(i) Y(A, B, C) = m (0, 1, 3, 5) + d (2, 5)
[Ans. A + C]
 1.74 Digital Principles and System Design
(ii) Y(A, B, C, D) = m (1, 3, 5, 8, 9, 11, 15) + d (2, 13) – –– –

[Ans. CD + ABC + AD + BD]

(iii) Y(A, B, C, D) = П M (1, 2, 3, 8, 9, 10, 11, 14)  d (7, 15) – – – –
[Ans. (A + B) (B + D)  (B + C)  (A + C)]
–
(iv) Y(A, B, C, D) = П M (5, 6, 7, 12, 13)  d (4, 9, 14, 15)
[Ans. Y = B]

FIVE VARIABLE K-MAP

5
A 5 variable requires, 2 = 32 cells, but adjacent cells are difficult to identify on a
single 32-cell Map. Therefore, two 16-cell K-Maps are generally used as shown below.

Grouping in 5-Variable K-Map

Boolean Algebra and Logic Gates 1.75

Example 1.53 Simplify the Boolean function:

Y(A, B, C, D, E) = m (4, 5, 6, 7, 20, 21, 22, 23)

Solution:

–
Y(A, B, C, D, E) = BC

Example 1.54 Simplify the Boolean function:

F(A, B, C, D, E) = m (1, 4, 8, 10, 11, 20, 22, 24, 25, 26) + d(0, 12, 16, 17)
1.76 Digital Principles and System Design


Solution:

––– ––– –– – – –– – –
F(A, B, C, D, E) = BCD + ADE + BCE + ABCD + ACD + ABCE

Example 1.55 Simplify the Boolean expression:

Y(A, B, C, D, E) = П M (3, 4, 7, 11, 15, 19, 21, 23, 27, 28, 29, 31)

Solution:

– – – – – – – – –
Y(A, B, C, D, E) = (A + C + E)  (A + B + C + D)  (A + B + C + D + E)  (D + E)
Boolean Algebra and Logic Gates 1.77

EXERCISE PROBLEM

Simplify the following Boolean expression.

(i) Y(A, B, C, D, E) = m (0, 5, 6, 8, 9, 10, 11, 16, 20, 24, 25, 26, 27, 29, 31)
––– –– – –– – – –––
[Ans. CDE + ABCDE + ABCDE + BC + ABDE + ABE]
(ii) Y(A, B, C, D, E) = m (0, 1, 5, 6, 9, 13, 14, 17, 21, 22, 25, 29)
– – – –––– – –
[Ans. DE + BCDE + ABCD + ACDE]
(iii) Y(A, B, C, D, E) = П M (0, 2, 4, 6, 9, 11, 13, 15, 17, 21, 25, 27, 29, 31)
– – – –
[Ans. (A + B + E)  (B + E)  (A + D + E)]

Limitations of K-Map
The K-Map method of simplification is convenient for the number of variables does not
exceed five or six. As the number of variables increases, the excessive number of squares
prevents a reasonable selection of adjacent squares. For the function of six or more
variables, it is difficult to plot and grouping the best selection has been made.

1.7.3. QUINE–McCLUSKEY

To overcome the limitations of K-Map, W. V. Quine and E.J. McCluskey developed an

exact tabular method to simplify the Boolean expression. This method is called Quine
McCluskey or tabular method.
It is a specific step by step procedure that is guaranteed to produce a simplified
standard-form expression for a function. It can be applied to the functions with many
variables and has the advantages of being suitable for machine computation.
The tabular method of simplification consists of two parts. The first is to find by an
exhaustive search all the terms that are candidates for inclusion in the simplified function.
These terms are called Prime-implicants. The second operation is to choose among the
prime-implicants those that give an expression with the least number of variables.

Procedure to Minimize the Expression using Tabular Method

Step 1: List all minterms in the binary form.
Step 2: Arrange the minterms according to the number of 1s and also split term.
Step 3: Compare each binary number with every term in the adjacent next higher

category column. If they differ by only one position, put a check ( ) mark
and write in the next column.
1.78 Digital Principles and System Design

Step 4: Repeat step 3 for the resultant column and continue these cycles until no further
elimination of variables takes place.
Step 5: List the prime implicants. [The remaining terms and the terms which do not
match during the process are called prime implicants] i.e., prime implicants
are which has uncheck mark].
Step 6: Form Prime Implicant Chart
(i) The prime implicants should be represented in rows and each minterm of
the function in a column.
(ii) Cross (X) should be placed in each row to show the composition of
minterm that makes the prime implicants.
(iii) A completed prime implicant table should be inspected for columns
containing only a single cross. Prime implicants that cover m interm with
a single cross in their columns are called essential prime implicants.
Step 7: Select the minimum number of primes that must cover all the minterms.

Example 1.56 Simplify the given expression using Quine McCluskey Method.
f(a, b, c, d) = m (0, 1, 2, 3, 8, 9)

Solution: Step 1: List all the minterms in the binary form.
Minterm Binary Representation

m0 0000
m1 0001
m2 0010
m3 0011
m8 1000
m9 1001

Step 2: Arrange the minterms according to the number of 1s and also split them.
Minterm Binary Representation Group
m0 0000 Group 0
Number of 1s zero
m1 0001 Group 1
m2 0010 Number of 1s one

m8 1000
m3 0011 Group 2
m9 1001 Number of 1s two
Boolean Algebra and Logic Gates 1.79

Step 3: Compare each binary number with next higher group. If they differ by only one
position and put a check mark.
Step 4: Repeat step 3 for the resultant column and continue these cycles until no
further elimination of variables takes place.
Minterms Binary Representation Minterms Binary
Representation
0, 1 0 0 0 –  0, 1, 8, 9 – 0 0 –
0, 2 0 0 – 0  0, 1, 2, 3 0 0 – –
0, 8 – 0 0 0 

1, 3 0 0 – 1 
1, 9 – 0 0 1 
2, 3 0 0 1 – 
8, 9 1 0 0 – 

Step 5: List the Prime Implicants

Prime Implicants Binary Representation
a b c d
0, 1, 8, 9 – 0 0 –
0, 1, 2, 3 0 0 – –

Step 6: Form Prime Implicant Chart

Prime Implicant Table
Prime Implicants Minterms
0 1 2 3 8 9
 X X X X
0, 1, 8, 9
 X X X X
0, 1, 2, 3
   

Step 7: Select the minimum number of primes that must cover all the minterms.

Here both (0, 1, 8, 9) and (0, 1, 2, 3) are essential prime implicants, so we have to
consider both the primes.
1.80 Digital Principles and System Design

a b c d
0, 1, 8, 9 – 0 0 – ––
=bc
0, 1, 2, 3 0 0 – – ––
=ab
–– ––
f (a , b, c , d ) = b c + a b

Example 1.57 Minimize the given expression using tabulation method.

F(x 1 x 2 x 3 x 4 ) =  (0, 5, 7, 8, 9, 10, 11, 14, 15) (May/June 2013)

Solution:
Step 1: List all minterms in the binary form.
Minterm Binary Representation
m0 0000
m5 0101
m7 0111
m8 1000
m9 1001
m 1010
10
m 1011
11
m 1110
14
m 1111
15

Step 2: Arrange the minterms according to the number of 1‟s.

Minterm Binary Representation Group
m0 0000 Number of 1s zero
m8 1000 Number of 1s one
m 0101
5

m9 1001 Number of 1s two

m 1010
10

m7 0111
m 1011 Number of 1s three
11
m 1110
14
m 1111 Number of 1s four
15
Boolean Algebra and Logic Gates 1.81
Step 3: Compare each binary number with higher group.

Minterm Binary Representation

0, 8 – 0 00
8, 9 100 
–
8, 10 1 0–0 
5, 7 0 1–1
9, 11 10– 
1
10, 11 101 
–
10, 14 1 – 10
7, 15 – 1 11
11, 15 1–1 
1
14, 15 1 11–

Step 4: Further grouping is also possible.

Minterms Binary Representation
8, 9, 10, 11 10–– Both are similar
8, 10, 9, 11 10––

10, 11, 14, 15 1–1– Both are similar

10, 14, 11, 15 1–1–

Step 5: List the prime implicant.

Prime Binary Representation

Implicant
x1 x2 x3 x4
0, 8 – 0 0 0
5, 7 0 1 – 1
7, 5 – 1 1 1
8, 9, 10, 11 1 0 – –
10, 11, 14, 15 1 – 1 –
1.82 Digital Principles and System Design
Step 6: Form Prime Implicant Table

Prime Minterms
Implicant 0 5 7 8 9 10 11 14 15

 X X
0, 8
 X X
5, 7
7, 15 X X
 X X X X
8, 9, 10, 11
 X X X X
10, 11, 14, 15
   
Essential Prime

Step 7: Select the minimum number of primes that must cover all the minterms.
Here (0, 8), (5, 7), (8, 9, 10, 11) and (10, 11, 14, 15) are the essential primes and (7, 15)
is covered by the prime (5, 7) and (10, 11, 14, 15). So eliminate the prime (7, 15).

Prime Binary Representation

Implicant
x1 x2 x3 x4
0, 8 – 0 0 0 –– –– ––
 x2 x3 x4
5, 7 0 1 – 1 ––
x x
 x1 2 4
8, 9, 10, 11 1 0 – – ––
 x 1 x2
10, 11, 14, 15 1 – 1 – x1x3
–– –– –– –– ––
f (x 1 x 2 x 3 x 4) = x2 x3 x4 + x1 x 2 x 4 + x 1 x2 + x 1 x 3

Example 1.58 Simplify the logic function using Quine-McCluskey Method and
realize using NAND gates.
F(A, B, C, D) = m (1, 3, 4, 5, 9, 10, 11) + d (6, 8) (Nov/Dec 2011)
Boolean Algebra and Logic Gates 1.83

Solution:
Minterm Binary Representation

m1 0001
m3 0011
m4 0100
m5 0101
m9 1001
m 1010
10
m 1011
11

d6 0110
d8 1000

Column – 1 Column – 2
Minterm Binary Minterm Binary Representation
Representation
1 0001 1, 3 
00–1
4 0100 1, 5 0–01
8 1000 1, 9 
–001
3 0011 4, 5 010–
5 0101 4, 6 01–0
6 0110 8, 9 
100–
9 1001 8, 10 
10–0
10 1010 3, 11 
–011
11 1011 9, 11 
10–1
10, 11 
101–

Minterm Binary Representation

1, 3, 9, 11 –0–1 Both are similar
1, 9, 3, 11 –0–1

8, 9, 10, 11 10–– Both are similar

8, 10, 9, 11 10––
 1.84 Digital Principles and System Design
Prime Table

Prime Binary Representation

Implicants A B C D
1, 5 0 – 0 1
4, 5 0 1 0 –
4, 6 0 1 – 0
1, 3, 9, 11 – 0 – 1
8, 9, 10, 11 1 0 – –

Prime Implicant Table

Prime Minterms
Implicants 1 3 4 5 9 10 11
1, 5 X X
 X X
4, 5
4, 6 X
 X X X X
1, 3, 9, 11
 X X X
8, 9, 10, 11
 

Prime Binary Representation

Implicants A B C D – –
4, 5 0 1 0 – = ABC
1, 3, 9, 11 – 0 – 1 –
= BD
8, 9, 10, 11 1 0 – – –
= AB
– – – –
F(A, B, C, D) = ABC + BD + AB

Realization using NAND Gate

 – – – –
F(A, B, C, D) = ABC + BD + AB
Boolean Algebra and Logic Gates 1.85

Fig. 1.12.
Example 1.59 Simplify the given Boolean function using tabulation method.
F(A, B, C, D) = m(1, 2, 3, 5, 7, 9, 10, 11, 13, 15) (Nov/Dec 2012)

Solution:
Minterm Binary Representation
m1 0001
m2 0010
m3 0011
m5 0101
m7 0111
m9 1001
m 1010
10
m 1011
11
m 1101
13
m 1111
15

Arrange according to number of 1‟s.

Minterm Binary Representation
1 0001
2 0010
3 0011
5 0101
9 1001
10 1010
7 0111
11 1011
13 1101
15 1111
1.86 Digital Principles and System Design

Column – 1 Column – 2
Minterms Binary Minterms Binary
Representation Representation
1, 3  1, 3, 5, 7 
00–1 0––1
1, 5  1, 3, 9, 11 
0–01 –0–1
1, 9  1, 5, 3, 7 
–001 0––1
2, 3  1, 5, 9, 13 
001– ––01
2, 10  1, 9, 3, 11 
–010 –0–1
3, 7  1, 9, 5, 13 
0–11 ––01
3, 11  2, 3, 10, 11 –01–
–011
5, 7  2, 10, 3, 11 –01–
01–1
5, 13  3, 7, 11, 15 ––11
–101
9, 11  3, 11, 7, 15 ––11
10–1
9, 13  5, 7, 13, 15 
1–01 –1–1
10, 11  5, 13, 7, 15 
101– –1–1
7, 15  9, 11, 13, 15 
–111 1––1
11, 15  9, 13, 11, 15 
1–11 1––1
13, 15 
11–1

Further grouping also possible and eliminate the similar variables in the above Table.

Column – 3
Minterms Binary Representation
1, 3, 9, 11, 5, 7, 13, 15 –––1 Both are similar
1, 3, 5, 7, 9, 13, 11, 15 –––1

Prime implicant Binary Representation

2, 10, 3, 11 –01–
3, 7, 11, 15 ––11
1, 3, 9, 11, 5, 7, 13, 15 –––1
Boolean Algebra and Logic Gates 1.87
Prime Implicant Table

Prime Implicant Minterms

1 2 3 5 7 9 10 11 13 15
 X X X X
2, 10, 3, 11
3, 7, 11, 15 X X X X
 X X X X X X X X
1, 3, 9, 11, 5, 7, 13, 15
     
Essential Prime

Prime Binary Representation

Implicants A B C D –
2, 10, 3, 11 0 0 1 – = BC
1, 3, 9, 11, 5, 7, 13, 15 – – – 1 =D

Prime (3, 7, 11, 15) is eliminated because it is covered by (1, 3, 9, 11, 5, 7, 13, 15).
–
F(A, B, C, D) = BC + D
We can verify by using K-Map

Verification using K-Map

F(A, B, C, D) = m (1, 2, 3, 5, 7, 9, 10, 11, 13, 15)
 –
F(A, B, C, D) = D + BC
1.88 Digital Principles and System Design

EXERCISE PROBLEM
Minimize the following Boolean function using Tabulation Method.
(i) F(a , b , c , d ) = m (0, 1, 2, 5, 6, 7, 8, 9, 10, 14) –– – –
[Ans. b c + cd + a b d ]
(ii) F(D, C, B, A) = m (1, 3, 13, 15) + d (8, 9, 10, 11) –
[Ans. CA + DA]
SOLVED EXAMPLES
Example 1.60 Simplify the Boolean function using Quine-McClusky method.
F(A, B, C, D, E, F) = m (0, 5, 7, 8, 9, 12, 13, 23, 24, 25, 28, 29, 37, 40, 42, 44, 46, 55,
56, 57, 60, 61)

Solution:
Step 1: List all minterms in the binary form, as shown in the below Table.
Step 2: Arrange minterms according to categories of 1s column (b).
Minterms Binary Representation Minterms Binary Representation
000000 
m0 m0 000000
000101 
m5 m8 001000
000111 
m7 m5 000101
001000 
m8 m9 001001
001001 m 
m9 12 001100
m 001100 m 
12 24 011000
m 001101 m 
13 40 101000
m 010111 
23 m7 000111
m 011000 m 
24 13 001101
m 011001 m 
25 25 011001
m 011100 m 
28 28 011100
m 011101 m 
29 37 100101
m 100101 m 
37 42 101010
m 101000 m 
40 44 101100
m 101010 m 
42 56 111000
m 101100 m 
44 23 010111
m 101110 m 
46 29 011101
m 110111 m 
55 46 101110
m 111000 m 
56 57 111001
m 111001 m 
57 60 111100
m 111100 m 
60 55 110111
m 111101 m 
61 61 111101
Column (a) Column (b)
Boolean Algebra and Logic Gates 1.89

Step 3: Compared each binary number with every term in the next higher category and
if they differ by only one position, put a check mark and copy the term in the next column
„–‟ in the position that they differed.
Minterms Binary Representation Minterms Binary Representation

0, 8 0 0 – 0 00 8, 9, 12, 13 001–0–
8, 9 0 0 1 0 0–  8, 9, 24, 25 0–100–

8, 12 0 0 1 – 00  8, 12, 24, 28 
0–1–00
8, 24 0 – 1 0 00  8, 12, 40, 44 –01–00

8, 40 – 0 1 0 00  8, 24, 40, 56 ––1000


5, 7 0 0 0 1 –1 9, 13, 25, 29 
0–1–01
5, 13 0 0 – 1 01 12, 13, 28, 29 
0–110–
5, 37 – 0 0 1 01 12, 44, 28, 60 
––1100
9, 13 0 0 1 – 01  24, 25, 28, 29 011–0–


9, 25 0 – 1 0 01  24, 25, 56, 57 –1100–


12, 13 0 0 1 1 0–  24, 56, 28, 60 –11–00

12, 28 0 – 1 1 00  40, 42, 44, 46 101––0

12, 44 – 0 1 1 00  40, 56, 44, 60 1–1–00
24, 25 0 1 1 0 0– 
24, 28 0 1 1 – 00  25, 29, 57, 61 –11–01

24, 56 – 1 1 0 00  28, 29, 60, 61 –1110–

40, 42 1 0 1 0 –0  56, 57, 60, 61 111–0–

40, 44 1 0 1 – 00 
40, 56 1 – 1 0 00 
7, 23 0 – 0 1 11
13, 29 0 – 1 1 01 
25, 29 0 1 1 – 01 
25, 57 – 1 1 0 01 
28, 29 0 1 1 1 0– 
28, 60 – 1 1 1 0– 
42, 46 1 0 1 – 10 
44, 46 1 0 1 1 –0 
44, 60 1 – 1 1 00 
56, 57 1 1 1 0 0–
56, 60 1 1 1 – 00 
23, 55 – 1 0 1 11 
29, 61 – 1 1 1 01 
57, 61 1 1 1 – 01 
60, 61 1 1 1 1 0– 
 1.90 Digital Principles and System Design

Step 4: Apply the same process described in step 3 for the resultant column and
continue these cycles until a single pass through cycle yields no further elimination of literals.
Minterms Binary Representation
8, 9, 12, 13, 24, 25, 28, 29 0–1–0–
8, 12, 40, 44, 24, 28, 56, 60 ––1–00
24, 25, 28, 29, 56, 57, 60, 61 –11–0–

Step 5: List the prime implicants.

Prime Implicants Binary Representation
– – – –– 0, 8 00–000
ABDEF
––– 5, 7 0001–1
ABCDF
–– – 5, 13 00–101
ABDEF
–– – 5, 37 –00101
BCDEF
– –– 40, 42 1010–0
ABCDF
–– 7, 23 0–0111
ACDEF
– 23, 25 –10111
BCDEF
– – 40, 42, 44, 46 101––0
ABCF
–– 40, 56, 44, 60 1–1–00
ACEF
– – 8, 9, 12, 13, 24, 25, 28, 29 0–1–0–
ACE
–– 8, 12, 40, 44, 24, 28, 56, 60 ––1–00
CEF
– 24, 25, 28, 29, 56, 57, 60, 61 –11–0–
BCE
Boolean Algebra and Logic Gates 1.91
Step 6: Prime Implicant Table

Prime Implicant 0 5 7 8 9 12 13 23 24 25 28 29 37 40 42 44 46 55 56 57 60 61

0, 8

5, 7
5, 13 X X
5, 37
40, 42 X X
7, 23 X X

23,55

40, 42, 44, 46
40, 56, 44, 60 X X X X
8, 9, 12, 13, 24, 25,

28, 29
8, 12, 40, 44, 24, 28, X X X X X X X X
56, 60
24, 25, 28, 29, 56,

57, 60, 61
      

Essential Primes
 1.92 Digital Principles and System Design

Primes A B C D E F
0, 8 0 0 – 0 0 0
– – – ––
ABDEF
5, 7 0 0 0 1 – 1 –––
ABCDF
5, 37 – 0 0 1 0 1 –– –
BCDEF
23, 55 – 1 0 1 1 1 –
BCDEF
40, 42, 44, 46 1 0 1 – – 0 – –
ABCF
8, 9, 12, 13, 24, 25, 28, 29 0 – 1 – 0 – – –
ACE
24, 25, 28, 29, 56, 57, 60, 61 – 1 1 – 0 – –
BCE
––––– ––– –– – – – – – – –
F(A, B, C, D, E, F) = ABDEF + ABCDF + BCDEF + BCDEF + ABCF + ACE + BCE

EXERCISE PROBLEM

1. Simplify the function using Quine-McCluskey Method.

F(A, B, C, D, E, F) = (6, 9, 13, 18, 19, 25, 27, 29, 41, 45, 57, 61)
––– – – –– – – –
[Ans. ABCDEF + ABCDE + ABCDF + CEF]

1.8. DIGITAL LOGIC GATES

Logic gates are the basic elements that make up a digital system. Boolean functions are
expressed in terms of AND, OR and NOT operations. It is easier to implement a Boolean
function with these types of gates.
The types of gates available are the NOT, AND, OR, NAND, NOR, Exclusive-OR, and
the Exclusive-NOR, Buffer.

NOT Gate
NOT gate has only one input. If binary input is 0, then the output 1 and vice versa. It is
also called as Inverter gate (or) Complementary gate.

Logic Symbol
Boolean Algebra and Logic Gates 1.93

Truth Table
–
Input x Output x
0 1
1 0
AND Gate
AND gate has two or more inputs. The output of AND gate is high (1) only when all
inputs are high, otherwise the output is low (0). It is also called as product gate.
Logic Symbol

Truth Table
Input Output
A B Y=AB
0 0 0
0 1 0
1 0 0
1 1 1

OR Gate
The OR gate has two or more inputs. The output of OR gate is high (1) when any one
of the input is high. It is also called as sum gate.

Logic Symbol

Truth Table
Input Output
A B Y=A+B
0 0 0
0 1 1
1 0 1
1 1 1
 1.94 Digital Principles and System Design

NAND Gate
The NAND gate has two or more inputs. NAND is the combination of NOT + AND
gate. The output of NAND gate is high only when one of the inputs is low. It is also called
universal gate.

Logic Symbol

Truth Table
Input Output
A B 
Y=AB
0 0 1
0 1 1
1 0 1
1 1 0

NOR Gate
The NOR gate has two or more inputs. NOR is the combination of NOT + OR gate. The
output of NOR gate is high when all the inputs are low. It is also called universal gate.

Logic Symbol

Truth Table
Input Output

A B 
Y=A+B
0 0 1
0 1 0
1 0 0
1 1 0
Boolean Algebra and Logic Gates 1.95

Exclusive OR (EX-OR) Gate

The output is high only when odd number of inputs are high.
Truth Table and Logic Symbol
Input Output
A B Y=AB
0 0 0
0 1 1
1 0 1
1 1 0

Exclusive NOR (EX-NOR) Gate

The output is high only when even number of inputs are low (or) high.
Logic Symbol

Truth Table
Input Output
A B 
Y = A B
0 0 1
0 1 0
1 0 0
1 1 1

Buffer
The output is same as input and used to increase output driving capacity.

Logic Symbol and Truth Table

Input Output
A Y
0 0
1 1
1.96 Digital Principles and System Design

Table 1.3. Digital Logic Gates

Name Graphic Symbol Algebraic Truth Table
Function
AND F=xy
Input Output
x y F
0 0 0
0 1 0
1 0 0
1 1 1

OR F=x+y
Input Output
x y F
0 0 0
0 1 1
1 0 1
1 1 1

Inverter (or) NOT –

F=x Input Output
x F
0 1
1 0

Buffer F=x
Input Output
x F
0 0
1 1

NAND 
F=xy
Input Output
x y F
0 0 1
0 1 1
1 0 1
1 1 0
Boolean Algebra and Logic Gates 1.97

Name Graphic Symbol Algebraic Truth Table

Function
NOR –––––
Input Output
F=x+y
x y F
0 0 1
0 1 0
1 0 0
1 1 0

Exclusive-OR – –
F = xy + x y
Input Output
(XOR)
=xy x y F
0 0 0
0 1 1
1 0 1
1 1 0

Exclusive-NOR ––
Input Output
or Equivalence F=xy+xy
=x  y x y F
0 0 1
0 1 0
1 0 0
1 1 1

1.8.1. UNIVERSAL GATES

The NAND and NOR gates are known as Universal gates because using these two
gates, we can implement any logic functions.
AND, OR and NOT gates are called basic gates. When we implement logic circuit
using these gates, we require ICs for AND, OR and NOT gates. It will reduce the utility
factor because all the gates from the IC packages are not required to build the circuit and
remaining gates are unused.
Using universal gates, we can increase the utility factor more because we can use only
one logic gate to implement the entire logic circuit.
That is the reason NAND and NOR gates are called universal gate.
 1.98 Digital Principles and System Design

NAND Gate
The NAND gate can be used to implement AND, OR and NOT function. Also we can
implement NOR function.

Implement AND operation using NAND Gate

The boolean expression for AND gate is
Y = A B

Y = === =
AB (since A = A)

Truth Table
 ===
A B AB A B AB AB
0 0 0 0 0 1 0
0 1 0 = 0 1 1 0
1 0 0 0 0 1 0
1 1 1 1 1 0 1

Implement OR operation using NAND Gate

The boolean expression for OR gate is
Y = = = =
A+B = A+B (A = A)
= ––––– (using DeMorgan‟s Theorem 1)
AB
Boolean Algebra and Logic Gates 1.99

Truth Table
– – – – – –
A B A+B A B A B A B A B
0 0 0 0 0 1 1 1 0
0 1 1 = 0 1 1 0 0 1
1 0 1 1 0 0 1 0 1
1 1 1 1 1 0 0 0 1
Implement NOT Operation using NAND Gate
An inverter can be made from a NAND gate by connecting all the inputs together and
creating, in effect, a single common input.


A B AB
X=0 0 0 1 Y=1
0 1 1
1 0 1
X=1 1 1 0 Y=0
Implement NOR Operation using NAND Gate
Boolean expression for NOR gate is
Y = 
A+B
– –
Y = AB
Y = ––––– (using DeMorgan‟s theorem 2)
AB
 1.100 Digital Principles and System Design

The above equation is implemented using only NAND gates.

Truth Table
 – – –– –––––
– –
––––– 
– –

A B A+B A+B A B AB A B AB A B A B = A + B


0 0 0 1 0 0 0 1 1 1 0 1
0 1 1 0 = 0 1 0 1 0 0 1 0
1 0 1 0 1 0 0 0 1 0 1 0
1 1 1 0 1 1 1 0 0 0 1 0

NOR Gate
Similar to NAND gate, the NOR gate is also a universal gate, it can be used to generate
the NOT, AND, OR and NAND functions.

Implement NOT Function using NOR Gate

An inverter can be made from a NOR gate by connecting all of the inputs together and
creating, in effect, a single common input.

 ––––– –
Y=A+B =X+X =X

A B A+B
X=0 0 0 1 Y=1
0 1 0
1 0 0
X=1 1 1 0 Y=0
Boolean Algebra and Logic Gates 1.101

Implement OR Function using NOR Gate

An OR function can be generated using only NOR gates. It can be generated by
inverting output of NOR gate. i.e.,
=====
A+B = A+B

 =====
A B A+B A B A+B A+B A+B
0 0 0 0 0 0 1 0
0 1 1 = 0 1 1 0 1
1 0 1 1 0 1 0 1
1 1 1 1 1 1 0 1

Implement AND Function using NOR Gate

The Boolean expression for AND gate is
Y = AB
Y = = = –
A B [A = A]

Y = ––––– [using DeMorgan‟s Theorem 2]
A+B
The above equation is implemented using only NOR gate as follows.
 1.102 Digital Principles and System Design

Truth Table
– – – – – –
A B AB A B A B A+B A+B
0 0 0 0 0 1 1 1 0
0 1 0 = 0 1 1 0 1 0
1 0 0 1 0 0 1 1 0
1 1 1 1 1 0 0 0 1
Implement NAND Function using NOR Gate
The Boolean expression for NAND gate is

Y = AB
– –
Y = A+B [DeMorgan‟s theorem 1]
=====
– –
=
Y = A+B [A = A]
The above equation is implemented using only NOR gates.
  – – – – – – – –
A B A B
A B A B A+B A+B A+B

0 0 1 0 0 1 1 1 0 1
0 1 1 = 0 1 1 0 1 0 1
1 0 1 1 0 0 1 1 0 1
1 1 0 1 1 0 0 0 1 0
Boolean Algebra and Logic Gates 1.103

1.9. IMPLEMENTATION OF LOGIC FUNCTIONS USING GATES

The Boolean algebra is used to express the output of any combinational network. Such
network can be implemented using logic gates.

Guidelines to draw the Logic Diagram for given Expression using Gates
(i) Identify the minterms and maxterms from the expression.
(ii) Identify the complement variables.
(iii) Draw the logic gates for each minterm and maxterms in the expression.
(iv) Simplify the input variable if it is used more one and as complementary function.

SOLVED EXAMPLES

Example 1.61 Draw the logic circuit using gates for the given function
– – –
F = AB + CD + BC

Solution:
 Given function is the SOP expression. In that we have three product terms with 2
literals in each product term.
 To draw the logic circuit, we need three AND gate as input and one OR gate as
output it contains three input.

– – –
Example 1.62 Draw the logic circuit for the function F = AB + BC + CDE.

Solution:

Given function is the SOP expression. In that we have three product terms.
1.104 Digital Principles and System Design

 We need three AND gate as input and one OR gate as output.

 Two AND gate has two input lines and one AND gate has three input lines.

Example 1.63 Draw the logic circuit using basic gates for the function
–
F = (A + B) (A + B) (C + D)

Solution:
 Given function is the POS expression. In that we have three sum terms.

 We need three OR gate as input and each gate contains two literals and one AND
gate as output.

Example 1.64 Draw the logic circuit using basic gates for the function
– –
F = (A + B) (B + C) (C + D + E)

Solution:
 Given function is a POS expression. We have three sum terms with 2 literals in two
terms and 3 literals in one term.
Boolean Algebra and Logic Gates 1.105


We need three OR gate and one AND gate.

1.9.1. NAND-NAND IMPLEMENTATION

 The implementation of a Boolean function with NAND-NAND logic requires that
the function to be simplified in the sum of product form.
 Lets consider SOP form (AND-OR logic) and how it will be represented in NAND-
NAND logic.
Consider the Boolean function Y = ABC + CD + E

AND-OR Logic Gate

NAND-NAND Implementation
 1.106 Digital Principles and System Design

Procedure for obtaining NAND-NAND Logic Diagram

1. Simplify the given Boolean function and express it in sum of product form (SOP
form).
2. Draw a NAND gate for each product term of the function.
3. If Boolean function includes any single literal or literals draw NAND gate for each
single literal.
4. Draw a single NAND gate in the second level, with inputs coming from outputs of
first level gates.

SOLVED EXAMPLES
Example 1.65 Implement the following Boolean function with NAND-NAND logi c
– –
F = AB + ABC + ABC + AB + D (using only NAND gates).

Solution:
Step 1: Simplify the given Boolean function to get minimum number of literals.
F = – –
AB + ABC + ABC + AB + D
= – – –
AB + BC (A + A) + AB + D [A + A = 1]
= – –
A (B + B) + BC (A + A) + D
F = A + BC + D
Step 2: Draw the AND-OR logic gate

Step 3: Convert AND-OR logic to NAND-NAND logic

Boolean Algebra and Logic Gates 1.107

Example 1.66 Implement the following Boolean function with NAND-NAND logi c F
= (A, B, C) = m (0, 1, 3, 5, 6, 7) (using only NAND gates).

Solution:
Step 1: Simplify the given Boolean function.

–– ––
F = C + AB + AB = AB + AB + C
Step 2: Implement Boolean function with AND-OR logic.

Step 3: Convert AND-OR logic to NAND-NAND logic.

1.9.2. NOR-NOR IMPLEMENTATION

 The implementation of a Boolean function with NOR-NOR logic requires that the
function to be simplified in the product of sum (POS) form.
 1.108 Digital Principles and System Design

 Lets consider POS form (OR-AND logic) and how it will be represented in NOR-
NOR logic.
Consider the Boolean function Y = (A + B + C) (D + E) F

OR-AND Logic Gate

NOR-NOR Implementation

Procedure for obtaining NOR-NOR Logic Diagram

1. Simplify the given Boolean function and express it in POS form.
2. Draw a NOR gate for each sum term of the function.
3. If Boolean function includes any single literal, draw NOR gate for each single
literal.
4. Draw a single NOR gate in the second level, with inputs coming from outputs of
first level gates.

SOLVED EXAMPLES

Example 1.67 Implement the following Boolean function with only NOR gates.
Y = AC + BC + AB + D

Solution:
Step 1: Here the given function is in SOP format. So first we convert it into POS form,
using duality theorem, we get
Boolean Algebra and Logic Gates 1.109
Y = AC + BC + AB + D
– – – – – – – –
Y = (A + C) (B + C) (A + B) D
Step 2: Implement Boolean function with OR-AND logic.

– – – – – – – –
Y = (A + C) (B + C) (A + B) D
Step 3: Convert OR-AND logic to NOR-NOR logic.

– ––––––––––––––––––––––––––––
––––– ––––– ––––– =
Y = (A + C) + (B + C) + (A + B) + D
= –––––––––––––––––––––––
– – – – – – –
Y = (A + C) (B + C) (A + B) D
Y = AC + BC + AB + D

Example 1.68 Implement the following Boolean function with NOR-NOR logi c
–
(using only NOR gates) F = (A + B) C.
 1.110 Digital Principles and System Design


Solution:
Step 1: Implement Boolean function with OR-AND logic.

Step 2: Convert OR-AND logic to NOR-NOR logic.

Example 1.69 Simplify and implement the following POS function using NOR gates
f(A, B, C, D) = П M (0, 1, 2, 3, 12, 13, 14, 15).

Solution:
Step 1: Simplify the given Boolean function.
 – –
f (A, B, C, D) = (A + B) (A + B)
Boolean Algebra and Logic Gates 1.111

Step 2: Implement Boolean function with OR-AND logic.

Step 3: Convert OR-AND logic to NOR-NOR logic.

Example 1.70 Simplify and implement the following SOP function using NOR
gates.
f(A, B, C, D) = m (0, 1, 4, 5, 10, 11, 14, 15)

Solution:
Step 1: Given function is SOP, so convert into its equivalent POS function.
 m (0, 1, 4, 5, 10, 11, 14, 15) = П M (2, 3, 6, 7, 8, 9, 12, 13)
Step 2: Simplify the given Boolean function using K-Map simplification.
 – –
f (A, B, C, D) = (A + C) (A + C)
 1.112 Digital Principles and System Design

Step 3: Implement Boolean function with OR-AND logic.

Step 4: Convert OR-AND logic to NOR-NOR logic.

EXERCISE PROBLEMS
– –
1. Implement the following Boolean function using only NAND gates F = AB + AB.
2. Implement the following Boolean function using only NAND gates.
–
Y = AC + ABC + ABC + AB + D
3. Implement the following Boolean function with NAND-NAND logic
–– – –
F = AB + AC + BC
4. Implement the following expression using logic gates.
f (A, B, C, D) = m (0, 8, 11, 12, 15) + d (1, 2, 4, 7, 10, 14)
5. Implement the following Boolean function with NOR-NOR logic.
F(x , y , z ) = П M (0, 1, 2, 3, 6, 7, 8, 10, 11)
6. Implement the following Boolean function with only NOR gates
–
f (A, B, C) = A (B + C)
–– –
7. Given the Boolean function: F = x y + x y + y z
(a) Implement it with AND, OR and NOT gates.
(b) Implement it with only OR and NOT gates.
(c) Implement it with only AND and NOT gates.
Boolean Algebra and Logic Gates 1.113

1.10. MULTILEVEL GATE IMPLEMENTATIONS

Logic gates can be cascaded to get the desired output. The maximum number of gates
cascaded in series between a network input and the output is referred to as number of
levels of gates.
 In SOP form or POS form having two level gate networks and usually it is assumed
that all variables and their complements are available as network inputs.

1.10.1. TWO LEVEL GATE NETWORK

– ––
1. F = ACD + BCD. Draw the two-level network for this Boolean expression.

Fig. 1.13. Two Level AND-OR Network

–
2. F = (C + D) (A + B + C) (A + D). Draw the two-level network for this Boolean
expression.
Fig. 1.14. Two Level OR-AND Network
1.114 Digital Principles and System Design

1.10.2. THREE LEVEL GATE NETWORK

––––
1. F = (C + AD + BD) (B + AD + CD). Draw the three level network for this Boolean
expression.

Fig. 1.15. Three Level AND-OR-AND Network

2. F = (A + B) (C + D) + (C + D). Draw the three level network for this Boolean
expression.

Fig. 1.16. Three Level OR-AND-OR Network

1.10.3. FOUR LEVEL GATE NETWORK

1. Four level gate network for Boolean expression F
= (AB + C) [(D + E) + (FG)] + H is
Boolean Algebra and Logic Gates 1.115

Fig. 1.17. Four Level Gate Network

2. Four level gate network for Boolean function
– –
F = [(A + B) (C + D) + (D + E)]  B

Fig. 1.18.

1.11. MULTI-OUTPUT GATE IMPLEMENTATIONS

In digital circuits, many times multiple outputs are derived from the same input
variables. Each output function can be separately simplified by the use of K-Map or Quine
McCluskey method. It is possible that the simplified output functions may have common
terms. The common term used by one output function can be shared by other functions.
This sharing of common terms reduces the total number of gates.
 1.116 Digital Principles and System Design

Example 1.71 Simplify the following functions and draw the logic diagram.
F1 = f(A, B, C) =  (1, 2, 3, 5)
F = f(A, B, C) =  (1, 3, 5, 7)
2
F3 = f(A, B, C) =  (2, 3, 4, 5)

Solution: First simplified the output functions using K-Map to get the Boolean
expression.

Fig. 1.19. Four product terms are required Fig. 1.20. Three product terms are required
–
when each function is treated separately
when common term AB is shared

Example 1.72 Draw the multi-output gate network for the Boolean expression
 – – – –
F1 = AB + AB, F2 = BC + AB
Boolean Algebra and Logic Gates 1.117
 – – – –
Solution: Given: F1 = AB + AB; F2 = BC + AB
–
In that two functions we have four product terms and one product term (AB) is shared
between two functions.

Fig. 1.21. Four product terms are required Fig. 1.22. Three product terms are required
–
when two function is treated separately when common term AB is shared
SOLVED UNIVERSITY PROBLEMS

Example 1.73 Find a minimal sum of product representation for f(A, B, C, D, E) =

m(1, 4, 6, 10, 20, 22, 24, 26) + d(0, 11, 16, 27) using K-Map method. Draw the circuit of
the minimal expression using only NAND gates. (May/June 03)

Solution: The given function has 5 variables. So K-Map for 5-variable is shown below.
 – – – – – –– ––
f (A, B, C, D, E) = ABCD + BCE + BCD + ABCE
1.118 Digital Principles and System Design

Sum of product can be implemented using NAND-NAND logic as shown below.

Example 1.74 Obtain 3-Level NOR-NOR implementation of

f(a, b, c, d, e, f) = [ab + cd] ef (Nov/Dec 04)
 f (a , b , c , d , e , f ) = [ab + cd] ef = abef + cdef
Solution:
= =========== =
abef + cdef [ A = A]
–––––––––– ––––––––––––––––––––––––––
– – – – – – – –
= abef  cdef = (a + b + e + f ) (c +d+e+f)
OR-AND function can be implemented using NOR-NOR logic.
Boolean Algebra and Logic Gates 1.119

Example 1.75 Minimize the following function using K-Map. Implement the
resultant function using NOR gates only. (May/June 05)
F(A, B, C, D, E) = П M (2, 4, 7, 9, 26, 28, 29, 31)

Solution:

– – – – –
F(A, B, C, D, E) = (A + B + C + D + E) (A + B + C + D + E) (A + B + C + D + E)
– – – – – – – – – – – –
(A + B + C + D + E) (A + B + C + D) (A + B + C + E) (A + B + C + D +
E) OR-AND implementation can be replaced by NOR-NOR implementation.

Logic diagram using NOR gates

1.120 Digital Principles and System Design

Example 1.76 Implement the following function using a quad 2-input NOR gates.
– – (Nov/Dec 2005)
f = (AB + C) D
 f = – –
Solution: (AB + C) D
===========
– –
f = (AB + C) D
= ––––––––––––––=
(AB + C) + D
= –––––––––––––
(AB + C) + D
–––––––––––––––– – –
====
= (A + B) + C + D [AB = AB ]

Example 1.77 Implement the expression:

(1) AB + BCD + EFGH
(2) (A + B) (C + D + E) (F + G + H + I) with logic gates. (Nov/Dec 2006)
 Solution:
Boolean Algebra and Logic Gates 1.121

Example 1.78 Write the Boolean expression for the output of the system shown i n
below Fig. (May/June 07)

 C =  – –
Solution: (A + B) B = A  B  B

C =0
–
Example 1.79 Draw the logic diagram for X = AB + BC. (Nov/Dec 07)
 X = –
Solution: AB + BC

– – –
Example 1.80 Implement F = (AB + AB) (C + D) with only NOR gates. (Nov/Dec 07)
 – – – – –– – – –
Solution: F = (AB + AB) (C + D) = ABC + ABD + ABC + ABD
=
========================== ––––––––––––––––––––––––––
–––––
=====
––––– –––––
– –– – – – –

F = ABC + ABD + ABC + ABD = ABC  ABD  ABC  ABD

–––––––––––––––––––––––––––––––––––––––––––––
– – – – – –

= (A + B + C)  (A + B + D) (A + B + C)  (A + B + D)
1.122 Digital Principles and System Design

Example 1.81 Implement the Boolean expression using gates.

–––––––
X = (AB + C) D + E (Nov/Dec 07)
–––––––  –
 X = (AB + C) D + E = (AB  C) D + E
Solution:
–––
X = ABCD+E

Example 1.82 Sketch a NAND-NAND logic circuit for the Boolean expression.
Y – (Nov/Dec 07)
= AB + AC + BD
 Y –
Solution: = AB + AC + BD
Given function is a SOP form, so we can implement NAND-NAND logic directly.

Example 1.83 Simplify the given Boolean function into:

(i) Sum of products form
(ii) Product of sum form and implement if using basic gates.
F(A, B, C, D) =  (0, 1, 2, 5, 8, 9, 10) (May/June 13)

Solution:
(i) SOP form
Given function F(A, B, C, D) =  (0, 1, 2, 5, 8, 9, 10)
It is a SOP form, so we can simplify it directly using K-Map. Then we get
Boolean Algebra and Logic Gates 1.123

–
[In SOP, 0 = A, 1 = A]

–– –– ––
F = BD + ACD + ABC
Implementation of SOP using Basic Gates:

F = –– –– ––
BD + ACD + ABC
(ii) POS Form: F(A, B, C, D) = П (3, 4, 6, 7, 11, 12, 13, 14, 15)
 –
[In POS, 0 = A, 1 = A]
– – – – – – –
F(A, B, C, D) = (C + D) (A + B) (B + C + D) (B + C)
1.124 Digital Principles and System Design

Implementation of POS using Basic Gates:

Example 1.84 Implement the given function using NAND gates

F(x, y, z) = m (0, 6) (Nov/Dec 12)

Solution: Given function F(x , y , z ) = m (0, 6) is a SOP form. Simplify it using K-Map.

––– –
F(x , y z ) = x y z + x y z
SOP format can be implemented directly using NAND gates.
––– –
F(x , y z ) = x y z + x y z
Boolean Algebra and Logic Gates 1.125

TWO MARKS QUESTIONS AND ANSWERS

1. State Distributive Law. (Nov/Dec 13)
If „+‟ and „‟ are the two binary operators on a set x , then „+‟ is said to be
distributive over „‟ whenever A  (B + C) = A  B + A 
C
2. What is prime implicant? (Nov/Dec 13)
A prime implicant is a product term obtained by combining the maximum possible
number of adjacent squares in the map. They cannot be reduced further.
3. Map the standard SOP expression on a Karnaugh Map. (Nov/Dec 11)
 – – –
ABC + ABC + ABC + ABC
Given:  – – –
ABC + ABC + ABC + ABC
Structure of K-map for three variable.

Map the given value in the Table

4. Draw the logic diagram of OR gate using universal gates. (Nov/Dec 11)
 1.126 Digital Principles and System Design

5. State DeMorgan’s theorem.(May/June 09, 13, Apr/May 11, 05, Nov/Dec 06)
DeMorgan suggested two theorems that form an important part of Boolean algebra. They
are:
Theorem 1:  – –
AB = A+B
Theorem 2:  – –
A+B = A B
6. What are don’t care terms? (May/June 13)
I0 represent the don‟t care conditions. Two terms are used as don‟t care terms such
as „X‟ or „d ‟.
7. Simplify the given Boolean expression F = x′ + x y + xz′ + xy′z′. (Nov/Dec 12)
F = x ′ + x y + x z′ + xy ′z ′
– – ––
F = x + x y + xz + x y z
– – –– –
= x + y + xz + xy z [ A + AB = A + B]
– – [ A + AB = A]
= x + y + xz
–– – – –
F = x + xz + y = x + z + y [ A + AB = A + B]
8. Implement the given function using NAND gates F(x, y, z) = m (0, 6). (Nov/Dec 12)
Given function F(x , y , z ) = m (0, 6) is a SOP. Simplify it using K-Map
 ––– –
F(x , y , z ) = x y z + x y z
Boolean Algebra and Logic Gates 1.127
9. What is Totem output? (Apr/May 2011)
In totem pole output configuration, transistor Q 3 and Q4 from a totem pole is
called as active pull-up or totem pole output. The totem output formed by Q 3 and Q4
has specific advantage.

10. If A and B are Boolean variables and if A = 1 and A + B = 0, then find B.
(Nov/Dec 03)
Given: A= 1 
and A + B = 0
A+B = 1
1+B = 1
B = 1–1
B = 0 therefore B can be either 0 or 1.
11. Express the switching function f(BA) = A in terms of minterms. (Nov/Dec 03)
Given: f (BA) = A
– –
= A (B + B) ( A + A = 1)
f (BA) = –
AB + AB
12. Plot the expression on K-Map: F(w, x, y) =  (0, 1, 3, 5, 6) + d(2, 4) (May/June 04)

–––––– (May/June 04)

13. Apply DeMorgan’s theorem to simplify A + BC .
–––––––
Given: A + BC
––––––– – –––– – –– –
A + BC = A  BC = A  (B + C) = AB + AC
– (May/June 05)
14. Simplify: A + AB + A + B
– –
A + AB + A + B = A (1 + B) + A + B
= –
A+A+B
= 1+B
=1
1.128 Digital Principles and System Design
15. Prove that A + A′B = A + B, using Boolean algebra. (Nov/Dec 05)
Given: A + A′ B = A+B
– = – [By theorem 4(a) A + AB = A]
A + AB A + AB + AB
= – [By postulates]
A + B  (A + A)
= A+B1 –
[By postulates A + A = 1]
= A+B [B  1 = B]
16. Define maxterms and minterms. (May/June 05)
– –
Variable A, A, B and B. If these variables are combined with an AND operation,
–– – –
there are four possible combinations AB, AB, AB, AB. Each of these four AND terms
are called minterm or a standard product.
In similar to minterms, if the variables are combined with an „OR‟ operation, there
– – – –
are four possible combinations A + B, A + B, A + B, A + B. Each of these four OR
terms are called a maxterm or a standard sum.
17. Mention any two applications of DeMorgan’s theorem. (May/June 2007)
 It is used to convert SOP expression into POS expression and vice versa.
 It is used to simplify the Boolean expressions.

18. Express F = A + B′C as sum of minterms. (Nov/Dec 07)

– – – –
A + B′C = A (B + B) (C + C) + (A + A) B C
– – – ––
= (AB + AB) (C + C) + ABC + ABC
– – –– – ––
= ABC + ABC + ABC + ABC + ABC + ABC
––– – – –
= ABC + ABC + ABC + ABC + ABC
= m (1, 4, 5, 6, 7)
19. Find the complement of A + BC + AB. (Nov/Dec 08)
F = ––––––––––––
A + BC + AB
= ––––––––––––
A + AB + BC
= –––––––
A + BC
– 
= A  BC
= – – –– – ––
A  (B + C) = AB + AC
Boolean Algebra and Logic Gates 1.129
20. –––––––––––– (Nov/Dec 08)
Apply DeMorgan’s theorem for the function (A + B + C) D .
–––––––––––– –––––––––– –
(A + B + C) D = (A + B + C) + D
– – – –
= A B  C + D
– –– –
= ABC+D
21. What are universal gates? (Nov/Dec 04)

NAND and NOR gates are called as universal gates because using these two gates
we can implement any logic functions.
AND, OR and NOT gates are called basic gates.
22. List the number systems.
1. Binary number system
2. Octal number system
3. Decimal number system
4. Hexadecimal number system
23. Define Boolean algebra.
Boolean algebra may be defined with a set of elements, a set of operations, and a
number of unproved postulates.
Boolean algebra may also be referred as an algebraic structure defined by a set of
element. A set of elements is a collection of objects which is two or more binary
numbers, together with two binary operator „+‟ and „‟ (dot).
24. What are the laws of Boolean algebra?
1. Commutative laws
2. Associative laws
3. Distributive law
25. Define Duality Theorem.
The principle of duality theorem states that every algebraic expression from the
postulates of Boolean algebra remain valid if the operators and identity elements are
interchanged.
If we apply dual principle for an algebraic expression simply interchange OR and
AND operators and replace 1‟s by 0‟s and vice versa.
 1.130 Digital Principles and System Design
26. Define consensus theorem.
–
In simplification of Boolean expression, an expression of the form AB + AC + BC,
–
the term BC is redundant and can be eliminated to form the equivalent AB + AC. The
theorem used for this simplification is known as consensus theorem and it is stated as
– –
AB + AC + BC = AB + AC
27. Define sum of product terms (SOP).
Sum of product term is also called as sum of minterms. That means if two or more
minterms are combined with an OR logic is said to be a sum of product (SOP).
28. Define product of sum terms (POS).
Product of sum terms is also called as product of max terms. That means if two or
more maxterms are combined with an AND logic is said to be product of sum (POS).
29. What is meant by Karnaugh map or K-Map method?
A K-Map is a diagram made up of squares with each square representing one
minterm of the function that is to be minimized. The simplified expressions produced
by the map are always in one of the two standard forms. Sum of products (SOP) or
product of sum (POS).
30. What are called don’t care conditions?
In some logic circuits certain input conditions never occur, therefore the
corresponding output never appears. In such cases, the output level is not defined, it
can be either high or low. These output levels are indicated by „X‟ or „ d ‟ in the truth
tables and are called don‟t care conditions or incompletely specified functions.
31. What is tabulation method?
A method involving an exhaustive tabular search method for the minimum
expression to solve a Boolean equation for more variables is called as a tabulation
method.
32. State two advantages of CMOS logic. (Nov/Dec 03)
 Consumes less power.
 Can be operated at high voltages, resulting in improved noise immunity.

33. Define noise margin. (Nov/Dec 03)

It is the maximum external noise voltage added to an input signal that does not
cause an undesirable change in the circuit output.
Boolean Algebra and Logic Gates 1.131
34. Determine the fan-out given I (May/June 04)
IH(max) = 40 A and IOH(max) = 400A.
I 400 A
OH(ma x)

fan-out = = = 10
IIH(ma x) 40 A
35. What is the advantage of Schottky TTL Family? (Nov/Dec 04)
The advantage of Schottky TTL family is fast switching speed.
36. What are tri-state gates? (May/June 05)

The tri-state configuration is a third type of TTL output configuration. It utilizes

the high speed operation of the totem-pole arrangement while permitting outputs to be
wired-AND. It is called tri-state TTL because it allows three possible output stages:
HIGH, LOW and High impedance.

REVIEW QUESTIONS – PART B

1. Write short notes on Boolean postulates and laws.

2. Simplify the Boolean functions.
(i) – (ii) – ––
x y + xy (a + b + c ) (a b + c )
(iii) –– – – (iv) –
(x + y) (x + y ) x y + x (w z + wz )
(v) – – – – (vi) ––
(a + c ) (a + b + c ) ABCD + ABD + ABCD
3. Write short notes on don‟t care conditions.
4. Minimize the Boolean function using K-Map.
(i) f (A, B, C, D, E) = П M (2, 4, 7, 9, 26, 28, 29, 31)
(ii) f (A, B, C, D, E) = П M (1, 4, 6, 10, 20, 22, 24, 26) + d (0, 11, 16, 27)

5. Explain the Quine-McClusky method of minimization with example.

6. Explain about the digital logic gates.
7. Explain about NAND and NOR implementation.
