A classic exercise in Discrete Mathematics is to negate a given proposition. Here, I’ll explain two things to consider after seeing how many students have problems solving this type of exercise.
Table of Contents
Background
A proposition is a sentence that states a fact. It is True or False but not both.
An example of a proposition is p=”Steve has a hard drive of 100 GB”. Propositions are usually denoted with the letters p, q, r, s, etc.
A compound proposition is that one formed using a conjunction (^) or disjunction (v). For example, p^q, qvq.
The negation of a proposition (¬q) means “it is not the case that q”. The truth value of the negation is the opposite of the truth value of the proposition. If the truth value of q is True, then the truth value of the negation of q (denoted as ¬q) is False.
The negation operator (¬) has precedence over conjunctions and disjunctions. For instance, ¬p^q means the negation of p and q, we could write it like (¬p)^q. But ¬(p^q), means we first calculate the truth value of the conjunction (p^q), and then we negate the truth value.
Let’s see the examples below:
- ¬False ^ True = True ^ True = True
- ¬(False ^ True) = ¬(False) = True
In this case, the truth value is the same but is calculated in a different order.
Let’s see the solution to the following exercise so you can see where the problem lies in this type of exercise.
What is the negation of each of these propositions?
Natural languages are ambiguous by design, so we need to be extra careful when we use them in mathematics.
a) Steve has more than 100 GB free disk space on his laptop.
Following the definition of the negation operator, we can just answer as follows.
It is not the case that Steve has more than 100GB free disc space on his laptop.
But we can write it more concisely.
Steve does not have more than 100GB free disc space on his laptop.
Steve has less than 101GB free disc space on his laptop. Some students choose this way, however, they usually answer “less than 100GB”. Notice that more than 100 starts at 101, so to state that is not more than 100 (greater or equal to 101), should be less than 101 (or less than or equal to 100).
b) Zach blocks e-mails and texts from Jennifer.
This type of question is where students make the most mistakes. The reason is that this is a compound proposition (see the conjunction?).
The straight answer is not a problem for students, you can just answer:
It is not the case that Zach blocks e-mails and texts from Jennifer.
The problem comes when you try to write the answer in a simplified way.
Notice that we can write the proposition we have to negate as follows:
p^q, where p = “Zach block e-mails from Jenifer”, q=”Zach block texts from Jenifer”.
So, the negation should be ¬(p^q) instead of ¬p^q.
You will find that ¬(p^q) is logically equivalent to ¬p v ¬q.
Following this logical equivalence, the negation in a simplified way should be as follows:
Zach does not block e-mails, or he does not block texts from Jenifer.
So the answer Zack does not block e-mails and texts from Jenifer will be wrong.
Let’s make a simple proof of the previous.
As you can see from the picture above, ¬(p^q) does not have the same truth values as ¬p^q (compare the 4th and 5th columns). Therefore, they are not logically equivalent. However, ¬(p^q) has the same truth values as ¬p v ¬q (compare the 4th and 6th columns).
c) 7·11·13 = 999.
This type of question and the next one does not cause any confusion. The answer is straightforward.
7·11·13 ≠ 999.
d) Diane rode her bicycle 100 miles on Sunday.
It is not the case that Diane rode her bicycle 100 miles on Sunday.
Or you can use a simplified way.
Diane did not ride her bicycle 100 miles on Sunday
Key points to remember
Be especially careful when you are negating compound propositions. The best way that works for me is that I represent each proposition with a propositional variable as I did in the answer to question b). Then you negate the compound proposition using the propositional variables and parenthesis. Lastly, you rewrite it in English.
If you ever doubt your answer, create the truth table for the compound proposition and the negation. If the truth values are the same, then you know you have the right answer.
Related posts:
- What is the negation of each of these propositions?
- How to create the truth table for a compound proposition
- Propositional Logic: Exercise 6 from the textbook.
- Propositional Logic: Exercise 7 from the textbook. Suppose that during the most recent fiscal year, the annual revenue of Acme Computer was 138 billion dollars …
- What are propositional equivalences in Discrete Mathematics?
- Which of these sentences are propositions? What are the truth values of those that are propositions?
- For each of these sentences, state what the sentence means if the logical connective or is an inclusive or (that is, a disjunction) versus an exclusive or. Which of these meanings of or do you think is intended?
