Math Help - Explain this tautology solution

1. Explain this tautology solution

Hello. I am showing that the conditional statement, [(p → q) ∧ (q → r)] → (p → r) is a tautology without truth tables. Below is the solution. How is step 2 achieved? I've tried using distributive law inside the brackets but it isn't producing what is show below.

1. [(p → q) ∧ (q → r)] ↔ (¬p ∨ q) ∧ (¬q ∨ r)
2. ↔ [(¬p ∨ q) ∧ ¬q] ∨ [(¬p ∨ q) ∧ r]
3. ↔ (¬p ∧ ¬q) ∨ [(¬p ∨ q) ∧ r]
4. ↔ [(¬p ∧ ¬q) ∨ (¬p ∨ q)] ∧ [(¬p ∧ ¬q) ∨ r]
5. ↔ [(¬p ∧ ¬q) ∨ (¬p ∨ q)] ∧ (¬p ∨ r) ∧ (¬q ∨ r)
6. → (¬p ∨ r)
7. ↔ (p → r)

2. Re: Explain this tautology solution

Originally Posted by lamentofking
Hello. I am showing that the conditional statement, [(p → q) ∧ (q → r)] → (p → r) is a tautology without truth tables. Below is the solution. How is step 2 achieved? I've tried using distributive law inside the brackets but it isn't producing what is show below.

1. [(p → q) ∧ (q → r)] ↔ (¬p ∨ q) ∧ (¬q ∨ r)
2. ↔ [(¬p ∨ q) ∧ ¬q] ∨ [(¬p ∨ q) ∧ r]
I assume that you understand step 1.

Note that $(a \vee b) \wedge (c \vee d) \leftrightarrow \left[ {(a \vee b) \wedge c} \right] \vee \left[ {(a \vee b) \wedge d} \right]$.

3. Re: Explain this tautology solution

Hello, lamentofking!

$\text{Prove: }\:\big[(p \to q) \wedge (q\to r)\big] \:\to\:(p\to r)\,\text{ without truth tables.}$

I would do it like this . . .

$\begin{array}{c}\sim \big[(\sim\!p \wedge q) \:\wedge (\sim\!q \vee r)\big] \,\vee\,(\sim\!p \vee r) \\ \\ \sim\!(\sim\!p \vee q)\: \vee \sim(\sim\!q \vee r) \,\vee\,(\sim\!p \vee r) \\ \\ (p\: \wedge \sim\!q) \vee (q \:\wedge \sim\!r)\: \vee \sim\!p \vee r \\ \\ \big[\sim\!p \vee (p\:\wedge \sim\!q)\big] \vee \big[r \vee (q\: \wedge \sim\!r)\big] \\ \\ \big[(\sim\!p \vee p) \wedge (\sim\!p\:\vee \sim\!q)\big] \vee \big[(r\vee q) \wedge (r \:\vee \sim\!r)\big] \\ \\ \big[T \wedge (\sim\!p \:\vee \sim\!q)\big] \vee \big[(r\vee q) \wedge T\big] \\ \\ (\sim\!p\:\vee \sim\!q) \vee (r \vee q) \\ \\ \sim\!p \vee (\sim\!q \vee q) \vee r \\ \\ \sim\!p \vee T \vee r \\ \\ T \end{array}$