Unit-2

Logic Gates and Simplification

Positive Logic and Negative Logic

Positive Logic

In positive logic, the higher voltage level represents binary 1 (TRUE) and the lower voltage
level represents binary 0 (FALSE).

Example

Voltage Level Binary Value

+5V 1
0V 0

So when the signal is HIGH, the system interprets it as logic 1.

Positive logic is the most commonly used logic convention in digital electronics.

Negative Logic

In negative logic, the interpretation of voltage levels is reversed.

The higher voltage level represents binary 0, and the lower voltage level represents binary 1.

Example

Voltage Level Binary Value

+5V 0
0V 1

Negative logic is used in some special circuit designs and control systems.

Logic Gates
Logic gates are the fundamental building blocks in digital electronics.
 Used to perform logical operations based on the inputs provided to it and gives a logical
output that can be either high(1) or low(0).
 The operation of logic gates is based on Boolean algebra, or mathematics.
 There are basically seven main types of logic gates that are used to perform various
logical operations in digital systems.
 By combining different logic gates, complex operations are performed, and circuits like
flip-flops, counters, and processors are designed. In this article, we will see various types
of logic gates in detail.
 Logic gates find their uses in our day-to-day lives, such as in the architecture of our
telephones, laptops, tablets and memory devices.
Types of Logic Gates
Logic gates can be broadly classified into three main categories :

[Link] gates
AND GATE
An AND gate is used to perform logical Multiplication of binary input. The Output state of
the AND gate will be high (1) if both the input is high (1), else the output state will be low(0)
if any of the input is low (0).
X = A.B
The value of X will be True when both the inputs will be True.

Properties of AND Gate

The following are two main properties of the AND gate:

1. AND gate can accept two or more than two input values at a time.
2. When all of the inputs are logic 1, the output of this gate is logic 1.
OR GATE
OR GATE is most widely used digital logic circuit. The output state of OR gate will be high
i.e., (1) if any of the input state is high or 1, else output state will be low i.e., 0.
The Boolean Expression for the OR gate is the logical addition of inputs denoted by plus sign
(+) as
X= A+B
The value of X will be high(true) when one of the inputs is set to high (true).

Properties of OR Gate

An OR gate have the following two properties:

1. It can have two or more input lines at a time.
2. When all of the inputs to the OR gate are low or logic 0, the output of it is low or logic 0.
NOT GATE
In digital electronics, the NOT gate is one of the basic Logic Gate having only a single input
and a single output. It is also known as inverter or inverting buffer. When the input signal is
"low" the output signal is "high" and vice-versa.
The Boolean expression of NOT Gate is as follows
Y = Ā or
Y = A’
the value of Y will be high when A will be low.
Properties of NOT Gate

 The output of a NOT gate is complemented or inverse of the input applied to it.
 NOT gate takes only one output.

[Link] gates
NOR GATE
The NOR gate is the type of universal logic gate. It takes two or more inputs and gives only
one output. The output state of the NOR gate will be high (1) when all the inputs are low
(0). NOR gate returns the complement result of the OR gate. It is basically a combination of
two basic logic gates i.e., OR gate and NOT gate.
The Boolean expression of NOR gate is as follows:
If A and B are considered as two inputs, and O as output, then the expression for a two input
NOR gate will be
O = (A + B)’
The value of O will be true when all of its inputs are set to 0.

Properties of NOR Gate

The following are two important properties of NOR gate:

1. A NOR gate can have two or more inputs and gives an output.
2. A NOR gate gives a high or logic 1 output only when it's all inputs are low or logic 0.
NAND GATE
The NAND Gate is another type of Universal logic gate. The NAND gate or "Not AND" is
the combination of two basic logic gates AND gate and the NOT gate connected in series. It
takes two or more inputs and gives only one output. The output of the NAND gate will give
result high (1) when either of its input is high (1) or both of its input are low (0). In simple, it
performs the inverted operation of AND gate.
The Boolean Expression of NAND Gate is as follows
Say we have two inputs, A and B and the output is called X, then the expression is
X = (A. B)’

Properties of NAND Gate

The following are the two key properties of NAND Gate

 NAND gate can take two or more inputs at a time and produces one output based on the
