确定性推理

基本概念

推理方式

从推出结论的途径划分：演绎、归纳、默认

演绎

从全称判断推导出单称判断的过程，由一般知识推理细化出适合某一情况的结论。从一般到个别。

三段论式

大前提：足球运动员都很强壮

小前提：高波是一名足球运动员

结论：高波身体强壮

归纳

从足够多的事例中归纳出一般性结论的推理过程。从个别到一般。

完全归纳：考虑全部对象后得出结论。是必然性推理。

不完全归纳：抽检，未考虑全部对象。是非必然性推理。

默认（缺省推理）

在知识不完全时假设某些条件已具备。

例如设计鸟笼，不确定要关的鸟会不会飞，先默认会飞，推出鸟笼要加盖子的结论。

按推理时所用知识的确定性划分：确定性、不确定性推理

确定性推理

所用的知识和证据都确定，结论也确定。真值只有真假两种。

不确定推理

所用的知识和证据都不确定，结论也不确定。真值不只有真假两种。

现实世界中的事物和现象大都是不确定的，或者模糊的，很难用精确的数学模型来表示与处理。不确定性推理又分为似然推理与近似推理或模糊推理，前者是基于概率论的推理，后者是基于模糊逻辑的推理。人们经常在知识不完全、不精确的情况下进行推理，因此，要使计算机能模拟人类的思维活动，就必须使它具有不确定性推理的能力。

按推理过程中推出的结论是否越来越接近最终目标划分：单调、非单调推理

单调推理

单调推理是在推理过程中随着推理向前推进及新知识的加入，推出的结论越来越接近最终目标。单调推理的推理过程中不会出现反复的情况，即不会由于新知识的加入否定了前面推出的结论，从而使推理又退回到前面的某一步。

非单调推理

非单调推理是在推理过程中由于新知识的加入，不仅没有加强已推出的结论，反而要否定使推理退回到前面的某一步，然后重新开始。

非单调推理一般是在知识不完全的情况下发生的。由于知识不完全，为使推理进行下去，就要先作某些假设，并在假设的基础上进行推理。当以后由于新知识的加入发现原先的假设不正确时，就需要推翻该假设以及由此假设推出的所有结论，再用新知识重新进行推理。显然,默认推理是一种非单调推理。

在人们的日常生活及社会实践中，很多情况下进行的推理都是非单调推理。明斯基举了一个非单调推理的例子：当知道X是一只鸟时，一般认为X会飞，但之后又知道X是企鹅，而企鹅是不会飞的，则取消先前加入的X能飞的结论，而加入X是不会飞的结论。

按推理中是否运用与推理有关的启发性知识划分：启发式、非启发式推理

如果推理过程中运用与推理有关的启发性知识,则称为启发式推理,否则称为非启发式推理。

所谓启发性知识是指与问题有关且能加快推理过程、求得问题最优解的知识。例如，推理的目标是要在脑膜炎、肺

炎、流感这三种疾病中选择一个，又设有r1、r2、r3这三条产生式规则可供使用，其中r1推出的是脑膜炎，r2推出

的是肺炎，r3推出的是流感。如果希望尽早地排除脑膜炎这一危险疾病，应该先选用r1；如果本地区目前正在盛行

流感，则应考虑首先选择r3。这里，“脑膜炎危险”及“目前正在盛行流感”是与问题求解有关的启发性信息。

推理方向

正向推理

正向推理是以已知事实作为出发点的一种推理。

正向推理的基本思想：从用户提供的初始已知事实出发，在知识库KB中找出当前可适用的知识，构成可适用知识集KS，然后按某种冲突消解策略从KS中选出一条知识进行推理，并将推出的新事实加入到数据库中作为下一步推理的已知事实，此后再在知识库中选取可适用知识进行推理，如此重复这一过程，直到求得了问题的解或者知识库中再无可适用的知识为止。正向推理的推理过程可用如下算法描述:

