Lecture Notes 10: Predicate Logic Derivations

Predicate Logic Derivations

We can use the method of derivations, like in Sentential Logic, as a means to demonstrate that arguments in predicate logic are valid.

This method is particularly important for Predicate Logic, because, unlike Sentential Logic, there is no easy alternative method such as truth tables to use to show that an argument is valid.

The basic idea of a derivation in Predicate Logic is the same as for sentential logic.

Moreover, all the rules of derivation you learned for sentential logic (&O, &I, ∨O, ∨I, ↔O, ↔I, →O, DN, etc.) carry over to predicate logic.

The only difference is that, although in stating the rules, we use single letters to represent places where we can “plug in” formulas, the formulas themselves will never consist of single letters.

At minimum, they will consist of a capital letter and lowercase letter. They may also contain quantifiers and/or other logical operators.

Example:

The techniques of ID and CD also carry over.

Warning: we can only use CD for SHOW lines whose “main operator” is the if-then (→). This does not include statements that have if-thens within the scope of quantifiers.

If our show line is SHOW: ∀x(Nx → Ox), we cannot use CD, or, at least, not right away.

We could, however use it for SHOW: ∀xNx → ∀xOx.

Universal Out

We need new rules to use for our new logical signs: the quantifiers.

Again, these can be divided into “in” rules and “out” rules. Our first such rule is called “Universal Out”.

The “official” way of writing this is as follows:

This requires some explanation. The 𝓍 is any variable (x, y, or z). The 𝒜  is some statement containing that variable. 𝒜 [𝒶/𝓍] represents what that formula becomes when some name 𝒶 replaces the variable 𝓍.

More informally, we could write the rule as follows:

The quantifier must extend over the whole statement. We cannot apply this rule, or any other rule, to part of a line.

We start with something that says that some formula is true for all things x. (Or, for all things y …) Therefore, that formula would be true for any particular thing. So we can replace the variable that goes with the quantifier everywhere it occurs afterwards with the same name, and the result will be true. (We must replace every occurrence of the variable letter with the same name.)

For example, consider this argument:

For everything, if it is human, then it is mortal.
Therefore, if Socrates is human, then Socrates is mortal.

This argument has this form:

This is a valid reasoning step by ∀O.

Some example problems:

We must do the ∀O steps before →O steps.

We can do ∀O to any letter we like, and even to multiple letters within the same derivation. The only thing we are restricted from doing is replacing different occurrences of the variable with different letters in one step.

Here’s a use of ∀O within an ID.

Take multiple quantifiers in the same statement one at a time.

Existential In

Our next rule deals with existential quantifiers. Here, we move in the opposite direction. We begin with a statement about some particular individual: a, b, c, etc. We then conclude that the statement is true about something (or someone).

Here, you replace one or more occurrences of the letter with a variable, and introduce an existential quantifier, which will extend over the whole statement. (You may need to add parentheses.) If the letter “x” already occurs in the statement, you need to use “y” or “z”, etc., as required.

Consider the argument:

The Bandersnatch is frumious.
Therefore, something is frumious.

This has the form:

This is a valid step of ∃I reasoning.

Some examples:

Unlike ∀O, we do not need to replace all occurrences of the letter; we can replace only one—or more—as required.

Existential Out

The next rule we are going to learn is trickier. Recall that ∀O allows us to drop off a universal quantifier and replace the variable with any letter we like. Of course, a universal quantifier is used to say that something is true about everything there is. An existential quantifier just says that something is true for at least one thing, but it doesn’t tell us what that thing is.

Therefore, we can’t drop off an existential quantifier to any letter we like. Instead, we make up a new name for the person or thing that makes the existentially quantified statement true. Then we use that name. The process is somewhat like this.

Something lives on Venus.
(Let’s arbitrarily call that something ALF.)
Therefore, ALF lives on Venus.

This argument has this form.

A new name is one that does not occur anywhere previously in the derivation, not even on a SHOW line.

We must pick a new letter. We cannot assume that the thing making the quantified statement true is the same thing as anything we already know something about. So if we already have “a” earlier in our derivation, we must use “b”. If we already have “a” and “b”, we must use “c”, and so forth.

An example derivation.

We can use “a” at line 4 since it doesn’t appear above.

This problem shows that it’s almost always better to do ∃O steps before ∀O steps.

Notice that if we had done the ∀O step first, we would have had to use a different letter—say “b”—for the ∃O step, and then we wouldn’t be able to do →O!

Some more examples:

We used “c” since “a” and “b” already appear.

Universal Derivation

There is no rule “Universal In”. Instead, we have a new form of derivation. (Remember we did not have a rule of →I, only CD.)

It takes a lot to prove that a certain formula holds of everything. Certainly, it is not enough to prove that the formula holds of some particular things, or some particular things you know things about.

However, suppose you made up a new name, “Frabjous”, and you could prove that some formula was true of Frabjous, without knowing anything else at all about “Frabjous”. It must be that you could give the same proof about anything else in the world, since it couldn’t be anything special about Frabjous.

This is the basic idea behind universal deviation. If you want to SHOW: ∀x …x…, it suffices to show …n…, where “n” is a new, made-up name that doesn’t occur anywhere above in your derivation.

Unlike CD and ID, universal derivation (UD), does not involve making an assumption.

To set one up, we simply write in a new SHOW line, making use of a new letter.

Here’s an example.

First we write “UD” on the right. Then, without any assumption line, our next line will be a new show line where we drop off the quantifier, and replace all the occurrences of the variable with the same new name:

The idea is that, if I can show the formula about some arbitrary thing I know nothing about, I can prove the universally quantified formula.

Notice that 4 is a SHOW line. I can’t use it. I still don’t really know anything about this entity “a”. I’m just giving myself something new to prove. I can prove it using the other techniques: CD, ID, or DD.

Now that I’ve shown Fa & Ga, and crossed off the “SHOW” for that line, I remember that I used the letter “a” arbitrarily—I could have done the same derivation for any other individual. Therefore, I am entitled to cross off the “SHOW” at line 3, by UD.

Here’s a UD within a CD:

Here’s an ID within a UD.

Here’s an ID within a UD within a CD.