Results 1 to 5 of 5

Math Help - sentential logic derivations?

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    1

    sentential logic derivations?

    how do i prove the following is a theorem in SD
    [(A -> B)->A]->A
    ... i started off by assuming [(A -> B)->A] then assume ~A to try to derive A in the end... but now i'm stuck

    and also:

    Suppose we dropped from SD the rule for vE, and adopted in its place the rule of Disjunctive Syllogism (DS), thus giving a modified system SD. Show that
    you can derive the SD rule for vE in SD.

    I have no idea how to even approach the second question.. any help would be greatly appreciated.. thanks!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    Hi

    Do you already have SD theorems?

    I didn't find an easy solution (but I'm not good at this), some way to do:

    ((A\rightarrow B)\rightarrow A)\vdash (\neg A\rightarrow \neg(A\rightarrow B)) .... (contraposition) and \neg A\vdash\neg A .... (axiom)

    \neg A, ((A\rightarrow B)\rightarrow A)\vdash \neg(A\rightarrow B) .... (with \rightarrow_e )

    \neg (A\rightarrow B)\vdash (A\wedge \neg B) .... ( (A\rightarrow B)\leftrightarrow (\neg A\vee B) and de Morgan's laws)

    \neg (A\rightarrow B)\vdash A\ .... (with \wedge_e )

    So we have \neg A, ((A\rightarrow B)\rightarrow A)\vdash A and \neg A\vdash\neg A

    Hence \neg A, ((A\rightarrow B)\rightarrow A)\vdash\bot .... (with contraction and \neg_e )

    And from there you can conclude. But if you cannot use de Morgan's laws, contraposition and some stuff, it will take some time.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,513
    Thanks
    769
    Hello,

    I'll look into this, but first I have a statement and a question.

    Statement: Unfortunately, in logic there are many different but equivalent ways to define many concepts. E.g., one can take \/, /\, -> and _|_ (falsehood) as primitive connectives, or take only -> and _|_ and consider the rest of the connectives as abbreviations. To make things worse, there are at least three general ways to define proofs: one (Hilbert's style) deals with formulas and has only inference rule but many axioms, the second (Natural Deduction) also deals with formulas but has many rules and no axioms, and the third (Sequent Calculus) deals with sets of formulas and also has many rules and no axioms. Therefore, if you look at ten different logic textbooks, you will probably find ten different notations, primitive connectives, inference rules, etc., though in the end they all give equivalent logics.

    Question: What are the inference rules that were given to you? Is it Natural Deduction (ND)? ND has introduction and elimination rules for each connective, and it has open and closed assumptions. You mentioned \/E (disjunction elimination rule); does it look like this?
    Code:
                 A     B
                   
    A \/ B       C     C
    ----------------------
              C
    The proof that you are looking for depends a lot on the definition of the proof, i.e., inference rules.

    Edit1: Also, what exactly is Disjunctive Syllogism?
    Edit2: Grammar.

    Evgeny
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,682
    Thanks
    614
    Hello, cosmopolitanx!

    I'm not familiar with the term "SD".
    I can solve it symbolically.

    We need some theorems for referencer:

    . . (P \to Q) \;=\; (\sim\!P \vee Q) . . . Alternate definition of Implication (ADI)

    . . [1]\;P\: \vee \sim\!P \;=\;t

    . . [2]\; P \wedge t \;=\;P

    . . [3]\;P \vee t \;=\;t



    Prove: . \bigg[(A \to  B) \to A\bigg] \to A

    . . \begin{array}{ccc}\bigg[(A \to B) \to A\bigg] \to A && \text{Given} \\ \\<br />
\bigg[(\sim\!A \vee B) \to A\bigg] \to A && \text{ADI} \\ \\<br /> <br />
\bigg[\sim(\sim\!A \vee B) \vee A\bigg] \to A && \text{ADI}\end{array}

    . . \begin{array}{cccc}<br /> <br />
\bigg[(A \:\wedge \sim\!B) \vee A\bigg] \to A && \text{DeMorgan} \\ \\<br /> <br />
\sim\bigg[(A \;\wedge \sim\!B) \vee A\bigg] \vee A && \text{ADI} \\ \\<br /> <br />
\bigg[\sim(A \:\wedge \sim\!B) \:\wedge \sim\!A\bigg] \vee A && \text{DeMorgan} \end{array}

    . . \begin{array}{ccccc}<br />
\bigg[(\sim\!A \vee B) \:\wedge \sim\!A\bigg] \vee A && \text{DeMorgan} \\ \\<br /> <br />
\bigg[(\sim\!A \vee B) \vee A\bigg] \wedge \bigg[\sim\!A \vee A\bigg] && \text{Distributive} \\ \\<br /> <br />
\bigg[(\sim\!A \vee B) \vee A\bigg] \wedge t && [1] \\ \\<br /> <br />
(\sim\!A \vee B) \vee A && [2] \end{array}

    . . . . . . . \begin{array}{cccccc}<br /> <br />
(\sim\!A \vee A) \vee B &&&&& \text{Comm/Assoc} \\ \\<br /> <br />
t \vee B &&&&& [1] \\ \\<br /> <br />
t &&&&& [3]<br />
\end{array}

    Follow Math Help Forum on Facebook and Google+

  5. #5
    Banned
    Joined
    Mar 2009
    Posts
    256
    Thanks
    1
    Quote Originally Posted by cosmopolitanx View Post
    how do i prove the following is a theorem in SD
    [(A -> B)->A]->A
    ... i started off by assuming [(A -> B)->A] then assume ~A to try to derive A in the end... but now i'm stuck

    and also:

    Suppose we dropped from SD the rule for vE, and adopted in its place the rule of Disjunctive Syllogism (DS), thus giving a modified system SD. Show that
    you can derive the SD rule for vE in SD.

    I have no idea how to even approach the second question.. any help would be greatly appreciated.. thanks!

    You started correctly by assuming [(A->B)->A] and then ~A.

    Now [(A ->B)->A] IS equivalent to :~A ->~(A ->B) ,by contrapositive law.
    From that formula and ~A ,by using M.Ponens you get :

    ~(A ->B) .

    From that formula by using De Morgan and the fact that (A ->B) IS equivalent to (~AvB) you have:

    A and ~B .

    From that formula and by using addition elimination you get:

    A

    Contradiction

    Hence A

    Hence by deduction theorem :

    [(A ->B) ->A] ->A
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Sentential Derivation (logic) help please
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: July 30th 2010, 08:16 PM
  2. Can someone check my logic (sentential logic)
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: July 13th 2010, 03:30 AM
  3. derivations.
    Posted in the Calculus Forum
    Replies: 3
    Last Post: December 8th 2009, 11:58 AM
  4. Sentential Logic Problem
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 7th 2009, 06:00 AM
  5. Replies: 1
    Last Post: October 6th 2009, 03:23 AM

Search Tags


/mathhelpforum @mathhelpforum