Tutorial 25 ...

Logical System
12/26/13

You now have the 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

[Unfortunately the images in this Tutorial use ∧ for 'and' whereas the Bergmann convention is to use &. The images will be re-taken at some stage.]

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         Cx∧∼Vx Ass
7         ? ? <<
8         (∃x)(Cx∧Ix) ?
     
9     (∃x)(Cx∧Ix) 5,8 EI

We have used Tactics, and it seemed likely that the last line has come from Existential Instantion (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         Cx∧∼Vx Ass
7         ? ? <<
8         Cx∧Ix ?
9         (∃x)(Cx∧Ix) 8 EG
     
10     (∃x)(Cx∧Ix) 5,9 EI

Tactics, EG. Now our problem is to get from line 6 Cx∧∼Vx to line 8 Cx∧Ix. The Cxs will take care of themselves, so the problem is to get from∼ Vx to Ix. The only place that I appears is on the right hand side of 2. So we should take the Cx, 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         Cx∧∼Vx Ass
7         Cx 6 ∧E
8         ? ? <<
9         Ix ?
10         Cx∧Ix 7,9 ∧I
11         (∃x)(Cx∧Ix) 10 EG
     
12     (∃x)(Cx∧Ix) 5,11 EI

 

and then the right hand side of 2 (and 3 while we are working on Cx)

 

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         Cx∧∼Vx Ass
7         Cx 6 ∧E
8         Cx⊃(Fx∨(Ix∨Px)) 2 UI
9         Fx∨(Ix∨Px) 8,7 ⊃E
10         Cx⊃Kx 3 UI
11         Kx 10,7 ⊃E
12         ? ? <<
13         Ix ?
14         Cx∧Ix 7,13 ∧I
15         (∃x)(Cx∧Ix) 14 EG
     
16     (∃x)(Cx∧Ix) 5,15 EI

Now we are still trying to get Ix from a variety of things, but most obviously line 9 Fx∨(Ix∨Px) 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         Cx∧∼Vx Ass
7         Cx 6 ∧E
8         Cx⊃(Fx∨(Ix∨Px)) 2 UI
9         Fx∨(Ix∨Px) 8,7 ⊃E
10         Cx⊃Kx 3 UI
11         Kx 10,7 ⊃E
12             Fx Ass
13             ? ? <<
14             Ix ?
         
15             Ix∨Px Ass
16             ? ?
17             Ix ?
         
18         Ix 9,14,17 ∨E
19         Cx∧Ix 7,18 ∧I
20         (∃x)(Cx∧Ix) 19 EG
     
21     (∃x)(Cx∧Ix) 5,20 EI

At this point we are not quite sure what to do. Sometimes a way forward is by finding a contradiction and using reductio. We have ∼Vx 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         Cx∧∼Vx Ass
7         Cx 6 ∧E
8         Cx⊃(Fx∨(Ix∨Px)) 2 UI
9         Fx∨(Ix∨Px) 8,7 ⊃E
10         Cx⊃Kx 3 UI
11         Kx 10,7 ⊃E
12             Fx Ass
13             (Cx∧(Kx∧Fx))⊃Vx 1 UI
14             Kx∧Fx 11,12 ∧I
15             Cx∧(Kx∧Fx) 7,14 ∧I
16             ? ? <<
17             Ix ?
         
18             Ix∨Px Ass
19             ? ?
20             Ix ?
         
21         Ix 9,17,20 ∨E
22         Cx∧Ix 7,21 ∧I
23         (∃x)(Cx∧Ix) 22 EG
     
24     (∃x)(Cx∧Ix) 5,23 EI

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         Cx∧∼Vx Ass
7         Cx 6 ∧E
8         Cx⊃(Fx∨(Ix∨Px)) 2 UI
9         Fx∨(Ix∨Px) 8,7 ⊃E
10         Cx⊃Kx 3 UI
11         Kx 10,7 ⊃E
12             Fx Ass
13             (Cx∧(Kx∧Fx))⊃Vx 1 UI
14             Kx∧Fx 11,12 ∧I
15             Cx∧(Kx∧Fx) 7,14 ∧I
16             Vx 13,15 ⊃E
17             ∼Vx 6 ∧E
18             ? ? <<
19             ∼∼Ix ?
20             Ix 19 ∼E
         
21             Ix∨Px Ass
22             ? ?
23             Ix ?
         
24         Ix 9,20,23 ∨E
25         Cx∧Ix 7,24 ∧I
26         (∃x)(Cx∧Ix) 25 EG
     
27     (∃x)(Cx∧Ix) 5,26 EI

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         Cx∧∼Vx Ass
7         Cx 6 ∧E
8         Cx⊃(Fx∨(Ix∨Px)) 2 UI
9         Fx∨(Ix∨Px) 8,7 ⊃E
10         Cx⊃Kx 3 UI
11         Kx 10,7 ⊃E
12             Fx Ass
13             (Cx∧(Kx∧Fx))⊃Vx 1 UI
14             Kx∧Fx 11,12 ∧I
15             Cx∧(Kx∧Fx) 7,14 ∧I
16             Vx 13,15 ⊃E
17             ∼Vx 6 ∧E
18                 ∼Ix Ass
19                 Absurd 16,17 AbsI
             
20             ∼∼Ix 19 ∼I
21             Ix 20 ∼E
         
22             Ix∨Px Ass
23             ? ? <<
24             Ix ?
         
25         Ix 9,21,24 ∨E
26         Cx∧Ix 7,25 ∧I
27         (∃x)(Cx∧Ix) 26 EG
     
28     (∃x)(Cx∧Ix) 5,27 EI

now all that is left is getting from Px to Ix

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         Cx∧∼Vx Ass
7         Cx 6 ∧E
8         Cx⊃(Fx∨(Ix∨Px)) 2 UI
9         Fx∨(Ix∨Px) 8,7 ⊃E
10         Cx⊃Kx 3 UI
11         Kx 10,7 ⊃E
12             Fx Ass
13             (Cx∧(Kx∧Fx))⊃Vx 1 UI
14             Kx∧Fx 11,12 ∧I
15             Cx∧(Kx∧Fx) 7,14 ∧I
16             Vx 13,15 ⊃E
17             ∼Vx 6 ∧E
18                 ∼Ix Ass
19                 Absurd 16,17 AbsI
             
20             ∼∼Ix 19 ∼I
21             Ix 20 ∼E
         
22             Ix∨Px Ass
23                 Ix Ass
             
24                 Px Ass
25                 ? ? <<
26                 Ix ?
             
27             Ix 22,23,26 ∨E
         
28         Ix 9,21,27 ∨E
29         Cx∧Ix 7,28 ∧I
30         (∃x)(Cx∧Ix) 29 EG
     
31     (∃x)(Cx∧Ix) 5,30 EI

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 Kx and Px at lines 11 and 24).

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         Cx∧∼Vx Ass
7         Cx 6 ∧E
8         Cx⊃(Fx∨(Ix∨Px)) 2 UI
9         Fx∨(Ix∨Px) 8,7 ⊃E
10         Cx⊃Kx 3 UI
11         Kx 10,7 ⊃E
12             Fx Ass
13             (Cx∧(Kx∧Fx))⊃Vx 1 UI
14             Kx∧Fx 11,12 ∧I
15             Cx∧(Kx∧Fx) 7,14 ∧I
16             Vx 13,15 ⊃E
17             ∼Vx 6 ∧E
18                 ∼Ix Ass
19                 Absurd 16,17 AbsI
             
