Warning 4.2.1.
The negation of the statement “all X are Y” is not “no X are Y” nor “all X are not Y”.
Section 4.2 Manipulating quantified statements
Subsection 4.2.1 Negation of quantified statements
Negating quantified statements in English can be tricky, but we will establish rules that make it easy in symbolic logic.
Example 4.2.2.
What is the negation of the statement “all cows eat grass”? To avoid making the mistake in the preceding warning, consider the following question: what is the minimum number of cows that do not eat grass that can be used as evidence to demonstrate that the statement “all cows eat grass” is false?
In this case, both “all cows eat grass” and “some cows eat grass” are true.
In this case, both “some cows eat grass” and “some cows do not eat grass” are true.
In this case, each of “no cows eat grass”, “all cows do not eat grass”, and “some cows do not eat grass” are true.
It takes just one lasagna-eating cow to make “all cows eat grass” false, so the negation of “all cows eat grass” is “some cows do not eat grass” or “at least one cow does not eat grass”.
Warning 4.2.3.
We have indicated that the statement “some cows eat grass” is technically true in the first diagram in Example 4.2.2, even though it is more precise to say “all cows eat grass” in that situation. Similarly, we have indicated that the statement “some cows do not eat grass” is technically true in the third diagram. Remember that truth and falsity are usually all that matter in logic, not necessarily making the most precise statement possible.
Proposition 4.2.4. Rules for negation of quantifiers.
Let \(A(x) \) represent a predicate in the variable \(x \text{.}\)
-
Universal negation.
The negation of \((\forall x)A(x) \) is \((\exists x)(\lgcnot A(x)) \text{.}\)
-
Existential negation.
The negation of \((\exists x)A(x) \) is \((\forall x)(\lgcnot A(x)) \text{.}\)
Checkpoint 4.2.5.
Use the “cows eat grass” diagrams in Example 4.2.2 to convince yourself that these negation rules are correct.
Worked Example 4.2.6. Negating a quantified statement.
Determine and “simplify” the negation of
\begin{equation*}
(\forall x)\left(
A(x) \lgccond \Bbrac{
(\exists y)(\forall z)\bbrac{
B(y)\lgcand \lgcnot C(z)
}
}
\right)\text{.}
\end{equation*}
Solution.
Using the rules of quantifier negation and known logical equivalences, we can perform the following manipulations:
\begin{align*}
\amp
\lgcnot (\forall x) \Bbrac{
A(x) \lgccond (\exists y)(\forall z)\bbrac{ B(y)\lgcand \lgcnot C(z) }
}\\
\amp\lgcequiv
(\exists x) \lgcnot \Bbrac{
A(x) \lgccond (\exists y)(\forall z)\bbrac{ B(y)\lgcand \lgcnot C(z) }
}
\amp \amp \text{(i)}\\
\amp\lgcequiv
(\exists x) \lgcnot \Bbrac{
\lgcnot A(x) \lgcor (\exists y)(\forall z)\bbrac{ B(y)\lgcand \lgcnot C(z) }
}
\amp \amp \text{(ii)}\\
\amp\lgcequiv
(\exists x) \Bbrac{
A(x) \lgcand \lgcnot (\exists y)(\forall z)\bbrac{ B(y)\lgcand \lgcnot C(z) }
}
\amp \amp \text{(iii)}\\
\amp\lgcequiv
(\exists x) \Bbrac{
A(x) \lgcand (\forall y)\lgcnot(\forall z)\bbrac{ B(y)\lgcand \lgcnot C(z) }
}
\amp \amp \text{(iv)}\\
\amp\lgcequiv
(\exists x) \Bbrac{
A(x) \lgcand (\forall y)(\exists z) \lgcnot \bbrac{ B(y)\lgcand \lgcnot C(z) }
}
\amp \amp \text{(v)}\\
\amp\lgcequiv
(\exists x) \Bbrac{
A(x) \lgcand (\forall y)(\exists z)\bbrac{ \lgcnot B(y)\lgcor C(z) }
}
\amp \amp \text{(vi)}
\end{align*}
with justifications
-
quantifier negation;
-
known equivalence \(p\lgccond q \lgcequiv \lgcnot p \lgcor q \text{;}\)
-
DeMorgan, double negation;
-
quantifier negation;
-
quantifier negation; and
-
DeMorgan, double negation.
Subsection 4.2.2 Distributing quantifiers
Proposition 4.2.7. Rules for distributing quantifiers.
Let \(A(x),B(x) \) represent predicates in the variable \(x \text{.}\)
-
Universal distributes across conjunction.
\(\displaystyle (\forall x)\bbrac{A(x) \lgcand B(x)} \lgcequiv (\forall x)A(x) \lgcand (\forall x)B(x) \)
-
Existential distributes across disjunction.
\(\displaystyle (\exists x)\bbrac{A(x) \lgcor B(x)} \lgcequiv (\exists x)A(x) \lgcor (\exists x)B(x) \)
Example 4.2.8.
-
The statement “every vegetable is delicious and nutritious” is the same as saying “every vegetable is delicious and every vegetable is nutritious”.
-
The statement “at least one vegetable in the garden is rotten or nibbled by squirrels” is the same as saying “at least one vegetable in the garden is rotten or at least one vegetable in the garden is nibbled by squirrels”.
Warning 4.2.9.
-
The universal quantifier \(\forall \) does not distribute over disjunction \(\lgcor \text{.}\)
-
The existential quantifier \(\exists \) does not distribute over conjunction \(\lgcand \text{.}\)
Checkpoint 4.2.10.
(a)
Create an example of predicates \(A(x) \) and \(B(x) \) such that, of the statements
\begin{align*}
(\forall x) \amp \bbrac{A(x) \lgcor B(x)} \text{,} \amp
(\forall x) A(x) \amp \lgcor (\forall x)B(x) \text{,}
\end{align*}
the first is true but the second is false.
(b)
Create an example of predicates \(A(x) \) and \(B(x) \) such that, of the statements
\begin{align*}
(\exists x) \amp \bbrac{A(x) \lgcand B(x)} \text{,} \amp
(\exists x) A(x) \amp \lgcand (\exists x)B(x) \text{,}
\end{align*}
the first is false but the second is true.
