人工智能导论-第3章-知识点与学习笔记

1. 参考教材3.2节的内容，介绍什么是自然演绎推理；解释“肯定后件”与“否定前件”两类错误的演绎推理是什么意义，给出具体例子加以阐述。
2. 参考教材3.3节的内容，介绍什么是文字（literal）；介绍什么是子句集。
3. 参考教材3.3节的内容，详细阐述谓词公式化为子句集的方法和步骤。需要给出具体的例子加以详细的说明。（电子版文档中，谓词公式必须是Word文档插入的可编辑的公式，直接截图的作业报告，需要重新提交）
4. 参考教材3.4节的内容，名词解释“消解原理”及其意义。
5. 参考教材3.4节的内容，从谓词公式转化为子句集的角度，阐述你对鲁宾孙归结原理的理解。
6. 认真学习教材第72页3.4节的定义3.1，谈谈你对定义3.1的理解，该定义中提及的“文字”及文字互补具体是指代什么含义。
7. 认真学习教材第76页3.5节的内容，从归结原理、子句集不可满足性的角度，谈谈你对归结反演的理解。
8. 参考教材32页的定义2.5，介绍什么是谓词公式不可满足性。再参考定义2.5，谈谈你对定理3.1的理解（教材第72页）。
9. 参考教材33页的定义2.7，介绍什么是谓词公式永真蕴含。再参考定义2.7，谈谈你对定理3.2的理解（教材第73页）。
10. 应用归结原理求解下面的问题

（1）已知如下信息如下：

         F1：王(Wang)先生是小李(Li)的老师。

           F2:   小李与小张(Zhang)是同班同学。

           F3:   如果x与y是同班同学，则，x的老师也是y的老师。

           求小张的老师是谁？

(2)  设TONY、MIKE和JOHN属于ALPINE俱乐部，ALPINE俱乐部的成员不是滑雪运动员就是登山运动员。登山运动员不喜欢雨，而且任何不喜欢雪的人不是滑雪运动员。MIKE讨厌TONY所喜欢的一切东西，而喜欢TONY所讨厌的一切东西。TONY喜欢雨和雪。试用谓词公式的集合表示这段知识，用归结原理回答问题：“谁是ALPINE俱乐部的一个成员？他是一个登山运动员但不是一个滑雪运动员。”

解答：

自然演绎推理是从已知为真的事实出发，直接运用经典逻辑的推理规则来推导出结论的过程。这种推理过程遵循逻辑规则，包括P规则、T规则、假言推理、拒取式推理等。其中，假言推理的一般形式为P、P→Q⇒Q，表示当条件P成立且条件P蕴含条件Q时，可以推出结论Q为真。而拒取式推理的一般形式是，当条件P蕴含条件Q为真且结论Q为假时，可以推出条件P为假。

肯定后件和否定前件。肯定后件是指，当已知条件P→Q为真时，试图通过观察到后件Q为真来推断前件P为真，这种推理是不正确的。否定前件是指，当已知条件P→Q为真时，试图通过观察到前件P为假来推断后件Q为假，这种推理也是不正确的。

举例

如果今天下雨，那么地面会湿润。

今天地面是湿润的（肯定后件）。

所以，今天下雨了。

这种推理是不正确的，因为地面湿润可能是由于其他原因，比如使用水管浇水，而不一定是因为下雨。

另一个例子是：

如果今天下雨，那么地面会湿润。

今天没有下雨（否定前件）。

所以，今天地面不会湿润。

这个推理也是错误的，因为即使没有下雨，也可能有其他原因导致地面湿润，比如有人洒水

文字：在谓词逻辑中，原子谓词公式及其否定称为文字。一个文字是一个不能再分解的命题，它可以是一个原子谓词，也可以是一个原子谓词的否定。比如，如果我们有一个原子谓词P，那么P和¬P（P的否定）都是文字，其中P称为正文字，¬P称为负文字。正文字和负文字互为补充，因为它们是同一个原子谓词的肯定和否定。

