Question

Express each of these statements using quantifiers. Then form the negation of the statement so that no negation is to the left of a quantifier. Next, express the negation in simple English. (Do not simply use the phrase “It is not the case that.”)

a) All dogs have fleas.

b) There is a horse that can add.

c) Every koala can climb.

d) No monkey can speak French.

e) There exists a pig that can swim and catch fish.

Short answer

a) There is a dog that does not have fleas.

b) All horses cannot add.

c) There is a koala that cannot climb.

d) A monkey can speak French.

e) All pigs cannot swim or not catch fish.

Step-by-step solution

INTERPRETATION SYMBOLS

Negation $\mathbf{\neg }\mathbf{p}$: not p

Conjunction$\mathbf{p}\mathbf{\wedge }\mathbf{q}\mathbf{:}\mathbf{p}$ and q

Existential quantification $\exists \mathbf{xP}\mathbf{\left(}\mathbf{x}\mathbf{\right)}$: There exists an element xin the domain such that P(x).

Universal $\mathbf{\forall }\mathbf{xP}\mathbf{\left(}\mathbf{x}\mathbf{\right)}\mathbf{:}\mathbf{P}\mathbf{\left(}\mathbf{x}\mathbf{\right)}$quantification for all values of x in the domain.

LOGICAL EQUIVALENCES

Double negation law:

$\mathbf{\neg }\mathbf{(}\mathbf{\neg }\mathbf{p}\mathbf{)}\mathbf{\equiv }\mathbf{p}$

De Morgan's laws:

$$\begin{gathered} \mathbf{\neg }\mathbf{(}\mathbf{p}\mathbf{\wedge }\mathbf{q}\mathbf{)}\mathbf{\equiv }\mathbf{\neg }\mathbf{p}\mathbf{\vee }\mathbf{\neg }\mathbf{q} \\ \mathbf{\neg }\mathbf{(}\mathbf{p}\mathbf{\vee }\mathbf{q}\mathbf{)}\mathbf{\equiv }\mathbf{\neg }\mathbf{p}\mathbf{\wedge }\mathbf{\neg }\mathbf{q} \end{gathered}$$

De Morgan's Laws for Qualifiers:

$$\begin{gathered} \mathbf{\neg }\exists \mathbf{xP}\mathbf{\left(}\mathbf{x}\mathbf{\right)}\mathbf{\equiv }\mathbf{\forall }\mathbf{x}\mathbf{\neg }\mathbf{P}\mathbf{\left(}\mathbf{x}\mathbf{\right)} \\ \mathbf{\neg }\mathbf{\forall }\mathbf{xP}\mathbf{\left(}\mathbf{x}\mathbf{\right)}\mathbf{\equiv }\exists \mathbf{x}\mathbf{\neg }\mathbf{P}\mathbf{\left(}\mathbf{x}\mathbf{\right)} \end{gathered}$$

¬(∀xP(x))≡∃x¬P(x)

Let the domain be dogs andP(x)mean "xhas fleas". We can then rewrite the given statement as:

$\mathbf{\forall }\mathbf{xP}\mathbf{\left(}\mathbf{x}\mathbf{\right)}$

The negation is then by De Morgan's Law for Qualifiers:

$\neg \mathbf{(}\mathbf{\forall }\mathbf{xP}\mathbf{(}\mathbf{x}\mathbf{)}\mathbf{\equiv }\exists \mathbf{x}\neg \mathbf{P}\mathbf{(}\mathbf{x}\mathbf{)}$

This means: There is a dog that does not have fleas.

b) Let the domain be horses and Q(x) mean "x can add". We can then rewrite the given statement as:

$\exists \mathbf{xQ}\mathbf{\left(}\mathbf{x}\mathbf{\right)}$

The negation is then by De Morgan's Law for Qualifiers:

$\mathbf{\neg }\mathbf{(}\exists \mathbf{xQ}\mathbf{(}\mathbf{x}\mathbf{\left)}\mathbf{\right)}\mathbf{\equiv }\mathbf{\forall }\mathbf{x}\mathbf{\neg }\mathbf{Q}\mathbf{\left(}\mathbf{x}\mathbf{\right)}$

This means: All horses can not add.

∀xR(x)

c) Let the domain be koalas and R(x)mean "x can climb". We can then rewrite the given statement as:

$\mathbf{\forall }\mathbf{xR}\mathbf{\left(}\mathbf{x}\mathbf{\right)}$

The negation is then by De Morgan's Law for Qualifiers:

$\mathbf{\neg }\mathbf{(}\mathbf{\forall }\mathbf{xR}\mathbf{(}\mathbf{x}\mathbf{)}\mathbf{\equiv }\exists \mathbf{x}\mathbf{\neg }\mathbf{R}\mathbf{(}\mathbf{x}\mathbf{)}$

This means: There is a koala that cannot climb.

∀x(¬S(x))

d) Let the domain be monkeys andS(x)mean "xcan speak French". We can then rewrite the given statement as "every monkey cannot speak French":

$\mathbf{\forall }\mathbf{x}\mathbf{(}\mathbf{\neg }\mathbf{S}\mathbf{(}\mathbf{x}\mathbf{\left)}\mathbf{\right)}$

The negation is then by De Morgan's Law for Qualifiers and the double negation law:

$\mathbf{\neg }\mathbf{(}\mathbf{\forall }\mathbf{x}\mathbf{(}\mathbf{\neg }\mathbf{s}\mathbf{\left(}\mathbf{x}\mathbf{\right)}\mathbf{\left)}\mathbf{\right)}\mathbf{\equiv }\exists \mathbf{x}\mathbf{\neg }\mathbf{(}\mathbf{\neg }\mathbf{S}\mathbf{(}\mathbf{x}\mathbf{\left)}\mathbf{\right)}\mathbf{\equiv }\exists \mathbf{xS}\mathbf{\left(}\mathbf{x}\mathbf{\right)}$

This means: A monkey can speak French.

∃x(T(x)∧U(x))

e) Let the domain be pigs and T(x) mean "xcan swim" and U(x)mean "x can catch fish". We can then rewrite the given statement as:

$\exists \mathbf{x}\mathbf{\left(}\mathbf{T}\mathbf{\right(}\mathbf{x}\mathbf{)}\mathbf{\wedge }\mathbf{U}\mathbf{(}\mathbf{x}\mathbf{\left)}\mathbf{\right)}$

The negation is then by De Morgan's Law for Qualifiers and the regular De Morgan's Law:

$$\begin{gathered} \mathbf{\neg }\exists \mathbf{x}\mathbf{\left(}\mathbf{T}\mathbf{\right(}\mathbf{x}\mathbf{)}\mathbf{\wedge }\mathbf{U}\mathbf{(}\mathbf{x}\mathbf{\left)}\mathbf{\right)}\mathbf{)}\mathbf{\equiv }\mathbf{\forall }\mathbf{x}\mathbf{\neg }\mathbf{(}\mathbf{T}\mathbf{\left(}\mathbf{x}\mathbf{\right)}\mathbf{\wedge }\mathbf{U}\mathbf{\left(}\mathbf{x}\mathbf{\right)}\mathbf{)} \\ \mathbf{\equiv }\mathbf{\forall }\mathbf{x}\mathbf{(}\mathbf{\neg }\mathbf{T}\mathbf{\left(}\mathbf{x}\mathbf{\right)}\mathbf{\vee }\mathbf{\neg }\mathbf{U}\mathbf{\left(}\mathbf{x}\mathbf{\right)}\mathbf{)} \end{gathered}$$

This means: All pigs cannot swim or not catch fish.