3
$\begingroup$

I am looking for a way to prove that the statement, $[(p \to q) \land (q \to r)] \to (p \to r)$, is a tautology without the help of the truth table. By using only Laws and Theorems like De Morgan's Law, Domination Law, etc. Also, I can't use the rules of inference. Please help, thank you.

$\endgroup$
4
$\begingroup$

As correctly suggested by Wuestenfux, first you should decompose $\to$. Then, you should apply several logical equivalences to simplify your formula to $\top$ (a formula that is always true). A complete simplification of your formula, using the logical equivalences listed here, is the following:

\begin{align} &\big((p \to q) \land (q \to r) \big) \to (p \to r) \\ \equiv \ & \lnot \big( (\lnot p \lor q) \land (\lnot q \lor r) \big) \lor (\lnot p \lor r) &\text{decomposition of }\to \\ \equiv \ & \lnot (\lnot p \lor q) \lor \lnot (\lnot q \lor r) \lor \lnot p \lor r&\text{De Morgan} \\ \equiv \ & (\lnot\lnot p \land \lnot q) \lor (\lnot\lnot q \land \lnot r) \lor \lnot p \lor r &\text{De Morgan} \\ \equiv \ & \lnot p \lor (\lnot\lnot p \land \lnot q) \lor (\lnot\lnot q \land \lnot r) \lor r &\text{commutativity} \\ \equiv \ & \big((\lnot p \lor \lnot\lnot p) \land (\lnot p \lor \lnot q)\big) \lor \big((\lnot\lnot q \lor r) \land (\lnot r \lor r) \big) &\text{distributivity} \\ \equiv \ & \big(\top \land (\lnot p \lor \lnot q)\big) \lor \big((\lnot\lnot q \lor r) \land \top \big) &\text{negation law} \\ \equiv \ & (\lnot p \lor \lnot q) \lor (\lnot\lnot q \lor r) &\text{identity law} \\ \equiv \ & \lnot p \lor (\lnot q \lor \lnot\lnot q) \lor r &\text{associativity} \\ \equiv \ & \lnot p \lor \top \lor r &\text{negation law} \\ \equiv \ & \top &\text{domination law} \\ \end{align}

$\endgroup$
  • $\begingroup$ Thanks. So the problem on my solution was that, some parentheses weren't removed, that's why i kept on using the distribution law. I also didn't know that you can use associativity like that. Thanks for helping! $\endgroup$ – Francis Aaron Milano Oct 14 '18 at 9:31
1
$\begingroup$

Hint: $p\rightarrow q$ is equivalent to $\neg p\vee q$.

$\endgroup$
  • 1
    $\begingroup$ Thanks. But my main problem is that whenever I use that theorem then start using the distributive law, i get an infinite loop because instead of shortening the statement, it just gets longer. $\endgroup$ – Francis Aaron Milano Oct 14 '18 at 9:02
1
$\begingroup$

When it comes to simplifying statements, a very handy rule of equivalence is:

Reduction

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

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

If you have this rule, you can do start by doing what @Taroccoesbrocco does, but finish more quickly:

\begin{align} &\big((p \to q) \land (q \to r) \big) \to (p \to r) \\ \equiv \ & \lnot \big( (\lnot p \lor q) \land (\lnot q \lor r) \big) \lor (\lnot p \lor r) &\text{implication law} \\ \equiv \ & \lnot (\lnot p \lor q) \lor \lnot (\lnot q \lor r) \lor \lnot p \lor r&\text{De Morgan} \\ \equiv \ & (\lnot\lnot p \land \lnot q) \lor (\lnot\lnot q \land \lnot r) \lor \lnot p \lor r &\text{De Morgan} \\ \equiv \ & \lnot p \lor (\lnot\lnot p \land \lnot q) \lor (\lnot\lnot q \land \lnot r) \lor r &\text{commutativity} \\ \equiv \ & \lnot p \lor \lnot q \lor \lnot\lnot q \lor r &\text{reduction} \\ \equiv \ & \lnot p \lor \top \lor r &\text{complement} \\ \equiv \ & \top &\text{domination law} \\ \end{align}

You also typically don't need to do an explicit commutation if you have generalized conjunctions or disjunctions, though doing so does help the reader

$\endgroup$

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.