Example of use De Morgan Law and the plain English behind it.

Question

I am currently reading "Discrete Mathematics and Its Applications, 7th ed", p.29.

Example:

Use De Morgan’s laws to express the negations of “Miguel has a cellphone and he has a laptop computer”.

Solution:

Let p be “Miguel has a cellphone” and q be “Miguel has a laptop computer.” Then “Miguel has a cellphone and he has a laptop computer” can be represented by p ∧ q. By the first of De Morgan’s laws, ¬(p ∧ q) is equivalent to¬p ∨¬q. Consequently, we can express the negation of our original statement as “Miguel does not have a cellphone or he does not have a laptop computer.”

---

Here and in De Morgan law I think I understand the math part. I am constructing truth tables of propositions and I see why propositions are equivalent in De Morgan law.

But I do not understand plain English part of the example. As I understand complete opposite means as opposite as possible and negation is the complete opposite. Why negation (complete opposite) of "Miguel has a cellphone and he has a laptop computer" is "Miguel does not have a cellphone or he does not have a laptop computer". Why complete opposite is not "Miguel does not have a cellphone and he does not have a laptop computer"? I mean if he does not have both it is more opposite than if he does not have one of them, right. Why is it so?

Answer 1

Correct me if I'm misunderstanding what you are saying but I believe the confusion you are having arises from not fully seeing the use of "or" in a mathematical context.

In conversation, if we say "A or B" we mean either A or B but NOT both A and B (this is also known as the exclusive or). In math, when we say "A or B" it means either:

1) A is true

2) B is true

3) both A and B are true

So now going back to your example we have “Miguel has a cellphone and he has a laptop computer” and the negation as you correctly noted is "Miguel does not have a cellphone or he does not have a laptop computer." So think about it this way - the negation of the original statement would imply that either Miguel is missing a cellphone, Miguel is missing a laptop computer, or he is missing both. This is exactly why the "or" is correct in this situation.

Answer 2

I think your basic problem here is that you expect negation to produce a "complete opposite", whatever that would mean.

The negation of

Miguel has a cellphone and a computer.

ought to be nothing more or less than

It is not true that Miguel has a cellphone and a computer.

If Miguel lacks a cellphone but has a computer it is still not true that he has both. So the negation of "he has both" ought to be true as soon as there is one of them he lacks.

In other words, if you take

Miguel has neither a cellphone nor a computer.

as the "negation", then you may be satisfying your intuitive sense of "oppositeness", but you have created a situation where it may be that both the sentence and its "negation" are false -- which is absurd.

Answer 3

Then “Miguel has a cellphone and he has a laptop computer” can be represented by p ∧ q.

Yes, which is equivalent to “Miguel has both a cellphone and a laptop computer”.

The negation of that is "Miguel does not have both a cellphone and a laptop computer", which means that he is missing at least one of the two items: he may not have a cellphone, or he may not have a laptop, or he may have neither. That is precisely what the quoted solution says.

we can express the negation of our original statement as “Miguel does not have a cellphone or he does not have a laptop computer.”

Note that the logic "or" is inclusive, so the above also covers the case where Miguel has neither a cellphone nor a laptop.

Answer 4

I think a different, more concrete example could make it easier to understand in plain English.

Let's say you have to take an exam which consists of 2 parts, a written test and an oral test. You get a mark on both, and they are independent, which means that you can pass both parts, or fail both, or pass one part but fail the other (doesn't matter which).

The rules are that to pass the full exam you must pass the written test AND the oral one.

Now, you come to me and say:

"I've passed the exam."

What does it imply? What can I infer? Clearly, that you passed the oral test AND you passed the written test. So far so good.

If, instead, you come to me and say the opposite:

"I've failed the exam."

What can I infer? Careful here: I can only infer that you failed the written part, or you failed the oral part, or both. Mathematically, if we use "or", there's no need to add the "or both" at the end, so we can shorten it to this: you failed the written part OR you failed the oral part.

This is what De Morgan's law tells us: the negation of "passed oral part AND passed written part" is "failed oral part OR failed written part". Failing either part is enough to fail the entire exam, there's no need to fail both parts to be rejected.

If I decided that the negation is the complete opposite, as you say, I could conclude something wrong. For example, if you passed the written test but failed the oral one, you would come to me and say "I have failed the exam".
In that case, if I concluded that you must have failed both the written part AND the oral part (complete opposite), I'd be wrong.

Answer 5

Why complete opposite is not "Miguel does not have a cellphone and he does not have a laptop computer"? I mean if he does not have both it is more opposite than if he does not have one of them, right. Why is it so?

That is not the complete opposite since it accounts for fewer cases where the original sentence is not true.

Draw a Venn Diagram of two overlapping circles. The complete opposite of their intersection is everything other than the intersection, not merely everything outside both circles.

Answer 6

In math each sentence has an exact logical value, either true (1) or false (0).

We may not know if Miguel has a laptop or a cellphone but our lack of knowledge does not change the state of his possession.

Now a negation means that a sentence that was true is now false and one that was false is now true. Sentence taken as a whole. In other terms, if sentence

Miguel has a cellphone and he has a laptop computer

Is true then it's negation has to be false. If it's false then it's negation has to be true.

This sentence is true when Miguel has both a cellphone and a laptop. In all other possible cases (Miguel has a laptop but no cellphone, Miguel has a cellphone but no laptop or Miguel has neither a laptop nor a cellphone) this sentence is false. So the negation of that sentence has to have exactly opposite logical values - false if Miguel has both a cellphone and a laptop but true in all other cases.

Now our common sense may suggests that if we want to negate a compound sentence with a specific preposition we need to keep the preposition and negate the composing sentences but that is not true. If you do that your sentence would change to:

Miguel has no cellphone and he has no laptop computer

The problem is that by negating the first sentence you don't need that strong condition. It is enough that Miguel doesn't have just one of the equipment. The first sentence is then false. But the second is false too, so something went wrong with our negation - it's not an exact opposition.

Here De Morgan laws step in. They tell you that you not only have to negate compouding sentences but also invert the preposition. this may sound counter-intuitive but only until you think it over. If you want to negate someones possession of two devices at the same time it's enough that this person does not own only one of the two. You can't say you have both a cellphone and a laptop computer if you don't have a cellphone. Even if you do have a laptop. Right?

So the correct negated statement is

Miguel does not have a cellphone or he does not have a laptop computer

One last remark that makes all that a bit more tricky. A spoken common language isn't always as strict as mathematical rules. If you say "Miguel doesn't have a laptop and a computer" it may not be 100% clear if he doesn't have either or only he doesn't have both. But math is very strict so you have to disambiguate such sentence.