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

Question

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 07 '18 at 10:13 — Mauro ALLEGRANZA, Mar 07 '18 at 10:13
Welcome to MSE. Please use MathJax. – José Carlos Santos Mar 07 '18 at 10:13 — José Carlos Santos, Mar 07 '18 at 10:13
@MauroALLEGRANZA How is the second line wrong? – Paul Zhu Mar 07 '18 at 10:26 — Paul Zhu, Mar 07 '18 at 10:26
You have switched the "or" into an "and". – Mauro ALLEGRANZA Mar 07 '18 at 10:38 — Mauro ALLEGRANZA, Mar 07 '18 at 10:38

score 1 · Answer 1 · answered Mar 07 '18 at 10:41

The two propositional formulas are equivalent because each one is a tautology. I'll do the first one (I've taken commutativity and associativity as given to keep the proof short): \begin{align*} ((p \to q) \land \neg q) \to \neg p &\equiv \neg ((\neg p \lor q) \land \neg q) \lor \neg p & \textsf{Implication Law} \\ &\equiv \neg (\neg p \lor q) \lor \neg\neg q \lor \neg p & \textsf{DeMorgan's Law} \\ &\equiv (\neg \neg p \land \neg q) \lor \neg\neg q \lor \neg p & \textsf{DeMorgan's Law} \\ &\equiv (p \land \neg q) \lor q \lor \neg p & \textsf{Double Negation Law} \\ &\equiv (p \land \neg q) \lor (\top \land q) \lor \neg p & \textsf{Identity Law} \\ &\equiv (p \land \neg q) \lor ((p \lor \neg p) \land q) \lor \neg p & \textsf{Complement Law} \\ &\equiv (p \land \neg q) \lor (p \land q) \lor (\neg p \land q) \lor \neg p & \textsf{Distributive Law} \\ &\equiv (p \land (\neg q \lor q)) \lor (\neg p \land q) \lor \neg p & \textsf{Distributive Law} \\ &\equiv (p \land \top) \lor (\neg p \land q) \lor \neg p & \textsf{Complement Law} \\ &\equiv p \lor (\neg p \land q) \lor \neg p & \textsf{Identity Law} \\ &\equiv (p \lor\neg p) \lor (\neg p \land q) & \textsf{Comm/Assoc Law} \\ &\equiv \top \lor (\neg p \land q) & \textsf{Complement Law} \\ &\equiv \top & \textsf{Domination Law} \\ \end{align*}

The proof for the other formula is nearly identical.

It's a tautology (true). See: https://en.wikipedia.org/wiki/Tautology_(logic) — Adriano, Mar 08 '18 at 03:55

score 0 · Answer 2 · answered Mar 07 '18 at 18:31

HINT

One really useful thing to do in these kinds of cases is to rewrite any implications as disjunctions, using:

$$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!

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

2 Answers2