Skip to main content
Logo image

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.

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”.

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?
A Venn diagram with the collection of cows completely inside the collection of things that eat grass.
In this case, both “all cows eat grass” and “some cows eat grass” are true.
A Venn diagram with the collection of cows only partially overlapping with the collection of things that eat grass.
In this case, both “some cows eat grass” and “some cows do not eat grass” are true.
A Venn diagram with the collection of cows not overlapping at all with the collection of things that eat grass.
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.

Check your understanding.

Use the “cows eat grass” diagrams in Example 4.2.2 to convince yourself that these negation rules are correct.

Worked Example 4.2.5. 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
  1. quantifier negation;
  2. known equivalence \(p\lgccond q \lgcequiv \lgcnot p \lgcor q\text{;}\)
  3. DeMorgan, double negation;
  4. quantifier negation;
  5. quantifier negation; and
  6. DeMorgan, double negation.

Subsection 4.2.2 Distributing quantifiers

Example 4.2.7.

  • 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.8.

  • The universal quantifier \(\forall\) does not distribute over disjunction \(\lgcor\text{.}\)
  • The existential quantifier \(\exists\) does not distribute over conjunction \(\lgcand\text{.}\)

Check your understanding.

  1. 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.
  2. 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.