您的当前位置是：第三章 确定性推理>>学习内容>>知识点五

6．将母式化成合取范式

利用分配律将前束范式化成前束合取范式：

P∨（Q∧R）=（P∨Q）∧（P∨R）（析取转化成合取）

7．消去全称量词

谓词公式已经化成了前束合取范式，且只包含全称量词，此时全称量词的次序也不重要了，所以可以消去全部量词（即前束、前缀）。

8．消去合取连结词∧

母式为合取范式：

A₁∧A₂∧…∧A_n

消去合取连结词∧，得到子句集：

{A₁，A₂，…，A_n}

9．更换变元名

更改变元名，使得一个变量符号不出现在一个以上的子句中，即不同的子句包含不同的约束变元名。

例3.9 将谓词公式化成子句集。

（x）A（x）=>（x）B（x）  仔细分析量词的辖域

①～（x）A（x）∨（x）B（x）  （消去“蕴含”）

②（x）（～A（x））∨（x）B（x）  （“非”直接作用谓词符号）

③（x）（～A（x））∨（z）B（z）  （改名）

④x=a，z=b

～A（a）∨B（b）  （消去存在量词）

子句集={～A（a）∨B（b）}

例3.10将谓词公式化成子句集。

[（x）P（x）∨（y）Q（y）]=>（x）R（x）

①～[（x）P（x）∨（y）Q（y）]∨（x）R（x）

②[～（x）P（x）∧～（y）Q（y）]∨（x）R（x）

=[（x）（～P（x））∧（y）（～Q（y））]∨（x）R（x）

③[（x）（～P（x））∧（y）（～Q（y））]∨（z）R（z） （改名）

④消去存在量词，x=a

[（～P（a））∧（y）（～Q（y））]∨（z）R（z）

⑤化成前束范式

（y）（z）[（～P（a））∧～Q（y）]∨R（z）

⑥化成前束合取范式

（y）（z）[（～P（a））∨R（z）]∧[～Q（y）∨R（z）]

⑦消去全称量词

[～P（a）∨R（z）]∧[～Q（y）∨R（z）]

⑧消去合取连结词∧

子句集={～P（a）∨R（z），～Q（y）∨R（z）}

⑨更换变元名

子句集={～P（a）∨R（z），～Q（y）∨R（x）}

三、 消解原理

1．消解式

令L1为任一原子公式，L2为另一原子公式；L1和L2具有相同的谓词符号，但一般具有不同的变量。

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

例3.10

设c₁=P（x）∨Q（x），c₂=～P（a）∨R（y），{P（x），P（a）}的最一般的合一者为{a/x}，α=Q（x），β=R（y），则c₁，c₂的消解式为c=Q（a）∨R（y）

1  2  3  4  5