combination of inputs applied.
 NAND gate produces a low or logic 0 output only when its all inputs are high or logic 1.

[Link] gates
XOR GATE
In digital electronics, there is a specially designed logic gate named, XOR gate, which is used
in digital circuits to perform modulo sum. It is also referred to as Exclusive OR gate or Ex-
OR gate. it is used extensively in arithmetic logic circuits., logic comparators and error
detection circuits. The XOR gate can take only two inputs at a time and give an output. The
output of the XOR gate is high (1) only when its two inputs are dissimilar i.e., if one of them
is low (0) then other one will be high (1).
Say we have two inputs, A and B and the output is called X, then the expression is
The Boolean expression of XOR Gate is as follows
X = A’B + AB’

Properties of XOR Gate

The following two are the main properties of the XOR gate:
 It can accept only two inputs at a time. There is nothing like a three or more input XOR
gate.
 The output of the XOR gate is logic 1 or high, when its inputs are dissimilar.
XNOR GATE
The XNOR is the combination of XOR gate and NOT gate. The output of the XNOR gate is
high(1) when both the inputs are high (1) or low(0). In other words, the output of the XNOR
gate is high(1) when both the inputs are the same. the XNOR gate can sometimes be called as
Equivalence gate. In simple words, The XNOR gate is the complement of the XOR gate.
The following is the Boolean expression of the XNOR gate,
Y=A⊙B
Here, A and B are the input variables and Y is the output variable.
This expression can also be written as follows,
Y = AB + A’B’
We can also express the operation of an XNOR gate using XOR gate logic as follows:
Y = (A ⊕ B)’

Properties of XNOR Gate

The following are two key properties of XNOR gate:

 XNOR gate takes only two inputs and produces one output.
 The output of the XNOR gate is high or logic 1 only when it has similar inputs.

What is Boolean Algebra?

Boolean algebra is a branch of mathematics that deals with binary variables (0 and 1) and
logical operations. It was introduced by George Boole in 1854 and later applied to digital
circuits by Claude Shannon in 1938.

Basic Postulates
The postulates are the basic assumptions or axioms on which Boolean algebra is built

2. Identity Elements

There exist two distinct identity elements 0 and 1 such that:

Law OR (+) AND (·)

Identity A + 0 = A A · 1 = A

Meaning:

 0 is the identity for OR → Adding 0 doesn't change the value

 1 is the identity for AND → Multiplying by 1 doesn't change the value

Example:

 1 + 0 = 1, 0 + 0 = 0
 1 · 1 = 1, 0 · 1 = 0

3. Commutative Law

The order of variables does not affect the result.

Operation Law
OR A+B=B+A
AND A·B=B·A

Example:

 1+0=0+1=1
 1·0=0·1=0

Logic Gate meaning: Swapping inputs of an AND/OR gate gives the same output.

4. Distributive Law

One operation distributes over the other.

Law Expression
AND over OR A · (B + C) = (A · B) + (A · C)
OR over AND A + (B · C) = (A + B) · (A + C)

Example (AND over OR):

 A=1, B=0, C=1

 LHS: 1 · (0+1) = 1 · 1 = 1
 RHS: (1·0) + (1·1) = 0 + 1 = 1
5. Complement Law

For every element A, there exists a complement Ā (NOT A) such that:

Law Expression
OR with complement A + Ā = 1
AND with complement A · Ā = 0

Meaning:

 A variable OR'd with its complement is always 1

 A variable AND'd with its complement is always 0

Example:

 If A = 1, then Ā = 0 → 1 + 0 = 1
 If A = 0, then Ā = 1 → 0 · 1 = 0

6. Associative Law

