DEV Community

David Hwang
David Hwang

Posted on

5/24 TIL: Predicates, Quantifiers

Predicates

  • A statement is either TRUE or false. But x > 5 is not a statement until we have the value determined for x.
  • A predicate is a sentence depending on variables which becomes a statement upon substituting values in the domain

Truth Set of a predicate P(x):

{ x ∈ D | P(x) }

  • shows which of the elements in the domain make the predicate true

Universal Quantifier ∀

  • "for all" (every)
  • main use: "quantifying" predicates
  • ∀x ∈ D, P(x) — for all x in the domain, P(x) is true

Existential Quantifier ∃

  • "there exists" (some)
  • ∃x ∈ D, P(x) — there exists x in the domain, such that P(x) is true

Universal/existential quantifiers turn predicates back into a statement

Negating a universal

  • ~(∀x ∈ D, P(x)) ≡ ∃x ∈ D, ~P(x)
  • meaning: if it's not the case that for all values some properties are true, there is at least one value where the property is false

Negating logical statements with multiple quantifiers

∀x ∈ D, P(x)) ≡ ∃

  • Ex) "Every integer has a larger integer"
  • ∀x ∈ Z, P(x) → ∀x ∈ Z, ∃y ∈ Z, y > x -negate→ ∃x ∈ Z, ∀y ∈ Z, y ≤ x

Discussion (0)