Boolean Algebra

&
Gate Networks

Dr. Mayank Jain

 Boolean Algebra
 The logical symbol 0 and 1 are used for representing the digital input or
output. The symbols "1" and "0" can also be used for a permanently open and
closed digital circuit.
 The digital circuit can be made up of several logic gates. To perform the
logical operation with minimum logic gates, a set of rules were invented,
known as the Laws of Boolean Algebra. These rules are used to reduce the
number of logic gates for performing logic operations.
 The Boolean algebra is mainly used for simplifying and analyzing the complex
Boolean expression. It is also known as Binary algebra because we only use
binary numbers in this.
 George Boole developed the binary algebra in 1854.
 Boolean algebra is the category of algebra in which the
variable’s values are the truth values, true and false, ordinarily
denoted 1 and 0 respectively. It is used to analyze and
simplify digital circuits or digital gates.
 It is also called Binary Algebra or logical Algebra. It has been
fundamental in the development of digital electronics and is
provided for in all modern programming languages. It is also
used in set theory and statistics.
Rules in Boolean algebra
 Only two values(1 for high and 0 for low) are possible for
the variable used in Boolean algebra.
 The overbar(-) is used for representing the complement
variable. So, the complement of variable C is
represented as .
 The plus(+) operator is used to represent the OR ing of
the variables.
 The dot(.) operator is used to represent the AND ing of
the variables.
 Logic Gates

 Logic gates play an important role in circuit design and

digital systems. It is a building block of a digital system
and an electronic circuit that always have only one
output. These gates can have one input or more than
one input, but most of the gates have two inputs. On the
basis of the relationship between the input and the
output, these gates are named as AND gate, OR gate,
NOT gate, etc.
 There are different types of gates which are as follows:
AND Gate

This gate works in the same way as the logical

operator "and". The AND gate is a circuit that performs the
AND operation of the inputs. This gate has a minimum of 2
input values and an output value.
Y=A AND B AND C AND D……N
Y=A.B.C.D……N
Y=ABCD……N Logic Design
 Common ways of expressing AND.
Engineering Y=A⋅B= AB = (A)(B) = AND(A,B) = A AND B
Programming Y= A&B = A&&B
Math and Formal Logic Y=A∧B
OR GATE:

 The OR gate is an electronic circuit which gives a high

output if one or more of its inputs are high. The operation
performed by an OR gate is represented by a plus (+)
sign.
Common ways of expressing XOR
Engineering Y= XOR(A,B) = A⊕B
Programming Y=AB
Math and Formal Logic Y= A v B= A⊕B
 NOT GATE:
 The NOT gate is an electronic circuit which produces an inverted
version of the input at its output. It is also known as an Inverter.
 compliment of an input signal.
 It takes only one input and one output.
 The output of the NOT gate is complement of the input applied to
it. Therefore, if we apply a low or logic 0 output to the NOT gate is
gives a high or logic 1 output and vice-versa.
 Understanding Boolean Algebra through Truth Table
Input Output
C AND
A B C D A AND B Y
Let Y= (A AND B) OR (C AND (NOT D)) (NOT D)

0 0 0 0 0 0 0

0 0 0 1 0 0 0

0 0 1 0 0 1 1

0 0 1 1 0 0 0

0 1 0 0 0 0 0

0 1 0 1 0 0 0

0 1 1 0 0 1 1

0 1 1 1 0 0 0

1 0 0 0 0 0 0

1 0 0 1 0 0 0

1 0 1 0 0 1 1

1 0 1 1 0 0 0

1 1 0 0 1 0 1

1 1 0 1 1 0 1

1 1 1 0 1 1 1

1 1 1 1 1 0 1
Examples

 A AND (B AND C)

 NOT (A OR B)
 (A OR B) AND NOT C
NAND Gate
 The NAND gate is a special type of logic gate in the digital logic circuit.
 The NAND gate is the universal gate. It means all the basic gates such as
AND, OR, and NOT gate can be constructed using a NAND gate.
 The NAND gate is the combination of the NOT-AND gate.
 The output state of the NAND gate will be low only when all the inputs are
high. Simply, this gate returns the complement result of the AND gate.

Truth Table
AND gate using NAND gate
NOR Gate

 The NOR gate is also a universal gate. So, we can also form all the basic
gates using the NOR gate.
 The NOR gate is the combination of the NOT-OR gate. The output state of
the NOR gate will be high only when all of the inputs are low.
 Simply, this gate returns the complement result of the OR gate.
Truth Table
OR gate using NOR gate
Laws and Rules of Boolean algebra

 There are the following laws of Boolean algebra:

 Commutative Law
 Associative Law
 Distributive Law