①将用户提供的初始已知事实送入数据库DB。

②检查数据库DB是否已经包含了问题的解，若有，则求解结束,并成功退出；否则，执行下一步

③根据数据库DB中的已知事实，扫描知识库KB，检查KB中是否有可适用(即可与DB中已知事实匹配)的知识，若有，则转向④，否则转向⑥。

④把KB中所有的适用知识都选出来，构成可适用知识集KS。

⑤若KS不空，则按某种冲突消解策略从中选出一条知识进行推理，并将推出的新事实加入DB 中，然后转向②；若KS空，则转向⑥。

⑥询问用户是否可进一步补充新的事实，若可补充,则将补充的新事实加入DB中，然后转向③；否则表示求不出解，失败退出。

逆向推理

逆向推理是以某个假设目标作为出发点的一种推理。

逆向推理的基本思想是：首先选定一个假设目标，然后寻找支持该假设的证据，若所需的证据都能找到，则说明原假设是成立的；若无论如何都找不到所需要的证据，则说明原假设是不成立的，为此需要另作新的假设。

逆向推理过程可用如下算法描述：

①提出要求证的目标(假设)。

②检查该目标是否已在数据库中，若在，则该目标成立，退出推理或者对下一个假设目标进行验证；否则，转下一步。

③判断该目标是否是证据，即它是否为应由用户证实的原始事实，若是，则询问用户；否贝转下一步。

④在知识库中找出所有能导出该目标的知识，形成适用的知识集KS，然后转下一步。

⑤从KS中选出一条知识，并将该知识的运用条件作为新的假设目标，然后转向②。

不必使用与目标无关的知识，目的性强。但起始目标只能盲目选择，如果不符合实际就要多次假设影响效率。

混合推理

以下情况需要用：

已知事实不充分、正向推出的结论可信度不高、希望得到更多结论。

先正后逆和先逆后正：

双向推理

一方面根据已知事实正向推理但不推到最终目标；另一方面从某假设出发逆向推理，但也不推至原事实，他俩在中途相遇得到中间结论。

冲突消解策略

推理过程中系统需要不断拿已知知识和知识库的知识做匹配。

三种情况

①已知事实只可以匹配知识库中的一个知识；

②已知事实不能匹配任何知识；

③已知事实可以匹配知识库中多个知识、或多个事实匹配一个知识、或多个事实匹配多个知识。

对于①，直接把这个知识用于推理。

对于②，推理无法继续。

对于③，称为发生冲突。需要按一定策略从多个知识中挑一个用于推理。

四种冲突消解策略

按规则的针对性排序

前件中条件详细(多)的规则先推。

按已知事实的新鲜性排序

新鲜事实(刚得到的局部结论)越多(越新鲜)的规则先推。

按匹配度排序

在不确定性匹配中，计算两个知识模式的相似度(匹配度)，并对其排序，相似度高的规则先推。

按条件个数排序

条件少的规则先推。

自然演绎推理

从一组已知为真的事实出发，直接运用经典逻辑的推理规则推出结论的过程，称为自然演绎推理。

假言推理

$$P,P\to Q\Rightarrow Q$$

拒取式推理

$$P\to Q,\mathrm{\neg }Q\Rightarrow \mathrm{\neg }P$$

归结演绎原理

定理证明即证明$P\to Q(\mathrm{\neg }P\vee Q)$的永真性。根据反证法，只要证明其反面$(P\wedge \mathrm{\neg }Q)$​的不可满足性即可。

子句

在谓词逻辑中，把原子谓词公式及其否定统称为文字。任何文字的析取式称为子句。

子句：$P(x)\vee Q(x),\mathrm{\neg }P(x,f(x))\vee Q(x,g(x))$.

不包含任何文字的子句称为空子句，永假。

任何谓词公式都可通过等价关系及推理规则化成相应的子句集。

谓词公式化为子句集

例：

