4.5.1缺省推理

4.5 非单调推理


建立在谓词逻辑基础上的传统系统是单调的，其意思是：已知为真的命题数目随时间而严格增加。那是由于新的命题可加入系统，新的定理可被证明，但这种加入和被证明决不会导致前面已知为真或已被证明的命题变成无效。这种系统具有以下优点：
(1) 当加入一新命题时，不必检查新命题与原有知识间的不相容性。
(2) 对每一个已被证明了的命题，不必保留一个命题表。它的证明以该命题表中的命题为根据，因为不存在那些命题会被取消的危险。
可是，这种单调系统不能很好地处理常常出现在现实问题领域中的3类情况，即不完全的信息、不断变化的情况、以及求解复杂问题过程中生成的假设。

4.5.1 缺省推理

很少有能在处理过程中拥有它所需要的一切信息的系统。但当缺乏信息时，只要不出现相反的证据，就可以作一些有益的猜想。构造这种猜想称为缺省推理(default reasoning)。例如，假设当你去朋友家吃晚饭，并经过路旁的卖花亭时，对于“你的主人喜欢花吗?”这样一个问题，你可能没有任何具体信息可作为回答问题的依据。但若利用一般的规则——因为大多数人们喜欢花，假定这个具体的人也喜欢，除非有相反的证据(如对花过敏)，那么，你可作出决定。这类缺省推理是非单调的(即加进一条信息就可能迫使取消另一条信息)，因为用这种方式推导出来的命题是依赖于在某个命题中缺少某种信念，即如果前面那些缺省的命题一旦加入系统，就必须消除用缺省推理产生的命题。这样一来，如果你拿着花走到门口时，你的主人立刻打喷嚏，你就应取消以前的信念——你的主人喜欢花。当然，你也必须取消建立在已被取消的信念基础上的任何信念。
上述举例说明了一个普通类型的缺省推理，称为最可能选择。如果知道一些事情中的某件事必为真，在缺乏完全知识条件下，应选最可能的那个。如：大多数人喜欢花；大多数狗有尾巴；对瑞典人而言，最一般的头发颜色为淡黄色。另一重要类型的缺省推理是约束推理(circumscription)在这种推理中只有当能证明某些对象满足性质P时，才认为它们满足性质P。例如，设需求解的问题是划船过河，可能列举许多妨碍成功过河的因素，如没有船桨，船漏水，船搁浅在泥沙中等等。而重要的是，问题求解程序不必去证明这些条件不是真的(因为可能问题本身的说明根本没提到船桨)。程序能作的是，假定只有那些能够清楚地被证明为真的事情才是真的(希望没一个为真)，否则不为真。那时，程序才能往前进行并假定能使用船。
一个既精确又可算的缺省推理的描述，必涉及结论Y且缺少某一信息X。所以缺省推理的定义为：
缺省推理的定义1：如果X不知道，那么得结论Y。
但在所有的系统中，除最简单的系统外，只有存贮在数据库中的事件的极小部分可看成是已知的。不过，通过各种努力，事件的其余部分可从已知部分推导出来。所以缺省推理的定义更像是：
缺省推理的定义2：如果X不能被证明，那么得结论Y。
但是，如果仍然以谓词逻辑工作，那怎么能知道X不能被证明?由于这系统是不可判定的，所以对任一X来说，仍不能担保它能否被证明。于是我们不得不重新考虑定义：
缺省推理的定义3：如果X不能在某个给定的时间内被证明，那么得结论Y。
值得注意，定义推出结论Y的推理过程依赖于逻辑领域外的某些事件，在规定时间内可作多少计算，以及在寻找待求的证明中计算是否有效。因此作出关于系统行为的形式说明就显得特别重要。加之，我们丧失了谓词逻辑所具有的对所提出的证明的正确性进行验证的能力，即使一个证明存在，也不一定能保证找到它。假如现在得到一证明，对证明过程中的某一步来说，由于没有能力证明X，所以得结论Y。但由于X是否可被证明是不可判定的，因而包含这个证明在内的更大的证明也就不可判定。于是，由于缺乏完全的知识，对缺省推理的需要迫使我们使用这样的系统，它的行为不易形式地描述出来。
即使有幸获得了关于某一情况的完全知识，也不能由此而长时间使用它，因为客观世界在迅速地变化着。这意味着在一个时刻完全精确的说明不会是持久的。这就是框架问题，一种引入状态变量对它进行处理的方法，已在第2.5节介绍过。但这种方法不很完善，因为只要状态中各谓词为真，它就要对每个状态作单独的描述。于是得花很多精力来重复地说明一个缓慢变化的事实。而且，凡每一操作执行后，就得引进一新状态，因此很难发现若干个操作序列已导致同一情况。另一种求解不断变化的世界问题的方法，是取消那些不能再精确描述世界的命题，而代之以另一些更精确的命题。这又使其变成了非单调系统。在这类系统中，命题既可从知识库中删去，也可加入。而且当一个命题被取消后，其证明依赖于这个被取消命题的其它命题也应取消。
即使供某一系统采用的知识不存在上述两个问题，一个好的问题求解系统在问题求解过程中，也可能产生某些非单调行为的知识。假若要编一程序来求解一个极简单的问题，例如找一适当时间使3个忙人能同时参加会议。一个办法是首先假设会议在某个具体日期举行，比如星期三，并将关于此假设的命题放入数据库中，再从3个人的时间安排表中检查不相容性。如果出现冲突，就表示假设的命题必须取消，而代之以另一个希望不矛盾的命题。当然，任何依赖于这个被取消命题而建立起来的命题也必须取消。于是又得到一个非单调系统。
当然，这种情况可用带回溯的直接树搜索来处理。一切假设和由假设得出的推论，均记录在产生它们的搜索树的结点上。当产生一个不相容时，只需回溯到尚未探索过的路径的一个结点上。这时原假设和它们的推论将自动消失。这种回溯方法如图4.22所示。

它显示出一个安排会议程序的搜索树的一部分。为此，程序必须求解一个约束满足问题，即找出每个参加者都有空闲的开会日期与时刻，并有可供开会的房间。
求解该问题时，系统必须试图在一个时刻满足一个约束。最初，几乎没有根据可以肯定哪个时间最好，所以随意确定为星期三。于是产生一个新的约束，解的其余部分必须满足会议在星期三举行的假设，且存放在所产生的结点上。接着，程序试图选择一个时刻，使之适合于所有参加者。在他们的工作时间表中，通常白天的会议时刻可能在除14∶00外的任意时刻，所以选择14∶00作为开会时间，至于在哪一天倒没关系。然而，程序发现在星期三无房间可供开会使用。所以它回溯穿过结点(假设星期三的结点)，并改在另一天，比如星期二。现在就必须复制导出时刻为14∶00的推理链，因为它回溯到选日期时，原推理链已经消失，尽管该时刻推理未依靠任何关于日期为星期三的假设。
如果按照搜索过程产生命题的次序去取消命题，而不是按照该命题内涵的不相容性去取消命题，那么将会产生很大的浪费。最好是在需要时既能直接将假设插入到数据库，又能取消它们。这种方式称为面向从属关系的回溯。
基于下述一些原因中的任何一个，都可察觉非单调推理系统的必要性：
(1) 不完全知识的出现要求缺省推理。
(2) 一个不断变化的世界必须用适应不断变化的数据库来描述。
(3) 产生一个问题的完全解可能要求关于部分解的暂时的假设。