authored by Premmi and Beguène
We will now briefly discuss the terms formula and free variables that we encountered during our discussion of the substitution axiom which is one of the two Axioms of Equality.
We can think of language as being comprised of a set of symbols or letters called the alphabet of the language, from which we form words by constructing sequences of letters taken from the alphabet.
Similarly, in mathematical logic, a formal language consists of words whose letters are taken from the set of formal symbols referred to as an alphabet and are well-formed according to a specific set of rules called formal grammar.
A symbol or string (sequence) of symbols may comprise a well-formed formula if it is consistent with the formation rules of the language. Formation rules describe which strings formed from the alphabet of a formal language are syntactically valid within that language. These rules address only the location and manipulation of strings; they do not describe anything else about a language, such as its semantics (i.e., what the strings mean).
Therefore, a well-formed formula, abbreviated WFF or wff, often referred to simply as a formula, is a finite sequence of symbols from a given alphabet that belongs to the formal language for which it makes sense to ask “Is this formula true?”, once any free variables in the formula have been instantiated.
A free variable is a symbol that specifies places in a formula where the symbol will later be replaced by some value. It should be noted that free variables appear only in the first-order formulas. A first-order formula is a formula in first-order logic—a system of logic more expressive and hence more powerful than proportional logic—used to express statements about objects and their relationships in a structured way, which we will discuss in detail later.
Example of a First-Order Formula
The following is an example of a first-order formula.
\forall x \ \, \, \exists y \ R(x, y)
This is interpreted in mathematical parlance as “for all x, there exists a y, such that x \text{ and} y are related by the relation R.” This formula isn’t true or false unless we assign values to x, y \text{ and the relation} R.
A first-order formula isn’t true or false on its own. Before we can get a truth value we have to give an interpretation.Turning a first-order formula into a statement that is either true or false is called giving an interpretation for the formula.
Interpretation
An interpretation of a first-order formula consists of a set X, called the domain of the interpretation, along with a relation on X for each relation symbol in the formula.
Once we’ve given an interpretation, i.e., substituted any variables in the formula with values from the domain and any relation with that defined on the domain, we can evaluate whether the formula is true or false in that interpretation.
Here are some interpretations of the first-order formula:
\forall x \ \, \, \exists y \ R(x, y)
In the ensuing discussion, let’s denote \mathbb{N} as the set of all natural numbers \{0, 1, 2, \dots\}.
First Interpretation:
- Domain: \mathbb{N}
- Relation: R is <
The interpreted formula becomes:
\forall x \in \mathbb{N} \ \, \, \exists y \in \mathbb{N} \ x < yThis interpreted formula is true. For every natural number x there does exist a natural number y with x < y, e.g. y could be the natural number x + 1.
Second Interpretation:
- Domain: \mathbb{N}
- Relation: R is >
The interpreted formula becomes:
\forall x \in \mathbb{N} \ \, \, \exists y \in \mathbb{N} \ x > yIn this case, the interpreted formula is false. It is not true that for every natural number x there exists a natural number y such that x > y. For example, x could be 0 in which case no natural number y satisfies x > y.