Predicates and Quantifiers

Discrete Mathematics — Lesson 4

Notes By Pr. El Hadiq Zouhair

1 / 10

Overview

Predicate logic expands the range of propositions that are possible.
A particular form of programming is possible using predicate logic: logic programming.
Universal truths can be differentiated from special cases.
You will learn about predicates and quantifiers.

2 / 10

Predicates

Many propositions have variables that determine their value.

The melting point of $x$ element is $y$ Kelvin: $M(x, y)$

Popular predicates include equality predicates: $<$, $>$, $\leq$ (<=), $\geq$ (>=), $=$ (==) and $\neq$ (!=):

Python — imports (run once) from sympy import symbols, Implies x = symbols('x')

Python # Predicate: (x + 2 > 4) => (x + 3 < 4) pred = Implies(x + 2 > 4, x + 3 < 4) # Evaluate for x = 2 and x = 3 results = [pred.subs(x, v) for v in [2, 3]] print(results) # [True, False]

3 / 10

Example: Pythagorean Triple

Consider the proposition $p:\; x^2 + y^2 = z^2$

Python # Define the predicate as a Python lambda p = lambda x, y, z: x**2 + y**2 == z**2 # What is the truth value for x=5, y=12, z=13? print(p(5, 12, 13)) # True # What is the truth value for x=160, y=241, z=290? print(p(160, 241, 290)) # False

To learn more about this equation, read about Pythagorean triples.

4 / 10

Universal Quantifier $\forall$

Universal quantification is the proposition: "$P(x)$ is true for all values of $x$."

$$\forall x\; (x^2 \geq 0)$$

Python — imports (run once) from z3 import Real, ForAll, Implies, prove

Python x = Real('x') # For all real x: x^2 >= 0 prove(ForAll([x], x**2 >= 0)) # proved

$$\forall x \geq 2\; (x \geq 0)$$

Python # For all x >= 2: x >= 0 (encode domain as implication) prove(ForAll([x], Implies(x >= 2, x >= 0))) # proved

5 / 10

Existential Quantifier $\exists$

Existential quantification is the proposition: "$P(x)$ is true for at least one value of $x$."

$$\exists x\; (x = -x)$$

Python — imports (run once) from z3 import Real, Reals, And, Exists, Solver

Python x = Real('x') s = Solver() s.add(x == -x) print(s.check()) # sat print(s.model()) # [x = 0]

This is a special case of existence — it is unique, denoted $\exists!\,x$.

6 / 10

Equivalences

Equivalences are also used for quantifiers, using sympy.simplify or reduce_inequalities:

Law	Equivalence
Conjunction	$\forall x(P(x)\wedge Q(x)) \;\Leftrightarrow\; \forall x\,P(x) \wedge \forall x\,Q(x)$
Disjunction	$\exists x(P(x)\vee Q(x)) \;\Leftrightarrow\; \exists x\,P(x) \vee \exists x\,Q(x)$
De Morgan's ($\forall$)	$\neg\forall x\,P(x) \;\Leftrightarrow\; \exists x\,\neg P(x)$
De Morgan's ($\exists$)	$\neg\exists x\,P(x) \;\Leftrightarrow\; \forall x\,\neg P(x)$

In fact, the negation can be passed all the way down the expression:

$$\begin{aligned} &\neg\exists v\;\forall w\;\exists x\;\exists y\;\forall z\;P(v,w,x,y,z)\\ \Leftrightarrow\;&\forall v\;\neg\forall w\;\exists x\;\exists y\;\forall z\;P(v,w,x,y,z)\\ \Leftrightarrow\;&\forall v\;\exists w\;\neg\exists x\;\exists y\;\forall z\;P(v,w,x,y,z)\\ \Leftrightarrow\;&\forall v\;\exists w\;\forall x\;\forall y\;\neg\forall z\;P(v,w,x,y,z)\\ \Leftrightarrow\;&\forall v\;\exists w\;\forall x\;\forall y\;\exists z\;\neg P(v,w,x,y,z) \end{aligned}$$ 7 / 10

Nested Quantifiers

How to interpret nested quantifiers:

Statement	Meaning
$\exists x\;\exists y\;P(x,y)$	At least one pair exists.
$\forall x\;\exists y\;P(x,y)$	A pair exists for every $x$.
$\exists x\;\forall y\;P(x,y)$	A specific $x$ works for any $y$.
$\forall x\;\forall y\;P(x,y)$	All pairs work!

Everyone in this course likes a branch of mathematics:

$$\forall\,s \in \mathrm{students}\;\; \exists\,b \in \mathrm{mathematics}\;\; \bigl(\mathrm{Likes}(s,\,b)\bigr)$$

8/ 10

Examples: Translating Statements to Logic

Translate the following statements in logic:

No one is perfect. $$\neg\,\exists x\;\mathrm{Perfect}(x)$$
Not all propositions are contradictions. $$\neg\,\forall x\;\mathrm{Contradiction}(x)$$
In my second-year class, only one person knew Java, SQL and Python. $$\exists!\,x\;\bigl(\mathrm{Java}(x) \wedge \mathrm{SQL}(x) \wedge \mathrm{Python}(x)\bigr)$$

9 / 10

Summary

Predicates are propositional functions with parameters.
There are three quantifiers: Universal ($\forall$), Existence ($\exists$) and Uniqueness ($\exists!$).
Z3 directly mirrors ForAll, Exists:
- Universal: prove(ForAll([x], ...))
- Existence: Solver().check() → sat / unsat
So far, propositions were taken as is.
The next lesson allows for analysis of propositions through rules of inference.

Python — key imports for this lesson from sympy import symbols, Implies # propositional predicates from z3 import Real, Reals, ForAll, Exists, And, Not, Implies as Imp from z3 import Solver, prove # quantifiers

10 / 10