施工基础原理教案模板（共2篇）

第1篇：人工智能原理教案02章归结推理方法2.3谓词逻辑归结法基础

2.3 谓词逻辑归结法基础

由于谓词逻辑与命题逻辑不同，有量词、变量和函数，所以在生成子句集之前要对逻辑公式做处理，具体的说就是要将其转化为Skolem标准形，然后在子句集的基础上再进行归结，虽然基本的归结的基本方法都相同，但是其过程较之命题公式的归结过程要复杂得多。

本节针对谓词逻辑归结法介绍了Skolem标准形、子句集等一些必要的概念和定理。

2．3．1 Skolem 标准形 Skolem标准形的定义：

前束范式中消去所有的存在量词，则称这种形式的谓词公式为Skolem标准形，任何一个谓词公式都可以化为与之对应的Skolem标准形。但是，Skolem标准形不唯一。

前束范式：A是一个前束范式，如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端。

Skolem标准形的转化过程为，依据约束变量换名规则，首先把公式变型为前束范式，然后依照量词消去原则消去或者略去所有量词。具体步骤如下：

将谓词公式G转换成为前束范式

前束范式的形式为：

(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn)

即： 把所有的量词都提到前面去。

注意：由于所有的量词的辖域都延伸到公式的末端，即，最左边量词将约束表达式中的所有同名变量。所以将量词提到公式最前端时存在约束变量换名问题。要严守规则。

约束变量换名规则：

(Qx)M（x）（Qy）M（y）

(Qx)M（x,z）（Qy）M（y,z）

量词否定等值式：

～(x)M（x）（y）～ M（y）

～(x)M（x）（y）～ M（y）

量词分配等值式：

(x)(P（x）∧Q（x）)(x)P（x）∧(x)Q（x）

(x)(P（x）∨ Q（x）)(x)P（x）∨(x)Q（x）

消去量词等值式：设个体域为有穷集合（a1, a2, …an）

(x)P（x）P（a1）∧ P（a2）∧ …∧ P（an）

(x)P（x）P（a1）∨ P（a2）∨ … ∨ P（an）

量词辖域收缩与扩张等值式：

(x)(P（x）∨ Q)(x)P（x）∨ Q

(x)(P（x）∧ Q)(x)P（x）∧ Q

(x)(P（x）→ Q)(x)P（x）→ Q

(x)(Q → P（x）)Q →(x)P（x）

(x)(P（x）∨ Q)(x)P（x）∨ Q

(x)(P（x）∧ Q)(x)P（x）∧ Q

(x)(P（x）→ Q)(x)P（x）→ Q

(x)(Q → P（x）)Q →(x)P（x）消去量词

量词消去原则：

1)消去存在量词""，即，将该量词约束的变量用任意常量（a, b等）、或全称变量的函数(f(x), g(y)等)代替。如果存在量词左边没有任何全称量词，则只将其改写成为常量；如果是左边有全程量词的存在量词，消去时该变量改写成为全程量词的函数。

2)略去全程量词""，简单地省略掉该量词。

Skolem 定理：

谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。

注意：公式G的SKOLEM标准形同G并不等值。例题2-2

将下式化为Skolem标准形：

～(x)(y)P(a, x, y)→(x)(～(y)Q(y, b)→R(x))

解：

第一步，消去→号，得：

～(～(x)(y)P(a, x, y))∨(x)(～～(y)Q(y, b)∨R(x))

第二步，～深入到量词内部，得：

(x)(y)P(a, x, y)∧～(x)((y)Q(y, b)∨R(x))

＝(x)(y)P(a, x, y)∧(x)((y)～Q(y, b)∧～R(x))

第三步，全称量词左移，（利用分配律），得

(x)((y)P(a, x, y)∧(y)(～Q(y, b)∧～R(x)))

第四步，变元易名，存在量词左移，直至所有的量词移到前面，得：

(x)((y)P(a, x, y)∧(y)(～Q(y, b)∧～R(x)))

