﻿ 3.4 Syntax and semantics of predicate logic

### 3.4 Syntax and semantics of predicate logic

#### Syntax of predicate logic

In 1.3 Truth tables we talked about the syntax and semantics of the language of propositional logic. The main task of the syntax of any language is to distinguish the grammatically correct from the grammatically incorrect sequences of words, which in our case are certain symbols, and the main task of its semantics is to determine when a grammatically correct sentence is true and when false. The syntax and semantics of the language of predicate logic make it possible to strictly define the concepts of logical inference, logical equivalence, contradiction, consistency, logical validity, etc.

The syntax is formulated by means of syntactic rules, which determine all possible ways of constructing grammatically correct expressions of the language, thus giving a recursive definition1 of the concept of a well-formed formula (in short, a formula) of predicate logic. The recursive definition works by specifying the simplest elements of the set of things that fall under the defined concept, then specifying the rules by which more simpler elements of the set produce more complex ones so that no element is left out. An important property of the recursive definition below is that it can be used as an algorithm to determine whether an arbitrary sequence of “words” (symbols in our case) is a well-formed formula or not.

Definition of a well-formed formula (briefly, formula) of predicate logic:

• The expression Ft1t2...tn, where F is an arbitrary predicate letter (i.e. F can be “F”, “G”, “H”…) and t1, t2, ... tn are arbitrary constants or variables (not necessarily different), is a well-formed formula.
• The expressions ¬α, (α∧β), (α∨β), (α→β) and (α↔β), where α and β are well-formed formulas, are well-formed formulas.
• The expressions ∀xα and ∃xα, where x is an arbitrary variable and α is a well-formed formula, are well-formed formulas.
• Well-formed formulas are those and only those expressions that can be obtained by the above three rules.

Syntactic rule i. is related to the atomic formulas of predicate logic – the direct connections between a general term and singular terms (i.e. between a predicate letter and constants or variables). Atomic formulas correspond to atomic statements or open sentences in natural languages, such as the statement “Socrates is a teacher of Plato” (“Fab”) or the open sentence “Socrates is a teacher of x” (“Fax”).

Rule ii. contains all syntactic rules of the language of propositional logic. When (in 1.3 Truth Tables) we set out its syntax, there was a rule for each logical connective – a rule for negation, for conjunction, and so on. For the sake of brevity, here we unite them in a single rule. For example, based on ii., from the formula “Fax”, which in the example above corresponded to the open sentence “Socrates is a teacher of x”, we may construct the formula “¬Fax” (“Socrates is not a teacher of x”). According to the rule, when we form conjunctions, disjunctions, conditionals, or biconditionals, we must enclose them in parentheses (including when they are whole formulas, not parts of formulas). In 1.3 Truth tables we explained why this is so. For convenience, we do not write the parentheses surrounding a whole formula, but they are officially there. In addition, we use rectangular or curly brackets only informally, for easier reading; formally they are not part of the language.

Through syntactic rule iii., we can form statements from open sentences with the help of quantifiers. For example, from the formula “¬Fax” (which we obtained by the first two rules and which we informally imagine corresponding to the open sentence “Socrates is not a teacher of x”), based on iii. we may get the formula “∃x¬Fax”, which corresponds not to an open sentence, but to a statement: in the example “Socrates is not a teacher of someone” or “There is someone of whom Socrates is not a teacher”.

In 3.2 Variables and quantifiers, we introduced only informally the concepts of scope of a quantifier, free and bound variable, free and bound occurrence of a variable, open sentence and statement. Based on the syntactic rules, these concepts are defined formally and strictly.

If ∀xα (respectively ∃xα) is a well-formed formula and x is an arbitrary variable, then α is called the scope of ∀x (respectively of ∃x).

The same variable can occur more than once in a formula, so we are talking about different occurrences of the variable. (Quantifier variables, for example “x” in “∀x”, do not count as occurrences.) An occurrence of a variable is free in a formula if it is not part of the scope of a quantifier with the same variable in that formula. Otherwise (if it is part of the scope of a quantifier with the same variable) it is bound. An occurrence of a variable is bound by a quantifier if the quantifier has the same variable, the occurrence of the variable is in its scope and is free in it. The last condition is needed because an occurrence of a variable in the scope of a quantifier with the same variable will not be bound by it if it is already bound by another quantifier in the scope of the former quantifier. For example, the occurrence of “x” immediately after “F” in the formula “∀x(∃xFxGxa)” is in the scope of the universal quantifier “∀x” but it is not bound by it because it is already bound by the existential quantifier “∃x”, which is in the scope of the universal quantifier.