Commutative Law

 This law states that no matter in which order we use the variables. It means
that the order of variables doesn't matter. In Boolean algebra, the OR and
the addition operations are similar. In the below diagram, the OR gate
display that the order of the input variables does not matter at all.
 A+B = B+A A.B = B.A
Associative Law

 This law states that the operation can be performed in any order when the
variables priority is same. As '*' and '/' have same priority. In the below
diagram, the associative law is applied to the 2-input OR gate.
 For three variables, the associative law of addition is written as:
 A + (B + C) = (A + B) + C
 A(BC) = (AB)C
 When a variable is used in an algebraic formula, it is generally assumed
that the variable may take any numerical value.
 For instance, in the formula 2X -SY = Z, we assume that X, Y, and Z may
range through the entire field of real numbers.
 The variables used in boolean equations have a unique characteristic,
how-ever; they may assume only one of two possible values. These two
values may be
DERIVATION OF A BOOLEAN
EXPRESSION
 When designing a logical circuit, the logical designer works from two sets of
known values:
 (1) the various states which the inputs to the logical network can take and (2)
the desired outputs for each input condition. The logical expression is derived
from these sets of values.
 Consider a specific problem. A logical network has two inputs X and Y and an
output Z. The relationship between inputs and outputs is to be as follows:
 1 When both X and Y are 0s, the output Z is to be 1.
 2 When X is 0 and Y is 1, the output Z is to be 0.
 3 When X is 1 and Y is 0, the output Z is to be 1.
 4 When X is 1 and Y is 1, the output Z is to be 1.
 These relations may be expressed in tabular form, as shown in Table 3.13.It is
now necessary to add another column to the table.
 This column will consist of a list of product terms obtained from the values of
the input variables.The new column will contain each of the input variables
listed in each row of the table, with the letter representing the respective
input complemented when the input value for this variable is 0 and not
complemented when the input value is 1. The terms obtained in this
manner are designated as product terms. With two input variables X and Y,
each row of the table will contain a product term consisting of X and Y,
with X or Y complemented or not, depending on the input values for that
row (see Table 3.14).Whenever Z is equal to 1, the X and Y product term
from the same row is removed and formed into a sum-of-products
expression. Therefore, the product terms from the first, third, and fourth rows
are selected. These are XY, XY, and XY
Introduction of K-Map (Karnaugh Map)

 A K-Map or Karnaugh Map is a graphical method that used for simplifying

the complex algebraic expressions in Boolean functions. This method avoid
the use of complex theorems and equations manipulations. A K-Map is
basically a special form of a truth table that can easily map out the values
of parameters and gives a simplified Boolean expression.
 K-Map method is best suited for such Boolean functions that have two to
four variables. However, it can be used for Boolean functions having five or
six variables as well, but its process becomes more difficult with the
increased number of variables in the function.
 Three-Variable K-Map

We can use the K-Map to simplify a Boolean function of

three-variables.
A Boolean function in three variables (A, B, C) can be
expressed in the standard sum of product (SOP)
form that can have total eight possible combinations,
which are as follows −
(A′B′C′),(A′B′C),(A′BC′),(A′BC),(AB′C′),(AB′C),(ABC′),(ABC)
 We can designate each of these combinations by m0, m1, m2, m3, m4, m5, m6, and
m7 respectively. Each of these terms are called a min-term. In these combinations,
A is called MSB (Most Significant Bit) and C is called LSB (Least Significant Bit).

In terms of POS (Product of Sum) form, the eight possible combinations of the three
variables Boolean expression are as follows −
(A+B+C),(A+B+C′),(A+B′+C),(A+B′+C′),(A′+B+C),(A′+B+C′),(A′+B′+C),(A′+B′+C′)

Each one of these combinations are often designated by M0, M1, M2, M3, M4, M5,
M6, and M7 respectively.
Each of these terms is called a maxterm. Similar to the minterm, A is called MSB (Most
Significant Bit) and C is called LSB (Least Significant Bit).

Here, the small number on the bottom right corner of each cell indicates the minterm
or maxterm designation.
Three Variable K – map:
For three variables two adjacent variables are taken on either side (vertical line or horizontal line) of the K – map and the
remaining one variable on the other side. Let A, B and C are the three variables.

OR
Four Variable K – map:
For four variables two adjacent variables are taken on either side (vertical line or horizontal line) of the K – map and the
two variables on the other side. Let A, B, C and D are the four variables.

OR
Example

 Z= A,B,C(1,3,6,7)

A’C
AB
 Example 1: Draw the K – maps for the following Boolean function of three variables.

