Symbolic Logic
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 tautological consequence?
• 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 equivalences.
• Know the other quantifier equivalences in chapter 10. For example, you should know that ∀x (Tet(x) ∧ Large(x)) ⇔ (∀x Tet(x) ∧ ∀x Large(x)), but ∃x (Tet(x) ∧ Large(x)) is not FO equivalent to (∃x Tet(x) ∧ ∃x Large(x)).
• 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). For instance, the following seems like a reasonable axiom concerning the Sibling(x,y) relation: ∀x∀y (Sibling(x,y) ↔ (∃z (Father(z,x) & Father(z,y)) ∧ ∃w (Mother(w,x) ∧ Mother(w,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?

2. Translations

• know how to translate sentences from English into symbolic notation, including quantifiers.
• 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 ∀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 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 ∀x (P(x) ∧ Q(x)) with ∀x P(x) ∧ ∀x Q(x), of ∃x (P(x) ∨ Q(x)) with ∃x P(x) ∨ ∃x 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 ⇔ ~O; I ⇔ ~E; E ⇔ ~I; O ⇔ ~A.)