Results 1 to 2 of 2

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

  1. #1
    Member
    Joined
    Mar 2009
    Posts
    90

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

    Hypothetical syllogism:

    <br />
((A \Rightarrow B) \wedge (B \Rightarrow C)) \Rightarrow (A \Rightarrow C)<br />

    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?

    <br />
... \Leftrightarrow A \Rightarrow C<br />

    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.
    Last edited by bmp05; March 19th 2009 at 03:04 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member
    Joined
    Mar 2009
    Posts
    90
    Here is an example I found on the web
    Disjunctive Syllogism
    <br />
(A \vee B) \wedge \neg A \Rightarrow B<br />


    <br />
\equiv \neg A \wedge (A \vee B) \Rightarrow B \\<br />
    (commutativity)

    <br />
\equiv (\neg A \wedge B) \vee (\neg A \wedge B) \Rightarrow B<br />
    (distribution)

    <br />
\equiv \emph{F} \vee (\neg A \wedge B) \Rightarrow B<br />
    (contradiction)

    <br />
\equiv \neg A \wedge B \Rightarrow B<br />
    (or-simplification)

    <br />
\equiv \neg (\neg A \wedge B) \vee B<br />
    (implication)

    <br />
\equiv (A \vee \neg B) \vee B<br />
    (De Morgan)

    <br />
\equiv A \vee (\neg B \vee B)<br />
    (associativity)

    <br />
\equiv A \vee T<br />
    (excluded middle)

    <br />
\equiv T<br />
    (or simplification)

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

    <br />
\equiv ((B \vee \neg A) \wedge (C \vee \neg B)) \Rightarrow (A \Rightarrow C)<br />
    but then I am stuck with a strange looking equation?

    <br />
\equiv ((\neg A \vee B) \wedge \neg B) \vee ((\neg A \vee B) \wedge C) ...<br />
    (distributive law)

    <br />
\equiv (\neg A \wedge \neg B) \vee (B \wedge \neg B) \vee ...<br />
    (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?
    Last edited by bmp05; March 27th 2009 at 08:19 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. tautology/logic help
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: September 12th 2010, 03:24 PM
  2. Replies: 2
    Last Post: February 24th 2010, 02:34 PM
  3. Predicate logic - Tautology?
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: March 11th 2009, 07:36 AM
  4. Formal Propositional Logic Statement
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 4th 2009, 08:35 AM
  5. Replies: 3
    Last Post: October 17th 2007, 11:41 PM

Search Tags


/mathhelpforum @mathhelpforum