子句集：在谓词逻辑中，由文字构成的析取式称为子句。而由多个子句构成的集合称为子句集。子句集可以包含单个子句，也可以包含多个子句。空子句是一种特殊的子句，它不包含任何文字，表示为NIL。空子句是永假的、不可满足的，因为它不包含任何文字，无法被满足。子句集的目的是用来描述问题或命题中的多个条件，通过对子句集的处理和推理，可以得到对问题的解答或结论。

步骤一：消去蕴含符号和等价符号

首先，我们需要消去谓词公式中的蕴含符号和等价符号，将其转化为否定和合取的形式，以便后续的处理。利用等价关系将蕴含符号和等价符号转化为合适的形式。

步骤二：移动否定符号

接下来，将否定符号移动到紧靠谓词的位置上，以减少否定符号的辖域，利用德摩根律等关系将否定符号移动到合适的位置。

步骤三：变量标准化

进行变量标准化，重新命名变元，使每个量词采用不同的变元，从而确保不同量词的约束变元有不同的名字。这样做是为了避免命名冲突和混淆，确保逻辑推理的准确性。

步骤四：消去存在量词

分两种情况进行处理：一种是存在量词不出现在全称量词的辖域内，另一种是存在量词出现在全称量词的辖域内。针对不同情况，采取不同的方式消去存在量词，通常使用Skolem函数进行替换。

步骤五：化为前束形

将所有的全称量词移到公式的前面，使每个量词的辖域都包括公式后的整个部分，从而形成前束形式。

步骤六：化为Skolem标准形

利用合取和析取的性质，将谓词公式化为Skolem标准形，即将其转化为一组子句的合取式形式。

步骤七：略去全称量词

由于所有的变量都是全称量词量化的变量，因此可以省略全称量词，子句中的变量仍然认为是全称量词量化的变量。

步骤八：子句变量标准化，即使每个子句中的变量的符号不同

例：

(∀x)|P(x)→|(∀y)[P(y)→ P(f(x, y))]∧¬ (∀y[Q(x,y)+ P(y)]

(1)消去蕴涵符号

(∀x){¬ P(x) V |( ∀y)[¬ P(y) V Pf(x,y))] ∧ ¬(∀y)[¬ Q(x,y) V P(y)]}

(2)把否定符号移到每个谓词前面

(∀x){¬P(x) V {( ∀y)[¬P(y) V P(f(x,y))]∧(∃y){¬[¬Q(x,y) VP(y)]}}}

(∀x)|¬ P(*) V {( ∀y)[¬ P(y)V P(f(x,y))] ∧(∃y)[Q(x,y)∧¬ P(y)]}}

(3)变量标准化

