(Homework) Prove the law of syllogism

Trying to prove, by symbol manipulation, that if $(P \rightarrow Q) \wedge (Q \rightarrow R) \rightarrow (P \rightarrow R)$

I am stuck after doing these steps:

(P $\rightarrow Q) \wedge (Q \rightarrow R) \rightarrow (P \rightarrow R$)

$(\neg P \vee Q) \wedge (\neg Q \vee R) \rightarrow (P \rightarrow R)$

$\neg [ (\neg P \vee Q) \wedge (\neg Q \vee R) ] \vee (\neg P \vee R)$

$[\neg (\neg P \vee Q) \vee \neg (\neg Q \vee R) ] \vee (\neg P \vee R)$

$(P \wedge \neg Q) \vee (Q \wedge \neg R) \vee (\neg P \vee R)$

I am really clueless by this point, this is the first problem propositional calculus problem I ever try. I was thinking maybe if there was some way to negate one of the Qs so I could then group them together then maybe I could get somewhere but I'm not sure how.

Sorry if this is a bad use of LaTex, its my first time using it.

You want to prove that your first formula (expression) is a tautology (has value true, whatever the truth values of the variables $P$, $Q$, $R$).

Use repeatedly the rewrite rule $$A\to B\quad \rightsquigarrow\quad \neg A\vee B \ .$$ The given expression is then equivalent to $$\neg\bigl((\neg P\vee Q)\wedge(\neg Q\vee R)\bigr)\vee(\neg P \vee R)\ .\tag{1}$$ According to $\neg(A\wedge B)=\neg A\vee\neg B$ and its dual the left part of expression $(1)$ is equivalent to $$\neg(\neg P\vee Q)\vee\neg(\neg Q\vee R)=(P\wedge\neg Q)\vee(Q\wedge\neg R)=P\vee\neg R\ .$$ This shows that $(1)$ is equivalent with $$(P\vee\neg R)\vee(\neg P \vee R)\ ,$$ which is certainly true.

• Can you explain me how you get this: $$(P\wedge\neg Q)\vee(Q\wedge\neg R)=P\vee\neg R\ .$$ – Eduardo Sebastian Apr 28 at 3:28

There is no proposed equivalence in your proposition that you can prove through symbolic manipulation of one or both sides using logical equivalencies. You can use a truth-table to show that your proposed implication is a tautology.

Your work is simply only manipulating the statement that you are trying to prove. It does nothing in the way of proving it.

I take it you are trying to prove that if $(p\rightarrow q)$ and $(q\rightarrow r)$, then $p \rightarrow q$. You do this by taking as assumptions/premises $p \rightarrow q$ and $q\rightarrow r$, and you work to prove that these two premises necessarily imply $p \rightarrow r$, by using valid rules of inferences.

$(p\rightarrow q) \land (q \rightarrow r)\quad \text{premise}$

$p\rightarrow q\quad (1): \text{ (simplification from premise.)}$

$q\rightarrow r\quad (2): \text{ (simplification from premise)}$

$\quad$ Assume ${\bf p}\quad\text{ assumption}$.

$\quad$ Then the assumption with $(1)$, by modus ponens, gives us $\bf q$.

$\quad$ Now $q$, together with $(2)$, again by modus ponens, gives us $\bf r$.

Hence, having assumed $p$, we have deduce $r$. That is, given our premise, IF p, then r. That is, the indented portion of the proof justifies the use of $\rightarrow$-Introduction, namely:

$p \rightarrow r$, as desired.

Now we can validly claim that $$\Big((p\rightarrow q)\land (q\rightarrow r)\Big)\rightarrow (p \rightarrow r)$$

As you see, I've used the following valid rules of logical inference:

• simplification (aka $\land$-elimination),