It is important to keep in mind that we talk of free or bound occurrences of a variable always with respect to a given formula. An occurrence of a variable can be bound in a formula and free in a formula that is a sub-formula of the first formula. For example, the occurrence of the variable “x” in “∃xyFxy” is bound, but its occurrence in the sub-formula “∀yFxy” of the same formula is free.

A variable (not an occurrence of a variable) is free in a formula if it has at least one free occurrence in it. For example, even though the first occurrence of “x” in the formula “∃xFxGxa” is bound, the variable is free in the formula because its second occurrence is free. Accordingly, a variable is bound in a formula if all its occurrences in the formula are bound.

If a formula has free variables, it is an open sentence. Otherwise it is a statement.

Rule iii. allows the existence of quantifiers that do not bind any variable. For example, applying iii. to “Fx”, we get the formula “∃xFx”, in which there are no free variables. Since “∃xFx” is a well-formed formula, based on iii. “∀xxFx” is also a well-formed formula. However, in that formula there is no free variable for the universal quantifier to bind. Although they seem strange, such expressions are considered well-formed so as not to complicate the syntactic rules. They are harmless because according to the semantics of predicate logic they are logically equivalent to the formulas obtained by removing the quantifiers in question. For example, “∀xxFx” is logically equivalent to “∃xFx”. So, we can simply disregard such quantifiers.

The syntactic rule iv. is more special because it mentions the other syntactic rules. It is a “meta-rule” according to which if an expression can be obtained by (repeated) applications of rules i.-iii., it is a formula of predicate logic, and that if it cannot be obtained in such a way, is not a formula of predicate logic. For example, “∀x((FxGx)∨Ga)” is a formula because of the following. Based on i., “Fx”, “Gx” and “Ga” are formulas. From there, applying ii. twice, we get that “((FxGx)∨Ga)” is a formula, from which on the basis of iii. it follows that “∀x((FxGx)∨Ga)” is also a formula. On the contrary, the expression “∀x(FxGxGa)” is not a formula of predicate logic because it is derived by iii. from “(FxGxGa)”. However, the latter expression cannot be obtained by ii., which is the rule related to logical connectives. This expression is ambiguous, as it is not clear whether it is a conditional between the atomic formula “Fx” and the disjunction “GxGa” or a disjunction between the conditional “FxGx” and the atomic formula “Ga”. By ii., from “Fx”, “Gx” and “Ga” we can get “(Fx→(GxGa))” or “((FxGx)∨Ga)”, not “(FxGxGa)”.

The well-formed formulas of predicate logic are interpreted with respect to a domain of objects called universe of discourse, which we denote by “D”.

To interpret a formula as a sentence (a statement or an open sentence) from the natural language, we need to interpret the predicate letters and the constants in it. The interpretation of a constant consists in determining the object in D it denotes. For example, if D is the set of humans (existed and existing), we can interpret the constant “a” so that, in effect, it has the meaning of the proper name “Socrates” by determining that it denotes (refers to) the person Socrates.

Different constants may denote the same thing. Constants are the equivalent of proper names (more generally, of singular terms) in natural languages, in which it is not uncommon for something to have different names. For example, the proper names “Everest” and “Chomolungma” denote the highest peak on Earth. Similarly, in the language of predicate logic, this peak could be denoted simultaneously by different constants – for example by “a” and “b”.

As for the interpretation of the predicate letters, when we interpret such a letter as a one-place predicate, the interpretation consists in determining which things in the universe of discourse D the predicate letter is true of2. When we interpret it as a two-place predicate, the interpretation consists in determining which ordered pairs of things in D it is true of; when we interpret it as a three-place predicate – which ordered triples it is true of, etc. For example, if D is the set of humans and we want to interpret the predicate letter “F” as the one-place predicate “…is a philosopher”, we will declare that “F” is true of each philosopher and false of every other human. If we want to interpret it as the two-place predicate “…is the teacher of…”, we will declare that “F” is true of those and only of those ordered pairs of humans such that the first is a teacher of the second. Then “F” will be true, for example, of the pair (Socrates, Plato), as Socrates is a teacher of Plato, and false, for example, of the pairs (Plato, Socrates) and (Aristotle, Socrates), as neither Plato nor Aristotle are teachers of Socrates. If we want to interpret “F” as the three-place predicate “…is a daughter of…and…”, we will declare that “F” is true of those and only of those ordered triples of people (m, n, l) such that m is a daughter of n and l.

