Chapter - 4 Boolean Algebra and Logic Gate

Boolean Algebra and Logic Gate

Introduction:

·         The algebra of logic, which deals with the study of binary variables and logical operations is called Boolean Algebra.

·         Today, it is the backbone of design and analysis of computer and other digital circuits.

·         They are useful not only to the hardware design in implementing circuits, but also to software designer in making decision and for many tasks.

·         In Boolean algebra the variables are permitted to have two values. They are

a)       Logic 1 ( i. e. on / yes / true / high)

b)      Logic 0 ( i. e. off / no / false / low)

Boolean Variables(Logical Variables):

The variables that have only two values 1 and 0 are called Boolean Variables or Logical Variables. These variables are denoted by A, B, X, Y etc.

Truth Table:

A table which represents the input output relationships of the binary variables for each gate is called Truth Table. It shows the relation between all inputs outputs in tabular form. Thus, a truth table is a table representing the results of the logical operations on all possible combinations of logical values.

Boolean Expression (Boolean Function)

An expression formed by binary variables, binary operators (AND, OR, NOT) , parenthesis and equal sign is called Boolean Expression or Boolean Function. For a given value of the variables, the function can be either 0 or 1.

For Example: Z = X.Y

Logic Gate:

An electronic circuit that operates on one or more input signals to produce an output signal is called logic gate. The logic gate is used for binary operation and is the basic component of digital computer. Each gate has its specific function and graphical symbol.

There are 3 basic gates:      1) AND gate                        2) OR gate                    3) NOT gate

From the combination of these 3 basic gates, we can get other derived gates, which are:

4) NAND gate                          5) NOR gate                6) Exclusive – OR (XOR) gate    

7) Excusive – NOR (XNOR) gate

1.       AND gate:

An electronic circuit which produces high(1) output when all inputs are high(1) otherwise, produces the output low (0) is called AND gate. The output of AND gate is equal to the product of the logic inputs. It can have two or more inputs and produces only one output.

Name	Graphical Symbol	Algebraic Function	Truth Table

2.       OR gate

An electronic circuit which produces high (1) output when all inputs are high (1) or any one of input is high (1) and produces output low (0) when all inputs are low (0) is called OR gate. The output of the OR gate is equal to the sum of the logic inputs. It has two or more inputs and produces only one output.

Name	Graphical Symbol	Algebraic Function	Truth Table

3.       NOT gate (Inverter)

An electronic circuit whose output is the complement of the input is called NOT gate. It is also called an inverter.  If we   provide high (1) input to NOT gate, it will produce low (0) output and vice- versa. It has only one input and only one output.

Name	Graphical Symbol	Algebraic Function	Truth Table

4.       NAND gate

The gate which is formed by the combination of AND gate and NOT gate is called NAND gate. NAND gate produces low (0) output, when all inputs are high (1); otherwise, produces high (1) output. It is the complement of the AND gate. It has two or more inputs and only one output.

Name	Graphical Symbol	Algebraic Function	Truth Table

5.       NOR gate

The gate which is formed by the combination of OR gate and NOT gate is called NOR gate. NOR gate produces high (1) output, when all inputs are low (0); otherwise, output will be low (0). It is the complement of OR gate. It has two or more inputs and only one output.

Name	Graphical Symbol	Algebraic Function	Truth Table

6.       Exclusive – OR (XOR) gate

The XOR gate produces low output (0) when the both inputs are same; otherwise, the output will be high (1). It can also have two or more inputs and only one output.

Name	Graphical Symbol	Algebraic Function	Truth Table

7.       Exclusive- NOR (XNOR) gate

The XNOR gate is equivalent to an XOR gate followed by an inverter. This gate produces high(1) output when all inputs are either low(0) or high(1). It can also have two or more inputs and a single output.

Name	Graphical Symbol	Algebraic Function	Truth Table

# Duality Principle:

Dual of a Boolean expression is derived by

1.       Replacing AND operation by OR

2.       Replacing OR operation by AND

3.       All 1’s are changed to 0

4.       All 0’s are changed to 1

