Predicate logic

For the specific term, see First-order logic.

In mathematical logic, predicate logic is the generic term for symbolic formal systems like first-order logic, second-order logic, many-sorted logic, or infinitary logic. This formal system is distinguished from other systems in that its formulae contain variables which can be quantified. Two common quantifiers are the existential ∃ ("there exists") and universal ∀ ("for all") quantifiers. The variables could be elements in the universe under discussion, 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". The foundations of predicate logic were developed independently by Gottlob Frege and Charles Peirce.

In informal usage, the term "predicate logic" occasionally refers to first-order 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, Saul Kripke, Barcan Marcus formulae, A. N. Prior, and Nicholas Rescher.

Syntax

Predicate calculus symbols may represent variables, constants, functions or predicates.

1. Constants name specific objects or properties in the domain of discourse. Thus George, tree, tall and blue are examples of well formed constant symbols. The constants $\top$ (true) and $\bot$ (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 (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 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, these logics can be viewed as automata just as well.

How it all fits together

General idea

There are functions of N variables that return a boolean value. The types of the variables can differ. The functions are called predicates.

An example:

Eats(the_one_who_digests,food_item)

As the predicates are functions that return boolean values, they can be combined with each-other by the means of propositional logic. An example:

Eats(the_one_who_digests,food_item) AND GoesToHell(politician)

A function that is constructed by combining predicates by the means of propositional logic is itself a predicate, because it takes in N variables and always returns a boolean value. An example:

JustAnotherPredicate(the_one_who_digests,food_item,politician):=

:=Eats(the_one_who_digests,food_item) AND GoesToHell(politician)

The "standard" predicates

There are two, "standard" predicates, i.e. functions that take something in and return a boolean value.

One of them is the ForAll(x,y), where y is a predicate and x is one of y's arguments.

The other one is the ExistsAtLeastOne(x,y), where y is a predicate and x is one of y's arguments.

Like all predicates as functions that return boolean values, the two standard functions can be combined by using propositional logic. An example:

ExistsAtLeastOne(alien,HaveAThreesome(alien,a,b)) OR ForAll(politician,IsLying(politician))

As the standard functions accept other predicates as its arguments, they can be

"fed to eachother" in various ways. An example:

ExistsAtLeastOne(alien,ForAll(alien,ThisIsAlsoAPredicate(alien,politician,apples,oranges))

The "standard" predicates have a "standard" notation:

ForAll(x,y) is written as ∀ x y or as ∀x(y)

ExistsAtLeastOne(x,y) is written as ∃ x y or as ∃x(y)

Sometimes some mathematicians also use a third "standard function",

the ExistsExactlyOne(x,y), where y is a predicate and x is one of y's arguments. The ExistsExactlyOne(x,y) has a standard notations of ∃!x y and ∃!x(y).

See also

• First-order logic
• Propositional logic

References

• A. G. Hamilton 1978, Logic for Mathematicians, Cambridge University Press, Cambridge UK ISBN 0-521-21838-1.
• Abram Aronovic Stolyar 1970, Introduction to Elementary Mathematical Logic, Dover Publications, Inc. NY. ISBN 0-486-64561
• George F Luger, Artificial Intelligence, Pearson Education, ISBN 978-81-317-2327-2
• "Predicate calculus", Encyclopedia of Mathematics, EMS Press, 2001 [1994]