《(等值式和前束范式以及推理理论)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,基本等值