Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

• Last time:
• Models vs theories. Axioms and proofs.
• Propositions.
• Logical connectives: ¬, ∧, ∨, ⇒, ⇔.
• Modus ponens: P, P ⇒ Q ⊢ Q.
• This time:
• Tautologies.
• Proving tautologies using truth tables.
• More on entailment (⊢)
• If P ⇒ Q is a tautology, then P ⊢ Q
• Proof: We can always add tautologies to our list of axioms, then P, P ⇒ Q ⊢ Q by modus ponens.
• We can get new inference rules by proving tautologies of the form P ⇒ Q.
• Example: P ⊢ P ∨ Q (addition rule) follows from P ⇒ (P ∨ Q).
• Example: P ∧ Q ⊢ P (simplification rule) follows from P ∧ Q ⇒ P.
• Converse: If P, R ⊢ Q, then R ⊢ P ⇒ Q. (Deduction Theorem)
• We can prove P ⇒ Q by assuming P and proving Q.
• Note distinction between implication (⇒) and entailment (⊢)
• Implication is inside the theory: P ⇒ Q might be true, might be false.
• Entailment is outside: P ⊢ Q depends only on structure of P and Q.
• More on logical equivalence (≡)
• P ≡ Q if P and Q are true under exactly the same conditions.
• To prove P ≡ Q:
1. Use truth tables.
2. Prove P ⇔ Q is a tautology.
• Payoff: if P ≡ Q, then we can substitute either for the other inside compound propositions.
• Example: ¬¬P ≡ P. (Double-negation elimination: prove using truth table.)
• Example: ¬(P∨Q) ≡ ¬P ∧ ¬Q. (De Morgan's Law: prove using truth table.)
• Example: ¬(P∧Q) ≡ ¬P ∨ ¬Q. Proof: ¬(P∧Q) ≡ ¬(¬¬P ∧ ¬¬Q) [double-negation] ≡ ¬¬(¬P ∨ ¬Q) [De Morgan] ≡ ¬P ∨ ¬Q [double-negation]
• Example: P ⇒ Q ≡ ¬Q ⇒ ¬P (contraposition). Proof: P ⇒ Q ≡ ¬P ∨ Q ≡ Q ∨ ¬P ≡ ¬¬Q ∨ ¬P ≡ ¬Q ⇒ ¬P.
• Predicate logic [if we get to it]
• Add constants: Socrates, 12/37, the 1962 Red Sox.
• Add predicates: e.g. P(x) for "x is mortal"
• Add quantifiers
• Universal quantifier ∀x P(x) ("for all x, P(x)") means P(x) is true for any x in the universe: essentially a very big AND.
• Existential quantifier: ∃x P(x) ("there exists x such that P(x)") means P(x) is true for at least one x in the universe: essentially a very big OR.
• How to interpret nested quantifiers, e.g. ∀x∃y y > x.

• Add inference rules
• Universal/existential specialization/generalization
• Optional: add function names and equality

2014-06-17 11:57