＝(x)((y)P(a, x, y)∧(z)(～Q(z, b)∧～R(x)))

=(x)(y)(z)(P(a, x, y)∧～Q(z, b)∧～R(x))

由此得到前述范式

第五步，消去""（存在量词），略去""全称量词

消去(y)，因为它左边只有("x)，所以使用x的函数f(x)代替之，这样得到：

(x)(z)(P(a, x, f(x))∧～Q(z, b)∧～R(x))

消去(z)，同理使用g(x)代替之，这样得到：

(x)(P(a, x, f(x))∧～Q(g(x), b)∧～R(x))

则，略去全称变量，原式的Skolem标准形为：

P(a, x, f(x))∧～Q(g(x), b)∧～R(x)2.3.2子句集

文字：不含任何连接词的谓词公式。

子句：一些文字的析取（谓词的和）。

子句集：所有子句的集合对于任一个公式G，都可以通过Skolem标准形，标准化建立起一个子句集与之相对应。因为子句不过是一些文字的析取，是一种比较简单的形式，所以对G的讨论就用对子句集S的讨论来代替，以便容易处理。

子句集S可由下面的步骤求取：

1.谓词公式G转换成前束范式

2.消去前束范式中的存在变量，略去其中的任意变量，生成SKOLEM标准形

3.将SKOLEM标准形中的各个子句提出，表示为集合形式

教师提示：为了简单起见，子句集生成可以理解为是用"，"取代SKOLEM标准形中的"Λ"，并表示为集合形式。

注意：SKOLEM标准形必须满足合取范式的条件。即，在生成子句集之前逻辑表达式必须是各"谓词表达式"或"谓词或表达式"的与。定理

谓词表达式G是不可满足的当且仅当 其子句集S是不可满足的公式G与其子句集S并不等值，但它们在不可满足的意义下是一致的。因此如果要证明A1∧A2∧A3→B，只需证明G＝ A1∧A2∧A3∧～B的子句集是不可满足的，这也正是引入子句集的目的。

注意：公式G和子句集S虽然不等值，但是它们的之间一般逻辑关系可以简单的说明为：G真不一定S真，而S真必有G真，即，S G。在生成SKOLEM标准形时将存在量词用常量或其他变量的函数代替，使得变量讨论的论域发生了变化，即论域变小了。所以G不能保证S真。定理的推广

对于形如G = G1Λ G2Λ G3Λ …Λ Gn 的谓词公式，G的子句集的求取过程可以分解成几个部分单独处理。如果Gi的子句集为Si，则

有 S' = S1 ∪ S2 ∪ S3 ∪ …∪ Sn，虽然G的子句集不为S'，但是可以证明：

SG 与S1 ∪ S2 ∪ S3 ∪ …∪Sn在不可满足的意义上是一致的。

即SG 不可满足 S1 ∪ S2 ∪S3 ∪ …∪ Sn不可满足

第2篇：人工智能原理教案02章 归结推理方法2.3 谓词逻辑归结法基础[推荐]

2.3 谓词逻辑归结法基础

由于谓词逻辑与命题逻辑不同，有量词、变量和函数，所以在生成子句集之前要对逻辑公式做处理，具体的说就是要将其转化为Skolem标准形，然后在子句集的基础上再进行归结，虽然基本的归结的基本方法都相同，但是其过程较之命题公式的归结过程要复杂得多。

本节针对谓词逻辑归结法介绍了Skolem标准形、子句集等一些必要的概念和定理。

2．3．1 Skolem 标准形

Skolem标准形的定义：

前束范式中消去所有的存在量词，则称这种形式的谓词公式为Skolem标准形，任何一个谓词公式都可以化为与之对应的Skolem标准形。但是，Skolem标准形不唯一。

前束范式：A是一个前束范式，如果A中的一切量词都位于该公式的最左边（不含否定词），且这些量词的辖域都延伸到公式的末端。

Skolem标准形的转化过程为，依据约束变量换名规则，首先把公式变型为前束范式，然后依照量词消去原则消去或者略去所有量词。具体步骤如下：

将谓词公式G转换成为前束范式

前束范式的形式为：

(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,…,xn)

即： 把所有的量词都提到前面去。

注意：由于所有的量词的辖域都延伸到公式的末端，即，最左边量词将约束表达式中的所有同名变量。所以将量词提到公式最前端时存在约束变量换名问题。要严守规则。

约束变量换名规则：

(Qx)M（x）

(Qx)M（x,z）

（Qy）M（y）

（Qy）M（y,z）

量词否定等值式：

～(x)M（x）

～(x)M（x）

量词分配等值式：

(x)(P（x）∧Q（x）)

(x)(P（x）∨ Q（x）)

(x)P（x）∧(x)Q（x）(x)P（x）∨(x)Q（x）

（y）～ M（y）

（y）～ M（y）

消去量词等值式：设个体域为有穷集合（a1, a2, …an）

(x)P（x）

(x)P（x）

P（a1）∧ P（a2）∧ …∧ P（an）P（a1）∨ P（a2）∨ … ∨ P（an）

量词辖域收缩与扩张等值式：

(x)(P（x）∨ Q)

(x)(P（x）∧ Q)

(x)(P（x）→ Q)

(x)(Q → P（x）)

(x)P（x）∨ Q(x)P（x）∧ Q(x)P（x）→ Q Q →(x)P（x）

(x)(P（x）∨ Q)

(x)(P（x）∧ Q)

(x)(P（x）→ Q)

(x)(Q → P（x）)

消去量词

量词消去原则：

(x)P（x）∨ Q(x)P（x）∧ Q(x)P（x）→ Q Q →(x)P（x）

1)消去存在量词""，即，将该量词约束的变量用任意常量（a, b等）、或全称变量的函数(f(x), g(y)等)代替。如果存在量词左边没有任何全称量词，则只将其改写成为常量；如果是左边有全程量词的存在量词，消去时该变量改写成为全程量词的函数。

