Deductive Proofs

Question 1

Why do we need a different method to truth tables to verify the validity of arguments?

Answer 1

Because truth tables become impractical with reasonably big arguments.

Question 2

What do we begin with to execute deductive proofs?

Answer 2

The assumption that the premises are true, and try to show that the conclusion must be true as well

Question 3

To prove that the conclusion is true, what do we take?

Answer 3

A series of steps from the premises to the conclusion

Question 4

Starting with the premises, which we assume are all true, what do we do to rech the conclusion?

Answer 4

Add another proposition to our stock of things that we know must be true

Question 5

What type of style will we use to do deductive proofs?

Answer 5

Fitch style

Question 6

What is the proof of the argument (A & B), (B → C) ∴ C?

Answer 6

1| A & B
2| B → C
————————
3| B &E 1
4| C →E 2, 3

Question 7

What are the premises of the argument written as?

Answer 7

The first lines of the proof, with one premise per line

Question 8

What do we write under the last premise?

Answer 8

A line to separate them from the remainder of the argument

Question 9

What is the final line in a fitch style proof?

Answer 9

The conclusion

Question 10

What do any lines between the premises and the conclusion contain?

Answer 10

Intermediate results that we’ve introduced alone the way

Question 11

What is each line after the premises annotated with?

Answer 11

A code explaining why this step is justified

Question 12

Explain what each line of this argument means.
1| A & B
2| B → C
————————
3| B &E 1
4| C →E 2, 3

Answer 12

Line 1: A & B is given as a premise
Line 2: B => C is also given as a premise
Line 3: If line 1 (A&B) is true then A is true because the argument A & B ∴ B is valid
Line 4: If line 2 (B => C) and line 3 (B) are true then C is true because the argument (B => C), B ∴ C is valid

Question 13

For each logical operator what two rules do we have?

Answer 13

An introduction rule and an elimination rule

Question 14

What do the introduction rule and elimination rule show respectively

Answer 14

How to prove and how to use a sentence with that operator as its main connective

Question 15

How is the &-Elimination rule written?

Answer 15

&E

Question 16

What does the &E rule tell us?

Answer 16

That if we know that X & Y is true then we can derive either two of the sentences X or Y from it

Question 17

Give an example of the &E Rule

Answer 17

α |X & Y
|X &E α

Question 18

Why does this argument work?
α |X & Y
|X &E α

Answer 18

Because the argument forms X & Y ∴ X
and X & Y ∴ Y are both valid.

Question 19

How do you prove this argument is valid with Fitch proofs?
A & B ∴ B ∨ C

Answer 19

2 |B &E 1
3 |B ∨ C ∨I 2

Question 20

How do you prove this complex argument is valid with Fitch proofs?
(P → Q) & (Q ∨ R) ∴ (Q ∨ R) ∨ (¬R → S)

Answer 20

2| (Q ∨ R) &E 1
3| (Q ∨ R) ∨ (¬R → S) ∨I 2

Question 21

What does this rule say?
α |X & Y
|X &E α

Answer 21

That if we have a proposition of the form ‘X & Y’ on any line above the current one then we’re allowed to write ‘X’ on the current line

Question 22

Give an example of how this rule works.
α |X & Y
|X &E α

Answer 22

If we have ‘P & (Q → R)’ on line 7, then on any line later we can write ‘P’

Question 23

On the right side of the rule, what does the number mean?

Answer 23

The line from which rule we’re citing

Question 24

What can the letters X, Y, etc be matched to?

Answer 24

An atomic sentence or something more complex

Question 25

When we use the &E rule, the content of the line must be what?

Answer 25

A conjunction

Question 26

The proposition on the current line must be what?

Answer 26

Exactly on the left side of that conjunction, or exactly on the right side of that conjunction

Question 27

What does this rule say?
α| X
| X ∨ Y ∨I α

Answer 27

That if we have a proposition ‘X’ on any line above the current one, then we’re allowed to write ‘X V Y’ (for any Y) on the current line

Question 28

So, for example, if we have ‘P’ on line 5, then on any later line, what are we allowed to write?

Answer 28

P ∨ (Q → R)

Question 29

On the right side we write what when we have this rule?

Answer 29

vI (for the ‘V Introduction’ rule) and the line number we’re citing

Question 30

When we use the vI rule, the content of the current line must be what?

Answer 30

A disjunction

Question 31

How would you prove this argument with the &E rule and vI rule?
A & B ∴ B ∨ C

Answer 31

2| B &E 1
3| B ∨ C ∨I 2

Question 32

What does →-Elimination correspond to?

Answer 32

X → Y , X ∴ Y (modus ponens)

Question 33

What does the →E α, β rule (→-Elimination) say?

Answer 33

If we have propositions ‘X → Y’ and ‘X’ on any line above the current one, then we’re allowed to write ‘Y’ on the current line

Question 34

What do we annotate for the →-Elimination rule?

Answer 34

→ E and the two line numbers we’re citing

Question 35

What are the two line numbers we’re citing?

Answer 35

The line where we have “X → Y ” and
the line where we have “X”.

Question 36

With these rules, prove
(P ∨ Q) → R, (A → P) & (C → Q), A & B ∴ R

Answer 36

