Flipping a Truth Value

Let $P$ = "7 is an even number". Find the truth values of $P$, $\neg P$ and $\neg(\neg P)$.

Evaluate P: 7 is odd, so the statement "7 is an even number" is **false** = P = F

Write the negation in words: $\neg P$ = "7 is not an even number" = ¬P in words

Apply NOT: $\neg P = \neg F = T$ = ¬P = T

Apply NOT a second time: $\neg(\neg P) = \neg T = F$, which is the same as P = ¬(¬P) = F

Answer: P is false, ¬P is true, and ¬(¬P) is false again. Two NOTs cancel out: ¬(¬P) = P.

Negating Sentences in English

Write the negation of "Anna has a bike." and of "Anna is at home."

Find the verb in the first sentence: In "Anna has a bike" the verb is has = Verb: has

Negate it the English way: English needs the helper verb do: has becomes does not have. "Anna not has a bike" is wrong = Anna does not have a bike.

Negate the second sentence: With the verb be, the word not goes right after the verb: is becomes is not = Anna is not at home.

Check the truth values: If "Anna has a bike" is true, then "Anna does not have a bike" is false, and the other way round = Exactly one is true

Answer: "Anna does not have a bike." and "Anna is not at home." Negating is not just adding a word: follow the grammar of your language.

Negating an "All" Statement

Write the negation of "All students passed the test."

Understand the claim: The statement says that every single student passed = Claim: every student passed

Ask what makes it false: One student who failed is already enough to make the claim false = At least one failed

Write the negation: "Not all students passed the test", or in other words "At least one student did not pass the test" = Not all students passed.

Reject the tempting wrong answer: "No student passed" is too strong: if 20 passed and 1 failed, both the claim and this sentence are false = Not a negation

Answer: "Not all students passed the test" (at least one student did not pass). The negation of "all" is "not all", not "none".

NOT Together with AND

P = "It is raining" is true and Q = "It is cold" is false. Evaluate $\neg P \land Q$ and $\neg(P \land Q)$.

NOT applies only to what stands right after it: In $\neg P \land Q$ only P is negated: $\neg P = \neg T = F$ = ¬P = F

Finish the first expression: $\neg P \land Q = F \land F = F$ = ¬P ∧ Q = F

Second expression: bracket first: $P \land Q = T \land F = F$ = P ∧ Q = F

Now negate the whole bracket: $\neg(P \land Q) = \neg F = T$ = ¬(P ∧ Q) = T

Answer: $\neg P \land Q$ is false, but $\neg(P \land Q)$ is true. Brackets decide what NOT applies to!

A First Look at De Morgan

Check that $\neg(P \vee Q)$ and $\neg P \land \neg Q$ give the same value for every choice of P and Q.

Left side for P = T, Q = F: $\neg(T \vee F) = \neg T = F$ = F

Right side for P = T, Q = F: $\neg T \land \neg F = F \land T = F$ = F, same

Both sides for P = F, Q = F: $\neg(F \vee F) = \neg F = T$ and $\neg F \land \neg F = T \land T = T$ = T, same

The two remaining cases: P = T, Q = T: $\neg T = F$ and $F \land F = F$. P = F, Q = T: $\neg T = F$ and $T \land F = F$ = F, same

Answer: Both sides always agree, so $\neg(P \vee Q) = \neg P \land \neg Q$. "I want neither tea nor coffee" means "I do not want tea AND I do not want coffee". This is one of De Morgan's laws.

Mistake: Negating "All cats are black" as "No cat is black"

Why: Both sentences can be false at the same time (some cats are black, some are not), so the second one is not the negation of the first.

Correct: The negation is "Not all cats are black", which means "At least one cat is not black".

Mistake: Writing the negation of $x > 5$ as $x < 5$

Why: This forgets the case $x = 5$. For $x = 5$ both $x > 5$ and $x < 5$ are false.

Correct: $\neg(x > 5)$ is $x \leq 5$: every number that is not greater than 5.

Mistake: Pulling NOT into a bracket without changing AND/OR: $\neg(P \land Q) = \neg P \land \neg Q$

Why: Test it with P = T, Q = F: $\neg(T \land F) = \neg F = T$, but $\neg T \land \neg F = F \land T = F$. The two sides are different.

Correct: When NOT goes into the bracket, AND turns into OR: $\neg(P \land Q) = \neg P \vee \neg Q$.

Mistake: Thinking that "not not" is still negative

Why: In some languages a double negative in speech is just one negation for emphasis (Spanish "No veo nada", Italian "Non vedo niente"). In logic, however, every NOT counts.

Correct: Two NOTs cancel: $\neg(\neg P) = P$. "It is not true that the shop is not open" means the shop is open.

Programming and Apps

Programmers write ! in front of a condition to run code only when that condition is false.

A homework app uses the rule !done: it shows a reminder only when the homework is NOT done.

NOT Gates in Electronics

A NOT gate (also called an inverter) has one input and one output. It always outputs the opposite signal.

A night light uses a light sensor that sends 1 when it is bright. After a NOT gate, the lamp gets 1 only when it is dark.

Shop Rules and Search Filters

Rules and searches often exclude something with AND NOT: the result must match one thing but not another.

A search for pizza AND NOT pineapple shows pizza pages, except the ones that mention pineapple.

Q: Why does NOT have only one input when AND and OR have two?

A: AND and OR combine two statements, but NOT simply changes one statement into its opposite truth value. That is why the NOT truth table has only two rows: P = T and P = F.

Q: Is "not happy" the same as "sad"?

A: No. "Not happy" is the negation and covers everything that is not happy: sad, bored, calm and so on. "Sad" is only one of these. A negation is true exactly when the original statement is false.

Q: What is the negation of "$x > 5$"?

A: It is $x \leq 5$. Every number is either greater than 5 or not, and "not greater than 5" includes 5 itself.

Q: What are De Morgan's laws?

A: They tell you how NOT moves into a bracket: $\neg(P \land Q) = \neg P \vee \neg Q$ and $\neg(P \vee Q) = \neg P \land \neg Q$. AND turns into OR and OR turns into AND. You will check them row by row in the lesson on truth tables.