2)略去全程量词""，简单地省略掉该量词。

Skolem 定理：

谓词逻辑的任意公式都可以化为与之等价的前束范式，但其前束范式不唯一。

注意：公式G的SKOLEM标准形同G并不等值。例题2-2

将下式化为Skolem标准形：

～(x)(y)P(a, x, y)→(x)(～(y)Q(y, b)→R(x))

解：

第一步，消去→号，得：

～(～(x)(y)P(a, x, y))∨(x)(～～(y)Q(y, b)∨R(x))

第二步，～深入到量词内部，得：

(x)(y)P(a, x, y)∧～(x)((y)Q(y, b)∨R(x))

＝(x)(y)P(a, x, y)∧(x)((y)～Q(y, b)∧～R(x))

第三步，全称量词左移，（利用分配律），得

(x)((y)P(a, x, y)∧(y)(～Q(y, b)∧～R(x)))

第四步，变元易名，存在量词左移，直至所有的量词移到前面，得：

(x)((y)P(a, x, y)∧(y)(～Q(y, b)∧～R(x)))

＝(x)((y)P(a, x, y)∧(z)(～Q(z, b)∧～R(x)))

=(x)(y)(z)(P(a, x, y)∧～Q(z, b)∧～R(x))

由此得到前述范式

第五步，消去""（存在量词），略去""全称量词

