6
$\begingroup$

I am having trouble with a problem in the book I'm self-studying from. It says the following:

Show that $(P\to Q) \land (Q \to R) $ is equivalent to $(P \to R)$ $\land [(P \iff Q) \lor (R \iff Q)]$ by using logical connectives

I have dedicated so far a hefty amount of time on this problem, and now I'm asking you guys advice/hints or solution as to how to solve this problem. Here is one of the methods I used. Point any flaws that I made.

$(P\to Q) \land (Q \to R) $

(Conditional Law)

$(\neg P \lor Q) \land (\neg Q \lor R) \Rightarrow$

(Distributive Law)

$[(\neg P \land \neg Q)] \lor [Q \land (\neg Q \lor R)] \Rightarrow$

(Distributive Law)

$[(\neg P \land \neg Q) \lor (R \land \neg P)] \lor [(Q \land \neg Q) \lor (R \land Q)] \Rightarrow$

Contradiction

$[(\neg P \land \neg Q) \lor (R \land \neg P)] \lor [(Contradiction) \lor (R \land Q)] \Rightarrow$

(Contradiction Law)

$[(\neg P \land \neg Q) \lor (R \land \neg P)] \lor [ (R \land Q)] \Rightarrow$

Typically at around step five I get stuck or get confused because the problem gets messy. I know you could show it by using the truth-tables. However, the problem says use logical connectives. My questions are: Am I on the right track into solving this problem? Did I make any mistakes? What advice/hints would you give me in my path to solving this problem?

Edit Some of you guys want me to list the laws. Here they are:

DeMorgan's laws

$\neg(P \land Q) \equiv \neg P \lor \neg Q$

$\neg(P \lor Q) \equiv \neg P \land \neg Q$

Commutative laws

$P \lor Q \equiv Q \lor P$

$Q\lor P \equiv P \lor Q$

Associative Laws

$P \land (Q \land R) \equiv (P \land Q) \land R $

$(P \land Q) \land R \equiv P \land (Q \land R) $

Idempotent Laws

$P \land P \equiv P$

$P \lor P \equiv P$

Distributive Laws

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

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

Absorption Laws

$P \lor (P \land Q) \equiv P$

$P \land (P \lor Q) \equiv P$

Tautology Laws

$P \land (tautology) \equiv P$

$P \lor (tautology) \equiv (tautology)$

Contradiction Laws

$P \land (contradiction) \equiv (contradiction)$

$P \lor (contradiction) \equiv P$

Conditional laws

$P \to Q \equiv \neg P \lor Q$

$P \to Q \equiv \neg (P \land \neg Q)$

$\endgroup$
9
  • 1
    $\begingroup$ What does "by using logical connectives" mean? $\endgroup$ Sep 23, 2013 at 20:07
  • $\begingroup$ @PeterSmith I guess the author means by using the laws that involves connectives like $\lor ,\land,\neg,\to$ . $\endgroup$
    – user93971
    Sep 23, 2013 at 20:25
  • 1
    $\begingroup$ (Out of interest, which book is this?) $\endgroup$ Sep 23, 2013 at 20:26
  • $\begingroup$ @PeterSmith How to prove it by Velleman $\endgroup$
    – user93971
    Sep 23, 2013 at 20:33
  • 1
    $\begingroup$ @DougSpoonwood I think I understand your point. However, it's up to the reader to understand which conditional law is being used. The writer can only do so much in how he arrived from A to B. I do not want this be a very technical problem with a very technical solution. For instance , I don't want to be very technical that 1+1=2. I just want a solution from someone that is clear enough for me to understand. If it's not clear enough for me, I'll ask questions to gain a better picture. $\endgroup$
    – user93971
    Sep 25, 2013 at 17:04

4 Answers 4

1
$\begingroup$

What we would like to prove is a conjunction, so it suffices to prove each conjunct separately and then glue them together at the end. This problem would probably be easier and more intuitive using proof by contradiction, but after talking with the asker, I will provide a direct proof.

