This question already has an answer here:

I've been trying to solve the exercise 7(a) of Velleman's "How To Prove It" and haven't succeeded. It asks the verification of the following equivalence:

$$ (P \to Q) \land (Q \to R) = (P \to R) \land ((P \leftrightarrow Q) \lor (R \leftrightarrow Q)) $$

While checking the website for help, I found a question posed by the user "yamad", who, despite his concern with a step futher on the resolution, came to this possible reduced form:

$$(\lnot P \lor Q) \land (\lnot Q \lor R) \land (\lnot P \lor R)$$

The problem is I couldn't even get to this step or any other simplfied form. I would appreciate if someone could provide me a hint.


marked as duplicate by Thomas Andrews, Daniel Robert-Nicoud, M Turgeon, Dan Rust, user63181 Jan 3 '14 at 20:20

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • 6
    $\begingroup$ Did you try to blast it with an eight-row truth table? $\endgroup$ – ncmathsadist Jul 26 '12 at 1:03
  • $\begingroup$ I'd start by changing things like $P \to Q$ into $\lnot P \lor Q$ everywhere they show up. This should get you some partial progress. $\endgroup$ – Jon Bannon Jul 26 '12 at 1:11
  • $\begingroup$ Sure! math.stackexchange.com/questions/135623/… $\endgroup$ – user36546 Jul 26 '12 at 2:12
  • $\begingroup$ @ncmathsadist I did it, but what I'm looking for is a way of solving this like Jon Bannon suggested. $\endgroup$ – user36546 Jul 26 '12 at 2:29

Let's take the RHS and simplify it a bit:

$$ (P \to R) \land ((P \leftrightarrow Q) \color{red}{\lor} (R \leftrightarrow Q)) \tag{1} $$ Distribute $(P \to R)$ into the parenthesis: $$(P \to R) \land (P \leftrightarrow Q) \quad \color{red}{\lor} \quad (P \to R) \land (R \leftrightarrow Q) \tag{2} $$ Use the definition of $A \leftrightarrow B \vdash (A \to B) \land (B \to A):$ $$ \color{blue}{(P \to R)} \land (P \to Q) \land \color{blue}{(Q \to P)} \quad \color{red}{\lor} \quad \color{green}{(P \to R)} \land \color{green}{(R \to Q)} \land (Q \to R) \tag{3} $$ At this point we need to assume the result $(A \to B) \land (B \to C) \vdash (A \to C):$ $$ (P \to Q) \land \color{blue}{(Q \to R)} \quad \color{red}{\lor} \quad \color{green}{(P \to Q)} \land (Q \to R) \tag{4} $$ We know $A \lor A \vdash A:$ $$ (P \to Q) \land (Q \to R) \tag{5} $$

Now we need to prove that $$(A \to B) \land (B \to C) \vdash (A \to C)$$ which we could verify using a truth table. But the correct proof needs to use the axioms and theorems of your proof system.

  • $\begingroup$ I tryed $(A \to B) \land (B \to C)$ on a truth table and it's not equivalent to $(A \to C)$, namely when the truth values for $A$, $B$, and $C$ are either (T, F, T) or (F, T, F). Nevetheless, $[(A \to B) \land (B \to C)] \to (A \to C)$ is indeed a tautology. Is it allowed to make the substitution above, even so? $\endgroup$ – user36546 Jul 27 '12 at 4:26
  • $\begingroup$ Yes, you can make the substitution since $ [(A→B)∧(B→C)]→(A→C)$ is a tautology. First, I assume you work in propositional logic which is sound and complete and hence semantic entailment $\vDash$ is equivalent to $⊢.$ Second, $⊢$ is syntactic entailment, which is not an "equivalence" between expressions. $A ⊢ B$ in a sound & complete systems iff $A → B.$ $\endgroup$ – user2468 Jul 27 '12 at 5:19
  • $\begingroup$ But, I mean, the way I see how the transition from (3) to (4) occurs is by means of the possibility of "interreplaceability" of statements, which I called equivalence. As such, how can I make that transition, if the statements $(P→R)∧(Q→P)$ and $(Q→R)$, for example, are not logically equivalent statements? Sorry if I missed something from your previous comment. $\endgroup$ – user36546 Jul 27 '12 at 14:12

The easiest way to verify the identity is to "blast it with an eight-row truth table" as ncmathsadist stated.

Alternatively, you can informally reason this out. If you take the time, you can formalize everything below:

Suppose $(P \rightarrow Q) \wedge (Q \rightarrow R)$. Then you have $P \rightarrow R$. Now suppose that $\neg((P \leftrightarrow Q) \vee (Q \leftrightarrow R))$. Then (without loss of generality) $P = T$, $Q = F$ and $R = T$. But then $(P \rightarrow Q) \wedge (Q \rightarrow R)$ is false. You can check the other cases.

Now suppose that $(P \rightarrow R) \wedge ((P \leftrightarrow Q) \vee (Q \leftrightarrow R))$. So suppose you have $(P \rightarrow R)$ and $P \equiv Q$. Then you automatically have $P \rightarrow Q$. You also have $Q \rightarrow P$ and $P \rightarrow Q$. So you have $Q \rightarrow R$. Thus you have $(P \rightarrow Q) \wedge (Q \rightarrow R)$. The other case is done similarly.

  • $\begingroup$ Thank you for your answer, William. I think I grasped the first reasoning (at least I could verify it by means of a truth table), but not the second. Unfortunately, I'm not familiar with proof techniques yet, since I'm gradually advancing on the book. The only way I could find it possible to verify this would be through the application of basic laws of connectives. $\endgroup$ – user36546 Jul 26 '12 at 2:07