Self-Assessment Quiz: Predicate Logic and Quantifiers

Twenty questions to check your understanding. Answer before opening the key. Aim for 16+. Throughout, $\mathbb{N}$ includes $0$.

Question 1

Which of the following is a predicate rather than a proposition?

A) "$7$ is prime" B) "$x > 5$" C) "$2 + 2 = 5$" D) "every integer has a successor"

Question 2

The statement $P(x)$ = "$x^2 = 2$" has different truth answers to "does anything satisfy it?" depending on the:

A) connective used B) domain of discourse C) name of the variable D) arity of the predicate

Question 3

Over a finite domain $D = \{d_1, \dots, d_n\}$, $\forall x\, P(x)$ is logically equivalent to:

A) $P(d_1) \lor \dots \lor P(d_n)$ B) $P(d_1) \land \dots \land P(d_n)$ C) $P(d_1) \rightarrow \dots \rightarrow P(d_n)$ D) $\neg P(d_1) \land \dots \land \neg P(d_n)$

Question 4

"Some prime is even" is correctly written as:

A) $\exists x\,(\text{Prime}(x) \rightarrow \text{Even}(x))$ B) $\forall x\,(\text{Prime}(x) \land \text{Even}(x))$ C) $\exists x\,(\text{Prime}(x) \land \text{Even}(x))$ D) $\forall x\,(\text{Prime}(x) \rightarrow \text{Even}(x))$

Question 5

"Every positive integer is $\ge 1$" is correctly written as:

A) $\forall x\,(x > 0 \land x \ge 1)$ B) $\forall x\,(x > 0 \rightarrow x \ge 1)$ C) $\exists x\,(x > 0 \rightarrow x \ge 1)$ D) $\exists x\,(x > 0 \land x \ge 1)$

Question 6

The pairing rule for restricted quantifiers is:

A) $\forall$ pairs with $\land$; $\exists$ pairs with $\rightarrow$ B) both pair with $\land$ C) $\forall$ pairs with $\rightarrow$; $\exists$ pairs with $\land$ D) both pair with $\rightarrow$

Question 7

Over the domain of integers, $\forall x\,\exists y\,(x + y = 0)$ is , and $\exists y\,\forall x\,(x + y = 0)$ is .

A) true; true B) true; false C) false; true D) false; false

Question 8

Which pair of statements always says the same thing, for every predicate and domain?

A) $\forall x\,\exists y\,P(x,y)$ and $\exists y\,\forall x\,P(x,y)$ B) $\exists x\,\exists y\,P(x,y)$ and $\exists y\,\exists x\,P(x,y)$ C) $\forall x\,\exists y\,P(x,y)$ and $\exists x\,\forall y\,P(x,y)$ D) none of these

Question 9

The negation $\neg\,\forall x\, P(x)$ is equivalent to:

A) $\forall x\,\neg P(x)$ B) $\exists x\, P(x)$ C) $\exists x\,\neg P(x)$ D) $\neg\exists x\, P(x)$

Question 10

To disprove the universal claim "$\forall x\, P(x)$," it suffices to:

A) prove $P(x)$ for half the domain B) exhibit one element $c$ with $P(c)$ false (a counterexample) C) prove $\forall x\,\neg P(x)$ D) check $P$ on every element, which is always possible

Question 11

The correct negation of $\forall x\,(Q(x) \rightarrow P(x))$ is:

A) $\exists x\,(Q(x) \rightarrow \neg P(x))$ B) $\forall x\,(Q(x) \land \neg P(x))$ C) $\exists x\,(Q(x) \land \neg P(x))$ D) $\exists x\,(\neg Q(x) \land P(x))$

Question 12

Pushing $\neg$ all the way inward, $\neg\,\exists x\,\forall y\, P(x,y)$ becomes:

A) $\forall x\,\exists y\,\neg P(x,y)$ B) $\exists x\,\forall y\,\neg P(x,y)$ C) $\forall x\,\forall y\,\neg P(x,y)$ D) $\exists x\,\exists y\,\neg P(x,y)$

Question 13

In Python, the universal quantifier $\forall x \in D,\ P(x)$ corresponds to:

A) any(P(x) for x in D) B) all(P(x) for x in D) C) sum(P(x) for x in D) D) [P(x) for x in D]

Question 14

all(...) returns False as soon as it meets one falsy element because:

A) it is an optimization unrelated to logic B) a big $\land$ is False the moment one conjunct is False C) all only checks the first element D) it computes a big $\lor$

Question 15 (True/False, justify)

True or false: all(x > 0 for x in []) evaluates to True. Justify in one sentence, naming the principle involved.

Question 16 (True/False, justify)

True or false: If a quantified statement is true over the finite domain range(-5, 6) when checked in code, then it is true over all of $\mathbb{Z}$. Justify in one sentence.

Question 17

In the formula $\forall x\, P(x, y)$, the variable $x$ is ___ and the variable $y$ is ___.

A) bound; bound B) free; bound C) bound; free D) free; free

Question 18

A function's precondition is best described as:

A) the function's guarantee on return B) the caller's obligation that must hold when the function is called C) the loop invariant D) a statement that is always vacuously true

Question 19 (Short answer)

Write the precondition "the list arr is sorted in non-decreasing order" as a single Python expression using all over range.

Question 20 (Short answer)

In one sentence, explain why a finite test suite can never establish a postcondition that is universally quantified over an infinite input domain (theme two).

Answer Key

Topics to review by question