In the K – map of three variables 1s entry are made for the combinations m1 , m3, m5, m6, m7 and in the remaining
combinations, 0s are entered.

Example 2: Draw the K – maps for the following Boolean function of four variables.
Encircling of Groups:
After constructing K – map, the pairs quads and octets of adjacent 1s in the K – map are made for getting the minimal
Boolean expression. A pair eliminates one variable with its complement; a quad and an octet eliminate two variables and
three variables respectively with their complements.
Pairs:
In the three-variable or four variable K – map having 1s and 0’s entry, two adjacent 1s (vertically or horizontally) are
encircled. The diagonally adjacent 1s are never encircled.
Quads:
In the K –map if four 1s are adjacent in a row or column or in the form of a square, then these 1s are encircled called as
quads.
Octets:
The eight adjacent 1s are encircled in a K – map known as octet. Figure shows the encircled octet (solid line) in
a K – map of 4 variables.

Overlapping groups: While making encircled groups in the K – map, it is always tried to have the groups of largest
number of 1s first than others, i.e. octets are encircled first than quads and than pairs. It is important to use same 1 more
than once. In other words same 1 may be used in more than one encircled groups. Such groups are called as the
overlapped groups. Some overlapped groups are shown in figure
The terms for each encircled groups are written in the same manner as is done for normal pairs, quads and octets.
Rolling groups:
It is also allowed to roll the K – map so that grouping of largest number of 1s may be formed. To understand this consider
a K – map as shown in figure 1. In this K – map while encircling, one can obtain two quads but using the rolling of K –
map, an octet may be formed as shown in figure 2. Here the rolling is done in such a way that the left hand side encircled
quad touches the right hand side encircled quad. This in fact looks like an octet. The rolling is shown by half encircling the
two groups as shown in figure 2.

figure 1 figure 2
The following rolling is possible as illustrated in figure
Redundant Groups:
While encircling the groups in the K – maps, there is a possibility that all the
elements (1s) of some group/groups are overlapped by other groups. Such a
group whose all 1s are overlapped by other groups is called a redundant group.
The redundant groups may be illustrated by considering a K – map as shown in
figure.

In this K – map the encircled groups are: one quad and four pairs. But
quad is redundant since all its four 1s are used in forming other pairs. The
quad is, therefore, eliminated. So the valid encircled groups will be as
shown in figure.
 Karnaugh Map Simplification Rules-

 To minimize the given boolean function,

• We draw a K Map according to the number of variables it contains.

• We fill the K Map with 0’s and 1’s according to its function.
• Then, we minimize the function in accordance with the following rules.
 Rule
1 Groups may overlap each other.
2 We can only create a group whose number of cells can be represented in
the power of 2. In other words, a group can only contain 2n i.e. 1, 2, 4, 8, 16
and so on number of cells.
 4 Groups can be only either horizontal or vertical.
 We can not create groups of diagonal or any other
shape.

5 Each group should be as large as possible.

6 Opposite grouping and corner grouping are allowed.
The example of opposite grouping is shown illustrated in Rule-04.
The example of corner grouping is shown below.

7 There should be as few groups as possible.

 Example : Minimize the following boolean function-
 F(A, B, C, D) = Σm(0, 1, 2, 5, 7, 8, 9, 10, 13, 15)

Solution-

•Since the given boolean expression has 4 variables, so we draw a 4 x 4 K Map.

•We fill the cells of K Map in accordance with the given boolean function.
•Then, we form the groups in accordance with the above rules.

Now, F(A, B, C, D)

= (A’B + AB)(C’D + CD) + (A’B’ + A’B + AB + AB’)C’D + (A’B’ + AB’)(C’D’ + CD’)

= BD + C’D + B’D’

Thus, minimized boolean expression is-

F(A, B, C, D) = BD + C’D + B’D’
 Minimize the following boolean function-
 F(A, B, C, D) = Σm(0, 1, 3, 5, 7, 8, 9, 11, 13, 15)

Now,
F(A, B, C, D)
= (A’B’ + A’B + AB + AB’)(C’D + CD) + (A’B’ + AB’)(C’D’ + C’D)
= D + B’C’

Thus, minimized boolean expression is-

F(A, B, C, D) = B’C’ + D
 Reduce the following using karnaugh map f (A, B, C, D) = Σm (0,1,4,8,9,10)
 Solve following examples :

1. Draw the K – map for m5 + m7 +m15 + m10 + m2 (K-map in A,B,C,D)

2. Draw the K – map for m1 + m5 + m7 + m6 + m12 + m13 + m15 + m11 (K – map in
W,X,Y,Z)