In the previous post, we saw why propositional logic is not sufficient to express general mathematical statements, and why predicate logic is required.
In this post, we’ll explore the formal syntax of predicate logic, detailing how statements are constructed using terms, predicates, quantifiers, and formulas.
Terms
In predicate logic, terms represent objects within a given domain. Terms can be:
- Variables (usually denoted by lowercase letters such as \(x\),\(y\),\(z\).
- Constants (symbolizing specific, fixed objects, e.g., \(0\),\(1\),\(a\),\(b\).
- Function symbols applied to terms (e.g., \(f(x)\), \(g(x,y)\)).
How Terms Are Built
Formally, terms are constructed recursively:
- Any variable is a term.
- Any constant symbol is a term.
- If \(f\) is an \(n\)-ary function symbol and \(t_1, t_2, \dots, t_n\) are terms, then \(f(t_1, t_2, \dots, t_n)\) is also a term.
Examples of Terms:
- Variables: \(x\),\(y\)
- Constants: \(0\),\(1\)
- Function terms: \(f(x)\), \(+(x,y)\), \(\sin(z)\)
Predicates
Predicates express properties of terms or relations between them. A predicate \(P\) applied to terms \(t_1, t_2, \dots, t_n\) is written as \(P(t_1, t_2, \dots, t_n)\).
Examples:
- \(Even(x)\) — “\(x\) is even.”
- \(Prime(y)\) — “\(y\) is prime.”
- \(Greater(x,y)\) — “\(x\) is greater than \(y\).”
Predicates are crucial in clearly describing properties and relationships in logic.
Quantifiers
Quantifiers allow us to express statements involving generality or existence:
- Universal quantifier (\(\forall\)): means “for all” or “every.”
- Example: \(\forall x\; Even(x) \vee Odd(x)\) — “Every number is either even or odd.”
- Existential quantifier (\(\exists\)): means “there exists.”
- Example: \(\exists y\; Prime(y) \wedge y > 2\) — “There exists some \(y\) that is prime and greater than 2.”
Quantifiers bind variables within their scope, turning predicates into full propositions. In general, quantifiers should explicitly define the domain to which the variable is bound, i.e. the above two examples should really read
- \(\forall x \in \mathbb{N}\; Even(x) \vee Odd(x)\), and
- \(\exists y \in \mathbb{N}\; Prime(y) \wedge y > 2\)
This means that the variables \(x\) and \(y\) are bound to the natural numbers. Propositions can that are true in one domain may be false in another domain. For example
- \(\forall x \in \mathbb{N}\; x \ge 0\) is true, but
- \(\forall x \in \mathbb{Z}\; x \ge 0\) is false.
In some situations, the domain is clear from the context and may be omitted.
Forming Formulas
Predicate logic uses the following rules to form formulas:
- Atomic Formulas: If \(P\) is an \(n\)-ary predicate and \(t_1, t_2, \dots, t_n\) are terms, \(P(t_1, t_2, \dots, t_n)\) is an atomic formula.
- Complex Formulas:
- If \(\varphi\) and \(\psi\) are formulas, then so are \((\varphi \wedge \psi)\), \((\varphi \vee \psi)\), \((\varphi \rightarrow \psi)\), \((\varphi \leftrightarrow \psi)\), \(\neg \varphi\).
- If \(\varphi\) is a formula and \(x\) a variable, then \(\forall x\; \varphi\) and \(\exists x\; \varphi\) are also formulas.
Well-Formed Formulas (WFFs)
Formulas constructed following the above rules are called well-formed formulas. They represent meaningful mathematical statements.
Examples:
- \(\forall x \in \mathbb{N}\; (Prime(x) \rightarrow x > 1)\)
- \(\exists y \in \mathbb{R}\;(y^2 = 2)\)
- \(\forall x \in \mathbb{N}\; \exists y \in \mathbb{N}\; (y > x)\)
Exercises
- Identify the terms, predicates, and quantifiers in the following formula: \(\forall x \in \mathbb{N}\; (Even(x) \rightarrow \exists y\; (y = x + 2 \wedge Even(y)))\)
- Construct a predicate logic formula stating: “Every positive integer has a successor.”
- Are the following expressions terms or formulas? Explain why.
- \(f(x,g(y))\)
- \(P(x,y,z)\)
- \(\forall x,\; g(x)\)
- Write a predicate logic formula to express: “There exists a number that is less than all other numbers.”
This post lays out the precise structure needed to form meaningful mathematical statements, setting the stage for exploring semantics and proofs in predicate logic.