Using facts from the bank

Using Facts from the Bank

Using ∀xP(x)

P(x) indicates some statement about x and ∀xP(x) means that P(x) holds for every x. If you find ∀xP(x) in your fact bank, then you are free to add specializations of P(x) to the fact bank. A similar rule holds when there are two or more variables. For example, if the fact bank contains

(1) For every x and y, xy = yx.

then you can add another fact

(2) z(b+1) = (b+1)z.

You can do as many specializations as you like, getting new facts to suit your needs.

Using ∃xP(x)

∃xP(x) means that there exists some x so that statement P(x) is true. Suppose that your fact bank contains ∃xP(x). Then you are free to select one value, say a, so that P(a) is true. For example, if you already have

(1) ∃x(x is a zebra)

then you are free to choose a value z and add to the fact bank

(2) z is a zebra.

But you should only do this once, since your fact only tells you that there is at least one zebra.

If is common practice to use the same name for the selected thing as you use in the statement of its existence. For example, if you know

(3) ∃m (m > n).

then you can select a particular value and call it m, and add to the fact bank

(4) m > n.

In fact, it is common practice to combine steps (3) and (4) as "There exists an m such that

(5) m > n."

If you know that two or more things exist that have a particular property, then select a them as a group. For example, if the fact bank contains

(5) ∃x∃y(x > y)

then you can select particular values, say x = a and y = b, so that

(6) a > b.

Using A = B

If your fact bank contains an equation, A = B, then you are free to substitute B for A or A for B. For example, if you know

(1) 2x = 3y + 1.
(2) z + 2x = 4x + 5.

then you can add fact

(3) z + (3y + 1) = 4x + 5.

Using A → B

You usually use an implication in cases where you already have the left-hand side in the fact bank. For example, if you know

(1) Larry is a lizard.
(2) For every x, if x is a lizard then x has scales.

then you specialize fact (2) with x = Larry to get

(3) If Larry is a lizard then Larry has scales.

Now, combining facts (1) and (3) gives

(4) Larry has scales.

Using A ∨ B

If you know that either A or B is true, you often break the proof down into cases. In one case, you assume that A is true and prove your claim. In the other case, you assume that B is true and prove the claim again. No matter which it is, A or B, your claim is true. The next page explores using cases.