离散数学及应用 课件 2.3 谓词逻辑等值式与前束范式

DiscreteMathematics鄢小虎

离散数学2.3谓词逻辑等值式与前束范式等值式基本等值式量词否定等值式量词辖域收缩与扩张等值式量词分配等值式前束范式等值式与基本等值式

基本等值式:命题逻辑中16个基本等值式的代换实例如，

xF(x)

yG(y)

xF(x)

yG(y)(蕴涵等值式)

xF(x)

(

xF(x)

yG(y))

xF(x)(吸收律)课堂练习：

(

xF(x)

yG(y))

xF(x)

yG(y)(德摩根)定义若A

B为逻辑有效式，则称A与B是等值的，记作A

B，并称A

B为等值式.基本等值式(续)量词辖域收缩与扩张等值式

设A(x)是含x自由出现的公式，B中不含x的出现关于全称量词的：

x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B

x(B

A(x))

B

xA(x)关于存在量词的:

x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B

x(A(x)

B)

xA(x)

B

x(B

A(x))

B

xA(x)B与x无关;A(x)与x相关，因此x必须靠近A(x)基本的等值式(续)量词否定等值式（

互换）设A(x)是含x自由出现的公式

xA(x)

x

A(x)(不是所有=存在不是)

xA(x)

x

A(x)量词分配等值式

x(A(x)

B(x))

xA(x)

xB(x)

x(A(x)

B(x))

xA(x)

xB(x)注意：

对

无分配律，

对

无分配律,即

x(A(x)

B(x))

xA(x)

xB(x)

x(A(x)

B(x))

xA(x)

xB(x)

例计算下列公式的真值（提示：代换实例）

(1)xF(x)→(

xyG(x,y)→xF(x))

(2)xF(x)→(

xF(x)yG(y))

(3)

(F(x,y)→R(x,y))R(x,y)解(1)把xF(x)和(

xyG(x,y)分别用P和Q表示则原式P→(Q→P)P(

Q

P)

1把xF(x)和yG(y)分别用P和Q表示

(2)则原式P→(PQ)P(PQ)

1把F(x,y)和R(x,y)分别用P和Q表示(P→Q)

Q

P(QQ)

0

(3)命题逻辑——析取（合取）范式谓词逻辑，规范形式？前束范式前束范式

例如，

x

y(F(x)

(G(y)

H(x,y)))

x

(F(x)

G(x))是前束范式,而

x(F(x)

y(G(y)

H(x,y)))不是前束范式.定义设A为一个谓词逻辑公式,若A具有如下形式Q1x1Q2x2…QkxkB,则称A为前束范式,其中Qi

(1

i

k)为

或

，B为不含量词的公式.简言之：量词都在前面；辖域都在后面抢答：

x(F(x)

G(x))、H(x,y)是不是前束范式？公式的前束范式例求下列公式的前束范式

(1)

xF(x)

xG(x)解

定理（前束范式存在定理）谓词逻辑中的任何公式都存在与之等值的前束范式，但不唯一求前束范式:使用重要等值式、置换规则、换名规则进行等值演算.步骤：消除

、

；利用否定等值式将

内移；利用分配等值式将

x和

x等前移

xF(x)

x

G(x)（量词否定等值式）

x(F(x)

G(x))（量词分配等值式）例(续)(2)

x(M(x)

F(x))解(3)

xF(x)

xG(x)

解

xF(x)

x

G(x)

x(F(x)

G(x))

x(

M(x)

F(x))量词否定等值式

x(M(x)

F(x))两步结果都是前束范式，说明前束范式不惟一.(4)

xP(x)

xQ(x)解例将下面命题符号化并转换为前束范式

(1)没有不犯错误的人

(2)不是所有的人都爱看电影解(1)令F(x)：x是人，G(x)：x犯错误.

x(F(x)

G(x))

x

(F(x)

G(x))否定等值式

x(F(x)

G(x))蕴涵等值式(2)令F(x)：x是人，G(x)：爱看电影.

医疗专家系统本项目实现一个引入谓词逻辑元素的医疗专家系统，同样通过输入文字症状，根据预定义规则输出可能的疾病诊断和推荐检查。相比上一章的专家系统实现，在规则定义等实现环节使用了谓词逻辑中相关概念的描述和推理，可以增强规则推理和描述的能力，便于扩展系统功能专家系统的规则存储在一个字典结构中，便于动态扩展。可以根据医学知识添加新的症状和疾病映射，实现更全面的疾病推断。首先创建专家系统实例，接着依次处理获取用户