Reference Manual
Chapter Seven:
Predicate Logic: Symbolization and Deduction

.pdf Version for Printing

This reference provides some of the basic points made in Chapter Six. In this chapter, we turn back to our formal language with names and predicates. But we add one small but terribly important element: the ability to talk about quantities. In English, this just means the words "all" and "some". This little wrinkle will take some time to develop. .

Contents
: Section 1: Predicate Logic and Derivations: Introduction; Section 2: A Special Case: Derivations in Categorical Logic; Section 3:^I and Strategy

 

1. Predicate Logic and Derivations: Introduction

We need to introduce new derivation rules. We have two quantifiers and we need rules for each. We'll need enough rules so that we can break down premises with main connective ^ or % and so that we can build up sentences with those connectives. Fortunately, these rules are mostly very easy. In fact we've already mentioned one while symbolizing.

Universal Elimination: ^E

Let's begin with an example application of a new but trivial rule. The rule is called^E and just eliminates the universal quantifier. And the idea is simple. If everything (in the universe of discourse) has property C, then a particular member of the universe of discourse must also:

Premise 1 (^x)(Mx&~Rx)
Premise 2 (^x)Cx
2 ^E 3 Cf
1 ^E 4 Mt&~Rt

Also, line 4 just says that, by universal elimination, t, is mammal and not a reptile.

What's going on here? We are simply taking a universally quantified sentence (^x)P and putting a name in the place of x after dropping the quantifier:P(a).

Here then is our first new rule:

^E
input:

output:
(^x)P

 P(a)

