7 Formal Language

The language of quantificational logic will afford the means to capture the validity of a variety of arguments for which propositional logic appears to be inadequate. We specify:

  • a syntax for the language, which will include a vocabulary and a set of grammatical rules designed to specify which expressions are formulas of the language, and

  • a semantics for the language, which will explain how to interpret the expressions and formulas of the language and define what is for a formula to be true under a given interpretation.

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. Each predicate comes with a fixed number of argument places.

\[ 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: \[ \neg, \vee, \wedge, \to \]

Quantifiers

There are two quantifier expressions: \[ \forall, \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’.

Example 7.1 Each of the expressions below is an atomic formula of quantificational logic: \[ \begin{array}{c} Pxy\\ Qabx\\ Rxaby_3\\ \dots \end{array} \]

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.

  1. All atomic formulas are formulas.
  2. If \(\varphi\) and \(\psi\) are formulas, then each of \[ \neg \varphi, (\varphi \wedge \psi), (\varphi \vee \psi), (\varphi \to \psi) \] is a formula.
  3. If \(\varphi\) is a formula and \(x\) is a variable, then each of \(\forall x \varphi\) and \(\exists x \varphi\) is a formula.
  4. Nothing else is a formula.

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

Example 7.2 Consider the expression: \((\forall x Pxy \to \exists y \ Qab)\). This is an official formula of the language. Here is a justification:

  1. \(Pxy\) is a formula (rule 1).
  2. \(Qab\) is a formula (rule 1).
  3. \(\forall x Pxy\) is a formula (rule 3, from 1).
  4. \(\exists y Qab\) is a formula (rule 3, from 2).
  5. \((\forall x Pxy \to \exists y \ Qab)\) is a formula (rule 2, from 3 and 4).

Therefore, we conclude that \((\forall x Pxy \to \exists y \ Qab)\) is a formula of quantificational logic.

Example 7.3 Consider the expression: \(\forall x (Pxy \to Qab)\). This is an official formula of the language. Here is a justification:

  1. \(Pxy\) is a formula (rule 1).
  2. \(Qab\) is a formula (rule 1).
  3. \((Pxy \to \exists y \ Qab)\) is a formula (rule 2, from 1 and 2).
  4. \(\forall x (Pxy \to \exists y \ Qab)\) is a formula (rule 3, from 3).

Therefore, we conclude that \(\forall x (Pxy \to Qab)\) is a formula of quantificational logic.

We now make a distinction between two types of occurrences of a variable in a formula. In the formula \(\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:

  1. All occurrences of a variable in an atomic formula are free.
  2. The free occurrences of a variable in formulas of the form \(\varphi\) and \(\psi\) remain free when they occur in \[ \neg \varphi, (\varphi \wedge \psi), (\varphi \vee \psi), (\varphi \to \psi) \]
  3. No occurrence of the variable \(v\) is free in a formula of the form \[ \forall v \varphi, \exists v \varphi \] All occurrences of variables other than \(v\) that are free in \(\varphi\) remain free in those formulas.

Example 7.4 Consider the expression: \(Px \to \forall x Rxx\). This is an official formula of the language.The first two occurrences of the variable \(x\) occur free in the formula:

Here is a justification:

  1. \(x\) occurs free in \(Px\) (rule 1).
  2. That occurrence of \(x\) remains free when embedded in a conditional of the from \((Px \to \psi)\) (rule 2).
  3. The occurrences of \(x\) in \(\forall x Rxx\) are not free (rule 3).

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 \(\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.

Example 7.5 Consider the expression: \((\forall x \exists y Rxy \vee Qyx)\). This is an official formula of the language.The formula is open because the last occurrences of the variables \(y\) and \(x\) are free in the formula.

Example 7.6 Consider the expression: \(\forall x \exists y (Rxy \vee Qyx)\). This is an official formula of the language.The formula is closed because no occurrences of the variables \(y\) or \(x\) are free in the formula.

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: \[ \forall x (Rxa \to Rax). \] For \((Rxa \to Rax)\) is here part of the formula \(\forall x (Rxa \to Rax)\). Such a formula is importantly different from: \[ (\forall x Rxa \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 \((\forall x Rxa \to Rax)\) as it is not in the scope of the universal quantifier \(\forall x\).

Example 7.7 We are able to use the expression \[ \forall x Rxa \to Rax \] as an abbreviation for the formula \[ (\forall x Rxa \to Rax) \]

Exercises

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

    1. \(\neg Rxy\)

    2. \(Rxy\)

    3. \(Aabx\)

    4. \(Qe\)

    5. \(Pxyza\)

    6. \(RPa\)

Open ↗

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

    1. \(\neg \neg Rxy\)

    2. \((Pa \to (Axy \wedge \exists x Qx))\)

    3. \(\forall x Ryy\)

    4. \(\exists x y (P \wedge P(y))\)

    5. \(\forall \forall x Ryx\)

    6. \(\exists x \exists y Rxy\)

Open ↗

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

    1. \(\exists x \exists y Rxy \to Px\)

    2. \(\forall x Rx \vee \exists y Qyy\)

    3. \(Px \wedge Qx \vee Rxy\)

    4. \(Px \wedge Qx \to Rxy\)

    5. \(\exists x Px \wedge \exists y Qy \wedge \exists z Rz\)

    6. \(\exists x \forall y \exists z (Px \wedge Qy \wedge Rxyz)\)

Open ↗

  1. Determine whether the following formulas contain a free occurrence of the variable \(x\).

    1. \(\forall x (Rxy \wedge Ryx)\)

    2. \(\forall x Rxy \wedge Ryx\)

    3. \(\exists x (Px \wedge Qx) \to \forall y Rxy\)

    4. \(\forall x \exists y Rxy \to \exists x \forall y Ryx\)

    5. \(\forall x \exists y Rxy \to \forall y Ryx\)

    6. \(\forall x (\exists y Rxy \to \forall y Ryx)\)

Open ↗

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

    1. \(\forall x Rxy \wedge Ryx\)

    2. \(Rab\)

    3. \(\exists x (Pax \wedge Qxa) \to \forall y Rxy\)

    4. \(\forall x Ryy\)

    5. \(\forall x \exists y \forall z Rxyx\)

    6. \(Rax \to \forall x Rxx\)

Open ↗