# Equivalance proof of ((p → q) ∧ ¬q) → ¬p and ((p ∨ q) ∧ ¬p) → q

I am trying to prove if the above propositional formulas is a tautology using the logic laws. However, I am really stuck, I don't know where else to go.

Here is what I've done for the former formula.

((p → q) ∧ ¬q) → ¬p

((¬p ∨ q) ∧ ¬q) → ¬p (implication law)

((q ∨ ¬p) ∧ ¬q) → ¬p (commutative law)

Here's what I've done for the latter formula:

((p ∨ q) ∧ ¬p) → q

((q ∧ p) ∧ ¬p) → q (commutative law)

(q ∧ (p ∧ q)) → q (associative law)

((q ∧ p) v (q ∧ q)) → q (distributive law)

((p v q) v (q ∧ q)) → q (commutative law)

((p v q) v q) → q (idempotent law)

((p v (q v q)) → q (associative law)

I am completely lost and I don't know what to do after the last steps.

Thanks

• Second and Third lines in the second part are wrong. – Mauro ALLEGRANZA Mar 7 '18 at 10:13
• Welcome to MSE. Please use MathJax. – José Carlos Santos Mar 7 '18 at 10:13
• @MauroALLEGRANZA How is the second line wrong? – Paul Zhu Mar 7 '18 at 10:26
• You have switched the "or" into an "and". – Mauro ALLEGRANZA Mar 7 '18 at 10:38

$$P \rightarrow Q \Leftrightarrow \neg P \lor Q$$
This is useful because we have far more equivalence principles involving the basic Boolean operators $\land$, $\lor$, and $\neg$ than we have dealing with implications. In fact, depending on what equivalence principles you have, sometimes you simply cannot show the equivalence while only relying on equivalence principles involving the $\rightarrow$. Indeed, notice how you keep having $\rightarrow q$ at the end of all of your statements!