Negating Logic Statements: How to Say “Not”

Last time, I started a series exploring aspects of the translation of English statements to or from formal logical terms and symbols, which will lead to discussions of converse and contrapositive, and eventually of logical arguments. We’ve looked at how to translate concepts of “or” (disjunction) and “if” (conditional); but our goals will also require negation: expressing the fact that something is not true. Like everything else in English and in logic, there are a few slippery spots in the process.

What does negation mean?

As usual, I’ll start with a fairly basic question to set the stage, this one from 1998:

Negating Statements

What is negation? My math teacher gave me some problems on it: "4 + 3 * 5 = 35" and "Violins are members of the string family." 

I've asked my parents about it and they don't know.

Heather has been asked to “negate” these statements; what does that mean? Doctor Teeple started with the concept of a statement:

To negate a statement, you write the opposite of what the statement says. But before we talk about the opposite of a statement, let's talk about the statements themselves. 

A statement is pretty much what it sounds like it should be. It's an equation or sentence or a declaration of some sort. It doesn't matter whether the statement is true or false; we still consider it to be a statement. For example, I could say, "The sky is purple" or "The earth is flat." Both of those are statements. I could say, "The U.S. is in North America" or "Giraffes are not short." Those are also statements. 

We can negate each of these statements by writing the opposite of what it says. So for example, the negation of "The sky is purple" is "The sky is not purple." The negation of "Giraffes are not short" is "Giraffes are short."

So, the negation of a statement is a statement that says the first one is not true. If the original was a true statement, the new one will be false, and vice versa. (Do you see why Doctor Teeple started out by emphasizing that a statement doesn’t have to be true?)

We make statements and negate them without judging whether they are true or false. That is another issue. But once we are given that a statement is true or false, we can note what happens to the statement when we negate it. For example, suppose we know the following: 

   "The sky is purple."               False
   "Giraffes are not short."          True

We negated these and got the following:

   "The sky is not purple."           True     
   "Giraffes are short."              False 

Notice what happened. Negation turns a true statement into a false statement and a false statement into a true statement.

So one way to check whether your answer is correct is to determine whether each of the pair is true (either in reality, or under some assumed reality); if they have the same truth value, then the second can’t be the negation of the first.

Now, all of the statements we have been working with are sentences. We can also do this with math equations. Here are some statements:

   6 * 3 = 18
   4 + 3*2 > 15
   15/7 = 12
   12 + 1 <= 13   (where <= means less than or equal to)            

Some of them are true and some are false, but that is a side issue; we can negate them either way. So here are the negations of the above statements:

   6 * 3 =/ 18     (where =/ means not equal to)
   4 + 3*2 <= 15
   15/7 =/ 12
   12 + 1 > 13

That's all there is to negating statements.

In English, we typically add the word “not”, or some equivalent; in symbols, we replace “=” with “\(\ne\)“, “>” with “\(\le\)“, “\(\ge\)” with “<“, and so on.

This should be enough for Heather to answer her own questions. Since enough time has passed, it’s okay to give the answers here:

• The negation of “\(4 + 3 \times 5 = 35\)” is “\(4 + 3 \times 5 \ne 35\)“.
• The negation of “Violins are members of the string family” is “Violins are not members of the string family”.

I want to warn you to be on the watch for statements that contain words like "for every," "for all," or "there exists." Negations of these types of statements can be tricky. Here's an entry in the Dr. Math archives that might help:

This leads us to the next question, from 1996:

Negating quantifiers (all, some, none)

Negation in Logic

What is the negation of the sentence "In every village, there is a person who knows everybody else in that village."?

My guess is "In at least one village, there is at least one person who knows at least one person in that village."

Am I close at all?

Words like “every”, “at least one”, “some”, “there exists a”, or “none”, are called “quantifiers”, because they tell how many of something there are. They are particularly tricky to negate.

Doctor Mike saw that Thomas needs to start simpler, so he turned the latter part of the statement temporarily into a single phrase, which can be a very helpful technique:

Close, but not quite there.  Think of it this way.  If you use "special person" to mean a person who knows everyone in his/her village, then the original sentence becomes: 

  "Every village has a special person." 

The negation would then be : 
  "Some village does NOT have a special person."

Notice how we can’t just stick in a “not” (unless you take the easy way out and say “It is not true that every village has a special person”). If this is not true of every village, then there must be at least one village for which it is not true. “Not every” means “at least one does not”, or equivalently, “some do not”. Thomas got this part right.

Now we need to expand the “special person” part, recalling that we temporarily defined it as “a person who knows everyone”:

So what does it mean for a village not to have a special person?  It means that every person in that village could be matched up with some person that he/she does not already know.  The negation should be: 

  "In at least one village,
  each person does not know everyone else."

or perhaps something like: 

  "In at least one village,
  and for every person in that village,
  that person does not know everybody." 

or alternatively: 

  "There exists a village,
  such that for every person in that village,
  there is another person that the first person does not know."

Each of these is a little awkward; you have to read them carefully. In the first, we aren’t just saying that “not everyone knows everyone else,” but more strongly, “each person has someone they don’t know.” The second says this explicitly, but not quite in everyday language (it reads more like a logician wrote it).  The third is even more “logicianese,” with phrases like “there exists” and “such that”. But the goal here is to write precisely, because that’s what we need in logic.

In plain English, the clearest wording might be, “In some village, no one knows everyone else.” Here I negated the inner phrase by replacing, in effect, “there is” with “there is no.”

