《离散数学 第二章 一阶逻辑等值式(精品).ppt》由会员分享，可在线阅读，更多相关《离散数学 第二章 一阶逻辑等值式(精品).ppt（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2.3 一阶逻辑等值式一阶逻辑等值式等值式等值式基本等值式基本等值式量词否定等值式量词否定等值式量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式量词分配等值式量词分配等值式前束范式前束范式 1等值式与基本等值式等值式与基本等值式 基本等值式基本等值式:命题逻辑中命题逻辑中1616组基本等值式的代换实例组基本等值式的代换实例如，如，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)定义定义 若若AB为逻辑有效式，则称为逻辑有
2、效式，则称A与与B是是等值等值的，的，记作记作 AB，并称并称AB为为等值式等值式.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(BA(x)BxA(x)关于存在量词的关于存在量词的:x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x)BxA(x)3基本的等值式基本的等值式(续续)量词否定等值式量词否定等值
3、式设设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)注意：注意：对对 无分配律，无分配律，对对 无分配律无分配律 4基本的等值式基本的等值式(续续)例例 将下面命题用两种形式符号化将下面命题用两种形式符号化 (1)没有不犯错误的人没有不犯错误的人 (2)不是所有的人都爱看电影不是所有的人都爱看电影解解(1)令令F(x)：x是人，是人，G(x)：x犯错误犯错误.x(F(x)G(x)x(F(x)G(x)请给出演算过程，并说明理由请给出演算过程，
4、并说明理由.(2)令令F(x)：x是人，是人，G(x)：爱看电影爱看电影.x(F(x)G(x)x(F(x)G(x)给出演算过程，并说明理由给出演算过程，并说明理由.5前束范式前束范式 例如，例如，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)不是前束范式不是前束范式.定义定义 设设A为一个一阶逻辑公式为一个一阶逻辑公式,若若A具有如下形式具有如下形式Q1x1Q2x2QkxkB,则称则称A为为前束范式前束范式,其中其中Qi(1 i k)为为 或或，B为不含量词的公式为不含量词的公式.6公式的前束范式公
5、式的前束范式 定理（前束范式存在定理）定理（前束范式存在定理）一阶逻辑中的任何公一阶逻辑中的任何公式都存在与之等值的前束范式式都存在与之等值的前束范式 注意注意:公式的前束范式不惟一公式的前束范式不惟一 求公式的前束范式的方法求公式的前束范式的方法:利用重要等值式、利用重要等值式、置换规则、换名规则、代替规则进行等值演算置换规则、换名规则、代替规则进行等值演算.7换名规则与代替规则换名规则与代替规则 换名规则换名规则:将量词辖域中出现的某个约束出现的将量词辖域中出现的某个约束出现的个体变项及对应的指导变项，改成其他辖域中未个体变项及对应的指导变项，改成其他辖域中未曾出现过的个体变项符号，公式中
6、其余部分不变，曾出现过的个体变项符号，公式中其余部分不变，则所得公式与原来的公式等值则所得公式与原来的公式等值.代替规则代替规则:对某自由出现的个体变项用与原公式对某自由出现的个体变项用与原公式中所有个体变项符号不同的符号去代替，则所得公中所有个体变项符号不同的符号去代替，则所得公式与原来的公式等值式与原来的公式等值.8公式的前束范式公式的前束范式(续续)例例 求下列公式的前束范式求下列公式的前束范式 (1)x(M(x)F(x)解解 x(M(x)F(x)x(M(x)F(x)（量词否定等值式）量词否定等值式）x(M(x)F(x)两步结果都是前束范式，说明前束范式不惟一两步结果都是前束范式，说明前
7、束范式不惟一.9例例(续续)(2)xF(x)xG(x)解解 xF(x)xG(x)xF(x)x G(x)（量词否定等值式）量词否定等值式）x(F(x)G(x)（量词分配等值式）量词分配等值式）另有一种形式另有一种形式 xF(x)xG(x)xF(x)x G(x)xF(x)y G(y)(换名规则换名规则)x y(F(x)G(y)(量词辖域扩张量词辖域扩张)两种形式是等值的两种形式是等值的 10例例(续续)(3)xF(x)xG(x)解解 xF(x)xG(x)xF(x)x G(x)x(F(x)G(x)（为什么？）为什么？）或或 x y(F(x)G(y)（为什么？）为什么？）(4)xF(x)y(G(x,y)H(y)解解 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)（为什么？）为什么？）11例例(续续)或或 xF(x)y(G(z,y)H(y)（代替规则）代替规则）x y(F(x)(G(z,y)H(y)(5)x(F(x,y)y(G(x,y)H(x,z)解解 用换名规则用换名规则,也可用代替规则也可用代替规则,这里用代替规则这里用代替规则 x(F(x,y)y(G(x,y)H(x,z)x(F(x,u)y(G(x,y)H(x,z)x y(F(x,u)G(x,y)H(x,z)注意：注意：x与与 y不能颠倒不能颠倒 12