Exam 3 Review
1. Basic concepts
- what are FO validity, FO equivalence, and FO consequence?
We defined these concepts informally, in terms of logical relations that
still hold regardless of what substitutions are made for predicates, including
substitution of predicates with unknown meanings like 'Mimsy(x)' and 'Outgrabe(x,y)'. How are they related to logical truth, logical equivalence,
and logical consequence; and to tautology, tautological equivalence, and
- Know the four Aristotelian forms for quantifier sentences, both how they
are written in English and how to translate them into a first-order language. Also know
equivalences involving those forms and negation (for example, that the
negation of a universal affirmative is equivalent to a particular negative).
- Know the DeMorgan's equivalences for quantifiers. You should also be
able to explain how they are similar to the propositional DeMorgan's
- Know the other quantifier equivalences in chapter 10. For example, you should know that
Large(x)) is not
FO equivalent to
- axioms: know what an axiom is, and what it's used for. Be able to
construct axioms to capture the relations between a collection of
predicates, for example the Tarski's World predicates for shape or size or
location, or perhaps something like the relations between the predicates
Parent(x,y), Son(x,y), Daughter(x,y), Father(x,y), Mother(x,y), Sibling(x,y).
instance, the following seems like a reasonable axiom concerning the Sibling(x,y) relation:
(Father(z,x) & Father(z,y))
- What does it mean to say that a deductive system is sound? What
does it mean to say that a deductive system is complete?
- know how to translate sentences from English into symbolic notation,
- Translations will include sentences with multiple quantifiers, mixed quantifiers,
truth-functional compounds of quantifier sentences, etc. 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
FO equivalence of
→ Q) with
→ Q and of
→ Q) with
→ Q (where Q contains no free
occurrences of x).
- know how to do proofs using all the rules we have covered so far. In
addition to all the propositional rules, this includes the introduction and
elimination rules for the quantifiers. If you had trouble with any of the
homework exercises, it would be a good idea to take another look at them!
- It would be a good
idea to be able to prove basic quantifier equivalences, e.g. the DeMorgan's
equivalences; the equivalence of
∨ Q(x)) with
Q(x); the Aristotelian form equivalences; and so on. (By the "Aristotelian
form equivalences," I mean the following. Recall that A = universal
affirmative, I = particular affirmative, E = universal negative, and O =
particular negative. Then A
Last update: April 4, 2011.
| Symbolic Logic
Department | Trinity