Predicate Logic

Existential Instantiation

- 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, say d.
One must NOT select c for Q as well as for P.

Consider the following argument: If you get 95 on the fianl 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.