$$\begin{array}{lr} 1. & (P \rightarrow Q)\wedge(Q \rightarrow R) & \text{Premise} \\ 2. & P \rightarrow Q &\text{Simplification, 1}\\ 3. & Q \rightarrow R & \text{Simplification, 1}\\ 4. & \neg{P} \vee Q & \text{Conditional Law, 2}\\ 5. & \neg{Q} \vee R & \text{Conditional Law, 3}\\ 6. & Q \vee \neg{Q} & \text{Tautology} \\ 7. & \neg{P} \vee R & \text{Constructive Dilemma, 4,5,6}\\ 8. & P \rightarrow R & \text{Conditional Law, 7}\\ 9. & (P \rightarrow Q) \vee (Q \rightarrow R) &\text{Addition, 2}\\ 10. & (Q \rightarrow P) \vee (Q \rightarrow R) &\text{Addition, 3}\\ 11. & (P \rightarrow Q) \vee (R \rightarrow Q) &\text{Addition, 2}\\ 12. & Q \vee \neg{Q} & \text{Tautology}\\ 13. & (Q \vee \neg{Q}) \vee (P \vee \neg{R}) & \text{Addidition, 12}\\ 14. & (\neg{Q} \vee P) \vee (\neg{R} \vee Q) & \text{Associative Law, 13}\\ 15. & (Q \rightarrow P) \vee (R \rightarrow Q) & \text{Conditional Law, 14}\\ 16. & \big((P \rightarrow Q) \vee (Q \rightarrow R)\big)\wedge \big((Q \rightarrow P) \vee (Q \rightarrow R)\big) & \text{Conjunction, 9,10}\\ 17. & \big((P \rightarrow Q) \vee (R \rightarrow Q)\big)\wedge \big((Q \rightarrow P) \vee (R \rightarrow Q)\big) & \text{Conjunction, 11,15}\\ 18. & \big((P \rightarrow Q) \wedge (Q \rightarrow P)\big)\vee (Q \rightarrow R) & \text{Distributive Law, 16}\\ 19. & \big((P \rightarrow Q) \wedge (Q \rightarrow P)\big)\vee (R \rightarrow Q) & \text{Distributive Law, 17}\\ 20. & \Big(\big((P \rightarrow Q) \wedge (Q \rightarrow P)\big)\vee (Q \rightarrow R)\Big) \wedge & \\ &\Big(\big((P \rightarrow Q) \wedge (Q \rightarrow P)\big)\vee (R \rightarrow Q)\Big) & \text{Conjunction, 18,19}\\ 21. & \big((P \rightarrow Q) \wedge (Q \rightarrow P)\big)\vee \big((Q \rightarrow R) \wedge (R \rightarrow Q) \big) & \text{Distributive Law, 20}\\ 22. & (P \equiv Q) \vee (Q \equiv R) & \text{Definition of Biconditional, 21}\\ \therefore & (P \rightarrow R)\wedge \big((P \equiv Q) \vee (Q \equiv R)\big) & \text{Conjunction, 8,22} \end{array}$$

As desired.

$\endgroup$
3
  • $\begingroup$ I think when you moved from 13. to 14. you used both the associative property and the commutativie property of $\lor$. It didn't result in an invalidity though. I don't see how this enables us to move from 22. to 1. ("addition" clearly is NOT reversible... (p $\lor$ q) implies q is NOT an inference rule permitted here). So, unless I've missed something, I think you've only provided "half" of a solution. $\endgroup$ Sep 26, 2013 at 5:06
  • 1
    $\begingroup$ @DougSpoonwood You're right about 13 to 14. I'm sure if you look hard enough there are several times where I combine some uses of associativity and commutativity with other rules. Its such a trivial step, I'm willing to sacrifice rigour for time/readability. About your second point, you're 100% correct. I only proved one direction of the equivalence, thanks for the heads up. I'll work on the other half today, which should be easier. I may do it using proof by contradiction since the asker asked about it in chat. $\endgroup$ Sep 26, 2013 at 21:31
  • $\begingroup$ I must admit that you have a very strong ming.I am waiting for the other half of the proof using contradiction $\endgroup$
    – user149368
    May 28, 2022 at 19:10
