Page 1

UNIT-II
NUMBER SYSTEMS & BOOLEAN ALGEBRA
Number Systems:
In a digital system, the system can understand only the optional number system. In these systems,
digits symbols are used to represent different values, depending on the index from which it settled
in the number system. In simple terms, for representing the information, we use the number system
in the digital system.
Types of Number System:
In the digital computer, there are various types of number systems used for representing
information.
1. Binary Number System
2. Decimal Number System
3. Hexadecimal Number System
4. Octal Number System
Decimal Number System:
The number system that we use in our day-to-day life is the decimal number system. The decimal
number system has a base of 10 because it uses ten digits from 0 to 9. In the decimal number
system, the positions successive to the left of the decimal point represent units, tens, hundreds,
thousands and so on. This system is expressed in decimal numbers. Every position shows a
particular power of the base (10).
Example:
The decimal number 1457 consists of the digit 7 in the unit’s position, 5 in the tens place, 4 in the
hundreds position, and 1 in the thousands place whose value can be written as:
(1×103) + (4×102) + (5×101) + (7×100)
(1×1000) + (4×100) + (5×10) + (7×1)
1000 + 400 + 50 + 7
1457
Binary Number System:
Generally, a binary number system is used in the digital computers. In this number system, it
carries only two digits, either 0 or 1. There are two types of electronic pulses present in a binary
number system. The first one is the absence of an electronic pulse representing '0' and second one
is the presence of electronic pulse representing '1'. Each digit is known as a bit. A four-bit
collection (1101) is known as a nibble, and a collection of eight bits (11001010) is known as a
byte. The location of a digit in a binary number represents a specific power of the base (2) of the
number system.
Characteristics:
1. It holds only two values, i.e., either 0 or 1.
2. It is also known as the base 2 number system.
3. The position of a digit represents the 0 power of the base (2). Example: 20
Modeling of Digital Circuits by D. O. Sakle
 Page 2

4. The position of the last digit represents the x power of the base (2). Example: 2x, where x
represents the last position, i.e., 1
Examples:
(10100)2, (11011)2, (11001)2, (000101)2, (011010)2.

Octal Number System:

The octal number system has base 8(means it has only eight digits from 0 to 7). There are only
eight possible digit values to represent a number. With the help of only three bits, an octal number
is represented. Each set of bits has a distinct value between 0 and 7.
Below, we have described certain characteristics of the octal number system:
Characteristics:
1. An octal number system carries eight digits starting from 0, 1, 2, 3, 4, 5, 6, and 7.
2. It is also known as the base 8 number system.
3. The position of a digit represents the 0 power of the base(8). Example: 80
4. The position of the last digit represents the x power of the base(8). Example: 8x, where x
represents the last position, i.e., 1

Hexadecimal Number System:

It is another technique to represent the number in the digital system called the hexadecimal number
system. The number system has a base of 16 means there are total 16 symbols (0, 1, 2, 3, 4, 5, 6,
7, 8, 9, A, B, C, D, E, F) used for representing a number. The single-bit representation of decimal
values10, 11, 12, 13, 14, and 15 are represented by A, B, C, D, E, and F. Only 4 bits are required
for representing a number in a hexadecimal number. Each set of bits has a distinct value between
0 and 15. There are the following characteristics of the octal number system:
Characteristics:
1. It has ten digits from 0 to 9 and 6 letters from A to F.
2. The letters from A to F defines numbers from 10 to 15.
3. It is also known as the base 16number system.
4. In hexadecimal number, the position of a digit represents the 0 power of the base(16).
Example: 160
5. In hexadecimal number, the position of the last digit represents the x power of the base(16).
Example: 16x, where x represents the last position, i.e., 1

Hexadecimal 0 1 2 3 4 5 6 7 8 9 A B C D E F
Decimal 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Conversion:
Binary, Octal and Hexadecimal to Decimal number system:
Binary to Decimal Conversion
The process of converting binary to decimal is quite simple. The process starts from multiplying
the bits of binary number with its corresponding positional weights. And lastly, we add all those
products.
Let's take an example to understand how the conversion is done from binary to decimal.
Example: (10110.001)2
We multiplied each bit of (10110.001)2 with its respective positional weight, and last we add the
products of all the bits with its weight.
Modeling of Digital Circuits by D. O. Sakle
 Page 3

(10110.001)2 = (1×24)+(0×23)+(1×22)+(1×21)+(0×20)+(0×2-1)+(0×2-2)+(1×2-3)
(10110.001)2 = (1×16)+(0×8)+(1×4)+(1×2)+(0×1)+(0×1⁄2)+(0×1⁄4)+(1×1⁄8)
(10110.001)2 = 16+0+4+2+0+0+0+0.125
(10110.001)2 = (22.125 )10

Octal to Decimal Conversion

