Deductive Proofs Flashcards
Why do we need a different method to truth tables to verify the validity of arguments?
Because truth tables become impractical with reasonably big arguments.
What do we begin with to execute deductive proofs?
The assumption that the premises are true, and try to show that the conclusion must be true as well
To prove that the conclusion is true, what do we take?
A series of steps from the premises to the conclusion
Starting with the premises, which we assume are all true, what do we do to rech the conclusion?
Add another proposition to our stock of things that we know must be true
What type of style will we use to do deductive proofs?
Fitch style
What is the proof of the argument (A & B), (B → C) ∴ C?
1| A & B
2| B → C
————————
3| B &E 1
4| C →E 2, 3
What are the premises of the argument written as?
The first lines of the proof, with one premise per line
What do we write under the last premise?
A line to separate them from the remainder of the argument
What is the final line in a fitch style proof?
The conclusion
What do any lines between the premises and the conclusion contain?
Intermediate results that we’ve introduced alone the way
What is each line after the premises annotated with?
A code explaining why this step is justified
Explain what each line of this argument means.
1| A & B
2| B → C
————————
3| B &E 1
4| C →E 2, 3
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
For each logical operator what two rules do we have?
An introduction rule and an elimination rule
What do the introduction rule and elimination rule show respectively
How to prove and how to use a sentence with that operator as its main connective
How is the &-Elimination rule written?
&E
What does the &E rule tell us?
That if we know that X & Y is true then we can derive either two of the sentences X or Y from it
Give an example of the &E Rule
α |X & Y
|X &E α
Why does this argument work?
α |X & Y
|X &E α
Because the argument forms X & Y ∴ X
and X & Y ∴ Y are both valid.
How do you prove this argument is valid with Fitch proofs?
A & B ∴ B ∨ C
2 |B &E 1
3 |B ∨ C ∨I 2
How do you prove this complex argument is valid with Fitch proofs?
(P → Q) & (Q ∨ R) ∴ (Q ∨ R) ∨ (¬R → S)
2| (Q ∨ R) &E 1
3| (Q ∨ R) ∨ (¬R → S) ∨I 2
What does this rule say?
α |X & Y
|X &E α
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
Give an example of how this rule works.
α |X & Y
|X &E α
If we have ‘P & (Q → R)’ on line 7, then on any line later we can write ‘P’
On the right side of the rule, what does the number mean?
The line from which rule we’re citing
What can the letters X, Y, etc be matched to?
An atomic sentence or something more complex
When we use the &E rule, the content of the line must be what?
A conjunction
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
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
So, for example, if we have ‘P’ on line 5, then on any later line, what are we allowed to write?
P ∨ (Q → R)
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
When we use the vI rule, the content of the current line must be what?
A disjunction
How would you prove this argument with the &E rule and vI rule?
A & B ∴ B ∨ C
2| B &E 1
3| B ∨ C ∨I 2
What does →-Elimination correspond to?
X → Y , X ∴ Y (modus ponens)
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
What do we annotate for the →-Elimination rule?
→ E and the two line numbers we’re citing
What are the two line numbers we’re citing?
The line where we have “X → Y ” and
the line where we have “X”.
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
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
If we can show that X leads to a contradiction, then we conclude what?
That X is false
If we can show that ¬X leads to a contradiction, then we can conclude what?
That X is true
What is proving that X is false sufficient for?
That some contradiction follows from it.
What does the symbol ⊥ stand for?
An arbitrary contradiction
What might we think of ⊥ as?
A new atomic sentence that can only ever have the truth value F
Since ⊥ stands for an arbitrary contradiction, what do we prove it with?
By exhibiting two sentences that form a contradiction
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
How can we write the introduction ⊥ rule?
α|Y
β| ¬Y
|⊥ ⊥ I α, β
How can we write the negation introduction rule?
α| X → ⊥
|¬X ¬I α
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
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.’
How can we write the negation ¬-Elimination rule?
α| ¬X → ⊥
|X ¬E α
For any proposition X what are the two possibilities?
X is true and ¬X is false; or
¬X is true and X is false
What does it mean if X leads to contradiction?
Then X is false and we can deduce ¬X
What does it mean if ¬X leads to contradiction?
Then ¬X is false and we can deduce X
What does the elimination rule for⊥ say?
That if we have a line whose content is just ⊥ then we can derive anything from it
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
What is the ⊥-Elimination rule?
α| ⊥
|Z ⊥E α
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
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
If X v Y is true, then what are the two possibilities?
X is true; Z is true
Y is true; Z is true
IF we want to derive some conclusion Z from X v Y, then we need to show what?
That Z is true
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
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
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
What is the Disjunction Elimination rule (vE)
α| X ∨ Y
β| X → Z
γ| Y → Z
|Z ∨E α, β, γ
To prove the conditional, what 5 things does our method of proof need to let us to?
- Add a new fact X to our stock (without justification;
- Use Z for a while to derive further consequences from it;
- Repay it when we’re finished
- Return to our original stock of facts when we’re finished with X
- Indicate that everything we derived whilst using X isn’t really something we know to be true, since it depends on assumption X
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
What is on the first line of a subproof?
The assumption
If we can derive Y within a subproof that starts with X, then what have we done?
Proved X -> Y
What lines does a justification cite?
The range of line α–β
What is the conditional introduction rule?
α| | X
| ——-
| | . . .
β| | Y
|X → Y →I α–β