消去(y)，因为它左边只有("x)，所以使用x的函数f(x)代替之，这样得到：

(x)(z)(P(a, x, f(x))∧～Q(z, b)∧～R(x))

消去(z)，同理使用g(x)代替之，这样得到：

(x)(P(a, x, f(x))∧～Q(g(x), b)∧～R(x))

则，略去全称变量，原式的Skolem标准形为：

P(a, x, f(x))∧～Q(g(x), b)∧～R(x)

2.3.2子句集

文字：不含任何连接词的谓词公式。

子句：一些文字的析取（谓词的和）。

子句集：所有子句的集合对于任一个公式G，都可以通过Skolem标准形，标准化建立起一个子句集与之相对应。因为子句不过是一些文字的析取，是一种比较简单的形式，所以对G的讨论就用对子句集S的讨论来代替，以便容易处理。

子句集S可由下面的步骤求取：

1.谓词公式G转换成前束范式

2.消去前束范式中的存在变量，略去其中的任意变量，生成SKOLEM标准形

3.将SKOLEM标准形中的各个子句提出，表示为集合形式

教师提示：为了简单起见，子句集生成可以理解为是用"，"取代SKOLEM标准形中的"Λ"，并表示为集合形式。

注意：SKOLEM标准形必须满足合取范式的条件。即，在生成子句集之前逻辑表达式必须是各"谓词表达式"或"谓词或表达式"的与。

定理

谓词表达式G是不可满足的当且仅当 其子句集S是不可满足的公式G与其子句集S并不等值，但它们在不可满足的意义下是一致的。因此如果要证明A1∧A2∧A3→B，只需证明G＝ A1∧A2∧A3∧～B的子句集是不可满足的，这也正是引入子句集的目的。

注意：公式G和子句集S虽然不等值，但是它们的之间一般逻辑关系可以简单的说明为：G真不一定S真，而S真必有G真，即，S G。在生成SKOLEM标准形时将存在量词用常量或其他变量的函数代替，使得变量讨论的论域发生了变化，即论域变小了。所以G不能保证S真。

定理的推广

对于形如G = G1Λ G2Λ G3Λ …Λ Gn 的谓词公式，G的子句集的求取过程可以分解成几个部分单独处理。如果Gi的子句集为Si，则

有 S' = S1 ∪ S2 ∪ S3 ∪ …∪ Sn，虽然G的子句集不为S'，但是可以证明：

SG 与S1 ∪ S2 ∪ S3 ∪ …∪Sn在不可满足的意义上是一致的。

即SG 不可满足

由上面的定理，我们对SG的讨论，可以用较为简单的S1 ∪ S2 ∪ S3 ∪ …∪ Sn来代替。为方便起见，也称S1 ∪ S2 ∪ S3 ∪ …∪ Sn为G的子句形，即：

S1 ∪ S2 ∪S3 ∪ …∪ Sn不可满足

SG＝S1 ∪ S2 ∪ S3 ∪ …∪ Sn。根据以上定理可对一个谓词表达式分而治之，化整为零，大大减少了计算复杂度。

例2－3

对所有的x,y,z来说，如果y是x的父亲，z又是y的父亲，则z是x的祖父。又知每个人都有父亲，试问对某个人来说谁是它的祖父？

用一阶逻辑表示这个问题，并建立子句集。

解：

这里我们首先引入谓词：

P(x, y)表示x是y的父亲

Q(x, y)表示x是y的祖父

ANS(x)表示问题的解答

于是有：

对于第一个条件，"如果y是x的父亲，z又是y的父亲，则z是x的祖父"，一阶逻辑表达式如下：

A1：(x)(y)(z)(P(x, y)∧P(y, z)→Q(x, z))

则把A1化为合取范式，进而化为Skolem标准形，表示如下：

S A1：～P(x ,y)∨～P(y, z)∨Q(x, z)

对于第二个条件："每个人都有父亲"，一阶逻辑表达式如下：

A2：(y)(x)P(x, y)

化为Skolem标准形，表示如下：

S A2：P(f(y), x)

结论：某个人是它的祖父

B：(x)(y)Q(x, y)

否定后得到子句：

S～B：～Q(x, y)∨ANS(x)

则得到的相应的子句集为：{ S A1，S A2，S～B }

解毕。

厂房基础施工方案

《分类计数原理》教案

化工原理教案模板

机械原理教案模板

教育学原理教案模板