Showing a conditional statement is a tautology without using a truth table.

Question

I wanted to show that [(p→q)∧(q→r)]→(p→r) is a tautology without using a truth table. This is what I got so far:

[(p→q)∧(q→r)] → (p→r)

=> ¬[(¬p v q) ∧ (¬q v r)] v (¬pvr) (logical equivalence)

=> [¬(¬p v q) v ¬(¬qvr)] v (¬pvr) (demorgan's law)

=> [(p ∧ ¬q) v (q∧¬r)] v (¬pvr) (demogran's law)

I can't seem to figure out what comes after this step. Can someone help me?

Answer 1

Notice that

$ [(p \land \neg q) \lor (q\land \neg r)] \lor (\neg p\lor r)$

is one big disjunction, so you can drop parentheses:

$ (p \land \neg q) \lor (q\land \neg r) \lor \neg p\lor r$

Now, if you have:

Reduction

$p \lor (\neg p \land q) \equiv p \lor q$

then you can apply that:

$ (p \land \neg q) \lor (q\land \neg r) \lor \neg p\lor r \equiv$

$\neg q \lor q \lor \neg p \lor r \equiv$

$\top \lor \neg p \lor r \equiv$

$\top$

But if you don't have Reduction:

$ (p \land \neg q) \lor (q\land \neg r) \lor \neg p \lor r \equiv$

$((p \lor \neg p) \land (\neg q \lor \neg p)) \lor ((q \lor r) \land (\neg r \lor r)) \equiv$

$(\top \land (\neg q \lor \neg p)) \lor ((q \lor r) \land \top) \equiv$

$\neg q \lor \neg p \lor q \lor r$

$\top \lor \neg p \lor r \equiv$

$\top$

Answer 2

Expand the expression $(p \wedge \neg q) \vee (q \wedge \neg r)$ by distributing the $\vee$ over the $\wedge$: \begin{align*} &(p \wedge \neg q) \vee (q \wedge \neg r)\\ &[(p \wedge \neg q) \vee q] \wedge [(p \wedge \neg q) \vee \neg r]\\ &[(p \vee q ) \wedge (\neg q \vee q)] \wedge [(p \vee \neg r ) \wedge (\neg q \vee \neg r)]\\ &[(p \vee q) \wedge \top ] \wedge[(p \vee \neg r) \wedge (\neg q \vee \neg r)]\\ &(p \vee q) \wedge [(p \vee \neg r) \wedge (\neg q \vee \neg r)]. \end{align*} Now overall we have $\{(p \vee q) \wedge [(p \vee \neg r) \wedge (\neg q \vee \neg r)]\}\vee (\neg p \vee r)$. If we distribute the $\vee$ over the $\wedge$, we get $[(p \vee q) \vee ( \neg p \vee r)]\wedge\{[(p \vee \neg r) \wedge (\neg q \vee \neg r)]\vee(\neg p \vee r)\}$. Focusing on the first half, you can manipulate $(p \vee q) \vee ( \neg p \vee r)$ to get $\top$ by shuffling parentheses around to get $(p \vee \neg p) \vee (q \vee r)$ (I'll leave that to you).

So we are left with $[(p \vee \neg r) \wedge (\neg q \vee \neg r)] \vee (\neg p \vee r)$. Again let's distribute the $\vee$ over the $\wedge$: \begin{align*} &[(p \vee \neg r) \vee (\neg p \vee r)] \wedge [(\neg q \vee \neg r) \vee (\neg p \vee r)]. \end{align*} Again both halves of this can be manipulated to get $\top$.

Answer 3

I can't seem to figure out what comes after this step. Can someone help me?

Yes.

$$\begin{align}\vdots\quad\\\iff&~\big((p \land \lnot q) \lor (q\land\lnot r)\big) \lor (\lnot p\lor r) \\[1ex]\iff &~\big(\lnot p\lor (p\land \lnot q)\big)\lor \big(r\lor (\lnot r\land q)\big)&\quad\textsf{(Commutation and Association)}\\\vdots\quad\end{align}$$

Answer 4

You can use Double Distribution to get $$[(p \lor q)\land(q \lor \lnot q)\land(\lnot q \lor \lnot r)\land(p \lor \lnot r)]\lor (\lnot p \lor r)$$ $q \lor \lnot q$ is a Tautology so this becomes $$[(p \lor q)\land(\lnot q \lor \lnot r)\land(p \lor \lnot r)]\lor (\lnot p \lor r)$$ which by distribution is $$[(p \lor q)\land[\lnot r\land(p \lor \lnot q)]]\lor (\lnot p \lor r)$$ Association gives $$[\lnot r \land [(p \lor q)\land(p \lor \lnot q)]]\lor (\lnot p \lor r)$$ Distribution again gives $$[\lnot r \land [p \lor(q \land \lnot q)]]\lor (\lnot p \lor r)$$ $q \land \lnot q$ is a contradiction so this becomes $$(\lnot r \land p)\lor (\lnot p \lor r)$$ Which by DeMorgan's Law is $$(\lnot r \land p)\lor \lnot(\lnot r \land p)$$ Which is a tautology.