4

Consider the statement

At least two of my library books are overdue.

I am trying to understand what the negation of this statement would be. I have a couple guesses:

  • Less than two of my library books are overdue
  • At least two of my library books are not overdue

Are there any rules to determine exactly what the correct negation is? In general, I have learned to switch the quantifier (e.g. "for all" becomes "there exists" vice versa) and negate the verb (e.g. "equals" becomes "does not equal"). But I'm not sure how this applies to an "at least" statement.

4

First, you will need to formalise that sentence. There are some different possibilities. Let's first define the set B of my library books and the predicate D(b:B) which is true iff book b is overdue.

Propositional logic

In propositional logic, the whole sentence would be an atomic expression. It cannot be split up into smaller parts. We would have:

T : #{b : b ∈ B, D(b)} ≥ 2  – the number of elements in the set of books that are overdue is ≥ 2

With the trivial negation ¬ T ≡ ¬ (#{b : b ∈ B, D(b)} ≥ 2) ≡ #{b : b ∈ B, D(b)} < 2. Translating that back to natural language you'd get "Less than two of my library books overdue" (this was your first guess).

Note: this method is the same as what Alf does in his answer, with N = #{b : b ∈ B, D(b)}.

First order predicate logic

In first order predicate logic, you could formalise the sentence in a different way. We could say:

∃ b1:B, ∃ b2:B, b1 ≠ b2 ∧ D(b1) ∧ D(b2)  – there is some book b1 and b2 which are not equal and are both overdue

The negation of that, ¬ ∃ b1:B, ∃ b2:B, b1 ≠ b2 ∧ D(b1) ∧ D(b2) ≡ ∀ b1:B, ∄ b2:B, b1 ≠ b2 ∧ D(b1) ∧ D(b2). This translates into natural language into "For all books b1 there does not exist a book b2 such that it is unequal to b1 and both are overdue". A more understandable but less strict version could be "For all overdue books there does not exist a different book that is also overdue".

Of course, there are always different ways to say the same thing. The expression ∀ b1:B, D(b1) → (∀ b2:B, D(b2) → b2 = b1)), which means "for all books b1 it holds that if they are overdue, it holds for all books that if they are overdue they are equal to b1".

What to remember from this?

There are (almost?) always different ways to say the same thing in natural language or in formal language (in formal language we call these equivalences). The negation of a sentence depends 1) on the formal language you're using (here I used propositional and first order predicate logic) and 2) on the rules you're using for negating expressions.

A very faint example would be that "It is not true that at least two of my library books are overdue" is also a correct negation of your expression. Whether it is an acceptable one, is up to (or your professor).

Your guesses

Less than two of my library books are overdue

This would work. It is the negation I showed under the heading 'propositional logic'.

At least two of my library books are not overdue

This would not work. Suppose you have ten books, five of which are overdue, and five not. The sentence "At least two of my library books are overdue" is true, as is "At least two of my library books are not overdue".

You always have to apply the negation to the outermost part of the expression you're negating. Here, you put the negation somewhere inside, which causes problems.

1
  • Wow - fantastically answered. I never expected I would get such a thorough explanation, which I appreciate. You put a lot of great information here, especially the part about formal language, rules, and the distinction between "first order" and "propositional" logic. This is right along the line of material I want to study in mathematical logic this summer. I am sure I will be back to read this post again soon. Thank you very much! May 28 '15 at 22:30
6

Let N denote "N books are overdue". Then the first statement is

N ≥ 2

The negation of “≥” is “<”, hence

not( N ≥ 2 ) ≡ (N < 2) ≡ (N ≤ 1)


Hence, the negation of the statement

At least two of my library books are overdue.

is

At most one of my library books are overdue.


It's also possible to derive this in more complex ways.

1
  • 1
    I really like how you were able to simplify the statement by first defining N as the number of books overdue, so that the statement became something we know how to negate, i.e. N ≥2. I wish I had been able to think of that myself! (Hopefully next time I'll recognize it.) Thank you very much for the help! May 28 '15 at 22:36
3

An easy way to decide between your two guesses is to interpret your statement featuring "At Least" as an "or" statement where two quantified judgements are being made. You can read "At least two library books are overdue" as "Either two library books are overdue, or more than two library books are overdue".

When you do this, you can see the behaviour of negation as an instance of a De Morgan law in boolean algebra. So the condition for the negation of the above would be that which satisfies both "it's not the case that more than two library books are overdue" and "it's not the case that two library books are overdue", which means it's got to be strictly less than two.

2
  • Uhm. I think for one struggling with the meaning of negation, taking the unexplained leap here from negation of XOR to a remaining pure AND would be difficult. May 28 '15 at 10:25
  • 1
    @Cheersandhth.-Alf I think this fits with much of how propositional logic is taught. But thanks, I'll remove the "exclusive" part.
    – Paul Ross
    May 28 '15 at 10:53
2

If you have a statement and its negation, then one of them is true and one of them is false. That's the definition of "negation". The negation of a statement is false if the statement is true, and true if the statement itself is false. Whatever the situation, one is true and one is false.

Now take your statement "At least two of my library books are overdue" and your proposed negation "At least two of my library books are not overdue". If you have borrowed ten books, five are overdue and five are not, then both statements are true. Your proposed negation is not a negation of the original statement.

2

I have read the accepted answer to your question which suggests that the negation of the statement "At least two of my library books are overdue" would depend on the formal language one is using, namely

  1. "Less than two of my library books are overdue" (propositional logic)
  2. "For all overdue books there does not exist a different book that is also overdue" (first order predicate logic)

My objection is: Is there really any difference between the two suggested solutions? For me, the second sentence is just a complicated way to say that the set of overdue books contains only one book, or equivalently, "less than two books are overdue", i.e., the same as that written in the first sentence. From this example, the differences between propositional logic and first order predicate logic do not become clear to me. I would not go as far as saying that the accepted answer is wrong, but perhaps a little bit misleading with the claim that the answer would depend on the formal language one is using (at least for the example given by @Keelan).

"Less than two of my library books are overdue", including some linguistic variances, is therefore the only answer to your question, irrespective of the formal language one is using.

[Additional note: I understand that my answer should perhaps be posted as a comment to the accepted answer rather than a new answer, but I lack the required reputation that is necessary for commenting.]

1
  • They are indeed equivalent different formulations. They are, necessarily, because they're all negations of the same sentence. Only the formulation depends on the formalisation, not the meaning of the negation.
    – user2953
    May 31 '15 at 19:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.