Decidability of ∀*∀‐Sentences in Membership Theories
作者:
Eugenio G. Omodeo,
Franco Parlamento,
Alberto Policriti,
期刊:
Mathematical Logic Quarterly
(WILEY Available online 1996)
卷期:
Volume 42,
issue 1
页码: 41-58
ISSN:0942-5616
年代: 1996
DOI:10.1002/malq.19960420105
出版商: WILEY‐VCH Verlag Berlin GmbH
关键词: Decidability;Fragment of set theory;NP‐complete;NP‐hard
数据来源: WILEY
摘要:
AbstractThe problem is addressed of establishing the satisfiability of prenex formulas involving a single universal quantifier, in diversified axiomatic set theories. A rather general decision method for solving this problem is illustrated through the treatment of membership theories of increasing strength, ending with a subtheory of Zermelo‐Fraenkel which is already complete with respect to the ∀*∀ class of sentences. NP‐hardness and NP‐completeness results concerning the problems under study are achieved and a technique for restricting the universal quantifier is presented.Mathematics Subject Classification:03B
点击下载:
PDF
(1007KB)
返 回