I have been attempting to use identities to get to the answer but I am unable to get anywhere. Here is the equation I am trying to prove tautological without using truth tables:

$[(p\rightarrow q) \land (q \rightarrow r)] \rightarrow (p \rightarrow r )$

And here is my attempt at using identities to work my way up. (a link to a page with a table of logical equivalence identities: http://en.wikipedia.org/wiki/Logical_equivalence)

$\lnot [(p \rightarrow q) \land (q \rightarrow r)] \lor (p \rightarrow r)$

$\lnot [(\lnot p \lor q) \land (q \rightarrow r)] \lor (p \rightarrow r)$

$[\lnot (\lnot p \lor q) \land \lnot (q \rightarrow r)] \lor (p \rightarrow r)$

$[(p\land \lnot q) \land (q \land \lnot r)] \lor (p \rightarrow r)$

I don't know where to go from there.

  • $\begingroup$ In fourth step you did not apply the nagasion properly due to nagasion sign the AND operator will change into OR operator and then the whole question will solve very easily. $\endgroup$
    – user620344
    Nov 27 '18 at 18:55

In your approach, you made a mistake in the derivation on the third line, it should be: $$[\lnot (\lnot p \lor q) \lor \lnot (q \rightarrow r)] \lor (p \rightarrow r)$$

so that your fourth line becomes:

$$[(p\land \lnot q) \lor (q \land \lnot r)] \lor (p \rightarrow r)$$

At this point, there isn't really much to be done except for a tedious case-by-case argument ("Suppose $p$ is true. [...] Now suppose $p$ is false [...].").

Let us take a step back. When proving a tautology (which is not easily seen to be so by virtue of known theorems), it is often a more productive technique to try and prove that its negation is a contradiction. The idea behind this is that if the original $\phi$ is to be a tautology, then by investigating its negation $\neg \phi$, we will obtain stricter and stricter conditions on $p, q, r$ to allow $\neg \phi$ to be true, until we get to the conclusion that there are no possibilities left, i.e. that $\phi$ is a tautology.

Essentially, one converts a universal check ("All interpretations yield true") to a search for an example ("Some interpretation does not yield true") -- keeping in mind that we want the latter search to be fruitless. Basically, it's easier to find the black sheep in a flock than to count the white ones. For a more detailed account of this approach, you can search for terms like semantic tableaux or analytic tableaux.

Returning to our concrete example, let us see how this approach works out. We use repeatedly the equivalences $p \to q \iff \neg p \lor q$ and $\neg (p \to q) \iff p \land \neg q$:

\begin{align*} & \neg\big([(p\rightarrow q) \land (q \rightarrow r)] \rightarrow (p \rightarrow r )\big)\\ \iff& (p\to q)\land (q\to r) \land \neg(p \to r) \\ \iff& (\neg p \lor q) \land (\neg q \lor r) \land p \land \neg r \end{align*}

From the last two clauses, we see that $p$ must be true and $r$ must be false. But then for $\neg p \lor q$ to be true, $q$ must be true as well. Similarly, $\neg q$ must be true in order for $\neg q \lor r$ to be true as well. Hence we need $q$ to be both true and false at the same time, a contradiction.

We conclude that $[(p\rightarrow q) \land (q \rightarrow r)] \rightarrow (p \rightarrow r )$ is a tautology, as desired.


In your approach you made a mistake when applying De Morgan's Law, this is how I solved it:

$[(p \to q) \land (q \to r)] \to (p \to r)$

$\lnot[(p \to q) \land (q \to r)] \lor (p \to r) \qquad \qquad \qquad \quad \ \ \text{(Logical Equivalence)}$

$[\lnot(p \to q) \lor \lnot(q \to r)] \lor (p \to r) \qquad \qquad \qquad \ \ \ \text{(De Morgan's Law)}$

$[(p \land \lnot q) \lor (q \land \lnot r)] \lor (\lnot p \lor r) \qquad \qquad \qquad \quad \ \text{(Logical Equivalence)}$

$[(p \land \lnot q) \lor \lnot p] \lor [(q \land \lnot r) \lor r] \qquad \qquad \qquad \quad \ \ \text{(Associative and Commutative Laws)}$

$[(p \lor \lnot p) \land (\lnot q \lor \lnot p)] \lor [(q \lor r) \land (\lnot r \lor r)] \quad \quad \text{(Distributive Laws)}$

$[ \mathbf T \land (\lnot q \lor \lnot p)] \lor [(q \lor r) \land \mathbf T] \qquad \qquad \qquad \quad \ \ \text{(Negation Law)}$

$(\lnot q \lor \lnot p) \lor (q \lor r) \qquad \qquad \qquad \qquad \qquad \qquad \ \ \text{(Identity Law)}$

$(\lnot q \lor q) \lor (\lnot p \lor r) \qquad \qquad \qquad \qquad \qquad \qquad \ \ \text{(Associative and Commutative Laws)}$

$\mathbf T\lor (\lnot p \lor r) \qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad \ \text{(Negation Law)}$

$ \equiv \mathbf T \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \qquad \ \ \ \text{(Domination Law)}$


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.