The process of converting octal to decimal is the same as binary to decimal. The process starts
from multiplying the digits of octal numbers with its corresponding positional weights. And lastly,
we add all those products.
Let's take an example to understand how the conversion is done from octal to decimal.
Example: (152.25)8
Step 1:
We multiply each digit of 152.25 with its respective positional weight, and last we add the products
of all the bits with its weight.
(152.25)8 = (1×82)+(5×81)+(2×80)+(2×8-1)+(5×8-2)
(152.25)8 = 64+40+2+(2×1⁄8)+(5×1⁄64)
(152.25)8 = 64+40+2+0.25+0.078125
(152.25)8 = 106.328125
So, the decimal number of the octal number (152.25)8 is (106.328125)10

Hexa-decimal to Decimal Conversion

The process of converting hexadecimal to decimal is the same as binary to decimal. The process
starts from multiplying the digits of hexadecimal numbers with its corresponding positional
weights. And lastly, we add all those products.
Let's take an example to understand how the conversion is done from hexadecimal to decimal.
Example: (152A.25)16
Step 1:
We multiply each digit of 152A.25 with its respective positional weight, and last we add the
products of all the bits with its weight.
(152A.25)16 = (1×163)+(5×162)+(2×161)+(A×160)+(2×16-1)+(5×16-2)
(152A.25)16 = (1×4096)+(5×256)+(2×16)+(10×1)+(2×16-1)+(5×16-2)
(152A.25)16 = 4096+1280+32+10+(2×1⁄16)+(5×1⁄256)
(152A.25)16 = 5418+0.125+0.125
(152A.25)16 = 5418.14453125
So, the decimal number of the hexadecimal number (152A.25)16 is (5418.14453125)10

Decimal to other Number System

The decimal number can be an integer or floating-point integer. When the decimal number is a
floating-point integer, then we convert both part (integer and fractional) of the decimal number in
the isolated form(individually). There are the following steps that are used to convert the decimal
number into a similar number of any base 'r'.
Step 1: In the first step, we perform the division operation on integer and successive part with
base 'r'. We will list down all the remainders till the quotient is zero. Then we find out
the remainders in reverse order for getting the integer part of the equivalent number of
base 'r'. In this, the least and most significant digits are denoted by the first and the last
remainders.
Modeling of Digital Circuits by D. O. Sakle
 Page 4

Step 2: In the next step, the multiplication operation is done with base 'r' of the fractional and
successive fraction. The carries are noted until the result is zero or when the required
number of the equivalent digit is obtained. For getting the fractional part of the
equivalent number of base 'r', the normal sequence of carrying is considered.

Decimal to Binary Conversion

For converting decimal to binary, there are two steps required to perform, which are as follows:
Step 1: In the first step, we perform the division operation on the integer and the successive
quotient with the base of binary (2).
Step 2: Next, we perform the multiplication on the integer and the successive quotient with the
base of binary (2).

Example: (152.25)10
Step 1:
Divide the number 152 and its successive quotients with base 2.
Operation Quotient Remainder
152/2 76 0 (LSB)
76/2 38 0
38/2 19 0
19/2 9 1
9/2 4 1
4/2 2 0
2/2 1 0
1/2 0 1(MSB)
(152)10 = (10011000)2
Step 2:
Now, perform the multiplication of 0.27 and successive fraction with base 2.
Operation Result carry
0.25×2 0.50 0
0.50×2 0 1
(0.25)10 = (.01)2
(152.25)10 = (10011000.01)2

Decimal to Octal Conversion

For converting decimal to octal, there are two steps required to perform, which are as follows:
Step 1: In the first step, we perform the division operation on the integer and the successive
quotient with the base of octal (8).
Step 2: Next, we perform the multiplication on the integer and the successive quotient with the
base of octal (8).
Example 1: (152.25)10
Step 1:
Divide the number 152 and its successive quotients with base 8.
Operation Quotient Remainder
152/8 19 0
19/8 2 3

Modeling of Digital Circuits by D. O. Sakle

 Page 5

2/8 0 2
(152)10 = (230)8
Step 2:
Now perform the multiplication of 0.25 and successive fraction with base 8.
Operation Result carry
0.25×8 0 2
(0.25)10 = (2)8
(152.25)10 = (230.2)8

Decimal to hexadecimal conversion

For converting decimal to hexadecimal, there are two steps required to perform, which are as
follows:
Step 1: In the first step, we perform the division operation on the integer and the successive
quotient with the base of hexadecimal (16).
Step 2: Next, we perform the multiplication on the integer and the successive quotient with the
base of hexadecimal (16).
Example: (152.25)10
Step 1:
Divide the number 152 and its successive quotients with base 8.

Operation Quotient Remainder

152/16 9 8
9/16 0 9

(152)10 = (98)16
Step 2:
Now perform the multiplication of 0.25 and successive fraction with base 16.
Operation Result carry
0.25×16 0 4

(0.25)10 = (4)16
So, the hexadecimal number of the decimal number (152.25)10 is (230.4)16.

Binary to Octal Conversion

