6 Formal Language

Syntax

We begin with the vocabulary of quantificational logic.

⊕Vocabulary

The vocabulary of quantificational logic contains six types of symbol:

Constants

These are the lowercase letters $a$, $b$, $c$, $d$, and $e$ with or without numerical subscripts:

$$a,b,c,d,e$$

Predicates

These are uppercase letters $P$, $Q$, $R$, $S$, and $T$ with or without numerical subscripts.

$$P,Q,R,S,T\dots$$

Variables

These are lowercase letters $x$, $y$, and $z$ with or without numerical subscripts:

$$x,y,z\dots$$

Connectives

These are the symbols: $$\mathrm{\neg },\vee ,\wedge ,\to$$

Quantifiers

There are two quantifier expressions: $$\mathrm{\forall },\mathrm{\exists }$$ Parentheses

There are two parentheses: $$),($$

Nothing else is a symbol of the language.

⊕Grammar

The grammar of quantificational logic explains how to combine these symbols into formulas of the language. We proceed in two stages.

Atomic Formula

If $P$ is a predicate with $n$ argument places, and each of ${\tau }_1,\dots ,{\tau }_n$ is a constant or a variable, then $$P{\tau }_1,\dots ,{\tau }_n$$ is an atomic formula.

Atomic formulas are the formal counterparts of simple predications such as ‘Los Angeles is a city’ or ‘Los Angeles is between San Diego and San Francisco’.

Atomic formulas provide simple constituents for more complex formulas.

Formula

We now define what is for an expression to be a formula of quantificational logic.

We proceed to illustrate the characterization of formula through concrete examples.

⊕ The construction tree depicts the construction of the formula from simpler constituents.

⊕ The construction tree depicts the construction of the formula from simpler constituents.

We now make a distinction between two types of occurrences of a variable in a formula. In the formula $\mathrm{\forall }x(Qxy\to Ryx)$ the last two occurrences of the variable $x$ match the variable accompanying the quantifier expression, whereas the occurrences of the variable $y$ do not. The occurrences of the variable $x$ have been captured by the initial quantifier, but the occurrences of the variable $y$ remain free.

⊕Free Occurrences

Free Occurrence of a Variable

We define what is for an occurrence of a variable to be free in a formula:

An occurrence of a variable is free when it has not been captured by a quantifier. In the last example, the last two occurrences of the variable $x$ are under the scope of the universal quantifier $\mathrm{\forall }x$, whereas the first two occurrences of the variable are not under the scope of a quantifier.

⊕Bound Occurrences

Bound Occurrence of a Variable:

An occurrence of a variable in a formula is bound if, and only if, it is not free in that formula.

A variable occurs freely in a formula if, and only if, some of its occurrences in the formula are free.

⊕Open and Closed Formulas

Open and Closed Formulas

A formula is open if, and only if, some variables occur freely in the formula. Otherwise, the formula is closed.

Notational Convention

We may remove the outer parentheses from a formula that is not part of another formula.

Notice that this convention will not allow us to omit the parentheses in a formula such as: $$\mathrm{\forall }x(Rxa\to Rax).$$ For $(Rxa\to Rax)$ is here part of the formula $\mathrm{\forall }x(Rxa\to Rax)$. Such a formula is importantly different from: $$(\mathrm{\forall }xRxa\to Rax).$$ The former formula is a closed formula whereas the latter is an open formula, since the last occurrence of the variable $x$ is free in $(\mathrm{\forall }xRxa\to Rax)$ as it is not in the scope of the universal quantifier $\mathrm{\forall }x$.

Semantics

We now explain how to interpret the language of quantificational logic. We will not use assignments of truth values to interpret the language but rather models, which will assign a semantic value to the simplest constituents of a formula. A model for quantificational logic includes:

• a domain of discourse for the quantifiers to range over,
• a specification of denotations for the constants of the language, and
• a specification of extensions for the predicates of the language

The domain of discourse determines the truth conditions of quantified formulas in much the way in which the truth value of a natural language sentence such as ‘I packed everything into my suitcase’ depends on what is the domain of objects over which we take the quantifier ‘everything’ to range. In what follows, we will use a non-empty set of objects as the domain of a model. There are no restrictions on the domain of discourse other than it must contain at least one object.

We will let a model specify denotations for the constants of the language. Constants are formal counterparts of names in natural language, which are generally taken to denote an object in the domain of discourse, e.g., ‘Los Angeles’ denotes a city in Southern California, and ‘Silver Lake’ denotes an area of Los Angeles. A model will assign a member of the domain to each constant of the language as a denotation.

The case of predicates is more subtle. Predicates are formal counterparts of predicate expressions in natural language, which are true of some objects and not of others. Let us begin with one-place predicates such as ‘is red’, which applies to red objects and does not apply to non-red objects. One suggestion at this point is to identify the interpretation of ‘red’ with the set of objects to which the predicate applies. The set of objects to which a given predicate applies is known as the extension of the predicate. Thus the extension of the predicate ‘red’ is the set of red objects and the extension of the predicate ‘human being’ is the set of human beings.

The case of two-place predicates is more complicated. The predicate ‘is south of’ applies to Los Angeles and San Francisco in that order but it fails to apply to San Francisco and Los Angeles in that order. This raises the question of how to specify the extension of the predicate. The answer is to use sets of ordered pairs of objects in the domain, e.g., $⟨LA,SF⟩$ is the ordered pair of Los Angeles and San Francisco in that order whereas $⟨SF,LA⟩$ is the ordered pair of San Francisco and Los Angeles in that order. The extension of the two-place predicate ‘is south of’ will be a set of ordered pairs, which contains $⟨LA,SF⟩$ but not $⟨SF,LA⟩$. The solution generalizes to predicates with even more argument places. The interpretation of a three-place predicate is a set of ordered triples, and more generally, the interpretation of an $n$-place predicate is a set of ordered $n$-tuples.

⊕Model

Model

A model $M$ for quantificational logic is an ordered pair $⟨D,I⟩$, where:

• $D$ is a non-empty set of objects, and
• $I$ interprets constants and predicates in accordance to the requirements:
  • If $a$ is a constant, $I(a)$ is a member of $D$.
  • If $P$ is a one-place predicate, $I(P)$ is a set of members of $P$.
  • If $R$ is an $n$-place predicate, $I(R)$ is a set of $n$-tuples of members of $D$.

Given an argument in the language of quantificational logic, we will often consider the question of whether there is an interpretation of the language on which the premises are true and the conclusion false. That amounts to the question whether there is a model for quantificational logic, which verifies the premises but not the conclusion of the argument.

One heuristic you may find helpful for the specification of a model is to use a diagrams as partial representation of the model. The diagram should come accompanied with a key designed to help us specify the interpretation of the relevant constants and predicates.

⊕
$P:\text{enclosed by a circle}$
$Q:\text{enclosed by a dark grey figure}$
$R:\text{points to}$
$a:p_1$
$b:p_2$

This heuristic comes with severe limitations, since some models, e.g., models with an infinite domain, are much too complex to be represented by means of a finite diagram. The method will, however, suffice for some purposes; it will enable us to establish the invalidity of a broad family of arguments in quantificational logic.

The definition of a model makes sure that models provide a semantic value for constants and predicates, but they remain silent when it comes to variables. If constants are the formal counterparts of names in natural language, variables resemble pronouns like ‘he’ or ‘she’, which do not appear to receive a denotation when used in a sentence like ‘If a person likes opera, then she likes classical music.’ For this reason, models do not assign a denotation to variables.

Instead, variables will be treated as temporary labels for members of the domain. That will allow us to evaluate an open formula $Px\wedge Rxy$ relative to an assignment of values to the variables that occur in it. More generally, given a model $M$, we now explain what is an assignment of members of $M$ to the variables of the language.

Variable Assignment

A variable assignment $\alpha$ over a model $M$ is a map from the range of variables to a members of the domain $D$.

Once variable assignments are in place, we are in a position to assign a semantic value to a variable $x$ in a model $M$ relative to an assignment $\alpha$, which is just $\alpha (x)$.

For technical reasons, we want to assign semantic values to open formulas in a model relative to a variable assignment over the model. The definition of truth in a model relative to a variable assignment will be inductive: we will define the truth conditions of complex formulas in terms of the truth conditions of simpler ones in much the way with did with the definition of truth under an assignment of truth values to propositional variables in the case of propositional logic. We will begin with an account of the truth conditions of atomic formulas, and we will explain how to assign truth values to more complex sentences in a model relative to an assignment.

Denotation

If $\tau$ is either a constant $c$ or a variable $x$, the denotation of $\tau$ in a model $M$ under assignment $\alpha$ is $I(c)$ if $\tau$ is a constant $c$ and $\alpha (x)$ if $\tau$ is a variable $x$.

Atomic Formulas

$P\tau$ is true in $M$ under $\alpha$ if the denotation of $\tau$ in $M$ under $\alpha$ is in the extension of $P$, e.g., $Px$ is true in $M$ under $\alpha$ if $\alpha (x)\in I(P)$ and $Pc$ is true in $M$ under $\alpha$ if $I(c)\in I(P)$.  More generally, $R{\tau }_1\cdots {\tau }_n$ is true in $M$ under $\alpha$ if the denotations of ${\tau }_1\cdots {\tau }_n$ are in that order in the extension of $R$, e.g., $Rax$ is true in $M$ under $\alpha$ if $⟨I(a),\alpha (x)⟩\in I(R)$ .

The evaluation of atomic formulas is similar when we use a diagram to specify a model.

⊕
$P:\text{enclosed by a circle}$
$Q:\text{enclosed by a dark grey figure}$
$R:\text{points to}$
$a:p_1$
$b:p_2$

If a complex formula is constructed from simpler formulas by an application of a connective such as $\mathrm{\neg }$, $\wedge$. $\vee$, $\to$, and $\leftrightarrow$, then its truth conditions in a model $M$ relative to an assignment $\alpha$ are given inductively in the style of the definition of truth for propositional logic. That is,

Negation

$\mathrm{\neg }\phi$ is true in $M$ relative to a variable asignment $\alpha$ if, and only if, $\phi$ is not true in $M$ relative to $\alpha$.

Conjunction

$\phi \wedge \psi$ is true in $M$ relative to a variable asignment $\alpha$ if, and only if, $\phi$ is true in $M$ relative to $\alpha$ and $\psi$ is true in $M$ relative to $\alpha$.

Disjunction

$\phi \vee \psi$ is true in $M$ relative to a variable asignment $\alpha$ if, and only if, $\phi$ is true in $M$ relative to $\alpha$ or $\psi$ is true in $M$ relative to $\alpha$.

Conditional

$\phi \to \psi$ is true in $M$ relative to a variable asignment $\alpha$ if, and only if, $\phi$ is not true in $M$ relative to $\alpha$ or $\psi$ is true in $M$ relative to $\alpha$.

The situation is similar for diagramatic representations of a model:

⊕
$P:\text{enclosed by a circle}$
$Q:\text{enclosed by a dark grey figure}$
$R:\text{points to}$
$a:p_1$
$b:p_2$

We now explain how to evaluate quantified formulas of the form $\mathrm{\forall }v\phi$ and $\mathrm{\exists }v\phi$ in a model $M$ relative to a variable assignment over $M$. We want a formula of the form $\mathrm{\exists }xP(x)$ to be true in $M$ relative to $\alpha$ if some member of the domain of $M$ lies in the extension of $P$. One way to achieve this is to declare the formula true in $M$ relative to $\alpha$ if there is an object in the domain of $M$ that we can assign to $x$ in order to verify $P(x)$, which means that there is an assignment $\beta$ which is just like $\alpha$ except perhaps for the fact that it assigns a different object to $x$ such that $P(x)$ is true in $M$ relative to $\beta$. Similarly, we want a formula $\mathrm{\forall }xP(x)$ to be true in $M$ relative to $\alpha$ if every member of the domain of $M$ lies in the extension of $P$. In other words, $P(x)$ is true in $M$ no matter what we assign to $x$ provided the new variable assignment remains just like $\alpha$ in all other respects.

Existential Quantification

$\mathrm{\exists }v\phi$ is true in $M$ relative to a variable asignment $\alpha$ if, and only if, there is an object $p$ in the domain of $M$ such that $\phi$ is true in $M$ relative to $\alpha [x/p]$, which is an assignment just like $\alpha$ except perhaps for the fact that it assigns $p$ to the variable $x$.

Universal Quantification

$\mathrm{\forall }v\phi$ is true in $M$ relative to a variable asignment $\alpha$ if, and only if, for every object $p$ in the domain of $M$, $\phi$ is true in $M$ relative to $\alpha [x/p]$, which is an assignment just like $\alpha$ except perhaps for the fact that it assigns $p$ to the variable $x$.

The situation is similar for diagramatic representations of a model $M$ relative to $\alpha$ because there is no member of $D$ we can assign to the variable $x$ making sure the new variable assignment remains just like $\alpha$ in all other respects in order to make:

⊕
$P:\text{enclosed by a circle}$
$Q:\text{enclosed by a dark grey figure}$
$R:\text{points to}$
$a:p_1$
$b:p_2$

Once we define what is for a formula $\phi$ to be true in a model $M$ relative to an assignment $\alpha$, we are in a position to define what is for a formula $\phi$ to be true in a model $M$.

Truth in a Model

A formula $\phi$ is true in a model $M$ if, and only if, $\phi$ is true in $M$ relative to all variable assignments over $M$.

Logical Truth

A formula $\phi$ of quantificational logic is a logical truth if, and only if, $\phi$ is true in every model.

One difference between propositional logic and quantificational logic is that we are not in a position to survey all interpretations of the language in order to determine whether a formula is a logical truth. There is an infinity of domains of discourse to consider and there are different interpretations available for the constants and predicates of the language available for each such domain. The generalization of the tableaux method will provide us with an indirect method for establishing the logical truth of a formula, but in the meantime, all we are in a position to do is to find a counterexample model when a formula is not a logical truth.

⊕
$R:\text{points to}$
$a:p_1$

Equivalence

Two formulas $\phi$ and $\psi$ of quantificational logic are equivalent if, and only if, they are true in exactly the same models.

We find ourselves in a similar situation. We are not yet in a position to establish that two formulas are logically equivalent, but if they are not, we may set out to find a counterexample in the form of a model in which one formula is true and the other one is false.

⊕
$P:\text{enclosed by a circle}$
$Q:\text{enclosed by a diamond}$

Consistency

A set of formulas $S$ of quantificational logic is consistent if, and only if, there is at least one model in which all of its members are true. Otherwise, the set is inconsistent.

If a set of formulas is consistent, then we are in a position to search for a model in which all of their members are true, but it is a different matter to conclusively establish that a set of sentences is inconsistent.

⊕
$P:\text{enclosed by a circle}$
$Q:\text{enclosed by a dark grey figure}$
$R:\text{points to}$
$a:p_1$
$b:p_2$

Validity

An argument of quantificational logic is valid if, and only if, there is no model which all of its premises are true while its conclusion is false. Otherwise, the argument is invalid.

If an argument is not valid, then we are in a position to search for a model in which the premises are true and the conclusion is false. Otherwise, we will have to rely on a generalization of the tableaux method in order to establish validity.

⊕
$P:\text{enclosed by a circle}$
$Q:\text{enclosed by a dark grey figure}$
$R:\text{points to}$
$a:p_1$
$b:p_2$

Exercises

1. Determine whether each of the following expressions is an atomic formula of quantificational logic.

   1. $\mathrm{\neg }Rxy$

   2. $Rxy$

   3. $Aabx$

   4. $Qe$

   5. $Pxyza$

   6. $RPa$

2. Determine whether each of the following expressions is a formula of quantificational logic.

   1. $\mathrm{\neg }\mathrm{\neg }Rxy$

   2. $(Pa\to (Axy\wedge \mathrm{\exists }xQx)$

   3. $\mathrm{\forall }xRyy$

   4. $\mathrm{\exists }xy(P\wedge P(y))$

   5. $\mathrm{\forall }\mathrm{\forall }xRyx$

   6. $\mathrm{\exists }x\mathrm{\exists }yRxy$

3. Determine whether each of the following expressions is an abbreviation for a formula of quantificational logic.

   1. $\mathrm{\exists }x\mathrm{\exists }yRxy\to Px$

   2. $\mathrm{\forall }xRx\vee \mathrm{\exists }yQyy$

   3. $Px\wedge Qx\vee Rxy$

   4. $Px\wedge Qx\to Rxy$

   5. $\mathrm{\exists }xPx\wedge \mathrm{\exists }yQy\wedge \mathrm{\exists }zRz$

   6. $\mathrm{\exists }x\mathrm{\forall }y\mathrm{\exists }z(Px\wedge Qy\wedge Rxyz)$

4. Determine whether the following formulas contain a free occurrence of the variable $x$.

   1. $\mathrm{\forall }x(Rxy\wedge Ryx)$

   2. $\mathrm{\forall }xRxy\wedge Ryx$

   3. $\mathrm{\exists }x(Px\wedge Qx)\to \mathrm{\forall }yRxy$

   4. $\mathrm{\forall }x\mathrm{\exists }yRxy\to \mathrm{\exists }x\mathrm{\forall }yRyx$

   5. $\mathrm{\forall }x\mathrm{\exists }yRxy\to \mathrm{\forall }yRyx$

   6. $\mathrm{\forall }x(\mathrm{\exists }yRxy\to \mathrm{\forall }yRyx)$

5. Determine whether the following formulas are open or closed. Justify your answers.

   1. $\mathrm{\forall }xRxy\wedge Ryxz$

   2. $Rab$

   3. $\mathrm{\exists }x(Pax\wedge Qxa)\to \mathrm{\forall }yRxy$

   4. $\mathrm{\forall }xRyy$

   5. $\mathrm{\forall }x\mathrm{\exists }y\mathrm{\forall }zRxyx$

   6. $Rax\to \mathrm{\forall }xRxx$

6. Determine which of the following formulas are true in the model: ⊕
   $Q:\text{enclosed by a dark grey figure}$
   $S:\text{enclosed by a circle}$
   $T:\text{enclosed by a diamond}$
   $R:\text{points to}$
   $a:p_1$
   $b:p_2$

   1. $Rab$

   2. $Rab\to Rbb$

   3. $Pa\wedge Qb$

   4. $\mathrm{\exists }xSx\wedge \mathrm{\exists }xTx$

   5. $\mathrm{\forall }x(\mathrm{\exists }yRxy\vee \mathrm{\exists }yRyx)$

   6. $\mathrm{\forall }x(Sx\to \mathrm{\exists }y(Qy\wedge Rxy))$