Predicates (vị từ)

• Predicate (vị từ) là một biểu thức logic chứa biến, nói về tính chất (property) của biến đó
• Gán biểu thức predicate cho $P(x)$, chưa rõ giá trị đúng/sai cho đến khi gán giá trị cụ thể cho biến đó.
• $P(x)$ is called propositional function

Quantifier (lượng từ)

Universal quantifier ($\mathrm{\forall }$)

• Universal quantification of a $P(x)$ is

$P(x)$ for all values of x in a domain

• Notation $\mathrm{\forall }xP(x)$ :
  • For every $xP(x)$
  • For all $xP(x)$
  • For each, for any, for arbitrary, …

Existential quantifier ($\mathrm{\exists }$)

• Existential quantification of a $P(x)$ is

There exists an element x in a domain such that $P(x)$

• Notation $\mathrm{\exists }xP(x)$ :
  • There is an x such that $P(x)$
  • There is at least one x ….
  • For some $xP(x)$

The uniqueness quantifier (Skipped)

Precedence of Quantifier

• The quantifiers ∀ and ∃ have higher precedence than all logical operators from propositional calculus

Quantifier with restricted domain

• The restriction of universal quantification $(\mathrm{\forall })$ is the same as the universal quantification of a conditional statement
  • $\mathrm{\forall }x<0(x^2>0)\iff \mathrm{\forall }x(x<0\to x^2>0)$
• The restriction of existential quantification is the same as the existential quantification of a conjunction $(\wedge )$
  • $\mathrm{\exists }x>0(x^2=0)\iff \mathrm{\exists }x(x>0\wedge x^2=0)$

Logical Equivalences Involving Quantifiers

• Statements involving predicates and quantifiers are logically equivalent, if and only if they have the same true value, no matter:
  • which predicates are substituted into
  • which domain of discourse is used?
• $S\equiv T$
• Example:
  • $\mathrm{\forall }x(P(x)\wedge Q(x))\equiv \mathrm{\forall }xP(x)\wedge \mathrm{\forall }xQ(x))$

Negating Quantified Expressions

Nested Quantifiers

• $\mathrm{\forall }x\mathrm{\forall }y(x+y=y+x)$ : for all real numbers x and y, x + y = y + x
• $\forall x\forall y((x>0)\wedge (y<0)\to (xy<0))$ : For all real numbers x and y, if x is positive and y is negative, then the product of x and y is negative

INFO

Think of nested quantifiers like a 2 NESTED LOOP IN PROGRAMMING

The Order of Quantifiers

Negating nested quantifier

• Apply De Morgan’s Laws for negating, just apply from left → right in propositions

Quantifiers: at least, at most, exactly

Setup

Let P(x) be a predicate over a domain.

---

1. At least n

Meaning

There are at least n distinct elements satisfying P.

Form (example n = 2)

$$\exists x\exists y(x\ne y\wedge P(x)\wedge P(y))$$

General pattern

• Use n existential quantifiers (∃)
• Add pairwise distinct conditions (≠)

---

2. At most n

Meaning

There are no more than n elements satisfying P.

Form (example n = 1)

$$\forall x\forall y((P(x)\wedge P(y))\to x=y)$$

Form (example n = 2)

$$\forall x\forall y\forall z((P(x)\wedge P(y)\wedge P(z))\to (x=y\vee x=z\vee y=z))$$

General pattern

• Use universal quantifiers (∀)
• If n+1 elements satisfy P → at least two must be equal

---

3. Exactly n

Meaning

There are exactly n elements satisfying P.

Form

TIP

(at least n) $\wedge$ (at most n)

---

Example: Exactly 2

$$\exists x\exists y(x\ne y\wedge P(x)\wedge P(y))$$$$\wedge$$$$\forall x\forall y\forall z((P(x)\wedge P(y)\wedge P(z))\to (x=y\vee x=z\vee y=z))$$

---

Special case: Exactly 1 (unique existence)

$$\exists x(P(x)\wedge \forall y(P(y)\to y=x))$$

---

Quick cheat sheet

• at least n -> $\exists n$ distinct elements
• at most n -> not exist $n+1$ distinct elements
• exactly n -> (≥ n) $\wedge$ (≤ n)