I know how to show this via truth tables, but I’m confused over the formal proof.

Wikipedia tells me that:

$ (P \Rightarrow Q) \equiv (\neg P \lor Q) \equiv (Q \lor \neg P) \equiv (\neg Q \Rightarrow \neg P) $.

I don’t understand how we get from $ (P \Rightarrow Q) $ to $ (\neg P \lor Q) $. I also don’t understand how $ (Q \lor \neg P) $ implies $ (\neg Q \Rightarrow \neg P) $.

  • $\begingroup$ "if it rains then the ground gets wet" ($P\implies Q$). Now can it happen that both following statemens are not true: 1)"it is not raining" and 2)"the ground is getting wet."? No it cannot, so at least one of them is true ($\neg P\vee Q$) $\endgroup$ – drhab Sep 11 '16 at 18:59
  • $\begingroup$ Before seeking a formal proof, you need to specify which proof calculus you wish to use. There are three well-known ones: Hilbert Calculus, Natural Deduction and Sequent Calculus. $\endgroup$ – Berrick Caleb Fillmore Sep 11 '16 at 19:05
  • $\begingroup$ Another way to convince yourself is to make truth tables for the two statements. There are two variables, $P$ and $Q$, so there are four possibilities for the truth values (both false, $P$ false and $Q$ true, $P$ true and $Q$ false, and both false). For each of the four possibilites, find the truth value of $P\implies Q$ and the truth value of $\neg Q\implies P$. You’ll find that in each of the four cases the truth value of $P\implies Q$ is the same as the truth value of $\neg Q\implies P$. Thus the two are logically equivalent. $\endgroup$ – Steve Kass Sep 11 '16 at 20:19

$ (P \Rightarrow Q) \equiv (\neg P \lor Q) \equiv (Q \lor \neg P) \equiv (\neg \neg Q \lor \neg P) \equiv (\neg Q \Rightarrow \neg P) $.

  • $\begingroup$ Thank you! But could you tell me the logic behind P⇒Q = ¬PvQ and ¬(¬Q)v(¬P) = ¬Q⇒¬P? $\endgroup$ – Nikitau Sep 11 '16 at 18:57
  • $\begingroup$ Its just manipulation.Which part you did not understand? $\endgroup$ – Ashar Tafhim Sep 11 '16 at 19:05
  • $\begingroup$ DrHab replied above so I now I understand P⇒Q = ¬PvQ . I'm confused over how ¬(¬Q)v(¬P) = ¬Q⇒¬P. I guess I should provide context by saying this is my first very rigorous proof-based class. $\endgroup$ – Nikitau Sep 11 '16 at 19:07
  • $\begingroup$ Let X=¬Q and Y=¬P then ¬(¬Q)v(¬P) =¬XvY = X⇒Y.Does this solve the problem? $\endgroup$ – Ashar Tafhim Sep 11 '16 at 19:09
  • $\begingroup$ OH, now I get it. Thank you so much! $\endgroup$ – Nikitau Sep 11 '16 at 19:11

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.