Predicate logic
First order predicate logic
Introduction and syntax
Predicate logic is an extension of propositional logic. Here we consider what is called first-order predicate logic, abbreviated FOL (sometimes abbreviated PL1, not to be confused with the programming language PL/I). Predicate logic (FOL) allows us to make statements about some given domain of discourse.
Since this is an extension of propositional logic, there are many common elements, including the use of negation and logical connectives. As with propositional logic, well-formed formulas (WFFs) are defined inductively. Well-formed formulas and construction from terms, predicates, and connectives, as well as quantifiers.
This extension allows us to make or reason about statements like:
- All featherless bipeds are human.
- Some cars are blue.
- If a person lives in Vermont then they know alot about cows.
(We won’t worry about the truth or falsity of these right now.)
Terms are formal expressions denoting elements of the domain of discourse. Terms are defined inductively, and they include variables and function symbols. We can use functions to construct more complex terms, where the arguments to the functions are terms, for example f(x, y), or s(s(0)). Drawing examples from arithmetic, + and \times are function symbols. These are used to produce new terms. For example,
\begin{gather*} +(x, y) \equiv x + y \equiv z\text{, such that }z = x + y \end{gather*}
Note that writing with an infix operator is just syntactic sugar for +(x y).1
We define predicates using predicate symbols (typically written as capital letters). For example, we may write P(x) to signify that the predicate “is a person” holds for some variable x.
Functions are used to create other terms or to express a relation between terms. Predicate symbols are operators that combine terms and produce a predicate. Predicates have a truth value. Again, to draw an example from arithmetic, =, <, \leq, >, \geq are predicate symbols. Their predicate is either true or false.
We refer to the number of arguments in a function or predicate as the arity of the function or predicate. For example, f(x, y) has an arity of two, P(a, b, c) has an arity of three.
Quantifiers
First-order predicate logic makes use of quantifiers, which range over domain elements.
The universal quantifier
The universal quantifier, \forall, is used to indicate that some predicate holds for all x within the domain of discourse. For example, we could write
\begin{gather*} (\forall x) P(x) \end{gather*}
We read this as “Within the domain of discourse, for all x, P(x) holds.”
Example: Assuming our domain of discourse is the mammals, and the predicate W(x) means x is warm-blooded:
(\forall x)W(x).
“All mammals are warm-blooded.”
Example: Assuming our domain of discourse is cars, and the predicate W(x) means x has wheels:
(\forall x)W(x).
“All cars have wheels.”
Example: Here’s one that’s false. Let our domain of discourse be butterflies, and the predicate D(x) mean x can dive for oysters.
(\forall x)D(x) (false).
The existential quantifier
The existential quantifier, \exists, is used to indicate that within the domain of discourse, there is some element which makes a predicate true. For example,
\begin{gather*} (\exists x) P(x) \end{gather*}
states that there exists some x (perhaps many, but at least one) for which the predicate, P, is true. We read this as “Within the domain of discourse, there exists some x, such that P(x) holds.”
Example: Let B(x) mean “x is blue”. Then we can write
(\exists x)B(x),
which we read as “There exists something, x, which is blue.” Note that this does not mean there’s only one x for which this is true. Rather, it’s saying there’s at least one x for which this is true.
Example: If we wanted to be more specific about our domain of discourse\ldots
Let C be the set of all cars. Then
(\exists x \in C) B(x)
would mean “There exists a car that is blue.”
We could also treat being a car as a predicate:
(\exists x)(C(x) \land B(x))
which amounts to “There’s some x such that x is a car and x is blue.
Negation of quantifiers
We can negate quantifiers.
Let the domain of discourse be amphibians and the predicate M(x) be “speaks Mandarin.”
\neg(\exists x)M(x).
There does not exist an amphibian which speaks Mandarin, or, more colloquially, no amphibian speaks Mandarin.
This is equivalent to
\forall(x)\neg M(x).
Notice that we push the negation to the other side of the quantifier and change the quantifier from \exists to \forall. For all amphibians, none speaks Mandarin.
Another example: Sticking with amphibians, let the predicate G(x) mean x is green.
\neg(\forall x)G(x).
It is not the case that all amphibians are green. This can be rewritten
(\exists x)\neg G(x).
There exists some amphibian which is not green (at least one).
Again, we’ve pushed the negation to the other side of the quantifier and changed the quantifier from \forall to \exists.
Check-in
Render the sentence “Some people are over seven feet tall” in predicate logic.
Consider how we’d handle more complex statements. For example, for example, render the sentence “All prime numbers greater than two are odd.” in predicate logic. (Hint: Try using an implication.)
Multiple or “stacked” quantifiers
WFFs can contain multiple quantifiers. For example, let C(x) mean “x is a course in the catalog”, let I(y) mean “y is an instructor”, and let A(y, x) mean “(instructor) y is assigned to (course) x”. Then we can write
(\forall x)(C(x) \implies (\exists y)(I(y) \land A(y,x)))
Be aware that the order of quantifiers is important! For example these are two very different sentences.
(\forall x)(\exists y)P(x, y)
(\exists y)(\forall x)P(x, y)
Let’s let P(x, y) mean y is x’s favorite song, and let all the x be elements of the set of all students, and all the y be elements of the set of all songs.
How would you render these statements in English?
(\forall x)(\exists y)P(x, y) becomes “Every student has a favorite song.”
(\exists y)(\forall x)P(x, y) becomes “There a song that is every student’s favorite.”
Clearly these are not the same.
Negating stacked quantifiers
Let’s look at what happens when we negate these statements.
\neg(\forall x)(\exists y)P(x, y)
“It is not the case that every student has a favorite song.”
\neg(\exists y)(\forall x)P(x, y)
“It is not the case that there a song that is every student’s favorite.”
When negating stacked quantifiers, we “push” the negation to the right, and change \forall to \exists and vice versa.
(\exists x)(\forall y)\neg P(x, y)
“There exists some student who has no favorite song.”
(\forall y)(\exists x)\neg P(x, y)
“Every song has at least one student for whom that song is not a favorite.” (This one’s a little awkward to render in English. Can you produce a better rendering?)
Summary of quantified logic
Let V be a set of variables, K a set of constants, and F a set of function symbols, all pairwise disjoint. All variables and constants are atomic terms. If t_1, t_2, \ldots, t_n are terms, and f is a function symbol (with arity n), then f(t_1, t_2, \ldots, t_n) is a term.
Let P be a set of predicate symbols. Well-formed predicate logic formulas are defined as follows.
- If t_1, t_2, \ldots, t_n are terms, and p is a predicate symbol (with arity n), then p(t_1, t_2, \ldots, t_n) is an atomic formula.
- As with propositional logic, if A and B are formulas then \neg A, (A), A \land B, A \lor B, A \implies B, and A \Longleftrightarrow B, are all formulas.
- If x is a variable, and A is a formula, then (\forall x) A and (\exists x) A are also formulas.
We call atomic formulas and their negations literals.
Formulas in which every variable is in the scope of a quantifier are called sentences or closed formulas.
Semantics
As with propositional logic, we have interpretations. Interpretations for expressions in predicate logic are possible meanings for predicates, functions, and variables. This is analogous to assigning truth values to propositional variables in propositional logic.
First, an interpretation in first-order predicate logic defines some domain of discourse. This is some non-empty set, D, and variables of FOL range over the elements of D. Second, an interpretation defines some mapping of function symbols to functions, and predicate symbols to relations over D^n, that is \varphi : D^n \rightarrow D.
We say that the formula (\forall x) A, is true under the interpretation \varphi, if it is true for any arbitrary change in the interpretation of x. Obviously, some predicate is true of all elements in the domain of discourse if and only if we can make such a change in the interpretation.
Example: Domain of discourse is animals.
\begin{gather*} (\forall x) (M(x) \implies V(x)) \end{gather*}
If we say the predicate M(x) means “is a mammal” and the predicate V(x) means “is a vertebrate” then consider the possible interpretations of x. Remember our domain of discourse is animals, so we can’t interpret x as, say, “toaster” or “the color blue.” We have to stick to animals. Given that restriction, there’s no animal we can substitute for x that will make (\forall x) (M(x) \implies V(x)) false. We could interpret x variously as “squirrel,” “whale,” or “human,” and this remains true. So we can say it is true for all x.
We say that the formula (\exists x) A is true, if there exists some interpretation for x from the domain of discourse which make A true.
All we’re saying here, is that within the domain of discourse, there’s some x—it maybe only one—but there’s some x which makes the sentence true.
Examples:
\begin{gather*} (\exists x) P(x) \end{gather*}
If our domain of discourse is planets of solar system, and P(x) means “has liquid water” then this is true for at least one planet, ours. It needn’t be true for any other element in the domain of discourse—one suffices. More than one is OK too, but there must be at least one interpretation that makes this true.
Satisfaction
As with propositional logic, a WFF is satisfiable if there is some interpretation under which it is true. An interpretation which makes an expression true is called a model. Similarly, we say an expression is valid if it is true for all possible interpretations.
Entailment
Also, we may speak of entailment in FOL. That is, if every interpretation which makes A true also makes B true, then we say A entails B, and we write A \vDash B. Sometimes this is referred to as semantic consequence. Again,
\begin{gather*} A \vDash B \quad \text{if and only if} \quad M(A) \subseteq M(B) \end{gather*}
where M(A) is the set of all models of A, and M(B) is the set of all models of B.
Some simple examples
Consider the expression P(x). This signifies that the predicate P holds for some element x in our domain of discourse—some x \in D. Now, there are some interpretations for which this is true, and some for which it is false, but keep in mind that in FOL, an interpretation must include definition of the domain of discourse, D, the mapping \varphi which assigns meaning to predicate symbols and function symbols, and the predicate variables.
Let’s consider only those expressions in which each variable is quantified, either universally or existentially.
So, for example, let the domain of discourse is the objects in our classroom, and let P(x) signify “x is an automobile.” Using the universal quantifier, we may write
\begin{gather*} (\forall x) P(x) \end{gather*}
to state that for all elements, x, of our domain of discourse, the predicate P holds. This is false, since there are no automobiles in the classroom.
If we interpret P(x) to mean “x is smaller than the Empire State Building,” then (\forall x) P(x) is true.
Now let’s consider the existential quantifier. Using the existential quantifier, we may write
\begin{gather*} (\exists x) P(x) \end{gather*}
to state that for some element, x, of our domain of discourse, the predicate P holds.
If we take P(x) to mean “x is student,” then this is true, since there does exist some x in the classroom which is a student. If we take P(x) to mean “x is a lizard,” then this is false (there are no lizards in the classroom—at least I think there aren’t).
Notice that in both these examples, since P(x) is not true for all interpretations, it is not valid.
We may also write more complex expressions involving multiple variables and predicates. For example, consider
\begin{gather*} (\forall x) (P(x) \implies Q(x)) \end{gather*}
If we take P(x) to mean “x is student,” and Q(x) “x is a mammal,” then we have a model. It is true that for all x in the classroom, if x is a student then x is a mammal. But if we take Q(x) to mean “x is an automobile,” then this is false.
Note that there’s more than one way to write this. For example, we might have written instead
\begin{gather*} \neg (\exists x) (P(x) \land \not Q(x)) \end{gather*}
and we’d have (under the first interpretation): “There is no x, such that x is a student and x is not a mammal.” This is true. Under the second interpretation, “There is no x, such that x is a student and x is not an automobile,” this is false.
Predicates of higher arity
All of the examples above involved unary predicates. However, we may have predicates of higher arity. In the case of predicates of arity two or greater, the predicate expresses some relation between its arguments. The examples of arithmetic operators, =, <, \leq, >, \geq, were given above. Another simple example is D(x, y, z) where we interpret D as “difference” and then treat this as true if and only if z = x - y.
Theories
A theory is a set of sentences in FOL. We may refer to such sentences as theorems.
Order of quantifiers
If, in some sentence, all quantifiers are of the same type—either all universal or all existential—then their order does not matter. For example, the following are equivalent.
\begin{gather*} (\forall x)(\forall y) P(x, y) \\ (\forall y)(\forall x) P(x, y) \end{gather*}
However, this is not the case if quantifiers are of mixed type. Clearly, these two sentences are not equivalent:
\begin{gather*} (\forall x)(\exists y) P(x, y) \\ (\exists y)(\forall x) P(x, y) \end{gather*}
Let’s say that we interpret P as “likes.” The first sentence states that everybody likes someone (even if everybody likes someone different). The second statement states that there’s some person whom everyone likes.
Deduction
We often ask ourselves questions of our theory like “Is our theory consistent?” That is, given a set of sentences in FOL, does the conjunction of these sentences have a model? Put another way, we can ask: “Is our theory satisfiable?”
Model existence theorem
Given some theory in FOL, if it is syntactically consistent—that is, there is no A such that the theory includes both A and \neg A—then it has a model.
Proof systems
The main objective of a deductive proof system is to prove semantic consequence, by purely syntactic inference. A proof is a finite sequence of inferences, starting from the set of all axioms and theorems given, to deduce new theorems. We say that A can can be derived from \Gamma, written \Gamma \vdash A, if there exists some proof of A from \Gamma.
Two things we desire for our proof system are soundness and completeness. These may be stated concisely,
\begin{gather*} \Gamma \vdash A \quad \implies \quad \Gamma \vDash A \tag{soundness} \end{gather*}
\begin{gather*} \Gamma \vDash A \quad \implies \quad \Gamma \vdash A \tag{completeness}. \end{gather*}
There are many different kinds of proof systems:
- Hilbert systems
- Fitch systems (natural deduction)
- Resolution
- Sequent
- etc.
All have their strengths and weaknesses, and some are more suited to efficient implementation in automated proof systems (but that’s for another day).
Solutions to check-ins
- Assume universe of discourse is humans. Predicate T(x) means x is over seven feet tall.
\hspace{2em}(\exists x)T(x).
\hspace{2em}Or, making "being human" a predicate H(x):
\hspace{2em}(\exists x)(H(x) \land T(x).
\hspace{2em}There exists something that's both human and over seven feet tall.
- Assume universe of discourse is \mathbb(N), the natural numbers, let P(x) mean x is prime, and O(x) mean x is odd.
\hspace{2em}(\forall x)((P(x) \land x > 2) \implies O(x)).
\hspace{2em} Of course, there are other ways to write this.
Copyright © 2023–2025 Clayton Cafiero
No generative AI was used in producing this material. This was written the old-fashioned way.
Footnotes
“In computer science, syntactic sugar is syntax within a programming language that is designed to make things easier to read or to express. It makes the language sweeter for human use: things can be expressed more clearly, more concisely, or in an alternative style that some may prefer.” (Wikipedia)↩︎