Print this problem set out (there 10 problems!) and answer the problems on the given sheet.
  1. Write the expression tree for x∨y∧¬z⊕¬y
  2. Write down the truth table for a⊕b⊕c
  3. Consider the boolean functions M, f, g and h defined below.
    Is there any interpretation for a and b for which the value of $M\left(f(a,b),g(a,b),h(a,b)\right)$ is true? If yes, give such an interpretation. If no, explain how you know.

  4. Class 4's big theorem shows that every boolean function is defined by a propositional formula. In fact, it gives an algorithm for producing a defining formula from a truth table. What would that algorithm produce for the boolean function M from the previous problem?
  5. Prove or disprove the following statement: The formula $a \Rightarrow b$ is equivalent to the formula $b \Rightarrow a$.
  6. Prove the following: For any propositional formula $F$, there is an equivalent propositional formula that only uses the operators $\wedge$, $\vee$ and $\neg$ (i.e. no $\Rightarrow$, $\oplus$, $\Leftrightarrow$).
    Note: This is a little bit open ended, since we've only seen a few proofs. Do the best you can.
  7. An important property in algebra is the distributive property, i.e. that multiplication distributes with addition. We write it as $a\cdot(b+c) = a\cdot b + a\cdot c$. So now with boolean operators, we would like to know which operators distribute with which others. I claim that $\wedge$ distributes with $\vee$, i.e. that $a \wedge (b \vee c)$ is equivalent to $(a \wedge b) \vee (a \wedge c)$. Is my claim correct? How do you know?
  8. Does the $\wedge$ operator distribute with the $\oplus$ operator too? Describe how you know your answer is correct!

  9. Is the following formula satisfiable? If so, write down a model (i.e. satisfying interpretation).
    Important: Do not type this! Use copy and paste!

    (s0∨s3)∧(s0∨s1∨s2∨s3)∧(j1∨j2)∧(j0∨j1∨j2∨j3)∧((¬e0∨s1)∧(¬e1∨s2)∧(¬e2∨s3)∧¬e3)∧ (e0∨e1∨e2∨e3)∧((¬t0∨¬e1)∧(¬t1∨¬e0∧¬e2)∧(¬t2∨¬e1∧¬e3)∧(¬t3∨¬e2))∧(t0∨t1∨t2∨t3)∧ (¬t0∨¬t1∧¬t2∧¬t3)∧(¬t1∨¬t0∧¬t2∧¬t3)∧(¬t2∨¬t0∧¬t1∧¬t3)∧(¬t3∨¬t0∧¬t1∧¬t2)∧ (¬e0∨¬e1∧¬e2∧¬e3)∧(¬e1∨¬e0∧¬e2∧¬e3)∧(¬e2∨¬e0∧¬e1∧¬e3)∧(¬e3∨¬e0∧¬e1∧¬e2)∧ (¬j0∨¬j1∧¬j2∧¬j3)∧(¬j1∨¬j0∧¬j2∧¬j3)∧(¬j2∨¬j0∧¬j1∧¬j3)∧(¬j3∨¬j0∧¬j1∧¬j2)∧ (¬s0∨¬s1∧¬s2∧¬s3)∧(¬s1∨¬s0∧¬s2∧¬s3)∧(¬s2∨¬s0∧¬s1∧¬s3)∧(¬s3∨¬s0∧¬s1∧¬s2)∧ (¬t0∨¬e0∧¬j0∧¬s0)∧(¬e0∨¬t0∧¬j0∧¬s0)∧(¬j0∨¬t0∧¬e0∧¬s0)∧(¬s0∨¬t0∧¬e0∧¬j0)∧ (¬t1∨¬e1∧¬j1∧¬s1)∧(¬e1∨¬t1∧¬j1∧¬s1)∧(¬j1∨¬t1∧¬e1∧¬s1)∧(¬s1∨¬t1∧¬e1∧¬j1)∧ (¬t2∨¬e2∧¬j2∧¬s2)∧(¬e2∨¬t2∧¬j2∧¬s2)∧(¬j2∨¬t2∧¬e2∧¬s2)∧(¬s2∨¬t2∧¬e2∧¬j2)∧ (¬t3∨¬e3∧¬j3∧¬s3)∧(¬e3∨¬t3∧¬j3∧¬s3)∧(¬j3∨¬t3∧¬e3∧¬s3)∧(¬s3∨¬t3∧¬e3∧¬j3)

  10. We have three people (alice, bob and cathy) who may or may not be wearing sunglasses and/or hats. We know the following information, and would like to use SAT solving to determine who's wearing what.
    1. someone is wearing sunglasses
    2. alice is wearing something
    3. if alice is wearing sunglasses then bob is wearing a hat
    4. it is not the case that both bob is wearing a hat and cathy is not wearing sunglasses
    5. if cathy is wearing a hat, then alice is wearing sunglasses
    6. cathy is not wearing sunglasses

    Use the variables below and write formulas for each constraint: 

    	  ah : "alice is wearing a hat",  as : "alice is wearing sunglasses"
	  bh : "bob is wearing a hat",    bs : "bob is wearing sunglasses"
	  ch : "cathy is wearing a hat",  cs : "cathy is wearing sunglasses"

    Put these pieces together an use a SAT solver to get a solution.