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