ACTIVITY
  1. Below is a sequence of simplifications of a formula with no justification for each step. Provide the justification by stating for each line (after the first) what tautology is being used and what the subformulas associated with the variables in the tautology are $$ \begin{array}{rcll} F_1 & = & (u | v) | u &\\ & = & (v|u)|u &\mbox{__________________}\\ & = & v | (u|u)&\mbox{__________________}\\ & = & v|u &\mbox{__________________}\\ \end{array} $$
  2. Below is an invalid simplification. [Warning! the below is invalid!] Identify the step that corresponds to a "simplification" that is not actually a tautology, and thus is not valid. $$ \begin{array}{rcll} F_2 & = & (y \Rightarrow x) \wedge x&\\ & = & x \wedge (y \Rightarrow x) &\\ & = & x\wedge y \Rightarrow x \wedge x &\\ & = & x \wedge y \Rightarrow x &\\ \end{array} $$
  3. Find a simple right-hand-side to the following equivalence that doesn't use parentheses and that gives a tautology:

    $\neg(a\wedge b) \Leftrightarrow\ \mbox{____________}$

  4. Find a simple right-hand-side to the following equivalence that doesn't use parentheses and that gives a tautology:

    $\neg(a\vee b) \Leftrightarrow\ \mbox{____________}$

  5. In the previous homework, one answer was "constraint d is $\neg(bh \wedge \neg cs)$". Using your answer to problem (3) and one of the above simplification rules, show how to simplify "constraint d". Please write it step-by-step like in problem (1).

  6. The Class 4 Theorem shows that every boolean function has a defining propositional formula. The proof actually shows how to build a defining formula from the truth table, and the formula it builds uses only $\wedge$, $\vee$ and $\neg$. That means any of the boolean operators can be defined using just those three operators.
    1. Find a simple equivalent to $a \Rightarrow b$ using only $\wedge$, $\vee$ and $\neg$. $(a \Rightarrow b) \Leftrightarrow$ _______________________
    2. Find a simple(ish) equivalent to $a \oplus b$ using only $\wedge$, $\vee$ and $\neg$. $(a \oplus b) \Leftrightarrow$ _______________________
  7. Recall that the definition of Propositional Formula consists of three rules: 1) variables are formulas, 2) nots of formulas are formulas, 3) the $\wedge,\vee,\oplus,\Leftarrow,\Leftrightarrow$ of two formulas is a formua. The definition of Extended Propositional Formula simply adds a new rule:

    0. The boolean constants true/false are Extended Propositional Formulas.

    Our definition of Propositional Formula does not allow the constants true or false. Let's define an Extended Propositional Formula to extend the definition of Propositional Formula by allowing the constants true and false. Thus, something like $a \vee (true \oplus b)$. Prove that for any Extended Propositional Formula $F$, there is a Propositional Formula that is equivalent to $F$. (Ask yourself, how could I convince someone that any Extended Propositional Formula can be converted to an equivalent formula containing no true/false constants.)
  8. With Extended Propositional Formulas, there are a few simplifcation rules we can express nicely.
    1. Complete the tautology to make a nice simplification rule (check it!): $\text{false}\oplus b \Leftrightarrow$ ______________
    2. Complete the tautology to make a nice simplification rule (check it!): $\text{true}\oplus b \Leftrightarrow$ ______________
    3. Based on your results, we two new rules:

      If formula $F$ is a tautology, we can simplify $(F) \oplus a$ to _______________.

      If formula $F$ is a contradiction, we can simplify $(F) \oplus a$ to _______________.