4
$\begingroup$

I'm new to discrete maths and I have been trying to solve this:

Decide whether $$(p \to q) \to (\neg q \to \neg p)$$ is a tautology or not by using the law of logical equivalence

I have constructed the truth table and concluded that it is indeed a tautology. However, I am having difficulty proving it using the law of logical equivalence. I can only realize that I can use $$(p \to q ) \equiv (\neg p \lor q)$$ but after that I have no idea how to continue. Any help would be appreciated.

$\endgroup$
4
  • 1
    $\begingroup$ ( ¬q → ¬p ) ≡ ( ¬¬ q ∨ ¬p ) ≡ ( q ∨ ¬p ) ≡ ( ¬p ∨ q ) $\endgroup$ – Mathematician 42 Jul 19 '16 at 14:29
  • 3
    $\begingroup$ By Double Negation and Commutativity, $¬ p ∨ q$ is equivalent to $¬¬ q ∨ ¬ p$. $\endgroup$ – Mauro ALLEGRANZA Jul 19 '16 at 14:30
  • $\begingroup$ Sorry. I really do not know what are you saying about @MauroALLEGRANZA $\endgroup$ – Lim Kha Shing Jul 19 '16 at 15:20
  • $\begingroup$ $\neg q\implies \neg p$ is just a contrapositive of a conditional. $\endgroup$ – Invisible Jan 7 '20 at 16:26
1
$\begingroup$

The following line of reasoning may help: \begin{align} (p\to q)\to(\neg q\to\neg p)&\equiv\neg(\neg p\lor q)\lor(q\lor\neg p)\tag{material implication}\\[1em] &\equiv\neg(\neg p\lor q)\lor(\neg p\lor q)\tag{commutativity}\\[1em] &\equiv \neg M\lor M\tag{$M:\neg p\lor q$}\\[1em] &\equiv \mathbf{T}.\tag{negation law} \end{align} Is the above clear? It makes minimal use of other logical equivalences.

$\endgroup$
4
  • $\begingroup$ still a little bit not clear on the third statement ¬M∨M what do it mean by M : ¬ p ∨ q ? $\endgroup$ – Lim Kha Shing Jul 20 '16 at 12:19
  • $\begingroup$ It's just to help you see that you have a statement of the form $\neg M\lor M$ which clearly must be true. The letter $M$ can be stand for any compound statement you want. $\endgroup$ – Daniel W. Farlow Jul 20 '16 at 14:14
  • $\begingroup$ @AhShing The justification, $(M: \neg p\vee q)$, reads "we defined a new symbol, $M$, to be equivalent to $\neg p\vee q$, so we could use substitution." $\endgroup$ – Graham Kemp Jul 21 '16 at 0:01
  • $\begingroup$ Sorry for late reply. Now i finally get it. Thank you for your help :D @GrahamKemp $\endgroup$ – Lim Kha Shing Jul 22 '16 at 14:23
1
$\begingroup$

It depends on the logical inferences you have available. One way is to note that $$ (p\rightarrow q)\equiv(\neg q\rightarrow\neg p)\qquad\text{(contrapositive)} $$ so your original expression is equivalent to $$ (p\rightarrow q)\rightarrow(p\rightarrow q) $$ and if we let $r=(p\rightarrow q)$ we have $r\rightarrow r$, which we either know is true or if you don't have that equivalence you can use material implication to get $(r\rightarrow r)\equiv (\neg r\lor r)$, which is true by inverse for OR.

$\endgroup$
1
  • $\begingroup$ wow now i finally understand thanks for the explanation :D $\endgroup$ – Lim Kha Shing Jul 20 '16 at 12:14
0
$\begingroup$

They're indeed equivalent (implication goes both ways). In fact

$$ p\Rightarrow q \equiv \neg(p \land \neg q) $$ and

$$ \neg q \Rightarrow \neg p \equiv \neg (\neg q \land \neg \neg p)\equiv \neg (p \land \neg q) $$

So the two are equal, and therefore one implies the other.

$\endgroup$
2
  • $\begingroup$ okay so they are implies each other. But what are the exactly the steps or laws I can use to prove it as tautology ? $\endgroup$ – Lim Kha Shing Jul 19 '16 at 15:20
  • $\begingroup$ If this does not convince you, you can simply write down the truth table, for all possible values for $p$ and $q$ and see what's the output. It will always be T. In fact, there is no way that the left hand side is T and the right hand side is F, because we showed that they are the same statement. $\endgroup$ – bartgol Jul 19 '16 at 15:22

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.