(∀x){¬P(x) V{(∀y)[¬P(y)VP(f(x,y))] ∧(∃w)[Q(x,w)∧P(w)]}

(4)消去存在量词

设 w的 Skolem 函数是 g(x),则

(∀x){¬P(x) V [(∀y)[¬P(y) V P((x,y))]^[Q(x,g(x)) ∧¬P(g(x))]]}

消解原理又称为归结原理，是由逻辑学家鲁宾孙在1965年提出的一种证明子句集不可满足性的理论及方法。这个原理是机器定理证明的基础之一，在人工智能、自动推理等领域有广泛的应用。

转化为子句集：首先，将给定的谓词逻辑公式转化为子句集。这个转化过程中，需要将逻辑连接词转化为子句间的关系，通常是合取关系。这样，一个谓词逻辑公式就可以表示为多个子句的集合。

子句集的不可满足性判定：为了判断子句集的不可满足性，需要对子句集中的每个子句进行判定。如果存在一个子句是不可满足的，那么整个子句集也是不可满足的。这是因为在合取关系下，只要有一个子句是假的，整个合取式就为假。

归结过程：如果子句集中不包含空子句，就需要应用归结规则来尝试导出空子句。归结规则的基本形式是对两个子句进行归结，如果其中一个子句包含一个文字，而另一个子句包含该文字的否定，则可以通过消解得到一个新的子句。这个新的子句可以被添加到子句集中，然后再次检查是否存在空子句。重复这个过程直到得到一个空子句或者无法再应用归结规则为止。

x判断结果：如果得到了一个空子句，就说明原始的子句集是不可满足的。这是因为如果子句集是可满足的，那么根据归结规则的应用，就不可能导出一个空子句。如果无法得到空子句，则说明原始子句集是可满足的。

在命题逻辑中，"文字"是指命题变量或其否定形式。具体来说，如果一个文字是一个命题变量或者其否定形式，那么它就是一个文字。例如，在命题逻辑中，如果P是一个命题变量，则P和¬P都是文字。

而"文字互补"指的是两个文字之间的关系，其中一个文字是另一个文字的否定形式。在命题逻辑中，如果有两个文字，一个是某个命题变量，另一个是该变量的否定形式，则它们被称为互补文字。例如，如果有两个文字分别是P和¬P，那么它们就是互补文字，因为P是¬P的否定形式，反之亦然。

在归结原理中，利用互补文字的性质，可以通过消解（归结）两个含有互补文字的子句来得到新的子句，从而进行推理和证明过程。

归结反演是一种利用归结原理证明定理的过程。它通过将已知前提和待证结论转化为谓词公式，然后将其转化为子句集，并应用归结原理进行归结操作，直到出现空子句或无法再进行归结为止。如果最终得到了空子句，那么就证明了待证结论是真的。

从归结原理和子句集不可满足性的角度来看，归结反演的理解可以总结如下：

转化为子句集: 首先，将已知前提和待证结论分别表示为谓词公式，并将其转化为子句集。这样做的目的是为了能够应用归结原理，因为归结原理是针对子句集的。

归结操作: 对于子句集中的子句，不断地应用归结原理进行归结操作。归结操作的目标是尝试消解含有互补文字的子句，从而得到新的子句，并将其加入到子句集中。这个过程会一直进行下去，直到出现空子句（表示矛盾）或者无法再进行归结为止。

判断结果: 如果最终得到了空子句，则说明待证结论是真的，因为在命题逻辑中，如果可以从已知前提中推导出矛盾，那么待证结论就是真的。如果无法得到空子句，则说明无法证明待证结论。

谓词公式P的不可满足性指的是不存在任何解释，使得公式P在该解释下的真值为真。换句话说，当无论如何选择谓词公式P中的各个谓词及其参数的赋值，都无法使得整个公式为真时，该谓词公式就是不可满足的。

以谓词逻辑为例，谓词公式通常包含谓词、变量和量词，并且有关系符号和逻辑连接词连接起来。不可满足性意味着无法找到一组解释（变量的赋值），使得公式中的每个子句都可以为真。这表示公式中的子句之间存在矛盾，或者说无法满足所有的限制条件。

选择互补文字的子句: 在子句集中选择两个子句，这两个子句中分别包含相互否定的文字（互补文字）。

应用归结原理: 对于选定的两个子句，从中消去互补文字，然后将剩余部分合取（取并集），形成一个新的子句，称为归结式。

验证结果: 如果得到的归结式是空子句（NIL），即不包含任何文字，那么表示这两个原始子句之间存在矛盾。如果未能得到空子句，则表明归结未成功，可能需要尝试其他的归结。

对于谓词公式p与q，若p->q永真，则称p永真蕴含q，记作P=>Q，且称p为q的逻辑结论，p为q的前提。C1与C2为真，则C12为真。

（1）

（2）

成员(x)：x是ALPINE俱乐部的一个成员。

登山运动员(x)：x是一个登山运动员。

滑雪运动员(x)：x是一个滑雪运动员。

喜欢(x, y)：x喜欢y。

讨厌(x, y)：x讨厌y。

雨(y)：y是雨。

雪(y)：y是雪。

推理：

1成员(TONY)。

2成员(MIKE)。

3成员(JOHN)。

4登山运动员(TONY)。

5登山运动员(MIKE)。

6登山运动员(JOHN)。

7非滑雪运动员(TONY)。

8非滑雪运动员(MIKE)。

9非滑雪运动员(JOHN)。

10雨和雪(TONY)。

11不喜欢(TONY, MIKE)。

12喜欢(MIKE, TONY)。

假设一个人x，是ALPINE俱乐部的一个成员，是一个登山运动员但不是一个滑雪运动员。

可得出

成员(x)。

登山运动员(x)。

非滑雪运动员(x)。

归结步骤如下：

归结1和3，得到非滑雪运动员(x)。

归结2和非滑雪运动员(x)，得到矛盾。