So, by interpretation of one or more formulas in a given universe of discourse D we will understand: 1) for each of the constants participating in the formulas to determine what they denote in D and 2) for each of the predicate letters participating in the formulas to determine what things (or ordered pairs of things, or ordered triples of things, etc.) in D they are true of.

Specifying a universe of discourse D and an interpretation I with respect to a formula or a set of formulas that do not have free variables (i.e. that represent statements) automatically determines their truth values. The combination (the ordered pair) of a universe of discourse and an interpretation (D, I) is called a structure. Predicate logic’s formulas are always true or false with respect to a structure. Structures in the semantics of predicate logic are the equivalent of truth table rows in the semantics of propositional logic. However, while a truth table always has a finite number of rows, the possible structures for a formula are always infinitely many. When a formula or a set of formulas is true in a structure, the structure is said to be a model of the formula (formulas).

If a formula has free variables (i.e. if it represents an open sentence rather than a statement), it will have a truth value in a structure (D, I) only if each free variable in it is associated with (takes as a value) a certain thing in D. We will call such associations of the free variables in a formula or a set of formulas with objects in D an assignment. So, by adding to a structure an assignment, not only formulas representing statements but also formulas representing open sentences become true or false in that structure.

Let us note that when we fix a universe of discourse, interpretation and (possibly) an assignment of values to the free variables, the formulas are not related to sentences of the natural language (as their translations); they are related to a certain reality (that of the universe of discourse). They become true or false by relating them to that reality, not by relating them to another language.

Once we have the concepts of structure, universe of discourse, interpretation and assignment, we proceed to the formulation of the semantic rules of predicate logic. They are as follows.

For each structure (D, I) and each assignment of values to the free variables (if any), we have the following:

• Let F be an arbitrary predicate letter and t1, t2, ... tn arbitrary constants or variables (possibly mixed and not necessarily different). Then the formula Ft1t1...tn is true if and only if the ordered n-tuple of objects in D (the object if n = 1) that the interpretation I or the assignment relate to t1, t2, ... tn is an element of the set of ordered n-tuples that I relates to F.
• If α and β are arbitrary formulas, then ¬α is true if and only if α is not true; (α∧β) is true if and only if α and β are true; (α∨β) is true if and only if α or β (or both) are true; (α→β) is true if and only if α is not true or β is true; (α↔β) is true if and only if α and β are both true or both not true.
• If x is an arbitrary variable and α is an arbitrary formula, then ∀xα is true if and only if α is true for every value of x in D; ∃xα is true if and only if α is true for at least one value of x in D.

Each of the semantic rules corresponds to one of the syntactic ones. In this way, more complex expressions obtain their truth conditions through the truth conditions of the simpler expressions that are parts of them.

Rule I. applies to atomic formulas. If such a formula contains variables, they are necessarily free, since it does not contain quantifiers. The formula represents an open sentence and is true or false in a structure only for certain assignments of values to the variables. For example, let the universe of discourse D be the set of humans and the interpretation I be such that the predicate letter “F” relates to the set of ordered pairs in which the first element is a teacher of the second. In addition, let the constant “a” be related by I to Socrates (the human, not the name). Then the atomic formula “Fax” will be true in the structure (D, I) if the assignment gives to “x” as a value, say, Plato (the human, not the name) and will be false in (D, I) if the assignment gives to “x” as a value, say, Aristotle. Atomic formulas that do not contain variables (that contain only constants) are statements and do not need an assignment in order to be true or false in a structure. For example, if in the above structure I relates the constant “b” to Plato, the atomic formula “Fab” will correspond to the fact that Socrates is a teacher of Plato and will be true in (D, I) without reference to any assignment. Thus, based on the semantic rule I., each atomic formula becomes either true of false in each structure for each assignment of values to the free variables (if any).

Rule II. determines the truth conditions of the logical connectives. The rule includes all semantic rules of propositional logic (a total of five – one for each logical connective). These rules could be reduced to two – one for negation and one for either conjunction, disjunction or conditional, because the rest of the logical connectives can be defined by the two chosen ones. The defined connectives would receive the same truth conditions as a consequence of the truth conditions of the connectives through which they are defined. However, to define the rest by two of the logical connectives would be a change in the syntax, because then the expressions in which the defined connectives occur would not be well-formed formulas, but abbreviations (through the definitions) of well-formed formulas constructed only by the two selected connectives. Here is a possible way to defines disjunction, conditional and biconditional through negation and conjunction:

 α∨β =def. ¬(¬α∧¬β) α→β =def. ¬(α∧¬β) α↔β =def. (α→β)∧(β→α)