The base numbers of binary and octal are 2 and 8, respectively. In a binary number, the pair of
three bits is equal to one octal digit. There are only two steps to convert a binary number into an
octal number which are as follows:
Step 1: In the first step, we have to make the pairs of three bits on both sides of the binary point.
If there will be one or two bits left in a pair of three bits pair, we add the required number
of zeros on extreme sides.
Step 2: In the second step, we write the octal digits corresponding to each pair.

Example: (111110101011.0011)2
Step 1: Firstly, we make pairs of three bits on both sides of the binary point.
111 110 101 011.001 1

Modeling of Digital Circuits by D. O. Sakle

 Page 6

On the right side of the binary point, the last pair has only one bit. To make it a complete pair of
three bits, we added two zeros on the extreme side.
111 110 101 011.001 100
Step 2: Then, we wrote the octal digits, which correspond to each pair.
(111110101011.0011)2 = (7653.14)8

Octal to Binary Conversion

The process of converting octal to binary is the reverse process of binary to octal. We write the
three bits binary code of each octal number digit.
Example: (152.25)8
We write the three-bit binary digit for 1, 5, 2, and 5.
(152.25)8 = (001101010.010101)2
So, the binary number of the octal number 152.25 is (001101010.010101)2

Binary to Hexadecimal Conversion

The base numbers of binary and hexadecimal are 2 and 16, respectively. In a binary number, the
pair of four bits is equal to one hexadecimal digit. There are also only two steps to convert a binary
number into a hexadecimal number which are as follows:
Step 1: In the first step, we have to make the pairs of four bits on both sides of the binary point.
If there will be one, two, or three bits left in a pair of four bits pair, we add the required
number of zeros on extreme sides.
Step 2: In the second step, we write the hexadecimal digits corresponding to each pair.

Example: (10110101011.0011)2
Step 1: Firstly, we make pairs of four bits on both sides of the binary point.
111 1010 1011.0011
On the left side of the binary point, the first pair has three bits. To make it a complete pair of four
bits, add one zero on the extreme side.
0111 1010 1011.0011
Step 2: Then, we write the hexadecimal digits, which correspond to each pair.
(011110101011.0011)2=(7AB.3)16

Hexadecimal to Binary Conversion

The process of converting hexadecimal to binary is the reverse process of binary to hexadecimal.
We write the four bits binary code of each hexadecimal number digit.
Example: (152A.25)16
We write the four-bit binary digit for 1, 5, A, 2, and 5.
(152A.25)16 = (0001 0101 0010 1010.0010 0101)2
So, the binary number of the hexadecimal number (152.25)16 is (1010100101010.00100101)2

Octal to hexadecimal conversion

For converting octal to hexadecimal, there are two steps required to perform, which are as follows:
Step 1: In the first step, we will find the binary equivalent of number 25.
Step 2: Next, we have to make the pairs of four bits on both sides of the binary point. If there
will be one, two, or three bits left in a pair of four bits pair, we add the required number
of zeros on extreme sides and write the hexadecimal digits corresponding to each pair.
Modeling of Digital Circuits by D. O. Sakle
 Page 7

Example: (152.25)8
Step 1:
We write the three-bit binary digit for 1, 5, 2, and 5.
(152.25)8 = (001101010.010101)2
So, the binary number of the octal number 152.25 is (001101010.010101)2
Step 2:
1. Now, we make pairs of four bits on both sides of the binary point.
0 0110 1010.0101 01
On the left side of the binary point, the first pair has only one digit, and on the right side, the last
pair has only two-digit. To make them complete pairs of four bits, add zeros on extreme sides.
0000 0110 1010.0101 0100
2. Now, we write the hexadecimal digits, which correspond to each pair.
(0000 0110 1010.0101 0100)2 = (6A.54)16

Hexadecimal to Octal Conversion

For converting hexadecimal to octal, there are two steps required to perform, which are as follows:
Step 1: In the first step, we will find the binary equivalent of the hexadecimal number.
Step 2: Next, we have to make the pairs of three bits on both sides of the binary point. If there
will be one or two bits left in a pair of three bits pair, we add the required number of
zeros on extreme sides and write the octal digits corresponding to each pair.
Example: (152A.25)16
Step 1:
We write the four-bit binary digit for 1, 5, 2, A, and 5.
(152A.25)16 = (0001 0101 0010 1010.0010 0101)2
So, the binary number of hexadecimal number (152A.25)16 is (0011010101010.010101)2
Step 2:
Then, we make pairs of three bits on both sides of the binary point.
001 010 100 101 010.001 001 010
Then, we write the octal digit, which corresponds to each pair.
(001010100101010.001001010)2 = (12452.112)8
So, the octal number of the hexadecimal number (152A.25)16 is (12452.112)8

1s And 2s Complement Codes:

1’s Complement Representation:
In 1’s complement representation, the representation of the positive number is same as the negative
number. But the representation of the negative number is different.
For example, if we want to represent -34 in 8-bit 1’s complement form, then first write the positive
number (+34). And invert all 1s in that number by 0s and 0s by 1s in that number. The
corresponding inverted number represents the -34 in 1’s complement form. It is also called 1s
complement of the number +34.