20             ∼∼Ix 19 ∼I
21             Ix 20 ∼E
         
22             Ix∨Px Ass
23                 Ix Ass
             
24                 Px Ass
25                 Kx∧Px 11,24 ∧I
26                 ? ? <<
27                 Ix ?
             
28             Ix 22,23,27 ∨E
         
29         Ix 9,21,28 ∨E
30         Cx∧Ix 7,29 ∧I
31         (∃x)(Cx∧Ix) 30 EG
     
32     (∃x)(Cx∧Ix) 5,31 EI

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         Cx∧∼Vx Ass
7         Cx 6 ∧E
8         Cx⊃(Fx∨(Ix∨Px)) 2 UI
9         Fx∨(Ix∨Px) 8,7 ⊃E
10         Cx⊃Kx 3 UI
11         Kx 10,7 ⊃E
12             Fx Ass
13             (Cx∧(Kx∧Fx))⊃Vx 1 UI
14             Kx∧Fx 11,12 ∧I
15             Cx∧(Kx∧Fx) 7,14 ∧I
16             Vx 13,15 ⊃E
17             ∼Vx 6 ∧E
18                 ∼Ix Ass
19                 Absurd 16,17 AbsI
             
20             ∼∼Ix 19 ∼I
21             Ix 20 ∼E
         
