2.3 一阶逻辑等值式与前束范式_第1页
2.3 一阶逻辑等值式与前束范式_第2页
2.3 一阶逻辑等值式与前束范式_第3页
2.3 一阶逻辑等值式与前束范式_第4页
2.3 一阶逻辑等值式与前束范式_第5页
已阅读5页，还剩5页未读， 继续免费阅读

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

2.3谓词逻辑等值式与前束范式定义若A

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

B，并称A

B为等值式.基本等值式:命题逻辑中16组基本等值式的代换实例如，

xF(x)

yG(y)

xF(x)

yG(y)

(

xF(x)

yG(y))

xF(x)

yG(y)等消去量词等值式设D={a1,a2,…,an}

xA(x)

A(a1)

A(a2)

…

A(an)

xA(x)

A(a1)

A(a2)

…

A(an)1量词否定等值式

xA(x)

x

A(x)；

xA(x)

x

A(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)2量词辖域收缩与扩张等值式

设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)3量词分配等值式

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)

前束范式

定义设A为一个一阶逻辑公式,若A具有如下形式Q1x1Q2x2…QkxkB,则称A为前束范式,其中Qi

(1

i

k)为

或

，B为不含量词的公式.例如，

x

y(F(x)

(G(y)

H(x,y)))

x

(F(x)

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

x(F(x)

y(G(y)

H(x,y)))

x(F(x)

G(x))不是前束范式.换名规则:将量词辖域中出现的某个约束出现的个体变项及对应的指导变项，改成其他辖域中未曾出现过的个体变项符号，公式中其余部分不变，则所得公式与原来的公式等值.定理

一阶逻辑中的任何公式都存在与之等值的前束范式.求前束范式:使用重要等值式、置换规则、换名规则进行等值演算.例求下列公式的前束范式

(1)

x(M(x)

F(x))解

x(

M(x)

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

x(M(x)

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

xF(x)

xG(x)解

xF(x)

x

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

x(F(x)

G(x))（量词分配等值式）或者

xF(x)

x

G(x)

xF(x)

y

G(y)(换名规则)

x

y(F(x)

G(y))(量词辖域扩张)(3)

xF(x)

xG(x)

解

xF(x)

x

G(x)

x(F(x)

G(x))或

xF(x)

yG(y)

x(F(x)

y

G(y))

x

y(F(x)

G(y))(4)

xF(x)

y(G(x,y)

H(y))解

zF(z)

y(G(x,y)

H(y))

z

y(F(z)

(G(x,y)

H(y)))(5)

x(F(x,y)

y(G(x,y)

H(x,z)))解

x(F(x,y)

u(G(x,u)

H(x,z)))

x

u(F(x,y)

G(x,u)

H(x,z)))注意：

与

不能颠倒苏格拉底三段论的正确性“凡是人都要死的.苏格拉底是人.所以苏格拉底是要死的.”设F(x)：x是人，G(x)：x是要死的，a：苏格拉底.∀x(F(x)→G(x))∧F(a)→G(a)设前件为真，即∀x(F(x)

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论