3
$\begingroup$

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 ?

$\endgroup$
1
  • $\begingroup$ Last line does not make sense $\endgroup$ Aug 1 '16 at 18:11
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.