Reasoning: An Introduction to Logic, Sets, and Functions

Subsection 4.3.5 Negation

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.