Monday, March 28, 2011

For My Lovely Logicians-In-Training

(So I don't have to re-make this every time I get a new student)

Notes on Propositional Calculus

Syntax: the study of the principles for constructing grammatical entities in a language or logic.
Semantics: the study of the meanings of the symbols in a language or logic.  

Syntax in PC refers to the formal structure of arguments and their component sentences, while semantics refers to the truths or falsehoods of the same.

  • is a semantic notion (it's about the *meanings* of the terms used in arguments).
  • is a combination of truth value assignments to the atomic propositions in a sentence or argument.
  • is a syntactic notion (it's about the *structure* of an infinite set of arguments)
  • does not depend on the actual truth values of the atomic sentences in the argument.
  • An argument is valid if and only if any valuation rendering the premises true also renders the conclusion true.
  • Operations in natural deduction (the proof system) depend on the presupposition that all the premises are simultaneously true.
Definition of propositional formula (plural formulae, pronounced form-you-lee)
  • p,q,r, ect. are formulae (specifically atomic formulae)
  • If X and Y are formulae,
  • X*Y, XvY, X-->Y, and ~X are also formulae.
Definition of operators (aka connectives):
  • *: T iff both conjuncts are T.
  • v: T iff at least one disjunct is T.
  • ~: T iff the negated formula is F.
  • -->: F iff the antecedent is T and the conclusion F.
Related terms:
  • Conjunct: a member of a conjunction
  • Disjunct: a member of a disjunction
  • Antecedent: the formula preceding the arrow in an implication
  • Consequent: the formula following the arrow in an implication
Notes on Predicate Logic
  • (∀x) applies to every element of the defined set (general)
  • (∃x) applies to at least one element of the defined set (particular)
When you hear... think...
  • "unless": if not
    • "Unless you like hate football you should watch the game," = "If not (hate football)--> (should watch the game)."
  • "only if" or "only": following goes to consequent
    • "Only cool people like jazz," = "(like jazz) --> (cool)"
    • "You're a good dancer only if you love music." = "(good dancer)-->(love music)"
  • if: following goes to antecedent
    • "If you're happy and you know it clap your hands," = "If (you're happy and you know it)-->(clap your hands)."
  • even if: (it or not it) then
    • "Even if you're bad at math you might love logic," = "(bad at math or not bad at math) then (might love logic)
  • not any: not some (negation of particular)
    • "There are not any more M&M's," = "not (there are some M&M's)."
  • no, no one, nothing: all not (general negative)
    • "Nothing can stop me now," = "(for all x) not(x can stop me now)"
    • "No snowman lives forever," = "(for all snowment) not (live forever)"
  • there is/there exists/some: particular
    • Some people like cake.
    • "There are three agencies of government when I get there that are gone..." (EPA?)
Questions to ask yourself when translating:
  • Is it an argument with premises or is it a single sentence?
  • What's the main connective?
  • What are the quantifiers?  To what parts of the sentence do they apply?
  • What do I immediately know from key words in the sentence (like unless, for all, etc.)?
  • When closing: again, to what parts of the sentence does the property apply?
Other notes: 
  • Conditional arguments are your friends.  If the conclusion is an implication, assume its antecedent and derive its consequent.
  • If the conclusion is a negation, assume the negated formula and derive an explicit contradiction.  Conclude the negation of your assumption.
  • If you're having trouble with your derivation, assume the negation of the conclusion and derive an explicit contradiction.  Conclude the negation of your assumption and apply double negation elimination.
  • If you're stuck on a particular derivation, stop thinking about it.  If possible, sleep before coming back to it.  Remember that there *is* an answer and it *will* come to you if you're patient.
  • If you're confused or uncertain about a translation, find a similar sentence whose translation appears in the back of the book and study it, then come back to your translation.
  • If you're feeling overwhelmed by the number of rules on your derivation cheat sheet, keep in mind that there are really only ten rules needed for any derivation in PC.  If needed, confine yourself to: assumption, conjunction introduction (conj), conjunction elimination (simplification), disjunction introduction (add), disjunction elimination (proof by cases), implication introduction (conditional proof), implication elimination (modus ponens), negation introduction (negation of assumption upon which a contradiction has been shown dependent), negation elimination (any formula, including the non-negated form of an assumed negation, can be concluded from an explicit contradiction), and double negation elimination.