Predicate logic
Encyclopedia
In mathematical logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...

, predicate logic is the generic term for symbolic formal system
Formal system
In formal logic, a formal system consists of a formal language and a set of inference rules, used to derive an expression from one or more other premises that are antecedently supposed or derived . The axioms and rules may be called a deductive apparatus...

s like first-order logic
First-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...

, second-order logic
Second-order logic
In logic and mathematics second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory....

, many-sorted logic
Many-sorted logic
Many-sorted logic can reflect formally our intention, not to handle the universe as a homogeneous collection of objects, but to partition it in a way that is similar to types in typeful programming...

or infinitary logic
Infinitary logic
An infinitary logic is a logic that allows infinitely long statements and/or infinitely long proofs. Some infinitary logics may have different properties from those of standard first-order logic. In particular, infinitary logics may fail to be compact or complete. Notions of compactness and...

. This formal system is distinguished from other systems in that its formulae contain variables which can be quantified
Quantification
Quantification has several distinct senses. In mathematics and empirical science, it is the act of counting and measuring that maps human sense observations and experiences into members of some set of numbers. Quantification in this sense is fundamental to the scientific method.In logic,...

. Two common quantifiers are the existential
Existential quantification
In predicate logic, an existential quantification is the predication of a property or relation to at least one member of the domain. It is denoted by the logical operator symbol ∃ , which is called the existential quantifier...

∃ ("there exists") and universal
Universal quantification
In predicate logic, universal quantification formalizes the notion that something is true for everything, or every relevant thing....

∀ ("for all") quantifiers. The variables could be elements in the universe under discussion
Domain of discourse
In the formal sciences, the domain of discourse, also called the universe of discourse , is the set of entities over which certain variables of interest in some formal treatment may range...

, or perhaps relations or functions over that universe. For instance, an existential quantifier over a function symbol would be interpreted as modifier "there is a function".

In informal usage, the term "predicate logic" occasionally refers to first-order logic
First-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...

. Some authors consider the predicate calculus to be an axiomatized form of predicate logic, and the predicate logic to be derived from an informal, more intuitive development.

Predicate logics also include logics mixing modal operators and quantifiers. See Modal logic
Modal logic
Modal logic is a type of formal logic that extends classical propositional and predicate logic to include operators expressing modality. Modals — words that express modalities — qualify a statement. For example, the statement "John is happy" might be qualified by saying that John is...

, Saul Kripke
Saul Kripke
Saul Aaron Kripke is an American philosopher and logician. He is a professor emeritus at Princeton and teaches as a Distinguished Professor of Philosophy at the CUNY Graduate Center...

, Barcan Marcus
Ruth Barcan Marcus
Ruth Barcan Marcus is the American philosopher and logician after whom the Barcan formula is named. She is a pioneering figure in the quantification of modal logic and the theory of direct reference...

formulae, A. N. Prior and Nicholas Rescher
Nicholas Rescher
Nicholas Rescher is an American philosopher at the University of Pittsburgh. In a productive research career extending over six decades, Rescher has established himself as a systematic philosopher of the old style and author of a system of pragmatic idealism which weaves together threads of...

.

## Syntax

Predicate calculus symbols may represent either variables, constants, functions or predicates.
1. Constants name specific objects or properties in the domain of discourse
Domain of discourse
In the formal sciences, the domain of discourse, also called the universe of discourse , is the set of entities over which certain variables of interest in some formal treatment may range...

. Thus George, tree, tall and blue are examples of well formed constant symbols. The constants (true) and (false) are sometimes included.
2. Variable symbols are used to designate general classes or objects or properties in the domain of discourse.
3. Functions denote a mapping of one or more elements in a set(called the domain of the function) into a unique element of another set(the range of the function). Elements of the domain and range are objects in the world of discourse. Every function symbol has an associated arity, indicating the number of elements in the domain mapped onto each element of range.

A function expression is a function symbol followed by its arguments. The arguments are elements from the domain of the function; the number of arguments is equal to the arity of the function. The arguments are enclosed in parentheses and separated by commas. e.g.:
• f(X,Y)
• father(david)
• price(apple)

are all well-formed function expressions.

Predicate logics may be viewed syntactically as Chomsky
Noam Chomsky
Avram Noam Chomsky is an American linguist, philosopher, cognitive scientist, and activist. He is an Institute Professor and Professor in the Department of Linguistics & Philosophy at MIT, where he has worked for over 50 years. Chomsky has been described as the "father of modern linguistics" and...

grammars. As such, predicate logics (as well as modal logics and mixed modal predicate logics) may be viewed as context-sensitive, or more typically as context-free, grammars. As each one of the four Chomsky-type grammars have equivalent automata
Automata theory
In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...

, these logics can be viewed as automata just as well.