# Chapter 27 Sentences of FOL

We know how to represent English sentences in FOL. The time has finally come to define the notion of a sentence of FOL.

## 27.1 Expressions

There are six kinds of symbols in FOL:

1. 1.

Predicates: $A$, $B$, $C$, …, $Z$, or with subscripts, as needed: $A_{1}$, $B_{1}$, $Z_{1}$, $A_{2}$, $A_{25}$, $J_{375}$, …

2. 2.

Names: $a$, $b$, $c$, …, $r$, or with subscripts, as needed: $a_{1}$, $b_{224}$, $h_{7}$, $m_{32}$, …

3. 3.

Variables: $s$, $t$, $u$, $v$, $w$, $x$, $y$, $z$, or with subscripts, as needed: $x_{1}$, $y_{1}$, $z_{1}$, $x_{2}$, …

4. 4.

Connectives: $\neg$, $\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$

5. 5.

Brackets: ( , )

6. 6.

Quantifiers: $\forall$, $\exists$

We define an expression of FOL as any string of symbols of FOL. Take any of the symbols of FOL and write them down, in any order, and you have an expression.

## 27.2 Terms and formulas

In chapter 6, we went straight from the statement of the vocabulary of TFL to the definition of a sentence of TFL. In FOL, we will have to go via an intermediary stage: via the notion of a formula . The intuitive idea is that a formula is any sentence, or anything which can be turned into a sentence by adding quantifiers out front. But this intuitive idea will take some time to unpack.

We start by defining the notion of a term.

A term is any name or any variable.

So, here are some terms:

$a,b,x,x_{1},x_{2},y,y_{254},z$

Next we need to define atomic formulas.

1. 1.

Any sentence letter is an atomic formula.

2. 2.

If $\mathscr{R}$ is an $n$-place predicate and $\mathscr{t}_{1},\mathscr{t}_{2},\ldots,\mathscr{t}_{n}$ are terms, then $\mathscr{R}(\mathscr{t}_{1},\mathscr{t}_{2},\ldots,\mathscr{t}_{n})$ is an atomic formula.

3. 3.

If $\mathscr{t}_{1}$ and $\mathscr{t}_{2}$ are terms, then $\mathscr{t}_{1}=\mathscr{t}_{2}$ is an atomic formula.

4. 4.

Nothing else is an atomic formula.

Note that we consider sentence letters also formulas of FOL, so every sentence of TFL is also a formula of FOL.

The use of script letters here follows the conventions laid down in chapter 8. So, ‘$\mathscr{R}$’ is not itself a predicate of FOL. Rather, it is a symbol of our metalanguage (augmented English) that we use to talk about any predicate of FOL. Similarly, ‘$\mathscr{t}_{1}$’ is not a term of FOL, but a symbol of the metalanguage that we can use to talk about any term of FOL. So, where ‘$F$’ is a one-place predicate, ‘$G$’ is a three-place predicate, and ‘$S$’ is a six-place predicate, here are some atomic formulas:

 $D$ $F(a)$ $x=a$ $G(x,a,y)$ $a=b$ $G(a,a,a)$ $F(x)$ $S(x_{1},x_{2},a,b,y,x_{1})$

Once we know what atomic formulas are, we can offer recursion clauses to define arbitrary formulas. The first few clauses are exactly analogous to those in the definition of ‘sentence of TFL’.

1. 1.

Every atomic formula is a formula.

2. 2.

If $\mathscr{A}$ is a formula, then $\neg\mathscr{A}$ is a formula.

3. 3.

If $\mathscr{A}$ and $\mathscr{B}$ are formulas, then $(\mathscr{A}\wedge\mathscr{B})$ is a formula.

4. 4.

If $\mathscr{A}$ and $\mathscr{B}$ are formulas, then $(\mathscr{A}\vee\mathscr{B})$ is a formula.

5. 5.

If $\mathscr{A}$ and $\mathscr{B}$ are formulas, then $(\mathscr{A}\rightarrow\mathscr{B})$ is a formula.

6. 6.

If $\mathscr{A}$ and $\mathscr{B}$ are formulas, then $(\mathscr{A}\leftrightarrow\mathscr{B})$ is a formula.

7. 7.

If $\mathscr{A}$ is a formula and $\mathscr{x}$ is a variable, then $\forall\mathscr{x}\,\mathscr{A}$ is a formula.

8. 8.

If $\mathscr{A}$ is a formula and $\mathscr{x}$ is a variable, then $\exists\mathscr{x}\,\mathscr{A}$ is a formula.

9. 9.

Nothing else is a formula.

