predicate logic

a branch of mathematical logic that studies the laws of logic common for any domain of objects (containing at least one object) with predicates (that is, properties and relations) stipulated for these objects. As a result of formalization, predicate logic takes the form of different calculi. The simplest logical calculi are propositional calculi. The laws of logic that specify the connections of the objects under study to the relations between such objects are described in the more complex predicate calculi.

The classical predicate calculus makes use of the following signs: (1) individual variables—the letters x, y, z, . . ., which are treated intuitively as indefinite names of the objects; (2) predicate variables—complexes of signs of the form P^m, Qⁿ, Rl, …(m, n, and l are natural numbers), with Qⁿ, for example, denoting an arbitrary n-place relation between the objects; (3) signs for the logical connectives, such as & (conjunction), V (disjunction), ⊃ (implication), and ℸ (negation), which denote, respectively, “and,” “or,” “if…then . . .,” and “it is false that…“; (4) signs for the quantifiers V (universal quantifier) and 3 (existential quantifier), which denote “for all …” and “there is a …such that. . .,” respectively; and (5) the comma and parentheses to indicate more precisely the structure of formulas.

If Qⁿ is an n-place predicate variable and x₁, . . ., x_n are the individual variables, then the expression Qⁿ (X₁, . . ., x_n) is, by definition, an atomic (elementary) formula. The superscript η in the predicate variable is usually omitted in the atomic formula. The formula Q(x₁, . . ., x_n) intuitively denotes the proposition asserting that the objects x₁, . . ., x_n are connected by the relation Q. Atomic formulas are considered to be formulas, as are expressions that can be obtained from them by means of the following operations for the formation of new formulas from those already obtained: (1) if φ and ψ are formulas, then (φ & ψ), (φ V ψ), (φ ⊃ ψ), and ℸ φ are also formulas; (2) if φ is a formula and x is an individual variable, then ∀ x φ and ∃ x φ are formulas. The description of the language of the predicate calculus ends with the definition of a formula.

The occurrence of an individual variable x in a formula φ is said to be bound if x occurs in a part of φ of the form ∃ xψ or ∀ xψ or if x immediately follows the quantifier sign. Any occurrence of a variable that is not bound in a formula is said to be free. If there is at least one free occurrence of x in φ, then the variable x is free in φ or is a parameter of φ. Intuitively, a formula with parameters expresses some condition that can be converted into a concrete proposition if (the domain of objects having first been concretely specified) definite values are assigned to the parameters and predicate letters in the formula. The bound variables, on the other hand, do not have an independent meaning and serve (with the corresponding quantifiers) to denote universal assertions or assertions of existence. If φ is a formula and x and y are the individual variables, then we denote by φ (x I y) the result of replacing all free occurrences of x in φ by y. (If, in this case, y turns up in the place of x in a part of the formula ∀ yψ or ∃ yψ, then all the bound occurrences of y in this part must be additionally replaced by a variable not in φ. This is done so that the meaning of φ is not distorted when x is replaced by y.)

Let φ, ψ, and η be arbitrary formulas and x and y individual variables. Then the following types of formulas are taken as the axioms of the classical predicate calculus:

(1) (φ ⊃ (ψ ⊃ η))

(2) ((φ ⊃ (ψ ⊃ η)) ⊃ ((φ ⊃ ψ) ⊃ (φ ⊃ η)))

(3) ((φ & ψ) ⊃ φ)

(4) ((φ & ψ) ⊃ ψ)

(5) (φ ⊃ (ψ ⊃ (φ & ψ)))

(6) ((φ ⊃ η) ⊃ ((ψ ⊃ η) ⊃ ((φ V ψ) ⊃ η)))

(7) (φ ⊃ (φ V ψ))

(8) (ψ ⊃ (φ V ψ))

(9) (ד φ ⊃ (φ ⊃ ψ))

(10) ((φ ⊃ ψ) ⊃ ((φ ⊃ ד ψ) ⊃ ד φ))

(11) (φ V ד φ)

(12) (∀ xφ ⊃ φ(x ǀ y))

(13) (φ(x ǀ y) ⊃ ∃ xφ)

Three rules of inference are used in the predicate calculus: the rule of modus ponens (1) and two rules of inference governing quantifiers (2) and (3).

(1) From the formula φ and (φ ⊃ ψ) we can infer the formula ψ.

(2) From the formula (φ ⊃ ψ), where φ does not contain a free variable x, we can infer (φ ⊃ ∀x ψ).

(3) From the formula (φ ⊃ ψ), where ψ does not contain a free variable x, we can infer (∃ x φ ⊃ ψ).

Unlike other formulations of the calculus, the φ, ψ, and η here do not belong to the language of the calculus under consideration but designate its arbitrary formulas. Thus, each of the notations (1)-(13) is an axiom schema that “generates” an actual axiom through the substitution of some concrete axiom for the Greek letters; special rules of substitution are not required in this formulation.

The intuitionistic predicate calculus differs from the classical predicate calculus only in that the law of excluded middle (axiom 11) is omitted from the axioms. The difference between the two calculi reflects the difference in their interpretations. The interpretation of the logical connectives &, V, ⊃, and ℸ in the predicate calculi are the same as in the corresponding propositional calculi. As for the interpretation of the quantifiers, the classical predicate calculus treats them from the standpoint of actual infinity. More precisely, every formula has the value of either “truth” or “falsity” if a model of the predicate calculus is defined, that is, if a set of objects is defined and some relation on this set is assigned to each predicate letter of the formula and certain objects are assigned as values to all the parameters of the formula. A formula is universally valid in a classical sense if it takes the value “true” in any model. As was shown by K. Godei, all and only universally valid formulas in the classical sense are derivable in the classical predicate calculus. This theorem by Godel also constitutes an exact statement of the idea of the formalization of logic: all the laws of logic common for all models are derived in the classical predicate calculus.

In the intuitionistic interpretation, on the other hand, the assertion that some formula is true requires a mathematical construction. For example, ∀ x ∃yφ is true from the intuitionistic standpoint only if there exists a general method that allows us to find the corresponding y for a given x. The truth of ∀_x (φVℸφ) assumes the existence of a method for determining which term of the disjunction (φVℸφ) is true for every value of the parameter x. For example, formulas that are universally valid in the classical sense and express the law of excluded middle (φ νℸφ) or the principle of passing negation through universality (φ∀ x φ ∃x ⊃ ℸφ) are not intuitionistically valid (the theory of models, however, is also being developed for the intuitionistic predicate calculus).

Predicate logic is the usual basis for constructing logical calculi intended for describing various disciplines (applied calculi). The language of the predicate calculus is “concretized” for this purpose: predicate symbols and signs of operation expressing the specific relations and operations of a particular discipline are added to them. For example, if we wish to describe the true propositions of the arithmetic of natural numbers, we may add the operations of addition, multiplication, the divisibility relation, and others. Axioms expressing the specific laws of the subject under study (applied or specific axioms) are then introduced into the calculus to complement the axioms and rules of inference of the predicate calculus (logical postulates). A formal arithmetic is thus constructed.

There are other logical systems in addition to the classical and intuitionistic predicate calculi that describe the laws of logic that can be expressed by other logical means or from other methodological standpoints. These include the calculi of modal logic, probability logic, and inductive logic.

REFERENCE