When trying to understand a piece of formal mathematics (e.g. a definition), it's often useful to figure out exactly what its negation is. That is, figure out what conditions make it not true. Wrapping the whole expression in a "not" is technically the negation. But it's usually easier to understand if we move the nots onto individual predicates.
We've already seen how to do this for the four propositional operators:
\(\neg \neg p \equiv p\)
\( \neg (p \rightarrow q) \equiv p \wedge (\neg q)\)
\(\neg(p \wedge q) \equiv (\neg p) \vee (\neg q)\)
\(\neg(p \vee q) \equiv (\neg p) \wedge (\neg q)\)
We also need similar rules for negating the two quantifiers:
\(\neg \forall x, P(x) \equiv \exists x, \neg P(x) \)
\(\neg \exists x, P(x) \equiv \forall x, \neg P(x) \)
Using these 6 rules, we can move a negation from the outside of a statement onto the individual predicates. For example
For any cookie c, if c is not small and c is tasty, then c is not healthy.
First, let's make shorthand for the individual predicates: S(x) is "x is small", T(x) is "x is tasty", H(x) is "x is healthy". Then translate the statement into shorthand so that it's easier to manipulate:
\(\forall c \in \text{cookies}, (\neg S(c) \wedge T(c)) \rightarrow \neg H(c) \)
Then wrap a negation around the statement:
\(\neg \forall c \in \text{cookies}, (\neg S(c) \wedge T(c)) \rightarrow \neg H(c) \)
The outermost operator is the \(\forall\). So move the negation across it:
\(\exists c \in \text{cookies}, \neg ((\neg S(c) \wedge T(c)) \rightarrow \neg H(c)) \)
Now use the rule for negating an if/then statement:
\(\exists c \in \text{cookies}, (\neg S(c) \wedge T(c)) \wedge H(c) \)
Since we have two "and" operators (not a combination of "and" and "or), we can drop the parentheses to make this more readable.
\(\exists c \in \text{cookies}, \neg S(c) \wedge T(c) \wedge H(c) \)
And then translate the sentence back into words:
Negation: There is a cookie c, such that c is not small and c is tasty but c is healthy.
This is a silly example. However, mechanical negation is most useful when you are trying to understand new concepts and when working in situations where it's difficult to understand what's going on. So it's important to be able to do the transformations mechanically, without using your intuitions about the situation.
A useful fact in logic is that an implication \(p \rightarrow q\) is equivalent to its contrapositive \(\neg q \rightarrow \neg p\). (E.g. build the two truth tables.) In practice, this is almost always seen with a universal quantifier: \(\forall x, p(x) \rightarrow q(x) \) is equivalent to \(\forall x, \neg q(x) \rightarrow \neg p(x)\).
Let's start with our cookie claim again:
For any cookie c, if c is not small and c is tasty, then c is not healthy.
\(\forall c \in \text{cookies}, (\neg S(c) \wedge T(c)) \rightarrow \neg H(c) \)
The contrapositive is:
\(\forall c \in \text{cookies}, H(c) \rightarrow \neg (\neg S(c) \wedge T(c)) \)
Simplifying this using De Morgan's Law:
\(\forall c \in \text{cookies}, H(c) \rightarrow S(c) \vee \neg T(c) \)
Translating back into words:
For any cookie c, if c is healthy, then c is small or c is not tasty.
Here's a claim that once appeared on a midterm. Let's try to make its negation and also figure out whether the claim is true.
Claim: \(\forall x,y \in \mathbb{R}\), if x is irrational and y is irrational, then x+y is irrational.
The negation is
\(\neg (\forall x,y \in \mathbb{R}\), if x is irrational and y is irrational, then x+y is irrational).
Moving the negation gradually into the middle of the statement, we get
\(\exists x,y \in \mathbb{R}, \neg \)(if x is irrational and y is irrational, then x+y is irrational).
And then, remembering that an if/then statement is false exactly when the hypothesis is true but the conclusion is false ....
\(\exists x,y \in \mathbb{R}, \) x is irrational and y is irrational and x+y is rational.
So now we know what would make the claim false: a pair of irrational numbers that add up to a rational number.
What are youf favorite irrational numbers? (Normally I'd ask this interactively, so take a sec to think.)
Now how could two irrational numbers add up to something rational? How about setting \(x = \pi \) and \(y = 1- \pi \)? Then \(x + y = 1\), which is rational.