Propositional Logic

Consider the statement about a party, “If it's your birthday or there will be cake, then there will be cake.”

1. Translate the above statement into symbols. Clearly state which statement is $P$ and which is $Q$.

2. Make a truth table for the statement.

3. Assuming the statement is true, what (if anything) can you conclude if there will be cake?

4. Assuming the statement is true, what (if anything) can you conclude if…

Determine whether the following two statements are logically equivalent: $\neg(P \imp Q)$ and $P \wedge \neg Q$. Explain how you know you are correct.

Simplify the following statements (so that negation only appears right before variables).

1. $\neg(P \imp \neg Q)$.
2. $(\neg P \vee \neg Q) \imp \neg (\neg Q \wedge R)$.
3. $\neg((P \imp \neg Q) \vee \neg (R \wedge \neg R))$.

4. It is false that if Sam is not a man then Chris is a woman, and that Chris is not a woman.

We can also simplify statements in predicate logic using our rules for passing negations over quantifiers, and then applying propositional logical equivalence to the “inside” propositional part. Simplify the statements below (so negation appears only directly next to predicates).

1. $\neg \exists x \forall y (\neg O(x) \vee E(y))$.
2. $\neg \forall x \neg \forall y \neg(x \lt y \wedge \exists z (x \lt z \vee y \lt z))$.

3. There is a number $n$ for which no other number is either less $n$ than or equal to $n$.

4. It is false that for every number