Week 7 - CPL: Natural Deduction Flashcards
What are the new rules added to CPL natural deduction?
Universal elimination
Universal introduction
Existential elimination
Existential introduction
What is the basic idea of universal elimination?
Form the claim that everything is P, one can infer any particular thing is P.
Example
From ‘everything has consciousness’ one can infer ‘Ben Nevis has
consciousness’.
How does the universal elimination work?
UE allows us to drop a universal quantifier and replace the
quantified variable with any constant.
1 | ∀xPx
2 |Pa UE, 1
When can universal elimination be applied?
When the universal quantifier is the main logical operator.
When eliminating multiple universal quantifiers what must you do?
- one has to proceed in a step-by-step way.
- distinct quantified variables may be replaced by the same constant.
What is an existential introduction?
From the claim that a particular thing is P, one can infer that there exists something that is P.
Example
From ‘SARS-CoV-2 is a virus’ one can infer ‘there exists a virus’.
What does EI allow us to do?
EI allows us to replace any constant with a variable and add an existential quantifier for that variable.
1| Pa
2|∃xPx EI, 1
1| Pc
2| ∃xPx EI, 1
What can we do using EI?
When using EI, we can choose how many and which occurrences of
a constant to replace with the existentially quantified variable.
1 Ldd Premise|Donald loves himself.
2 ∃xLxd EI, 1|So, someone loves Donald.
1 Ldd Premise|Donald loves himself.
2 ∃xLdx EI, 1|So, Donald loves someone.
1 Ldd Premise|Donald loves himself.
2 ∃xLxx EI, 1|So, some love themselves.
What is the basic idea of universal introduction?
Basic idea
If one can infer that an arbitrary thing is P, then one can infer that everything is P.
Given Pc (where c is arbitrary), one may infer ∀xPx.
How is something arbitrary?
c is arbitrary:
1. there is no premise in which c occurs.
2. there is no undischarged assumption in which c occurs.
What makes something undischarged?
In logic, an assumption is undischarged in the natural deduction calculus when the conclusion of an inference is not dependent on it. This means that the conclusion is an immediate result of a sub-derivation, rather than the premise itself
What is the basic idea of existential elimination?
Given that something is P, we may drop the existential quantifier by assuming that an arbitrary particular thing c is P provided that we discharge that assumption later on.
What is the pattern of EE?
Pattern
1. Something is P.
2. Suppose c is P. (EE assumption)
3. Draw inferences until you reach a conclusion ψ that does not
contain any occurrence of c.
4. Close the subproof, and infer ψ by EE.
What are the conditions for applying EE?
Conditions for applying EE:
1. c must not occur in ∃xϕ[. . . x . . . x . . .].
2. c must not occur in any undischarged assumption before line i or in any premise.
3. c must not occur in ψ.