In the biconditional definition, we use that conditional is already defined in terms of conjunction and negation. By truth tables or truth-value analysis, it can be verified that the expressions on the two sides of the definition sign “=def.” are logically equivalent and therefore have the same meaning. The possibility to use definitions and thereby reduce the number of semantic rules was only a digression – we have chosen not to define connectives by other connectives and therefore we have given a semantic rule for each of them.

Based on the semantic rule II., all compound well-formed formulas of the type ¬α, α∧β, α∨β, α→β and α↔β (i.e. formulas having the form of negation, conjunction, disjunction, conditional or biconditional) become true or false in each structure (D, I) (for some assignment of values to the free variables in them, if any), provided that α and β are already true or false in that structure. In the structure we used as an example above, the formula “Fab” was interpreted as equivalent to the statement “Socrates is a teacher of Plato” and accordingly is true in it. If, moreover, the interpretation I of the same structure relates the predicate letter “G” to the beautiful humans in D, then the atomic formula “Ga” will have the same meaning as the statement “Socrates is beautiful” and will be false in that structure. Based on rule II., then the formula “Fab∧¬Ga” will be true in the structure. The truth conditions that rule II. gives to negation and conjunction make this formula equivalent to the statement “Socrates is a teacher of Plato and is not beautiful”.

Rule III. gives truth conditions to the universal and existential statements or open sentences, i.e. to the formulas whose main logical operator is a quantifier. Consider a structure having as a universe of discourse the set of natural numbers {0, 1, 2, ...}, whose interpretation relates the predicate letter “F” to the infinite set of all ordered pairs of natural numbers in which the first element is greater than the second (thus “F” corresponds to the predicate “…is greater than…”). In addition, let the constant “a” be interpreted in the structure as denoting the number 7. Then the formula “Fxa” will have the same meaning as the open sentence “x is greater than 7”. There is at least one value of “x” for which this open sentence is true because there is at least one number (infinitely many actually) that is greater than 7. Therefore, as “Fxa” is true for at least one value of “x”, by III. “∃xFxa” will be true in this structure. The truth conditions that III. gives to “∃xFxa” make it equivalent to the statement “There is a number greater than 7”. As a second example, consider the formula “∀xFxy” in the same structure. It has a free variable, so it is not a statement but an open sentence and is true or false in the structure only with respect to some assignments of values to the free variable “y”. Consider an assignment that gives as a value to “y” the number 0. By III., “∀xFxy” will be true for this value of “y” if and only the formula “Fxy” is true for each value of “x” (for the same value of “y”). By rule I., this means that “∀xFxy” will be true if and only if every natural number is greater than 0. The latter condition is not satisfied, however, because there is a natural number that is not greater than 0 – the number 0 itself. Therefore, “∀xFxy” is false in that structure under that assignment.

To each syntactic rule corresponds a semantic one. Since each well-formed formula is obtained by successive applications of syntactic rules, by the corresponding semantic rules each formula receives a truth value. The simplest subformulas of a formula are the atomic formulas. They get truth values by rule I. Each subsequent, more complex subformula is formed from simpler ones by a logical connective or a quantifier, so by rule II. or III. it also receives a truth value. In this way, finally the whole formula receives a truth value. All this makes it possible to prove (strictly, by induction) that on the basis of the semantic rules every formula of predicate logic is true or false in every structure for every assignment of values to its free variables (if any); and that in no structure under no assignment it is both true and false.

The concepts of logical inference, logical equivalence, logical validity, consistency and contradiction are defined in terms of the concept of truth in a structure. As we know, these most important logical concepts are related to forms of sentences, not to their contents (to what they are talking about). Therefore, the concepts are not dependent on specific universes of discourse and interpretations (structures). The result is that the definitions refer to all structures. Moreover, the definitions given below are valid for all formulas, not just for statements (formulas without free variables). If we limit ourselves only to statements (ignoring open sentences), assignments of values to free variables will be irrelevant, as there will be no such in the considered formulas. In fact, each predicate can be regarded as an open sentence, so applying the definitions also to formulas with free variables, we apply the concepts of logical inference, logical equivalence, contradiction, etc. also to terms (to parts of sentences), not only to statements.

Logical inference: A formula α is a logical consequence of a set of formulas Δ if and only if, when all formulas in Δ are true in some structure (for some assignment of values to the free variables, if any), then α is also true in that structure (for the assignment); i.e. when each model of Δ is also a model of α.

Accordingly, if the premises and the conclusion of a natural language argument are symbolized by formulas between which there is a logical inference in the sense of the above definition, then this argument is logically valid.

