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.
My Menu
Saved Items

Presenting intuitive deductions via symmetric simplification

Frank PfenningContact Information and Dan NesmithContact Information

(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 Cprime, where C and Cprime 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)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.110 • Server: mpweb19
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)