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?
Best Answer
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$