Logic 12: Natural Deduction Flashcards
Natural Deduction
Good for constructing an argument, starting from certain premises and seeing what we can prove from them
Starts from certain assumptions and uses rules on how to introduce and eliminate sentential connectives to get new sentences that depend on the assumptions we have made
What is a proof?
a list of lines, each which shows 1) the sentence we’ve generated, 2) what rule we used to generate it 3) what assumptions that sentence depends on
Conjunction rules
conjunction elimination ^E
conjunction introduction ^I
Conjunction elimination ^E
if you have proven a conjunction A^B from some set of assumptions X, then you can infer A and it will also rest on the assumptions in X, and you can infer B and it will rest on the assumptions in X
Conjunction introduction ^I
if you have proven a formula A from some set of assumptions X, and you have proven B from some set of assumptions Y, then you can infer A^B, and it will rest on the union of the assumptions in X and Y
(all the assumptions in X and all the assumptions in Y)
Example using conjunction
(A∧B)∧C ⊢ B∧C
1 1) (A∧B)∧C Ass 1 2) A∧B 1,∧E 1 3) B 2,∧E 1 4) C 1,∧E 1 5) B∧C 3,4,∧I
First Step
At line 1, we start by assuming the premise of our argument: “Ass”
every natural deduction proof will start out by assuming each premise of the argument
- an assumption depends for its truth on itself– we haven’t generated it from anything
- we’ve merely assumed it– write 1 on the far left
Conditional rules
conditional elimination →E
conditional introduction →I
Conditional elimination→E
if you’ve got a conditional A→B resting on some assumptions X, and you’ve got A resting on some assumptions Y, then you can infer B and it will rest on the union of X and Y
Conditional elimination example
A∧B, A→C ⊢ C
1 1) A∧B Ass
2 2) A→C Ass
1 3) A 1,∧E
1,2 4) C 2,3,→E
Conditional introduction →I
you can prove a conditional A→B by assuming A and proving B on that assumption
reasoning known as conditional proof
but we only assume A temporarily, once I conclude the conditional, we DISCHARGE the assumption that A
RULE: if I assume A, and then if I can infer B resting on A and some assumptions X, I can then infer A→B resting just on X
Conditional introduction example
A→B ⊢ (B→C)→(A→C).
1 1) A→B Ass 2 2) B→C Ass 3 3) A Ass 1,3 4) B 1,3,→E 1,2,3 5) C 2,4,→E 1,2 6) A→C 3,5,→I 1 7) (B→C)→(A→C) 2,6,→I
Ass
Assume whatever you like at any stage, and it will depend on itself.
n n) A Ass
∧I
If you’ve got A depending on set of assumptions X and B depending on set of
assumptions Y, infer A∧B, which will depend on the union of X and Y.
X n) A . . .
Y m) B . . .
X,Y o) A∧B n,m∧I
∧E
If you’ve got A∧B depending on set of assumptions X, infer A, which will depend on
assumptions X.
X n) A∧B . . .
X m) A n,∧E
→I
If you can assume A, then prove B resting on a set of assumptions X together with A,
infer A→B, which will depend just on assumptions X.
n n) A Ass
X,n m) B . . .
X o) A→B n,m→I
→E
If you’ve got A depending on set of assumptions X and A→B depending on set of
assumptions Y, infer B, which will depend on the union of X and Y.
X n) A . . .
Y m) A→B . . .
X,Y o) B n,m,→E
↔E
If you’ve got A↔B depending on set of assumptions X, infer (A→B)∧(B→A), which will
also depend on set of assumptions X.
X n) A↔B . . .
X m) (A→B)∧(B→A) n,↔E
↔I
If you’ve got A→B depending on set of assumptions X and B→A depending on set of
assumptions Y, infer A↔B, which will depend on the union of X and Y.
X n) A→B . . .
Y m) B→A . . .
X,Y o) A↔B n,m,↔I
∨I
If you’ve got A depending on assumptions X, infer A∨B, which will also depend on
assumptions X.
X n) A . . .
X m) A∨B n,∨I
∨E ****
If you’ve got A∨B depending on assumptions X then: if you can assume A and prove C
depending on that assumption and some assumptions Y, and assume B and prove C
depending on that assumption and some assumptions Z, then you can infer that C,
which will then depend on the union of X, Y and Z.
X n) A∨B . . . m m) A Ass Y,m o) C . . . p p) B Ass Z,p q) C . . . X,Y,Z r) C n,m,o,p,q,∨E
vE explained
if you know that one thing or another is true, and you can show that each
option has a common conclusion, you can infer that common conclusion from the
disjunction. So if you have A∨B, you can assume A and show it leads to C, and then
assume B and show it leads to C, and thereby conclude that C follows from A∨B. No
matter which of A and B is true, C follows, and we know that one of them is true - so C
must be true. Whatever the disjunction depends on, C will also depend on, and C will
also depend on any assumptions we used to show that it follows from A and that it
follows from B, but we discharge the assumptions of A and B themselves, as they were
only assumed temporarily, in order to show what followed from them (just as with →I)
¬E
If you’ve got the double negation of something, you can get rid of the two negations,
and the result will depend on whatever the double negation depended on.
X n) ¬¬A . . .
X m) A n,¬E
¬I
If you can assume A and then derive a contradiction together with the assumption that
A and some assumptions X, infer ¬A, which will depend on assumptions X.
n n) A Ass
X,n m) B∧¬B . . .
X o) ¬A n,m,¬I
If you assume something and it leads to a contradiction then you know it must not be true (since no truth leads to contradiction), and therefore you can infer its
negation.
The negation of your assumption will depend on whatever assumptions you used in addition to the thing you’re inferring the negation of in order to get the conclusion, but it will not depend on the assumption you’re inferring the negation of, as it is being discharged: it was only assumed temporarily, in order to show what followed from it.
