Homework 7

Problem 1

NAND
A	B	A NAND A	A NAND B	(A NAND B)'	A' NAND B'
0	0	1	1	0	0
0	1	1	1	0	1
1	0	0	1	0	1
1	1	0	0	1	1
		A'		A AND B	A OR B

A NAND A is A', and from DeMorgan's law,
A NAND B = (AB)' = A' + B' ==> (A'B')' = A'' + B'' = A + B

The table above shows that you can form AND, OR, and NOT from NAND. Tha's sufficient, since all boolean expressions are formed using these operators.

NOR
A B A NOR A A NOR B (A NOR B)' A' NOR B'

0 0 1 1 0 0

0 1 1 0 1 0

1 0 0 0 1 0

1 1 0 0 1 1

A' A OR B A AND B

A NOR A is A', and from DeMorgan's law,
(AB)' = A' + B' ==> ((AB)')' = AB = (A' + B')' = A' NOR B'

The table above shows that you can form AND, OR, and NOT from NOR.

AND
A B A AND A A AND B

0 0 0 0

0 1 0 0

1 0 1 0

1 1 1 1

Here, clearly AND is not a complete set. There is no way to generate the complement or the OR function.

AND
A	B	A AND A	A AND B
0	0	0	0
0	1	0	0
1	0	1	0
1	1	1	1

XOR
A B A XOR 1 A XOR B

0 0 1 0

0 1 1 1

1 0 0 1

1 1 0 0

A'

Even though we can form A' with XOR, we can't do any more. It is impossible to produce the OR or AND functions.

XOR
A	B	A XOR 1	A XOR B
0	0	1	0
0	1	1	1
1	0	0	1
1	1	0	0
		A'

Problem 2

A1 B1 A0 B0 Ci | Co S1 S0
---------------+---------
 0  0  0  0  0 |  0  0  0
 0  0  0  0  1 |  0  0  1
 0  0  0  1  0 |  0  0  1
 0  0  0  1  1 |  0  1  0

 0  0  1  0  0 |  0  0  1
 0  0  1  0  1 |  0  1  0
 0  0  1  1  0 |  0  1  0
 0  0  1  1  1 |  0  1  1

 0  1  0  0  0 |  0  1  0
 0  1  0  0  1 |  0  1  1
 0  1  0  1  0 |  0  1  1
 0  1  0  1  1 |  1  0  0

 0  1  1  0  0 |  0  1  1
 0  1  1  0  1 |  1  0  0
 0  1  1  1  0 |  1  0  0
 0  1  1  1  1 |  1  0  1

 1  0  0  0  0 |  0  1  0
 1  0  0  0  1 |  0  1  1
 1  0  0  1  0 |  0  1  1
 1  0  0  1  1 |  1  0  0

 1  0  1  0  0 |  0  1  1
 1  0  1  0  1 |  1  0  0
 1  0  1  1  0 |  1  0  0
 1  0  1  1  1 |  1  0  1

 1  1  0  0  0 |  1  0  0
 1  1  0  0  1 |  1  0  1
 1  1  0  1  0 |  1  0  1
 1  1  0  1  1 |  1  1  0

 1  1  1  0  0 |  1  0  1
 1  1  1  0  1 |  1  1  0
 1  1  1  1  0 |  1  1  0
 1  1  1  1  1 |  1  1  1

Sum of Products

S0 = A1'B1'A0'B0'Ci + A1'B1'A0'B0Ci + A1'B'1A0B0'Ci' + A1'B1'A0B0Ci +
     A1'B1A0'B0'Ci + A1'B1A0'B0Ci' + A1'B1A0B0'Ci' + A1'B1A0B0Ci +
     A1B1'A0'B0'Ci + A1B1'A0'B0Ci' + A1B1'A0B0'Ci' + A1B1'A0B0Ci +
     A1B1A0'B0'Ci + A1B1A0'B0Ci' + A1B1A0B0'Ci' + A1B1A0B0Ci

S1 = A1'B1'A0'B0Ci + A1'B1'A0B0'Ci + A1'B1'A0B0Ci' + A1'B1'A0B0Ci +
     A1'B1A0'B0'Ci' + A1'B1A0'B0'Ci + A1'B1A0'B0Ci' + A1'B1A0B0'Ci' +
     A1B1'A0'B0'Ci' + A1B1'A0'B0'Ci + A1B1'A0'B0Ci' + A1B1'A0B0'Ci' +
     A1B1A0'B0Ci + A1B1A0B0'Ci + A1B1A0B0Ci' + A1B1A0B0Ci

Co = A1'B1A0'B0Ci + A1'B1A0B0'Ci + A1'B1A0B0Ci' + A1'B1A0B0Ci +
     A1B1'A0'B0Ci + A1B1'A0B0'Ci + A1B1'A0B0Ci' + A1B1'A0B0Ci +
     A1B1A0'B0'Ci' + A1B1A0'B0'Ci + A1B1A0'B0Ci' + A1B1A0'B0Ci +
     A1B1A0B0'Ci' + A1B1A0B0'Ci + A1B1A0B0Ci' + A1B1A0B0Ci