0
$\begingroup$

I use Polish notation.

By distribution we have 1.

  1. KCprAEpqErq = AKCprEpqKCprErq.

Suppose KCprEpq. Then, by two conjunction eliminations we have Cpr and Epq. Suppose p. Then by detachment, we have r. Also, by detachment we have q (if we have "p" and "Epq", then "q" also). By conditional introduction, we have Cpq. Next suppose q. Since we have Epq also, we can then "reverse detach" p. Since we have p as well as Cpr, we can thus detach r. By conditional introduction, we have Cqr. Thus, by conjunction introduction we have KCpqCqr. So, KCprEpq yields KCpqCqr.

Now suppose KCprErq. Then, by two conjunction eliminations we have Cpr and Erq. Suppose p. Then since we have Cpr also, we can detach r. Since we have Erq also, we can detach q. Thus, Cpq. Next suppose q. Then since we have Erq, we can detach r. Thus, by conditional introduction we have Cqr. So, by conjunction introduction we obtain KCpqCqr.

Since both cases lead to KCpqCqr, AKCprEpqKCprErq implies KCpqCqr.

Suppose KCpqCqr. Then by two conjunction eliminations we have Cpq and Cqr. Suppose p. Suppose p again. Then since we have Cpq also, we obtain q. Since we have q and Cqr, we obtain r. Discharging the first p we obtain Cpr. Now we still have Cpq in play. So, by detachment and the first p supposed, we obtain q. There exists a law which says $\vdash$CpCqEpq. So, thus by two detachments we obtain Epq. By disjunction introduction we thus obtain AEpqErq. By conjunction introduction we then have KCprAEpqErq. Now discharging the first p we have CpKCprAEpqErq.

Suppose Np. We still have Cpq and Cqr. Since there exists a law which says CNpCpr, and we have Np, we get Cpr by detachment. Suppose Nq. There exists a law which says $\vdash$CNpCNqEpq. So, from that law, Np, and Nq we obtain Epq. By disjunction introduction we thus have AEpqErq. So, by conjunction introduction we have KCprAEpqErq. Discharging Nq, we have CNqKCprAEpqErq. Suppose q. Since we have Cqr, by detachment we have r. Since we a law which says $\vdash$CrCqErq, by two detachments we pass to Erq. By disjunction introduction we have AEpqErq. By conjunction introduction we then get KCprAEpqErq. Discharging q we have CqKCprAEpqErq. Now, we have AqNq. Consequently, via AqNq, CqKCprAEpqErq, and CNqKCprAEpqErq we obtain KCprAEpqErq by disjunction elimination under the scope of the hypothesis Np. Thus, discharging Np we obtain CNpKCprAEpqErq.

Now, we have ApNp, CpKCprAEpqErq, and CNpKCprAEpqErq. Thus, by disjunction elimination we obtain KCprAEpqEqr. We still have KCpqCqr in place, and thus by conditional introduction we obtain CKCpqCqrKCprAEpqEqr.

Since we had CKCprAEpqEqrKCpqCqr above, we now infer EKCpqCqrKCprAEpqEqr.

$\endgroup$
3
  • $\begingroup$ Wow! This is super confusing LOL! But it looks like you took a lot of time to write it. I never thought this could possible be a solution. I will look up the Polish Notation you linked. $\endgroup$
    – user93971
    Sep 26, 2013 at 2:43
  • $\begingroup$ Why do you use Polish notation if the OP clearly doesn't? $\endgroup$
    – Pedro
    Sep 26, 2013 at 2:49
  • $\begingroup$ @PedroTamaroff I find it easier to use in some respects (after having learned it). I found this problem fairly difficult for me at present. $\endgroup$ Sep 26, 2013 at 4:55
0
$\begingroup$

Here's a more complete answer using equivalences only:

I reduce each of the two expressions as much as possible.

