Are there any errors in my proof for "prove [(p→q)∧(q→r)]→(p→r) is a tautology"?

241 Views Asked by At

Please help me be 100% sure that there are no errors in this proof. I am especially worried that I applied a rule incorrectly or dropped parenthesis when it was inappropriate. This proof thing is very new to me. Thanks a lot! $$[(p\implies q)\land(q\implies r)]\implies(p\implies r)$$ $$\equiv\neg[(\neg p\lor q)\land(\neg q\lor r)]\lor(\neg p\lor r)$$ because $$p\implies q\equiv\neg p\lor q$$ $\neg(\neg p\lor q)\lor\neg(\neg q\lor r)\lor(\neg p\lor r)$ by DeMorgan's law.

$p\land \neg q\lor q\land \neg r\lor(\neg p\lor r)$ by De Morgan's law

$p\land \neg q\lor q\land\neg r\lor(r\lor \neg p)$by Commutative law

$p\land\neg q\lor q\land(\neg r\lor r)\lor\neg p$ by Associative law

$p\land T\land T\lor\neg p$ by Negation law

$p\lor\neg p \equiv 1$ by Identity law

T by Negation law

$$Q.E.D$$

2

There are 2 best solutions below

10
On BEST ANSWER

$\begin{array}{l} ((P\implies Q)\land(Q\implies R))\implies(P\implies R)\\\\ \bigg((P'+Q)\times(Q'+R)\bigg)\implies(P'+R) & \text{translate implications}\\\\ \bigg((P'+Q)\times(Q'+R)\bigg)'+(P'+R) & \text{translate overall implication}\\\\ (P'+Q)'+(Q'+R)'+(P'+R) & \text{negation of big parenthesis}\\\\ PQ'+QR'+P'+R & \text{negation of small parenthesis}\\\\ PQ'+QR'+1P'+ 1R & \text{introduce multiplication by 1}\\\\ PQ'+QR'+(Q+Q')P'+ (Q+Q')R & \text{replace 1 by tautology}\\\\ \color{red}{PQ'}+\color{green}{QR'}+ P'Q+ \color{red}{P'Q'} +\color{green}{QR}+ Q'R & \text{develop}\\\\ \color{red}{(P+P')Q'}+\color{green}{Q(R+R')}+ P'Q + Q'R & \text{factorize}\\\\ 1Q'+1Q+ P'Q + Q'R & \text{replace tautology by 1}\\\\ Q'+Q+ P'Q + Q'R & \text{remove multiplication by 1}\\\\ (Q+ Q') + P'Q+Q'R & \text{associativity}\\\\ 1 + P'Q+Q'R & \text{replace tautology by 1}\\\\ 1 & \text{ replace 1+X by 1} \end{array}$


The same written in logic formalism:

$\begin{array}{l} ((p\implies q)\land (q\implies r))\implies(p\implies r)\\ ((\lnot p\lor q)\land (\lnot q\lor r))\implies(\lnot p\lor r)\\ \lnot ((\lnot p\lor q)\land (\lnot q\lor r)) \lor (\lnot p\lor r)\\ \lnot (\lnot p\lor q) \lor \lnot (\lnot q\lor r) \lor (\lnot p\lor r)\\ (p\land \lnot q) \lor (q\land \lnot r) \lor \lnot p \lor r\\ (p\land \lnot q) \lor (q\land \lnot r) \lor (\tau\land \lnot p) \lor (\tau\land r)\\ (p\land \lnot q) \lor (q\land \lnot r) \lor ((q\lor \lnot q)\land \lnot p) \lor ((q\lor \lnot q)\land r)\\ \color{red}{(p\land \lnot q)} \lor \color{green}{(q\land \lnot r)} \lor (\lnot p\land q) \lor \color{red}{(\lnot p\land \lnot q)} \lor \color{green}{(q\land r)}\lor (\lnot q\land r)\\ \color{red}{((p\lor \lnot p)\land \lnot q)} \lor \color{green}{(q\land (r\lor \lnot r))} \lor (\lnot p\land q) \lor (\lnot q\land r)\\ (\tau\land \lnot q) \lor (\tau\land q) \lor (\lnot p\land q) \lor (\lnot q\land r)\\ \lnot q \lor q \lor (\lnot p\land q) \lor (\lnot q\land r)\\ (q\lor \lnot q) \lor (\lnot p\land q) \lor (\lnot q\land r)\\ \tau \lor (\lnot p\land q) \lor (\lnot q\land r)\\ \tau\end{array}$

1
On

Your use of delimiters seems a bit janky to me. See if you can follow this line of reasoning:

\begin{align} \Omega &\equiv [(p\to q)\land(q\to r)]\to(p\to r) & (\text{for brevity})\\[0.5em] &\equiv \neg(\neg p\lor q)\lor\neg(\neg q\lor r)\lor(\neg p\lor r)\\[0.5em] &\equiv (p\land\neg q)\lor(q\land\neg r)\lor(\neg p\lor r)\\[0.5em] &\equiv \bigl\{[(p\land\neg q)\lor q]\land[(p\land\neg q)\lor\neg r]\bigr\}\lor(\neg p\lor r)\\[0.5em] &\equiv [(p\lor q)\land(p\lor\neg r)\land(\neg q\lor\neg r)]\lor(\neg p\lor r)\\[0.5em] &\equiv (p\lor q\lor\neg p\lor r)\land(p\lor\neg r\lor\neg p\lor r)\land(\neg q\lor\neg r\lor\neg p\lor r)\\[0.5em] &\equiv \mathbf{T}\land\mathbf{T}\land\mathbf{T}\\[0.5em] &\equiv \mathbf{T}. \end{align}