Modeling of Digital Circuits by D. O. Sakle

 Page 8

Here is another example which shows how to represent -60 in 8-bit 1’s complement form.

Using n-bits, the range of numbers that can be represented in 1’s complement form is from – (2n-
1 – 1) to (2n -1 – 1). For example, using 4-bits, it is possible to represent integers numbers from -7

to +7 in a 1’s complement form representation.

Similar to sign-magnitude form, there are two different representations of 0 in 1’s complement
form representation.

2’s Complement Representation

In 2’s complement representation also, the representation of the positive number is same as1’s
complement and sign-magnitude form.

But the representation of the negative number is different. For example, if we want to represent -
34 in 2’s complement form then
1. Write the number corresponding to +34.
2. Starting from Least Significant Bit (LSB), just copy all the bits until the first 1 is
encountered in the number.
3. After the first ‘1’ is encountered, invert all the 1s in the number with 0s and 0s in the
number with 1s (including the sign bit)
4. The resultant number is 2’s complement representation of the number -34.
The same is shown below.

Modeling of Digital Circuits by D. O. Sakle

 Page 9

The second way of representing -34 in 2’s complement form is

1. Write the number corresponding to +34.
2. Find 1’s complement of +34
3. Add ‘1’ to the 1’s complement number
4. The resultant is 2’s complement representation of -34
The same is shown below.

For n-bit number N, its 2’s complement is (2n – N). For example, the 2’s complement of +34 in 8-
bit form is (28 – 34). In binary, it is 100000000 – 00100010 = 11011110. That is a third way of
finding the 2’s complement.
Here is the representation of -60 in sign-magnitude form, 1’s complement, and 2’s complement
form.

Using n-bits, the range of number which can be represented in 2’s complement form is from -(2n-
1
) to 2n-1 – 1. For example, using 4-bits, it is possible to represent numbers from -8 to +7. Unlike
1’s complement and sign magnitude form, there is a unique way of representing 0 in this 2’s
complement form.

Modeling of Digital Circuits by D. O. Sakle

 Page 10

Boolean Laws:
A set of rules or Laws of Boolean Algebra expressions have been invented to help reduce the
number of logic gates needed to perform a particular logic operation resulting in a list of functions
or theorems known commonly as the Laws of Boolean Algebra.
Boolean Algebra is the mathematics we use to analyze digital gates and circuits. We can use these
“Laws of Boolean” to both reduce and simplify a complex Boolean expression in an attempt to
reduce the number of logic gates required. Boolean Algebra is therefore a system of mathematics
based on logic that has its own set of rules or laws which are used to define and reduce Boolean
expressions.
The variables used in Boolean Algebra only have one of two possible values, a logic “0” and a
logic “1” but an expression can have an infinite number of variables all labelled individually to
represent inputs to the expression, for example, variables A, B, C etc., giving us a logical
expression of A + B = C, but each variable can ONLY be a 0 or a 1.

Examples:
1) Prove that ABC + ABC̅ + AB̅C + A̅BC = AB + AC + BC
ABC + ABC̅ + AB̅C + A̅BC = AB (C + C̅) + AB̅C + A̅BC
= AB + AB̅C + A̅BC
= A(B + B̅C) + A̅BC
Modeling of Digital Circuits by D. O. Sakle
 Page 11

= A(B + C) + A̅BC
= AB + AC + A̅BC
= B(A + A̅C) + AC
= B(A + C) + AC
= AB + BC + AC
= AB + AC +BC ...Proved

2) Show that (X + Y̅ + XY)(X + Y̅)(X̅Y) = 0

(X + Y̅ + XY)(X + Y̅)(X̅Y) = (X + Y̅ + X)(X + Y̅)(X̅ + Y)
= (X + Y̅)(X + Y̅)(X̅Y)
= (X + Y̅)(X̅Y)
= XX̅ + Y̅X̅Y
= 0...Proved

3) Simplify the following expression Y = (A + B)(A + C̅)(B̅ + C̅)

Y = (A + B)(A + C̅)(B̅ + C̅)
= (AA̅ + AC +A̅B +BC)(B̅ + C̅)
= (AC + A̅B + BC)(B̅ + C̅)
= AB̅C + ACC̅ + A̅BB̅ + A̅BC̅ + BB̅C + BCC̅
= AB̅C + A̅BC̅

Associative Law:
Associative law defines that the different grouping of variable in the multivariable AND and OR
operation doesn’t change the output. The laws are
i) A + (B + C) = (A + B) + C
ii) A.(B.C) = (A.B).C

Input variables AND Logic OR Logic

A B C A.B B.C A.(B.C) (A.B).C A+B B+C A+(B+C) (A+B)+C
0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 1 1 1
0 1 0 0 0 0 0 1 1 1 1
0 1 1 0 1 0 0 1 1 1 1
1 0 0 0 0 0 0 1 0 1 1
1 0 1 0 0 0 0 1 1 1 1
1 1 0 1 0 0 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1