Logical equivalence: Two formulas are logically equivalent if and only if they are true in the same structures (for the same assignments of values to the free variables, if any); i.e. if their models are the same.

Two expressions (statements or open sentences) from a natural language are logically equivalent if they can be symbolized by logically equivalent formulas.

Logical validity: A formula is logically valid if and only if it is true in each structure (for each assignment of values to the free variables, if any); i.e. if each structure is its model.

Accordingly, an expression from a natural language (a statement or open sentence) is logically valid when it can be symbolized by a logically valid formula.

The concept of logical validity in predicate logic is the analogue of the concept of tautology in propositional logic. In the semantics of predicate logic, structures (combinations of universes of discourse, interpretations, and possibly assignments) are the analogue of the truth table rows in the semantics of propositional logic. However, the concept of logical validity is broader than that of tautology. All tautologies are logically valid, but not all logically valid formulas are tautologies. For example, the formulas “Fax ∨ ¬Fax” and “∃xGxb → ∃xGxb” are tautologies because they have the form “p∨¬p” and “pp”, respectively. As such, they cannot be false in any structure (for any assignment), so they are logically valid. But, for example, the formula “∀xFxFa” is logically valid without being a tautology (in propositional logic it corresponds to “pq”). The formula is true in each structure because it tells us that if everything is F, then a is F. Regardless of the structure, if everything in its universe of discourse falls under “F”, then the thing a (which is an element of the discourse universe) will also fall under “F”.

In propositional logic, we had a decision procedure, through which we could always check whether a given inference scheme is logically valid or whether two formulas are logically equivalent (see 1.6 Logical inference and logical equivalence). It was based on the following two connections between the concepts of logical inference and logical equivalence, on the one hand, and the concept of tautology:

 The formula β is a logical consequence of the formulas α1, α2, … αn if and only if the formula (α1 ∧ α2 ∧ … ∧ αn) → β is a tautology. The formulas α and β are logically equivalent if and only if the formula α ↔ β is a tautology.

These two principles could be used as definitions of the concepts of logical inference and logical equivalence in terms of the concept of tautology in propositional logic. To the concept of tautology, in predicate logic corresponds the broader concept of logical validity. Accordingly, logical inference and logical equivalence could be defined in the same way by replacing “tautology” with “logically valid”.

Contradiction: A formula is a contradiction if and only if it is false in each structure (for each assignment of values to the free variables, if any); i.e. if it does not have models.

Consistency: A formula is consistent if it is not a contradiction. In other words, if and only if it is true in at least one structure (for at least one assignment of values to the free variables, if any); i.e. if it has at least one model.

A statement or an open sentence from a natural language is a contradiction if it can be symbolized by a contradictory formula; and it is consistent if it can be symbolized by a consistent formula.

In propositional logic, we had a general decision procedure through which we could always check whether a given inference scheme or equivalence scheme is logically valid. For this purpose, we checked (for example through a truth table or truth-value analysis) whether a certain formula is a tautology. If we had such a decision procedure for determining whether an arbitrary predicate logic formula is logically valid, in the same way we could always check whether a given inference scheme or equivalence scheme of predicate logic is logically valid. However, such a decision procedure cannot be formulated. This has been proven independently by Turing (Turing, 1936) and Church (Church, 1936). On the other hand, however, shortly before them, Gödel proved that there are proof procedures by which any logically valid formula of predicate logic can be proved to be such (Gödel, 1930). Such proof procedures are called complete.3 Together, the two results mean that if a statement logically follows from a theory (i.e. a set of statements), then there is a proof of this fact (so to speak, in the mind of God), which, however, we may never find. Decision procedures (algorithms) are more than proof procedures because they guarantee that if the truth of a statement can be proved within a theory, then, if we want to (and have time4), we will find at least one such proof.

Historically, the semantics of predicate logic originated in a study by Tarski, published in the 1930s in Polish, which explored the possibility of a strict definition of the concept of truth in relation to the formal language of logic (Tarski, 1956).

1. For recursive definitions, see also 1.3 Truth tables. 2. In 3.1 General and singular terms, we saw that it is essential for predicates (general terms) to be true or false of things (when they are one-place predicates), or of ordered pairs of things (when they are two-place predicates), or of ordered triples of things (when they are three-place predicates), … etc. 3. In the next section, we will introduce such a procedure. 4. Modern methods of cryptography (for example, those used in cryptocurrencies) are such that there are obvious recipes (algorithms) for decrypting the encrypted information. However, cryptographers have made sure that the time to apply such an algorithm (using the most powerful modern computers) is, say, greater than the age of the universe.