离散数学第五章一阶逻辑等值演算与推理.ppt

《离散数学第五章一阶逻辑等值演算与推理.ppt》由会员分享，可在线阅读，更多相关《离散数学第五章一阶逻辑等值演算与推理.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、主要内容l 一阶逻辑等值式与基本的等值式l 置换规则、换名规则、代替规则l 前束范式l 自然推理系统NL 及其推理规则第五章 一阶逻辑等值演算与推理15.1 一阶逻辑等值式与置换规则定义5.1 设A,B是两个谓词公式,如果A B是永真式,则称A与B等值,记作A B,并称A B是等值式基本等值式第一组 命题逻辑中16组基本等值式的代换实例 例如，xF(x)xF(x),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)量词否定等值式 xA(x)xA(x)xA

2、(x)xA(x)(3)量词辖域收缩与扩张等值式.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)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(B A(x)B xA(x)(4)量词分配等值式 x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)注意：对，对无分配律4置换规则、换名规则、代替规则1.置换规则 设(A)是含A的公式,那么,若A B,

3、则(A)(B).2.换名规则 设A为一公式，将A中某量词辖域中个体变项的所有约束 出现及相应的指导变元换成该量词辖域中未曾出现过的个 体变项符号，其余部分不变，设所得公式为A，则A A.3.代替规则 设A为一公式，将A中某个个体变项的所有自由出现用A中 未曾出现过的个体变项符号代替，其余部分不变，设所得 公式为A，则A A.5实例例1 将下面命题用两种形式符号化,并证明两者等值:(1)没有不犯错误的人解 令F(x)：x是人，G(x)：x犯错误.x(F(x)G(x)或 x(F(x)G(x)x(F(x)G(x)x(F(x)G(x)量词否定等值式 x(F(x)G(x)置换 x(F(x)G(x)置换6

4、实例(2)不是所有的人都爱看电影解 令F(x)：x是人，G(x)：爱看电影.x(F(x)G(x)或 x(F(x)G(x)x(F(x)G(x)x(F(x)G(x)量词否定等值式 x(F(x)G(x)置换 x(F(x)G(x)置换7实例例2 将公式化成等值的不含既有约束出现、又有自由出现的个体变项:x(F(x,y,z)yG(x,y,z)解 x(F(x,y,z)yG(x,y,z)x(F(x,y,z)tG(x,t,z)换名规则 xt(F(x,y,z)G(x,t,z)辖域扩张等值式或者 x(F(x,y,z)yG(x,y,z)x(F(x,u,z)yG(x,y,z)代替规则 xy(F(x,u,z)G(x,y

5、,z)辖域扩张等值式8实例例3 设个体域D=a,b,c,消去下述公式中的量词:(1)xy(F(x)G(y)解 xy(F(x)G(y)(y(F(a)G(y)(y(F(b)G(y)(y(F(c)G(y)(F(a)G(a)(F(a)G(b)(F(a)G(c)(F(b)G(a)(F(b)G(b)(F(b)G(c)(F(c)G(a)(F(c)G(b)(F(c)G(c)9实例解法二 xy(F(x)G(y)x(F(x)yG(y)辖域缩小等值式 x(F(x)G(a)G(b)G(c)(F(a)G(a)G(b)G(c)(F(b)G(a)G(b)G(c)(F(c)G(a)G(b)G(c)例3 设个体域D=a,b,c

6、,消去下述公式中的量词:(1)xy(F(x)G(y)10实例(2)xyF(x,y)xyF(x,y)x(F(x,a)F(x,b)F(x,c)(F(a,a)F(a,b)F(a,c)(F(b,a)F(b,b)F(b,c)(F(c,a)F(c,b)F(c,c)例3 设个体域D=a,b,c,消去下述公式中的量词:1 15.2 一阶逻辑前束范式定义5.2 设A为一个一阶逻辑公式，若A具有如下形式 Q1x1Q2x2QkxkB则称A为前束范式，其中Qi(1 i k)为或，B为不含量词的公式.例如，x(F(x)G(x)xy(F(x)(G(y)H(x,y)是前束范式而 x(F(x)G(x)x(F(x)y(G(y)

7、H(x,y)不是前束范式，12前束范式存在定理定理5.1（前束范式存在定理）一阶逻辑中的任何公式都存在与之等值的前束范式例4 求下列公式的前束范式(1)x(M(x)F(x)解 x(M(x)F(x)x(M(x)F(x)（量词否定等值式）x(M(x)F(x)后两步结果都是前束范式，说明公式的前束范式不惟一.13求前束范式的实例(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)y G(y)换名规则 xy(F(x)G(y)辖域收缩扩张规则14求前束范式的实例

8、(3)xF(x)y(G(x,y)H(y)或 xF(x)y(G(z,y)H(y)代替规则 xy(F(x)(G(z,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)辖域收缩扩张规则155.3 一阶逻辑的推论理论推理的形式结构1.A1A2Ak B 若次式是永真式,则称推理正确,记作A1A2Ak B2.前提:A1,A2,Ak 结论:B推理定理:永真式的蕴涵式16推理定律第一组 命题逻辑推理定律的代换实例 如,xF(x)yG(y)xF(x)第二组 基本等值式生成的推理定律 如,xF(x)xF(x),xF(x)xF(x)x

9、F(x)xF(x),xF(x)xF(x)第三组 其他常用推理定律(1)xA(x)xB(x)x(A(x)B(x)(2)x(A(x)B(x)xA(x)xB(x)(3)x(A(x)B(x)xA(x)xB(x)(4)x(A(x)B(x)xA(x)xB(x)17量词消去引入规则1.全称量词消去规则(-)或 其中x,y是个体变项符号,c是个体常项符号,且在A中x不在y和y的辖域内自由出现.2.全称量词引入规则(+)其中x是个体变项符号,且不在前提的任何公式中自由出现xA(x)A(y)xA(x)A(c)A(x)xA(x)18量词消去引入规则3.存在量词消去规则(-)其中x是个体变项符号,且不在前提的任何公式

10、和B中自由出现 A(x)BxA(x)B19量词消去引入规则4.存在量词引入消去规则(+)或 或其中x,y是个体变项符号,c是个体常项符号,且在A中y和c不在x和x的辖域内自由出现.B A(y)B xA(x)B A(c)B xA(x)A(y)xA(x)A(c)xA(x)20自然推理系统NL定义5.3 自然推理系统NL 定义如下:1.字母表.同一阶语言L 的字母表2.合式公式.同L 的合式公式3.推理规则:(1)前提引入规则(2)结论引入规则(3)置换规则(4)假言推理规则(5)附加规则(6)化简规则(7)拒取式规则21自然推理系统NL(8)假言三段论规则(9)析取三段论规则(10)构造性二难推理

11、规则(11)合取引入规则(12)-规则(13)+规则(14)-规则(15)+规则推理的证明22构造推理证明的实例例5 在自然推理系统NL 中构造下面推理的证明,取个体域R:任何自然数都是整数.存在自然数.所以,存在整数.解 设F(x):x是自然数,G(x):x是整数.前提:x(F(x)G(x),xF(x)结论:xG(x)证明:x(F(x)G(x)前提引入 F(x)G(x)-F(x)xG(x)+xF(x)xG(x)-xF(x)前提引入 xG(x)假言推理 23构造推理证明的实例例6 在自然推理系统NL 中构造下面推理的证明,取个体域R:不存在能表示成分数的无理数.有理数都能表示成分数.所以,有理

12、数都不是无理数.解 设F(x):x是无理数,G(x):x是有理数,H(x):x能表示成分数.前提:x(F(x)H(x),x(G(x)H(x)结论:x(G(x)F(x)证明:x(F(x)H(x)前提引入 x(F(x)H(x)置换 x(F(x)H(x)置换 F(x)H(x)-24构造推理证明的实例 x(G(x)H(x)前提引入 G(x)H(x)-H(x)F(x)置换 G(x)F(x)假言三段论 x(G(x)F(x)+25重要提示要特别注意使用-、+、-、+规则的条件.反例1.对A=xyF(x,y)使用-规则,推得B=yF(y,y).取解释I:个体域为R,在I下A被解释为xy(xy),真;而B被解释

13、为y(yy),假 原因:在A中x自由出现在y的辖域F(x,y)内反例2.前提:P(x)Q(x),P(x)结论:xQ(x)取解释I:个体域为Z,在I下前提为真,结论为假,从而推理不正确26反例2(续)“证明”:P(x)Q(x)前提引入 P(x)前提引入 Q(x)假言推理 xQ(x)+错误原因:在使用+规则,而x在前提的公式中自由出现.27第五章 习题课主要内容l 一阶逻辑等值式 基本等值式，置换规则、换名规则、代替规则l 前束范式l 推理的形式结构l 自然推理系统NL 推理定律、推理规则28基本要求l 深刻理解并牢记一阶逻辑中的重要等值式,并能准确而熟练地应用它们l 熟练正确地使用置换规则、换名

14、规则、代替规则l 熟练地求出给定公式的前束范式l 深刻理解自然推理系统NL 的定义，牢记NL 中的各条推理规则，特别是注意使用、+、+、4条推理规则的条件l 能正确地给出有效推理的证明 29练习11.给定解释I如下:(1)个体域D=2,3(2)(3)(4)求下述在I下的解释及其真值:xy(F(f(x)G(y,f(a)解 xF(f(x)yG(y,f(a)F(f(2)F(f(3)(G(2,f(2)G(3,f(2)10(1 0)030练习22.求下述公式的前束范式:xF(x)y(G(x,y)H(x,y)解 使用换名规则,xF(x)y(G(x,y)H(x,y)zF(z)y(G(x,y)H(x,y)z(

15、F(z)y(G(x,y)H(x,y)z y(F(z)(G(x,y)H(x,y)使用代替规则 xF(x)y(G(x,y)H(x,y)xF(x)y(G(z,y)H(z,y)x(F(x)y(G(z,y)H(z,y)xy(F(x)(G(z,y)H(z,y)31练习33.构造下面推理的证明:(1)前提：x(F(x)G(x),xF(x)结论：xG(x)证明：x(F(x)G(x)前提引入 F(y)G(y)xF(x)前提引入 F(y)G(y)假言推理 yG(y)+xG(x)置换 32练习3(续)(2)前提：x(F(x)G(x),xG(x)结论：xF(x)证明：用归谬法 xF(x)结论否定引入 xF(x)置换

16、xG(x)前提引入 xG(x)置换 x(F(x)G(x),前提引入 F(c)G(c)F(c)G(c)G(c)析取三段论 G(c)G(c)合取引入 33练习3(续)(3)前提：x(F(x)G(x),x(G(x)H(x)结论：xF(x)xH(x)证明:用附加前提法 xF(x)附加前提引入 F(x)x(F(x)G(x)前提引入 F(x)G(x)x(G(x)H(x)前提引入 G(x)H(x)F(x)H(x)假言三段论 H(x)假言推理 xH(x)+34练习44.在自然推理系统NL 中，构造推理的证明 人都喜欢吃蔬菜但不是所有的人都喜欢吃鱼所以,存在喜欢吃蔬菜而不喜欢吃鱼的人解 令F(x):x为人，G(

17、x):x喜欢吃蔬菜，H(x):x喜欢吃鱼前提：x(F(x)G(x),x(F(x)H(x)结论：x(F(x)G(x)H(x)证明：用归谬法(1)x(F(x)G(x)H(x)结论否定引入(2)x(F(x)G(x)H(x)(1)置换(3)(F(y)G(y)H(y)(2)(4)G(y)F(y)H(y)(3)置换(5)x(F(x)G(x)前提引入35练习4(续)(6)F(y)G(y)(5)(7)F(y)F(y)H(y)(4)(6)假言三段论(8)F(y)H(y)(7)置换(9)y(F(y)H(y)(8)+(10)x(F(x)H(x)(9)置换(11)x(F(x)H(x)前提引入(12)0(10)(11)合取 36