Distributive Law:
Distributive law defines that the distribution of variables with AND operation over OR operation
is equal to the distribution of variables with OR operation over AND operation. This law states
that,
i) A + BC = (A + B)(A + C)
Modeling of Digital Circuits by D. O. Sakle
 Page 12

ii) A(B + C) = AB + AC

i) A + BC = (A + B)(A + C)

Input variables Distributive Law

A B C B.C A+B A+C A+(BC) (A+B)(A+C)
0 0 0 0 0 0 0 0
0 0 1 0 0 1 0 0
0 1 0 0 1 0 0 0
0 1 1 1 1 1 1 1
1 0 0 0 1 1 1 1
1 0 1 0 1 1 1 1
1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1

ii) A(B + C) = AB + AC

Input variables Distributive Law

A B C B+C A.B A.C A.(B+C) A.B+A.C
0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 1 0 1 0 0 0 0
0 1 1 1 0 0 0 0
1 0 0 0 0 0 0 0
1 0 1 1 0 1 1 1
1 1 0 1 1 0 1 1
1 1 1 1 1 1 1 1

De-Morgan’s theorems:
We use De Morgan’s theorems to solve the expressions of Boolean Algebra. It is a very powerful
tool used in digital design. This theorem explains that the complements of the products of all the
terms are equal to the sums of the complements of each and every term. Likewise, the complements
of the sums of all the terms are equal to the products of the complements of each and every term.
Two of the theorems were suggested by De Morgan that are extremely useful for Boolean Algebra.
These two theorems have been discussed below in this article:

Theorem 1:
DeMorgan’s first theorem proves that when two (or more) input variables are AND’ed and
negated, they are equivalent to the OR of the complements of the individual variables. Thus the
equivalent of the NAND function will be a negative-OR function, proving that ̅̅̅̅̅ ̅+𝐁
𝐀. 𝐁 = 𝐀 ̅ . We
can show this operation using the following table

A B A.B ̅̅̅̅̅
𝐀. 𝐁 A̅ B̅ A̅ + B̅
0 0 0 1 1 1 1

Modeling of Digital Circuits by D. O. Sakle

 Page 13

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

Theorem 2:
DeMorgan’s Second theorem proves that when two (or more) input variables are OR’ed and
negated, they are equivalent to the AND of the complements of the individual variables. Thus the
equivalent of the NOR function is a negative-AND function proving that ̅̅̅̅̅̅̅̅
𝐀+𝐁= 𝐀 ̅. 𝐁
̅ , and again
we can show operation this using the following truth table.

A B A+B ̅̅̅̅̅̅̅̅
𝐀+𝐁 A̅ B̅ A̅.B̅
0 0 0 1 1 1 1
0 1 1 0 1 0 0
1 0 1 0 0 1 0
1 1 1 0 0 0 0

Logic Gates:
The logic gate is the most basic building block of any digital system, including computers. Each
one of the basic logic gates is a piece of hardware or an electronic circuit that can be used to
implement some basic logic expression. While laws of Boolean algebra could be used to do
manipulation with binary variables and simplify logic expressions, these are actually implemented
in a digital system with the help of electronic circuits called logic gates. The three basic logic gates
are the OR gate, the AND gate and the NOT gate.

OR Gate:
An OR gate performs an ORing operation on two or more than two logic variables. The OR
operation on two independent logic variables A and B is written as Y = A + B and reads as Y
equals A OR B and not as A plus B. An OR gate is a logic circuit with two or more inputs and one
output. The output of an OR gate is LOW only when all of its inputs are LOW. For all other
possible input combinations, the output is HIGH. Figure shows the circuit symbol and the truth
table of a two-input OR gate. The operation of a two-input OR gate is explained by the logic
expression
Y=A+B

A B Y
0 0 0
0 1 1
1 0 1
1 1 1
Fig: Two-input OR gate.

Modeling of Digital Circuits by D. O. Sakle

 Page 14

AND Gate:
An AND gate is a logic circuit having two or more inputs and one output. The output of an AND
gate is HIGH only when all of its inputs are in the HIGH state. In all other cases, the output is
LOW. The logic symbol and truth table of a two-input AND gate are shown in Figure. The AND
operation on two independent logic variables A and B is written as Y = A.B and reads as Y equals
A AND B and not as A multiplied by B. Here, A and B are input logic variables and Y is the
output. An AND gate performs an ANDing operation:

A B Y
0 0 0
0 1 0
1 0 0
1 1 1
Fig: Two-input AND gate.

NOT Gate:
A NOT gate is a one-input, one-output logic circuit whose output is always the complement of the
input. That is, a LOW input produces a HIGH output, and vice versa. It is also known as a
‘complementing circuit’ or an ‘inverting circuit’. Figure shows the circuit symbol and the truth
table. The NOT operation on a logic variable X is denoted as X̅. That is, if X is the input to a NOT
circuit, then its output Y is given by Y = X̅ and reads as Y equals NOT X. Thus, if X = 0, Y = 1
and if X = 1, Y = 0.

