我一直在阅读一些关于将一阶逻辑 (FOL) 句子转换为连接范式 (CNF)，然后执行解析的笔记。
转换为 CNF 的步骤之一是Standardize variables.
如果我不标准化变量，我一直在寻找为什么解析算法的完整条件违反并且健全性不违反。
任何人都可以添加细节，为什么只是违反完整性，而完整性仍然存在？
user4012783
问问题
386 次
1 回答
1
这是一个可以帮助您形象化的示例。假设你的理论是
(for all X : nice(X)) or (for all X : smart(X)) (1)
如果分开标准化，将产生 CNF：
nice(X) or smart(Y)
也就是说，人群中的每个人都很好，或者人群中的每个人都很聪明，或者两者兼而有之。
将标准化分开将产生 CNF
nice(X) or smart(X)
这相当于
(for all X : nice(X) or smart(X)) (2)
也就是说，对于群体中的每个人来说，那个人是好人，还是聪明人，或者两者兼而有之。
这个理论（2）比原来的理论（1）说得更少，它更弱，因为它承认了这样一种情况：每个人都不是很好，每个人都不是很聪明，但它是确实，每个人都是一个或另一个或两者兼而有之。换句话说，（2）并不意味着（1），但（1）意味着（2）（如果整个人口都是好的，那么每个人都是好的；如果整个人口都是聪明的，那么每个人都是聪明的；因此，每个人要么善良要么聪明）。(2) 接受的可能世界集合严格大于 (1) 接受的可能世界集合。
这对完整性和健全性有什么看法？
使用 (2) 是不完整的，因为我可以向您展示 (1) 中的真定理的反例，该定理在使用 (2) 时未被证明为真。考虑定理“如果约翰不是很好但很聪明，那么丽兹很聪明”。鉴于（1），这是正确的，因为如果整个人口都具有这两种品质之一，那么它一定是“聪明的”，因为约翰并不好，所以丽兹（和其他所有人）也一定很聪明。然而，考虑到（2），这不再是真的（可能是 Liz 很好但不聪明，其他人都是其中之一，考虑到（2）仍然可以）。所以我不能再用 (2) 证明一个真实的定理（在去掉标准化之后），因此我的推论是不完整的。
现在假设我使用 (2) 证明某个定理 T 为真。这意味着 T 在 (2) 成立的每个可能世界中成立，包括在 (1) 中成立的子集（根据此处的第三段）。因此 T 在 (1) 中也是正确的，因此使用 (2) 进行推理仍然是合理的。
简而言之：当你不标准化时，你“加入”了关于整个领域（人口）的陈述，并使它们关于个人，这将更弱，不会暗示一些以前暗示的事实；它们将丢失，您的程序将不完整。
于 2015-03-13T00:31:45.097 回答