22             Ix∨Px Ass
23                 Ix Ass
             
24                 Px Ass
25                 Kx∧Px 11,24 ∧I
26                 (∃x)(Kx∧Px) 25 EG
27                 ? ? <<
28                 Ix ?
             
29             Ix 22,23,28 ∨E
         
30         Ix 9,21,29 ∨E
31         Cx∧Ix 7,30 ∧I
32         (∃x)(Cx∧Ix) 31 EG
     
33     (∃x)(Cx∧Ix) 5,32 EI

We set out on the reductio via the double negation.

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         Cx∧∼Vx Ass
7         Cx 6 ∧E
8         Cx⊃(Fx∨(Ix∨Px)) 2 UI
9         Fx∨(Ix∨Px) 8,7 ⊃E
10         Cx⊃Kx 3 UI
11         Kx 10,7 ⊃E
12             Fx Ass
13             (Cx∧(Kx∧Fx))⊃Vx 1 UI
14             Kx∧Fx 11,12 ∧I
15             Cx∧(Kx∧Fx) 7,14 ∧I
16             Vx 13,15 ⊃E
17             ∼Vx 6 ∧E
18                 ∼Ix Ass
19                 Absurd 16,17 AbsI
             
20             ∼∼Ix 19 ∼I
21             Ix 20 ∼E
         
22             Ix∨Px Ass
23                 Ix Ass
             
24                 Px Ass
25                 Kx∧Px 11,24 ∧I
26                 (∃x)(Kx∧Px) 25 EG
27                 ? ? <<
28                 ∼∼Ix ?
29                 Ix 28 ∼E
             
30             Ix 22,23,29 ∨E
         
31         Ix 9,21,30 ∨E
32         Cx∧Ix 7,31 ∧I
33         (∃x)(Cx∧Ix) 32 EG
     
34     (∃x)(Cx∧Ix) 5,33 EI

Laying it out.

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         Cx∧∼Vx Ass
7         Cx 6 ∧E
8         Cx⊃(Fx∨(Ix∨Px)) 2 UI
9         Fx∨(Ix∨Px) 8,7 ⊃E
10         Cx⊃Kx 3 UI
11         Kx 10,7 ⊃E
12             Fx Ass
13             (Cx∧(Kx∧Fx))⊃Vx 1 UI
14             Kx∧Fx 11,12 ∧I
15             Cx∧(Kx∧Fx) 7,14 ∧I
16             Vx 13,15 ⊃E
17             ∼Vx 6 ∧E
18                 ∼Ix Ass
19                 Absurd 16,17 AbsI
             
20             ∼∼Ix 19 ∼I
21             Ix 20 ∼E
         
22             Ix∨Px Ass
23                 Ix Ass
             
