predicate logic

Also found in: Dictionary, Thesaurus, Acronyms, Wikipedia.
Related to predicate logic: propositional logic

predicate logic

(Or "predicate calculus") An extension of propositional logic with separate symbols for predicates, subjects, and quantifiers.

For example, where propositional logic might assign a single symbol P to the proposition "All men are mortal", predicate logic can define the predicate M(x) which asserts that the subject, x, is mortal and bind x with the universal quantifier ("For all"):

All x . M(x)

Higher-order predicate logic allows predicates to be the subjects of other predicates.

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 Pm, Qn, Rl, …(m, n, and l are natural numbers), with Qn, 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 Qn is an n-place predicate variable and x1, . . ., xn are the individual variables, then the expression Qn (X1, . . ., xn) is, by definition, an atomic (elementary) formula. The superscript η in the predicate variable is usually omitted in the atomic formula. The formula Q(x1, . . ., xn) intuitively denotes the proposition asserting that the objects x1, . . ., xn 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 ǀ y))

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

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.


Kleene, S. C. Vvedenie ν metamatematiku. Moscow, 1957. (Translated from English.)
References in periodicals archive ?
GOLEM generates knowledge in the form of logical rules which one can model in a language like first-order predicate logic.
n], [Chi] are arbitrary predicate logic formulae (i.
The extension of predicate logic outlined very sketchily in the present section offers a direct formalization of what Gauker calls a neutral perspective on the T&S example, since it replaces truth simpliciter by two different notions of truth, one of which depends on the speaker and the other on the hearer.
42) On first-order predicate logic and the subject-predicate structure, see SB, 193-95.
But if students familiar with the modern propositional logic and first-order predicate logic with identity wish to grapple with Frege's ideas, Kanterian's Frege: A Guide for the Perplexed is an excellent introduction.
I was particularly taken by his insistence that the remarks about facts at the beginning of the Tractatus are 'meant to be read in a way that is as vacuous as possible' (26), his explanation of Wittgenstein's argument that picturing the world presupposes the existence of simple objects (38-44), his discussion of the requirement that sense be determinate (54-60), his examination of the all-important Tractarian idea of propositions as pictures (68-74), his survey of Wittgenstein's remarks about generating all (meaningful) propositions from elementary propositions by means of a single truth-operator (83-98), and his analysis of how Wittgenstein's view of logical truth does--and does not--fall foul of the undecidability of predicate logic (106-08).
Predicate logic as a language for parallel programming.
In this book, his chief aim is to show that the arguments can all be presented in logically valid form, according to the canons of first order predicate logic.
During this period the idea of programming in predicate logic was born.
Puntel finds here an alternative to the materialist ontology that analytic philosophers take for granted when translating everyday speech into first-order predicate logic, using an existential quantifier that carries illegitimate ontological baggage: there is no "x" apart from the facts themselves.
This is not to suggest that Frege's introduction of predicate logic with quantifiers, formulation of the context principle, and account of the distinction between sense and reference are not fundamental insights presupposed by the kind of theory of meaning Dummett envisages as forming the foundation of philosophy.