Subsection4.3.5Negation

While negation is a straightforward concept, it’s easy to make mistakes when encoding it in logic. So we’ll go through some examples for practice.

Recall the Both My Pills example that we considered back in the introduction to this course: Consider the claim, “I didn’t take both of my pills this morning.” We pointed out that this sentence could mean either of these things:

[1] For each of my pills, it’s the case that I didn’t take it this morning.

[2] I took one of my pills this morning, but not both of them.

Now we can show how to encode each of these meanings in predicate logic. Define:

Pill(x): True if x is one of my pills.

Took(x, w): True if I took x at time w.

For both meanings, we need to say (if it’s important to do so) that I take exactly two pills. We can do that with the conjunction of two claims:

[3] $$\exists$$ x, y (Pill(x) $$\wedge$$ Pill(y) $$\wedge$$ $$\neg$$ (x = y)) I have at least two pills.

[4] $$\forall$$ x, y, z ((Pill(x) $$\wedge$$ Pill(y) $$\wedge$$ Pill(z)) $$\rightarrow$$ ((x = y) $$\vee$$ (x = z))) I have no more than two pills.

[3] can be read literally as, “There exist two objects that are my pills and that are not the same thing.”

[4] can be read literally as, “If there are three objects that are my pills, there is some pair of them that are the same thing.

This may feel like a very clunky way of saying that I have exactly two pills. It is. Unfortunately, to do it more elegantly, we need to develop a language for talking about sets (in this case, the set of my pills) and the sizes of sets. We’ll do that in the follow on course on Sets, Functions and Relations.

Now on to encoding the specific claims [1] and [2] (either of which can be anded with the conjunction of [3] and [4]):

[1] $$\forall$$x (Pill(x) $$\rightarrow$$ $$\neg$$Took(x, ThisMorning))

[2] $$\exists$$x (Pill(x) $$\wedge$$ Took(x, ThisMorning)) $$\wedge$$ $$\exists$$y (Pill(y) $$\wedge$$ $$\neg$$Took(y, ThisMorning))

We make negated statements much more frequently than you might imagine.

English Aside

Recall that, in English, there are many ways to make negative statements. We can use words that contain implied negations, such as, “never”, “nowhere”, “none”, “only”, “just”, “unless”, “except”, “without”, and “but”. We can also use negative prefixed, such as, “un-”, “il-”, and “in-”.

Lying Suppose that we want to encode the fact that some people never lie. Define:

Person(x): True if x is a person.

Time(t): True if t is a time.

Lying(x, t): True if x is lying at time t.

Notice that the word “never” contains an implied negation. So we can write:

[1] $$\forall$$x (Person(x) $$\wedge$$ $$\forall$$t ($$\neg$$Lying(x, t)))

We read [1] as: There’s some x who is a person and, at all times, x isn’t lying at that time.

Sometimes we can say the same thing in two different ways, one that involves negation and one that doesn’t. It may depend on the predicates we choose to work with.

Let’s return to the Lying problem. This time, define:

Person(x): True if x is a person.

Time(t): True if t is a time.

TruthTelling(x, t): True if x is telling the truth at time t.

Now we can write:

[2] $$\exists$$x (Person(x) $$\wedge$$ $$\forall$$t (TruthTelling(x, t)))

Suppose that we add a new premise:

[3] $$\forall$$x,y (TruthTelling(x, t) $$\equiv$$ $$\neg$$Lying(x, t))

Then we should (using the proof techniques we’re about to discuss) be able to prove [1] from [2] and vice versa.

When we discuss the new inference rules that we’ll need for working with predicate logic statements, we’ll formalize what happens with existential and universal quantifiers when they are negated. For now, let’s just look at a simple example where we can easily see how to encode what we want to say.

Suppose that we want to encode the claim that no one likes beets. (This is apparently not true, although some of us find that amazing.) In any case, we can encode things, whether they’re true or not. Define:

Likes(x, y): True if x likes y.

There are two probably equally obvious ways to say what we have to say:

[1] $$\forall$$x ($$\neg$$Likes(x, Beets)) Everyone dislikes beets. or

[2] $$\neg$$$$\exists$$x (Likes(x, Beets)) There doesn’t exist anyone who likes beets.

ExercisesExercises

1.

1. Define:

Curable(x): True if x is a curable disease.

Which one or more of the following logical expressions corresponds to the claim that leprosy is not an incurable disease?

I. Curable(Leprosy)

II. ¬Curable(Leprosy)

III. ¬¬Curable(Leprosy)

1. Just I.

2. Just II.

3. Just III.

4. Just I and II.

5. Just I and III.

Correct answer is E.
Solution.
Explanation: III is the most direct translation of the original statement, which contains a double negative. But we know that P is equivalent to P. So III is equivalent to I.

2.

Define: Lying(x, t): True if x is lying at time t.

Wednesday(t): True if t is a Wednesday

Which one or more of the following logical expressions corresponds to the claim that John only lies on Wednesday? (Notice that the word “only” contains an implied negation.)

I. ∀tWednesday(t) → ¬Lying(John, t))

II. ¬∃tWednesday(t) ∧ Lying(John, t))

III. ∀t (Wednesday(t) → Lying(John, t))

1. Just I.

2. Just II.

3. Just III.

4. Just I and II.

5. All three

Correct answer is D.
Solution.
Explanation: I says that, if it’s not Wednesday, John isn’t lying. That’s correct. II says that there doesn’t exist any non-Wednesday time when John is lying. That’s correct too. But III says that if it is Wednesday, then John is lying. Our claim doesn’t say that. In fact, literally it doesn’t even say that he ever lies. But it’s a bit misleading to make this claim if the stronger claim, “John never lies,” is also true.

3.

3. Let’s do one more example that involves our corporate database and our corporate policies. We want to encode the fact that only supervisors can sign time cards. Define:

Super(x): True if x is a supervisor.

CanSign(x, y): True if x can sign y.

Timecard(x): True if x is a timecard.

Which one or more of the following expressions corresponds to our claim:

I. ∀x, y ((Super(x) ∧ Timecard(y)) → CanSign(x, y))

II. ∀x, y ((¬Super(x) ∧ Timecard(y)) → ¬CanSign(x, y))

III. ∀x, y ((Super(x) ∧ ¬Timecard(y)) → CanSign(x, y))

1. Just I.

2. Just II.

3. Just III.

4. Just I and II.

Correct answer is B.
Solution.
Explanation: I doesn’t say anything about nonsupervisors being unable to sign (which is what our claim is). II does say exactly what we need. III says something about what happens when the object in question isn’t a timecard.

4.

4. Consider one famous girl of song, my girl, “the girl who loves nobody but me.” Define:

Loves(x, y): True if x loves y.

Which one or more of the following expressions describes this girl, given the reading most of us have of the song:

I. Loves(MyGirl, Me) ∧∀y (¬(y = Me) → ¬Loves(MyGirl, y))

II. Loves(MyGirl, Me) ∧∀y ( (y = Me) ∨ ¬Loves(MyGirl, y))

III. ∀y ( (y = Me) ∨ ¬Loves(MyGirl, y))

1. Just I.

2. Just II.

3. Just III.

4. Just I and II.

5. Just I and III.