Philosophy 2340
Symbolic Logic I

Notes on Barwise and Etchemendy,
Language, Proof, and Logic, Chapter 9

With Chapter 9, we move from (mainly) propositional logic to predicate logic. We will need to extend and complicate our language.

1. Syntax

Here is a quick list of the main changes to the syntax of the first-order language we're developing.

We 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 ∀.

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:

1. If F is a predicate of arity n, and t₁, . . ., t_n are terms, then F(t₁, . . ., t_n) is an atomic wff. 
2. If P is a wff, then so is ¬P.
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 and Q are wffs, then so is (P ↔ Q).
7. If P is a wff, and v is a variable, then ∃v P is a wff.
8. If P is a wff, and v is a variable, the ∀v P is a wff.
9. Nothing else is a wff.

The scope of a quantifier is the first complete wff that follows it.

A quantifier binds any variable which (a) is within its scope, (b) matches the quantifier's variable, and (c) isn't already bound by another quantifier.

A variable that is not bound by any quantifier is free.

A sentence is a wff with no free variables.

2. Semantics

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.