Proving theorems based on equivalent transformation using resolution and factoring

摘要

We propose a method for proving theorems based on equivalent transformation (ET). As opposed to conventional proof methods, our proof method uses meaning-preserving Skolemization, which necessitates incorporation of function variables and accordingly requires an extension of first-order formulas. Using the proposed method, a proof problem in first-order logic is converted into a problem of checking unsatisfiability of an existentially quantified conjunctive normal form, which can be identified with a set of extended clauses by assuming implicit global existential quantifications of function variables and implicit clause conjunction. Checking unsatisfiability of a set of extended clauses is realized by successive application of ET rules for transforming extended clauses. ET rules corresponding to resolution and factoring in first-order logic are established for extended clauses.