推理 训练 人工智能_人工智能常用算法

一.命题逻辑基础——基本等值式

①交换率
p∨q <=> q∨p
p∧q <=> q ∧p
②结合率
(p∨q)∨r<=> p∨(q∨r)
(p ∧q)∧r<=> p ∧(q∧r)
③分配率
p∨(q∧r)<=>(p∨q)∧(p∨r)
p∧(q∨r)<=>(p∧q)∨(p∧r)
④摩根率
～ (p∨q) <=> ～ p ∧～ q
～ (p∧q) <=> ～ p ∨ ～ q
⑤吸收率
p∨(p∧q ) <=>p
p∧(p∨q )<=>p
⑥同一律
p∨0 <=> p
p∧1 <=> p
⑦蕴含等值式
p→q<=>～p∨q
⑧假言易位式
p→q<=>～p→～q

二.消解原理

1.消解推理技术
已知两子句L1∨α和～L2∨β ，如果L1和L2具有最一般合一者σ，那么通过消解可以从这两个父辈子句推导出一个新子句(α∨β) σ。
这个新子句叫做消解式，它是由取这两个子句的折取，然后消去互补对而得到的。

2.消解推理常用规则

3.消解反演
(1)否定L，得～L；
(2)把～L添加到S中去；
(3)把新产生的集合｛～L，S｝化成子句集；
(4)应用消解原理，力图推导出一个表示矛盾的空子句NIL。

例题：快乐学生问题

假设：任何通过计算机考试并获奖的人都是快乐的，任何肯学习或幸运的人都可以通过所有考试，张不肯学习但他是幸运的，任何幸运的人都能获奖。求证：张是快乐的。