(Because 'a' is colored, we see that it is a metavariable: Any name can take it's place.)

2. Let's move on to a second new rule.

Existential Introduction: %I

The next rule is just as simple. We want a way to build a sentence with main connective %. So, the rule is called "%I".

We can see how this rule works by extending our simple derivation.

 

Premise 1 (^x)(Mx&~Rx)
Premise 2 (^x)Cx
2 ^E 3 Cf
1 ^E 4 Mt&~Rt
3 %I 5 (%x)Cx

This inference, from 3 to 5, is trivial, right? Line 3 says that f is C (that Felix is a cat), so we conclude that something is C (that something is a cat). Nothing too complicated!

In any case, the form of the thinking is a bit the reverse of ^E: line 3 is the substitution instance of 5. The general statement of the rule, then, is:

%I
input:

output:
 P(a)

 (%x)Px

The idea is simple: If a is a P, then something is a P! (Remember that a is a stand-in or placeholder for any name; it's a metavariable.)

^E
input:

output:
(^x)P

 P(a)
     
%I
input:

output:
 P(a)

 (%x)Px

...along with two very simple applications:
 

...we will add only one very simple and intuitive rule of replacement. In fact we've already seen this in action. This was how we put it back in chapter 6.

QN: "no cats are reptiles" can be symbolized '~(%x)Rx' or, equivalently, '(^x)~Rx'.

Where are universe of discourse remains just cats, we have two ways of saying that none are reptiles: "it's not the case that one is a reptile" ('~(%x)Rx') and "all are non-reptiles" ('(^x)~Rx'). They are logically equivalent.

Similarly,

QN (new form): "not all cats are wild" can be symbolized as '~(^x)Wx' (the literal symbolization) or as '(%x)~Wx' ("some cats are tame").

This is just to say that tildes and quantifiers can be switched if the quantifier type changes from '^' to '%' or vice versa. Or in our usual double arrow representation:

QN
(Quantifier Negation)
~(^x)P (%x)~P
or
~(%x)P (^x)~P

 

2. A Special Case: Derivations in Categorical Logic

We can use our derivation system as developed so far to show that much of categorical logic can be comprehended within

 

Conversion via CM

We have seen that commutation gives a logical equivalence for existential and negative categorical sentences.

"Some S are P" is logically equivalent to "Some P are S".

and

"No S are P" is logically equivalent to "No P are S".

For examples,

(*) "Some mammals are carnivores" is logically equivalent to "Some carnivores are mammals".

and

(**) "No mammals are reptiles " is logically equivalent to "Some reptiles are mammals".

OK? Now, if these are really equivalent, then their symbolizations in PL should be equivalent too. Let's see that they are.

First, to symbolize the sentences in (*) we would write these:

(* in PL)                       

(%x)(Mx&Cx)

(%x)(Cx&Mx)

Now, are these two logically equivalent? The answer is yes. All we need to do is show how to derive one from the other.

The derivation test for equivalence of two sentences is to show that if either one is taken as premise, then the other can be derived.

But to deriving one from the other is a snap, it's just CM:

Notice that this is just our old way of doing two derivations on one page to show logical equivalence. We've derived one from the other, so
   (%x)(Mx&Cx)

and
  
(%x)(Cx&Mx)
are logically equivalent: there is no way for one to be true without the other.

 

Now, let's see if we can do the same thing with

"No S are P" is logically equivalent to "No P are S".

and

(**) "No mammals are reptiles " is logically equivalent to "Some reptiles are mammals".

First we symbolize.

(* in PL)                       

~(%x)(Mx&Cx)

~(%x)(Cx&Mx)

 

There is an alternative symbolization for "No S are P": that is '(^x)(Sx>~Px)'. We will get a hint how to move back and forth between this and "No P are S"='(^x)(Px>~Sx)' in the next section of this tutorial. It's really very easy and it's 7.1b. (Hint: use TR.)

 

 

 

 

 

Contraposition via TR

 

All tigers are mammals.

and

All non-mammals are non-tigers.

Can be show logically equivalent. Here's the little proof:

Using TR, transposition, allows us an easy proof of equivalence.

And this makes perfectly good sense: If all tigers are mammals, then surely any non-mammal can't be a tiger.

OK?

 

Obversion via QN

Here's an example of two categorical statements that are obviously logically equivalent:

(*) All tigers are carnivores.

From our Venn diagrams, we know that this means: there is not tiger that is not also a carnivore. In other words, (*) is logically equivalent to

(**) No tigers are non-carnivores.

 

 

This one takes a few more steps. But the only new rule in the mix is QN.

 

 

 

 

3. ^I and Strategy

To think about our last rule of inference, take an example of a valid categorical syllogism.

All tigers are mammals.
All mammals are animals.
So, all tigers are animals.

Not very interesting...but it is clearly valid. In symbols:

(^x)(Tx>Mx)
(^x)(Mx>Ax)
(^x)(Tx>Ax)

Now let's think about doing a derivation of the conclusion. Look at the main connective of your two premises, in both cases it is the universal quantifier. So use ^I:

 

Once you eliminate the ^ and justify lines 3 and 4, you can use HS.

But what to do next? You know only that if a is a tiger, then a is an animal!

 

 

 

Here's a hint. We've substituted in with 'a', but of course we could have picked 'b', or 'c', or any name we might want to give for anything in the universe of discourse. (Hint: this will mean that 'a' is arbitrary!)

Whenever a name is arbitrary in this way, we pulled it out of the blue (so to speak), it could stand for anything.

That's the idea behind ^I: we generalize from a particular instance, so long as the instance uses the arbitrary name.

So, the last two lines of our derivation will look like this:

5-10 >I 11 (Ma&~Fa)>Pa                 
11 ^I 12

(^x)[(Mx&~Fx)>Px]

 

Line 11 we understand in this way: "If an arbitrary person makes more than four thousand dollars but does not file, then he or she will be prosecuted". As long as 'a' is arbitrary, then, the step to line 12 makes sense.

As you see, this is exactly what we call ^I: the move from a substitution instance with arbitrary variable to the universally quantified sentence.

Now for the big question: How do we tell when a name is arbitrary? Our prescription is fairly simple: make sure the name does not occur in any premise or undischarged assumption and does not occur in the line derived by ^I. Here's the general formulation:

^I
input:

output:
P(a)

(^x)P

Provided 'a' is arbitrary in this sense:

  •  'a' does not occur in any premise or in the assumption of a subderivation still in progress (unterminated).
  •  'a' does not occur in P.

 

 

Finally let's think about strategy. The last little example will help.

We start with the premise that is about a specific thing named by 'c'.

And we have a goal: '(^x)Lx'

 

 

 

 

Because the first conjunct of the premise seems to have nothing to do with the goal, use &E to "bring down" the second conjunct to line 2.

 

 

 

 

 

Now, because everything is both L and J (says line 2), we can conclude that a is both.

Careful, one needs to pick a brand new name to make sure it is "arbitrary". Don't' pick 'c'...it's in the premise!

 

 

 

 

Now, use &E again...and again in a way that leads toward your goal.

And...

 

 

 

 

We are done by the new rule.

Because 'a' is arbitrary, it could be anything! So, we can rightly conclude that everything has property L.

 

Notice that we use elimination rules to break sentences down (here &E and ^E) and then introduction rules to build back up (here ^I).

But what do we do when we don't have an "E" rule for breaking down? For example, we don't have %E. Here's what we need to do instead.

1. Take this example:

 

 

2. Because there is little else to do, set up for RD: make an assumption that is the opposite of what you need to prove.

 

 

 

3. You can do some work from here. But it's important not to don anything that won't lead toward the conclusion. But do the obvious if it looks hopeful:

 

 

4. But then you run out of hope! At least until you find an intermediate goal. You need a contradiction by line 9. There is no other use for line 1 than to be part of a contradiction (because there is no %E rule). So, figure that line 8 and 9 need to be like so. This is working backwards from your goal: strategic thinking!

 

 

5. Finish by using now familiar rules that lead to 8. Erase the question marks at 10 and you're done!