• modus ponens (which some call $\rightarrow$-elimination, and

• $\rightarrow$-introduction

• Thank you for your answer. Would you know how to go about it just doing symbol manipulation using the different rules of logic? – nx__ Sep 6 '14 at 16:42

This is a bit old question but I would like to fix some formula deformation.

According to $\neg(A\wedge B)=\neg A\vee\neg B$ and its dual the left part of expression $(1)$ is equivalent to

$$\neg(\neg P\vee Q)\vee\neg(\neg Q\vee R)=(P\wedge\neg Q)\vee(Q\wedge\neg R)=P\vee\neg R\ .$$

This might be wrong. You can check this easily by drawing Venn-diagram.

I think the easiest way to "prove" this question is using truth table....but,

of course,

There is no proposed equivalence in your proposition that you can prove through symbolic manipulation of one or both sides using logical equivalencies. You can use a truth-table to show that your proposed implication is a tautology.

Anyway, give it a try.

First, as you can see in the question, you can deform the given formula like this.

$(P \rightarrow Q) \wedge (Q \rightarrow R) \rightarrow (P \rightarrow R)$

$\equiv (P \wedge \neg Q) \vee (Q \wedge \neg R) \vee (\neg P \vee R)$

used $\neg$ and $\vee$ instead of implication and used de Morgan's law.

$\equiv ((( P \wedge \neg Q) \vee Q) \wedge ((P \wedge \neg Q) \vee \neg R)) ) \vee (\neg P \vee R)$

applied distributive law to $(P \wedge \neg Q) \vee (Q \wedge \neg R)$ .

$\equiv ((( P \vee Q ) \wedge (\neg Q \vee Q)) \wedge ((P \vee \neg R) \wedge (\neg Q \vee \neg R)) ) \vee (\neg P \vee R)$

dist. law to the each of $(P \wedge \neg Q) \vee Q$ and $(P \wedge \neg Q) \vee \neg R$.

$\equiv ((( P \vee Q ) \wedge T)) \wedge ((P \vee \neg R) \wedge (\neg Q \vee \neg R)) ) \vee (\neg P \vee R)$

used $T \equiv A \vee \neg A$ for simplicity.

$\equiv (( P \vee Q ) \wedge (P \vee \neg R) \wedge (\neg Q \vee \neg R ) )\vee (\neg P \vee R)$

used $A \wedge T \equiv A$

and, use dist. law to ($(.....) \vee (\neg P \vee R))$).

$\equiv (( P \vee Q )\vee (\neg P \vee R)) \wedge ((P \vee \neg R)\vee (\neg P \vee R)) \wedge ((\neg Q \vee \neg R )\vee (\neg P \vee R))$

use associative law.

$\equiv (P \vee Q \vee \neg P \vee R) \wedge (P \vee \neg R\vee \neg P \vee R) \wedge (\neg Q \vee \neg R \vee \neg P \vee R)$

use $T \equiv A \vee \neg A$ and use $T \vee X \equiv T$

$\equiv (P \vee \neg P \vee Q \vee R) \wedge (P \vee \neg P \vee \neg R \vee R) \wedge (R \vee \neg R \vee \neg Q \vee \neg P )$ $\equiv (T \vee Q \vee R) \wedge (T \vee \neg R \vee R) \wedge (T \vee \neg Q \vee \neg P )$ $\equiv T \wedge T \wedge T$

finally,

$\equiv T$

Just use dist. law several times and you will get the answer.

HAVE A NICE DAY!

You can prove it using a truth table. A more intuition based "proof" would be to think of them as a stack of dominoes. p is the first domino, q is the second domino and r is the third domino. Since p knocked over (implied) q which knocked over (implied) r, we can say that p knocked over r.

As for a more formal proof I wouldn't know. Maybe try taking $[(p \rightarrow q) \wedge (q \rightarrow r)] \rightarrow (p \rightarrow r)$ (which is syllogism in a logical form) and reducing it to a tautology, but that is only a suggestion.

Here is an example using Modus Ponens (Also known as Rule of Detachment)

I just happened to help a friend out with this exact problem for an introductory discrete math course. The only difference is that it starts off with extra (i.e. unnecessary) square brackets, as this is how it was presented in the assignment.

The initial statement is transformed step-by-step strictly using operator precedence rules and logical equivalence transformations (as per the requirements of the assignment). Eventually, the statement is simplified to 'true', i.e. " T ", via Domination law, thus proving the initial statement is indeed a tautology.

Note: I was not consistent with declaring multiple uses of the same equivalence rule in a single step (i.e. "x2", "x3"), but it should be obvious enough, and the solution still holds.