缺省逻辑

缺省逻辑是Raymond Reiter提出的非单调逻辑,用于使用默认假设来形式化推理。

缺省逻辑可以表达“默认情况下,某些事情是真实的”等事实; 相比之下,标准逻辑只能表达某些事物是真实的或某些事物是错误的。 这是一个问题,因为推理通常涉及在大多数情况下都是正确的事实,但并非总是如此。 一个典型的例子是:“鸟类通常会飞”。 这个规则可以用标准逻辑表达,或者是“所有鸟类飞翔”,这与企鹅不会飞行的事实不符,或者是“所有不是企鹅而不是鸵鸟和……飞翔的鸟类”,这需要所有要指定的规则的例外情况。 缺省逻辑旨在形式化这样的推理规则,而没有明确提及它们的所有异常。

缺省逻辑的语法
默认理论是一对  。 W是一组逻辑公式,称为背景理论,它将已知的事实形式化。 D是一组默认规则,每个规则都是以下形式:

根据这个默认值,如果我们认为先决条件是真的,那么每个 {\ displaystyle \ mathrm {Justification} _ {i}} 与我们目前的信念一致,我们被认为结论是正确的。

W中的逻辑公式和默认中的所有公式最初都假定为一阶逻辑公式,但它们可能是任意形式逻辑中的公式。 它们是命题逻辑中的公式的情况是研究最多的案例之一。

例子
默认规则“鸟类通常飞行”通过以下默认设置形式化:

这个规则意味着,如果X是一只鸟,并且可以假设它是苍蝇,那么我们可以得出它飞得很快的结论。包含有关鸟类的一些事实的背景理论如下:

根据这个默认规则,神鹰飞行是因为前提条件Bird(Condor)是真的,并且理由Flies(Condor)与当前已知的不一致。 相反,伯德(企鹅)不允许结束苍蝇(企鹅):即使默认鸟(企鹅)的前提条件是真的,理由苍蝇(企鹅)与已知的不一致。 从这个背景理论和这个默认值,Bird(Bee)无法得出结论,因为默认规则只允许从Bird(X)派生Flies(X),反之则不然。 从后果中推导出推理规则的前因是对后果的一种解释形式,也是诱导推理的目的。

一个常见的默认假设是,未知的事实被认为是错误的。 这被称为封闭世界假设,并且在缺省逻辑中使用类似于下面的缺省逻辑来形式化每个事实F.

例如,计算机语言Prolog在处理否定时使用了一种默认假设:如果负原子不能被证明是真的,则假定它是假的。 但请注意,Prolog使用所谓的否定作为失败:当解释器必须评估原子时  ,它试图证明F是真的,并得出结论  如果失败则为真。 相反,在缺省逻辑中,缺省逻辑具有  作为理由只能适用于  与目前的知识一致。

限制
如果默认值没有先决条件(或等效地,其先决条件是重复的),则默认为分类或无先决条件。 如果默认值具有与其结论等效的单个对齐,则默认值是正常的。 如果默认为分类和正常,则默认为超常。 如果所有的理由都需要得出结论,那么默认是初始化的。 如果默认理论包含的所有默认值分别为分类,正态,超常或者半自动,则默认理论​​称为分类,正态,超常或半正规。

缺省逻辑的语义
如果理论引入其前提条件并且其理由与理论一致,则可以将默认规则应用于理论。 默认规则的应用导致其理论的后果。 然后可以将其他默认规则应用于所得到的理论。 当理论不能应用其他默认理论时,该理论被称为默认理论的延伸。 默认规则可能以不同的顺序应用,这可能会导致不同的扩展。 尼克松钻石示例是一个默认理论,有两个扩展:

由于尼克松既是共和党人又是贵格会,因此可以应用两种默认值。 但是,应用第一个默认值会得出尼克松不是和平主义者的结论,这使得第二个默认值不适用。 以同样的方式,应用第二个默认值我们得到Nixon是和平主义者,因此使第一个默认值不适用。 因此,这个特定的默认理论有两个扩展,一个是Pacifist(Nixon)是真的,另一个是Pacifist(Nixon)是假的。

缺省逻辑的原始语义基于函数的固定点。 以下是等效的算法定义。 如果默认包含带有自由变量的公式,则认为它表示通过为所有这些变量赋值而获得的所有默认值的集合。 默认值  适用于命题理论T if  和所有理论  是一致的。 将此默认值应用于T导致了该理论  。 可以通过应用以下算法生成扩展:

T=W           /* current theory */
A=0           /* set of defaults applied so far */
 
              /* apply a sequence of defaults */
while there is a default d that is not in A and is applicable to T
  add the consequence of d to T
  add d to A
 
              /* final consistency check */
if 
  for every default d in A
    T is consistent with all justifications of d
then
  output T

该算法是非确定性的,因为可以替代地将若干默认值应用于给定的理论T.在Nixon菱形示例中,第一默认值的应用导致不能应用第二默认值的理论,反之亦然。 结果,产生了两个扩展:一个是尼克松是和平主义者,另一个是尼克松不是和平主义者。

对所有默认值的一致性进行的最终检查意味着某些理论没有任何扩展。 特别是,只要对每个可能的适用默认序列进行此检查失败,就会发生这种情况。 以下默认理论没有扩展名:

以来  与背景理论一致,可以应用默认值,从而得出结论  是假的。 然而,这个结果破坏了为应用第一个默认值而做出的假设。 因此,这个理论没有任何扩展。