(Often added as an extension of Huntington's postulates)

Grouping of variables does not affect the result.

Operation Law
OR A + (B + C) = (A + B) + C
AND A · (B · C) = (A · B) · C

Example:

 1 + (0 + 1) = (1 + 0) + 1 = 1

What is DeMorgan's Theorem?

DeMorgan's Theorem is a powerful theorem in Boolean algebra which has a set of two rules
or laws. These two laws were developed to show the relationship between two variable AND,
OR, and NOT operations. These two rules enable the variables to be negated, i.e. opposite of
their original form. Therefore, DeMorgan's theorem gives the dual of a logic function.

Now, let us discuss the two laws of DeMorgan's theorem.

DeMorgan's First Theorem (Law 1)

DeMorgan's First Law states that the complement of a sum (ORing) of variables is equal to
the product (ANDing) of their individual complements. In other words, the complement of
two or more ORed variables is equivalent to the AND of the complements of each of the
individual variables, i.e.

A+ B = A . B

Or, it may also be represented as,

⟮A+B⟯′=A′⋅B′

The logic implementation of left side and right side of this law is shown in Figure 1.

Thus, DeMorgan's first law proves that the NOR gate is equivalent to a bubbled AND gate.
The following truth table shows the proof of this law.

Left Side Right Side

Input Output Input Output
A B (A + B)' A' B' A'· B'
0 0 1 1 1 1
0 1 0 1 0 0
1 0 0 0 1 0
1 1 0 0 0 0

This truth table proves that the Boolean expression on the left is equivalent to that on the
right side of the expression of DeMorgan's first law.
DeMorgan's Second Theorem (Law 2)

DeMorgan's second law states that the complement of the product (ANDing) of variables is
equivalent to the sum (ORing) of their individual complements.

In other words, the complement of two or more ANDed variables is equal to the sum of the
complement of each of the individual variables, i.e.,

A . B= A+B

It may also be represented as,

⟮AB⟯′=A′+B′

The logic implementation of left and right sides of this expression is shown in Figure 2.

Hence, De Morgan's second law proves that the NAND gate is equivalent to a bubbled OR
gate. The following truth table shows the proof of this law.

Left Side Right Side

Input Output Input Output
A B AB A' B' A' + B'
0 0 0 1 1 1
0 1 1 1 0 1
1 0 1 0 1 1
1 1 1 0 0 0

This truth table proves that the Boolean expression on the left side is equivalent to that on the
right side of the expression of DeMorgan's second law.

Implementation of Boolean (logic) equation with gates

1. F=(y'z'+x'y'z')(xy'z+y')
2. F=A'B'C+A

3. F=(x'+y')(x'+y)(y'+x)

4. F=(A+B)(B'+A')A'B
 5. F=x'+y'+(x'+y')(x'+y)

6. F=ABC(B+AB'C)

Introduction of K-Map (Karnaugh Map)

In numerous digital circuits and other practical problems, finding expressions that have
minimum variables becomes a prerequisite. In such cases, minimisation of Boolean
expressions is possible that have 3, 4 variables. It can be done using the Karnaugh map
 without using any theorems of Boolean algebra. The K-map can easily take two forms,
namely, Sum of Product or SOP and Product of Sum or POS, according to what we need in
the problem. K-map is a representation that is table-like, but it gives more data than the
TRUTH TABLE. Fill a grid of K-map with 1s and 0s, then solve it by creating various
groups.

here are following two methods of minimizing or reducing the boolean expressions-

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-01:

 We can either group 0’s with 0’s or 1’s with 1’s but we can not group 0’s and 1’s together.
 X representing don’t care can be grouped with 0’s as well as 1’s.

NOTE
There is no need of separately grouping X’s i.e. they can be ignored if all 0’s and 1’s are already grouped.

Rule-02:

 Groups may overlap each other.

Rule-03:
 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.

Example-

Rule-04:

 Groups can be only either horizontal or vertical.

 We can not create groups of diagonal or any other shape.

Rule-05:

 Each group should be as large as possible.

Example-
 Rule-06:

 Opposite grouping and corner grouping are allowed.

 The example of opposite grouping is shown illustrated in Rule-05.
 The example of corner grouping is shown below.

Example-

Rule-07:

 There should be as few groups as possible.

Solving an Expression Using K-Map

Here are the steps that are used to solve an expression using the K-map method:
1. Select a K-map according to the total number of variables.

2. Identify maxterms or minterms as given in the problem.

3. For SOP, put the 1’s in the blocks of the K-map with respect to the minterms (elsewhere
0’s).

4. For POS, putting 0’s in the blocks of the K-map with respect to the maxterms (elsewhere
1’s).

5. Making rectangular groups that contain the total terms in the power of two, such as 2,4,8 ..
(except 1) and trying to cover as many numbers of elements as we can in a single group.

6. From the groups that have been created in step 5, find the product terms and then sum them
up for the SOP form.

SOP FORM(Sum of Product Form)

SOP form is way to simplify and write Boolean expressions using AND to combine inputs
and OP to combine the results.

1. K-map for 2 variables

The number of cells in 2 variable K-map is four (2 2) 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)}.

Reduce the function using K-map F(A,b) = Σ(0,2,3)

Simplify the function using Karnaugh Map F(x,y)= Σ(0,1,3)

2. K-map of 3 variables
The number of cells in 3 variable K-map is eight (23), since the number of
variables is three. The following figure shows 3 variable K-Map.

• There is only one possibility of grouping 8 adjacent min terms.

Reduce the function y(A,B,C) = Σ (0,1,3,6,7)

Solution
Here the 3 variable as in the function so we draw 3 variable k-map and fill ones
in the given minterms

Problem: 73
Reduce the given function y = Σ (4,5,7)

Solution:

Here the 3 variable we use 3 variable k-map and put ones in the k-map

Simplify the sop function F(A,B,C) = Σ (1,2,3,7)

Solution:
Simply the sop function F(A,B,C) = Σ (1,3,5,7)

Solution:

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

From red group we get product term:

A’C
From green group we get product term:
AB
Summing these product terms we get- Final expression (A’C+AB)
3. K-map for 4 variables
The number of cells in 4 variable K-map is sixteen (2 4), since the number of
variables is four. The following figure shows 4 variable K-Map.

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

[Link] the given function F(A,B,C,D) = Σ (1,2,3,5,8,10,11,12)

Solution:

In this problem 4 variable is given use 4 variable k-map

[Link] the following using karnaugh map f (A, B, C, D) =

Σm (0,1,4,8,9,10)

Solution:
POS FORM (Product of Sum Form)
POS form is a way to simplify and write Boolean expressions using OR to combine terms
inside parentheses and then AND to combine those groups.

1.K-map of 2 variables

In the 2 variable k-map, four squares are constructed. Each square contains one term of
expression with two variables.
K-map of 2 variables

2. K-map of 3 variables
 K-map 3 variable POS form

F (A,B,C)=ℼ(0,3,6,7)

From red group we find terms

A B
Taking complement of these two
A' B'
Now sum up them
(A' + B')
From brown group we find terms
B C
Taking complement of these two terms
B’ C’
Now sum up them
(B’+C’)
From yellow group we find terms
A' B' C’
Taking complement of these two
ABC
Now sum up them
(A + B + C)

We will take product of these three terms : Final expression -

(A' + B’) (B’ + C’) (A + B + C)
3. K-map of 4 variables

K-map 4 variable POS form

F(A,B,C,D)=ℼ(3,5,7,8,10,11,12,13)

From green group we find terms

C’ D B
Taking their complement and summing them
(C+D’+B’)
From red group we find terms
C D A’
Taking their complement and summing them
(C’+D’+A)
From blue group we find terms
A C’ D’
Taking their complement and summing them
(A’+C+D)
From brown group we find terms
A B’ C
Taking their complement and summing them
(A’+B+C’)
Finally we express these as product -
(C+D’+B’).(C’+D’+A).(A’+C+D).(A’+B+C’)

Advantages of K-MAP
 Makes Logic Simpler: It makes complicated Boolean expressions simpler.
 Minimizes Logic Gates: Simplifying the logic helps us to use fewer logic gates, making
circuits more efficient.
 Reduce Errors: The visual representation of k-map helps to avoid errors while
simplifying.
 Time-Saving: It's quicker than traditional methods for simplifying logic.
 No need for Boolean Laws: K-map doesn't require deep knowledge of Boolean laws,
making it easy for beginners.
Disadvantages of K-MAP
 Limited to Fewer Variables: K-maps are best suited for 2 to 4 variables and above it,
process becomes hard and complicated to manage.
 Not suitable for all functions: In some cases, its hard to group terms correctly, leading
to errors and making simplification difficult.
 Space Limitations: As the number of variables increases, the K-map grid becomes too
large to handle easily.
 Requires Careful Grouping: Sometimes incorrect grouping of terms can cause mistakes
in logic simplification.