3
$\begingroup$

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.

  • 0
    @ncmathsadist I did it, but what I'm looking for is a way of solving this like Jon Bannon suggested.2012-07-26

2 Answers 2

3

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.

  • 0
    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.2012-07-27
1

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.

  • 0
    Th$a$nk you for your answer, William. I think I grasped the first reasoning (at least I could verify it $b$y me$a$ns of a truth ta$b$le), but not the second. Unfortun$a$tely, I'm not familiar with proof techniques yet, since I'm gradually advancing on the $b$ook. The only way I could find it possible to verify this would be through the application of basic laws of connectives.2012-07-26