在普通默认理论中,所有默认值都是正常的:每个默认值都有表格  。 普通默认理论保证至少有一个扩展。 此外,普通默认理论的扩展是相互矛盾的,即彼此不一致。

蕴涵
默认理论可以包含零个,一个或多个扩展。 默认理论中的公式包含可以通过两种方式定义:

怀疑的
一个公式是由默认理论引入的,如果它的所有扩展都包含它;

轻信
如果至少有一个扩展需要一个默认理论,那么公式就是一个公式。

因此,尼克松钻石示例理论有两个扩展,一个是尼克松是和平主义者,另一个是非和平主义者。 因此,无论是Pacifist(尼克松)还是¬Pacifist(Nixon)都是怀疑论者,而他们两人都被轻率地引入。如这个例子所示,默认理论的轻微后果可能彼此不一致。

替代默认推理规则
缺省逻辑的以下备选推断规则都基于与原始系统相同的语法。

正当
与原始的不同之处在于,如果因此集合T与所应用的默认的对齐不一致,则不应用默认值;

简洁
只有当T的结果不是T时才会应用默认值(确切的定义比这个更复杂;这只是它背后的主要思想);

约束
仅当由背景理论,所有应用的默认值的理由以及所有应用的默认值(包括此默认值)的后果组成的集合一致时,才应用默认值;

合理的
类似于约束缺省逻辑,但在一致性检查中不考虑默认添加的结果;

谨慎
不应用可以应用但相互冲突的默认值(如尼克松钻石示例中的默认值)。

推理规则的对齐和约束版本至少为每个默认理论分配了一个扩展。

缺省逻辑的变体
缺省逻辑的以下变体在语法和语义上与原始逻辑不同。

断言变种
断言是一对  由公式和一组公式组成。 这样的一对表示p是公式时的p  一直被认为是证明p是真的。 断言默认理论由称为背景理论的断言理论(一组断言公式)和原始语法中定义的一组默认值组成。 每当默认应用于断言理论时,由其结果和其理由组成的对被添加到理论中。 以下语义使用断言理论:

累积缺省逻辑
承诺假设缺省逻辑
准缺省逻辑

弱扩展
而不是检查前提条件是否在由背景理论和所应用的默认值的后果组成的理论中是有效的,而是检查前提条件在将要生成的扩展中的有效性; 换句话说,生成扩展的算法首先是猜测一个理论并用它来代替背景理论; 扩展生成过程的结果实际上只有在它与开头猜测的理论相当时才是一个扩展。 缺省逻辑的这种变体原则上与自动认知逻辑相关,其中一个理论  有一个模型,其中x是真的只是因为,假设  是的,公式  支持最初的假设。

析取缺省逻辑
默认的结果是一组公式而不是单个公式。 无论何时应用默认值,其后果中的至少一个都是不确定地选择并且为真。

违约的优先顺序
可以明确指定默认值的相对优先级; 在适用于理论的默认值中,只能应用一个最优选的默认值。 缺省逻辑的某些语义不需要明确指定优先级; 相反,更具体的默认值(适用于较少情况的默认值)优先于不太具体的默认值。

统计变量
统计默认值是默认值,其错误频率附加上限; 换句话说,默认值被假定为不正确的推理规则,最多只是应用它的一小部分。

翻译
默认理论可以转化为其他逻辑中的理论,反之亦然。 考虑了以下翻译条件:

后果保留
原始和翻译的理论具有相同的(命题)后果;

可信
这种情况仅在缺省逻辑的两个变体之间或缺省逻辑和逻辑之间进行转换时才有意义,其中存在类似于扩展的概念,例如模态逻辑中的模型; 如果在原始理论和翻译理论的扩展(或模型)之间存在映射(通常是双射),则翻译是忠实的;

模块化
如果默认值和背景理论可以单独翻译,则从缺省逻辑到另一个逻辑的转换是模块化的; 而且,在背景理论中增加公式只会导致在翻译结果中增加新的公式;

同一字母
原始和翻译的理论建立在同一个字母表中;

多项式
翻译的运行时间或生成的理论的大小需要是原始理论大小的多项式。

翻译通常需要忠实或至少保留后果,而模块化和相同字母的条件有时会被忽略。
已经研究了命题缺省逻辑与以下逻辑之间的可译性:

经典命题逻辑;
自我认知逻辑;
命题缺省逻辑仅限于半自动理论;
缺省逻辑的替代语义;
界限。

是否存在翻译取决于强加的条件。 除非多项式层次结构崩溃,否则从命题缺省逻辑到经典命题逻辑的翻译不能总是生成多项式大小的命题理论。 根据是否需要模块化或使用相同的字母表,存在或不存在对自动认知逻辑的翻译。

复杂
关于缺省逻辑的以下问题的计算复杂性是已知的:

存在扩展
决定命题默认理论是否至少有一个扩展是  -完成;

持怀疑态度
判断一个命题默认理论是否怀疑地含有一个命题公式  -完成;

信誉蕴涵
判断命题默认理论是否含有命题公式  -完成;

扩展检查
判断命题公式是否等同于命题默认理论的扩展是  -完成;

模型检查
决定命题解释是否是命题默认理论的延伸模型  -完成。

实现
实现缺省逻辑的三个系统是DeReS,XRay和GADeL