CSE 370, Autumn 2000

Homework 2 Solutions

1.  Draw a schematic in Design Works for the following function: f(A,B,C,D)=(AB'+C'D)'

• (a) Using only two-input NOR gates:

• (b) Using only two-input NAND gates:

2.  Prove using truth-table method:

• (a)  (A + B') B = AB

 A B A + B' (A + B') B AB 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 1 1 1 1 Result: (A + B')  B = AB
• (b)  (A + B) (A' + C) = AC + A'B

 A B C AC A'B A + B A' + C AC + A'B (A + B) (A' +C) 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 1 1 0 0 0 0 1 0 0 0 1 0 1 1 0 1 1 1 1 1 1 0 0 0 1 0 0 0 1 1 1 1 0 1 1 1 1 Result: (A+B)(A'+C)= AC + A'B

3.  Prove the following using other theorems and laws (listing the number of the law at each step).

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

(A + B).(A +C) = (A + B).(A)+ (A + B).(C) (Distributive law)

= (A.A + B.A) + (A.C +B.C) (Distributive law)

= A.A + B.A +A.C + B.C     (Associative law)

= A + B.A + A.C + B.C        (Idempotent Theorem)

= A + A.B + A.C + B.C       (Commutative law)

= A + B.C            (Simplification Theorem X + X.Y = X) X)

(b)  AB + A'C = (A + C).(A' + B)

(A + C).(A' + B) = (A + C).(A') + (A + C).B    (Distributive law)

= (A.A' + C.A') + (A.B + C.B) (Distributive law)

= A.A' + C.A' + A.B + CB  (Associative law)

=   C.A' + AB + CB (Theorem of complementarity A.A' = 0)

= A'C + AB + CB (Commutative law)

= A'C + AB  (Consensus Theorem)

4.  Use DeMorgan's theorem to invert the following expressions:

• (a) ABC + B(C' + D') :    (ABC + B(C' + D'))' = (A' + B' + C').(B' + (CD))

• (b) A + (BC)' :     (A + (BC)')' = A'(B' + C')' = A'BC

5.  Demonstrate that a 2-input NOR gate is a universal logic element.  Is an XOR gate universal?  Why? What about NAND ?

We show that we can implement NOT, AND and OR gates using NOR gates only to show that NOR is a universal logic element. We show that using a design works schematic below :

We show that NAND gates can create all other logic functions, and in particular  AND, OR and NOT gates.

To implement a NOT gate using NAND : (A NAND A) =  NOT A = A'

A NAND gate with its output inverted gives us an AND gate.

 NAND -> OR X Y X' Y' (X' Y')' X + Y 0 0 1 1 0 0 0 1 1 0 1 1 1 0 0 1 1 1 1 1 0 0 1 1 X' NAND Y' = X OR Y A NAND gate with its inputs inverted creates an OR gate, and adding another inverter to the output yields a NOR gate.

Thus, having created all other logic gates from NAND gates, we can say that NAND is a universal logic function.

An XOR gate is clearly not a universal element, because there is no way to create an AND or OR gate using only XOR gates.

6.  f(A, B, C, D) = Σm(1, 2, 3, 5, 8, 13)

• (a)  Rewrite as Boolean expression in canonical minterm form.

• A' B' C' D + A' B' C D' + A' B' C D + A' B C' D + A B' C' D' + A B C' D

• (b)  Rewrite in canonical maxterm form.

• (A + B + C + D) (A + B' + C + D) (A + B' + C' + D) (A + B' + C' + D') (A' + B + C + D') (A' + B + C' + D) (A' + B + C' + D') (A' + B' + C + D) (A' + B' + C' +D) (A' + B' + C' + D')

• (c)  Rewrite the complement of f in "little m" notation and in canonical minterm form.

f'(A, B, C, D) = Σm(0, 4, 6, 7, 9, 10, 11, 12, 14, 15)

= A' B' C' D' + A' B C' D' + A' B C D' + A' B C D + A B' C' D + A B' C D' + A B' C D + A B C' D' + A B C D' + A B C D

• (d)  Rewrite the complement of f in "big M" notation and in canonical maxterm form.

f'(A, B, C, D) = ΠM(1, 2, 3, 5, 8, 13)

=(A + B + C + D') (A + B + C' + D) ( A + B + C' + D') (A + B' + C + D') (A' + B + C + D) (A' + B' + C + D')

7. Consider the function f(A,B,C) = AB +  B'C' + AC'

(a) Express the function in canonical sum-of-products form. Use "little m" notation.

f(A,B,C) = ABC + ABC' + AB'C' + A'B'C' = Σm(0, 4, 6, 7)

(b) Express the complement of the function in canonical product-of-sums form. Use "big M" notation.

f'(A,B,C) = (A + B + C).(A + B' + C').(A' + B' + C).(A' + B' +C') =  ΠM(0 , 4, 6, 7)