When one is ON, the other is OFF.

Processing digital signals

Principle of Duality

Note: Put brackets around all AND terms before doing the substitution

What our logic elements are made of?

Real Digital Gates

Check for equality Inverter that can be controlled

Adder

What is inside the box?

NOT ENOUGH!

MUX (Multiplexer) i.e. 2-input MUX

Check for Odd and Even Number of Input “1”

Priority Circuit

Priority Circuit

Note: Put brackets around all AND terms before doing the substitution

Take the Dual back

Inverse

More Algebra: DeMorgan’s Theorem

Inverse

Additional logic gates from DeMorgan’s

Real Logic Gates

Logic Gates that are understandable (not real)

Schematic with Real Gates Schematic with simple (not real) Gates

How to transfer from NANDs/NORs into ANDs/Ors?

Bubbles cancel out

Example:

Remember this from DeMorgan’s!

Back to DeMorgan’s Algebra

Example 1: Example 2:

Example 3: Example 4:

Example 5:

Conversion from ANDs/ORs to NANDs/NORs

Example:

Given a boolean expression

Choose every second layer

Place bubbles (inverters) from both ends. add inverters where necessary (see (a), (b), (c))

See (h): inverter (b) and bubble are redundant. Move them to the outside.

4) Same as previous slide.

Choose gates with bubble-inputs.

6) Now using DeMorgan’s,

Change them to real gates

same example, but choosing other layers

Review on DeMorgan’s

Be very CAREFUL!!!

Definitions

1. Literal:A variable or its complement

2. Product term:literals connected by •

3. Sum term:literals connected by +

4. Minterm: a product term in which all the variables appear exactly once, either complemented or uncomplemented

5. Maxterm: a sum term in which all the variables appear exactly once, either complemented or uncomplemented

🞂 One or more digital signal inputs

🞂 One or more digital signal outputs

🞂 Outputs are only functions of current input values (ideal) plus logic propagation delays

Combinational Logic

I1 O1

Im On

🞂 Combinational logic has no memory.

🞂 Outputs are only function of current input combination

🞂 Nothing is known about past events

🞂 Repeating a sequence of inputs always gives the same output

sequence

🞂 Sequential logic (covered later) does have memory

🞂 Repeating a sequence of inputs can result in an entirely

different output sequence

🞂 Three main steps in designing a single-output combinational switching network:

1. Find a switching function which specifies the desired behavior of the network.

Simplify the algebraic expression for the function.

3. Realize the function using available logic elements (gates).

COMBINATIONAL LOGIC EXAMPLE

Sentence

Representation

Z= The alarm will ring if

A= the alarm switch is on and B’= the door is not closed or C= it is after 6 pm and D’= the window is not closed.

EquationRepresentation

Z = AB’ + CD’

Schematic B Z

Representation

DESIGN USING TRUTH TABLE

Example:

ABC represents a 3-bit binary number e.g. 011 = 3, 101 = 5 Output F is 1 if ABC >= 011 and is 0 if ABC < 011

A	B	C	F
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

The ‘1’s represent F(A,B,C). The ‘0’s represent F’(A,B,C)

EXAMPLE Cont’d: TRUTH TABLE TO SOP

FORM

Can write SOP form of equation directly from truth table.

F(A,B,C) = A’BC + AB’C’ + AB’C + ABC’ + ABC

A 0	B 0	C 0	F 0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

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

A’BC B F

AB’C’ C

AB’C ABC’ ABC

Note that each term in F has ALL variables present. If a product term has ALL

variables present, it is a MINTERM.

TRUTH TABLE TO POS FORM

To get POS form of F, write SOP form of F’, then use

DeMorgan’s Law.

A B C 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

F 0 0 0 1 1 1 1 1

A’B’C’

A’B’C

A’BC’

F’(A,B,C) = A’B’C’ + A’B’C + A’BC’

Take complement of both sides:

(F’(A,B,C))’ = (A’B’C’ + A’B’C + A’BC’)’

Apply DeMorgan’s Law to right side.

Left side is (F’)’ = F.

F(A,B,C) = (A’B’C’)’ (A’B’C)’ (A’BC’)’

Apply DeMorgan’s Law to each term F(A,B,C) = (A+B+C)(A+B+C’)(A+B’+C)

which is in POS Form.

MINTERMS, MAXTERMS

We saw that:

F(A,B,C) = A’BC + AB’C’ + AB’C + ABC’ + ABC’ + ABC

SOP form. If a product term has all variables present (each occurring exactly once, in complemented or uncomplemented form, but not both), it is a MINTERM.

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

POS form. If a sum term has all variables present (each occurring exactly once, in complemented or uncomplemented form, but not both), it is a MAXTERM.

All Boolean functions can be written in terms of either

Minterms or Maxterms.

MINTERM, MAXTERM NOTATION

Each line in a truth table represents both a Minterm and a

Row No.

A B C

Minterms

Maxterms

Maxterm.

0	0	0	0 A’B’C’ = m0 A+B+C = M0
1	0	0	1 A’B’C = m1 A+B+C’ = M1
2	0	1	0	A’B C’	= m2	A+B’+C = M2
3	0	1	1	A’B C	= m3	A+B’+C’ = M3
4	1	0	0	A B’C’	= m4	A’+B+C = M4
5	1	0	1	A B’C	= m5	A’+B+C’= M5
6	1	1	0	A B C’	= m6	A’+B’+C = M6
7	1	1	1	A B C	= m7	A’+B’+C’= M7

