2
$\begingroup$

Let $p$, $q$, and $r$ be any propositions. Then, using a chain of logical equivalences, how to establish the following logical identity? $$ \big( (p \rightarrow q) \land (q \rightarrow r) \big) \rightarrow \big( p \rightarrow r \big) \ \equiv \ T. $$

My Attempt:

In the following chain of equivalences, I will be using the same nomenclature as that used in Table 6, Sec. 1.3, of the book Discrete Mathematics and Its Applications by Kenneth H. Rosen, 8th edition.

We note that $$ \begin{align} &\qquad \big( (p \rightarrow q) \land (q \rightarrow r) \big) \rightarrow \big( p \rightarrow r \big) \\ &\equiv \left( \overline{ \left( \overline{p} \lor q \right) \land \left( \overline{q} \lor r \right) } \right) \lor \left( \overline{p} \lor r \right) \\ & \qquad \mbox{[ using the conditional-disjunction equivalence ]} \\ &\equiv \left( \left( \overline{ \overline{p} \lor q } \right) \lor \left( \overline{ \overline{q} \lor r } \right) \right) \lor \left( \overline{p} \lor r \right) \\ &\qquad \mbox{[ using a DeMorgan's law ]} \\ &\equiv \left( \left( \overline{ \overline{p}} \land \overline{q} \right) \lor \left( \overline{ \overline{q}} \land \overline{r} \right) \right) \lor \left( \overline{p} \lor r \right) \\ &\qquad \mbox{[ using a DeMorgan's law ]} \\ &\equiv \left( \left( p \land \overline{q} \right) \lor \left( q \land \overline{r} \right) \right) \lor \left( \overline{p} \lor r \right) \\ &\qquad \mbox{[ using the double-negation law ]} \\ &\equiv \left( \left( p \land \overline{q} \right) \lor \overline{p} \right) \ \lor \ \left( \left( q \land \overline{r} \right) \lor r \right) \\ &\qquad \mbox{[ using the associativity and commutativity of $\lor$ ]} \\ &\equiv \left( \left( p \lor \overline{p} \right) \land \left( \overline{q} \lor \overline{p} \right) \right) \ \lor \ \left( \left( q \lor r \right) \land \left( \overline{r} \lor r \right) \right) \\ &\qquad \mbox{[ using the distributivity of $\lor$ over $\land$ ]} \\ &\equiv \left( T \land \left( \overline{q} \lor \overline{p} \right) \right) \ \lor \ \left( \left( q \lor r \right) \land T \right) \\ &\qquad \mbox{[ using a negation law ]} \\ &\equiv \left( \overline{q} \lor \overline{p} \right) \ \lor \ \left( q \lor r \right) \\ &\qquad \mbox{[ using an identity law ]} \\ &\equiv \left( \overline{q} \lor q \right)\ \lor \ \left( \overline{p} \lor r \right) \\ &\qquad \mbox{[ using the associativity and commutativity of $\lor$ ]} \\ &\equiv T \ \lor \ \left( \overline{p} \lor r \right) \\ &\qquad \mbox{[ using a negation law ]} \\ &\equiv T. \\ &\qquad \mbox{[ using a domination law ]} \end{align} $$

Is the above calculation correct and clear enough? If so, is this the shortest possible chain of logical equivalences necessary for establishing the tautology in question, using the same machinary as developed by Rosen up to Sec. 1.3?

Or, are there any issues?

$\endgroup$
3
  • $\begingroup$ Your solution is correct and clear. I've no idea if it's the shortest possible method. $\endgroup$ Nov 24, 2023 at 11:42
  • 1
    $\begingroup$ You can’t expect us to have a copy of Rosen just laying around, so if you want an answer to this question you need to include the rules in your post. $\endgroup$
    – Bram28
    Nov 24, 2023 at 14:06
  • 2
    $\begingroup$ Yikes! Unless you are required to use such "chains of logical equivalence" for coursework, you should really consider using some form of natural deduction. Using only rules for conditional proof, elimination of $\land$ (split), and elimination of $\implies$ (detachment), I was able to formally prove your statement in only 8 lines. $\endgroup$ Nov 24, 2023 at 15:23

1 Answer 1

1
$\begingroup$

I'm with Dan Christensen. It is not only just horribly messy to use "chains of logical equivalence" it completely obscures why $((p \rightarrow q) \land (q \rightarrow r)) \rightarrow \big( p \rightarrow r)$ is logically true on any sensible treatment of the conditional (including e.g. in constructive frameworks where De Morgan's Laws, for example, aren't available).

It is worth seeing this, and as Dan says, a natural deduction framework makes this absolutely obvious:

$\quad \quad | \quad \quad (p \to q) \land (q \to r)\quad\quad temporary\ assumption\\ \quad \quad | \quad \quad (p \to q)\quad\quad\quad\quad\quad unpacking\ the\ conjunction\\ \quad \quad | \quad \quad (q \to r)\\ \quad \quad | \quad \quad | \quad \quad p\quad \quad\quad\quad\quad another\ temporary\ assumption\\ \quad \quad | \quad \quad | \quad \quad q\quad \quad\quad\quad\quad modus\ ponens!\\ \quad \quad | \quad \quad | \quad \quad r\quad \quad\quad\quad\quad modus\ ponens!\\ \quad \quad | \quad \quad (p \to r)\quad\quad\quad\quad\quad we've\ shown\ r\ follows\ from\ p\\ ((p \to q) \land (q \to r)) \to (p \to r)\quad we've\ shown\ (p \to r)\ follows\ from\ (p \to q) \land (q \to r) $

That's entirely intuitive: if we are given both $p \to q$ and $q \to r$ then obviously the supposition that $p$ gets you to $r$, so $p \to r$ -- and that's just using basic principles about the conditional (and unpacking the conjunction). There's nothing here that depends on the conditional-disjunction equivalence (not valid in e.g. intuitionistic logic) or on your use of De Morgan's laws (ditto). So I'd say that the use of "use chains of logical equivalence" is to be deprecated as hiding what is going.

Of course this is not intended as any criticism of the OP, assuming Rosen's book has been thrust upon them!

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .