Skip to content
Tutorials Center
My learning

Topics

Lesson 8 of 68 Β· Logic

Predicates and Quantifiers

Learn predicate logic: predicates, universal and existential quantifiers, nested quantifiers and negation rules, tested on finite domains with all() and any().

Propositional logic treats each statement as an indivisible unit: "it is raining" is true or false, and that is all it can say. It cannot express "every student passed" or "some number is prime", because those statements are about many objects at once. Predicate logic adds the missing pieces: statements with blanks, called predicates, and quantifiers that say how many objects must fill the blank.

Nearly all of mathematics, and a good deal of programming, is written in this language. Database queries, loop conditions, test assertions and formal specifications all say "for all" and "there exists". In this lesson you will learn to read and write such statements, negate them correctly, and test them over finite domains with all() and any().

Predicates and domains

A predicate is a statement with one or more variables that becomes a proposition once you plug in values. P(x) might mean "x is even". Then P(4) is true and P(7) is false. A predicate with two variables, such as L(x, y) meaning "x is less than y", needs two arguments.

Every predicate lives over a domain (or universe of discourse): the collection that the variables are allowed to take values from. The same sentence can be true over one domain and false over another, so the domain is part of the statement. "Every x has a square root" is true over the non-negative reals and false over the integers.

In Python a predicate is simply a function that returns a Boolean, and a finite domain is a collection you can loop over.

Python
def is_even(x):
    return x % 2 == 0

def less_than(x, y):
    return x < y

domain = range(1, 11)

The two quantifiers

A quantifier turns a predicate back into a proposition by saying which values must work.

Name Symbol Meaning Python over a finite domain
Universal βˆ€x P(x) P(x) is true for every x in the domain all(P(x) for x in D)
Existential βˆƒx P(x) P(x) is true for at least one x in the domain any(P(x) for x in D)

A universal statement is like a very long AND: P(x1) ∧ P(x2) ∧ .... An existential statement is a very long OR. That is why a single counterexample (one x where P(x) fails) is enough to disprove a universal statement, while a single witness (one x where P(x) holds) is enough to prove an existential one.

Remember the edge case from Mathematical Notation and Python: over an empty domain, a universal statement is true and an existential statement is false.

Two quantifiers

For all Like a long AND. One counterexample kills it.
There exists Like a long OR. One witness proves it.

Always say which domain you mean.

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.

Using next(..., None) is a nice way to return the witness or counterexample instead of only a yes or no. When a universal claim fails, the counterexample is the most useful thing a test can tell you.

Nested quantifiers

Statements often use several quantifiers. Read them left to right, one at a time. Take the predicate L(x, y): "x < y" over the integers 1 to 5.

  • βˆ€x βˆƒy L(x, y): for every x there is a y bigger than it. (Here: false, because x = 5 has no larger y in the domain. Over all integers it would be true.)
  • βˆƒy βˆ€x L(x, y): there is one y that is bigger than every x. (This is false too, because y must be bigger than itself when x = y.)
  • βˆƒx βˆ€y Β¬L(y, x): some x has nothing below it. (True: x = 1.)

The order of different quantifiers matters. βˆ€x βˆƒy P(x, y) lets y depend on x: each x may get its own partner. βˆƒy βˆ€x P(x, y) demands a single y that works for all x, which is much stronger. Swapping two quantifiers of the same kind never changes the meaning: βˆ€x βˆ€y equals βˆ€y βˆ€x.

In Python, nested quantifiers are nested all/any calls, and the nesting order mirrors the symbols:

Python
all(any(P(x, y) for y in D) for x in D)    # for all x there exists y
any(all(P(x, y) for x in D) for y in D)    # there exists y for all x
Python Order of quantifiers matters

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 first statement is true, since every x pairs with 6 - x, which stays inside 1 to 5. The second is false: no single y works for every x. This difference is exactly the difference between "everyone has a partner" and "there is one person who is everyone's partner".

Negating quantified statements

Negation flips the quantifier and pushes the negation inward. These are the generalized De Morgan laws:

  • Β¬βˆ€x P(x) is equivalent to βˆƒx Β¬P(x): "not everything has the property" means "something lacks it".
  • Β¬βˆƒx P(x) is equivalent to βˆ€x Β¬P(x): "nothing has the property" means "everything lacks it".

For nested statements, flip each quantifier in turn, working from the outside in, and finally negate the predicate. The negation of βˆ€x βˆƒy P(x, y) is βˆƒx βˆ€y Β¬P(x, y).

A sentence example: the claim "every student has read some book" has the negation "some student has read no book", not "no student has read any book". The common mistake is to negate only the predicate and keep the quantifier.

Python Verifying the negation rules

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.

Propositional versus predicate logic, and the quantifier theorems

Propositional logic treats whole statements as indivisible atoms: p might stand for "it rains". It can combine them but cannot look inside. Predicate logic opens the atoms up.

Propositional logic Predicate logic
Basic unit a proposition p, true or false a predicate P(x) over a domain
Can express combinations with ∧, ∨, Β¬, β†’, ↔ the same, plus "for all" and "there exists"
Decidable by truth table? yes, 2^n rows no, in general (the domain may be infinite)
Talks about objects? no yes: names, variables, relations
Example p β†’ q βˆ€x (Student(x) β†’ βˆƒy Teaches(y, x))