A Y
0 1
1 0
Fig: NOT gate.

EXCLUSIVE-OR Gate:
The EXCLUSIVE-OR gate, commonly written as EX-OR gate, is a two-input, one-output gate.
Figures shows the logic symbol and truth table of a two-input EX-OR gate. As can be seen from
the truth table, the output of an EX-OR gate is a logic ‘1’ when the inputs are unlike and a logic
‘0’ when the inputs are like. Although EX-OR gates are available in integrated circuit form only
as two-input gates, unlike other gates which are available in multiple inputs also, multiple-input
EX-OR logic functions can be implemented using more than one two-input gates. The truth table
of a multiple-input EX-OR function can be expressed as follows. The output of a multiple-input
EX-OR logic function is a logic ‘1’ when the number of 1s in the input sequence is odd and a logic
‘0’ when the number of 1s in the input sequence is even, including zero. That is, an all 0s input

Modeling of Digital Circuits by D. O. Sakle

 Page 15

sequence also produces a logic ‘0’ at the output. Figure shows the truth table of a four-input EX-
OR function. The output of a two-input EX-OR gate is expressed by

A B Y
0 0 0
0 1 1
1 0 1
1 1 0
Fig: Two-input EX-OR gate.

EXCLUSIVE-NOR Gate:
EXCLUSIVE-NOR (commonly written as EX-NOR) means NOT of EX-OR, i.e. the logic gate
that we get by complementing the output of an EX-OR gate. Figure shows its circuit symbol along
with its truth table. The truth table of an EX-NOR gate is obtained from the truth table of an EX-
OR gate by complementing the output entries. Logically,

A B Y
0 0 1
0 1 0
1 0 0
1 1 1
Fig: Two-input EX-NOR gate.

NAND Gate:
NAND stands for NOT AND. An AND gate followed by a NOT circuit makes it a NAND gate.
Figure shows the circuit symbol of a two-input NAND gate. The truth table of a NAND gate is
obtained from the truth table of an AND gate by complementing the output entries. The output
of a NAND gate is a logic ‘0’ when all its inputs are a logic ‘1’. For all other input combinations,
the output is a logic ‘1’. NAND gate operation is logically expressed as

In general, the Boolean expression for a NAND gate with more than two inputs can be written
as

Modeling of Digital Circuits by D. O. Sakle

 Page 16

A B Y
0 0 1
0 1 1
1 0 1
1 1 0

Fig: Two-input NAND gate.

NOR Gate:
NOR stands for NOT OR. An OR gate followed by a NOT circuit makes it a NOR gate. The truth
table of a NOR gate is obtained from the truth table of an OR gate by complementing the output
entries. The output of a NOR gate is a logic ‘1’ when all its inputs are logic ‘0’. For all other input
combinations, the output is a logic ‘0’. The output of a two-input NOR gate is logically expressed
as

In general, the Boolean expression for a NOR gate with more than two inputs can be written as

A B Y
0 0 1
0 1 0
1 0 0
1 1 0
Fig: Two-input NOR gate.

Minterm:
Each of the product terms in the canonical SOP form is called a minterm. Minterm are
represented as binary numbers in terms of 0s and 1s. The binary words are formed by
representing each non-complemented variable by 1 and each complemented variable by 0, and
the decimal equivalent of this binary word is represented as a subscript of m as m0, m1, m2, etc.
We generally use the ∑ (sigma) notation to represent minterms.
In Minterm, we look for the functions where the output results in “1”. We perform Sum of
minterm also known as Sum of products (SOP).

Maxterm:
Each of the sum terms in the canonical POS form is called a maxterm. Maxterm can also be
represented using binary numbers where each non-complemented variable is represented using
0 and complemented variable using 1, and the decimal equivalent of this binary word is
represented as a subscript of M as M0, M1, M2, etc. We generally use ∏ (pi) notation to
represent the max terms.

Modeling of Digital Circuits by D. O. Sakle

 Page 17

In Maxterm we look for function where the output results in “0”. We perform Product of
Maxterm also known as Product of sum (POS).

Table: Min and Max terms for three literal binary expressions

From the above table it is clear that minterm is expressed in product format and maxterm is
expressed in sum format.

Example: Express the following in corresponding minterm and maxterm expression

Modeling of Digital Circuits by D. O. Sakle

 Page 18

Note: If a truth table is given, and if the output is 1 then it corresponds to minterm and in case
the output is 0 then it corresponds to maxterm.

In the above truth table, the minterms will be m2, m5, m6 and m7 i.e.,
F = ∑m (2, 5,6, 7)

and maxterms will be M0, M1, M3 and M4 i.e.,

F = ∏M (0, 1, 3, 4)

Sum of Product (SOP) Form:

The sum-of-products (SOP) form is a method (or form) of simplifying the Boolean expressions of
logic gates. In this SOP form of Boolean function representation, the variables are operated by
AND (product) to form a product term and all these product terms are ORed (summed or added)
together to get the final function. A sum-of-products form can be formed by adding (or summing)
two or more product terms using a Boolean addition operation. Here the product terms are defined
by using the AND operation and the sum term is defined by using OR operation.
The sum-of-products form is also called as Disjunctive Normal Form as the product terms are
ORed together and Disjunction operation is logical OR. SOP form representation is most suitable
to use them in FPGA (Field Programmable Gate Arrays).
Examples:
ABCD + AC + BCD

Modeling of Digital Circuits by D. O. Sakle

 Page 19

A̅B + AB̅C̅ + CD̅E

Product of Sums (POS) Form:

The product of sums form is a method (or form) of simplifying the Boolean expressions of logic
gates. In this POS form, all the variables are ORed, i.e. written as sums to form sum terms.
All these sum terms are ANDed (multiplied) together to get the product-of-sum form. This form
is exactly opposite to the SOP form. So this can also be said as “Dual of SOP form”.
Here the sum terms are defined by using the OR operation and the product term is defined by using
AND operation. When two or more sum terms are multiplied by a Boolean OR operation, the
resultant output expression will be in the form of product-of-sums form or POS form.
The product-of-sums form is also called as Conjunctive Normal Form as the sum terms are ANDed
together and Conjunction operation is logical AND. Product-of-sums form is also called as
Standard POS.
Examples:
(A+B)(A̅ + B̅ + C)(C +D)
(A̅+B)(C̅ + D̅ + E̅)

Canonical Form (Standard SOP and POS Form):

Any Boolean function that is expressed as a sum of minterms or as a product of max terms is said
to be in its “canonical form”. It mainly involves in two Boolean terms, “minterms” and
“maxterms”.

Standard SOP Form:

When the SOP form of a Boolean expression is in canonical form, then each of its product term is
called ‘minterm’. So, the canonical form of sum of products function is also known as “minterm
canonical form” or Sum-of-minterms or standard canonical SOP form.
Example:
F = A̅BC + AB̅C + ABC̅ + ABC
Truth table:

Standard POS Form:

When the POS form of a Boolean expression is in canonical form, then each of its sum term is
called ‘maxterm’. So, the canonical form of product of sums function is also known as “maxterm
canonical form or Product-of sum or standard canonical POS form”.
Modeling of Digital Circuits by D. O. Sakle
 Page 20

Example:
F = (A + B + C) (A + B + C̅) (A + B̅ + C) (A̅ + B + C)
Truth table:

Conversions of Canonical Forms:

We can represent the one canonical formed equation in other canonical form i.e. we can represent
the SOP form of equation in POS form and POS form equation in SOP form. To convert the
canonical equations, we interchange the Σ and Π symbols after listing out the index numbers of
the equations, which are excluded from the original form of equation.
The important thing to remember about Boolean functions is that, the SOP and POS forms are
Duals to each other. There are 2 steps to follow to convert the canonical form of the equations.
They are
Step 1: Interchanging the operational symbols, Σ and Π in the equation.
Step 2: Use the De Morgan’s principle of Duality to the index numbers of the Boolean function
or writing the indexes of the terms that are not presented in the given form of equation.

Conversion of SOP form to POS form:

To convert the SOP form into POS form, first we should change the Σ to Π and then write the
numeric indexes of missing variables of the given Boolean function.
Example:
The SOP function
F = ∑ A, B, C (0, 2, 3, 5, 7) = A̅B̅C̅ + AB̅C̅ + AB̅C + ABC̅ + ABC is written in POS form by
Step 1: changing the operational sign to Π
Step 2: writing the missing indexes of the terms, 001, 100 and 110. Now write the sum form for
these noted terms.
001 = (A +B + C), 100 = (A + B̅ + C̅), 110 = (A + B̅ + C̅)
Writing down the new equation in the form of POS form,
F = Π A, B, C (1, 4, 6) = (A + B + C) (A + B̅ + C̅) (A + B̅ + C̅)

Conversion of POS form to SOP form:

To convert the POS form into SOP form, first we should change the Π to Σ and then write the
numeric indexes of missing variables of the given Boolean function.
Ex: The POS function F = Π A, B, C (2, 3, 5) = AB̅C̅ + AB̅C + ABC̅ is written in SOP form by
Step 1: changing the operational sign to Σ

Modeling of Digital Circuits by D. O. Sakle

 Page 21

Step 2: writing the missing indexes of the terms, 000, 001, 100, 110, and 111. Now write the
product form for these noted terms.
000 = A̅B̅C̅, 001 = A̅B̅C, 100 = AB̅C̅, 110 = ABC̅, 111 = ABC
Writing down the new equation in the form of SOP form,
F = Σ A, B, C (0, 1, 4, 6, 7) = A̅B̅C̅ + A̅B̅C + AB̅C̅ + ABC̅ + ABC

Conversion of SOP form to standard SOP form or Canonical SOP form:

