CmSc 180 – Discrete mathematics

Negation of Quantifiers

**
**

General rule for negation of quantified expressions:

- Change the quantifier
- Negate the predicate expressions

**Negation of universally quantified statements****Negation of existentially quantified statements**- "Some students are math majors" can be written as:
- "Some horses fly" can be written as:
**Summary**- To negate a quantified expression do the following:
- change the quantifier
- 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))

**
**

**~(" 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)

Negation:

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.

**
**

**~($ ****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:

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

The negation would be "No horses fly":

**
**

Learning Goals

- Know how to write the negation of a quantified expression

and how to translate the negation in English.

Exam-like problems

- Here are some
**problems with solutions**

Back to CmSc 180 home page