[1] : The Free On-line Dictionary of Computing (27 SEP 03)

natural deduction
     
        a set of rules expressing how valid proofs may be
        constructed in predicate logic.
     
        a horizontal line separates premises above from conclusions
        below.  vertical ellipsis dots stand for a series of
        applications of the rules.  "t" is the constant "true" and "f"
        is the constant "false" sometimes written with a latex
        \perp.
     
        "^" is the and conjunction operator, "v" is the inclusive or
        disjunction operator and "/" is not negation or
        complement, normally written with a latex \neg.
     
        p, q, p1, p2, etc. stand for propositions such as "socrates
        was a man".  px is a proposition possibly containing
        instances of the variable x, e.g. "x can fly".
     
        a proof a sequence of applications of the rules may be
        enclosed in a box.  a boxed proof produces conclusions that
        are only valid given the assumptions made inside the box,
        however, the proof demonstrates certain relationships which
        are valid outside the box.  for example, the box below
        labelled "implication introduction" starts by assuming p,
        which need not be a true propoistion so long as it can be
        used to derive q.
     
        truth introduction:
     
         -
         t
     
        truth is free.
     
        binary and introduction:
     
         -----------
         | .  | .  |
         | .  | .  |
         | q1 | q2 |
         -----------
           q1 ^ q2
     
        if we can derive both q1 and q2 then q1^q2 is true.
     
        n-ary and introduction:
     
         ----------------
         | .  | .. | .  |
         | .  | .. | .  |
         | q1 | .. | qn |
         ----------------
          q1^..^qi^..^qn
     
        other n-ary rules follow the binary versions similarly.
     
        quantified and introduction:
     
         ---------
         | x  .  |
         |    .  |
         |  qx |
         ---------
         for all x . qx
     
        if we can prove q for arbitrary x then q is true for all x.
     
        falsity elimination:
     
         f
         -
         q
     
        falsity opens the floodgates.
     
        or elimination:
     
           p1 v p2
         -----------
         | p1 | p2 |
         | .  | .  |
         | .  | .  |
         | q  | q  |
         -----------
              q
     
        given p1 v p2, if q follows from both then q is true.
     
        exists elimination:
     
         exists x . px
         -----------
         | x  px |
         |     .   |
         |     .   |
         |     q   |
         -----------
               q
     
        if q follows from px for arbitrary x and such an x exists
        then q is true.
     
        or introduction 1:
     
            p1
         -------
         p1 v p2
     
        if p1 is true then p1 or anything is true.
     
        or introduction 2:
     
            p2
         -------
         p1 v p2
     
        if p2 is true then anything or p2 is true.  similar
        symmetries apply to ^ rules.
     
        exists introduction:
     
             pa
         -------------
         exists x.px
     
        if p is true for "a" then it is true for all x.
     
        and elimination 1:
     
         p1 ^ p2
         -------
            p1
     
        if p1 and p2 are true then p1 is true.
     
        for all elimination:
     
         for all x . px
         ----------------
               pa
     
        if p is true for all x then it is true for "a".
     
        for all implication introduction:
     
         -----------
         | x  px |
         |     .   |
         |     .   |
         |    qx |
         -----------
         for all x . px -> qx
     
        if q follows from p for arbitrary x then q follows from p for
        all x.
     
        implication introduction:
     
         -----
         | p |
         | . |
         | . |
         | q |
         -----
         p -> q
     
        if q follows from p then p implies q.
     
        not introduction:
     
         -----
         | p |
         | . |
         | . |
         | f |
         -----
          / p
     
        if falsity follows from p then p is false.
     
        not-not:
     
         //p
         ---
          p
     
        if it is not the case that p is not true then p is true.
     
        for all implies exists:
     
         pa   for all x . px -> qx
         -------------------------------
        	      qa
     
        if p is true for given "a" and p implies q for all x then q
        is true for a.
     
        implication elimination, modus ponens:
     
         p   p -> q
         ----------
              q
     
        if p and p implies q then q.
     
        not elimination, contradiction:
     
         p   /p
         ------
           f
     
        if p is true and p is not true then false is true.
     
        1995-01-16
     
     
see also:
proof predicate logic latex \perp complement \neg 
proposition propoistion 

Deduction >> D Words
Deduction, definition of term: Deduction
deduction_pag1.html

Natural >> N Words
Natural, definition of term: Natural
natural_pag1.html

Natural Resourc >> N Words
Natural Resourc, definition of term: Natural Resourc
natural+resourc_pag1.html

Natural Religio >> N Words
Natural Religio, definition of term: Natural Religio
natural+religio_pag1.html

Natural Resourc >> N Words
Natural Resourc, definition of term: Natural Resourc
natural+resourc_pag1.html

Natural Science >> N Words
Natural Science, definition of term: Natural Science
natural+science_pag1.html

Natural Theolog >> N Words
Natural Theolog, definition of term: Natural Theolog
natural+theolog_pag1.html

Natural Selecti >> N Words
Natural Selecti, definition of term: Natural Selecti
natural+selecti_pag1.html

Natural Philoso >> N Words
Natural Philoso, definition of term: Natural Philoso
natural+philoso_pag1.html

Natural Logarit >> N Words
Natural Logarit, definition of term: Natural Logarit
natural+logarit_pag1.html

Page 1 2 Next