In 1928, Bernays and Schoenfinkel proved the decidability of prenex sentences whose matrices contain no function symbols, now known as the Bernays-Schoenfinkel (BS) class. We investigate the decidability of the BS class for all Goedel logics. Our validity argument relies on the fact that Skolemization works for prenex Goedel logics, while 1-satisfiability follows from structural properties of prenex formulas. We show that validity and 1-satisfiability for the BS class are decidable in every Goedel logic, and that these properties persist across all infinite Goedel logics.


翻译:1928年,Bernays与Schoenfinkel证明了不含函数符号的前束范式语句的可判定性,该语句类现称为Bernays-Schoenfinkel(BS)类。本文研究所有哥德尔逻辑中BS类的可判定性问题。我们的有效性论证基于以下事实:Skolem化方法适用于前束哥德尔逻辑,而1-可满足性则源于前束公式的结构性质。我们证明在任意哥德尔逻辑中,BS类的有效性与1-可满足性均是可判定的,且这些性质在所有无限哥德尔逻辑中均保持成立。

0
下载
关闭预览

相关内容

NeurIPS 2021 | 寻找用于变分布泛化的隐式因果因子
专知会员服务
17+阅读 · 2021年12月7日
专知会员服务
25+阅读 · 2021年7月31日
【ICML2021】因果匹配领域泛化
专知
12+阅读 · 2021年8月12日
【NeurIPS2019】图变换网络:Graph Transformer Network
NAACL 2019 | 一种考虑缓和KL消失的简单VAE训练方法
PaperWeekly
20+阅读 · 2019年4月24日
基于Lattice LSTM的命名实体识别
微信AI
48+阅读 · 2018年10月19日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
VIP会员
相关VIP内容
相关资讯
【ICML2021】因果匹配领域泛化
专知
12+阅读 · 2021年8月12日
【NeurIPS2019】图变换网络:Graph Transformer Network
NAACL 2019 | 一种考虑缓和KL消失的简单VAE训练方法
PaperWeekly
20+阅读 · 2019年4月24日
基于Lattice LSTM的命名实体识别
微信AI
48+阅读 · 2018年10月19日
相关基金
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
2+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
Top
微信扫码咨询专知VIP会员