Simplification of Boolean functions

Draft notes or 22C: 040
Simplification of Boolean functions
Using the theorems of Boolean Algebra, the algebraic forms of functions can often be simplified, which leads to simpler (and cheaper) implementations.

Example 1

F = A.B + A.B + B.C = A. (B + B) + B.C = A.1 + B.C = A + B.C

How many gates do you save from this simplification?

A

A

B

F

B

FC

C

2

Example 2

Draft notes or 22C: 040

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

Example 3 Show that A + A.B = A

A + AB = A.1 + A.B = A. (1 + B) = A. 1 =A

3

Draft notes or 22C: 040

Simplification using Karnaugh Maps

A

B

01

1 0 1 K-map of 2-variable OR function

01 1

BC

A

00 01 11 10

0

1

1

1 1 1 K-map of majority function

Follow the class lectures to understand how to simplify Boolean functions using K-maps. Several examples will be worked out in the class.

4

Other types of gates

Draft notes or 22C: 040

A

A

A.B

B

A+B

B

NAND gate

NOR gate

Be familiar with the truth tables of these gates.

A

B

A + B = A.B + A.B

Exclusive OR (XOR) gate

5

Draft notes or 22C: 040
NAND and NOR are universal gates
Any function can be implemented using only NAND or only NOR gates. How can we prove this?
(Proof for NAND gates) Any boolean function can be implemented using AND, OR and NOT gates. So if AND, OR and NOT gates can be implemented using NAND gates only, then we prove our point.

1. Implement NOT using NAND

A

A

6

Draft notes or 22C: 040
2. Implementation of AND using NAND

A

A.B

B

A

1. Implementation of OR using NAND

A

A

B B

A.B = A+B

(Exercise) Prove that NOR is a universal gate.

7

Draft notes or 22C: 040

Example (to be worked out in class) How to convert any circuit that uses AND, OR and NOT gates to a version that uses NAND (or NOR gates only)?

Additional properties of XOR XOR is also called modulo-2 addition. Why?

AB C F 0000 001 1 01 01 01 1 0 1 001 1 01 0 1 1 00 1111

A B = 1 only when there are an odd number of 1’s in (A,B). The same is true for A B C also.

1 A=A 0 A=A

Why?

8

Draft notes or 22C: 040

Logic Design Exercise

Half Adder

A

Half

Sum (S)

Adder

B

Carry (C)

S=A B C = A.B

AB SC 0000 01 1 0 1 01 0 1 1 01

A S
B C

9

Draft notes or 22C: 040

Full Adder

Sum (S)

A B C S Cout

A

Full

B Adder

00000 001 1 0

Cin

Carry (Cout) 0 1 0 1 0

01 1 01

1 001 0

1 01 01

1 1 001

11111

S = A B Cin Cout = A.B + B.Cin + A.Cin
How can you add two 32-bit numbers? It will be discussed in the class.
10

Draft notes or 22C: 040
Combinational vs. Sequential Circuits
Combinational circuits. The output depends only on the current values of
the inputs and not on the past values. Examples are adders, subtractors, and all the circuits that we have studied so far Sequential circuits.
The output depends not only on the current values of the inputs, but also on their past values. These hold the secret of how to memorize information. We will study sequential circuits later.
11