[FrontPage] [TitleIndex] [WordIndex

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.

More logic: PredicateLogic, InferenceRules and ProofTechniques. Readings: Sections 1.4-1.6, 3.6.

1. Proving things in propositional logic

2. Proving things in predicate logic

PropositionalLogic adds variables and quantifiers to PredicateLogic. So now we can say things like ∀x Human(x) => Mortal(x).

3. Choosing a proof technique

Key idea is that structure of consequent hints at possible structure for the proof, e.g. to prove P /\ Q prove P and Q separately (and then use conjunction to smack them together---this step is usually implicit); to prove P => Q assume P and prove Q (then Deduction Theorem does the rest---again this is usually not stated explicitly); to prove ∀x P(x) prove that P(x) holds for some arbitrary x. See ProofTechniques for the big table.

Often there is more than one technique you can try. If the first one doesn't work, try another one. Repeat until something works. If it doesn't look like anything is working, look for a counterexample or disproof.


2014-06-17 11:57