Cdtjkyj

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?

Notice that

$ [(p land neg q) lor (qland neg r)] lor (neg plor r)$

is one big disjunction, so you can drop parentheses:

$ (p land neg q) lor (qland neg r) lor neg plor 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 (qland neg r) lor neg plor 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 (qland 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$

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

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

Yes.

$$begin{align}vdotsquad\iff&~big((p land lnot q) lor (qlandlnot r)big) lor (lnot plor r)
\[1ex]iff &~big(lnot plor (pland lnot q)big)lor big(rlor (lnot rland q)big)&quadtextsf{(Commutation and Association)}\vdotsquadend{align}$$

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 rland(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.