《（等值式和前束范式以及推理理论）PPT课件》由会员分享，可在线阅读，更多相关《（等值式和前束范式以及推理理论）PPT课件（49页珍藏版）》请在金锄头文库上搜索。
1、一、等值式,定义 1 若AB为逻辑有效式，则称A与B是等值的， 记作 AB，并称AB为等值式.,定义 2 若谓词公式A和B对任意一个解释都取相同的真值，则称A与B是等值的，记作 AB，并称AB为等值式.,5.1 一阶逻辑等值式与置换规则,二、基本等值式,第一组 命题逻辑中16组基本等值式的代换实例 由代换实例可知,命题逻辑中的等值式可以得到一类谓词逻辑中的等值式.例如 xF(x)yG(y) xF(x)yG(y) (xF(x)yG(y) xF(x)yG(y) 等 第二组 1、 消去量词等值式 设D=a1,a2,an xA(x)A(a1)A(a2)A(an) xA(x)A(a1)A(a2)A(an
2、),2、量词否定等值式 设A(x)是含x自由出现的公式， (1) xA(x)x A(x) (2) xA(x) x A(x),证: (1)对于任意的解释，设其个体域为。,若 xA(x)在解释下为真，由否定律可知， xA(x)为假，根据全称量词的定义，存在x0 D,使A(x)为假，从而A(x)为真，所以解释也使xA(x)为真。,三、量词否定等值式,4个公式的叙述,若 xA(x)在解释下为假，由否定律可知， xA(x)为真，根据全称量词的定义，对任意xD,使A(x)为真，亦即对任意xD， A(x)为假，所以解释也使x A(x)为假。,(2)可类似于(1)证明之，也可以利用(1)的结果证明。（练习题）
3、,设A(x)是含x自由出现的公式， (1) xA(x)x A(x) (2) xA(x) x A(x),令D是全班所有同学组成的集合, A(x): x今天来上课,则 “并非每位同学今天都来上课”逻辑等价于 “有同学今天没有来上课”, “并非有同学今天来上课”逻辑等价于 “每位同学今天都没有来上课”。,量词否定等值式之举例说明：,设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(
4、x)B)xA(x)B x(BA(x)BxA(x),3、 量词辖域收缩与扩张等值式.,4、量词分配等值式,x(A(x)B(x)xA(x)xB(x) x(A(x)B(x)xA(x)xB(x) 注意：对无分配律，对无分配律,证:取具体谓词公式F(x)和G(x) 分别代入A(x)和B(x) 使得x(A(x)B(x) xA(x)xB(x)不是逻辑有效式即可.,5、量词交换等值式,xy A(x,y) y x A(x,y); x y A(x,y) y x A(x,y) .,例 将下面命题用两种形式符号化 (1) 没有不犯错误的人 (2) 不是所有的人都爱看电影,解 (1) 令F(x)：x是人，G(x)：x犯
5、错误. x(F(x)G(x) x(F(x)G(x) 请给出演算过程，并说明理由.,(2) 令F(x)：x是人，G(x)：x爱看电影. x(F(x)G(x) x(F(x)G(x) 给出演算过程，并说明理由.,七、前束范式,例如，xy(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 (1ik) 为或，B为不含量词的公式.,公式的前束范式,定理（前束范式存在定理）： 谓词逻辑中的任何公式都存在与之
6、等值的前束范式。,注意: （1）公式的前束范式不惟一. （2）求公式的前束范式的方法: 利用重要等值式、置换规则、换名规则、代替规则进行等值演算.,换名规则与代替规则,换名规则: 将量词辖域中出现的某个约束出现的 个体变项及对应的指导变项，改成另一个辖域中未 曾出现过的个体变项符号，公式中其余部分不变， 则所得公式与原来的公式等值. 代替规则: 对某自由出现的个体变项用与原公式 中所有个体变项符号不同的符号去代替，则所得公 式与原来的公式等值.,换名规则与代替规则例子,分别用换名规则和代替规则对下列公式改名: x(F(x)G(x) H(x,y) 解: (1)用换名规则: 由于x既是约束变项,又
7、是自由变项,故将约束变项x改为z,得 z(F(z)G(z) H(x,y) (2)用代替规则: 将公式中的自由变项x用z代替,得 x(F(x)G(x) H(z,y),公式的前束范式(续),例 求下列公式的前束范式 (1) x(M(x)F(x) 解 x(M(x)F(x) x(M(x)F(x) （量词否定等值式） x(M(x)F(x) 两步结果都是前束范式，说明前束范式不惟一.,例(续),(2) xF(x)xG(x) 解 xF(x)xG(x) xF(x)xG(x) （量词否定等值式） x(F(x)G(x) （量词分配等值式） 另有一种形式 xF(x)xG(x) xF(x)xG(x) xF(x)yG(
8、y) ( 换名规则 ) xy(F(x)G(y) ( 量词辖域扩张 ) 两种形式是等值的,例(续),(3) xF(x)xG(x) 解 xF(x)xG(x) xF(x)xG(x) x(F(x)G(x) （为什么？） 或 xy(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) （换名规则） zy(F(z)(G(x,y)H(y) （为什么？）,例(续),或 xF(x)y(G(z,y)H(y) （代替规则） xy(F(x)(G(z,y)H(y) (5) x(F(x,y)y(G(x,y)H(x,z) 解
9、用换名规则, 也可用代替规则, 这里用代替规则 x(F(x,y)y(G(x,y)H(x,z) x(F(x,u)y(G(x,y)H(x,z) xy(F(x,u)G(x,y)H(x,z) 注意：x与y不能颠倒,5.3 一阶逻辑的推论理论,一、推理的形式结构 二、判断推理是否正确的方法 三、重要的推理定律 四、推理规则 五、构造证明 六、附加前提证明法,一、推理的形式结构,推理的形式结构有两种： 第一种 A1A2AkB (*) 第二种 前提：A1，A2，Ak 结论： B 其中 A1,A2,Ak,B为谓词逻辑公式. 若(*)为永真式, 则称推理正确, 否则称推理不正确. 判断方法: (1)真值表法;(
10、2)等值演算法;(3)主析取范式法(4)构造证明法. 前3种方法采用第一种形式结构, 构造证明法采用第二种形式结构.,重要的推理定律,第一组 命题逻辑推理定律代换实例 如 xF(x)yG(y)xF(x)为化简律代换实例. 第二组 由基本等值式生成 如 由 xA(x)xA(x) 生成 xA(x)xA(x), xA(x)xA(x), 第三组 xA(x)xB(x)x(A(x)B(x) x(A(x)B(x)xA(x)xB(x),永真蕴涵式,推理规则,(1)前提引入规则 (2)结论引入规则 (3)置换规则 (4)假言推理规则 (5)附加规则 (6)化简规则 (7)拒取式规则 (8)假言三段论规则 (9)
11、析取三段论规则 (10)构造性二难推理规则 (11)合取引入规则,复习,推理规则(续),(12) 全称量词消去规则（简记为UI规则或UI） 两式成立的条件是： 在第一式中，取代x的y应为任意的不在A(x)中 约束出现的个体变项. 在第二式中，c为任意个体常项. 用y或c去取代A(x)中的自由出现的x时，一定要在x自由出现的一切地方进行取代.,推理规则(续),(13) 全称量词引入规则（简记为UG规则或UG） 该式成立的条件是： 无论A(y)中自由出现的个体变项y取何值，A(y) 应该均为真. 取代自由出现的y的x，也不能在A(y)中约束出 现.,推理规则(续),(14) 存在量词引入规则（简记
12、为EG规则或EG） 该式成立的条件是： c是使A为真的特定个体常项. 取代c的x不能在A(c)中出现过.,推理规则(续),(15) 存在量词消去规则（简记为EI规则或EI） 该式成立的条件是： c是使A为真的特定的个体常项.c不能在A(x)、前提或前面的推导公式中出现过。 c不在A(x)中出现. 若A(x)中除自由出现的x外，还有其他自由出现的个体变项，此规则不能使用.,例1 证明苏格拉底三段论: “人都是要死的, 苏格拉 底是人，所以苏格拉底是要死的.”,令 F(x): x是人, G(x): x是要死的, a: 苏格拉底 前提：x(F(x)G(x)，F(a) 结论：G(a),证明： F(a)
13、 前提引入 x(F(x)G(x) 前提引入 F(a)G(a) UI G(a) 假言推理 注意：使用UI时，用a取代x .,构造推理证明(续),例2 乌鸦都不是白色的. 北京鸭是白色的. 因此， 北京鸭不是乌鸦.,令 F(x): x是乌鸦, G(x): x是北京鸭, H(x): x是白色的,前提：x(F(x)H(x)， x(G(x)H(x) 结论：x(G(x)F(x),例2(续),证明： x(F(x)H(x) 前提引入 F(y)H(y) UI x(G(x)H(x) 前提引入 G(y)H(y) UI H(y)G(y) 置换 F(y)G(y) 假言三段论 G(y)F(y) 置换 x(G(x)F(x)
14、 UG,构造推理证明(续),例3 构造下述推理证明 前提：x(F(x)G(x)，xF(x) 结论：xG(x) 证明： xF(x) 前提引入 x(F(x)G(x) 前提引入 F(c) EI F(c)G(c) UI G(c) 假言推理 xG(x) EG 注意：必须先消存在量词,构造推理证明(续),例4 构造下述推理证明 前提：xF(x)xG(x) 结论：x(F(x)G(x) 证明： xF(x)xG(x) 前提引入 xy(F(x)G(y) 置换 x(F(x)G(z) UI F(z)G(z) UI x(F(x)G(x) UG 说明: 不能对xF(x)xG(x)消量词, 因为它不是前束范式. 对此题不能
15、用附加前提证明法.,构造推理证明(续),例5 构造下述推理证明 前提：x(F(x)G(x) 结论：xF(x)xG(x) 证明： xF(x) 附加前提引入 F(y) UI x(F(x)G(x) 前提引入 F(y)G(y) UI G(y) 假言推理 xG(x) UG,stop,基本等值式 （命题定律）,(1)双重否定律 : AA,(5)分配律: A(BC)(AB)(AC) A(BC) (AB)(AC),(4)结合律: (AB)CA(BC) (AB)CA(BC),(3)交换律: ABBA, ABBA,(2)等幂律： AAA, AAA,基本等值式(续),(7)德摩根律 : (AB)AB (AB)AB (8)吸收律: A(AB)A, A(AB)A (9)零律: A11, A00 (10)同一律: A0A, A1A (11)排中律: AA1 (12)矛盾律: AA0,基本等值
