Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-18T02:21:20.289Z Has data issue: false hasContentIssue false

On the reduction of the decision problem

Published online by Cambridge University Press:  12 March 2014

László Kalmár
Affiliation:
The Bolyai Institute, University Of Szeged
János Surányi
Affiliation:
The Bolyai Institute, University Of Szeged

Extract

In the first paper of the above main title, one of us has proved that any formula of the first order predicate calculus is equivalent (as to being satisfiable or not) to some binary first order formula having a prefix of the form (Ex1)(x2)(Ex3) … (xn) and containing a single predicate variable. This result is an improvement of a theorem of Ackermann stating that any first order formula is equivalent to another with a prefix of the above form but saying nothing about the number of predicate variables appearing therein. Hence the question arises if other theorems reducing the decision problem to the satisfiability question of the first order formulas with a prefix of a special form can be improved in like manner. In the present paper we shall answer this question concerning Gödel's reduction theorem stating that any first order formula is equivalent to another the prefix of which has the form

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1947

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable