数理逻辑（讲义）(8)

(5) A(u)|?(?x)A(x) (??)，(4)

(6) ?(?x)?A(x)|?(?x)A(x) （可传，(4，5))

(7) ?(?x)A(x),?(?x)?A(x)|?(?x)A(x) (单调性， (6)) (8) ?(?x)A(x),?(?x)?A(x)|??(?x)A(x) (?) (9) ?(?x)A(x)|?(?x)?A(x) (

??)，(8，9)

前束范式：Q1x1......QnxnB。其中，Q1,......,Qn?{?,?}，B中不含量词，称为公式的母式。

定理. 每一个谓词公式A都可以划为与之语义等价的前束范式A’.即， A|?|A'，其中A’具有形式Q1x1......QnxnB。

进一步，可以要求母式具有合取范式（或析取范式）形式。 证明方法：基于如下语义等价关系： （1）等价替换

如果A|?|A',B|?|B',C(u)|?|C'(u)，则 （1.1）?A|?|?A' （1.2）A?B|?|A'?B' （1.3）A?B|?|A'?B' （1.4）A?B|?|A'?B' （1.5）A?B|?|A'?B' (1.6) (?x)C(x)|?|(?x)C'(x) (1.7) (?x)C(x)|?|(?x)C'(x)

(保证母式部分可以仿命题公式代范式方法) （2）（量词向前移动）

(2.1)?(?x)A(x)|?|(?x)?A(x)。 （2.2）?(?x)A(x)|?|(?x)?A(x) （3）分配律仍然成立

35

(3.1) A?(B?C)|?|(A?B)?(A?C) (3.2) A?(B?C)|?|(A?B)?(A?C)

前束范式与公式分层：

量词合并：(?x1)(?x2)B(x1,x2)|?|(?x)B(x),x??x1,x2?

(?x1)(?x2)B(x1,x2)|?|(?x)B(x)

标准前束范式：Q1x1......QnxnB前束词Q1x1......Qnxn要求具有如下交替形式：

(?x1)(?x1)......(?xn)(n为奇数),(?x1)(?x1)......(?xn)(n为偶数) (?x1)(?x1)......(?xn)(n为奇数),(?x1)(?x1)......(?xn)(n为偶数)

公式分层：

（1）?0??0:不含量词的公式类。 （2）?1:?{(?x)B:B??0}?1:?{(?x)B:B??0}。

（3）?n?1:?{(?x)B:B??n}?n?1:?{(?x)B:B??n}。 习题：P108: 3.4.3(2,4,6) P119: 3.5.4.

36

第四章 可靠性和完备性

可靠性：指形式推理的可靠性。

形式推理的结论在逻辑推理下是否仍然成立？

可靠性保证：应作系统中形式推理（纯符号演算）结论的正确性、安全性、…..。

一个智能专家系统中，形式推理完全由程序完成。如果没有可靠性保证，专家系统推理的结论不一定可靠、不一定正确。命题逻辑和谓词逻辑中的可靠性定理都成立。 可靠性定理：设A?Form(L),??Form(L)，?|?A??|?A。

完备性：指形式推理的完备性。推理系统的能力。逻辑推理的结论能否在形式推理下完成？ 完备性体现：形式推理系统的推理能力。逻辑推理正确性推理结论，在形式系统中一定能做

到！

一个智能专家系统中，如果形式推理具有完备性，则表示它的能力己经足够。然而，通常的专家系统（如：医疗诊断系统）不具备完全性。所以，是用准确率刻划系统的功能。

命题逻辑和谓词逻辑中的完备性定理都成立。

完备性定理：设A?Form(L),??Form(L)，?|?A??|?A。 从证明的难易程度上看：?|?A的证明比?|?A难。

如果完备性定理成立，则只需证明?|?A，就能保证?|?A成立。

命题逻辑和谓词逻辑中的可靠性定理和完备性定理都成立。 ◆可靠性定理的证明比较容易。直接可以证明。 ◆

完备性定理的证明比较难容易。采用间接证明。证明它的一个等价定理。并将命题逻辑和谓词逻辑中的完备性定理分别证明。 借助于协调性概念，两个定理有如下等价形式： 对于任意的A?Form(L),?,?'?Form(L) 原始定理1 等价定理2

37

可靠性定理 完备性定理 ?|?A??|?A ?|?A??|?A ?'可满足??'协调 ?'协调??'可满足 协调：设??Form(L)，称?不协调，如果存在B?Form(L)，使得?|?B,?|??B。?不是不

协调，称?协调。

可靠性定理

可满足性与有效性：

定理1. 设A?Form(L)，则A可满足??A不是有效。A有效??A 不可满足。 证明：由定义。

定理2. 设A?Form(L)，则

A(u) 可满足? (?x)A(x)可满足。 A(u)有效 ? (?x)A(x)有效。

1?A(u)?A(u)证明：(1) (==>) 设A(u) 可满足。则存在赋值v满足A。令a?uv?D。

即，[(?x)A(u)]v?1。

vv[u/a]，

(<==) 设(?x)A(x) 可满足。则存在赋值v满足(?x)A(x)： [(?x)A(x)]v?1。 由定义，存在

a?D，A(u)v[u/a]?1。

此表明：vua满足A(u).

（2）类似证明。或由定理1及(1)证明。 A(u)有效 ??A(u)为不可满足 ?(?x)A(x有效。■)定理3. (可靠性定理1) 设A?Form(L)，??Form(L)。

如果?|?A，则?|?A。 如果|?A，则|?A。

证明： 对规则的使用归纳法： 如：(??)：

?为不可满足??(?x)A(x)为不可满足(?x)?A(x) 38

?,?A|?B,?,?A|??B?????????????

?|?A归纳假设：?,?A|?B,?,?A|??B，证明：?|?A。

v设赋值v使得??1。如果Av?0，则(?A)v?1。

于是，(???A)v?1，则归纳假设：?,?A|?B,?,?A|??B。我们有：(?B)v?1,Bv?1。矛盾。 如：(??)：(u不在?,B中出现)

?,A(u)|?B ?????????????

?,(?x)A(x)|?B归纳假设：?,A(u)|?B，证明：?,(?x)A(x)|?B。

注意：由于u不在?,B中出现，?v[u/a]??v?1，Bv[u/a]?Bv。

vv?v[u/a]??v?1。设??[(?x)A(x)]?1，?a?D，A(u)v[u/a]?1，由于u不在?,B中出现，

由归纳假设：?,A(u)|?B。因此，Bv[u/a]?1。从而，Bv?Bv[u/a]?1。所以，?,(?x)A(x)|?B。■

定理4. (可靠性定理2) 设??Form(L)，A?Form(L)。

（1）如果?可满足，则?协调。（2）如果A可满足，则A协调。

证明：?可满足，证明：?协调。 若?不协调，则存在B?Form(L)，使得?|?B,?|??B.由(可靠性定理1)，?|?B,?|??B，则?不可满足。否则，存在赋值v, 使得?v?1。从而，

Bv?1,(?B)v?1。矛盾。

从(可靠性定理2)证明 (可靠性定理1)[如果?|?A，则?|?A]。

设?|?A，若?|?A，则??{?A}可满足。由(可靠性定理2)，??{?A}协调。 但是，??{?A}|?A,??{?A}|??A。 表明：??{?A}不协调。矛盾。■

39