So, what is the general procedure for doing this?

In general, for language exercises like this, there are two basic rules. The negation of a sentence like "For every...there exists a...such that X is true." is a sentence like "There exists a...such that for all...X is false.".  (The other basic rule is the reverse of this.)  

It is also often easier to see what is happening if some symbols are used.  See if you follow the symbolic version below for the sentence and the negation. 
 
  "For all V, there is a P in V,
  such that for all Q in V, P knows Q."
  
  "There is a V, such that for every P in V,
  there is a Q in V such that P does not know Q."

More generally, perhaps, we can say this:

• The negation of “For all A, p” is “For some A, not p”.
• The negation of “For some A, p” is “For no A, p”, or “For all A, not p”.
• The negation of “For no A, p” is “For some A, not p”.

We applied the first rule to the first part of the statement, which required then negating the inner part, for which we can apply the second rule. I applied the first version of the second rule; Doctor Mike applied the second version, probably because he was assuming that the ultimate goal is a symbolic statement, where only “some” and “all” (existence and universality) are allowed, with no special symbol for “none”.

Negating conjunctions (and)

Another common difficulty arises when we want to negate a compound sentence using “and” or “or”. Here is a question about the former, from 2003:

Distributing 'Not' over a Conjunction

If 

  p = today is sunny 

and 

  q = tomorrow is Friday 

then which of the following means "It is not true that today is sunny and tomorrow is Friday"? 

  1. not (p^q) or 
  2. not p ^ q

I'm not sure whether "it is not true" in front of a conjunction applies to both conjuncts or only the first one.

This is mostly a question of English grammar. Doctor Achilles focused on that:

Translations are always tricky.  However, I would say that "it is not true that ..." means that the negation applies to everything that follows.

Contrast 

  It is not true that today is sunny and tomorrow is Friday

with 

  Today is not sunny and tomorrow is Friday

In the sentence I just made up, the 'not' is only in the first clause, and so only applies to 'p'.  In your sentence, the 'not' governs the whole thing, so should apply to 'p' and 'q'.

So the correct translation is

  not (p^q)

I hope this helps.  If you have other questions or you'd like to talk about this some more, please write back.

Note that if the statement was, “It is not true that today is sunny, and tomorrow is Friday,” we would translate this as “\((\lnot p) \wedge q\);” the comma serves as a parenthesis in English.

We could have also brought up the fact that \(\lnot(p \wedge q)\) doesn’t mean the same thing as \(\lnot p \wedge \lnot q\); if you did want to “distribute” the negation, you would have to follow deMorgan’s Law and change the and to an or: \(\lnot p \vee \lnot q\) (“Today is not sunny, or tomorrow is not Friday”). But I suspect that Sarah already knew that.

Negating “At least two”

Let’s look at one more question, from 2010, that touches on our topic for next time, contrapositives:

Negating a Quantifier

I have to write the converse, inverse, and contrapositive of this conditional statement:

   If a triangle is isosceles,
   then it has at least two congruent sides.

I know that

                p: a triangle is isosceles
                q: the triangle has at least two congruent sides
        statement: if p then q 
         converse: if q then p 
          inverse: if not p then not q 
   contrapositive: if not q then not p 

So

   Converse: If a triangle has at least two congruent sides,
   then the triangle is isosceles.

But what is the negation of "at least two"? Is it "none"? or "at most two," as in

   Inverse: If a triangle is not isosceles,
   then it has at most two congruent sides.

   Contrapositive: If a triangle has at most two congruent sides,
   then it's not an isosceles.

In order to write the inverse and the contrapositive, Marianne has to negate the two statements, “a triangle is isosceles,” and “it has at least two congruent sides”. The first is easy; the second, though not quite the same as the quantifiers in an earlier question, is very similar: What is the negation of “at least two”, considering that the negation of “at least one” is “none”?

I answered, focusing on the meaning of the specific statement, keeping in mind that a triangle has only three sides, and that it makes no sense to talk about having “one congruent side”:

Just consider the cases. It either has none, or two, or three:

   Number of
congruent sides    At least 2?    At most 2?    None?
---------------    -----------    ----------    -----
       0                F             T           T
       2                T             T           F
       3                T             F           F

Which column is the negation of "at least 2"? The one that switches every falsehood to a truth and every truth to a falsehood -- the one titled "None?"

So, the negation of “at least two congruent sides” is “no congruent sides”. If we chose “at most two”, both the original and the purported negation would be true when there are two congruent sides.

Rather than making a table, we could do this:

There are other ways to come up with this fact. You might write it as an inequality.

   N is at least 2
   
means

   N >= 2
   
The negation of that is

   N < 2
   
which in turn means 0 or 1. Since a triangle can't have "one congruent side," that really means none.

The negation of “greater than or equal” is “less than.” It would be valid to say, “less than two congruent sides,” but that might confuse readers.

Or, by the same reasoning as the last sentence, if a triangle does NOT have at least two congruent sides, then it has none. Saying it has two congruent sides means it has a PAIR of congruent sides, and if it doesn't have at least one pair, then it has none.

So your inverse and contrapositive are wrong. (You could also directly check them: the contrapositive should be true, but if you make a triangle that has at most two congruent sides, it might have two, and WILL be isosceles.)

Next time, we’ll look at the converse, inverse, and contrapositive themselves, which is the reason we had to look at negation.