Deductive Proofs Flashcards

1
Q

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

A

Because truth tables become impractical with reasonably big arguments.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What do we begin with to execute deductive proofs?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

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

A

A series of steps from the premises to the conclusion

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

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

A

Fitch style

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What are the premises of the argument written as?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What do we write under the last premise?

A

A line to separate them from the remainder of the argument

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the final line in a fitch style proof?

A

The conclusion

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

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

A

Intermediate results that we’ve introduced alone the way

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is each line after the premises annotated with?

A

A code explaining why this step is justified

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

For each logical operator what two rules do we have?

A

An introduction rule and an elimination rule

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What do the introduction rule and elimination rule show respectively

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

How is the &-Elimination rule written?

A

&E

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

What does the &E rule tell us?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

Give an example of the &E Rule

A

α |X & Y
|X &E α

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

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

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

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

A

The line from which rule we’re citing

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

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

A

An atomic sentence or something more complex

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
When we use the &E rule, the content of the line must be what?
A conjunction
26
The proposition on the current line must be what?
Exactly on the left side of that conjunction, or exactly on the right side of that conjunction
27
What does this rule say? α| X | X ∨ Y ∨I α
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
28
So, for example, if we have 'P' on line 5, then on any later line, what are we allowed to write?
P ∨ (Q → R)
29
On the right side we write what when we have this rule?
vI (for the 'V Introduction' rule) and the line number we're citing
30
When we use the vI rule, the content of the current line must be what?
A disjunction
31
How would you prove this argument with the &E rule and vI rule? A & B ∴ B ∨ C
1| A & B -------------- 2| B &E 1 3| B ∨ C ∨I 2
32
What does →-Elimination correspond to?
X → Y , X ∴ Y (modus ponens)
33
What does the →E α, β rule (→-Elimination) say?
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
34
What do we annotate for the →-Elimination rule?
→ E and the two line numbers we're citing
35
What are the two line numbers we're citing?
The line where we have “X → Y ” and the line where we have “X”.
36
With these rules, prove (P ∨ Q) → R, (A → P) & (C → Q), A & B ∴ R
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
37
What does &-Introduction correspond to?
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
38
If we can show that X leads to a contradiction, then we conclude what?
That X is false
39
If we can show that ¬X leads to a contradiction, then we can conclude what?
That X is true
40
What is proving that X is false sufficient for?
That some contradiction follows from it.
41
What does the symbol ⊥ stand for?
An arbitrary contradiction
42
What might we think of ⊥ as?
A new atomic sentence that can only ever have the truth value F
43
Since ⊥ stands for an arbitrary contradiction, what do we prove it with?
By exhibiting two sentences that form a contradiction
44
What does the ⊥-Introduction rule require?
Us to cite a line whose contents is some sentence Y and another line whose contents is exactly the negation of Y
45
How can we write the introduction ⊥ rule?
α|Y β| ¬Y |⊥ ⊥ I α, β
46
How can we write the negation introduction rule?
α| X → ⊥ |¬X ¬I α
47
IN words, how can we write the negation introduction rule?
If we can prove that X leads to a contradiction then X must be false, and so ¬X is true
48
Seeing as every sentence is either true or false, how can we write negation elimination in words?
'If ¬X implies a contradiction, then ¬X must be false, and so X must be true.'
49
How can we write the negation ¬-Elimination rule?
α| ¬X → ⊥ |X ¬E α
50
For any proposition X what are the two possibilities?
X is true and ¬X is false; or ¬X is true and X is false
51
What does it mean if X leads to contradiction?
Then X is false and we can deduce ¬X
52
What does it mean if ¬X leads to contradiction?
Then ¬X is false and we can deduce X
53
What does the elimination rule for⊥ say?
That if we have a line whose content is just ⊥ then we can derive anything from it
54
What is it called if we have a line whose content is just ⊥ then we can derive anything from it?
Rule of Explosion or ex falso quodlibet
55
What is the ⊥-Elimination rule?
α| ⊥ |Z ⊥E α
56
Prove the following argument A & B, B → ¬A ∴ C.
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
57
Concerning disjunction elimination, if we know X v Y is true, does it tel us?
That at least one of X or Y is true, but not which one
58
If X v Y is true, then what are the two possibilities?
X is true; Z is true Y is true; Z is true
59
IF we want to derive some conclusion Z from X v Y, then we need to show what?
That Z is true
60
How do we show Z is true in order to derive some conclusion Z from X v Y
Know if X -> Z and Y -> Z
61
Give an example of disjunction elimination.
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
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
P1: A v B P2: A -> C P3: B -> C Conc: C
63
What is the Disjunction Elimination rule (vE)
α| X ∨ Y β| X → Z γ| Y → Z |Z ∨E α, β, γ
64
To prove the conditional, what 5 things does our method of proof need to let us to?
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
65
To prove A → B, B → C ∴ A → C, we need subproofs. Prove this utilising subproofs.
1| A → B 2| B → C ----------------- 3| | A | ------- 4| | B →E 1, 3 5| | C →E 2, 4 6| A → C →I 3–5
66
What is on the first line of a subproof?
The assumption
67
If we can derive Y within a subproof that starts with X, then what have we done?
Proved X -> Y
68
What lines does a justification cite?
The range of line α–β
69
What is the conditional introduction rule?
α| | X | ------- | | . . . β| | Y |X → Y →I α–β