We can include all the variables in each product term of the SOP form equation, which doesn’t
have all the variables by converting into standard SOP form. The normal SOP form function can
be converted to standard SOP form by using the Boolean algebraic law, (A + A̅ = 1) and by
following the below steps.
Step 1: By multiplying each non-standard product term with the sum of its missing variable and
its complement, which results in 2 product terms
Step 2: By repeating the step 1, until all resulting product terms contain all variables
By these two steps we can convert the SOP function into standard SOP function. In this process,
for each missing variable in the function, the number of product terms will double.

Example:
Convert the non-standard SOP function F = XY + XZ + YZ
Sol:
F = XY + XZ + YZ
= XY(Z + Z̅) + XZ(Y+Y̅) + YZ(X+X̅)
= X Y Z + X Y Z̅ + X Y Z + X Y̅ Z + X Y Z + X̅ Y Z
= X Y Z + X Y Z̅ + X Y̅ Z + X̅ Y Z
The standard SOP form is F = X Y Z + X Y Z̅ + X Y̅ Z + X̅ Y Z

Conversion of POS form to standard POS form or Canonical POS form:

We can include all the variables in each product term of the POS form equation, which doesn’t
have all the variables by converting into standard POS form. The normal POS form function can
be converted to standard POS form by using the Boolean algebraic law, (AA̅ = 0) and by following
the below steps.
Step 1: By adding each non-standard sum term to the product of its missing variable and its
complement, which results in 2 sum terms
Step 2: Applying Boolean algebraic law, A + BC = (A + B) (A + C)
Step 3: By repeating the step 1, until all resulting sum terms contain all variables
By these three steps we can convert the POS function into standard POS function.
Example:
F = (A̅ + B + C) (B̅ + C + D̅) (A + B̅ + C̅ + D)
In the first term, the variable D or D̅ is missing, so we add DD̅ = 1 to it. Then
(A̅ + B + C + DD̅) = (A̅ + B + C + D) (A̅ + B + C + D̅)
Similarly, in the second term, the variable A or A̅ is missing, so we add AA̅ = 1 to it. Then
(B̅ + C + D̅ + AA̅) = (A + B̅ + C + D̅) (A̅ + B̅ + C + D̅)
The third term is already in the standard form, as it has all the variables. Now the standard POS
form equation of the function is
F = (A̅ + B + C + D) (A̅ + B + C + D̅) (A + B̅ + C + D̅) (A̅ + B̅ + C + D̅) (A + B̅ + C̅ + D)

Modeling of Digital Circuits by D. O. Sakle

 Page 22

Karnaugh map:
The K-map is a systematic way of simplifying Boolean expressions. With the help of the K-map
method, we can find the simplest POS and SOP expression, which is known as the minimum
expression. The K-map provides a cookbook for simplification.
Just like the truth table, a K-map contains all the possible values of input variables and their
corresponding output values. However, in K-map, the values are stored in cells of the array. In
each cell, a binary value of each input variable is stored.
The K-map method is used for expressions containing 2, 3, 4, and 5 variables. In K-map, the
number of cells is similar to the total number of variable input combinations. For example, if the
number of variables is three, the number of cells is 23=8, and if the number of variables is four, the
number of cells is 16. The K-map takes the SOP and POS forms. The K-map grid is filled using
0's and 1's. The K-map is solved by making groups. There are the following steps used to solve
the expressions using K-map:
1. First, we find the K-map as per the number of variables.
2. Find the maxterm and minterm in the given expression.
3. Fill cells of K-map for SOP with 1 respective to the minterms.
4. Fill cells of the block for POS with 0 respective to the maxterm.
5. Next, we create rectangular groups that contain total terms in the power of two like 2, 4, 8,
… and try to cover as many elements as we can in one group.
6. With the help of these groups, we find the product terms and sum them up for the SOP
form.
2 variable k-map: – In the 2 variable k-map, four squares are constructed. Each square contains
one term of expression with two variables. A 2 variable k-map for SOP and POS form are as
follows: –

3 variables k-map: – In the three variable k-map, 8 square is required. The 3-variables k-map can
content either horizontally or vertically. An example of 3 variables k-map for SOP and POS form
are as follows: –

Modeling of Digital Circuits by D. O. Sakle

 Page 23

4 variable k-map: – In the 4 variable k-map, 16 square are required. An example of 4 variable k-
map for SOP and POS form are as follows: –

Example 1: Minimize the four-variable logic function using K-map

f(A,B,C,D) = ∑m(0,1,2,3,5,7,8,9,11,14)
Answer:

From K-map the minimized Boolean expression is,

Example 2: Minimize the four-variable logic function using K-map

f(P,Q,R,S) = ∑m(0,2,5,7,8,10,13,15)
Answer:

Modeling of Digital Circuits by D. O. Sakle

 Page 24

From K-map the minimized Boolean expression is,

f(P,Q,R,S) = QS + QS

Modeling of Digital Circuits by D. O. Sakle