# 程序代写代做代考 Microsoft PowerPoint – 046-Boolean-properties

Microsoft PowerPoint – 046-Boolean-properties

9/10/2016

University of Illinois at Urbana-Champaign

Dept. of Electrical and Computer Engineering

ECE 120: Introduction to Computing

Boolean Properties and Optimization

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 1

The Dual Form Swaps 0/1 and AND/OR

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 2

Boolean algebra has an interesting

property called duality.

Let’s define the dual form of

an expression as follows:

◦Starting with the expression,

◦ swap 0 with 1

(just the values, not variables),

◦and swap AND with OR.

Every Boolean Expression Has a Dual Form

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 3

For example, what is the dual of

A + (BC) + (0 (D + 1) ) ?

First replace the 0 with 1 and the 1 with 0.

Then replace + (OR) with· (AND)

and vice-versa.

We obtain:

A· (B + C)· (1 + (D· 0) )

The Dual of the Dual is the Expression

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 4

So what is the dual of

A· (B + C)· (1 + (D· 0) ) ?

Since we’re swapping things, swapping them

again produces the original expression:

A + (BC) + (0 (D + 1) )

Thus any Boolean expression has a

unique dual, and the dual of the dual is the

expression (hence the term duality—two

aspects of the same thing).

9/10/2016

Pitfall: Do Not Change the Order of Operations

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 5

Be careful not to change the order of

operations when finding a dual form.

For example, the dual form of

A + BC

is

A (B + C)

The operation on B and C must happen

before the other operation.

Why Do You Care? One Reason: the Principle of Duality

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 6

Three reasons:

◦CMOS gate structures are dual forms

◦Quick way to complement any expression

◦ the principle of duality

Let’s start with the last, which we’ll use

shortly (when we examine more properties).

Principle of duality: If a Boolean theorem

or identity is true/false, so is the dual of

that theorem or identity.

Generalized DeMorgan is Quick and Easy

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 7

Let’s say that we have an expression F.

To find F’ … apply DeMorgan’s Laws …

Apply repeatedly, as many times as necessary.

Or use the generalized version based on

duality:

◦Write the dual form of F.

◦Swap variables and

complemented variables.

◦ (That’s all.)

An Example of Finding a Complement with the Dual Form

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 8

F = AB (C + (DL’G(B’ + A + E))) (H + (J’A’B))

What’s F’?

The dual is

A + B + (C (D + L’ + G + (B’AE))) +

(H (J’ + A’ + B))

So

F’ = A’ + B’ + (C’ (D’ + L + G’ + (BA’E’))) +

(H’ (J + A + B’))

You can skip the middle step once

you’re comfortable with the process.

9/10/2016

We Can Derive a Gate’s Output from the n-type Network

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 9

What about CMOS gate structures?

Think about the network of n-type

MOSFETS connecting an output Q to 0V.

For example, consider a set of

four n-type arranged in parallel

with inputs A, B, C, and D.

So Q = 0 if ANY of the transistors is on. In

other words, Q is 0 when A + B + C + D.

Thus Q = (A + B + C + D)’. A NOR gate.

We Can Also Derive Function from the p-type Network

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 10

What about the p-type transistors

on the same gate?

◦They are arranged in series.

◦They connect Q to Vdd.

But p-type transistors are on when their

gates are set to 0. So Q = 1 when ALL

of the inputs are 0.

Thus Q = A’B’C’D’.

That’s the same expression, of course.

The Expressions are Related via Generalized DeMorgan

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 11

But notice that we can also

◦ get the second form

◦by applying generalized DeMorgan

to the first form.

Starting with

Q = (A + B + C + D)’,

we find the dual of A+B+C+D to be ABCD, so

Q = A’B’C’D’.

The Networks are Dual Forms of One Another

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 12

The complemented variables come from the use of

p-type transistors.

The dual form is built into the gate design.

If we want to design a gate for something

OTHER than NAND, NOR, NOT:

◦ Write the output as Q = (expression)’,

◦ Build that expression from n-type MOSFETs.

◦ Build the dual of the expression from

p-type MOSFETs.

9/10/2016

An Example of an Unusual Gate

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 13

Consider the gate here:

From the n-type network,

Q = ((A + B) C)’

The dual of the expression

(ignoring the complement)

is

AB + C

which is the structure

of the p-type network.

Area and Speed for the Unusual Gate

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 14

So the function Q = ((A + B) C)’ requires six

transistors and one gate delay.

We can, of course, limit ourselves

to NAND/NOR gates.

In that case, Q = ((A’B’)’ C)’

We use one two-input NAND for (A’B’)’,

and a second two-input NAND for Q.

If we assume that A’ and B’ are available,

the NAND design requires eight transistors

and two gate delays.

Optimization versus Abstraction

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 15

Most designers just use NAND and NOR

(or, today, even higher-level abstractions!).

In general:

◦ breaking abstraction boundaries

can give us an advantage,

◦ but the boundaries make

the design task less complex,

◦ which improves human productivity and

reduces the likelihood of mistakes.

That’s another tradeoff.

Computer aided design (CAD) tools can perform

some of these optimizations for us, too.

Simple Boolean Properties

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 16

Easy, but useful to commit to memory for

analyzing circuits…

1 + A = 1 0· A = 0

1· A = A 0 + A = A

A + A = A A· A = A

A· A’ = 0 A + A’ = 1

(Each row gives two dual forms.)

9/10/2016

More Dual Form Boolean Properties

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 17

DeMorgan’s Laws are also dual forms

(A + B)’ = A’B’ (AB)’ = A’ + B’

What about distributivity? Here’s the rule

that you know from our usual algebra

A(B + C) = AB + AC

(multiplication distributes over addition)

It’s also true in Boolean algebra:

AND distributes over OR.

OR Also Distributes Over AND in Boolean Algebra

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 18

A(B + C) = AB + AC

Now take the dual form…

A + BC = (A + B)(A + C)

OR distributes over AND!

(Note that this property does NOT hold in our

usual algebra. 14 + 7· 4 ≠ (14 + 7)(14 + 4) )

One More Property: Consensus

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 19

The last property is non-intuitive.

AB + A’C + BC = AB + A’C

It’s called “consensus” because

◦ the first two terms TOGETHER

(when both are true, and thus reach a

consensus) imply the third term

◦ so the third term can be dropped.

A K-Map Illustrates Consensus Well

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 20

Let’s look at a

K-map.

AB is the

vertical

green loop.

A’C is the

horizontal

green loop.

BC is the

black loop.

9/10/2016

Consensus Has Two Dual Forms (SOP and POS)

ECE 120: Introduction to Computing © 2016 Steven S. Lumetta. All rights reserved. slide 21

And, of course, there is another form of

consensus for POS form.

Start with our first form:

AB + A’C + BC = AB + A’C

Then find the dual to obtain:

(A + B)(A’ + C)(B + C) = (A + B)(A’ + C)