$$(\mathrm{\forall }x)((\mathrm{\forall }y)P(x,y)\to (\mathrm{\forall }y)(Q(x,y)\to R(x,y)))$$

1、消去蕴涵（$P\to Q\iff \mathrm{\neg }P\vee Q$​）

$$\begin{array}{c}\Rightarrow (\mathrm{\forall }x)((\mathrm{\forall }y)P(x,y)\to (\mathrm{\forall }y)(\mathrm{\neg }Q(x,y)\vee R(x,y)))\\ \Rightarrow (\mathrm{\forall }x)(\mathrm{\neg }(\mathrm{\forall }y)P(x,y)\vee \mathrm{\neg }(\mathrm{\forall }y)(\mathrm{\neg }Q(x,y)\vee R(x,y)))\end{array}$$

2、利用等价关系把$\mathrm{\neg }$​移到紧靠谓词的位置上

$$\begin{array}{c}(\mathrm{\forall }x)((\mathrm{\exists }y)\mathrm{\neg }P(x,y)\vee (\mathrm{\exists }y)\mathrm{\neg }(\mathrm{\neg }Q(x,y)\vee R(x,y)))\\ (\mathrm{\forall }x)((\mathrm{\exists }y)\mathrm{\neg }P(x,y)\vee (\mathrm{\exists }y)(Q(x,y)\wedge \mathrm{\neg }R(x,y)))\end{array}$$

3、利用换名规则换名

$$(\mathrm{\forall }x)((\mathrm{\exists }y)\mathrm{\neg }P(x,y)\vee (\mathrm{\exists }z)(Q(x,z)\wedge \mathrm{\neg }R(x,z)))$$

4、消去存在量词

若存在量词不出现在全称量词的辖域内，则只要用一个新的个体常量替换受该量词约束的变元。

若在全称量词辖域：利用Skolem函数替换：即用一个以全程量词变元为自变量的函数换掉存在量词变元：

$$(\mathrm{\forall }x)((\mathrm{\exists }y)\mathrm{\neg }P(x,y)\vee (\mathrm{\exists }z)(Q(x,z)\wedge \mathrm{\neg }R(x,z)))$$

在这里，后边都在$x$的辖域内，所以Skolem函数的自变量都是x。分别用$f(x)$, $g(x)$ 替换$y$和$z$这两个变元：

$$(\mathrm{\forall }x)(\mathrm{\neg }P(x,f(x))\vee (Q(x,g(x))\wedge \mathrm{\neg }R(x,g(x))))$$

5、化前束范式

把所有全称量词移到公式的左边，并使每个全称量词的辖域包括这个量词后面公式的整个部分。其实上边的已经是前束范式了：

$$(\mathrm{\forall }x)(\mathrm{\neg }P(x,f(x))\vee (Q(x,g(x))\wedge \mathrm{\neg }R(x,g(x))))$$

6、化合取范式（用合取符号连接一堆析取式）

等价关系：

$$P\vee (Q\wedge R)⟺(P\vee Q)\wedge (P\vee R)$$$$(\mathrm{\forall }x)((\mathrm{\neg }P(x,f(x))\vee Q(x,g(x)))\wedge (\mathrm{\neg }P(x,f(x))\vee \mathrm{\neg }R(x,g(x))))$$

7、消去全称量词

到了这一步，所有余下的量词均被全称量词量化了。同时全称量词的次序也不重要了。因此，我们可以消去全称量词：

$$(\mathrm{\neg }P(x,f(x))\vee Q(x,g(x)))\wedge (\mathrm{\neg }P(x,f(x))\vee \mathrm{\neg }R(x,g(x)))$$

8、获取子句集

子句集就是合取范式的各个部分组成的集合：

$$\{(\mathrm{\neg }P(x,f(x))\vee Q(x,g(x))),(\mathrm{\neg }P(x,f(x))\vee \mathrm{\neg }R(x,g(x)))\}$$

子句的性质