So, assuming again that ‘$F$’ is a one-place predicate, ‘$G$’ is a three-place predicate and ‘$S$’ is a six place-predicate, here are some formulas you can build this way:

 $\displaystyle F(x)$ $\displaystyle G(a,y,z)$ $\displaystyle S(y,z,y,a,y,x)$ $\displaystyle(G(a,y,z)\rightarrow\,$ $\displaystyle S(y,z,y,a,y,x))$ $\displaystyle\forall z(G(a,y,z)\rightarrow\,$ $\displaystyle S(y,z,y,a,y,x))$ $\displaystyle F(x)\wedge\forall z(G(a,y,z)\rightarrow\,$ $\displaystyle S(y,z,y,a,y,x))$ $\displaystyle\exists y(F(x)\wedge\forall z(G(a,y,z)\rightarrow\,$ $\displaystyle S(y,z,y,a,y,x)))$ $\displaystyle\forall x\exists y(F(x)\wedge\forall z(G(a,y,z)\rightarrow\,$ $\displaystyle S(y,z,y,a,y,x)))$

We can now give a formal definition of scope, which incorporates the definition of the scope of a quantifier. Here we follow the case of TFL, though we note that a logical operator can be either a connective or a quantifier:

• The main logical operator in a formula is the operator that was introduced most recently, when that formula was constructed using the recursion rules.

• The scope of a logical operator in a formula is the subformula for which that operator is the main logical operator.

So we can graphically illustrate the scope of the quantifiers in the preceding example thus:

$\overbrace{\forall x\overbrace{\exists y(F(x)\leftrightarrow\overbrace{\forall z% (G(a,y,z)\rightarrow S(y,z,y,a,y,x))}^{\text{scope of }\forall z\text{'}}}^{% \text{scope of }\exists y\text{'}})}^{\text{scope of `\forall x'}}$

## 27.3 Sentences and free variables

Recall that we are largely concerned in logic with assertoric sentences: sentences that can be either true or false. Many formulas are not sentences. Consider the following symbolization key:

domain:

people

$L(x,y)$:

blankx loves blanky

$b$:

Boris

Consider the atomic formula ‘$L(z,z)$’. All atomic formulas are formulas, so ‘$L(z,z)$’ is a formula, but can it be true or false? You might think that it will be true just in case the person named by ‘$z$’ loves themself, in the same way that ‘$L(b,b)$’ is true just in case Boris (the person named by ‘$b$’) loves himself. However, ‘$z$’ is a variable, and does not name anyone or any thing.

Of course, if we put an existential quantifier out front, obtaining ‘$\exists z\,L(z,z)$’, then this would be true if⁠f someone loves themselves. Equally, if we wrote ‘$\forall z\,L(z,z)$’, this would be true if⁠f everyone loves themselves. The point is that we need a quantifier to tell us how to deal with a variable.

Let’s make this idea precise.

An occurrence of a variable $\mathscr{x}$ is bound if⁠f it falls within the scope of either $\forall\mathscr{x}$ or $\exists\mathscr{x}$. An occurrence of a variable which is not bound is free .

For example, consider the formula

$(\forall x(E(x)\vee D(y))\rightarrow\exists z(E(x)\rightarrow L(z,x)))$

The scope of the universal quantifier ‘$\forall x$’ is ‘$\forall x(E(x)\vee D(y))$’, so the first ‘$x$’ is bound by the universal quantifier. However, the second and third occurrence of ‘$x$’ are free. Equally, the ‘$y$’ is free. The scope of the existential quantifier ‘$\exists z$’ is ‘$\exists z(E(x)\rightarrow L(z,x))$’, so ‘$z$’ is bound.

Formulas that do not have free variables, i.e., every variable is bound, are called sentences . Only sentences can be true or false.

A sentence of FOL is any formula of FOL that contains no free variables.

Note that in the formation rules given in section 27.2, specifically in the clauses for $\forall$ and $\exists$, we did not require that the variable $\mathscr{x}$ in $\forall\mathscr{x}\,\mathscr{A}$ and $\exists\mathscr{x}\,\mathscr{A}$ does not already occur as a bound variable in $\mathscr{A}$. So we allow, for instance, ‘$\exists x(\forall x\,F(x)\rightarrow G(x))$’ as a sentence. We won’t be meeting such special cases often, since we can always rename bound variables to obtain an equivalent sentence that avoids such weirdness; in this case, e.g., ‘$\exists x(\forall y\,F(y)\rightarrow G(x))$’. But since it is allowed to happen, we should clarify which quantifiers bind which variables: An occurrence of a bound variable is always bound by the quantifier with the same matching variable that is closest to it. By “closest” we mean: it is the main logical operator of the smallest subformula into the scope of which the occurrence of the variable falls. So in our previous example, ‘$\forall x$’ binds the occurrence of $x$ in ‘$F(x)$’, since it is the main logical operator of ‘$\forall x\,F(x)$’. The ‘$\forall x$’ does not bind the ‘$x$’ in ‘$G(x)$’, however. The ‘$\exists x$’ does not bind the ‘$x$’ in ‘$F(x)$’, but it does bind the ‘$x$’ in ‘$G(x)$’.

The rules also do not require that the bound variable $\mathscr{x}$ actually occurs free in $\mathscr{A}$ (or even at all). So our rules also allow ‘$\exists x\,F(a)$’ and ‘$\exists x\forall x\,G(x)$’ as formulas. In each case, the ‘$\exists x$’ does not bind ‘$x$’, because ‘$x$’ does not occur free in ‘$F(a)$’ or in ‘$\forall x\,G(x)$’. In the former case, ‘$x$’ does not occur at all; in the latter, it is already bound by ‘$\forall x$’. This is called vacuous quantification . It rarely appears in practice, and isn’t harmful. The two sentences are equivalent to the sentences without the ‘$\exists x$’, i.e., to ‘$F(a)$’ and ‘$\forall x\,G(x)$’.

## 27.4 Bracketing conventions

We will adopt the same notational conventions governing brackets that we did for TFL (see chapters 6 and 11.3.) First, we may omit the outermost brackets of a formula. Second, we may use square brackets, ‘[’ and ‘]’, in place of brackets to increase the readability of formulas.

Sentences of FOL used in our examples can become quite cumbersome, and so we also introduce a convention to deal with conjunctions and disjunctions of more than two sentences. We stipulate that $A_{1}\land A_{2}\land\dots\land A_{n}$ and $A_{1}\lor A_{2}\lor\dots\lor A_{n}$ are to be interpreted as, respectively:

• $(\dots(A_{1}\land A_{2})\land\dots\land A_{n})$

• $(\dots(A_{1}\lor A_{2})\lor\dots\lor A_{n})$

In practice, this just means that you are allowed to leave out parentheses in long conjunctions and disjunctions. But remember that (unless they are the outermost parentheses of the sentence) you must still enclose the entire conjunction or disjunction in parentheses. Also, you cannot mix conjunctions and disjunctions with each other or with other connectives. So the following are still not allowed, and would be ambiguous if they were:

• $A\lor B\land C\land D$

• $B\lor C\rightarrow D$

## 27.5 Superscripts on predicates

Above, we said that an $n$-place predicate followed by $n$ terms is an atomic formula. But there is a small issue with this definition: the symbols we use for predicates do not, themselves, indicate how many places the predicate has. Indeed, in some places in this book, we have used the letter ‘$G$’ as a one-place predicate; in other places we have used it as a three-place predicate. So, unless we state explicitly whether we want to use ‘$G$’ as a one-place predicate or as a three place predicate, it is indeterminate whether ‘$G(a)$’ is an atomic formula or not.

There is an easy way to avoid this, which many books adopt. Instead of saying that our predicates are just capital letters (with numerical subscripts as necessary), we could say that they are capital letters with numerical superscripts (and with numerical subscripts as necessary). The purpose of the superscript would be to say explicitly how many places the predicate has. On this approach, ‘$G^{1}$’ would be a one-place predicate, and ‘$G^{3}$’ would be an (entirely different) three places predicate. They would need to have different entries in any symbolisation key. And ‘$G^{1}(a)$’ would be an atomic formula, whereas ‘$G^{3}(a)$’ would not; likewise ‘$G^{3}(a,b,c)$’ would be an atomic formula, and ‘$G^{1}(a,b,c)$’ would not.

So, we could add superscripts to all our predicates. This would have the advantage of making certain things completely explicit. However, it would have the disadvantage of making our formulas much harder to read; the superscripts would distract the eye. So, we will not bother to make this change. Our predicates will remain without superscripts. (And, in practice, any book which includes superscripts almost immediately stops including them!)

However, this leaves open a possibility of ambiguity. So, when any ambiguity could arise—in practice, very rarely—you should say, explicitly, how many places your predicate(s) have.

## Practice exercises

A. Identify which variables are bound and which are free.

1. 1.

$\exists x\,L(x,y)\wedge\forall y\,L(y,x)$

2. 2.

$\forall x\,A(x)\wedge B(x)$

3. 3.

$\forall x(A(x)\wedge B(x))\wedge\forall y(C(x)\wedge D(y))$

4. 4.

$\forall x\exists y[R(x,y)\rightarrow(J(z)\wedge K(x))]\vee R(y,x)$

5. 5.

$\forall x_{1}(M(x_{2})\leftrightarrow L(x_{2},x_{1}))\wedge\exists x_{2}\,L(x_% {3},x_{2})$