Computer Architecture

Main page | Homework | Syllabus | Resources

Section 2 Solutions:

1. Evaluate the given Boolean functions for the variable values given
- A. X = (a + b)(c + d) given a = 1, b = 1, c = 0, d = 0
  0.
- B. Y = a + b * c + d given a = 0, b = 1, c = 0, d = 0
  0.
- C. Z = a * b * c * d' + a' * b * c * d' + a' * b' * c * d given a = 0, b = 1, c = 1, d = 0
  1.

2. Draw logic circuits that directly implement the following functions using logic gates. Do not simplify the equations.
- A. X = AB + A'B'
- B. Y = a + (b + (c + d))
- C. Z = abc' + a'bc + a'b'c
- D. W = mn + m'no + p

3. Prove the following theorems using Boolean algebraic manipulation using the basic Boolean algebra postulates
- A. X + X * Y = X
  X * (1 + Y)
  X * 1
  X
- B. X * (X + Y) = X
  X * X + X * Y
  X + X * Y
  X * (1 + Y)
  X * 1
  X
- C. X * Y + X * Y' = X
  X * (Y + Y')
  X * 1
  X
- D. (X + Y) * (X + Y') = X
  X + (Y * Y')
  X + 0
  X
- E. X * Y + X' * Z + Y * Z = X * Y + X' * Z
  X * Y + X' * Z + Y * Z * 1
  X * Y + X' * Z + Y * Z * (X + X')
  X * Y + X' * Z + X * Y * Z + X' * Y * Z
  X * Y + X * Y * Z + X' * Z + X' * Y * Z
  X * Y * (1 + Z) + X' * Z * (1 + Z)
  X * Y * 1 + X' * Z * 1
  X * Y + X' + Z
- F. (X + Y) * (X' + Z) * (Y + Z) = (X + Y) * (X' + Z)
  (X + Y) * (X' + Z) * ((Y + Z) + 0)
  (X + Y) * (X' + Z) * ((Y + Z) + (X * X'))
  (X + Y) * (X' + Z) * (X + Y + Z) * (X' + Y + Z)
  (X + Y) * (X + Y + Z) * (X' + Z) * (X' + Z + Y)
  (X + Y) * (1 + Z) * (X' + Z) * (1 + Y)
  (X + Y) * 1 * (X' + Z) * 1
  (X + Y) * (X' + Z)

4. Vahid 2.11
- A. pump = water * enabled
- B. alarm = light * night * motion'
- C. open = enabled * (rain + freeze)'

5. Vahid 2.17
- A.
- B.
- C.
6. Vahid 2.20
B = M * L'

7. Vahid 2.27
F = a(b + c)(d') + ac'(b + d)
F = ad'(b + c) + ac'(b + d)
F = ad'b + ad'c + ac'b + ac'd
F = abd' + acd' + abc' + ac'd

8. Vahid 2.28
F = a'b(c + d') + a(b' + c) + a(b + d)c
F = a'b(c + d') + a(b' + c) + ac(b + d)
F = a'bc + a'bd' + ab' + ac + acb + acd
F = a'bc + a'bd' + ab' + ac + abc + acd

9. Vahid 2.29
F = abc + a'b
F' = (abc + a'b)'
F' = (abc)'(a'b)'
F' = (a' + b' + c')(a + b')
F' = a(a' + b' + c') + b'(a' + b' + c')
F' = aa' + ab' + ac' + a'b' + b'b' + b'c'
F' = 0 + ab' + ac' + a'b' + b' + b'c'
F' = ab' + ac' + a'b' + b' + b'c'
F' = ab' + a'b' + b' + b'c' + ac'
F' = b'(a + a' + 1 + b') + ac'
F' = b'1 + ac'
F' = b' + ac'

10. Vahid 2.30
F = ac' + abd' + acd
F' = (ac' + abd' + acd)'
F' = (ac')'(abd')'(acd)'
F' = (a' + c)(a' + b' + d)(a' + c' + d')
F' = (a'(a' + b' + d) + c(a' + b' + d))(a' + c' + d')
F' = (a' + a'b' + a'd + a'c + b'c + cd)(a' + c' + d')
F' = (a'(1 + b' + d + c) + b'c + cd)(a' + c' + d')
F' = (a' + b'c + cd)(a' + c' + d')
F' = a'(a' + c' + d') + b'c(a' + c' + d') + cd(a' + c' + d')
F' = a'a' + a'c' + a'd' + a'b'c + b'cc' + b'cd' + a'cd + cc'd + cdd'
F' = a' + a'c' + a'd' + a'b'c + b'cc' + b'cd' + a'cd + cc'd + cdd'
F' = a' + a'c' + a'd' + a'b'c + b'0 + b'cd' + a'cd + 0d + c0
F' = a' + a'c' + a'd' + a'b'c + b'cd' + a'cd
F' = a' + a'c' + a'd' + a'b'c + a'cd + b'cd'
F' = a'(1 + c' + d' + b'c + cd) + b'cd'
F' = a'1 + b'cd'
F' = a' + b'cd'

11. Vahid 2.31
- A.
- B.
- C.
- D.

12. Vahid 2.34
- A.
- B.
- C.
- D.

13. Vahid 2.48
- A. a'bc + abc + abc'
- B. a'bc + a'bc'
- C. a'b'c + a'bc' + a'bc + ab'c' + ab'c + abc' + abc
- D. a'b'c' + a'bc' + ab'c' + abc'

14. Vahid 2.49
- A. (a + b)' * a
  (a' * b') * a
  a * a' * b'
  0 * b'
  0
  0 is not equal to a + b'.
- B.
  
  ((a + b)' * a) is not equal to (a + b')

15. Vahid 2.52
- A. First circuit is (ab + cd)
  Manipulating the equation into minterms and minterm order.
  abc + abc' + acd + a'cd
  abcd' + abcd + abc'd' + abc'd + ab'cd + abcd + a'b'cd + a'bcd
  abcd' + abcd + abc'd' + abc'd + ab'cd + a'b'cd + a'bcd
  a'b'cd + a'bcd + ab'cd + abc'd' + abc'd + abcd' + abcd
  
  Second circuit is ((ab)'(cd)')''
  Manipulating the equation into minterms and minterm order.
  (ab)'(cd)'
  (a' + b')(c' + d')
  a'(c' + d') + b'(c' + d')
  a'c' + a'd' + b'c' + b'd'
  a'b'c' + a'bc' + a'b'd' + a'bd' + a'b'c' + ab'c' + a'b'd' + ab'd'
  a'b'c' + a'bc' + a'b'd' + a'bd' + ab'c' + ab'd'
  a'b'c'd' + a'b'c'd + a'bc'd' + a'bc'd + a'b'c'd' + a'b'cd' + a'bc'd' + a'bcd' + ab'c'd' + ab'c'd + ab'cd'
  a'b'c'd' + a'b'c'd + a'bc'd' + a'bc'd + a'b'cd' + a'bcd' + ab'c'd' + ab'c'd + ab'cd'
  a'b'c'd' + a'b'c'd + a'b'cd' + a'bc'd' + a'bc'd + a'bcd' + ab'c'd' + ab'c'd + ab'cd'
  
  Since the minterms are not equal the two circuits are not equivalent.
- B.
  
  The two circuits are not equal.

16. Vahid 2.58. Implement as a sum of minterms.

P = m2 + m3 + m5 + m7 + m11 + m13

17. Vahid 2.69

18. Design a 4 to 16 line decoder using 2 to 4 line decoders and the minimum amount of additional combinational logic.

19. Design a 16 to 1 multiplexer using 4 to 1 multiplexers and the minimum amount of additional combinational logic.

20. Using a 4 to 16 line decoder and one OR gate, design a circuit that implements problem 15 (Vahid 2.58).

21. Using an 8 to 1 multiplexer and one NOT gate, design a circuit that implements problem 15 (Vahid 2.58).

22. Using AND, OR, NAND, NOR, and NOT logic gates, design a 4 to 2 line priority encoder with a valid output.