Skip to content

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 (∀) ​

  • Universal quantification of a P(x) is

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

  • Notation ∀xP(x) :
    • For every xP(x)
    • For all xP(x)
    • For each, for any, for arbitrary, …

Existential quantifier (∃) ​

  • Existential quantification of a P(x) is

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

  • Notation ∃xP(x) :
    • There is an x such that P(x)
    • There is at least one x ….
    • For some xP(x)

The uniqueness quantifier (Skipped) ​

image.png

Precedence of Quantifier ​

Quantifier with restricted domain ​

  • The restriction of universal quantification (∀) is the same as the universal quantification of a conditional statement
    • ∀x<0(x2>0)⇔∀x(x<0→x2>0)
  • The restriction of existential quantification is the same as the existential quantification of a conjunction (∧)
    • ∃x>0(x2=0)⇔∃x(x>0∧x2=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≡T
  • Example:
    • ∀x(P(x)∧Q(x))≡∀xP(x)∧∀xQ(x))

Negating Quantified Expressions ​

image.png

Nested Quantifiers ​

  • ∀x∀y(x+y=y+x) : for all real numbers x and y, x + y = y + x
  • ∀x∀y((x>0)∧(y<0)→(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 ​

image.png

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) ​

∃x∃y(x≠y∧P(x)∧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) ​

∀x∀y((P(x)∧P(y))→x=y)

Form (example n = 2) ​

∀x∀y∀z((P(x)∧P(y)∧P(z))→(x=y∨x=z∨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) ∧ (at most n)


Example: Exactly 2 ​

∃x∃y(x≠y∧P(x)∧P(y))∧∀x∀y∀z((P(x)∧P(y)∧P(z))→(x=y∨x=z∨y=z))

Special case: Exactly 1 (unique existence) ​

∃x(P(x)∧∀y(P(y)→y=x))

Quick cheat sheet ​

  • at least n -> ∃n distinct elements
  • at most n -> not exist n+1 distinct elements
  • exactly n -> (≥ n) ∧ (≤ n)

Built with ❤️ and curiosity