24                 Px Ass
25                 Kx∧Px 11,24 ∧I
26                 (∃x)(Kx∧Px) 25 EG
27                     ∼Ix Ass
28                     ? ? <<
29                     Absurd ?
                 
30                 ∼∼Ix 29 ∼I
31                 Ix 30 ∼E
             
32             Ix 22,23,31 ∨E
         
33         Ix 9,21,32 ∨E
34         Cx∧Ix 7,33 ∧I
35         (∃x)(Cx∧Ix) 34 EG
     
36     (∃x)(Cx∧Ix) 5,35 EI

Finally, completing the proof

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         Cx∧∼Vx Ass
7         Cx 6 ∧E
8         Cx⊃(Fx∨(Ix∨Px)) 2 UI
9         Fx∨(Ix∨Px) 8,7 ⊃E
10         Cx⊃Kx 3 UI
11         Kx 10,7 ⊃E
12             Fx Ass
13             (Cx∧(Kx∧Fx))⊃Vx 1 UI
14             Kx∧Fx 11,12 ∧I
15             Cx∧(Kx∧Fx) 7,14 ∧I
16             Vx 13,15 ⊃E
17             ∼Vx 6 ∧E
18                 ∼Ix Ass
19                 Absurd 16,17 AbsI
             
20             ∼∼Ix 19 ∼I
21             Ix 20 ∼E
         
22             Ix∨Px Ass
23                 Ix Ass
             
24                 Px Ass
25                 Kx∧Px 11,24 ∧I
26                 (∃x)(Kx∧Px) 25 EG
27                     ∼Ix Ass
28                     Absurd 26,4 AbsI
                 
29                 ∼∼Ix 28 ∼I
30                 Ix 29 ∼E
             
31             Ix 22,23,30 ∨E
         
32         Ix 9,21,31 ∨E
33         Cx∧Ix 7,32 ∧I
34         (∃x)(Cx∧Ix) 33 EG
     
35     (∃x)(Cx∧Ix) 5,34 EI

 

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.]

a) ∴ ((∀x)F)≡F (*this is true for any formula F provided that x is not free in F*)

b)∴ ((∀x)Fx)≡((∀y)Fy) (*change of variables*)

c) ∴ ((∀x)(∀y)Fxy)≡((∀y)(∀x)Fxy) (*permuting universal quantifiers*)

d) ∴ ((∃x)(∃y)Fxy)≡((∃y)(∃x)Fxy) (*permuting existential quantifiers*)

e) ∴ ((∃x)(∀y)Fxy)⊃((∀y)(∃x)Fxy)

f) 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*)

g) ∴ ((∃x)Fx)≡(∼(∀x)∼Fx) (*equivalence of connectives*)

h) ∴ (∼(∃x)∼Fx)≡((∀x)Fx) (*equivalence of connectives*)

i) ∴ (∀x)(Fx≡Gx)⊃((∀x)Fx≡(∀x)Gx)

(*but j) note that (or prove that) ∴(∀x)(Fx≡Gx)≡((∀x)Fx≡(∀x)Gx) is invalid*)

k) ∴ (∀x)(Fx≡Gx)⊃((∃x)Fx≡(∃x)Gx)

l) ∴ (∀x)(Fx⊃Gx)⊃((∀x)Fx⊃(∀x)Gx)

m) ∴ (∀x)(Fx⊃Gx)⊃((∃x)Fx⊃(∃x)Gx)

n) ∴ ((∀x)Fx⊃(∀x)Gx)⊃(∃x)(Fx⊃Gx)

o) ∴ (∀x)(Fx∧Gx)≡((∀x)Fx∧(∀x)Gx)

p) ∴ (∀x)(Fx∨Gx)⊃((∀x)Fx∨(∃x)Gx)

q) ∴ ((∀x)Fx∨(∀x)Gx)⊃(∀x)(Fx∨Gx)

r) ∴ ((∃x)Fx∨(∃x)Gx)≡(∃x)(Fx∨Gx)


Interpretations Widget