what are FO validity, FO equivalence, and FO consequence?
We discussed two ways of defining 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)';
and more formally, in terms of
interpretations. How are they related to logical truth, logical equivalence,
and logical consequence; and to tautology, tautological equivalence, and
tautological consequence?
Suppose the only logical connectives our language included were those for
negation and conjunction. Would our language lose any expressive power?
Explain.
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))⇎(∃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)))).
2. Truth Tables
be able to identify the truth-functional form of quantifier
sentences, and use a truth table to determine whether a quantifier sentence
is a tautology, is tautologically equivalent to other another sentence, or
is a tautological consequence of a set of other sentences. (Don't forget the
truth-functional form algorithm described on p. 261 of our text.)
3. 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
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).
4. 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, better 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.)