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

• Mar 19th 2009, 02:21 PM
bmp05
How can I prove that this propositional logic statement a tautology is?
Hypothetical syllogism:

$
((A \Rightarrow B) \wedge (B \Rightarrow C)) \Rightarrow (A \Rightarrow C)
$

Hi everyone,
I want to prove that the above statement is a tautology, but I don't want to use logic tables for A, B and C. I have tried using the rules of replacement, but I can't make it work. The proposition is called the "Hypothetical Syllogism." Which you can 'read' from the statement pretty easily, ie. if (a implies b) and (b implies c) then this implies (a implies c). You might know it from essay writing? Anyway, doesn't this mean the proof should give the following?

$
... \Leftrightarrow A \Rightarrow C
$

If I do use a truth table, I get 'true' for every value of A, B or C, which means that the statement is a tautology, but this has nothing to do with my idea for the proof. Can there be an equivalent proposition that only gives true? Is there a way of simplifying the proposition or do you have to use a table in this case?

Sorry, everyone, this was my mistake, I was trying to create a simple equivalent proposition, when I only had to show that the proposition was a tautology. My apologies.
• Mar 27th 2009, 07:43 AM
bmp05
Here is an example I found on the web
Disjunctive Syllogism
$
(A \vee B) \wedge \neg A \Rightarrow B
$

$
\equiv \neg A \wedge (A \vee B) \Rightarrow B \\
$

(commutativity)

$
\equiv (\neg A \wedge B) \vee (\neg A \wedge B) \Rightarrow B
$

(distribution)

$
\equiv \emph{F} \vee (\neg A \wedge B) \Rightarrow B
$

$
\equiv \neg A \wedge B \Rightarrow B
$

(or-simplification)

$
\equiv \neg (\neg A \wedge B) \vee B
$

(implication)

$
\equiv (A \vee \neg B) \vee B
$

(De Morgan)

$
\equiv A \vee (\neg B \vee B)
$

(associativity)

$
\equiv A \vee T
$

(excluded middle)

$
\equiv T
$

(or simplification)

Maybe it is possible to simplify hypothetical syllogism using this type of algebra?
It is easy to replace the original implications eg.

$
\equiv ((B \vee \neg A) \wedge (C \vee \neg B)) \Rightarrow (A \Rightarrow C)
$

but then I am stuck with a strange looking equation?

$
\equiv ((\neg A \vee B) \wedge \neg B) \vee ((\neg A \vee B) \wedge C) ...
$

(distributive law)

$
\equiv (\neg A \wedge \neg B) \vee (B \wedge \neg B) \vee ...
$

(distributiv law)
Which allows you to simplify a bit, but it's still a very big mess... Is there a simpler way? Or should I just continue on expanding using distribution?