Show that this statement is tautology without using truth table.

**Ammar** · March 16th 2013, 03:44 AM

Hi,

[(p -> q) ^ (q->r)] -> (p -> r)

??

**emakarov** · March 16th 2013, 09:04 AM

What other methods besides truth tables have your course used to show that a given statement is a tautology?

**HallsofIvy** · March 16th 2013, 09:16 AM

You can just think about what the symbols mean: If the hypothesis is true then we have both p->q and q->r true. If p is true then, from p->q, what can you say about q? And what does that tell you about r?

**Soroban** · March 16th 2013, 03:27 PM

Hello, Ammar!

I assume we want a two-column proof.

We have this identity: . $(p\to q)\:\longleftrightarrow\:(\sim p \vee q)$

I call it Alternate Definition of Implication (ADI).

$\text{Prove: }\:\big[(p\to q) \wedge (q\to r)\big]\:\to\:(p\to r)$

$\begin{array}{cccccc} 1.& \big[(p\to q)\wedge(q\to r)\big]\:\to\:(p\to r) && 1. & \text{Given} \\ 2. &\big[(\sim\!p\vee q) \wedge(\sim\!q\vee r)\big] \:\to\:(\sim\!p \vee r) && 2. & \text{ADI} \\ 3. & \sim\big[(\sim\!p \vee q) \wedge (\sim\!q\vee r)\big]\:\vee\:(\sim\!p\vee r) && 3. & \text{ADI} \\ 4. & \sim(\sim\!p\vee q) \vee \sim(\sim\!q\vee r) \vee (\sim\!p\vee r) && 4. & \text{DeMorgan} \\ 5. & (p\:\wedge \sim\!q) \vee(q\:\wedge\sim\!r) \vee\sim\!p \vee r && 5. & \text{DeMorgan} \\ 6. & \big[\sim\!p\vee(p\:\wedge\sim\!q)\big] \vee \big[r\vee(q\:\wedge\sim\!r)\big] && 6. & \text{Comm.Assoc.} \\ 7. & \big[(\sim\!p \vee p) \wedge(\sim\!p\:\vee\sim\!q) \vee \big[(r\vee q)\wedge(r\vee\sim\!r)\big] && 7. &\text{Distr.} \\ 8. & \big[t \wedge(\sim\!p\vee\sim\!q)\big] \vee \big[(r\vee q)\wedge t\big] && 8. & a\:\vee\sim\!a \,=\,t \\ 9. & (\sim\!p\:\vee \sim\!q) \vee (r\vee q) && 9. & a\wedge t \,=\,a \end{array}$
$\begin{array}{cccccc}10. & \qquad\qquad\quad \sim\!p \vee (\sim\!q \vee q) \vee r & \qquad\qquad\qquad & 10.& \text{Comm.Assoc.} \\ 11. & \qquad\qquad\sim\!p \vee t \vee r && 11. & a\:\vee \sim\!a \,=\,t \\ 12. & \qquad\qquad t && 12. & a\vee t \,=\,t \end{array}$

Thread: Show that this statement is tautology without using truth table.

LinkBack

Thread Tools

Display

Show that this statement is tautology without using truth table.

Re: Show that this statement is tautology without using truth table.

Re: Show that this statement is tautology without using truth table.

Re: Show that this statement is tautology without using truth table.

Similar Math Help Forum Discussions

Prove a tautology without truth tables.

Constructing a truth table from a giving statement

How can I prove that this propositional logic statement a tautology is?

Tautology, truth table

if then statement. truth table.

Search Tags