# Predicate Logic and Quantifiers

Computer Science I · Discrete Mathematics · https://tryals.app/learn/computer-science-i/predicate-logic-and-quantifiers

## Statements About Everything and Something

Propositional logic cannot express general statements like "every integer has a successor." **Predicate logic** solves this by adding **predicates** $P(x)$—statements with variables that are true or false depending on $x$—and **quantifiers**.

| Quantifier | Symbol | Meaning | Condition |
| --- | --- | --- | --- |
| **Universal** | $\forall x\, P(x)$ | For all $x$, $P(x)$ | True for every $x$ in the domain |
| **Existential** | $\exists x\, P(x)$ | There exists $x$, $P(x)$ | True for at least one $x$ |

**Common pitfall:** A universal claim ($\forall x\, P(x)$) is disproved by a single **counterexample** where $P(x)$ fails.

## Order and Negation

The **order of quantifiers** matters enormously. $\forall x\, \exists y\, P(x,y)$ means "every $x$ has some $y$," which is very different from $\exists y\, \forall x\, P(x,y)$, meaning "some single $y$ works for all $x$."

For example, "every person has a mother" is true, but "there is one mother of everyone" is false. Swapping quantifiers silently alters meaning.

To negate quantifiers, flip the quantifier and negate the inner predicate:
- $\neg \forall x\, P(x) \equiv \exists x\, \neg P(x)$
- $\neg \exists x\, P(x) \equiv \forall x\, \neg P(x)$

**Common pitfall:** $\neg \forall x\, P(x)$ means "not all" ($+\text{at least one isn't}$), **not** "none is."

## Practice questions

7 of this lesson's 11 practice questions, with answers. The full set is in the app.

### 1. 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.

**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.

Page: https://tryals.app/practice/computer-science-i/predicate-logic-and-quantifiers/four-statements-are-built-from-the-same-two-place-predicate-p-x-y

### 2. Select every statement that correctly expresses the negation of 'for all x, P(x)'.

A. there exists x with P(x)
B. for all x, NOT P(x)
C. it is not the case that every x satisfies P(x)
D. no x satisfies P(x)
E. there exists x with NOT P(x)

**Answer:** C. it is not the case that every x satisfies P(x); E. there exists x with NOT P(x)

**Why:** 'There exists x with not P(x)' is the formal negation and 'it is not the case that every x satisfies P' is the same claim in words. Options 2 and 5 both say no x satisfies P, which is stronger than needed, and option 1 is not a negation at all. 'Not all' means 'at least one is not', never 'none is'.

Page: https://tryals.app/practice/computer-science-i/predicate-logic-and-quantifiers/select-every-statement-that-correctly-expresses-the-negation-of-for

### 3. "Every student who studied passed" is true in a class where nobody studied. Why does the universal claim survive a domain with no qualifying members?

A. Because an implication with a false premise is true, so it holds vacuously.
B. Because the statement is meaningless when nobody studied, and meaningless statements count as true.
C. Because the claim should be read as asserting that some students studied, which makes it false.
D. Because universal statements are true only when their domain is non-empty, so this one is actually false.

**Answer:** A. Because an implication with a false premise is true, so it holds vacuously.

**Why:** Written out, the claim is an implication per student, and a counterexample would be someone who studied and failed, with nobody studying, none exists. It is the same vacuous truth that makes ∅ a subset of every set. The practical warning is that it hides failure: a test asserting 'every returned record matches' goes green when the query returns nothing at all.

Page: https://tryals.app/practice/computer-science-i/predicate-logic-and-quantifiers/every-student-who-studied-passed-is-true-in-a-class-where-nobody

### 4. Match each quantified statement to its correct negation.

**Answer:**

- for all x, P(x) → there exists x with NOT P(x)
- there exists x with P(x) → for all x, NOT P(x)
- every student passed → at least one student did not pass
- some student passed → no student passed

**Why:** Negating 'all are P' gives 'at least one is not P', which is exactly why one counterexample refutes a universal claim; negating 'some is P' gives 'none is P'. Writing the negation of 'all are P' as 'all are not P' is the standard error, and it is a much stronger claim than the truth requires.

Page: https://tryals.app/practice/computer-science-i/predicate-logic-and-quantifiers/match-each-quantified-statement-to-its-correct-negation

### 5. Sort each English claim by the quantifier it uses.

**Answer:**

- Universal claim: Every prime greater than 2 is odd, No integer is both even and odd, Each vertex of this graph has even degree
- Existential claim: Some integer is both even and prime, There is a number that divides every integer, At least one student in the class studies Latin

**Why:** 'Every', 'each' and 'no' are all universal, 'no integer is both even and odd' says that for all x, x is not both. 'Some', 'there is' and 'at least one' are existential. Filing a 'no' statement as existential because it feels negative is the trap; the negation of an existential is a universal, which is exactly what 'no' expresses.

Page: https://tryals.app/practice/computer-science-i/predicate-logic-and-quantifiers/sort-each-english-claim-by-the-quantifier-it-uses

### 6. The negation of "every student passed" is "no student passed".

**Answer:** False

**Why:** False. $\lnot\forall x\,P(x)$ is $\exists x\,\lnot P(x)$, *some* student did not pass. 'No student passed' is $\forall x\,\lnot P(x)$, a far stronger claim. Confusing the contrary with the contradictory is one of the most common quantifier errors, and it is why a single counterexample settles a universal.

Page: https://tryals.app/practice/computer-science-i/predicate-logic-and-quantifiers/the-negation-of-every-student-passed-is-no-student-passed

### 7. A test asserts *"every returned record matches the filter"* and passes when the query returns nothing at all. What went wrong?

A. Vacuous truth, a universal claim over an empty set holds
B. Nothing, an empty result genuinely satisfies the filter
C. The test framework treats empty results as successes by convention
D. The assertion was written with the wrong comparison operator

**Answer:** A. Vacuous truth, a universal claim over an empty set holds

**Why:** No records means no counterexample, so the test goes green precisely when the query is returning nothing, the failure mode strengthens the assertion. It is why such tests must also assert the collection is non-empty, and the same trap catches validation rules applied to empty configurations.

Page: https://tryals.app/practice/computer-science-i/predicate-logic-and-quantifiers/a-test-asserts-every-returned-record-matches-the-filter-and-passes