CS350 · Session 3 · The Complexity of Negation

Saying the opposite, precisely

Negating 'it is cold and foggy' is not 'it is not cold and not foggy.' Getting the opposite of a sentence exactly right is harder than it looks, and it is where De Morgan's laws, truth tables, and the strange little word 'unless' earn their keep.

01

The connective playground

Every compound sentence is built from five machines. Flip P and Q and watch all five react.

connectivesentencevalue
negation¬P·
conjunctionP ∧ Q·
disjunctionP ∨ Q·
conditionalP → Q·
biconditionalP ↔ Q·
Note what just happened: P → Q is false only when P is true and Q is false. This one row is the source of most confusion in the course. Stare at it.
Why is P → Q true when P is false?

Read P → Q as a promise: 'if P happens, Q happens.' The only way to break the promise is for P to happen without Q. If P never happens, the promise was never tested, so it was never broken, so it stands as true.

02

The roommate puzzle: build the truth table

Are these two sentences consistent, can they both be true at once?

1. My roommate is neither tired nor has an assignment due, but she wants coffee.
2. My roommate wants coffee only if she has an assignment due or is tired.

P my roommate is tired
Q my roommate has an assignment due
R my roommate wants coffee
1. ¬(P ∨ Q) ∧ R ('neither nor' = ¬( ∨ ), 'but' = ∧)
2. R → (P ∨ Q) ('A only if B' = A → B)

The first two columns are done for you. Click the empty cells to cycle T / F, then check your table.

Stuck? How to attack any truth table

Work inside-out. First evaluate P ∨ Q (done for you), then negate it for ¬(P ∨ Q), then AND with R. For the conditional, remember: false only on rows where R is T and P ∨ Q is F.

03

De Morgan's lamp board

Three lamps claim to be the negation of A ∧ B. Only one deserves the title: the true negation must light up in exactly the worlds where A ∧ B is dark. Flip the switches and find the impostor.

A ∧ B
¬(A ∧ B)
¬A ∨ ¬B
¬A ∧ ¬B

Now negate in plain language. One option in each set is exactly right.

De Morgan's laws, and the conditional

¬(A ∧ B) ≡ ¬A ∨ ¬B  ·  ¬(A ∨ B) ≡ ¬A ∧ ¬B. Negation flips ∧ into ∨ and back, pushing the ¬ inward onto each part.

For conditionals, first rewrite: P → Q ≡ ¬P ∨ Q. Then negate with De Morgan: ¬(P → Q) ≡ P ∧ ¬Q. The negation of 'if P then Q' is NOT another if-then. It is 'P happened and Q didn't.'

04

'Unless', or Kipling's two promises

Two readings of the same idea, one with if, one with unless. Are they the same promise?

1. If foes cannot hurt you, then yours is the world and everything that's in it.
2. Unless foes can hurt you, yours is the world and everything that's in it.

Symbolization key

F foes can hurt you
Y yours is the world

Translations

1. ¬F → Y
2. F ∨ Y (unless = or)
FY¬F → YF ∨ Y
The takeaway on 'unless'

'Unless F, Y' means 'if not F, then Y', which is ¬F → Y, which is logically equivalent to F ∨ Y. When translating, the cheapest safe move is: replace 'unless' with 'or'.

05

Reflection

Negate this sentence from the study guide, in natural English: 'San Francisco weather is cold and foggy, or it is cold and sunny.'
How could a truth table prove that your negation above is correct? Describe the check you would run.
'By focusing attention on the requirement for reasons or evidence to support our views, logic provides a fundamental defense against prejudiced and uncivilized attitudes…' Agree or disagree? Connect your answer to something from today's session.