Computer Science I / Predicate Logic and Quantifiers
Practice question · Put in order

Four statements are built from the same two-place predicate P(x, y). Order them from the weakest claim, which is the easiest to satisfy, to the strongest.

Hints
  1. A claim is stronger when it demands more: one witness is the least demanding, and every pair the most.
  2. Compare the two middle claims carefully, one allows a different y for each x, the other insists on a single y that serves them all.
Show the answer
  1. there exists x and there exists y with P(x, y)
  2. for all x there exists y with P(x, y)
  3. there exists y such that for all x, P(x, y)
  4. for all x and for all y, P(x, y)
Why

One pair suffices for the first; the second wants a witness for each x, and it may be a different y each time; the third demands a single y that works for every x, which is far harder; the fourth demands every pair. 'Every person has a mother' is of the second kind and true, while 'there is one mother of everyone' is of the third kind and false, swapping the quantifier order silently changes the meaning.

Read the lesson: Predicate Logic and Quantifiers →

Practise Predicate Logic and Quantifiers

The app has 4 more questions on this lesson, and keeps your place in the course. Computer Science I is free to start.

More questions on Predicate Logic and Quantifiers