Predicate logic includes propositional logic as a special case, and every propositional law carries over, with quantifiers adding new ones.

How quantifiers interact with connectives

Over a finite domain, βˆ€x is a big AND and βˆƒx is a big OR, so the laws follow from the propositional ones:

  • βˆ€x (P(x) ∧ Q(x)) ≑ βˆ€x P(x) ∧ βˆ€x Q(x): βˆ€ distributes over ∧.
  • βˆƒx (P(x) ∨ Q(x)) ≑ βˆƒx P(x) ∨ βˆƒx Q(x): βˆƒ distributes over ∨.
  • Only one direction holds otherwise: βˆ€x P(x) ∨ βˆ€x Q(x) implies βˆ€x (P(x) ∨ Q(x)), but not conversely (everyone is even or odd, but it is false that everyone is even or that everyone is odd). Similarly, βˆƒx (P(x) ∧ Q(x)) implies βˆƒx P(x) ∧ βˆƒx Q(x), but not conversely.

Nested quantifier theorems

For a two-place predicate P(x, y):

  • Two quantifiers of the same kind can swap: βˆ€x βˆ€y P ≑ βˆ€y βˆ€x P and βˆƒx βˆƒy P ≑ βˆƒy βˆƒx P.
  • Swapping different kinds is not an equivalence, but one direction always holds: βˆƒy βˆ€x P(x, y) implies βˆ€x βˆƒy P(x, y). If a single y works for everyone, then certainly each x has a partner. The converse fails.

Rather than trust these, we can test them on every possible predicate over a small domain. There are 2^9 = 512 binary relations on three elements.

Python Verifying quantifier theorems on all predicates over a 3-element 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.

Every implies column is True, and the converse column is False for exactly the three statements we said are one-directional. A single counterexample (here found by exhaustive search) is all it takes to prove that a converse is not a law.

From English to nested quantifiers

Read the sentence in the order of its quantifiers, and decide for each whether the choice may depend on the earlier ones.

  • "Every student has a favorite course": βˆ€s βˆƒc Likes(s, c). Different students may pick different courses.
  • "There is a course that every student likes": βˆƒc βˆ€s Likes(s, c). One course for all. This is stronger, and it implies the first sentence.
  • "No student likes every course": Β¬βˆƒs βˆ€c Likes(s, c), which negates into βˆ€s βˆƒc Β¬Likes(s, c): every student dislikes at least one course.
  • "Exactly one winner": βˆƒw (Wins(w) ∧ βˆ€x (Wins(x) β†’ x = w)).

From domains to the real world

A finite check is a proof only when the domain is finite and you checked all of it. For an infinite domain such as the integers, a loop over a few hundred values can still do real work: it can find a counterexample, which settles a universal claim as false, or find a witness, which settles an existential claim as true. If no counterexample turns up, you have evidence and a conjecture, but not a proof. How Proofs Work shows how to go from there.

A few translations you will use constantly:

  • "Every even number greater than 2 is the sum of two primes": βˆ€n ((n is even ∧ n > 2) β†’ βˆƒp βˆƒq (p is prime ∧ q is prime ∧ p + q = n)). A universal statement usually pairs with an implication, not an AND. Writing βˆ€x (even(x) ∧ P(x)) would claim that everything is even.
  • An existential statement usually pairs with AND: βˆƒx (even(x) ∧ P(x)) says some even number has P. Using an implication here is wrong, because βˆƒx (even(x) β†’ P(x)) becomes true as soon as one odd number exists.

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. What is the negation of 'every student passed the exam'?

    Β¬βˆ€x P(x) is equivalent to βˆƒx Β¬P(x). One student who did not pass is enough to make the original claim false; it does not need to be that nobody passed.
  2. 2. Over the domain {1, 2, 3, 4}, which statement is true?

    x = 1 is at most every y, so βˆƒx βˆ€y (x <= y) is true. The first fails because y would have to exceed itself when x = y, the second fails for x = 4 (nothing is larger), and the last fails for x = 2.
  3. 3. What does all(P(x) for x in []) evaluate to?

    A universal statement over an empty domain is vacuously true because there is no element that could violate the property.
  4. 4. Which pairing is the usual correct one?

    'All A are B' is βˆ€x (A(x) β†’ B(x)); 'some A is B' is βˆƒx (A(x) ∧ B(x)). Swapping them gives statements with very different truth values.

Summary

  • A predicate is a Boolean function of variables; a domain says which values are allowed, and it is part of the meaning.
  • βˆ€ is a long AND (all) and βˆƒ is a long OR (any); counterexamples disprove universal claims and witnesses prove existential ones.
  • Nested quantifiers read left to right; mixing βˆ€ and βˆƒ in a different order changes the meaning, while repeating one kind does not.
  • Negation flips each quantifier and negates the predicate: Β¬βˆ€ = βˆƒΒ¬ and Β¬βˆƒ = βˆ€Β¬.
  • Universal statements pair with implication and existential statements with AND.

Next: Sets and Set Operations, the objects that quantifiers range over.