解：先将问题用谓词表示如下：
“任何通过计算机考试并获奖的人都是快乐的”
(∀x) (Pass(x，computer)∧Win(x，prize)) →Happy(x)
“任何肯学习或幸运的人都可以通过所有考试”
(∀x) (∀y) (Study(x)∨Lucky(x)→Pass(x，y)
“张不肯学习但他是幸运的”
～Study(zhang)∧ Lucky(zhang)
“任何幸运的人都能获奖”
（∀x）(Lucky(x) → Win(x，prize)
结论“张是快乐的”的否定
～Happy(zhang)

将上述谓词公式转化为子句集如下：
（1）～Pass（x， computer）∨～Win（x，prize）∨Happy（x）
（2）～Study（y）∨ Pass（y，z）
（3）～Lucky（u）∨ Pass（u，v）
（4）～Study（zhang）
（5）Lucky（zhang）
（6）～Lucky（w）∨ Win（w， prize）
（7）～Happy（zhang）（本子句为结论的否定）

按谓词逻辑的归结原理对此子句集进行归结，其归结反演过程如图所示。由于归结出了空子句，这就证明了张是快乐的。

例题：激动人心的生活
例 “激动人心的生活”问题。
假设：所有不贫穷并且聪明的人都是快乐的。那些看书的人是聪明的。李明能看书且不贫穷。快乐的人过着激动人心的生活。
求证：李明过着激动人心的生活。

解：先将问题用谓词表示如下：
“所有不贫穷并且聪明的人都是快乐的”
(∀x) ((～Poor(x)∧Smart(x) →Happy(x))
“那些看书的人是聪明的”
(∀y) (Read(y)→Smart(y))
“李明能看书且不贫穷”
Read(LiMing) ∧～Poor(LiMing)
“快乐的人过着激动人心的生活”
(∀z)(Happy(z)→Exciting(z))
目标“李明过着激动人心的生活”的否定
～Exciting(LiMing)

将上述谓词公式转化为子句集如下：
（1）Poor（x）∨～Smart（x）∨ Happy（x）
（2）～ Read（y）∨ Smart（y）
（3） Read（ LiMing ）
（4）～Poor（ LiMing ）
（5）～Happy（z）∨ Exciting（z）
（6）～Exciting（LiMing ）
按谓词逻辑的归结原理对此子句集进行归结，其归结反演过程如图所示。由于归结出了空子句，这就证明了李明过着激动人心的生活。

4.反演求解过程
①把问题的已知条件用谓词公式表示出来，并化为相应的子句集
②把问题的目标的否定用谓词公式表示出来，并化为子句集
③对目标否定子句集中的每个子句，构造该子句的重言式（即把该目标否定子句和④此目标否定子句的否定之间再进行析取所得到的子句），用这些重言式代替相应的目标否定子句式，并把这些重言式加入到前提子句集中，得到一个新的子句集
⑤对这个新的子句集，应用归结原理求出其证明树，这时证明树的根子句不为空，称这个证明树为修改证明树
⑥用修改证明树的根子句作为回答语句，则答案就在此根子句中。

例题 教室问题
已知：张和李是同班同学，如果x和y是同班同学，则x的教室也是y的教室，现在张在302教室上课。问：现在李在哪里上课？

解：首先定义谓词：
C(x,y) x和y是同班同学；
At(x,u) x在u教室上课。
把已知前提用谓词公式表示如下：
C(zhang,li);
At(zhang,302)
(∀x)(∀y)(∀u)(C(x,y)∧At(x,u) →At(y,u))
把目标的否定用谓词公式表示如下：
～ (∃v)At(li,v)

把上述公式化为子句集：
{C(zhang,li), At(zhang,302), ～C(x,y) ∨～At(x,u) ∨At(y,u)}
把目标的否定化成子句式，并用重言式 ~ At(li,v) ∨ At(li,v)代替之。
并利用 Skolem函数消去存在量词

三.规则演绎系统

1.正向规则演绎系统
（1）事实表达式的与或图
每个节点表示该事实表达式的一个子表达式。
某个事实表达式(E1∨…∨Ek)的析取关系子表达式E1，…，Ek是用后继节点表示的，并由一个k线连接符把它们连接到父辈节点上。
某个事实表达式(E1∧…∧En)的每个合取子表达式E1，…，En是由单一的后继节点表示的，并由一个单线连接符接到父辈接点。

注意:
①与问题归约法和逆向推理中的与或图表示图样正好相反，问题归约法中，用K线连接符表示与，用单线连接符表示或。
②解树集中每个解树的端节点上的文字的析取就是子句集中的一个子句。

（2）与或图的F规则变换
F规则: L→W,其中, L为单文字, W为与或形公式.
F规则的化简
① 暂时消去蕴涵符号;
② 减少否定符号的辖域, 使仅作用于文字;
③ 消去存在量词Skolem化;
④ 化成前束式并消去全称量词;
⑤ 恢复蕴涵式表示：(L1∨L2) →W
⑥ 转换成: L1 → W, L2 →W

例题
事实：((P ∨ Q) ∧ R) ∨ (S ∧ (T ∨ U))
规则：S→(X ∧ Y) ∨ Z

解：

（3）一致解树与一致置换
一致解树：一个具有一致置换的解树称为一致解树。
一致置换：当置换集没有矛盾存在时，称该置换集是一致的，否则就是不一致的。
从事实出发，正向应用规则，到得到目标结点为结束的一致解图为止，存在合一复合时，则解图是一致的。

2.规则逆向演绎系统
（1）从目标表达式出发，反方向使用规则（B规则）对表示目标的与或树进行变换，直到得到含有事实节点的一致解树。
目标表达式: 目标的与或树
事实表达式: 限制为文字的合取形.
规则: B规则, W→L
注：当B规则为W→L1∧L2时，则可化简为两条规则：W→L1，W→L2其中, W是任意形式的与或形，L是单文字。
终止条件: 得到含有事实节点的一致解树
（2）目标公式的与或图表示
规定子表达式间的析取用单线连接符连接，即表示为“或”的关系，而子表达式的合取用K线连接符连接，即表示为“与”的关系。

例题 猫狗问题
事实：
F1: DOG(FIDO)；狗的名字叫Fido
F2: ￢BARKS(FIDO)；Fido是不叫的
F3: WAGS-TAIL(FIDO)；Fido摇尾巴
F4: MEOWS(MYRTLE)；猫咪的名字叫Myrtle
规则：
R1: (WAGS-TAIL(x1)∧DOG(x1))→FRIENDLY(x1); 摇尾巴的狗是温顺的狗
R2: (FRIENDLY(x2)∧￢BARKS(x2))→￢AFRAID(y2,x2)；温顺而又不叫的东西是不值得害怕的
R3: DOG(x3) → ANIMAL(x3)；狗为动物
R4: CAT(x4) →ANIMAL(x4)；猫为动物
R5: MEOWS(x5) → CAT(x5)；猫咪是猫
问题：是否存在这样的一只猫和一条狗，使得这只猫不怕这条狗?

一致解树所有匹配弧上的置换集：{x/x5}，{MYRTLE/x}, {FIDO/y}, {x/y2, y/x2}, {FIDO/y}, {y/x1}, {FIDO/y},{FIDO/y},没有矛盾, 是一致置换集。
回答语句：CAT(MYRTLE)∧DOG(FIDO)∧～AFRAID(MYRTLE,FIDO)

3.规则正向和逆向演绎系统的区别

4.规则双向演绎系统

同时利用规则正向和逆向演绎系统进行演绎推理。

四.产生式系统

1.组成：总数据库、产生式规则、控制策略
2.在冲突解决中用到的排序规则：专一性排序、规则排序、数据排序、规模排序、就近排序、上下文限制

例题：产生式系统
一.综合数据库：{x},其中x为字符

二.规则集

1. IF A∧B THEN C
2. IF A∧C THEN D
3. IF B∧C THEN G
4. IF B∧E THEN F
5. IF D THEN E

三.控制策略：顺序排队
四.初始条件：{A,B}
五.结束条件：F∈{x}
六.求解过程：