Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Presenting intuitive deductions via symmetric simplification
| |
|
Presenting intuitive deductions via symmetric simplification
Frank Pfenning1 and Dan Nesmith2 
| (1) |
School of Computer Science, Carnegie Mellon University, 15213 Pittsburgh, PA, USA |
| (2) |
Department of Mathematics, Carnegie Mellon University, 15213 Pittsburgh, PA, USA |
Abstract
In automated deduction systems that are intended for human use, the presentation of a proof is no less important than its discovery. For most of today's automated theorem proving systems, this requires a non-trivial translation procedure to extract human-oriented deductions from machine-oriented proofs. Previously known translation procedures, though complete, tend to produce unintuitive deductions. One of the major flaws in such procedures is that too often the rule of indirect proof is used where the introduction of a lemma would result in a shorter and more intuitive proof.
We present an algorithm, symmetric simplification, for discovering useful lemmas in deductions of theorems in first- and higher-order logic. This algorithm, which has been implemented in the TPS system, has the feature that resulting deductions may no longer have the weak subformula property. It is currently limited, however, in that it only generates lemmas of the form C v C , where C and C have the same negation normal form.
This work was supported in part by NSF grant CCR-8702699 and in part by the Defense Advanced Research Projects Agency (DOD), ARPA Order No. 5404, monitored by the Office of Naval Research under contract N00014-84-K-0415.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|