6/24/07 10 Software
You now have to tools to appraise arguments to the level of detail offered by predicate logic.
Let us run through how these might be used with a long and difficult example.
Consider the argument
Anyone on the committee who knew the nominee would vote for the nominee, if free to do so. Everyone on the committee was free to vote for the nominee except those who were either instructed not to do so by the party caucus or who had pledge support to someone else. Everyone on the committee knew the nominee. No one who knew the nominee had pledged support to anyone else. Someone on the committee did not vote for the nominee. So the party caucus had instructed some members of the committee not to vote for the nominee. [This example is adapted from Copi]
First we symbolize it
(∀x) ((Cx&Kx&Fx)⊃Vx )
(∀x) (Cx⊃(Fx∨Ix∨Px))
(∀x) (Cx⊃Kx)
∼(∃x)(Kx&Px)
(∃x)(Cx&∼Vx)
∴
(∃x)(Cx&Ix)Cx= x is on the committee
Fx= x is free to vote for the nominee
Ix= x has been instructed by the party caucus not to vote for the nominee
Kx= x knew the nominee
Px= x had pledged support to someone else
Vx= x votes for the nominee
Then we should have a quick look at the semantics. We start by producing an interpretation in which the conclusion is false, say
Now the first four premises are true in this, but the fifth one is not, we need for (∃x)(Cx&∼Vx) to be true (ie for there to be an x which is C but not V). We try
Now, the conclusion is true, and so too is premise 5, but premises 2 and 3, (∀x)(Cx⊃(Fx∨Ix∨Px)) and (∀x)(Cx⊃Kx), are not true.
We need to make our a have the property K to get (∀x)(Cx⊃Kx) to be true, and it must also have one of the properties F, I, or P to get premise 2 to be true. This is all starting to get a little sticky.
At this point we should wonder whether the argument might be valid, and whether we can produce a derivation of it. The derivation starts
1 (∀x)((Cx&(Kx&Fx))⊃Vx) Ass 2 (∀x)(Cx⊃(Fx∨(Ix∨Px))) Ass 3 (∀x)(Cx⊃Kx) Ass 4 ∼(∃x)(Kx&Px) Ass 5 (∃x)(Cx&∼Vx) Ass 6 Ca&∼Va Ass 7 ? ? << 8 (∃x)(Cx&Ix) ? 9 (∃x)(Cx&Ix) 5,8 ∃E
We have used Tactics, and it seemed likely that the last line has come from Existential Elimination on line 5 (which we have put in). (There is a little hint here. If you have a whole lot of universally quantified formulas, and a single existentially quantified one, try working with instantiating the existential quantifier first (that gives you a suitable term to plug into the universally quantified formulas). Line 5 offers an invitation.)
1 (∀x)((Cx&(Kx&Fx))⊃Vx) Ass 2 (∀x)(Cx⊃(Fx∨(Ix∨Px))) Ass 3 (∀x)(Cx⊃Kx) Ass 4 ∼(∃x)(Kx&Px) Ass 5 (∃x)(Cx&∼Vx) Ass 6 Ca&∼Va Ass 7 ? ? << 8 Ca&Ia ? 9 (∃x)(Cx&Ix) 8 ∃I 10 (∃x)(Cx&Ix) 5,9 ∃E
Tactics, EI. Now our problem is to get from line 6 Ca&∼Va to line 8 Ca&Ia. The Cas will take care of themselves, so the problem is to get from∼ Va to Ia. The only place that I appears is on the right hand side of 2. So we should take the Ca, which we need
1 (∀x)((Cx&(Kx&Fx))⊃Vx) Ass 2 (∀x)(Cx⊃(Fx∨(Ix∨Px))) Ass 3 (∀x)(Cx⊃Kx) Ass 4 ∼(∃x)(Kx&Px) Ass 5 (∃x)(Cx&∼Vx) Ass 6 Ca&∼Va Ass 7 Ca 6 &E 8 ? ? << 9 Ca&Ia ? 10 (∃x)(Cx&Ix) 9 ∃I 11 (∃x)(Cx&Ix) 5,10 ∃E
and then the right hand side of 2 (and 3 while we are working on Ca)
1 (∀x)((Cx&(Kx&Fx))⊃Vx) Ass 2 (∀x)(Cx⊃(Fx∨(Ix∨Px))) Ass 3 (∀x)(Cx⊃Kx) Ass 4 ∼(∃x)(Kx&Px) Ass 5 (∃x)(Cx&∼Vx) Ass 6 Ca&∼Va Ass 7 Ca 6 &E 8 Ca⊃(Fa∨(Ia∨Pa)) 2 ∀E 9 Fa∨(Ia∨Pa) 8,7 ⊃E 10 Ca⊃Ka 3 ∀E 11 Ka 10,7 ⊃E 12 ? ? << 13 Ca&Ia ? 14 (∃x)(Cx&Ix) 13 ∃I 15 (∃x)(Cx&Ix) 5,14 ∃E
Line 13 will have come from &I.
1 (∀x)((Cx&(Kx&Fx))⊃Vx) Ass 2 (∀x)(Cx⊃(Fx∨(Ix∨Px))) Ass 3 (∀x)(Cx⊃Kx) Ass 4 ∼(∃x)(Kx&Px) Ass 5 (∃x)(Cx&∼Vx) Ass 6 Ca&∼Va Ass 7 Ca 6 &E 8 Ca⊃(Fa∨(Ia∨Pa)) 2 ∀E 9 Fa∨(Ia∨Pa) 8,7 ⊃E 10 Ca⊃Ka 3 ∀E 11 Ka 10,7 ⊃E 12 ? ? << 13 Ia ? 14 Ca&Ia 7,13 &I 15 (∃x)(Cx&Ix) 14 ∃I 16 (∃x)(Cx&Ix) 5,15 ∃E
Now we are still trying to get Ia from a variety of things, but most obviously line 9 Fa∨(Ia∨Pa) which suggests an ∨E
1 (∀x)((Cx&(Kx&Fx))⊃Vx) Ass 2 (∀x)(Cx⊃(Fx∨(Ix∨Px))) Ass 3 (∀x)(Cx⊃Kx) Ass 4 ∼(∃x)(Kx&Px) Ass 5 (∃x)(Cx&∼Vx) Ass 6 Ca&∼Va Ass 7 Ca 6 &E 8 Ca⊃(Fa∨(Ia∨Pa)) 2 ∀E 9 Fa∨(Ia∨Pa) 8,7 ⊃E 10 Ca⊃Ka 3 ∀E 11 Ka 10,7 ⊃E 12 Fa Ass 13 ? ? << 14 Ia ? 15 Ia∨Pa Ass 16 ? ? 17 Ia ? 18 Ia 9,14,17 ∨E 19 Ca&Ia 7,18 &I 20 (∃x)(Cx&Ix) 19 ∃I 21 (∃x)(Cx&Ix) 5,20 ∃E
At this point we are not quite sure what to do. Sometimes a way forward is by finding a contradiction and using reductio, in this case ~E. We have ∼Va at line 6 and the right hand side of 1 is Vx, so this might be a way to go.
1 (∀x)((Cx&(Kx&Fx))⊃Vx) Ass 2 (∀x)(Cx⊃(Fx∨(Ix∨Px))) Ass 3 (∀x)(Cx⊃Kx) Ass 4 ∼(∃x)(Kx&Px) Ass 5 (∃x)(Cx&∼Vx) Ass 6 Ca&∼Va Ass 7 Ca 6 &E 8 Ca⊃(Fa∨(Ia∨Pa)) 2 ∀E 9 Fa∨(Ia∨Pa) 8,7 ⊃E 10 Ca⊃Ka 3 ∀E 11 Ka 10,7 ⊃E 12 Fa Ass 13 ∼Ia Ass 14 ? ? << 15 Va ? 16 ? ? 17 ∼Va ? 18 Ia 15,17 ∼E 19 Ia∨Pa Ass 20 ? ? 21 Ia ? 22 Ia 9,18,21 ∨E 23 Ca&Ia 7,22 &I 24 (∃x)(Cx&Ix) 23 ∃I 25 (∃x)(Cx&Ix) 5,24 ∃E
Then
1 (∀x)((Cx&(Kx&Fx))⊃Vx) Ass 2 (∀x)(Cx⊃(Fx∨(Ix∨Px))) Ass 3 (∀x)(Cx⊃Kx) Ass 4 ∼(∃x)(Kx&Px) Ass 5 (∃x)(Cx&∼Vx) Ass 6 Ca&∼Va Ass 7 Ca 6 &E 8 Ca⊃(Fa∨(Ia∨Pa)) 2 ∀E 9 Fa∨(Ia∨Pa) 8,7 ⊃E 10 Ca⊃Ka 3 ∀E 11 Ka 10,7 ⊃E 12 Fa Ass 13 ∼Ia Ass 14 (Ca&(Ka&Fa))⊃Va 1 ∀E 15 ? ? << 16 Va ? 17 ∼Va 6 &E 18 Ia 16,17 ∼E 19 Ia∨Pa Ass 20 ? ? 21 Ia ? 22 Ia 9,18,21 ∨E 23 Ca&Ia 7,22 &I 24 (∃x)(Cx&Ix) 23 ∃I 25 (∃x)(Cx&Ix) 5,24 ∃E
We finish the reductio and are looking at a second ∨E
1 (∀x)((Cx&(Kx&Fx))⊃Vx) Ass 2 (∀x)(Cx⊃(Fx∨(Ix∨Px))) Ass 3 (∀x)(Cx⊃Kx) Ass 4 ∼(∃x)(Kx&Px) Ass 5 (∃x)(Cx&∼Vx) Ass 6 Ca&∼Va Ass 7 Ca 6 &E 8 Ca⊃(Fa∨(Ia∨Pa)) 2 ∀E 9 Fa∨(Ia∨Pa) 8,7 ⊃E 10 Ca⊃Ka 3 ∀E 11 Ka 10,7 ⊃E 12 Fa Ass 13 ∼Ia Ass 14 (Ca&(Ka&Fa))⊃Va 1 ∀E 15 Ka&Fa 11,12 &I 16 Ca&(Ka&Fa) 7,15 &I 17 Va 14,16 ⊃E 18 ∼Va 6 &E 19 Ia 17,18 ∼E 20 Ia∨Pa Ass 21 ? ? << 22 Ia ? 23 Ia 9,19,22 ∨E 24 Ca&Ia 7,23 &I 25 (∃x)(Cx&Ix) 24 ∃I 26 (∃x)(Cx&Ix) 5,25 ∃E
now all that is left is getting from Pa to Ia
1 (∀x)((Cx&(Kx&Fx))⊃Vx) Ass 2 (∀x)(Cx⊃(Fx∨(Ix∨Px))) Ass 3 (∀x)(Cx⊃Kx) Ass 4 ∼(∃x)(Kx&Px) Ass 5 (∃x)(Cx&∼Vx) Ass 6 Ca&∼Va Ass 7 Ca 6 &E 8 Ca⊃(Fa∨(Ia∨Pa)) 2 ∀E 9 Fa∨(Ia∨Pa) 8,7 ⊃E 10 Ca⊃Ka 3 ∀E 11 Ka 10,7 ⊃E 12 Fa Ass 13 ∼Ia Ass 14 (Ca&(Ka&Fa))⊃Va 1 ∀E 15 Ka&Fa 11,12 &I 16 Ca&(Ka&Fa) 7,15 &I 17 Va 14,16 ⊃E 18 ∼Va 6 &E 19 Ia 17,18 ∼E 20 Ia∨Pa Ass 21 Ia Ass 22 Pa Ass 23 ? ? << 24 Ia ? 25 Ia 20,21,24 ∨E 26 Ia 9,19,25 ∨E 27 Ca&Ia 7,26 &I 28 (∃x)(Cx&Ix) 27 ∃I 29 (∃x)(Cx&Ix) 5,28 ∃E
This is a bit of a puzzle (so again reductio might be in order). Another little hint or observation here is that we have not used line 4 at all (you don't have to use all the premises, but they are a resource for you). Line 4 is ∼(∃x)(Kx&Px) which cannot be used directly on its own. But it has a negation as its main connective which means it may play a role in reductio (especially when we realize that we have both Ka and Pa at lines 11 and 24). We do the steps, including EG, to produce the positive side of the contradiction
1 (∀x)((Cx&(Kx&Fx))⊃Vx) Ass 2 (∀x)(Cx⊃(Fx∨(Ix∨Px))) Ass 3 (∀x)(Cx⊃Kx) Ass 4 ∼(∃x)(Kx&Px) Ass 5 (∃x)(Cx&∼Vx) Ass 6 Ca&∼Va Ass 7 Ca 6 &E 8 Ca⊃(Fa∨(Ia∨Pa)) 2 ∀E 9 Fa∨(Ia∨Pa) 8,7 ⊃E 10 Ca⊃Ka 3 ∀E 11 Ka 10,7 ⊃E 12 Fa Ass 13 ∼Ia Ass 14 (Ca&(Ka&Fa))⊃Va 1 ∀E 15 Ka&Fa 11,12 &I 16 Ca&(Ka&Fa) 7,15 &I 17 Va 14,16 ⊃E 18 ∼Va 6 &E 19 Ia 17,18 ∼E 20 Ia∨Pa Ass 21 Ia Ass 22 Pa Ass 23 ∼Ia Ass 24 Ka&Pa 11,22 &I 25 (∃x)(Kx&Px) 24 ∃I 26 Ia 25,4 ∼E 27 Ia 20,21,26 ∨E 28 Ia 9,19,27 ∨E 29 Ca&Ia 7,28 &I 30 (∃x)(Cx&Ix) 29 ∃I 31 (∃x)(Cx&Ix) 5,30 ∃E
And that completes the proof.
The example argument is valid. The derivation that proves that it is valid is long and difficult (it might have been easier if rewrite rules had been used). Also, derivations are not unique. There are can be many different proofs of a theorem (or that an argument is valid). There may even be an 8 line proof of the above!
Exercise to accompany Predicate Tutorial 15.
Exercise 1(of 1)
Most experienced logicians are pretty familiar with the following theorems. Although the theorems are stated in terms of Fx and Gx etc. most of them hold of most formulas. Derive them. [You may use rewrite rules for these, if you wish.]
Proofs
a)∴ ((∀x)Fx)≡((∀y)Fy) (*change of variables*)
b) ∴ ((∀x)(∀y)Fxy)≡((∀y)(∀x)Fxy) (*permuting universal quantifiers*)
c) ∴ ((∃x)(∃y)Fxy)≡((∃y)(∃x)Fxy) (*permuting existential quantifiers*)
d) ∴ ((∃x)(∀y)Fxy)⊃((∀y)(∃x)Fxy)
e) Note that the following is not a theorem, see if you can produce a counter example
∴((∀y)(∃x)Fxy)⊃((∃x)(∀y)Fxy)
(*this is the 'everything has a cause therefore some (one) thing is the cause of everything' fallacy*)
Proofs
f) ∴ ((∃x)Fx)≡(∼(∀x)∼Fx) (*equivalence of connectives*)
g) ∴ (∼(∃x)∼Fx)≡((∀x)Fx) (*equivalence of connectives*)
h) ∴ (∀x)(Fx≡Gx)⊃((∀x)Fx≡(∀x)Gx)
(*but j) note that (or prove that) ∴(∀x)(Fx≡Gx)≡((∀x)Fx≡(∀x)Gx) is invalid*)
i) ∴ (∀x)(Fx≡Gx)⊃((∃x)Fx≡(∃x)Gx)
j) ∴ (∀x)(Fx⊃Gx)⊃((∀x)Fx⊃(∀x)Gx)
Proofs
k) ∴ (∀x)(Fx⊃Gx)⊃((∃x)Fx⊃(∃x)Gx)
l) ∴ ((∀x)Fx⊃(∀x)Gx)⊃(∃x)(Fx⊃Gx)
m) ∴ (∀x)(Fx&Gx)≡((∀x)Fx&(∀x)Gx)
n) ∴ (∀x)(Fx∨Gx)⊃((∀x)Fx∨(∃x)Gx)
o) ∴ ((∀x)Fx∨(∀x)Gx)⊃(∀x)(Fx∨Gx)
p) ∴ ((∃x)Fx∨(∃x)Gx)≡(∃x)(Fx∨Gx)
Interpretations Applet