1. I Cant Blab Such Blibber Blubber!

Translate these English statements into logic, making the atomic propositions as small as possible.

• Only if the stadium is full and the crowd is not subdued will we win the game.
• Define a set of at most three atomic propositions. Then, use them to translate all of these sentences about my plan to buy a watch into logic:
  1. If the watch is no more than $25, then I will buy it.
  2. Unless it is on sale, I will not buy the watch. iii) I will buy the watch only if it is on sale and not more than $25.
• Define a set of at most four atomic propositions. Then, use them to translate all of these sentences about how a stack data structure can be used into logic:
  1. You can push onto but not pop from the stack if it is empty. ii) Only if the stack is full can you pop from but not push onto it. iii) The stack is neither empty nor full unless you cannot pop from it or cannot push onto it.

2. One, Two Three How Many Fingers Do I See?

Find a compound proposition involving the propositional variables p, q, and r that is true precisely when a majority of p, q, and r are true. Explain why your answer works.

3. Would You, Could You, With a Gate?

Using only

AND Gates, OR Gates, and Inverters (NOT Gates),

draw the diagram of a circuit with three inputs that computes the function B_(p,q,r), defined as follows: If both p and q are true, then B_{(p,q,r) = r}. If exactly one of p and q is true, then B_{(p,q,r) = r}. Otherwise, we have B(p,q,r) = F.

4. Aunt Annies Alligator

Define the A gate by the rule A_(r,s) :_{= r s} .

Show how to implement the following gates using only As. You are allowed to use the constants T and F and the inputs p and q. You are allowed to use inputs multiple times. You must justify your answers.

• _p, using only one _A gate
• p _q, using at most two _A gates
• _{(p q)}, using at most two _A gates
• p _q, using at most three _A gates

5. Thing One and Thing Two

Use truth assignments (i.e., an assignment of a truth value to each variable) to demonstrate that the two propositions in each part are not logically equivalent. Explain why your assignment demonstrates this.

• p (p q) q (p q)
• (p q) p q
• p (q r) (p q) r
• (p q) (q p) (q p) (p q)

6. The Curious Case of The Lying TAs

A new UW CSE student wandered around the Paul Allen building on their first day in the major. They found (as many do) that there is a secret room in its basements. On the door of this secret room is a sign that says:

All ye who enter, beware! Every inhabitant of this room is either a TA who always lies or a student who always tells the truth!

• The CSE student walked into the room, and two inhabitants walked up to the student. One of them said at least one of us is a TA. Determine (with justification) all the possibilities for each of the two inhabitants.
• Three inhabitants walk up to the CSE student and surround the UW CSE student. One of them says every TA in this circle has a TA to his immediate right. Determine (with justification) all the possibilities for each of the three inhabitants.

7. EXTRA CREDIT: XNORing

Imagine a computer with a fixed amount of memory. We give names, R_1,R2,R3, , to each of the locations where we can store data and call these registers. The machine can execute instructions, each of which reads the values from some register(s), applies some operation to those values to calculate a new value, and then stores the result in another register. For example, the instruction R₄ :_{= AND(R1,R2)} would read the values stored in R₁ and R₂, compute the logical and of those values, and store the result in register R₄.

We can perform more complex computations by using a sequence of instructions. For example, if we start with register R₁ containing the value of the proposition p and R₂ containing the value of the proposition q, then the following instructions:

1. R₃ := NOT(R₁)
2. R₄ := AND(R₁,R₂)
3. R₄ := OR(R₃,R₄)

would leave R₄ containing the value of the expression _{p (p q)}. Note that this last instruction reads from R₄ and also stores the result into R₄. This is allowed.

Now, assuming p is stored in register R₁ and q is stored in register R₂, give a sequence of instructions that

• only uses the _XNOR operation (no _AND, _OR, etc.),
• only uses registers R₁ and R₂ (no extra space), and
• ends with q stored in R₁ and p stored in R₂ (i.e., with the original values in R₁ and R₂ swapped).