15110 Fall 2012 [Touretzky/Kaynar]

Problem Set 8 - due Friday, October 26 in class

Reading Assignment

Read sections 8.1-8.6 in chapter 8 of the textbook Explorations in Computing.

Instructions

Exercises

  1. (1 pt) For the following Boolean formulas, write a truth table that shows the value of the function for each possible combination of assignments to the boolean variables A, B and C. Use 1 for true and 0 for false.

    1. (A ∧ B) ∨ ¬C

    2. A ∧ (B ∨ C)

  2. (2 pts) The laws of Boolean algebra, presented in the slides for Unit 8A (updated; see pages 4 and 8), can be used to show that two formulae are equivalent by transforming one into the other. For example, here is the proof that P ∧ (Q ∧ P) is equivalent to P ∧ Q:
    Step   FormulaJustification (Rule)
    1.P ∧ (Q ∧ P)
    Commutative
    2.P ∧ (P ∧ Q)
    Associative
    3.(P ∧ P) ∧ Q    
    Idempotence
    4.P ∧ Q
    The commutative rule lets us switch the order of two terms, while the associative rule lets us move parentheses around (or add or remove them) when the connectives are all the same. The above table shows that step 2 was derived from step 1 via the commutative rule, step 3 was derived from step 2 via the associative rule, and step 4 was derived from step 3 via the idempotence rule.

    We can also use DeMorgan's law to transform expressions. Here is the proof that ¬(P ∧ Q) ∨ ¬ R is equivalent to ¬ P ∨ ¬ (Q ∧ R):

    Step   FormulaJustification (Rule)
    1.¬(P ∧ Q) ∨ ¬ R
    DeMorgan's Law
    2.(¬ P ∨ ¬ Q) ∨ ¬ R    
    Associative
    3.¬ P ∨ (¬ Q ∨ ¬ R)
    DeMorgan's Law
    4.¬ P ∨ ¬ (Q ∧ R)
    Similarly. here is the proof that (A ∨ (B ∧ C)) ∧ ¬(A ∨ C) is false, i.e., equivalent to 0:
    Step   FormulaJustification (Rule)
    1.[A ∨ (B ∧ C)] ∧ ¬(A ∨ C)
    Distributive
    2.[(A ∨ B) ∧ (A ∨ C)] ∧ ¬(A ∨ C)   
    Associative
    3.(A ∨ B) ∧ [(A ∨ C) ∧ ¬(A ∨ C)]
    Complement: x ∧ ¬ x
    4.(A ∨ B) ∧ 0
    Dominance: x ∧ 0
    5.0
    For each of the following proofs, fill in the missing elements.
    1. First problem:
      StepFormulaRule
      1.B ∧ A ∧ C ∧ A
      ?
      2.B ∧ A ∧ A ∧ C
      ?
      3.B ∧ (A ∧ A) ∧ C    
      ?
      4.B ∧ A ∧ C
      ?
      4.A ∧ B ∧ C

    2. Second problem:
      StepFormulaRule
      1.A ∧ (A ∨ B)
      ?
      2.(A ∨ 0) ∧ (A ∨ B)    
      ?
      3.A ∨ (0 ∧ B)
      ?
      4.A ∨ 0
      Identity
      5.?

    3. Third problem:
      StepFormulaRule
      1.¬ A ∨ ¬ B ∨ ¬ C
      ?
      2.(¬ A ∨ ¬ B) ∨ ¬ C    
      DeMorgan's Law
      3.¬(A ∧ B) ∨ ¬ C
      ?
      4.¬ ((A ∧ B) ∧ C)
      Associative
      5.¬ (A ∧ B ∧ C)

  3. (1 pt)

    1. The boolean expressions in Problem 1 can be realized as an electronic circuit. Such circuits can be represented abstractly using logic gates (instead of transistors). Draw how the formulas in problem 1 would be realized as a computational circuit using AND, OR and NOT gates.

    2. How could you realize the expression (¬ A ∨ ¬B) using a NAND gate?

    3. How could you realize the expression (A ∧ B) ∨ (C ∧ D) using only NAND gates and no other types of gate?

  4. (2 pts) Let ABCD represent a 4-bit binary-coded decimal number. For example, the decimal number 2 would be represented by the binary number 0010, which is expressed by letting A = 0, B = 0, C = 1 and D = 0.

    A seven-degment display can be used to form each of the ten decimal digits as shown below.

    Seven Segment Display and Examples

    We can define a circuit abstractly below that requires four Boolean inputs A, B, C, and D, and produces seven Boolean outputs s1, s2, ..., s7 to make the segments of the display form digits:

    Seven Segment Display Unit Diagram

    Segment s1 should be on for all digits except 1 (0001) and 4 (0100), so a Boolean expression for s1 might be: ¬ (¬ A ∧ ¬ C ∧ (B ⊕ D)). This can be simplified using DeMorgan's law to A ∨ C ∨ ¬ (B ⊕ D).

    1. Derive a simple Boolean expression for s6 as a function of A, B, C, and D that is true (represented by 1) if and only if the segment s6 is lit. Hint: Segment s6 is lit for all digits except when the digit is number 2.

    2. Derive a Boolean formula for s4 as a function of A, B, C, and D that determines when the middle segment of the display should be lit.

  5. (1 pt) In Ruby, there is another loop called an until loop that runs until a particular condition is true. For example, Consider the following code using a while loop: 

    i = 0
while i != 10 do
    puts i
    i = i + 1
end

    We can also write this code equivalently using an until loop: 

    i = 0
until i == 10 do
    puts i
    i = i + 1
end

    Use DeMorgan's Law to convert the following while loops to equivalent until loops. You should focus on translating the while loop condition to an equivalent until loop condition. What the loop computes is irrelevant for the purposes of this question. 

    1. x = 0
y = 0
while (x < 5) && (y <= 10) do
   # some computation with x and y
   x = x + 1
   y = y + 1
end


    2. a = 0
b = 0
c = 0
while (a != 20) || (b == 0 && c < 10) do
   #some computation with a and b
   a = a + 1
   b = b + 1
   c = c + 1
end

  6. (2 pts) Write a MARS program that computes the average of two values called x and y, stores the result in a location called avg, and halts. For testing purposes, let x be 5 and let y be 3.

    Test your program in irb using the MARSLab from RubyLabs. First, make a test machine with your program using the make_test_machine function. Then use the dump function to show how your program is represented in "memory". Then repeat the following until the program halts: execute the step function followed by the dump instruction. Once you are done, copy all of the results from irb into a text file and include this with your homework, along with the MARS program itself, to show that you have tested your solution.

  7. (1 pt) Consider the following MARS program imp.txt: 

    start   MOV 0, 1
        end start

    This is loaded into MARS as follows:

    m = make_test_machine("imp.txt", 100)

    What does this program do? Explain clearly. (HINT: Look at your textbook!)