Final Exam Review

This is an overview of material we have covered since the third exam. **
Since the final is cumulative, you should also be familiar with the material on
the three previous reviews. **The final will be approximately twice as long as
the in-class exams.

Some of the important concepts are discussed in the pages on equivalent systems of propositional logic, nonclassical logics, and Gödel's incompleteness theorem.

**1. Basic concepts**

**equivalent systems of propositional logic**. You should know how to prove that two rule systems for propositional logic are equivalent. I might give you an example of systems that are equivalent and ask you to prove this. The necessary proofs would be fairly straightforward proofs in propositional logic; the hard part is knowing exactly what you need to show. (For details on how to do this and some examples of equivalent systems, see my web page on this topic.) I will*not*give an example that involves adding or deleting rules that use subproofs.- what is
**many-valued logic**? What are some reasons one might find it desirable? I might ask something like this: give a three-valued truth table for conjunction (or: disjunction, negation, the conditional, etc.). Explain what your third value is and justify your choices of truth values in the rows where the base columns contain the third value. (For more see the nonclassical logics page.) - what is
**fuzzy logic**and how does it differ from classical logic? I might give you the fuzzy truth values for some atomic sentences and ask you to determine the fuzzy values of compound sentences containing them. (For more see the nonclassical logics page.) - what is
**intuitionistic logic**? How does it differ from the classical system we have learned? (For more see the nonclassical logics page.) It would be enough to state that the deductive system we have studied, minus the ~Elim rule, is a system of intuitionistic logic. - what is
**G****ö****del's incompleteness theorem**? You don't need to be able to prove anything, just to state the main idea of the theorem. The following would be just fine: Gödel shows that for any consistent set of axioms for arithmetic that can prove certain basic arithmetic facts, there will inevitably be true sentences of arithmetic that cannot be proven from the axioms. For short, no consistent, sufficiently strong set of axioms for arithmetic can be complete. (For details see the incompleteness theorems page.)

**2. Translations**

- know how to translate sentences from English into symbolic notation, including quantifiers.
- Translations will include sentences saying that there are at least n
objects, at most n objects, and exactly n objects. Also included will be
translations of sentences containing the terms 'both', 'neither', and 'the'.
(Note that you will need to be able to give the full translations for these
sentences, not just abbreviations such as E
^{≥n}xF(x)!) - Some reminders on things people have a tendency to forget (repeated from the review sheet for the third exam): remember the four Aristotelian forms, and the step-by-step method of translation; the more complex the sentence, the more helpful these will be (and the more dangerous it is to ignore them!).
- Don't forget how to handle potentially troublesome sentences, including
sentences containing "only" (e.g. "only large dogs have hip
problems," "only those who buy a ticket can win the lottery,"
etc.); donkey sentences; sentences in which existential-sounding phrases are
really universal ("an elephant is a large mammal with a trunk" --
this does
**not**mean that there is at least one elephant that is a large mammal with a trunk!). - Keep in mind that it's a bad idea to translate anything as an existentially quantified conditional. Also keep in mind the somewhat surprising interactions between quantification and conditionals, notably the equivalence of ∀x (P(x) → Q) with ∃x P(x) → Q and of ∃x (P(x) → Q) with ∀x P(x) → Q (where Q contains no free occurrences of x).

**3. Proofs**

- Know how to do proofs involving logical relations between sentences that translate notions like 'at most', 'at least', 'exactly', 'the', 'both', and 'neither'.
- Although these proofs are not usually intrinsically difficult, they do tend to get longer than the proofs on earlier exams. And you need to remember the identity rules!
- Possible examples include: proving that there are at most two cubes from the premise that there is at most one cube; proving that there is at least one cube from the premise that there are at least two cubes; proving that there are at least two cubes and/or that there are at most two cubes from the premise that there are exactly two cubes; proving that there is exactly one cube from the premise that the cube is large; proving that there are exactly two cubes from the premise that neither cube is small. And so on -- you get the idea, hopefully! (I will write the premise(s) and conclusion out in symbolic notation on the exam however; the translation questions will be separate from the proofs.) These proofs will resemble the final batch of homework proofs.

Last update: April 29, 2011.

Curtis Brown
| Symbolic Logic
| Philosophy
Department | Trinity
University

cbrown@trinity.edu