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 a certain logic. Based on this, logic gates are named as AND gate, OR gate, NOT gate etc.

AND Gate

A circuit which performs an AND operation is shown in figure. It has n input (n >= 2) and one output.

Logic diagram

Truth Table

OR Gate

A circuit which performs an OR operation is shown in figure. It has n input (n >= 2) and one output.

Logic diagram

Truth Table

NOT Gate

NOT gate is also known as Inverter. It has one input A and one output Y.

Logic diagram

Truth Table

NAND Gate

A NOT-AND operation is known as NAND operation. It has n input (n >= 2) and one output.

Logic diagram

Truth Table

NOR Gate

A NOT-OR operation is known as NOR operation. It has n input (n >= 2) and one output.

Logic diagram

Truth Table

XOR Gate

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

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

Laws of Boolean Algebra

Boolean Algebra uses a set of Laws and Rules to define the operation of a digital logic circuit  

As well as the logic symbols “0” and “1” being used to represent a digital input or output, we can also use them as constants for a permanently “Open” or “Closed” circuit or contact respectively.

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 analyse 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 of these individual laws of Boolean, rules and theorems for Boolean Algebra are given in the following table.

Truth Tables for the Laws of Boolean

Switching CircuitBoolean Algebra
Law or Rule A + 1 = 1 A in parallel with
closed = “CLOSED”

AnnulmentA + 0 = AA in parallel with
open = “A”

IdentityA . 1 = AA in series with
closed = “A”

IdentityA . 0 = 0A in series with
open = “OPEN”

AnnulmentA + A = AA in parallel with
A = “A”

IdempotentA . A = AA in series with
A = “A”

IdempotentNOT A = ANOT NOT A
(double negative) = “A” Double NegationA + A = 1A in parallel with
NOT A = “CLOSED”

ComplementA . A = 0A in series with
NOT A = “OPEN”

ComplementA+B = B+AA in parallel with B =
B in parallel with A

CommutativeA.B = B.AA in series with B =
B in series with A

The basic Laws of Boolean Algebra that relate to the Commutative Law allowing a change in position for addition and multiplication, the Associative Law allowing the removal of brackets for addition and multiplication, as well as the Distributive Law allowing the factoring of an expression, are the same as in ordinary algebra.

Each of the Boolean Laws above are given with just a single or two variables, but the number of variables defined by a single law is not limited to this as there can be an infinite number of variables as inputs too the expression. These Boolean laws detailed above can be used to prove any given Boolean expression as well as for simplifying complicated digital circuits.

A brief description of the various Laws of Boolean are given below with A representing a variable input.

Description of the Laws of Boolean Algebra

• de Morgan´s Theorem – There are two “de Morgan´s” rules or theorems,
• (1) Two separate terms NOR´ed together is the same as the two terms inverted (Complement) and AND´ed for example:  A+B = A . B
• (2) Two separate terms NAND´ed together is the same as the two terms inverted (Complement) and OR´ed for example:  A.B = A + B

Karnaugh Map

In this tutorial we will learning about Karnaugh Map.

We know that truth table is used to represent values of aboolean function. Similarly, Karnaugh map is another way of representing the values of aboolean function. So, K-map is a table consisting of cells which represents a Minterm or Maxterm. Karnaugh map or K-map is named after Mayrice Karnough.

Karnaugh Map for Sum of Products

For SOP or Sum of Products, each cells in a K-map represents a Minterm. If there are n variables for a given boolean function then, the K-map will have 2ⁿ cells. And we fill the cells with 1s whose Minterms output is 1. Lets check the K-map for 2, 3 and 4 variables.

2 variables K-map for Sum of Products

Say we have two variables X and Y then, there will be 2² = 4 cells in the K-map.

Each cell has a subscripted number at the bottom right corner. It is the value of the minterm. So, if a cell has number 2 then it represent minterm m₂.

3 variables K-map for Sum of Products

Say we have three variables X, Y and Z then there will be 2³ = 8 cells in the K-map.

Each cell has a subscripted number at the bottom right corner it is the value of the minterm. So, if a cell has number 7 then it represent minterm m₇.

Now if we look at the above K-map we will see that the numbering scheme is 0, 1, 3, 2 in the first row and 4, 5, 7, 6 in the second row. So, the numbers differ in one place when moving from left to right.

