Logic 12: Natural Deduction

Question 1

Natural Deduction

Answer 1

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

Question 2

What is a proof?

Answer 2

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

Question 3

Conjunction rules

Answer 3

conjunction elimination ^E

conjunction introduction ^I

Question 4

Conjunction elimination ^E

Answer 4

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

Question 5

Conjunction introduction ^I

Answer 5

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)

Question 6

Example using conjunction

(A∧B)∧C ⊢ B∧C

Answer 6

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

Question 7

First Step

Answer 7

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

Question 8

Conditional rules

Answer 8

conditional elimination →E

conditional introduction →I

Question 9

Conditional elimination→E

Answer 9

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

Question 10

Conditional elimination example

A∧B, A→C ⊢ C

Answer 10

1 1) A∧B Ass
2 2) A→C Ass
1 3) A 1,∧E
1,2 4) C 2,3,→E

Question 11

Conditional introduction →I

Answer 11

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

Question 12

Conditional introduction example

A→B ⊢ (B→C)→(A→C).

Answer 12

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

Question 13

Ass

Answer 13

Assume whatever you like at any stage, and it will depend on itself.
n n) A Ass

Question 14

∧I

Answer 14

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

Question 15

∧E

Answer 15

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

Question 16

→I

Answer 16

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

Question 17

→E

Answer 17

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

Question 18

↔E

Answer 18

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

Question 19

↔I

Answer 19

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

Question 20

∨I

Answer 20

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

Question 21

∨E ****

Answer 21

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

Question 22

vE explained

Answer 22

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)

Question 23

¬E

Answer 23

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

Question 24

¬I

Answer 24

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.