Microsoft Word - Digital Logic Design v_4_6a

 Theorem 9 “DeMorgan’s Theorem (2-Variable form)”

a) X+Y=X.Y

b) X•Y=X+Y

 Theorem 10 “DeMorgan’s Theorem (General form)”

a) X 1 +X 2 +K+Xn=X 1 • X 2 • K•Xn

b) X 1 • X 2 • K•Xn=X 1 +.X 2 .+K+Xn

 Example of two type of Proofs (Truth Table and Algebraic)

Prove Theorem 8, “Simplification Theorem”.
Hint: Use truth table

 Prove Theorem 10, “DeMorgan’s Theorem (General form)”.

Hint: Apply Theorem 9.

 Utilizing Demorgan’s Theorem NAND and NOR gates may be represented using the other’s base

signal as shown below (“not” circle indicates complement):

Transforming from one form to another requires only two steps:

1) Complement every input and output.

2) Swap OR and AND gates.

 Example: Design an XOR using only NAND gates.

F(A,B) = A ⊕ B

Solution:

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

Apply conversion rules “Complement every input and output; Swap ORs and ANDs”

F(A,B) = ((A’.B)’. (B’.A)’)’

Gate Type

NAND gate

NOR gate

AND gate

OR gate

AND form OR form

=

=

=

=