Predicate (mathematical logic)
In mathematical logic, a predicate is the formalization of the mathematical concept of statement. A statement is commonly understood as an assertion that may be true or false, depending on the values of the variables that occur in it. A predicate is a well-formed formula that can be evaluated to true or false in function of the values of the variables that occur in it. It can thus be considered as a Boolean-valued function.
A predicate consists of atomic formulas connected with logical connectives. An atomic formula is a well-formed formula of some mathematical theory. The main logical connectives are negation (not or ¬), logical conjunction (and or ∧), logical disjunction (or or ∨), existential quantification (∃) and universal quantification (∀); the predicates always true (denoted true or ⊤) and always false (denoted false or ⊥) are commonly considered also as logical connectives.
A predicate that does not contain any quantifier (∃ or ∀), is called a propositional formula. A predicate whose all quantifiers apply to individual elements, and not to sets or predicates is called a first-order predicate.
Simplified overview
Informally, a predicate, often denoted by capital roman letters such as , and ,[1] is a statement that may be true or false depending on the values of its variables.[2] It can be thought of as an operator or function, that returns a value that is either true or false depending on its input.[3][4] For example, predicates are sometimes used to indicate set membership: when talking about sets, it is sometimes inconvenient or impossible to describe a set by listing all of its elements. Thus, a predicate P(x) will be true or false, depending on whether x belongs to a set or not.
A predicate can be a proposition if the placeholder x is defined by domain or selection.
Predicates are also commonly used to talk about the properties of objects, by defining the set of all objects that have some property in common. For example, when P is a predicate on X, one might sometimes say P is a property of X. Similarly, the notation P(x) is used to denote a sentence or statement P concerning the variable object x. The set defined by P(x), also called the extension[5] of P, is written as {x | P(x)}, and is the set of objects for which P is true.
For instance, {x | x is a positive integer less than 4} is the set {1,2,3}.
If t is an element of the set {x | P(x)}, then the statement P(t) is true.
Here, P(x) is referred to as the predicate, and x the placeholder of the proposition. Sometimes, P(x) is also called a (template in the role of) propositional function, as each choice of the placeholder x produces a proposition.
A simple form of predicate is a Boolean expression, in which case the inputs to the expression are themselves Boolean values, combined using Boolean operations. Similarly, a Boolean expression with inputs predicates is itself a more complex predicate.
Formal definition
The precise semantic interpretation of an atomic formula and an atomic sentence will vary from theory to theory.
- In propositional logic, atomic formulas are called propositional variables.[6] In a sense, these are nullary (i.e. 0-arity) predicates.
- In first-order logic, an atomic formula consists of a predicate symbol applied to an appropriate number of terms.
- In set theory, predicates are understood to be characteristic functions or set indicator functions(i.e., functions from a set element to a truth value). Set-builder notation makes use of predicates to define sets.
- In autoepistemic logic, which rejects the law of excluded middle, predicates may be true, false, or simply unknown. In particular, a given collection of facts may be insufficient to determine the truth or falsehood of a predicate.
- In fuzzy logic, predicates are the characteristic functions of a probability distribution. That is, the strict true/false valuation of the predicate is replaced by a quantity interpreted as the degree of truth.
See also
References
- "Comprehensive List of Logic Symbols". Math Vault. 2020-04-06. Retrieved 2020-08-20.
- Cunningham, Daniel W. (2012). A Logical Introduction to Proof. New York: Springer. p. 29. ISBN 9781461436317.
- Haas, Guy M. "What If? (Predicates)". Introduction to Computer Programming. Berkeley Foundation for Opportunities in IT (BFOIT). Archived from the original on 13 August 2016. Retrieved 20 July 2013.
- "Mathematics | Predicates and Quantifiers | Set 1". GeeksforGeeks. 2015-06-24. Retrieved 2020-08-20.
- "Predicate Logic | Brilliant Math & Science Wiki". brilliant.org. Retrieved 2020-08-20.
- Lavrov, Igor Andreevich; Maksimova, Larisa (2003). Problems in Set Theory, Mathematical Logic, and the Theory of Algorithms. New York: Springer. p. 52. ISBN 0306477122.