5.       Variables and complements are left unchanged.

For Example:

F=(X’.1).(0+X) , Here dual of F= (X’+0)+(1.X)

# Laws of Boolean algebra- Associative, Commutative, Distributive, Identity, Complement Law:

1.       Associative Laws:

The associative law of Boolean algebra is expressed by:

* (A+B)+C=A+(B+C)

* (A.B).C=A.(B.C)

Proof for (A+B)+C=A+(B+C)

Truth Table:

Inputs				Output 1		Output 2
A	B	C	A+B	(A+B)+C	B+C	A+(B+C)
0	0	0	0	0	0	0
0	0	1	0	1	1	1
0	1	0	1	1	1	1
0	1	1	1	1	1	1
1	0	0	1	1	0	1
1	0	1	1	1	1	1
1	1	0	1	1	1	1
1	1	1	1	1	1	1

Conclusion:

Comparing the values of (A+B)+C and A+(B+C) from truth table, since ,both are equal. Hence, Proved.

2.       Commutative Laws:

The commutative law of Boolean algebra is expressed by:

            * (A+B)=(B+A)

            * (A.B)=(B.A)

Proof for (A+B)=(B+A)

Truth Table:

Inputs		Output 1	Output 2
A	B	A+B	(B+A)
0	0	0	0
0	1	1	1
1	0	1	1
1	1	1	1

Conclusion:

Comparing the values of (A+B) and (B+A) from truth table, since, both are equal. Hence, proved.

3.       Distributive Laws:

A distributive law of Boolean algebra is expressed by:

* A.(B+C)=(A.B)+(A.C)

* A+(B.C)=(A+B).(A+C)

Proof for a. (B+C)=(A.B)+(A.C)

Truth Table:

				Output 1			Output 2
A	B	C	B+C	A.(B+C)	A.B	A.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	1	0	1	1
1	1	0	1	1	1	0	1
1	1	1	1	1	1	1	1

Conclusion:

Comparing the values of A.(B+C) and (A.B)+(A.C) from truth table, since ,both are equal. Hence, Proved.

1.       Identity Laws:

The identify law of Boolean algebra is expressed by:

* A+0 = A    and A.1=A

Proof for A+0=A

Truth Table

Inputs		Output
A	0	A+0
0	0	0
1	0	1

Conclusion:

Hence from the truth table the output will be same as the input.

2.       Complement Laws:

The complement law of Boolean algebra is expressed by:

* A+A’=1       and  A.A’=0

Proof for A+A’=1

Truth Table:

Inputs		Output
A	A’	A+A’
0	1	1
1	0	1

Conclusion:

Hence from the truth table the sum of an input and its complement will always be true (1).

Universal gate (NAND and NOR gate):

NAND Gate:

NOR gate:

# De Morgan’s Theorem:

First Theorem:

The De Morgan’s first theorem states that “The complement of a sum equals to the product of the complements of individual”. i.e. (A+B)’=A’.B’

Truth Table:

Inputs			Output 1			Output 2
A	B	(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

Conclusion:

Comparing the values of (A+B)’ and A’.B’ from the truth table, both are equal, hence, proved.

Second Theorem:

The De Morgan’s first theorem states that “The complement of a product is  equal to the sum of the complements of individual”. i.e. (A.B)’=A’+B’

Truth Table:

Inputs			Output 1			Output 2
A	B	(A.B)	(A.B)’	A’	B’	A’+B’
0	0	0	1	1	1	1
0	1	0	1	1	0	1
1	0	0	1	0	1	1
1	1	1	0	0	0	0

Conclusion:

Comparing the values of (A.B)’ and A’+B’ from the truth table, both are equal, hence, proved.

# Venn Diagram:

Venn diagram is the diagram in which areas represents operations of logic gates.

Homework [Unit-4]

1.     Describe the De Morgan’s Law.

2.     Define Boolean algebra. Explain AND, OR , NAND and X-OR gate with truth table and logic gate.

3.     Describe any four logic gates with truth table and gate symbol.

4.     Differentiate between OR and AND gate.