# Mathematical logic proof that true

I have a small exercice in mathematical logic, i must proof that :

 (( p ⇒ q ) ∧ ( q ⇒ r )) ⇒ ( p ⇒ r)


is true.

I know i can replace :

A ⇒ B by ∼A ∨ B
A ⇔ B by (A ∧ B) ∨ (∼A ∧ ∼B)


so my first thing is to develop :

( ~p ∨ q ∧ ~q ∨ r) ⇒ ~p ∨ r
( ~p ∨ 0 ∨ r)  ⇒ ~p ∨ r
( ~p ∨ r)  ⇒ ~p ∨ r


Can i stop my develop and conclude tha true, because ~p ∨ r consequence ~p ∨ r ?

• Last line does not make sense Aug 1 '16 at 18:11

$\wedge$ and $\vee$ are not associative one with respect to another.

Specifically, I'd say your development $$(\neg p\vee q)\wedge (\neg q\vee r)\equiv \neg p\vee (\neg q\wedge q)\vee r$$ is a mistake of algebra.

It should have been, due to distributivity,

$$(\neg p\vee q)\wedge (\neg q\vee r)\equiv (\neg p\wedge \neg q)\vee (\neg p\wedge r)\vee (q\wedge \neg q)\vee (q\wedge r)\equiv\\\equiv(\neg p\wedge \neg q)\vee (\neg p\wedge r)\vee (q\wedge r)\stackrel{\text{def.}}\equiv T$$

Hence, $T\rightarrow (\neg p\vee r)$ becomes $$((p\vee q)\wedge (p\vee \neg r)\wedge (\neg q\vee \neg r))\vee (\neg p\vee r)\equiv \\\equiv (\color{blue}p\vee q\vee \color{blue}{\neg p}\vee r)\wedge (\color{red}p\vee \neg r\vee \color{red}{\neg p}\vee \neg r)\wedge(\neg q\vee \color{orange}r\vee\neg p\vee \color{orange}{\neg r})\equiv \\\equiv 1\wedge 1\wedge 1\equiv 1$$

This is a tautology. So for any p, q and r it will be true.

One common way to prove is by contradiction. So assume there exits p, q and r which makes $p \rightarrow r$ false but $(p \rightarrow q) \land (q \rightarrow r)$ true. This should lead to a contradiction.

So if p, q and r makes $p \rightarrow r$ false, we get $\lnot (p \rightarrow r) \equiv \lnot (\lnot p \lor r) \equiv p \land \lnot r$, so p must be true and r must be false.

Now we have assumed p, r and q are such that $(p \rightarrow q) \land (q \rightarrow r)\equiv (\lnot p \lor q) \land (\lnot q \lor r)$ is true. But because p must be true and r must be false we get $(\lnot p \lor q) \land (\lnot q \lor r) \equiv q \land \lnot q$, which is false by definition, so $(p \rightarrow q) \land (q \rightarrow r)$ must be false, which is a contradiction to the premises.

So there is no p, q and r which makes $p \rightarrow r$ false AND $(p \rightarrow q) \land (q \rightarrow r)$ true.

Another way would be to establish a truth table

Tip: Don't drop the brackets until you can drop the brackets (via associativity).

$\vee$ and $\wedge$ do not associate, so your second line was erroneous.   Instead by keeping the parenthesis in place you should continue using another implication equivalence, then deMorgan's negations , until you have a DNF statement and some brackets can be removed via association.   The result can then be simplified using ...

$$\begin{array}{c:l}((p\to q)\wedge (q\to r)) \to (p\to r) & \textsf{given} \\ ((\neg p\vee q)\wedge (\neg q\vee r))\to(\neg p\vee r) & \textsf{implication equivalence} \\ \neg((\neg p\vee q)\wedge (\neg q\vee r))\vee(\neg p\vee r) & \textsf{implication equivalence}\\ \color{silver}((p\wedge\neg q)\vee (q\wedge\neg r)\color{silver})\vee \color{silver}(\neg p\vee r\color{silver}) & \textsf{deMorgan's}\\ \color{silver}((p\wedge\neg q)\vee \neg p\color{silver})~\vee~\color{silver}( (q\wedge\neg r)\vee r\color{silver}) & \textsf{association and commutivity}\\ \neg q\vee \neg p~\vee~ q\vee r & \textsf{complement absorbtion}\\ \color{silver}(\neg q\vee q\color{silver})~\vee~ \neg p\vee r &\textsf{commutivity} \\ \top\vee\color{silver}(\neg p\vee r\color{silver})& \textsf{complementation}\\\top & \text{anhillation}\end{array}$$

You can then write \begin{align} &( \neg p ∨ r) ⇒ \neg p ∨ r \\& \neg (\neg p ∨ r) ∨( \neg p ∨ r) \\& 1 \end{align} since $\neg a ∨ a=1.$