Training Set Theory & Logic Quantifiers & Predicate Logic
3 / 5

Quantifiers & Predicate Logic

24 min Set Theory & Logic

Quantifiers & Predicate Logic

Predicate

A statement containing a variable: $P(x)$ = "$x$ is even." Becomes a proposition when $x$ is assigned a value or quantified.

Quantifiers
  • Universal: $\forall x\, P(x)$ — "For all $x$, $P(x)$"
  • Existential: $\exists x\, P(x)$ — "There exists an $x$ such that $P(x)$"
Negating Quantifiers

$$\lnot (\forall x\, P(x)) \equiv \exists x\, \lnot P(x)$$

$$\lnot (\exists x\, P(x)) \equiv \forall x\, \lnot P(x)$$

Example 1

Symbolize: "Every integer is either even or odd."

$\forall n \in \mathbb{Z}, \; (2 \mid n) \lor (2 \nmid n)$.

Example 2

Negate: "All students passed the exam."

Original: $\forall s\, P(s)$. Negation: $\exists s\, \lnot P(s)$ — "Some student did not pass."

Example 3

Negate: $\exists x\,(x^2 < 0)$.

$\forall x\,(x^2 \geq 0)$ — true for real numbers.

Practice Problems

1. Symbolize: "There exists a prime number greater than 100."
2. Negate: $\forall x\,(x > 0)$.
3. Is $\forall x \in \mathbb{R},\, x^2 \geq 0$ true?
4. Negate: "No dog can fly."
5. Symbolize: "For every $\epsilon > 0$, there exists $\delta > 0$..."
6. True or false: $\exists x \in \mathbb{R},\, x^2 = -1$.
7. Negate: $\exists x\, (x > 5 \land x < 3)$.
8. What is the domain of discourse?
9. Translate: $\forall x\, (P(x) \to Q(x))$.
10. Negate: $\forall x\, \exists y\, (x+y=0)$.
11. Is $\exists x\, (x = x+1)$ true for reals?
12. Write using quantifiers: "Between any two reals there is a rational."
Show Answer Key

1. $\exists p\,(\text{prime}(p) \land p > 100)$

2. $\exists x\,(x \leq 0)$

3. True

4. "There is a dog that can fly." ($\exists d\, F(d)$)

5. $\forall \epsilon > 0\, \exists \delta > 0\, ...$

6. False (in $\mathbb{R}$)

7. $\forall x\, (x \leq 5 \lor x \geq 3)$

8. The set of values $x$ can take

9. "For all $x$, if $P(x)$ then $Q(x)$"

10. $\exists x\, \forall y\, (x+y \neq 0)$

11. False

12. $\forall a,b \in \mathbb{R}\,(a < b \to \exists q \in \mathbb{Q},\, a < q < b)$

Propositional Logic & Truth Tables Methods of Proof