子句集S的不可满足性：对于任意论域中的任意一个解释，S中的子句不能同时取得真值T。

定理 设有谓词公式F，其子句集为S，则F不可满足的充要条件是S不可满足。

因为子句是从合取范式来的，只要一个子句永假，整个谓词公式就永假。

消解推理

设$L1$为任一原子公式，$L2$为另一原子公式，且具有相同的谓词名，但一般具有不同的变量。已知两子句$L1\vee \alpha$和$\neg L2\vee \beta$，如果$L1$和$L2$具有最一般合一$\sigma$，那么通过消解可以从这两个子句推导出一个新子句$\alpha \sigma \vee \beta \sigma$。这个新子句叫做消解式（归结式）。

例：

$$C_1=P(x)\vee Q(x),C_2=\mathrm{\neg }P(a)\vee R(y)$$

最一般合一（求法见上一篇）：

$$\begin{array}{c}\sigma =\{a/x\}\\ C_1\sigma =P(a)\vee Q(a)\\ C_2\sigma =\mathrm{\neg }P(a)\vee R(y)\end{array}$$

归结式：

$$\begin{array}{c}{C}_1\sigma \vee C_2\sigma \\ \iff P(a)\vee Q(a)\vee \mathrm{\neg }P(a)\vee R(y)\\ \iff 1\vee Q(a)\vee R(y)\\ \iff Q(a)\vee R(y)\end{array}$$

若某个子句$C$含有可合一的文字，则在进行归结之前应先对这些文字进行合一：

$$C_1=P(x)\vee P(f(a))\vee Q(x),C_2=\mathrm{\neg }P(x)\vee R(b)$$$$\begin{array}{c}\sigma =\{f(a)/x\}\\ C_1\sigma =P(f(a))\vee Q(f(a))\\ C_2\sigma =\mathrm{\neg }P(f(a))\vee R(b)\\ C_{12}=Q(f(a))\vee R(b)\end{array}$$

定理 若$C_{12}$是子句$C_1$与$C_2$的消解式，则$C_{12}$是$C_1$与$C_2$的逻辑结论。

推论 设 $C_1$ 与 $C_2$ 是子句集 $S$ 中的两个子句，$C_{12}$ 是它们的消解式。若用 $C_{12}$ 代替$C_1$和$C_2$加入 $S$ 中得到新子句集 $S_1$，则 $S$ 与 $S_1$ 在不可满足的意义上是等价的，即$S_1$不可满足 $\Rightarrow$ $S$不可满足。

如果一个东西的逻辑结论为假，那它本身也假。

但是$S$不可满足不能推$S_1$不可满足，因为只要有一个子句为假，整个子句集就为假，假的子句不一定就是$S_1$。

推论 设 $C_1$ 与 $C_2$ 是子句集 $S$ 中的两个子句，$C_{12}$ 是它们的消解式。若把 $C_{12}$ 加入 $S$ 中得到新子句集 $S_2$，则 $S$ 与 $S_2$ 在不可满足的意义上是等价的，即$S_2$不可满足 $\iff$ $S$​不可满足。

$S_2$就比$S$多了一个由它自己产生的逻辑结论，如果$S_2$为假，那就说明$S$​里有错误结论，假。

$S$的不可满足性不会因为$C_{12}$​的加入而改变。

消解反演求解

用已知公式集$F=\{P_1,P_2,...,P_n\}$证明$Q$：

得到如下公式集：

$$\{F,\mathrm{\neg }Q\}$$

化为子句集

$$(P_1\wedge P_2\wedge ...\wedge P_n)\wedge \mathrm{\neg }Q$$

应用归结原理对子句集S中的子句进行归结，并把每次归结得到的归结式都并入S中。如此反复进行，若出现了空子句，则停止归结，此时就证明了Q为真。

例：

