Inferencing



Predicate logic is more powerful than propositional logic. It allows one to reason about properties and relationships of individual objects. In predicate logic, one can use some additional inference rules, which are discussed below, as well as those for propositional logic such as the equivalences, implications and inference rules.

The following four rules describe when and how the universal and existential quantifiers can be added to or deleted from an assertion.

These rules are explained below with examples.
For examples of reasoning using these rules and identities and implications from propositional logic, go to proofs of set theory theorems. .


1. Universal Instantiation

Rule:

x P(x)
-------
P(c)

where c is some arbitrary element of the universe.


Restrictions:

If c is a variable, then it must not already be quantified somewhere in P(x) --- see Explanation and Note below.


Explanation:

What this rule says is that from x P(x) one can infer P(c) for any object in the universe represented by the variable c, thus stripping off the universal quantifier. It should be noted that P holds for any specific object in the universe in this case. This rule follows because x P(x) says that P(x) holds true for all objects in the universe. Note that P(x), in general, may be a compound wff involving a number of predicates, variables, and quantifiers. Thus c in P(c) must not be a variable which is quantified within P(x). See Note below for an example of what can happen c is not properly chosen.


Example:

For example, the following argument can be proven correct using the Universal Instantiation:"No humans can fly. John Doe is human. Therefore John Doe can not fly."

First let us express this using the following notation:
F(x) means "x can fly."
H(x) means "x is human."
d is a symbol representing John Doe.

Then the argument is
[x [H(x) F(x)] H(d) ] F(d).

The proof is
1. x [H(x) F(x)] Hypothesis
2. H(d) Hypothesis
3. H(d) F(d) Universal instantiation on 1.
4. F(d) Modus ponens on 2 and 3.








Note:

If the restriction on the Universal Instantiation does not exist, then y x P(x,y) may become y P(y,y), that is y has been substituted for x by the Universal Instantiation, which is not correct.


2. Universal Generalization

Rule:

P(c)
----------
x P(x)

where P(c) holds for every element c of the universe of discourse.


Restrictions:

x must not appear as a free variable in P(c). Click universal generalization on the left for illustration for this point.


Explanation:

What this rule says is that if P(c) holds for any arbitrary element c of the universe, then we can conclude that x P(x).
If, however, c is supposed to represent some specific element of the universe that has the property P, then one can not generalize it to all the elements. For example, if P(x) means "x is fast", then all it means is that an unspecified element represented by x is fast. It does not necessarily mean that everything in the universe is fast.

This rule is something we can use when we want to prove that a certain property holds for every element of the universe. That is when we want to prove x P(x), we take an arbitrary element x in the universe and prove P(x). Then by this Universal Generalization we can conclude x P(x).


Example:

For example, consider the following argument: For every number x if x > 1, then x - 1 > 0. Also for every number x, x > 1. (Here we are making a hypothetical argument. We know, of course, every number is not greater than 1.)
Hence we conclude that for every number x, x - 1 >0.
This argument can be justified as follows using this Universal Generalization.

Let P(x) represent x > 1, and Q(x) represent x - 1 > 0.
Then the argument above is represented by
[x [P(x) Q(x)] P(x)] x Q(x).

To prove it we proceed as follows:
1. x [P(x) Q(x)] Hypothesis
2. x P(x) Hypothesis
3. [P(x) Q(x)] Universal Instantiation on 1.
4. P(x) Universal Instantiation on 2.
5. Q(x) Modus ponens on 3 and 4.
6. x Q(x) Universal Generalization on 6.










Note:

Without the restriction on Universal Generalization one may deduce x P(x) from P(x). However, this deduction is not correct. For what P(x) means is P(x) holds for an unspecified element x, but it does not necessarily mean that P(x) holds for all x.


3. Existential Instantiation

Rule:

x P(x)
-------
P(c)

where c is some element of the universe of discourse. It is not arbitrary but must be one for which P(c) is true.


Restrictions:

c must be a new name or constant symbol.


Explanation:

What this rule says is that if P holds for some element of the universe, then we can give that element a name such as c (or x, y, a etc). When selecting symbols, one must select them one at a time and must not use a symbol that has already been selected within the same reasoning/proof.


Example:

For example, if x P(X) x Q(x) is true, then select a name for P say c, then for Q (or vice versa) say d. One must NOT select c for Q as well as for P.

Consider the following argument: If you get 95 on the final exam for CS 398, then you get an A for the course. Someone, call him/her say c, gets 95 on the final exam. Therefore c gets an A for CS398. This argument uses Existential Instantiation as well as a couple of others as can be seen below.

Let the universe be the set of all people in the world, let N(x) mean that x gets 95 on the final exam of CS398, and let A(x) represent that x gets an A for CS398.

Then the proof proceeds as follows:
1. x [ N(x) A(x) ] Hypothesis
2. x N(x) Hypothesis
3. N(c) Existential instantiation on 3.
4. N(c) A(c) Universal instantiation on 1.
5. A(c) Modus ponens on 3 and 4.








In step 3 above, a specific person with property N was given the name c. For that same person c, the statement [ N(c) A(c) ] holds by the universal instantiation.
Note that the order of steps 3 and 4 can not be reversed.



4. Existential Generalization

Rule:

P(c)
----------
x P(x)

where c is an element of the universe.


Restrictions:

x must not appear free in P(c).


Explanation:

What this rule says is that if there is some element c in the universe that has the property P, then we can say that there exists something in the universe that has the property P.


Example:

For example the statement "if everyone is happy then someone is happy" can be proven correct using this existential generalization rule.

To prove it, first let the universe be the set of all people and let H(x) mean that x is happy.

Then the argument is
x [H(x) x H(x)]

The proof is
1. x H(x) Hypothesis
2. H(c) Universal instantiation
4. x H(x) Existential generalization.







Note:

Without the restriction that x must not appear free in P(c), one may produce an incorrect formula by existential generalization. For example, x Q(x, x) may be derived from Q(x,c) by existential generalization. But Q(x,c) x Q(x, x) is not valid, as you can see if Q(x,y) means "x is not equal to y", or "x > y", for example.



Back to Inferencing
Back to Predicate Logic