Product of Sums

S0 = (A1 + B1 + A0 + B0 + Ci) * (A1 + B1 + A0 + B0' + Ci') * 
     (A1 + B1 + A0' + B0 + Ci') * (A1 + B1 + A0' + B0' + Ci) * 
     (A1 + B1' + A0 + B0 + Ci) * (A1 + B1' + A0 + B0' + Ci') * 
     (A1 + B1' + A0' + B0 + Ci') * (A1 + B1' + A0' + B0' + Ci) * 

     (A1 + B1' + A0' + B0' + Ci') * (A1' + B1 + A0 + B0' + Ci') * 
     (A1' + B1 + A0' + B0 + Ci') * (A1' + B1 + A0' + B0' + Ci) * 
     (A1' + B1' + A0 + B0 + Ci) * (A1' + B1' + A0 + B0' + Ci') * 
     (A1' + B1' + A0' + B0 + Ci') * (A1' + B1' + A0' + B0' + Ci) 

S1 = (A1 + B1 + A0 + B0 + Ci) * (A1 + B1 + A0 + B0 + Ci') * 
     (A1 + B1 + A0 + B0' + Ci) * (A1 + B1 + A0' + B0 + Ci) * 
     (A1 + B1' + A0 + B0' + Ci') * (A1 + B1' + A0' + B0 + Ci') * 
     (A1 + B1' + A0' + B0' + Ci) * (A1 + B1' + A0' + B0' + Ci') * 

     (A1' + B1 + A0 + B0' + Ci') * (A1' + B1 + A0' + B0 + Ci') * 
     (A1' + B1 + A0' + B0' + Ci) * (A1' + B1 + A0' + B0' + Ci') * 
     (A1' + B1' + A0 + B0 + Ci) * (A1' + B1' + A0 + B0 + Ci') * 
     (A1' + B1' + A0 + B0' + Ci) * (A1' + B1' + A0' + B0 + Ci) 

Co = (A1 + B1 + A0 + B0 + Ci) * (A1 + B1 + A0 + B0 + Ci') * 
     (A1 + B1 + A0 + B0' + Ci) * (A1 + B1 + A0 + B0' + Ci') * 
     (A1 + B1 + A0' + B0 + Ci) * (A1 + B1 + A0' + B0 + Ci') * 
     (A1 + B1 + A0' + B0' + Ci) * (A1 + B1 + A0' + B0' + Ci') * 

     (A1 + B1' + A0 + B0 + Ci) * (A1 + B1' + A0 + B0 + Ci') * 
     (A1 + B1' + A0 + B0' + Ci) * (A1 + B1' + A0' + B0 + Ci) * 
     (A1' + B1 + A0 + B0 + Ci) * (A1' + B1 + A0 + B0 + Ci') * 
     (A1' + B1 + A0 + B0' + Ci) * (A1 + B1' + A0' + B0 + Ci)

Problem 3

	S0 = A0'B0' + A0B0
	S1 = A1'B1'B0 + A1'B1'A0 + A1B1B0 + A1B1A0 (Not unique)
	Co = A1B1 + B1B0 + B1A0 + A1B0 + A1A0

Problem 4

Katz 2.7

a) (X + Y)(X + Y') = XX + XY' + XY + YY'
  = X + XY' + XY 
  = X + X(Y + Y') 
  = X + X = X

b)  X(X + Y) = XX + XY
  = X(1 + Y) = X

```
c) (X + Y')Y = XY + YY'
  = XY 
```

d) (X + Y)(X' + Z) = XX' + XZ + YX' + YZ
  = XZ(Y + Y') + X'Y(Z + Z') + YZ(X + X')
  = XYZ + XY'Z + X'YZ + X'YZ' + XYZ + X'YZ
  = (XYZ + XYZ) + (X'YZ + X'YZ) + X'YZ' + XY'Z
  = XYZ + X'YZ + X'YZ' + XY'Z
  = X'(YZ + YZ') + XZ(Y + Y')
  = X'Y + XZ

Katz 2.10

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

b) (ABC + B(C' + D'))'
  = (ABC)'(B(C' + D'))'
  = (A' + B' + C')(B' + (C' + D')')
  = (A' + B' + C')(B' + CD)

```
c) (X' + Y')'
  = X''Y'' = XY
```

d) (X + YZ')'
  = X'(YZ')'
  = X'(Y' + Z)

e) ((X + Y)Z)'
  = (X + Y)' + Z'
  = X'Y' + Z'

f) (X + Y'Z)'
  = X'(Y'Z)'
  = X'(Y + Z')

g) (X(Y + ZW' + V'S))'
  = X' + (Y + ZW' + V'S)'
  = X' + Y'(ZW')'(V'S)'
  = X' + Y'(Z' + W)(V + S')