(All of these are equivalences. I'll freely use commutative/associative laws in what follows to disregard order and drop excess parentheses.)

  1. $(P\rightarrow Q) \land (Q \rightarrow R)$

  2. $(\lnot P \lor Q) \land (\lnot Q \lor R)$ (def. of $\rightarrow$)

  3. $[\lnot P \land (\lnot Q \lor R)] \lor [Q \land (\lnot Q \lor R)]$ (distrib)

  4. $(\lnot P \land \lnot Q) \lor (\lnot P \land R) \lor (Q \land R)$ (distrib & tautology [skipped some intermediates])

Now for the other side:

  1. $(P \rightarrow R) \land [(P \leftrightarrow Q) \lor (Q \leftrightarrow R)]$

  2. $(\lnot P \lor R) \land [(P \land Q) \lor (\lnot P \land \lnot Q) \lor (R \land Q) \lor (\lnot R \land \lnot Q)]$ (see the lemma below)

  3. $(\lnot P \land P \land Q) \lor (\lnot P \land \lnot P \land Q) \lor (\lnot P \land R \land Q) \lor (\lnot P \land \lnot R \land \lnot Q) \lor (R \land P \land Q) \lor (R \land \lnot P \land \lnot Q) \lor (R \land R \land Q) \lor (R \land \lnot R \land \lnot Q)$ (distrib)

  4. $(\lnot P \land Q) \lor (\lnot P \land R \land Q) \lor (\lnot P \land \lnot R \land \lnot Q) \lor (R \land P \land Q) \lor (R \land \lnot P \land \lnot Q) \lor (R \land Q)$ (tautology and idempotent)

  5. $(R \land Q) \lor [(\lnot P \land R \land Q) \lor (\lnot P \land R \land \lnot Q)] \lor [(\lnot P \land \lnot Q \land R) \lor (\lnot P \land \lnot Q \land \lnot R)]$ (comm/assoc to rearrange, idempotent to duplicate $(\lnot P \land R \land \lnot Q)$ and absorption to get rid of $(R \land P \land Q)$)

  6. $(R\land Q) \lor (\lnot P \land R) \lor (\lnot P \land \lnot Q)$ (distrib and tautology)

Now notice 4 at the top is the same as 6 on the bottom, by comm/assoc laws.

The Lemma noted above: $A \leftrightarrow B$ is equivalent to $(A\land B) \lor (\lnot A \land \lnot B)$. Showing this: It's $(A \rightarrow B) \land (B \rightarrow A)$ which is equivalent to $(\lnot A \lor B) \land (A \lor \lnot B)$ which, distributing twice, is equivalent to $(\lnot A \land A) \lor (\lnot A \land \lnot B) \lor (B \land A) \lor (B \land \lnot B)$ which is $(\lnot A \land \lnot B) \lor (B \land A)$ by tautology laws.

$\endgroup$
0
$\begingroup$

You can use implication's transitivity

(proof here:http://www.personal.psu.edu/tcr2/311w/iftransitive.pdf)

Just like: $$((P\implies Q)\wedge (Q\implies R))\iff(P\implies R)$$ We have:

$$(P\implies R)\wedge[(P\iff Q)\vee(Q\iff R)]\iff$$ $$(P\implies R)\wedge[(P\implies Q \wedge Q\implies P)\vee (Q\implies R\wedge R\implies Q)]\iff$$ $$((P\implies R \wedge P\implies Q\wedge Q\implies P)\vee(P\implies R\wedge Q\implies R\wedge R\implies Q))\iff$$ $$((Q\implies P\wedge P\implies R\wedge P\implies Q)\vee(Q\implies R\wedge P\implies R\wedge R\implies Q))\iff $$ $$((Q\implies R \wedge P\implies Q)\vee(Q\implies R\wedge P\implies Q))\iff(Q\implies R\wedge P\implies Q)$$ $$\iff(P\implies Q\wedge Q\implies R)\iff(P\implies R)$$ $$Q.E.D.$$

$\endgroup$

You must log in to answer this question.