1| (P ∨ Q) → R
2| (A → P) & (C → Q)
3| A & B
——————————
4| A &E 3
5| A → P &E 2
6| P →E 4, 5
7| P ∨ Q ∨I 6
8| R →E 7, 1

Question 37

What does &-Introduction correspond to?

Answer 37

X, Y ∴ X & Y;
If we know that X is true and we know that Y is true, then we know that X & Y is true

Question 38

If we can show that X leads to a contradiction, then we conclude what?

Answer 38

That X is false

Question 39

If we can show that ¬X leads to a contradiction, then we can conclude what?

Answer 39

That X is true

Question 40

What is proving that X is false sufficient for?

Answer 40

That some contradiction follows from it.

Question 41

What does the symbol ⊥ stand for?

Answer 41

An arbitrary contradiction

Question 42

What might we think of ⊥ as?

Answer 42

A new atomic sentence that can only ever have the truth value F

Question 43

Since ⊥ stands for an arbitrary contradiction, what do we prove it with?

Answer 43

By exhibiting two sentences that form a contradiction

Question 44

What does the ⊥-Introduction rule require?

Answer 44

Us to cite a line whose contents is some sentence Y and another line whose contents is exactly the negation of Y

Question 45

How can we write the introduction ⊥ rule?

Answer 45

α|Y
β| ¬Y
|⊥ ⊥ I α, β

Question 46

How can we write the negation introduction rule?

Answer 46

α| X → ⊥
|¬X ¬I α

Question 47

IN words, how can we write the negation introduction rule?

Answer 47

If we can prove that X leads to a contradiction then X must be false, and so ¬X is true

Question 48

Seeing as every sentence is either true or false, how can we write negation elimination in words?

Answer 48

‘If ¬X implies a contradiction, then ¬X must be false, and so X must be true.’

Question 49

How can we write the negation ¬-Elimination rule?

Answer 49

α| ¬X → ⊥
|X ¬E α

Question 50

For any proposition X what are the two possibilities?

Answer 50

X is true and ¬X is false; or
¬X is true and X is false

Question 51

What does it mean if X leads to contradiction?

Answer 51

Then X is false and we can deduce ¬X

Question 52

What does it mean if ¬X leads to contradiction?

Answer 52

Then ¬X is false and we can deduce X

Question 53

What does the elimination rule for⊥ say?

Answer 53

That if we have a line whose content is just ⊥ then we can derive anything from it

Question 54

What is it called if we have a line whose content is just ⊥ then we can derive anything from it?

Answer 54

Rule of Explosion or ex falso quodlibet

Question 55

What is the ⊥-Elimination rule?

Answer 55

α| ⊥
|Z ⊥E α

Question 56

Prove the following argument A & B, B → ¬A ∴ C.

Answer 56

1| A & B
2| B → ¬A
—————-
3| A &E 1
4| B &E 1
5| ¬A →E 2, 4
6| ⊥ ⊥I 3, 5
7| C ⊥E 6

Question 57

Concerning disjunction elimination, if we know X v Y is true, does it tel us?

Answer 57

That at least one of X or Y is true, but not which one

Question 58

If X v Y is true, then what are the two possibilities?

Answer 58

X is true; Z is true
Y is true; Z is true

Question 59

IF we want to derive some conclusion Z from X v Y, then we need to show what?

Answer 59

That Z is true

Question 60

How do we show Z is true in order to derive some conclusion Z from X v Y

Answer 60

Know if X -> Z and Y -> Z

Question 61

Give an example of disjunction elimination.

Answer 61

P1: I go to the cinema or I go to the funfair;
P2: If I go to the cinema then I feel unwell;
P3: If I go to the funfair then I feel unwell;
Conc: I feel unwell

Question 62

Formalise this argument.
P1: I go to the cinema or I go to the funfair;
P2: If I go to the cinema then I feel unwell;
P3: If I go to the funfair then I feel unwell;
Conc: I feel unwell

Answer 62

P1: A v B
P2: A -> C
P3: B -> C
Conc: C

Question 63

What is the Disjunction Elimination rule (vE)

Answer 63

α| X ∨ Y
β| X → Z
γ| Y → Z
|Z ∨E α, β, γ

Question 64

To prove the conditional, what 5 things does our method of proof need to let us to?

Answer 64

1. Add a new fact X to our stock (without justification;
2. Use Z for a while to derive further consequences from it;
3. Repay it when we’re finished
4. Return to our original stock of facts when we’re finished with X
5. Indicate that everything we derived whilst using X isn’t really something we know to be true, since it depends on assumption X

Question 65

To prove A → B, B → C ∴ A → C, we need subproofs. Prove this utilising subproofs.

Answer 65

1| A → B
2| B → C
—————–
3| | A
| ——-
4| | B →E 1, 3
5| | C →E 2, 4
6| A → C →I 3–5

Question 66

What is on the first line of a subproof?

Answer 66

The assumption

Question 67

If we can derive Y within a subproof that starts with X, then what have we done?

Answer 67

Proved X -> Y

Question 68

What lines does a justification cite?

Answer 68

The range of line α–β

Question 69

What is the conditional introduction rule?

Answer 69

α| | X
| ——-
| | . . .
β| | Y
|X → Y →I α–β