$$F:(\mathrm{\forall }x)((\mathrm{\exists }y)(A(x,y)\wedge B(y))\to (\mathrm{\exists }y)(C(y)\wedge D(x,y)))$$$$G:\mathrm{\neg }(\mathrm{\exists }x)C(x)\to (\mathrm{\forall }x)(\mathrm{\forall }y)(A(x,y)\to \mathrm{\neg }B(y))$$

求证：$G$ 是 $F$ 的逻辑结论。

证明：首先把 $F$ 和 $\mathrm{\neg }G$ 化为子句集：

$$F=\{\mathrm{\neg }A(x,y)\vee \mathrm{\neg }B(y)\vee C(f(x)),\mathrm{\neg }A(x,y)\vee \mathrm{\neg }B(y)\vee D(x,f(x))\}$$$$\mathrm{\neg }G=\{\mathrm{\neg }C(z),A(a,b),B(b)\}$$

归结：

$\mathrm{\neg }A(x,y)\vee \mathrm{\neg }B(y)\vee C(f(x))$ 和 $\mathrm{\neg }C(z)$ 有合一：$\{f(x)/z\}$

归结得到：

$$\mathrm{\neg }A(x,y)\vee \mathrm{\neg }B(y)$$

$A(a,b)$ 和 $\mathrm{\neg }A(x,y)\vee \mathrm{\neg }B(y)$ 有合一：$\{a/x,b/y\}$

归结得到：

$$\mathrm{\neg }B(b)$$

$\mathrm{\neg }B(b)$ 和 $B(b)$ 归结得到：

$$NIL$$

出现空子句，停止归结，证毕。

现实例子

设 $A,B,C$ 三人中有人从不说真话，也有人从不说假话。现在向这三人提出同一个问题：谁是说谎者？ A答：“$B$ 和 $C$ 都是说谎者”；B答：“$A$ 和 $C$ 都是说谎者”；C答：“$A$ 和 $B$ 中至少有一个是说谎者”。 请证明 $A$ 不是老实人。

用 $T(x)$ 表示 $x$ 说真话。则已知前提为：

$$\begin{array}{c}T(C)\vee T(A)\vee T(B)\\ \mathrm{\neg }T(C)\vee \mathrm{\neg }T(A)\vee \mathrm{\neg }T(B)\end{array}$$

三个人有真有假

$$\begin{array}{c}T(A)\to \mathrm{\neg }T(B)\wedge \mathrm{\neg }T(C)\\ \mathrm{\neg }T(A)\to T(B)\vee T(C)\\ T(B)\to T(A)\wedge \mathrm{\neg }T(C)\\ \mathrm{\neg }T(B)\to T(A)\vee T(C)\\ T(C)\to \mathrm{\neg }T(A)\vee \mathrm{\neg }T(B)\\ \mathrm{\neg }T(C)\to T(A)\wedge T(B)\end{array}$$

如果一个为真，另外俩一定至少有个假的；一个为假，另外俩一定至少有个真的。

以上推出的子句集：

$$\begin{array}{c}(1)\neg T(A)\vee \neg T(B)\\ (2)\neg T(A)\vee \neg T(C)\\ (3)T(C)\vee T(A)\vee T(B)\\ (4)\neg T(B)\vee \neg T(C)\\ (5)\neg T(C)\vee \neg T(A)\vee \neg T(B)\\ (6)T(A)\vee T(C)\\ (7)T(B)\vee T(C)\end{array}$$

要证明 $A$ 不是老实人，即要证$\mathrm{\neg }T(A)$。把$\mathrm{\neg }(\mathrm{\neg }T(A))$加入子句集，开始归结：

（1）和（7）得到

$$(9)\mathrm{\neg }T(A)\vee T(C)$$

（2）和（9）得到

$$(10)\mathrm{\neg }T(A)$$

（8）和（10）得到

$$NIL$$

证毕，$A$和$B$都不老实。

在消解反演中，并不一定要用到全部的子句，只要能得到NIL他就是对的。

自动定理证明——Herbrand定理

机器定理证明——Robinson归结原理