缺省逻辑
公式命题逻辑
缺省逻辑是 Ray Reiter 提出的用来形式化有缺省假定的推理的非单调逻辑。 缺省逻辑可以表达像“缺省的,某个事物是真的”的事实;相反的,标准逻辑只能表达某个事物为真或某个事物为假。这是一个问题,因为推理经常涉及在多数时候是真但不总是真的事实的推理。经典的例子是: “鸟通常会飞”。这个规则可以在标准逻辑中表达为要么“所有鸟都会飞”,这与企鹅不会飞的事实相矛盾;要么“除了企鹅、鸵鸟 ... 的所有鸟都会飞”,这要求规则指定出所有的例外。缺省逻辑致力于形式化像这样的推理规则,而不需要明确提及所有的例外。
缺省逻辑的变体
缺省逻辑的下列变体同最初的语法和语义二者有所区别。
断言变体:断言是由一个公式和一个公式的集合构成的对。这种对指示P是真,当公式已经被假定为一致于证明P为真的时候。一个断言缺省理论由叫做背景理论的断言理论(断言公式的集合)和按原始语法定义的缺省的集合构成。当一个缺省应用于断言理论的时候,把由它的结论和它的论据合成的对增加到这个理论。下列语义使用了断言理论:
弱扩展:不再检查前件在由背景理论和已应用的缺省的结论构成的理论中是否是有效的,检查前件在将要生成的扩展中的有效性;换句话说,生成扩展的算法开始于猜测一个理论并使用它代替背景理论;从扩展生成的过程得到的结果实际上是一个扩展,只在它等价于在开始时所猜测的理论的时候。缺省逻辑的这个变体在原理上与自动认识逻辑有关,在那里理论 有一种模型,在其中x是真,只是因为假定 为真,公式 支持这个初始假定。
转换
缺省理论可以被转换成其他逻辑的理论或反之。转换要考虑下列条件:
转换典型的要求忠实或至少是结论保持,而模块化和同字母表的条件有时被忽略。
在命题缺省逻辑和下列逻辑之间的转换已经研究过了:
转换存在与否依赖于施加那种条件。从命题缺省逻辑到经典命题逻辑的转换不能总是生成多项式大小的命题理论,除非多项式层次瓦解。到自动认识逻辑的转换存在与否依赖于是否要求模块性或使用相同的字母表。
复杂性
关于缺省逻辑的下列问题的计算复杂性是已知的:
实现
有两个系统实现了缺省逻辑:DeReS和XRay
参考资料
最新修订时间:2022-08-26 10:36
目录
概述
缺省逻辑的变体
参考资料