00, 01, 11, 10 this is done so that only one variable change at a time from complement to un-complement or un-complement to complement every row.

Example, in the first row we have X’Y’Z’, X’Y’Z, X’YZ and X’YZ’ so, only one variable change at a time as we move from left to right.

1st row: moving left to right cell-wise
X’Y’Z’ —> X’Y’Z [Z’ changed to Z]
X’Y’Z —> X’YZ [Y’ changed to Y]
X’YZ —> X’YZ’ [Z changed to Z’]

4 variables K-map for Sum of Products

Say we have four variables W, X, Y and Z then there will be 2⁴ = 16 cells in the K-map.

Each cell has a subscripted number at the bottom right corner. It is the value of the minterm. So, if a cell has number 12 then, it represent minterm m₁₂.

And in this case the numbering scheme is 0, 1, 3, 2 in the first row 4, 5, 7, 6 in the second row 12, 13, 15, 14 in the third row and 8, 9, 11, 10 in the fourth row.

How to fill values in the K-map for Sum of Products?

Say we have a boolean function F defined on two variables A and B and F = 1 i.e., output is 1 only when exactly one of the input is 1. So, we can draw the following truth table with all possible input and output values.

To express F using Minterm shorthand notation we have to consider only those minterms for which F = 1.

F = m₁ + m₂

This can also be written as
F = ∑(1, 2)

Now, we have F = m₁ + m₂ = ∑(1, 2)
Draw an empty K-map having 4 cells (since there are 2 variables so 2₂ = 4 cells).

F = m₁ + m₂
So, fill the cells marked with subscript 1 and 2 with value 1. And fill rest of the cells of the K-map with value 0.

In a similarly way we can fill 3 and 4 variables K-map.

Karnaugh Map for Product of Sums

For POS each cells in a K-map represents a Maxterm. If there are n variables for a given boolean function then the K-map will have 2n cells. And we fill the cells with 0s whose Maxterm output is 0. Lets check the K-map for 2, 3 and 4 variables.

2 variables K-map for Product of Sums

Say we have two variables X and Y then there will be 2² = 4 cells in the K-map.

Each cell has a subscripted number at the bottom right corner. It is the value of the maxterm. So, if a cell has number 2 then, it represent maxterm M₂.

3 variables K-map for Product of Sums

Say we have three variables X, Y and Z then there will be 2³ = 8 cells in the K-map. So, if a cell has number 0 then it represent maxterm M₀.

Now if we look at the above K-map we will see that the numbering scheme is 0, 1, 3, 2 in the first row and 4, 5, 7, 6 in the second row. So, the numbers differ in one place when moving from left to right.

00, 01, 11, 10 this is done so that only one variable change at a time from complement to un-complement or un-complement to complement every row.

Example, in the first row we have X+Y+Z, X+Y+Z’, X+Y’+Z’ and X+Y’+Z so, only one variable change at a time as we move from left to right.

1st row: moving left to right cell-wise
X+Y+Z —> X+Y+Z’ [Z changed to Z’]
X+Y+Z’ —> X+Y’+Z’ [Y changed to Y’]
X+Y’+Z’ —> X+Y’+Z [Z’ changed to Z]

4 variables K-map for Product of Sums

Say we have four variables W, X, Y and Z then there will be 2⁴ = 16 cells in the K-map.

Each cell has a subscripted number at the bottom right corner. It is the value of the maxterm. So, if a cell has number 15 then it represent maxterm M_15.

And in this case the numbering scheme is 0, 1, 3, 2 in the first row 4, 5, 7, 6 in the second row 12, 13, 15, 14 in the third row and 8, 9, 11, 10 in the fourth row.

How to fill values in the K-map for Product of Sums

Say we have a boolean function F defined on two variables A and B and F = 1 i.e., output is 1 only when exactly one of the input is 1. So we can draw the following truth table with all possible input and output values.

To express F using Maxterm shorthand notation we have to consider only those maxterms for which F = 0.

F = M₀ . M₃

This can also be written as
F = ∏(0, 3)

Now that we have F = M₀ . M₃ = ∏(0, 3).

Draw an empty K-map having 4 cells (since there are 2 variables so 2² = 4 cells)

F = M₀ . M₃
So, fill the cells marked with subscript 0 and 3 with value 0. And fill rest of the cells of the K-map with value 1.

In a similarly way we can fill 3 and 4 variables K-map.