- 1、本文档共16页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
第二章 谓词逻辑第5讲 离散数学Discrete Mathematics 第5讲 §2—6 前束范式 要求:理解前束范式、前束合取范式和前束析取范式的定义,会将一个谓词公式wffA化为前束范式、前束合取范式和前束析取范式。 学习本节的目的是掌握谓词公式的标准化形式。 重点:化谓词公式为前束范式。 (4)指导变元、作用域、约束变元、自由变元 一、前束范式 定义2-6.1 一个合式公式称为前束范式,如果它有如下形式: (Q1x1)(Q2x2)…(Qkxk)A 其中Qi(1≤i≤k)为?或?,A为不含有量词的谓词公式。称Q1x1Q2x2…Qkxk为公式的首标。 特别地,若A中无量词,则A也看作是前束范式。 可见,前束范式的特点是,所有量词均非否定地出现在 公式最前面,且它的辖域一直延伸到公式之末。 例如,(?x)(?y)(?z)(P(x,y)?Q(y,z)),R(x,y)等 都是前束范式,而(?x)P(x)?(?y)Q(y), (?x)(P(x)?(?y)Q(x,y))不是前束范式。 定理2.6.1 (前束范式存在定理) Lp中任意公式A都有与之等价的前束范式。 斯柯林范式 前束范式的优点是全部量词集中在公式前面,其缺点是各量词的排列无一定规则,这样当把一个公式化归为前束范式时,其表达形式会显现多种情形,不便应用。1920年斯柯林(Skolem)提出对前束范式首标中量词出现的次序给出规定:每个存在量词均在全称量词之前。按此规定得到的范式形式,称为斯柯林范式。显然,任一公式均可化为斯柯林范式。它的优点是:全公式按顺序可分为三部分,公式的所有存在量词、所有全称量词和辖域。这给Lp的研究提供了一定的方便。 二、前束合取范式 定义2-6.2 一个wffA称为前束合取范式,如果它有如下形式: (Q1x1)(Q2x2)…(Qkxk)[(A11∨A12∨…∨A1l1)∧(A21∨A22∨…∨A2l2) ∧ …∧(Am1∨Am2∨…∨Amlm)] 其中Qi(1≤i≤k)为量词?或?,xi(i=1,2, …,n)是客体变元,Aij是原子公式或其否定。 三、前束析取范式 定义2-6.3 一个wffA称为前束析取范式,如果它有如下形式: (Q1x1)(Q2x2)…(Qkxk)[(A11∧A12∧…∧A1l1) ∨(A21∧A22∧…∧A2l2) ∨ …∨ (Am1∧Am2∧…∧Amlm)] 其中Qi(1≤i≤k)为量词?或?,xi(i=1,2, …,n)是客体变元,Aij是原子公式或其否定。 * * 复习: (1)量词与联结词?之间的关系 (2)量词扩张/收缩律 这里A(x)是任意包括个体变元x的谓词公式,B是不包括个体变元x的任意谓词公式。 (3)量词与命题联结词之间的一些等价式 量词分配律 量词 指导变元 辖域 约束变元 自由变元 (5)约束变元换名和自由变元代入 在一公式中,有的个体变元既是约束出现,又是自由出现,这就容易产生混淆。为了避免混淆,可对约束变元换名或自由变元代入。 约束变元换名 将量词辖域中某个约束出现的个体变元及相应指导变元,改成本辖域中未曾出现过的个体变元,其余不变。 自由变元代入 对某自由出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入,且处处代入。 举例 73页 例题1,例题2,例题3 例题2 化公式 (?x)(?y)((?z)(P(x,z)∧P(y,z))?(?u)Q(x,y,u))为前束范式 解 原公式?(?x)(?y)(┐(?z)(P(x,z)∧P(y,z))∨(?u)Q(x,y,u)) ?(?x)(?y)((?z)(┐P(x,z)∨┐P(y,z))∨(?u)Q(x,y,u)) ?(?x)(?y)(?z)(?u)(┐P(x,z)∨┐P(y,z)∨Q(x,y,u)) 解 第一步否定深入 原式 第二步改名,以便把量词提到前面。 例题3 把公式 练习 75页(1)题 将约束变元x改名为u,将约束变元y改名为z, 化为前束范式 例如公式 是前束合取范式 定理2-6.2 每一个wffA都可转化为与其等价的前束合取范式。 例题4 将wffD: 转化为与其等价的前束合取范式。 解 第一步取消多余量词 第二步换名 第三步消去条件联结词 第四步将否定深入 第五步将量词推到左边 ?(?x)(?z)(?w)[(┐P(x)∨┐R(x,w))∧(┐Q(z,y)∨┐R(x,w))] 例如公式 是前束析取范式。 ) *
您可能关注的文档
- 福建省毕业生就业公共网注册流程.ppt
- 福建省毕业生就业公共网注册登记说明.ppt
- 福建省泉州市实验课题.ppt
- 福建省泉州市泉港三川中学九年级数学总复习课件:第19讲三角形与全等三角形.ppt
- 福建省毕业生就业公共网操作流程.ppt
- 福建省文科数学第三轮:数学思想——数形结合思想28.ppt
- 福建省泉州市泉港博文中学九年级语文《逆向思维立意》课件.ppt
- 福建省福鼎市龙安中学九年级政治《走向共同富裕的道路》课件人教新课标版.ppt
- 福建省罗源县第一中学高中历史明末清初的思想活跃局面课件人民版必修3.ppt
- 福建省福州第三十六中学八年级语文《老王》课件28.ppt
- 北师大版小学数学三年级上册《寄书》教学设计.docx
- 统编版(部编版)语文二年级上册《雪孩子》教学设计.docx
- 统编版(部编版)语文二年级上册《八角楼上》教学设计.docx
- 北师大版小学数学三年级上册《长方形周长》教学设计.docx
- 北师大版小学数学三年级上册《丰收了》教学设计.docx
- 统编版(部编版)语文二年级上册《夜宿山寺》教学设计.docx
- 统编版(部编版)语文二年级上册《风娃娃》教学设计.docx
- 统编版(部编版)语文二年级上册《朱德的扁担》教学设计.docx
- 统编版(部编版)语文二年级上册《难忘的泼水节》教学设计.docx
- 统编版(部编版)语文二年级上册《纸船和风筝》教学设计.docx
文档评论(0)