# Natural Deduction

0    29 speciālā zīme

jautājums atbilde
&I
Any 2 well-formed formulas may be conjoined. The relevant lines-numbers and '&I' must be cited. The dependency-numbers of the new line consist of all the dependency-numbers of both lines used.
&E
A conjunct may be removed from a conjunction by an application of '&E'. The line number of the conjunction must be cited together with '&E'. The dependency-numbers of the new line are identical with those of the original line.
&E (alt)
A conjunct may be removed from a conjunction by an application of '&E'. The line number of the conjunction must be cited together with '&E'. The dependency-numbers of the new line are identical with those of the original line.
MP
Given a conditional formula on one line of proof and its antecedent on another line, its consequent may be inferred. The line numbers of each must be cited together with MP. The dependency-numbers of the new line consist of those of both cited lines.
MT
Given a conditional on a line and the negation of its consequent on another, infer the negation of the antecedent. Annotate the new line with the line numbers of both lines used and 'MT'. The dependency-numbers of the new line are those of such lines.
DNE
Given the double negation of a formula on any line of proof you may write the original un-negated formula on a new line. Annotate the new line 'DNE' together with the line number of the the double negative. The dependency-numbers are the same as the old.
DNI
Given an un-negated formula on any line of proof you may write the double negative of that formula on a new line. Annotate the new line 'DNI' together with the line number of the the double negative. The dependency-numbers are the same as the old.
vI
Given a formula on a line of proof you may infer the disjunction of that formula with any other well-formed formula on a new line. Annotate the line with the line number of the old line and 'vI'. The dependency-numbers are the same as the old.
CP
Assume the antecedent. Derive the consequent. Enter the conditional on a line along with 'CP'. The line numbers are the antecedent and the consequent. Discharge the dependency-numbers of the antecedent. Pool the remaining and complete the line.
vE
Assume each disjunct in turn and derive desired formula from each. After, repeat the formula on a new line. Annotate the line numbers of the disjunction, first disjunct, its conclusion, second, and its conclusion followed by 'vE'. Discharge the disjuncts.
RAA
If a contradiction is shown to be derivable from a formula you may write the negation of that formula on a new line of proof. Annotate the new line with the contradiction, the relevant formula, and 'RAA'. Discharge that relevant formula and pool the rest.
The contradiction consists of any well-formed formula and its negation. This may be the assumption and its negation or some other formula and its negation. You may also pair RAA with DNE to infer an un-negated formula from its negation.
The Golden Rule
Provide the strategy one must adopt if they answer "yes" to any of the questions.
(1) Is the MC in the conclusion a conditional? If not, (2) is the MC of any member of the set of premises a disjunction? If not, (3) try RAA.
If so for (1), apply the strategy for CP. If so for (2), apply the strategy for vE. For (3), the trick is to assume the opposite of what you want and then try to derive a contradiction from that assumption. DNI & DNE will help you finish things as needed.
Remember that some or even all of these strategies can work together within a single proof, one strategy providing a sub-proof of something useful for another. Remember also that in some cases we just have to keep bashing away through trial and error!
< -- >I
How is this different from Df. < -- >?
Given 2 conditionals on any 2 lines of proof such that the antecedent of the first is the consequent of the second and vice versa, you may combine their antecedents into a biconditional. Cite the lines of the conditionals and pool their dependency-numbers
Df. < -- > requires one to form the conjunction of the two relevant conditionals, the definition of a biconditional, before actually inferring the relevant biconditional. Thus, < -- >I allows one to shortcut 1 line from any given proof.
< -- >E
How is this different from Df. < -- >?
Given a biconditional on any line of proof, you may infer a conjunction consisting of two conditionals such that the antecedent of one is the consequent of the other and vice versa. Cite the line of the biconditional, and pool the dependency numbers.
Df. < -- > and < -- >E are similar in that they both have one infer a conjunction from a given biconditional—this conditional, with the relevant conditionals as conjuncts, is, in fact, the definition of a biconditional. < -- >E simply accompanies < -- >I.
Law of Identity
This is a theorem.
P materially implies P.
Assume P is true. If P is true, then P is true. Therefore, P materially implies P.
TI [2.6.1]
If it is the case that if P implying P then materially implies Q, then it is the case that Q is true.
Assume (P --> P) --> Q. Now suppose P is true. If P were true, then P is true. If (P --> P) is true, then Q is true. Thus, (P --> P) --> Q materially implies Q.
TI [(2.6.2) & (2.6.3)]
The proof can work similarly if you switch the order of assumption—the end is different.
Provide the alternative theorem to this.
If it is the case that P materially implies Q, then it is the case that if Q materially implies R then P materially implies R.
Assume P --> Q and Q --> R. Now suppose P is true. If P is true, then Q is true. If Q is true, then R is true. So, P implies R. As such, Q --> R implies P --> R. Therefore, P --> Q materially implies (Q --> R) --> (P --> R).
Alt: If it is the case that Q materially implies R, then it is the case that if P materially implies Q then P materially implies R.
TI [2.6.4]
If P is true, then Q materially implies both P and Q.
Assume P is true. Now suppose Q were true. P and Q are both true. So, Q implies P & Q. Therefore, P materially implies (Q --> (P & Q)).
Principle of Transposition
This is a theorem.
If P materially implies Q, then ~Q materially implies ~P.
Assume P --> Q. Now suppose that Q is false. If Q is false, then P is false. So, ~Q implies ~P. Therefore, P --> Q materially implies ~Q --> ~P.
Law of Duns Scotus
This is a theorem that relies on monotonicity.
If P is false, then P materially implies Q.
Asuume ~P. Now suppose P is true. Suppose also that Q is false. P may be augmented by ~Q such that ~Q --> P. From this conditional, if P is false, then ~Q is false. If ~Q is false, then Q is true. So, P implies Q. Therefore, ~P materially implies P --> Q.
It is not the case that both P is true and P is false.
Assume P & ~P. This assumption contradicts itself, so P & ~P must be false.
Law of Excluded Middle
This is a theorem.
Either P is true or P is false.
Assume ~(P v ~P). Now suppose P is true. It follows that P v ~P. This contradicts the assumption, so P must be false. It then follows that P v ~P. This again contradicts the assumption, so ~(P v ~P) must be false. Therefore, P v ~P is true.
Theorem of Interpolation
This theorem relies on monotonicity.
Explain how the proof proves the theorem true.
Either P materially implies Q, or Q materially implies R.
The theorem follows whether Q is true or not. So, the negation of the theorem must be false. Therefore, the theorem is true.
Assume the negation. Now assume Q. Suppose P true. P augments Q: P --> Q. The theorem follows, contradicting the assumption; so, Q must be false. Now suppose Q true and R false. ~R augments Q: Q & ~Q, so ~R must be false. Q implies R. The theorem follows.
Disjunctive Syllogism
This is a derived rule of inference that relies on monotonicity.
Given a disjunction, if you have the negation of one of its disjuncts on any line of proof, you may infer the other disjunct on another line. Cite the line numbers of the disjunction and the negated disjunct, and pool the dependency numbers.
Given the premises, assume P as true. Suppose that Q is false. P may be augmented by ~Q such that P contradicts ~P; so, ~Q must be false. If ~Q is false, Q is true. Now assume Q is true. If Q is true, Q is true. Therefore, P v Q entails Q if P is false.
Hypothetical Syllogism
This is a derived rule of inference.
Given a conditional on a line of proof, if you have another conditional such that its antecedent is identical to the consequent of the former, you may infer a conditional connecting the antecedent of the former conditional to the consequent of the latter.
Given the premises, assume P is true. If P is true, then Q is true. If Q is true, then R is true. Therefore, P materially implies R.
Cite the two relevant conditionals, and pool their dependency numbers.
Constructive Dilemma
This is a derived rule of inference.
Given a conditional on a line of proof, if you have another such that its antecedent is the negation of the former and its consequent is identical to the former, you may infer the shared consequent. Cite the conditionals, and pool the dependency numbers.
Given the premises, assume Q is false. If Q is false, then P is false as per the first conditional. Also, if Q is false, then ~P is false as per the second. If ~P is false, then P is true. ~P and P contradict, so ~Q must be false. Therefore, Q is true.
Destructive Dilemma
This is a derived rule of inference.
Given a conditional on a line of proof, if you have another such that its consequent is the negation of the former and they share the same antecedent, you may infer the negation of that antecedent. Cite the conditionals, and pool the dependency numbers.
Given the premises, assume P is true. If P is true, then Q is true as per the first conditional. Also, if P is true, then Q is false as per the second. Q and ~Q contradict, so P must be false. Therefore, P is false.
Consequentia Mirabilis
This is a derived rule of inference.
If you have a conditional on any line of proof such that its antecedent is the negation of its consequent, you may infer the unnegated consequent on another line of proof. Cite the conditional, and pool the dependency numbers.
Given the premise, assume P is false. If P is false, then P is also true as per the conditional premise. P and ~P contradict, so ~P must be false. If ~P is false, then P is true. Therefore, P is true.
SI [3.10.6]
How does this stem from Consequentia Mirabilis?
If you have a conditional on any line of proof such that its consequent is the negation of its antecedent, you may infer the negated consequent on another line of proof. Cite the conditional, and pool the dependency numbers.
Given the premise, assume P is true. If P is true, then P is also false as per the conditional premise. P and ~P contradict, so P must be false. Therefore, ~P is true.
If you substituted in ~P for square, you would end up with ~~P --> ~P |- ~P. By applying DNE to the antecedent of the conditional premises, you would end up with this sequent!