LOGIC GATES

Logic gates are the basic building blocks of any digital system. It is an electronic
circuit having one or more than one input and only one output. The relationship
between the input and the output is based on certain logic. Based on this, logic gates
are named as AND gate, OR gate, NOT gate etc.

 AND Gate
An AND gate has a single output and two or more inputs.
1. When all of the inputs are 1, the output of this gate is 1.
2. The AND gate’s Boolean logic is Y=A.B if there are two inputs A and B.
An AND gate’s symbol and truth table are as follows:

 OR Gate
Two or more inputs and one output can be used in an OR gate.
1. The logic of this gate is that if at least one of the inputs is 1, the output
will be 1.
2. The OR gate’s output will be given by the following mathematical
procedure if there are two inputs A and B: Y=A+B

Logic diagram

Truth Table
 NOT Gate
The NOT gate is a basic one-input, one-output gate.
1. When the input is 1, the output is 0 and vice versa. A NOT gate is
sometimes called as an inverter because of its feature.
2. If there is only one input A, the output may be calculated using the
Boolean equation Y=A’.
3. NOT gate is also known as Inverter. It has one input A and one output Y.

Logic diagram

Truth Table

Universal Logic Gates

 NOR Gate
A NOR gate, sometimes known as a “NOT-OR” gate, consists of an OR gate
followed by a NOT gate.
1. This gate’s output is 1 only when all of its inputs are 0. Alternatively,
when all of the inputs are low, the output is high.
2. The Boolean statement for the NOR gate is Y=(A+B)’ if there are two
inputs A and B.

Logic diagram
 Truth Table of NOR gate

 NAND Gate
A NAND gate, sometimes known as a ‘NOT-AND’ gate, is essentially a Not
gate followed by an AND gate.
1. This gate’s output is 1 only if none of the inputs is 1. Alternatively, when
all of the inputs are not high and at least one is low, the output is high.
2. If there are two inputs A and B, the Boolean expression for the NAND gate
is Y=(A.B)’

Logic diagram

Truth Table

Other Logic Gates

 XOR Gate
The Exclusive-OR or ‘Ex-OR’ gate is a digital logic gate that accepts more than
two inputs but only outputs one value.
1. If any of the inputs is ‘High,’ the output of the XOR Gate is ‘High.’ If both
inputs are ‘High,’ the output is ‘Low.’ If both inputs are ‘Low,’ the output
is ‘Low.’
2. The Boolean equation for the XOR gate is Y=A’.B+A.B’ if there are two
inputs A and B.
XOR or Ex-OR gate is a special type of gate. It can be used in the half adder, full
adder and subtractor. The exclusive-OR gate is abbreviated as EX-OR gate or
sometime as X-OR gate. It has n input (n >= 2) and one output.

Logic diagram

Truth Table

 XNOR Gate
The Exclusive-NOR or ‘EX-NOR’ gate is a digital logic gate that accepts more
than two inputs but only outputs one.
1. If both inputs are ‘High,’ the output of the XNOR Gate is ‘High.’ If both
inputs are ‘Low,’ the output is ‘Low.’ If one of the inputs is ‘Low,’ the
output is ‘Low.’
2. If there are two inputs A and B, then the XNOR gate’s Boolean equation
is: Y=A.B+A’B’.

XNOR gate is a special type of gate. It can be used in the half adder, full adder
and subtractor. The exclusive-NOR gate is abbreviated as EX-NOR gate or
sometime as X-NOR gate. It has n input (n >= 2) and one output.
 Logic diagram

Truth Table

BOOLEAN ALGEBRA
Boolean Algebra is used to analyze and simplify the digital (logic) circuits. It uses
only the binary numbers i.e. 0 and 1. It is also called as Binary Algebra or logical
Algebra. Boolean algebra was invented by George Boole in 1854.
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.

Rule in Boolean Algebra

Following are the important rules used in Boolean algebra.
 Variable used can have only two values. Binary 1 for HIGH and Binary 0 for
LOW.
 Complement of a variable is represented by an overbar (-). Thus, complement
of variable B is represented as . Thus if B = 0 then = 1 and B = 1 then
= 0.
 ORing of the variables is represented by a plus (+) sign between them. For
example ORing of A, B, C is represented as A + B + C.
  Logical ANDing of the two or more variable is represented by writing a dot
between them such as A.B.C. Sometime the dot may be omitted like ABC.

Boolean Laws/Properties of Boolean Algebra

There are Following types of Boolean Laws.

 Commutative law
Any binary operation which satisfies the following expression is referred to as
commutative operation.

Commutative law states that changing the sequence of the variables does not have
any effect on the output of a logic circuit.

 Associative law
This law states that the order in which the logic operations are performed is
irrelevant as their effect is the same.

 Distributive law
Distributive law states the following condition.

 AND law
These laws use the AND operation. Therefore they are called as AND laws.

 OR law
These laws use the OR operation. Therefore they are called as OR laws.

 INVERSION law/ Double Negation Law

This law uses the NOT operation. The inversion law states that double inversion of a
variable results in the original variable itself.
  Annulment Law
