12/30/06
Learning further propositional rules of inference. Carrying out simple propositional derivations using some of the Rules of Inference.
Thus far we have encountered 3 propositional rules of inference: Simplification, Conjunction, and Addition. If we write these out as forms or patterns, these are the kinds of inferences they permit.
Simplication (Simp)
p.q
∴
pConjunction (Conj)
p,
q
∴
p.qAddition(Add)
p
∴
p∨q
The ps and qs are understood as variables that can stand for any formula. So, for example, all 3 of the following are examples of Simplification
F.G
∴
FP.Q
∴
P(F⊃G). ~F
∴
F⊃G
We started with these three rules just because they are slightly simpler to explain in that each operate on only one formula (or one line of a proof). There are actually six other rules of inference, most of which work with two formulas (or two lines of a proof). Here are three more
Modus Ponens (MP)
p⊃q,
p
∴
qModus Tollens (MT)
p⊃q,
~q
∴
~pHypothetical Syllogism (HS)
p⊃q,
q⊃r
∴
p⊃r
Here are some examples of those three rules at work (press the Proof buttons, and select Derive It from the Wizard menu).
Proof applet
Example 1 F.H,F⊃G ∴ G
Example 2 ~G,F⊃G ∴ ~F∨H
Example 3 F⊃G,G⊃H,K ∴ K.(F⊃H)
For these you do not use Derive It. You do them yourself! Select the appropriate lines, choose the rules, and do the proof. [If you are truly stuck use Next Line or Derive It.]
Each of the derivations in the following Exercise can be done using the Rule of Modus Ponens (MP), and the rules learned previously.
If a formula in a line of a derivation has the form
<formula1> ⊃ <formula2>
and a formula in a line of a derivation has the form
<formula1>
the Rule of Modus Ponens allows you to add
<formula2>
This is the classical inference rule known as Modus Ponens. In English, if you have If A then B and A you are entitled to B.
Show each of the following arguments to be valid.
If you are stuck, ask the program to do one line for you (choose Next Line under the Wizard Menu); then, having seen what the next line is, go to the Edit Menu click Undo Next Line and try to do it yourself.
(a) F, F⊃G ∴ G
(b) F⊃G, F ∴ G.F
(c) F⊃G, G⊃H,F ∴H
(d) F⊃(G⊃H), F⊃G,F ∴H.F
(e) F⊃((~G)⊃H), F⊃~G,F ∴H.F
Proofs
Each of the derivations in the following Exercise can be done using the Rule of Modus Tollens (MT), and the rules learned previously.
If a formula in a line of a derivation has the form
<formula1> ⊃ <formula2>
and a formula in a line of a derivation has the form
~<formula2>
the Rule of Modus Tollens allows you to add
~<formula1>
This is the classical inference rule known as Modus Tollens. In English, if you have not-B and If A then B you are entitled to not-A.
Show each of the following arguments to be valid.
a) (X∨Y)⊃~(Z.~A), ~~(Z.~A)∴ ~(X∨Y)
b) ~(B.C)⊃(D∨E), ~(B.C)∴ (D∨E)
c) G⊃H, ~H.F,K ∴K.~G
Proofs
Each of the derivations in the following Exercise can be done using the Rule of Hypothetical Syllogism (HS), and the rules learned previously.
If a formula in a line of a derivation has the form
<formula1> ⊃ <formula2>
and a formula in a line of a derivation has the form
<formula2> ⊃ <formula3>
the Rule of Hypothetical Syllogism allows you to add
<formula1> ⊃ <formula3>
This rule is known as Hypothetical Syllogism. In English, if you have If A then B and If B then C you are entitled to If A then C.
Show each of the following arguments to be valid.
If you are stuck, ask the program to do one line for you (choose Next Line under the Wizard Menu); then, having seen what the next line is, go to the Edit Menu click Undo Next Line and try to do it yourself.
a) H⊃G,(X∨Y)⊃H ∴ (X∨Y)⊃G
b) ~(B.A)⊃(K.(G⊃H)),(W≡ V)⊃~(B.A)∴ (W≡ V)⊃(K.(G⊃H))
c)(H⊃G).K,(~~A)⊃H,I∴ ((~~A)⊃G).I
Proofs