CmSc 180 Discrete mathematics


Negation of Quantifiers

Learning goals
Exam-like questions and problems


General rule for negation of quantified expressions:

  • Change the quantifier
  • Negate the predicate expressions

  1. Negation of universally quantified statements
  2. ~(" x, P(x)), is equivalent to: $ x, (~P(x))

    The statement: "It is not true that all x have the property P"

    is equivalent to: "There is an x for which ~P is true".

    Example:

    ~(" x, P(x) → Q(x) ) ≡ $ x (P(x) Λ ~Q(x))

    The implication is negated by De Morgan's laws, after representing it as a disjunction:

    ~(P(x) → Q(x)) ≡ ~(~P(x) V Q(x)) ≡ P(x) Λ ~Q(x)

    All people are honest: (" x, person(x) → honest(x) )
    Negation: ~(" x, person(x) → honest(x) ) ≡ $ x (person(x) Λ ~honest(x))
    Translation: There is a person that is not honest; Some people are not honest.

    In general P(x) may be a compound expression, e.g. wise(x) V healthy(x), or bird(x) → fly(x).
    Such expressions are negated using the laws of De Morgan.

  3. Negation of existentially quantified statements
  4. ~($ x P(x)) is equivalent to: " x (~ P(x))

    The statement: "It is not true that there is an x with the property P"

    is equivalent to: "No x has the property P" or "All x have the property ~P."

    As with the universal quantifiers, in general P(x) may be a compound expression,
    e.g. wise(x) V healthy(x). Such expressions are negated using the laws of De Morgan.

    ~($ x (D(x) Λ P(x))) ≡ " x (D(x) → ~ P(x))

    The negation is obtained by the following transformations:

    ~$ x (D(x) Λ P(x)) ≡ " x (~(D(x) Λ P(x)) ≡ " x (~D(x) V~ P(x))

    " x (D(x) → ~ P(x))

    Examples:

    1. "Some students are math majors" can be written as:
    2. $ x (student(x) Λ math_major(x))

      The negation would be " No students are math majors":

      " x (student(x) → ~ math_major(x))

    3. "Some horses fly" can be written as:
    4. $ x (horse(x) Λ fly(x))

      The negation would be "No horses fly":

      " x (horse (x) → ~ fly(x))

  5. Summary
    • To negate a quantified expression do the following:
      1. change the quantifier
      2. negate the predicate expression that follows the quantifier.
    • Examples:

      All horses fly:       " x (horse (x) →  fly(x))
      Negation: There is a horse that does not fly: $ x (horse(x) Λ ~fly(x))

      Some horses fly:  $ x (horse(x) Λ fly(x))
      Negation: No horses fly      " x (horse (x) → ~ fly(x))

Learning Goals

  • Know how to write the negation of a quantified expression
    and how to translate the negation in English.

Exam-like problems


Back to CmSc 180 home page
Created by Lydia Sinapova