General rule for negation of quantified expressions:

• Change the quantifier
• Negate the predicate expressions

1. Negation of universally quantified statements

~(" 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.

2. Negation of existentially quantified statements

~($ 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:
$ x (student(x) Λ math_major(x))

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

" x (student(x) → ~ math_major(x))
2. "Some horses fly" can be written as:
$ x (horse(x) Λ fly(x))

The negation would be "No horses fly":

" x (horse (x) → ~ fly(x))
3. 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))