next up previous
Next: Acknowledgments Up: APPLICATIONS OF CIRCUMSCRIPTION Previous: APPENDIX A

APPENDIX B

Here is an annotated EKL proof that circumscribes the predicate e(x,y) discussed in section 6.

displaymath1561

What the user types is indicated by the numbered statements in lower case. What EKL types is preceded by semicolons at the beginning of each line and is in upper case. We omit EKL's type-out when it merely repeats what the command asked it to do, as in the commands DERIVE, ASSUME and DEFINE.

displaymath1562

Since EKL does not have attachments to determine the equivalence of names, we establish a correspondence between the names in our domain and some natural numbers.

displaymath1563

EKL does know about the distinctness of natural numbers, so this can be derived.

displaymath1564

We have to tell EKL to use the properties of equality rather than regarding it as just another predicate symbol in order to do the next step. Sometimes this leads to combinatorial explosion.

displaymath1565

This shows that two names themselves are distinct.

displaymath1566

Here we use second order logic to define the notion of equivalence relation. The first word after ``define'' is the entity being defined and included between vertical bars is the defining relation. EKL checks that an entity satisfying the relation exists.

displaymath1567

We define ax as a predicate we want our imitation equality to satisfy. We have chosen a very simple case, namely making a and b ``equal'' and nothing else.

displaymath1568

This defines ax1 as the second order predicate specifying the circumscription of ax.

displaymath1569

We now specify that e0 satisfies ax1. It takes till step 17 to determine what e0 actually is. When EKL includes circumscription as an operator, we may be able to write something like circumscribe(e0,ax1) and make this step occur. For now it's just an ordinary assumption.

displaymath1570

The predicate e2 defined here is what e0 will turn out to be.

displaymath1571

Now EKL agrees that e2 is an equivalence relation. This step takes the KL-10 about 14 seconds.

displaymath1572

Moreover it satisfies ax.

displaymath1573

A trivial step of expanding the definition of ax1. EKL tells us that this fact depends on the assumption CIRCUM. So do many of the subsequent lines of the proof, but we omit it henceforth to save space.

displaymath1574

The first conjunct of the previous step.

displaymath1575

We expand ax(e0) according to the definitions of ax and equiv.

displaymath1576

This is a fact of propositional calculus used as a rewrite rule in the next step. A program that can use circumscription by itself will either need to generate this step or systematically avoid the need for it.

displaymath1577

This is the least obvious step, because rewrite by cases is used after some preliminary transformation of the formula.

displaymath1578

DERIVE is substituting e2 for the variable e1 in step 11 and using the fact ax(e2) and step 15 to infer the conclusion of the implication that follows the quantifier tex2html_wrap_inline1637

displaymath1579

Expanding the definition of e2 tells us the final result of circumscribing e0(x,y). A more complex ax(e0) -- see step 5 -- would give a more complex result upon circumscription. However, it seems that the proof would be similar. Therefore, it could perhaps be made into some kind of macro.


next up previous
Next: Acknowledgments Up: APPLICATIONS OF CIRCUMSCRIPTION Previous: APPENDIX A

John McCarthy
Sat Jun 1 13:54:22 PDT 1996