A boolean function can be written in terms of Minterm or Maxterm notation as a shorthand method of specifying the function.

F(A,B,C) = A’BC + AB’C’ + AB’C + ABC’ + ABC’ + ABC

= m3 + m4 + m5 + m6 + m7

= S m(3,4,5,6,7)

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

= M0 M1 M2

= Õ M(0,1,2)

Minterms correspond to ‘1’s of F, Maxterms correspond to ‘0’s of F in truth table.

Minterms correspond to ‘1’s in Truth table

F(A,B,C) = S m(1,2,6) = m1 + m2 + m6

A 0	B 0	C 0	F 0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	0

= A’B’C + A’BC’ + ABC’

m1 m2

FROM MINTERMS TO MAXTERMS TO TRUTH TABLE

To go from Minterms to Maxterms, list the numbers that belong to F’ (with 3 variables, minterm/maxterm numbers range from 0 to 7)

A B C 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1

F 0 1 1 0 0 0 1 0

F(A,B,C) = S m(1,2,6)

= Õ M(0,3,4,5,7) M3

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

(A’+B+C’)(A’+B’+C’) M5

Maxterms correspond to ‘0’s in Truth table

CONVERSION OF FORMS -- SUMMARY

§ Sum-of-Minterms to Product-of-Maxterms

-Rewrite minterm shorthand using maxterm shorthand.

-Replace minterm indices with indices not already used.

e.g: F(A,B,C) = åm(3,4,5,6,7) = ÕM(0,1,2)

§ Product-of-Maxterms to Sum-of-Minterms

-Rewrite maxterm shorthand using minterm shorthand.

-Replace maxterm indices with indices not already used.

e.g: F(A,B,C) = ÕM(0,3,5,6) = åm(1,2,4,7)

§ Sum-of-Minterms of F to Sum-of-Minterms of F’

-In minterm shorthand form, list the indices not already used

in F.

e.g: F(A,B,C) = åm(3,4,5,6,7)

F’(A,B,C) = åm(0,1,2)

§ Product-of-Maxterms of F to Prod-of-Maxterms of F’

-In maxterm shorthand form, list the indices not already used

in F.

e.g: F(A,B,C) = ÕM(0,1,2)

F’(A,B,C) = ÕM(3,4,5,6,7)

§ Sum-of-Minterms of F to Product-of-Maxterms of F’

-Rewrite in maxterm shorthand form, using the same indices as in F.

e.g: F(A,B,C) = åm(3,4,5,6,7)

F’(A,B,C) = ÕM(3,4,5,6,7)

§ Product-of-Maxterms of F to Sum-of-Minterms of F’

-Rewrite in minterm shorthand form, using the same indices

as in F.

e.g: F(A,B,C) = ÕM(0,1,2)

F’(A,B,C) = åm(0,1,2)

EXAMPLES

F(A,B,C,D) = S m(0) (minterm form)

= A’B’C’D’ (SOP form)

= Õ M(1,2,3,4,5,6,7,8,9,10,11,12,13,14,15)

(maxterm form)

(POS form too long to write…..)

F(A,B) = S m(1,2) (minterm form)

= A’B + AB’ (SOP form)

= Õ M(0,3) (maxterm form)

= (A+B)(A’+B’) (POS form)

A minterm must have every variable present. If a boolean product term does not have every variable present, then it can be expanded to its minterm representation.

F(A,B,C) = AB + C neither AB, or C are minterms

To expand AB to minterms, use the relation:

AB = AB(C+ C’) = ABC + ABC’

To expand C to minterms, do:

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

= ABC + AB’C + A’BC + A’B’C

F = AB +C = A’B’C + A’BC + AB’C + ABC’ + ABC

F(A,B,C) = S m(1,3,5,6,7)

A maxterm must have every variable present. If a boolean sum term does not have every variable present, then it can be expanded to its maxterm representation.

F(A,B,C) = (A+B) (C) neither (A+B), or C are maxterms

To expand (A+B) to maxterms, use the relation:

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

To expand C to maxterms, do:

C = C+A’A = (A’+C)(A+C) = (A’+C +BB’)(A+C+BB’)

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

F = (A+B)(C) =

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

F(A,B,C) = P M(0,1,2,4,6)

#	A	B	C	D	Z
0	0	0	0	0	1	Z = S m(0,3,6,9)
1	0	0	0	1	0	+ S d(10,11,12,13,14,15)
2	0	0	1	0	0
3	0	0	1	1	1
4	0	1	0	0	0
5	0	1	0	1	0	In order to find the simplest
6	0	1	1	0	1	network which will realize Z,
7	0	1	1	1	0	we must choose some of the
8	1	0	0	0	1	don’t cares (X’s) to be 0 and some
9	1	0	0	1	0	to be 1.
A	1	0	1	0	X
B	1	0	1	1	X	The easiest way to do this is with a
C	1	1	0	0	X	Karnaugh map …… next chapter.
D	1	1	0	1	X
E	1	1	1	0	X
F	1	1	1	1	X