Skip to content
Tutorials Center
My learning

Topics

Lesson 10 of 37 ยท Predicate Logic

Predicates and Quantifiers

Learn predicates, domains and the universal and existential quantifiers, how to read and write quantified statements, and how Python's all() and any() model them.

Propositional logic treats each statement as an indivisible atom. That is too coarse to say "every student passed" or "some server is down". Predicate logic (also called first-order logic) looks inside statements. It adds objects, properties of objects and two quantifiers, for all and there exists. With these few additions, nearly all of ordinary mathematics can be written precisely.

Predicates

A predicate is a statement with a blank for an object. Even(x) ("x is even") is neither true nor false until you fill in x: Even(4) is true, Even(7) is false. A predicate can have several places: Less(x, y) is written x < y, and Parent(a, b) says "a is a parent of b".

In programming terms, a predicate is a function returning a boolean: is_even(x). That correspondence is the best way to build intuition.

The domain of discourse

Quantified statements are only meaningful relative to a domain (or universe): the collection of objects the variables range over. "Every x is positive" is false over the integers, true over the positive integers. When you read or write a statement, always ask: what is the domain?

The universal quantifier โˆ€

โˆ€x P(x) means "for every x in the domain, P(x) holds". It is true when no object fails P. Over an empty domain it is vacuously true.

Python's all() has precisely this meaning:

Python
all(P(x) for x in domain)

The existential quantifier โˆƒ

โˆƒx P(x) means "there is at least one x in the domain with P(x)". It is true when some object satisfies P, and false over an empty domain. Python's matching function is any().

Python
any(P(x) for x in domain)

Two quantifiers

โˆ€x P(x) Every x satisfies P
โˆƒx P(x) Some x satisfies P
Domain Where x comes from
all() and any() Python's quantifiers

Always name the domain

1 / 2
Python Quantifiers over a finite domain

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The empty-domain line shows the vacuous truth of โˆ€ and the falsity of โˆƒ.

Counterexamples and witnesses

  • To disprove โˆ€x P(x), exhibit one counterexample: an x with ยฌP(x).
  • To prove โˆƒx P(x), exhibit one witness: an x with P(x).
  • To prove โˆ€x P(x) you need an argument covering all objects; examples never suffice.
  • To disprove โˆƒx P(x) you must show every object fails.

In code, a counterexample search is a loop that returns the first failing element.

Python Witnesses and counterexamples

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The polynomial produces primes for n = 0..39 but fails at n = 40 (1681 = 41ยฒ). Forty confirming cases and one counterexample: a vivid reminder that examples never prove a universal claim.

Free and bound variables

In โˆ€x (x + y > 0), the variable x is bound by the quantifier, while y is free. A formula with free variables is a predicate; a formula with none is a sentence and has a definite truth value once the domain and the meanings of symbols are fixed. The same variable name in different quantifiers is independent: โˆ€x P(x) โˆง โˆƒx Q(x) uses two unrelated xs. Think of bound variables as local loop variables.

Restricted quantification

Mathematics often writes "for every even x, โ€ฆ" with the condition after the quantifier. In logic that is an implication (for โˆ€) or a conjunction (for โˆƒ):

  • "Every even number is divisible by 2" โ‰ก โˆ€x (Even(x) โ†’ Div2(x))
  • "Some even number is prime" โ‰ก โˆƒx (Even(x) โˆง Prime(x))

The classic error: writing โˆ€x (Even(x) โˆง P(x)) for "every even x satisfies P". That claims everything is even. Likewise โˆƒx (Even(x) โ†’ P(x)) is trivially true whenever some x is odd. Use โ†’ with โˆ€ and โˆง with โˆƒ.

Common quantified statements in math and code

Statement Logic
The list is sorted โˆ€i (a[i] โ‰ค a[i+1])
The list contains k โˆƒi (a[i] = k)
f is injective โˆ€x โˆ€y (f(x) = f(y) โ†’ x = y)
There is no largest integer โˆ€n โˆƒm (m > n)
Every user has an email โˆ€u โˆƒe (Email(u, e))

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which Python function corresponds to the universal quantifier?

    all() is true exactly when every element satisfies the condition, like โˆ€.
  2. 2. What is โˆ€x P(x) when the domain is empty?

    There is no element that could fail P, so the universal claim holds vacuously.
  3. 3. How do you formalize 'every dog barks' with Dog(x) and Barks(x)?

    Restricted universal claims use implication.
  4. 4. One counterexample is enough to disprove...

    A single x with ยฌP(x) refutes a universal claim; an existential claim needs every x to fail.

Summary

  • A predicate is a boolean-valued function of objects; quantifiers say how many objects satisfy it.
  • โˆ€ matches all() and โˆƒ matches any() over a domain; always state the domain.
  • Prove โˆƒ with a witness, disprove โˆ€ with a counterexample.
  • Bound variables are local; free variables make a formula a predicate rather than a sentence.
  • Restricted quantification: use โ†’ with โˆ€ and โˆง with โˆƒ.

Next: Nested Quantifiers and Negation