I came across the following problem in a book:

Show that if $p, q$, and $r$ are compound propositions such that $p$ and $q$ are logically equivalent and $q$ and $r$ are logically equivalent, then $p$ and $r$ are logically equivalent.

The book's solution certainly makes sense:

To say that $p$ and $q$ are logically equivalent is to say that the truth tables for $p$ and $q$ are identical; similarly, to say that $q$ and $r$ are logically equivalent is to say that the truth tables for $q$ and $r$ are identical. Clearly if the truth tables for $p$ and $q$ are identical, and the truth tables for $q$ and $r$ are identical, then the truth tables for $p$ and $r$ are identical. Therefore $p$ and $r$ are logically equivalent.

I decided to "symbolically translate" the problem in the book:

Show that $[(p\leftrightarrow q)\land(q\leftrightarrow r)]\to(p\leftrightarrow r)$ is a tautology.

I wrote out a truth table and everything checks out, as expected (and as mentioned in the book's solution). My question is whether or not there is a more "algebraic" solution using equivalences (not resorting to CNF or DNF).

Any ideas?

  • 1
    $\begingroup$ Which axioms and accepted theorems do you have? There are many different logical systems, and proofs of simple statements like these depend greatly on your system. $\endgroup$ – Rory Daulton Sep 20 '15 at 0:37
  • $\begingroup$ @RoryDaulton I only have basic first-order logic in mind--tools available include all those one might expect for an introductory discrete math course (identity, domination, idempotent, double negation, commutative, associative, distributive, De Morgan, absorption, negation, etc. laws). $\endgroup$ – Daniel W. Farlow Sep 20 '15 at 0:44
  • 1
    $\begingroup$ Using such equivalences means that you have a first-order theory with equality which underlies your reasoning process. Weaker theories, that is theories that assume less, such as natural deduction or axiomatic propositional calculi can solve this problem without having a notion of equality. $\endgroup$ – Doug Spoonwood Sep 23 '15 at 0:19

I managed to work out a solution, and I thought I would share even though it is rather hideous (picture posted to make formatting much more pleasant to read). enter image description here

  • $\begingroup$ Oh, that school algebra. It's so much easier in modern logic. Intuitionistic type theory lets us write a one-line proof for that and check it on a PC. Take a look at line 15, it's there: ideone.com/X59Rvx $\endgroup$ – polkovnikov.ph Jan 15 '16 at 22:25

Here is a proof which is slightly more algebraic than the "just look at the truth tables" one while not ballooning out into something lengthy and potentially unreadable:

\begin{array}l (p \leftrightarrow q) \land (q \leftrightarrow r) \\ = \{\mbox{definition of $\leftrightarrow$}\} \\ (p \rightarrow q) \land (q \rightarrow p) \land (q \rightarrow r) \land (r \rightarrow q) \\ = \{\mbox{commutativity of $\land$}\} \\ (p \rightarrow q) \land (q \rightarrow r) \land (r \rightarrow q) \land (q \rightarrow p) \\ \implies \{\mbox{transitivity of $\rightarrow$}\} \\ (p \rightarrow r) \land (r \rightarrow p) \\ = \{\mbox{definition of $\leftrightarrow$}\} \\ p \leftrightarrow r \end{array}

The only step in this chain that you may consider ill-founded is the "transitivity of $\rightarrow$" step; but we can pretty easily prove that separately if that's wanted:

\begin{array}l (p \rightarrow q) \land (q \rightarrow r) \\ = \{\mbox{definition of $\rightarrow$}\} \\ (\lnot p \lor q) \land (\lnot q \lor r) \\ = \{\mbox{distributivity}\} \\ (\lnot p \land \lnot q) \lor (\lnot p \land r) \lor (q \land \lnot q) \lor (q \land r) \\ \implies \{\mbox{weakening}\} \\ \lnot p \lor \lnot p \lor (q \land \lnot q) \lor r \\ = \{\mbox{simplification}\} \\ \lnot p \lor r \\ = \{\mbox{definition of $\rightarrow$}\} \\ p \rightarrow r \end{array}

The line marked "simplification" actually uses a number of algebraic facts -- but I think they are clear enough to the human reader.


I assume you accept that $a\Rightarrow b$ is equivalent to $\tilde{} a \vee b$

and that $c \Leftrightarrow d$ is equivalent to $(c\Rightarrow d) \wedge (d\Rightarrow c)$.

Then $x \Leftrightarrow y$ is equivalent to $(\tilde{} x \vee y) \wedge (\tilde{} y\vee x )$.

AND is distributive over OR, so $x \Leftrightarrow y$ is equivalent to $((\tilde{} x \vee y) \wedge \tilde{} y) \vee ((\tilde{} x \vee y) \wedge x )$.

Thus $x \Leftrightarrow y$ is equivalent to $(((\tilde{} x \wedge \tilde{} y)\vee(y \wedge \tilde{}y)) \vee ((\tilde{} x \wedge x)\vee(y \wedge x)))$.

This gives us $(((\tilde{} x \wedge \tilde{} y)\vee 0) \vee (0\vee(y \wedge x)))$.

This gives us $((\tilde{} x \wedge \tilde{} y) \vee (y \wedge x))$.

Try using this as a starting pointy for your $p$, $q$ and $r$ statement.


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.