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
- 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
- know how to translate sentences from English into symbolic notation,
- 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≥nxF(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).
- 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
Last update: April 29, 2011.
| Symbolic Logic
Department | Trinity