EECS 31/CSE 31/ICS 151 Homework 2 Questions with Strategies

View Questions Only
View Questions with Solutions

Problem 1

Question

(Theorems of Boolean algebra) Give proofs to the following theorems.

  1. Theorem 3(a) and (b)
  2. Theorem 6(a) and (b)

Strategy

There is no strategy for this kind of question, the only thing you can do is to remember all axioms and some useful theorems, then use your experience and intuition to transform the left side, the right side or both sides of the equations until both sides are equal.

Note: use the theorems that have been proved.

Problem 2

Question

(Theorems and proofs) Using truth tables, prove the validity of the following identies.

  1. (xyz)' = x'+y'+z'

Strategy

  1. Create an empty table.
  2. Write all possible combinations of the variable values.
  3. Evaluate left side expression.
  4. Evaluate right side expression.
  5. Compare two side values.

Problem 3

Question

(Boolean functions) Derive truth tables for the following Boolean functions.

  1. F(x, y, z) = (x+z)'
  2. F(x, y, z) = (x+z)'(x+y')

Strategy

  1. Create an empty table.
  2. Write all possible combinations of the variable values.
  3. Using the knowledge of computation order of Boolean expression, compute sub-expressions(for example, in (d) they should be (x+z)' and (x+y')).
  4. Evaluate the whole expression from the sub-expression values.

Problem 4

Question

(Boolean algebra) Prove by algebraic manipulation that the following expressions are equivalent.

  1. x'y'+xy = (xy'+x'y)'
  2. x'z+xy = x'y'z+yz+xy

Strategy

There is no strategy for this kind of question, the only thing you can do is to remember all axioms and some useful theorems, then use your experience and intuition to transform the left side, the right side or both sides of the equations until both sides are equal.

Problem 5

Question

(Algebraic manipulation) Minimize the number of operators in the following Boolean expressions.

  1. x'y'+xy+xy'
  2. (x+y)(x+y')

Strategy

The number of operators in a Boolean expression can generally be minimized by means of algebraic manipulation (that is transformed by axioms or theorems). Unfortunately, there is no procedure to guarantee the minimal number of operators or literals in the expression.

Problem 6

Question

(Boolean implementations) Implement the XOR function by means of:

  1. NAND gates only
  2. NOR gates only
  3. AND, OR, and NOT gates

Strategy

  1. Apply axioms and theorems to transform XOR into required format, 
    
in (a),
    a XOR b = ab' + a'b
            = (ab' + a'b)''
            = ((ab')'(a'b)')'  
    -- you can stop here, if there is no requirement for minimal number of gates.
            = ((ab' + aa')'(a'b + b'b)')'
            = ((a(a' + b'))'(b(a' + b'))')'
            = ((a(ab)')'(b(ab)')')' in (b),
    a XOR b = ab' + a'b
            = (a + a'b)(b' + a'b)
            = (a + a')(a + b)(a' + b')(b' + b)
            = (a + b)(a' + b')
            = ((a + b)(a' + b'))''
            = ((a + b)' + (a' + b')')' in (c),
    a XOR b = ab' + a'b
  2. Represent these expression by gates.

Problem 7

Question

(Boolean implementations) Implement x XOR y XOR z using the components in the basic logic library presented in Table 3.14. Find the implementation that has:

  1. The smallest cost
  2. The shortest delay

Strategy

  1. Expand x XOR y XOR z into sum of products
  2. Try implementation with these different operators
    1. AND, OR, and NOT gates only
    2. NAND or NOR gates only
    3. XOR or XNOR gates only
  3. Select the implementation with the minimum cost and delay

Problem 8

Question

(Logic Libraries) Using the basic logic library presented in Table3.14, implement the full subtractor that is specified by the following table:


  Xi   Yi   Bi |   Bi+1    Di
------------------------------
  0    0    0  |    0      0
  0    0    1  |    1      1
  0    1    0  |    1      1
  0    1    1  |    1      0
  1    0    0  |    0      1
  1    0    1  |    0      0
  1    1    0  |    0      0
  1    1    1  |    1      1

Find the implementation that has:

  1. The smallest cost
  2. The shortest delay

Strategy

  1. Write the expression in Canonical form
  2. Convert the expression to 2-input NAND or NOR gates to get the smallest cost and shortest delay since NAND and NOR gates have smallest cost and delay

Problem 9

Question

(Logic Libraries) Redo Problem 3.15 using only the gates that are given in Table 3.15 and 3.16

Strategy

  1. Write the expression in Canonical form
  2. Transform expression and group it with 2 to 3 terms, with 2-3 variables.
  3. Use 2 or 3-wide, 2 or 3 input, AOI or OAI gates
  4. Use multiple input NAND or NOR gates, and convert XOR into the forms that use multiple-input NAND and NOR operations.
  5. Compare different group methods and get the best implementation

Problem 10 (3.18)

Question

(Logic Libraries) Redo Problem 3.15 using any of the standard logic gates that are given in Table 3.14, 3.15 and 3.16

Strategy

  1. The smallest cost and the smallest cost-delay product
    1. This problem includes all three library tables. Implement different logic gates and compare the solutions to get the best result.
    2. Note that: x XOR y XOR z = x XNOR y XNOR z (see strategy in Problem 3.15). XNOR has smaller cost and shorter delay values.
  2. The shortest delay
    1. To get the shortest delay, use multiple-input NAND and NOR, and convert XOR into the forms that use multiple-input NAND and NOR operations.
    2. Express x XOR y XOR z in canonical form for simplification.

Problem 11 (3.19)

Question

(Gate arrays) Using a 3-input NAND gates, derive a logic schematic of a:

  1. full adder
  2. full subtractor

Strategy

  1. Write the truth table;
  2. Write out sum of minterms expression of this truth table;
  3. Group operators into 3-input format;
  4. Group literals into 3-input format;
  5. Change inverter into 3-input NAND gate;
  6. Compare different group methods and get the best implementation