When the variable is AND with 0, it will give the result 0, and when the variable is
OR with 1, it will give the result 1, i.e.

B.0 = 0

B+1 = 1

 Identity Law
When the variable is AND with 1 and OR with 0, the variable remains the same, i.e.,

B.1 = B

B+0 = B

 Idempotent Law
When the variable is AND and OR with itself, the variable remains same or
unchanged, i.e.,

B.B = B

B+B = B

 Complement Law
When the variable is AND and OR with its complement, it will give the result 0 and 1
respectively.

B.B' = 0

B+B' = 1

 Absorption Law
This law allows us for absorbing the similar variables.

B+(B.A) = B

B.(B+A) = B
 Theorems of Boolean algebra
The following two theorems are used in Boolean algebra.

 Duality theorem


 DeMorgan’s theorem

Duality Theorem

This theorem states that the dual of the Boolean function is obtained by
interchanging the logical AND operator with logical OR operator and zeros with
ones. For every Boolean function, there will be a corresponding Dual function.
Let us make the Boolean equations relations relations that we discussed in the
section of Boolean postulates and basic laws into two groups. The following table
shows these two groups.
Group1 Group2

x+0=x x.1 = x

x+1=1 x.0 = 0

x+x=x x.x = x

x + x’ = 1 x.x’ = 0

x+y=y+x x.y = y.x

x + y+zy+z = x+yx+y + z x.y.zy.z = x.yx.y.z

x.y+zy+z = x.y + x.z x + y.zy.z = x+yx+y.x+zx+z

In each row, there are two Boolean equations and they are dual to each other. We
can verify all these Boolean equations of Group1 and Group2 by using duality
theorem.
 De Morgan's Theorems
De Morgan has suggested two theorems which are extremely useful in Boolean
Algebra. The two theorems are discussed below.

Theorem 1

 The left hand side (LHS) of this theorem represents a NAND gate with inputs A
and B, whereas the right hand side (RHS) of the theorem represents an OR
gate with inverted inputs.
 This OR gate is called as Bubbled OR.

Table showing verification of the De Morgan's first theorem −

Theorem 2

 The LHS of this theorem represents a NOR gate with inputs A and B, whereas
the RHS represents an AND gate with inverted inputs.
 This AND gate is called as Bubbled AND.

Table showing verification of the De Morgan's second theorem −

Boolean Expression ⁄ Function

Boolean algebra deals with binary variables and logic operation. A Boolean
Function is described by an algebraic expression called Boolean expression which
consists of binary variables, the constants 0 and 1, and the logic operation symbols.
Consider the following example.
Here the left side of the equation represents the output Y. So we can state equation
no. 1

Truth Table Formation

A truth table represents a table having all combinations of inputs and their
corresponding result.
It is possible to convert the switching equation into a truth table. For example,
consider the following switching equation.

The output will be high (1) if A = 1 or BC = 1 or both are 1. The truth table for this
equation is shown by Table (a). The number of rows in the truth table is 2 n where n
is the number of input variables (n=3 for the given equation). Hence there are 2 3 = 8
possible input combination of inputs.

Methods to simplify the Boolean function

The methods used for simplifying the Boolean function are as follows −

 Karnaugh-map or K-map, and

 NAND gate method.

Karnaugh-map or K-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. For a
higher number of variables, there is another method used for simplification called
the Quine-McClusky method. 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 24. 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
The number of cells in 2 variable K-map is four, since the number of variables is two.
The following figure shows 2 variable K-Map.

 There is only one possibility of grouping 4 adjacent min terms.

 The possible combinations of grouping 2 adjacent min terms are {(m 0, m1), (m2,
m3), (m0, m2) and (m1, m3)}.

3 Variable K-Map
The number of cells in 3 variables K-map is eight, since the number of variables is
three. The following figure shows 3 variables K-Map.
  There is only one possibility of grouping 8 adjacent min terms.
 The possible combinations of grouping 4 adjacent min terms are {(m 0, m1, m3,
m2), (m4, m5, m7, m6), (m0, m1, m4, m5), (m1, m3, m5, m7), (m3, m2, m7, m6) and (m2,
m0, m6, m4)}.
 The possible combinations of grouping 2 adjacent min terms are {(m 0, m1), (m1,
m3), (m3, m2), (m2, m0), (m4, m5), (m5, m7), (m7, m6), (m6, m4), (m0, m4), (m1, m5),
(m3, m7) and (m2, m6)}.
 If x=0, then 3 variable K-map becomes 2 variable K-map.

4 Variable K-Maps
The number of cells in 4 variables K-map is sixteen, since the number of variables is
four. The following figure shows 4 variables K-Map.

 There is only one possibility of grouping 16 adjacent min terms.

 Let R1, R2, R3 and R4 represents the min terms of first row, second row, third
row and fourth row respectively. Similarly, C 1, C2, C3 and C4 represents the min
terms of first column, second column, third column and fourth column
respectively. The possible combinations of grouping 8 adjacent min terms are
{(R1, R2), (R2, R3), (R3, R4), (R4, R1), (C1, C2), (C2, C3), (C3, C4), (C4, C1)}.
 If w=0, then 4 variable K-map becomes 3 variable K-map.
