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.


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

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.



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!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.