Exercises for Chapter 0

10 points. Due Monday, August 31

1(a). For this circuit,

write the proposition (linear representation) that it depicts. Also, write the truth table for the proposition. Show the values of all the internal subexpressions of the proposition as well as the value of the overall proposition, like it's done in the lecture notes, Chapter 0. (The truth table will have 4 rows.)

1(b). Draw another circuit that uses only the NOT and AND gates that has the same input-output behavior as the circuit in part (a). Write its proposition (linear representation). Prove that your circuit has the same behavior by writing its truth table.

2. Write the truth tables for these propositions:

(a) ¬((¬ P) ∧ (¬Q))

(b) (P ∧ ¬P) ∨ ¬P (This table has 2 rows)

3. Here is a circuit-layout program for an exclusive-or circuit: Its input wires are named A and B, and its output wire is R:

def XOR(A, B):
    # computes  (A ∨ B) ∧ ¬(A ∧ B) 
    M = A ∨ B
    N = A ∧ B
    P = ¬N
    R = M ∧ P
    return R

The function is called ``exclusive or'' because it returns True as an answer only when A is True or B is True but not both are True. Verify this by computing the truth-table for XOR.

Despite the complicated definition of the above function, XOR gates are cheap to manufacture. (The reason is that XOR(A, B) is the same as A != B.)

3(a). XOR plus ∧ are used in practice to wire the addition circuits in a processor chip. As a "wiring exercise", use XOR to write this function:

def NOT(A):
    # computes  ¬A and returns it as the answer
    . . . use assignments like above, with only  XOR,  A, and True
          in the expressions . . .

3(b). Next, use ∧ and NOT to define this function:

def OR(A, B):
    # computes  A ∨ B  and returns it as the answer
    . . . use assignments, with only  A, B, NOT, and  ∧ 
          in the expressions  (Hint: see Exercise 2(a) above) . . .

4. Here are two equations:

2x + 1 = 3y
y = 4x

Use algebra to show that x = 1/10.