# Simplification of Boolean functions

Download Simplification of Boolean functions

## Preview text

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

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

## Categories

## You my also like

### Lecture 5: More Logic Functions: NAND, NOR, XOR

376 KB2.1K231### Logic Circuit Design Class Notes EE242

10.8 MB1.4K230### Bms Institute Of Technology And Management

2.4 MB18.4K2.2K### Logic gates Logic gates and truth tables

80.6 KB2.3K809### Nand Ghar Building

650.1 KB5.9K773### Inverting Logic: NOT, NAND, & NOR

1.4 MB35.8K8.6K### UNIT :ii logic gates

2.2 MB34K13.6K### Universal Gates: NAND and NOR

235.9 KB23.2K6.9K### Binary Adders and Subtractors

12 KB5.4K2.2K