Logic (PHIL 2080, COMP 2620, COMP 6262) Chapter: Propositional Natural Deduction — Negation, Disjunction
Logic (PHIL 2080, COMP 2620, COMP 6262)
Chapter: Propositional Natural Deduction
— Negation, Disjunction
Pascal Bercher
Planning & Optimization
Yoshihiro Maruyama
Logic
Intelligent Agents
College of Engineering and Computer Science
the Australian National University (ANU)
9 & 11 March 2021
Introduction Negation Disjunctions Summary
Introduction
Pascal Bercher and Yoshihiro Maruyama 1.27
Introduction Negation Disjunctions Summary
Recap on Natural Deduction
What are theorems? (Sequents without assumptions!)
Relationship between ` and→:
• They live in completely different worlds!
• → is a connective and thus part of a formula, just like ¬, ∧, and ∨.
• ` is not a connective and can thus not possibly be part of any
formula! It only states whether we can derive a single formula A
from a set of formulae X , expressed by X ` A.
How do proofs in natural deduction look?
• We use a list/table format with 4 columns.
• All of these columns are essential!
Introduction and elimination rules for:
• Conjunction (easy!)
• Implication (not quite that easy!)
So what’s missing?
• Negation (not as easy as you might think!)
• Disjunction (quite hard… Practice it!)
Pascal Bercher and Yoshihiro Maruyama 2.27
Introduction Negation Disjunctions Summary
Negation
Pascal Bercher and Yoshihiro Maruyama 3.27
Introduction Negation Disjunctions Summary
Introduction: Intuitive Meaning
What does the negation connective in logics mean?
It inverts truth values! Remember our introductory example:
• Socrates is a goat (= p)
• It’s not true that Socrates is a goat (= ¬p)
Be careful when translating “not” used in natural language:
• Someone likes Logic (= p)
• Someone doesn’t like Logic! (6= ¬p)
• Such complex propositions will be covered in predicate logic!
Pascal Bercher and Yoshihiro Maruyama 4.27
Introduction Negation Disjunctions Summary
Introduction: Truth Table
Since the not connective simply inverts a single truth value we get
a simple truth table:
p ¬p
0 1
1 0
p ¬p ¬¬p
0 1 0
1 0 1
I.e., in propositional logic, two negations eliminate each other!
It’s not true that it’s not true that Socrates is a goat (So it is true!)
Pascal Bercher and Yoshihiro Maruyama 5.27
Introduction Negation Disjunctions Summary
The 1-Step Rules: Double-Negation Elimination and Introduction
The (second) truth table gives us the following two rules:
Double-Negation Elimination and Introduction Rules:
¬¬A
A
¬¬E
A
¬¬A
¬¬I
Again based on sequents:
X ` ¬¬A
X ` A
¬¬E
X ` A
X ` ¬¬A
¬¬I
Pascal Bercher and Yoshihiro Maruyama 6.27
Introduction Negation Disjunctions Summary
The 1-Step Rules: A Mistake That Will Cost You Marks
Avoid the next common mistake:
Look carefully what/where the main connective is!
The rule refers to a complete formula!
So, e.g., we cannot go from p ∧ ¬¬q to p ∧ q in just one step!
Correctly handling that: (with a slightly more complex example)
p ∧ ¬¬q ` ¬¬p ∧ q
α1 (1) p ∧ ¬¬q A
α1 (2) p 1 ∧E
α1 (3) ¬¬p 2 ¬¬I
α1 (4) ¬¬q 1 ∧E
α1 (5) q 4 ¬¬E
α1 (6) ¬¬p ∧ q 3, 5 ∧I
Pascal Bercher and Yoshihiro Maruyama 7.27
¬¬A
A
¬¬E
A
¬¬A
¬¬I
Because A = (p ∧ ¬¬q),
but the rule states it should be ¬¬q!
Introduction Negation Disjunctions Summary
The 1-Step Rules: A Mistake That Will Cost You Marks
Avoid the next common mistake:
Look carefully what/where the main connective is!
The rule refers to a complete formula!
So, e.g., we cannot go from p ∧ ¬¬q to p ∧ q in just one step!
Correctly handling that: (with a slightly more complex example)
p ∧ ¬¬q ` ¬¬p ∧ q
α1 (1) p ∧ ¬¬q A
α1 (2) p 1 ∧E
α1 (3) ¬¬p 2 ¬¬I
α1 (4) ¬¬q 1 ∧E
α1 (5) q 4 ¬¬E
α1 (6) ¬¬p ∧ q 3, 5 ∧I
Pascal Bercher and Yoshihiro Maruyama 7.27
Introduction Negation Disjunctions Summary
The 1-Step Rules: Negation-Elimination
With the double-negation rules we can’t introduce or eliminate a
single negation.
To deal with single negations, we require the symbol ⊥.
We introduced it before: it represents “false”, an “absurd”
constant that can never be satisfied.
Negation-Elimination rule: (without and with sequent-notation)
A ¬A
⊥
¬E
X ` A Y ` ¬A
X ,Y ` ⊥
¬E
Pascal Bercher and Yoshihiro Maruyama 8.27
Introduction Negation Disjunctions Summary
The 1-Step Rules: Negation-Introduction
Negation-Introduction rule: (without and with sequent-notation)
[A]
…
⊥
¬A
¬I
X ,A ` ⊥
X ` ¬A
¬I
Negation-Introduction discharges assumption A.
Interesting fact(s):
• Since we do not pose further restrictions on A, we can blame the
contradiction on anything we want! E.g., if X = {A1, . . . ,An} and
X ` ⊥, we can conclude X \ {Ai} ` ¬Ai for any Ai ∈ X .
• This rule is the main proof idea behind the proof technique “Proof
by contradiction”. (There are, e.g., nice illustrations on YouTube
proving that
√
2 is not rational by that technique.)
Pascal Bercher and Yoshihiro Maruyama 9.27
Introduction Negation Disjunctions Summary
The 1-Step Rules: Excursion, Proof by Contradiction
We want to show:
If you are in Canberra (p), you are not in Sydney (¬q); thus:
if you are in Sydney (q), you are not in Canberra (¬p)
Proof:
• We assume “If you are in Canberra, you are not in Sydney”
• Assume the conclusion (i.e., the second implication) is wrong!
That is, assume “You are in Sydney and in Canberra.
• Because of the first assumption, and since we just assumed we
are in Canberra, we can conclude that we are not in Sydney.
• But now we are in Sydney, and not in Sydney, contradiction!
• Thus our assumption that the second implication is false must be
false, so it must be true.
• Thus, the first implication implies the second! q.e.d.
Pascal Bercher and Yoshihiro Maruyama 10.27
Remember what implication means:
a b →
0 0 1
0 1 1
1 0 0
1 1 1
thus, a non-satisfied
implication looks as
follows:
a b “not”→
0 0 0
0 1 0
1 0 1
1 1 0
Introduction Negation Disjunctions Summary
The 1-Step Rules: Excursion, Proof by Contradiction
We want to show:
If you are in Canberra (p), you are not in Sydney (¬q); thus:
if you are in Sydney (q), you are not in Canberra (¬p)
Proof:
• We assume “If you are in Canberra, you are not in Sydney”
• Assume the conclusion (i.e., the second implication) is wrong!
That is, assume “You are in Sydney and in Canberra.
• Because of the first assumption, and since we just assumed we
are in Canberra, we can conclude that we are not in Sydney.
• But now we are in Sydney, and not in Sydney, contradiction!
• Thus our assumption that the second implication is false must be
false, so it must be true.
• Thus, the first implication implies the second! q.e.d.
Pascal Bercher and Yoshihiro Maruyama 10.27
Introduction Negation Disjunctions Summary
The 1-Step Rules: Negation-Elimination and -Introduction, Example 1
If you are in Canberra (p), you are not in Sydney (¬q); thus:
if you are in Sydney (q), you are not in Canberra (¬p)
p → ¬q ` q → ¬p
α1 (1) p → ¬q A
α2 (2) q A
α3 (3) p A
α1, α3 (4) ¬q 1, 3→E
α1, α2, α3 (5) ⊥ 2, 4¬E
α1, α2 (6) ¬p 5[α3]¬I
α1 (7) q → ¬p 6[α2]→I
(n − 1) ¬p
(n) q → ¬p (n − 1) →I
Pascal Bercher and Yoshihiro Maruyama 11.27
X ,A ` ⊥
X ` ¬A
¬I
Introduction Negation Disjunctions Summary
The 1-Step Rules: Negation-Elimination and -Introduction, Example 1
If you are in Canberra (p), you are not in Sydney (¬q); thus:
if you are in Sydney (q), you are not in Canberra (¬p)
p → ¬q ` q → ¬p
α1 (1) p → ¬q A
α2 (2) q A
α3 (3) p A
α1, α3 (4) ¬q 1, 3→E
α1, α2, α3 (5) ⊥ 2, 4¬E
α1, α2 (6) ¬p 5[α3]¬I
α1 (7) q → ¬p 6[α2]→I
Pascal Bercher and Yoshihiro Maruyama 11.27
X ,A ` ⊥
X ` ¬A
¬I
X ` A Y ` ¬A
X ,Y ` ⊥
¬E
When line 5 is revealed, we can decide to “blame” any of
the assumptions α1 to α3 for the contradiction! But we
choose α3 = p, because that is the reason why we
introduced it! (We want to obtain ¬p.)
Introduction Negation Disjunctions Summary
The 1-Step Rules: Negation-Elimination and -Introduction, Example 1
If you are in Canberra (p), you are not in Sydney (¬q); thus:
if you are in Sydney (q), you are not in Canberra (¬p)
p → ¬q ` q → ¬p
α1 (1) p → ¬q A
α2 (2) q A
α3 (3) p A
α1, α3 (4) ¬q 1, 3→E
α1, α2, α3 (5) ⊥ 2, 4¬E
α1, α2 (6) ¬p 5[α3]¬I
α1 (7) q → ¬p 6[α2]→I
(n − 1) ¬p
(n) q → ¬p (n − 1) →I
Pascal Bercher and Yoshihiro Maruyama 11.27
X ,A ` ⊥
X ` ¬A
¬I
X ` A Y ` ¬A
X ,Y ` ⊥
¬E
Introduction Negation Disjunctions Summary
The 1-Step Rules: Negation-Elimination and -Introduction, Example 2
Contradict yourself, and I don’t care anymore!
In other words: We can conclude all we want from an inconsistent
knowledge base.
p,¬p ` q
α1 (1) p A
α2 (2) ¬p A
α1, α2 (3) ⊥ 1, 2¬E
α1, α2 (4) ¬¬q 3[]¬I
α1, α2 (5) q 4¬¬E
Here we have another example of vacuous discharge: We blame
the contradiction on a non-existing assumption ¬q.
Pascal Bercher and Yoshihiro Maruyama 12.27
Introduction Negation Disjunctions Summary
A 2-Step Rule: Reductio ad Absurdum (RAA)
We can combine Negation-Elimination with its Introduction:
Again, notations without and with sequents:
[B]
…
A
[B]
…
¬A
¬B
RAA
X ,B ` A Y ,B ` ¬A
X ,Y ` ¬B
RAA
The rules discharge assumption B.
Why is it correct?
X ,A ` ⊥
X ` ¬A
¬I
X ` A Y ` ¬A
X ,Y ` ⊥
¬E
X ,B ` A Y ,B ` ¬A
X ,Y ,B ` ⊥
¬E
X ,Y ` ¬B
¬I
Pascal Bercher and Yoshihiro Maruyama 13.27
Introduction Negation Disjunctions Summary
A 2-Step Rule: Reductio ad Absurdum (RAA), Example 1
p → ¬p ` ¬p: p is so false, it implies its own negation!
Or: Since p and ¬p can’t be true at the same time, the implication
p → ¬p cannot be “activated”, so its precondition must be false.
p → ¬p ` ¬p
α1 (1) p → ¬p A
α2 (2) p A
α1, α2 (3) ¬p 1, 2→E
α1 (4) ¬p 2, 3[α2]RAA
α1 (n) ¬p ?, ?[α2]RAA
Pascal Bercher and Yoshihiro Maruyama 14.27
X ,B ` A Y ,B ` ¬A
X ,Y ` ¬B
RAA
Introduction Negation Disjunctions Summary
A 2-Step Rule: Reductio ad Absurdum (RAA), Example 2
¬p → p ` p: if p is even implied by its own negation,
then it must be true!
Again! Since p and ¬p can’t be true at the same time, the
implication ¬p → p cannot be “activated”, so its precondition
must be false.
¬p → p ` p
α1 (1) ¬p → p A
α2 (2) ¬p A
α1, α2 (3) p 1, 2→E
α1 (4) ¬¬p 2, 3[α2]RAA
α1 (5) p 4¬¬E
Pascal Bercher and Yoshihiro Maruyama 15.27
X ,B ` A Y ,B ` ¬A
X ,Y ` ¬B
RAA
Introduction Negation Disjunctions Summary
Disjunctions
Pascal Bercher and Yoshihiro Maruyama 16.27
Introduction Negation Disjunctions Summary
Introduction: (Our) Or versus Exclusive Or
Disjunctions are of the form A ∨ B
It rains this afternoon or this evening.
(But it can also be both!)
The cat is either dead or alive.
(Unless it’s a physicist’s cat, the choice is exclusive!
The cat cannot be both dead and alive!)
We use the first, non-exclusive, notion of or:
At least one proposition needs to be true!
Pascal Bercher and Yoshihiro Maruyama 17.27
Introduction Negation Disjunctions Summary
The 1-Step Rules: Disjunction-Introduction
Disjunction-Introduction Rules:
Notation without sequents:
A
A ∨ B
∨I
B
A ∨ B
∨I
Notation with sequents:
X ` A
X ` A ∨ B
∨I
X ` B
X ` A ∨ B
∨I
Great! So we have that easy rule to prove a disjunction, right?
Well… No. (That’s only one sub step.) More later!
Pascal Bercher and Yoshihiro Maruyama 18.27
Introduction Negation Disjunctions Summary
The 1-Step Rules: Disjunction-Elimination, Introduction
If x is even, then x2 + x is even.
If x is odd, then x2 + x is even.
x is either odd or even.1
Thus, x2 + x is even.
We call this the constructive dilemma: From only knowing the
conclusion, we can’t know which of the cases applied!
Formally, this can be expressed as p → r , q → r , p ∨ q ` r
1Technically, we use the exclusive or here, but the argument remains true even if
it’s the non-exclusive or.
Pascal Bercher and Yoshihiro Maruyama 19.27
Introduction Negation Disjunctions Summary
The 1-Step Rules: Disjunction-Elimination Rule
Disjunction-Elimination Rule:
A ∨ B A→ C B → C
C
∨E
This does not help us so much:
• It’s too restrictive because it requires implications to work!
(Which would get eliminated as well.)
• But we only want to eliminate the disjunction without further
restrictions on the rest!
So, what do we do?
Pascal Bercher and Yoshihiro Maruyama 20.27
Introduction Negation Disjunctions Summary
The 1-Step Rules: Disjunction-Elimination Rule (Based on Sequents)
Deduction equivalence: X ` A→ B iff X ,A ` B
Thus, we can re-write the previous rule as follows:
A ∨ B
[A]
…
C
[B]
…
C
C
∨E
X ` A ∨ B Y ,A ` C Z ,B ` C
X ,Y , Z ` C
∨E
Now we:
• . . . don’t rely on implications anymore!
• . . . can discharge two assumptions (A and B), i.e., exactly those
of the disjunction (but from two different sequents!).
Some good news and bad news: This is the hardest rule in
natural deduction (So practice it!)
Pascal Bercher and Yoshihiro Maruyama 21.27
Introduction Negation Disjunctions Summary
The 1-Step Rules: When to Use that Rule
X ` A ∨ B Y ,A ` C Z ,B ` C
X ,Y , Z ` C
∨E
Technically, this rule is used to “eliminate” a disjunction.
But in practice, we use it to prove one!
How is that possible? Because we can use any formula for C!
I.e., when we want to derive a disjunction, we can use it as C –
but this will also require another disjunction for the first sequent!
We often obtain that one via assuming it.
Pascal Bercher and Yoshihiro Maruyama 22.27
Introduction Negation Disjunctions Summary
The 1-Step Rules: Disjunction-Introduction and -Elimination, Example 1
Disjunction is commutative: p ∨ q ` q ∨ p
α1 (1) p ∨ q A
α2 (2) p A
α2 (3) q ∨ p 2 ∨I
α3 (4) q A
α3 (5) q ∨ p 4 ∨I
α1 (6) q ∨ p 1, 3[α2], 5[α3] ∨E
In line 3, the q was just some arbitrary truth value that we’ve
added due to Disjunction-Introduction!
Similarly in line 5 the p was arbitrary. Notably, that’s not the p
from assumption α2.
Pascal Bercher and Yoshihiro Maruyama 23.27
X ` B
X ` A ∨ B
∨I
X ` A
X ` A ∨ B
∨I
Introduction Negation Disjunctions Summary
The 1-Step Rules: Disjunction-Introduction and -Elimination, Example 1
Disjunction is commutative: p ∨ q ` q ∨ p
α1 (1) p ∨ q A
α2 (2) p A
α2 (3) q ∨ p 2 ∨I
α3 (4) q A
α3 (5) q ∨ p 4 ∨I
α1 (6) q ∨ p 1, 3[α2], 5[α3] ∨E
Pascal Bercher and Yoshihiro Maruyama 23.27
X ` B
X ` A ∨ B
∨I
X ` A
X ` A ∨ B
∨I
X ` A ∨ B Y ,A ` C Z ,B ` C
X ,Y , Z ` C
∨E
X = {p ∨ q} A = α2 = p
Y = ∅ B = α3 = q
Z = ∅ C = α1 = q ∨ p
Introduction Negation Disjunctions Summary
The 1-Step Rules: Disjunction-Introduction and -Elimination, Example 2
Conjunction and disjunction behave just like multiplication and
addition, e.g. p · (q + r) = p · q + p · r :
p, q ∨ r ` (p ∧ q) ∨ (p ∧ r)
α1 (1) p A
α2 (2) q ∨ r A
α3 (3) q A
α4 (4) r A
α1, α3 (5) p ∧ q 1, 3 ∧I
α1, α3 (6) (p ∧ q) ∨ (p ∧ r) 5 ∨I
α1, α4 (7) p ∧ r 1, 4 ∧I
α1, α4 (8) (p ∧ q) ∨ (p ∧ r) 7 ∨I
α1, α2 (9) (p ∧ q) ∨ (p ∧ r) 2, 6[α3], 8[α4] ∨E
α1, α2 (n) (p ∧ q) ∨ (p ∧ r)
Pascal Bercher and Yoshihiro Maruyama 24.27
Just a comment:
The analogy would have been stronger
if instead of using the two assumptions
α1 = p and α2 = q ∨ r , only a single assumption
α′1 = p ∧ (q ∨ r) would have been used.
(You can prove the other on your own.)
Introduction Negation Disjunctions Summary
The 1-Step Rules: Disjunction-Introduction and -Elimination, Example 2
Conjunction and disjunction behave just like multiplication and
addition, e.g. p · (q + r) = p · q + p · r :
p, q ∨ r ` (p ∧ q) ∨ (p ∧ r)
α1 (1) p A
α2 (2) q ∨ r A
α3 (3) q A
α4 (4) r A
α1, α3 (5) p ∧ q 1, 3 ∧I
α1, α3 (6) (p ∧ q) ∨ (p ∧ r) 5 ∨I
α1, α4 (7) p ∧ r 1, 4 ∧I
α1, α4 (8) (p ∧ q) ∨ (p ∧ r) 7 ∨I
α1, α2 (9) (p ∧ q) ∨ (p ∧ r) 2, 6[α3], 8[α4] ∨E
α1, α2 (n) (p ∧ q) ∨ (p ∧ r) x , y [α3], z[α4] ∨E
Pascal Bercher and Yoshihiro Maruyama 24.27
X ` A ∨ B Y ,A ` C Z ,B ` C
X ,Y , Z ` C
∨E
X ` A
X ` A ∨ B
∨I
Introduction Negation Disjunctions Summary
The 1-Step Rules: Disjunction-Introduction and -Elimination, Example 2
Conjunction and disjunction behave just like multiplication and
addition, e.g. p · (q + r) = p · q + p · r :
p, q ∨ r ` (p ∧ q) ∨ (p ∧ r)
α1 (1) p A
α2 (2) q ∨ r A
α3 (3) q A
α4 (4) r A
α1, α3 (5) p ∧ q 1, 3 ∧I
α1, α3 (6) (p ∧ q) ∨ (p ∧ r) 5 ∨I
α1, α4 (7) p ∧ r 1, 4 ∧I
α1, α4 (8) (p ∧ q) ∨ (p ∧ r) 7 ∨I
α1, α2 (9) (p ∧ q) ∨ (p ∧ r) 2, 6[α3], 8[α4] ∨E
α1, α2 (n) (p ∧ q) ∨ (p ∧ r) x , y [α3], z[α4] ∨E
Pascal Bercher and Yoshihiro Maruyama 24.27
X ` A ∨ B Y ,A ` C Z ,B ` C
X ,Y , Z ` C
∨E
X ` B
X ` A ∨ B
∨I
Introduction Negation Disjunctions Summary
The 1-Step Rules: Disjunction-Introduction and -Elimination, Example 3
p → r , q → s ` (p ∨ q)→ (r ∨ s)
α1 (1) p → r A
α2 (2) q → s A
α3 (3) p ∨ q A
α4 (4) p A
α5 (5) q A
α1, α4 (6) r 1, 4→E
α1, α4 (7) r ∨ s 6 ∨I
α2, α5 (8) s 2, 5→E
α2, α5 (9) r ∨ s 8 ∨I
α1, α2, α3 (10) r ∨ s 3, 7[α4], 9[α5] ∨E
α1, α2 (11) (p ∨ q)→ (r ∨ s) 10[α3]→I
α1, α2, α3 (n − 1) r ∨ s 3, y [α4], z[α5] ∨E
α1, α2 (n) (p ∨ q)→ (r ∨ s) (n − 1)[α3]→I
Pascal Bercher and Yoshihiro Maruyama 25.27
X ` A ∨ B Y ,A ` C Z ,B ` C
X ,Y , Z ` C
∨E
X = {p ∨ q} A = α4 = p
Y =? B = α5 = q
Z =? C = r ∨ s
Introduction Negation Disjunctions Summary
The 1-Step Rules: Disjunction-Introduction and -Elimination, Example 3
p → r , q → s ` (p ∨ q)→ (r ∨ s)
α1 (1) p → r A
α2 (2) q → s A
α3 (3) p ∨ q A
α4 (4) p A
α5 (5) q A
α1, α4 (6) r 1, 4→E
α1, α4 (7) r ∨ s 6 ∨I
α2, α5 (8) s 2, 5→E
α2, α5 (9) r ∨ s 8 ∨I
α1, α2, α3 (10) r ∨ s 3, 7[α4], 9[α5] ∨E
α1, α2 (11) (p ∨ q)→ (r ∨ s) 10[α3]→I
α1, α2, α3 (n − 1) r ∨ s 3, y [α4], z[α5] ∨E
α1, α2 (n) (p ∨ q)→ (r ∨ s) (n − 1)[α3]→I
Pascal Bercher and Yoshihiro Maruyama 25.27
Introduction Negation Disjunctions Summary
Summary
Pascal Bercher and Yoshihiro Maruyama 26.27
Introduction Negation Disjunctions Summary
Content of this Lecture
The remaining rules for natural deduction: negation and
disjunction
Note that, this time, we had more than just 1-step rules!
→ The entire Logic Notes sections:
• Propositional natural deduction: Negation
• Propositional natural deduction: Disjunction
→ We are done now with everything until Section 2!
Pascal Bercher and Yoshihiro Maruyama 27.27
Introduction
Negation
Introduction
The 1-Step Rules
A 2-Step Rule
Disjunctions
Introduction
The 1-Step Rules
Summary