.

Minimization of Boolean Functions using K-Maps

Sum of Products (SOP) Form
It is in the form of sum of three terms AB, AC, BC with each individual term is a
product of two variables. Say A.B or A.C etc. Therefore such expressions are known
as expression in SOP form. The sum and products in SOP form are not the actual
additions or multiplications. In fact they are the OR and AND functions. In SOP form,
0 represents a bar and 1 represents an unbar. SOP form is represented by .
Given below is an example of SOP.

Follow these rules for simplifying K-maps in order to get standard sum of products
form.
 Select the respective K-map based on the number of variables present in the
Boolean function.
 If the Boolean function is given as sum of min terms form, then place the ones
at respective min term cells in the K-map. If the Boolean function is given as
sum of products form, then place the ones in all possible cells of K-map for
which the given product terms are valid.
 Check for the possibilities of grouping maximum number of adjacent ones. It
should be powers of two. Start from highest power of two and upto least
power of two. Highest power is equal to the number of variables considered
in K-map and least power is zero.
 Each grouping will give either a literal or one product term. It is known
as prime implicant. The prime implicant is said to be essential prime
implicant, if atleast single ‘1’ is not covered with any other groupings but only
that grouping covers.
 Note down all the prime implicants and essential prime implicants. The
simplified Boolean function contains all essential prime implicants and only
the required prime implicants.

Example
Let us simplify the following Boolean function,
f(W,X,Y,Z) = WX’Y’ + WY + W’YZ’ using K-map.
The given Boolean function is in sum of products form. It is having 4 variables W, X,
Y & Z. So, we require 4 variable K-map. The 4 variable K-map with ones
corresponding to the given product terms is shown in the following figure.

Here, 1s are placed in the following cells of K-map.

 The cells, which are common to the intersection of Row 4 and columns 1 & 2
are corresponding to the product term, WX’Y’.
 The cells, which are common to the intersection of Rows 3 & 4 and columns 3
& 4 are corresponding to the product term, WY.
 The cells, which are common to the intersection of Rows 1 & 2 and column 4
are corresponding to the product term, W’YZ’.
There are no possibilities of grouping either 16 adjacent ones or 8 adjacent ones.
There are three possibilities of grouping 4 adjacent ones. After these three
groupings, there is no single one left as ungrouped. So, we no need to check for
grouping of 2 adjacent ones. The 4 variable K-map with these three groupings is
shown in the following figure.

Here, we got three prime implicates WX’, WY & YZ’. All these prime implicates
are essential because of following reasons.
 Two ones (m8 & m9) of fourth row grouping are not covered by any other
groupings. Only fourth row grouping covers those two ones.
 Single one (m15) of square shape grouping is not covered by any other
groupings. Only the square shape grouping covers that one.
  Two ones (m2 & m6) of fourth column grouping are not covered by any other
groupings. Only fourth column grouping covers those two ones.
Therefore, the simplified Boolean function is
f = WX’ + WY + YZ’

Product of Sums (POS) Form

It is in the form of product of three terms (A+B), (B+C), or (A+C) with each term is in
the form of a sum of two variables. Such expressions are said to be in the product of
sums (POS) form. In POS form, 0 represents an unbar and 1 represents a bar. POS
form is represented by .
Given below is an example of POS.

Follow these rules for simplifying K-maps in order to get standard product of sums
form.
 Select the respective K-map based on the number of variables present in the
Boolean function.
 If the Boolean function is given as product of Max terms form, then place the
zeroes at respective Max term cells in the K-map. If the Boolean function is
given as product of sums form, then place the zeroes in all possible cells of K-
map for which the given sum terms are valid.
 Check for the possibilities of grouping maximum number of adjacent zeroes. It
should be powers of two. Start from highest power of two and upto least
power of two. Highest power is equal to the number of variables considered
in K-map and least power is zero.
 Each grouping will give either a literal or one sum term. It is known as prime
implicant. The prime implicant is said to be essential prime implicant, if
atleast single ‘0’ is not covered with any other groupings but only that
grouping covers.

Example
Let us simplify the following Boolean function,
f(X,Y,Z)=∏M(0,1,2,4)f(X,Y,Z)=∏M(0,1,2,4) using K-map.
The given Boolean function is in product of Max terms form. It is having 3 variables
X, Y & Z. So, we require 3 variables K-map. The given Max terms are M 0, M1, M2 & M4.
The 3 variable K-map with zeroes corresponding to the given Max terms is shown in
the following figure.

There are no possibilities of grouping either 8 adjacent zeroes or 4 adjacent zeroes.

There are three possibilities of grouping 2 adjacent zeroes. After these three
groupings, there is no single zero left as ungrouped. The 3 variable K-map with
these three groupings is shown in the following figure.

Here, we got three prime implicants X + Y, Y + Z & Z + X. All these prime implicants
are essential because one zero in each grouping is not covered by any other
groupings except with their individual groupings.
Therefore, the simplified Boolean function is
f = X+YX+Y.Y+ZY+Z.Z+X

NAND gates Realization

NAND gates can be used to simplify Boolean functions as shown in the example
below.