Logical Equivalence Discussion

(The following is/are the initial prompt(s) for an online discussion; students may have posted responses, and prompts for further discussion may have been added, but these things are not shown.)

Logical equivalence and rules for when two statements are equivalent is central to many proofs. The following questions all involve logical equivalence in one way or another. Think about them, and post comments, answers, other questions, etc. Many have multiple answers, so even if someone else has already offered an answer to one, see if you can find another.

Can you rewrite (¬P ∨ Q) ∧ (P ∨ ¬Q) in an equivalent form that uses only “and” and “not” operations?

Show that the following equivalencies hold:

\[\lnot ( P \leftrightarrow Q) \equiv (P \lor Q) \land (\lnot P \lor \lnot Q)\]

\[\lnot(P\rightarrow(Q \lor R)) \equiv P \land \lnot Q \land \lnot R\]

\[P \wedge Q \rightarrow R \equiv \lnot P \lor \lnot Q \lor R\]

Intuitively you probably believe that “and” and “or” are associative, i.e., that P ∧ (Q ∧ R) ≡ (P ∧ Q) ∧ R and P ∨ (Q ∨ R) ≡ (P ∨ Q) ∨ R. But can you prove it?