With Chapter 9, we move from (mainly) propositional logic to predicate logic. We will need to extend and complicate our language.
1. Primitive Symbols
We now add two new pieces to our language: variables and quantifiers.
Up until now, the primitive symbols of our language have all been constants, predicates, and connectives.
Now, however, we will introduce two new syntactic categories. First, we need the notion of a term. This is a general category for expressions that can occupy the argument places of predicates (and function symbols, but we have mostly been considering languages without function symbols). Constants are terms, but they are no longer the only kind of term. Variables are also terms. (So are function symbols with terms in their argument places.)
We use letters early in the alphabet for constants: a, b, c, d, e, f, g.
We use letters late in the alphabet for variables: t, u, v, w, x, y, z
Variables can appear anywhere constants do. So our syntax is now more complex.
Our second new syntactic category is the quantifier. We will have two quantifiers, ∃ and ∀. ∃ is known as the existential quantifier and ∀ is known as the universal quantifier.
We will define the notion of a well-formed formula, or wff for short. ("Well-formed" basically means "grammatically correct" or "legal.") Up until now the only wffs we have been able to construct are sentences. With the introduction of variables, however, we will be able to build wffs that are not sentences.
So, here is our new definition of a wff:
0. If F is a predicate of arity n, and t1, . . ., tn are terms, then F(t1, . . ., tn) is an atomic wff.
1. If P is a wff, then so is ¬P.
2. If P and Q are wffs, then so is (P ∧ Q).
3. If P and Q are wffs, then so is (P ∨ Q).
4. If P and Q are wffs, then so is (P → Q).
5. If P and Q are wffs, then so is (P ↔ Q).
6. If P is a wff, and v is a variable, then ∃v P is a wff.
7. If P is a wff, and v is a variable, the ∀v P is a wff.
8. Nothing else is a wff.
The formula ∃x Tet(x) is read: "There is an x such that x is a tetrahedron," or "There exists an x such that x is a tetrahedron," or, more colloquially, "There is a tetrahedron." (You can think of the backward E as standing for "exists.")
The formula ∀x Tet(x) is read: "For all x, x is a tetrahedron" or "For every x, x is a tetrahedron," or, more colloquially, "Everything is a tetrahedron." (You can think of the upside-down A as standing for "all.")
The scope of a quantifier is the first complete wff that follows it.
A quantifier binds any occurrence of a variable which (a) is within its scope, (b) matches the quantifier's variable, and (c) isn't already bound by another quantifier.
An occurrence of a variable that is not bound by any quantifier is free.
A sentence is a wff with no free variables.
Examples: (are they wffs? are they sentences? [remember that a sentence is a wff with no free variables])
Ex Tet(x) & Ex Cube(x)
Ex Tet(x) & Cube(x)
Ex (Tet(x) & Cube(x))
Ex (Tet(x) & Cube(y))
3. SemanticsThe first thing we need in order to do semantics for a full first-order language is a domain or universe. This is the set of objects we want to use the language to talk about. (When we construct sentences about a blocks world, for example, the domain is the set of blocks in that world.)
A formula with n free variables is satisfied by a sequence of n objects from the domain iff the result of replacing the variables by names of the objects, in order, yields a true sentence.
A universal sentence ∀x P(x) is true iff the formula P(x) is satisfied by every object in the domain.
An existential sentence ∃x P(x) is true iff the formula P(x) is satisfied by at least one object in the domain.
3. Translation Issues
The four Aristotelian forms and their standard translations are extremely helpful in translating many English sentences containing quantifiers into symbolic notation. My summary of the Aristotelian forms is here (TLEARN link).
General strategy for translating from English into symbolic notation:
A few issues that sometimes cause problems:
"A", "an", "some", and "something" most often indicate that you need an existential quantifier. "A frog is happy," for instance, would get translated ∃x (Frog(x) ∧ Happy(x)). But not always! Sometimes we use these terms when making a universal claim. "An elephant is a large mammal with a trunk" is most likely intended to be a general claim about all elephants. So it would be translated by something like ∀x (Elephant(x) → (Large(x) ∧ Mammal(x) ∧ HasTrunk(x))). Similarly, "someone who studies hard will get an A" is most likely intended to be a claim about anyone who studies hard, not about some particular person, so it would be translated ∀x (StudiesHard(x) → GetsA(x)).
The difference between "any" and "every" can be confusing. They both "feel" universal, and in the absence of additional operators, there doesn't seem to be much difference. "Brown will eat anything" and "Brown will eat everything" both seem translatable by ∀x WillEat(b, x).
When combined with other logical operators, though, a difference emerges. Compare: "Brown will not eat everything": ¬∀x WillEat(b, x), but "Brown will not eat anything": ∀x ¬WillEat(b, x). One way to think about what is going on here: if "any" is translated by a universal quantifier, it takes "wide scope." That is, when it is combined with another logical connective, that other connective will be inside the scope of the universal quantifier. [However, note that the translation for "Brown will not eat anything" is equivalent, by the DeMorgan's quantifier equivalences, to ¬∃x WillEat(b, x). So a different way to think about things would be to say that when combined with other operators, "any" can be construed as existential instead of universal.]
Another example, this time combining "any" with the conditional. Situation 1: Brown is at a buffet with a lot of fatty food. He would like to try everything. But if he eats everything, he will get sick. So we have: "If Brown eats everything, he will get sick." One way to translate this would be: ∀x Eats(b, x) → GetSick(b). Notice that the universal quantifier only binds the antecedent of the sentence: the overall form of the sentence is a conditional, not a universal.
Contrast that with a situation in which the food is poisoned, so that if Brown eats any of it he will get sick. "If Brown eats anything, he will get sick": ∀x (Eats(b, x) → GetSick(b)). This says that for every piece of food on the buffet, if Brown eats that piece of food, he will get sick. [A different way to look at it: this quantifier translation is actually equivalent to ∃x Eats(b, x) → GetSick(b). So instead of translating the sentence as a universally quantified conditional, we could translate it as a conditional with an existential antecedent.]
One more issue: not every English sentence will fit one of the four Aristotelian forms. This includes some of the sentences in the exercises. Consider "There is something that is neither left of c nor back of d." This is an existential sentence, but it does not quite fit the particular affirmative or particular negative patterns. We want: Ex ~(LeftOf(x, c) v BackOf(c, d)). Similarly, "every object is a large cube" is not a universal affirmative or negative: it says Ax (Large(x) & Cube(x)).