20130109
Syllogistic logic was effectively the only logic system in use until Gottlob Frege (1848 - 1925) laid the foundations for modern logic.  In this course we will study a logical proof system called
Natural Deduction", first developed by Gentzen in 1934 as a direct extension of Frege's work.  The form of Natural Deduction we will use is the creation of Gentzen and Prawitz.

Natural Deduction deals with sequents.   A sequent is a statement which looks like this:

            PHI-1, PHI-2, PHI-3, .... PHI-n |-  PSI

in which PHI-1 ... PHI-n are called premises and PSI is called the conclusion

The meaning of the sequent statement is "if PHI-1 ... PHI-n are all true statements, then we can apply the rules of Natural Deduction to prove that PSI is also a true statement".  If this is true, we call this a
valid sequent.

Note that a sequent with just two premises would look very much like a syllogism.  However we will have to go quite a long way before we can successfully prove even the simplest
syllogism  using Natural Deduction.

Propositional Logic

Syllogisms deal with relationships between sets ("All dogs are animals").  In propositional logic we deal with assertive statements and relationships between them.  For historical reasons we call
our statements propositions.  In practice the premises and conclusions of our sequents are always propositions.

Atomic Propositions - non-divisible assertions to which we can apply the values TRUE and FALSE

Examples:
       1+1 = 2
       2*2 = 5
       All hobbits have hairy feet
       The time is exactly 11:23
       x = 86

but not
       Please open the door.   (not an assertion)
       Does 1+1=2 ?   (not an assertion)
       Her eyes are brown and her hair is black.   (not non-divisible)

Propositions are usually represented by letters such as p, q, r, etc - sometimes with subscripts.

Propositional logic is only concerned with the truth value of propositions, not their content or meaning, or our shared ground-knowledge.  This can make it very
difficult to express very simple "real world" arguments as sequents.  For example, anyone familiar with fundamental arithmetic would probably accept the argument

        1 < 2
        2 < 3
Therefore 1 < 3

But in propositional logic we would give the statements names
        p : 1 < 2
        q :  2 < 3
        r:   1 < 3

and the sequent  
        p, q |- r

has no proof since it is easy to come up with propositions p, q and r where p and q are both true but r is false.   Thus
        p, q |- r
is an invalid sequent.

Complex (or Compound) Propositions - combinations of one or more atomic propositions, with Logical Connectives - "NOT", "AND", "OR", and "->"

NOT - "not p" is TRUE if and only if p is FALSE, and vice versa

AND - "p and q" is TRUE if and only if p is TRUE and q is TRUE

OR - "p or q" is TRUE if and only if at least one of p and q is TRUE

In natural language, we often use "or" to describe mutually exclusive alternatives, as in "We will go to the zoo on Saturday or Sunday", or "Would you like tea or coffee?"  There is an implicit "but not both".  The logical "OR" does not carry this meaning.  A proposition such as "x=3 or y=4" admits the possibility that both sub-propositions might be true.   To state that exactly one of p and q is true, we can write "(p or q) and not (p and q)" - there are many other ways to write this - as an exercise, try to come up with a couple.
->  - "p -> q" (we read it as "p implies q") is TRUE if it is not the case that p is TRUE and q is FALSE - all other combinations of p and q being TRUE and FALSE make the implication true.

In natural language, the word "implies" often carries a suggestion of causality, as in "I watered the lawn, which implies it will need cutting soon."  The logical "implies" does not carry this meaning.  The propositions p and q in "p -> q" can be completely unrelated.

Examples:
       "2+2 = 4 -> 3*3 = 8"   This is FALSE because the left side is true and the right side is false
       "2+2 = 4 -> 3*3 = 9"   This is TRUE because both sides are true - note that there is no suggestion that the truth of the left side causes the truth of the right side
       "2+2 = 4 -> water molecules contain 3 atoms"   This is TRUE for the same reason as the last one
       "water molecules contain 3 atoms" -> "2+2 = 4"   This is TRUE - starting to belabour the point a bit now
       "2+2 = 3" -> "the moon is made of cheese"          This is TRUE - when the left side is false, the implication is true regardless of the right side's truth
       "2+2 = 3" -> "2+2 = 4"                                       This is TRUE - if we fall into the trap of thinking that there is some relationship between the two sides, this                                                                                             makes no sense at all, but if we understand that the implication is no more than a statement about a
                                                                                        particular combination of true and false for the two sides, we are ok

Ambiguity

A proposition such as "p and q or r" is ambiguous.  It could be interpreted as "(p and q) or r" or as "p and (q or r)".  To see that this is important, think about what happens if p is FALSE and r is TRUE (it doesn't matter what q is).  We will follow the convention of the text and always adopt the second interpretation.  This is called "right associativity".   It is worth mentioning that Java uses the first interpretation.  Best advice: always use parentheses to disambiguate.

The same thing applies to chained implications.  "p -> q -> r" is interpreted to mean "p -> (q -> r)"

Binding Order - to reduce the need for parentheses, we adopt the following precedence rule for logical operators:
    NOT binds first
    AND and OR bind next
    -> binds last

Thus the proposition  "not p or q -> a -> b and c or d -> not e" is interpreted as if it were "((not p) or q) -> (a -> ((b and (c or d)) -> (not e)))"