◀ ▲ ▶Branches / Logic / Proof

Proof

(related to Lemma: Hypothetical Syllogism)

We want to prove that the hypothetical syllogism is a valid logical argument. * The hypothetical syllogism can be formulated in propositional logic as $((p\Rightarrow q)\wedge (q\Rightarrow r))\Rightarrow (p\Rightarrow r).$ * Using the definition of implication "$\Rightarrow$", we can construct the following truth table:

$[[p]]_I$ |$[[q]]_I$|$[[r]]_I$|$[[p\Rightarrow q]]_I$|$[[q\Rightarrow r]]_I$|$[[p\Rightarrow r]]_I$:------------- |:------------- |:------------- |:------------- |:------------- |:-------------$0$|$0$|$0$|$1$|$1$|$1$$0$|$0$|$1$|$1$|$1$|$1$$0$|$1$|$0$|$1$|$0$|$1$$0$|$1$|$1$|$1$|$1$|$1$$1$|$0$|$0$|$0$|$1$|$0$$1$|$0$|$1$|$0$|$1$|$1$$1$|$1$|$0$|$1$|$0$|$0$$1$|$1$|$1$|$1$|$1$|$1$`

• We can see that $p\Rightarrow r$ is true (valued as $1$), whenever $p\Rightarrow q$ AND $q\Rightarrow r$ are both true.
• By definition of a valid logical argument, the hypothetical syllogism $((p\Rightarrow q)\wedge (q\Rightarrow r))\Rightarrow (p\Rightarrow r)$ is valid.

This result can also be achieved by calculating the truth table of the whole expression of the hypothetical syllogism, which confirmes that it is a tautology. Please click evaluate to verify this:

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Kane, Jonathan: "Writing Proofs in Analysis", Springer, 2016