(Homework) Prove the law of syllogism

Question

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.

Answer 1

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.

Sorry for my poor English and thanks for your reading.

HAVE A NICE DAY!

Answer 2

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.

Answer 3

This question is quite old by now but I ran into the same problem and found a simpler solution than the ones listed here.

I proceed from where OP left off. The key is to move the 2 operands of the last disjunction. \begin{array}{l@{\quad}l} (P\land\neg Q)\lor(Q\land\neg R)\lor(\neg P\lor R) & \text{from OP}\\ (P\land\neg Q)\lor(Q\land\neg R)\lor \neg P\lor R & \text{remove last parenthesis pair}\\ ((P\land\neg Q)\lor \neg P)\lor((Q\land\neg R)\lor R) & \text{commute penultimate operand and re-associate}\\ ((P\lor\neg P)\land(\neg Q\lor\neg P)) \lor ((Q\lor R)\land(\neg R\lor R)) & \text{distribute}\\ (T\land(\neg Q\lor\neg P)) \lor ((Q\lor R)\land T) & \text{negation}\\ (\neg Q\lor\neg P) \lor (Q\lor R) & \text{identity}\\ \neg Q\lor Q\lor\neg P \lor R & \text{commutation}\\ T\lor\neg P \lor R & \text{negation}\\ T & \text{domination}\\ \end{array}

Answer 4

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.

So you start with the given antecedent as a premise:

$(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

Answer 5

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.

Full handwritten solution here.

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.

Answer 6

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)