离散数学高等教育出版社屈婉玲市公开课一等奖百校联赛特等奖课件.pptx

主要内容主要内容一阶逻辑等值式与基本等值式一阶逻辑等值式与基本等值式置换规则、换名规则、代替规则置换规则、换名规则、代替规则前束范式前束范式自然推理系统自然推理系统NL 及其推理规则及其推理规则第五章第五章 一阶逻辑等值演算与推理一阶逻辑等值演算与推理1第1页5.1 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则定义定义5.1 设设A,B是两个谓词公式是两个谓词公式,假如假如AB是永真式是永真式,则称则称A与与B等值等值,记作记作AB,并称并称AB是是等值式等值式基本等值式基本等值式第一组第一组 命题逻辑中命题逻辑中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页基本等值式基本等值式(2)量词否定等值式量词否定等值式 xA(x)x A(x)xA(x)x A(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(BA(x)BxA(x)3第3页基本等值式基本等值式 关于存在量词：关于存在量词：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)(4)量词分配等值式量词分配等值式 x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)注意：注意：对对，对对 无分配律无分配律4第4页置换规则、换名规则、代替规则置换规则、换名规则、代替规则1.置换规则置换规则 设设(A)是含是含A公式公式,那么那么,若若AB,则则(A)(B).2.换名规则换名规则 设设A为一公式，将为一公式，将A中某量词辖域中个体变项全部约束中某量词辖域中个体变项全部约束 出现及对应指导变元换成该量词辖域中未曾出现过个出现及对应指导变元换成该量词辖域中未曾出现过个 体变项符号，其余部分不变，设所得公式为体变项符号，其余部分不变，设所得公式为A，则，则AA.3.代替规则代替规则 设设A为一公式，将为一公式，将A中某个个体变项全部自由出现用中某个个体变项全部自由出现用A中中 未曾出现过个体变项符号代替，其余部分不变，设所得未曾出现过个体变项符号代替，其余部分不变，设所得 公式为公式为A，则，则AA.5第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第6页实例实例(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第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)换名规则换名规则 x t(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)代替规则代替规则 x y(F(x,u,z)G(x,y,z)辖域扩张等值式辖域扩张等值式8第8页实例实例例例3 设个体域设个体域D=a,b,c,消去下述公式中量词消去下述公式中量词:(1)x y(F(x)G(y)解解 x y(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第9页实例实例解法二解法二 x y(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)10第10页实例实例(2)x yF(x,y)x yF(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)11第11页5.2 一阶逻辑前束范式一阶逻辑前束范式定义定义5.2 设设A为一个一阶逻辑公式，若为一个一阶逻辑公式，若A含有以下形式含有以下形式 Q1x1Q2x2QkxkB则称则称A为为前束范式前束范式，其中，其中Qi(1 i k)为为 或或，B为不含量词为不含量词公式公式.比如，比如，x(F(x)G(x)x y(F(x)(G(y)H(x,y)是前束范式是前束范式而而 x(F(x)G(x)x(F(x)y(G(y)H(x,y)不是前束范式，不是前束范式，12第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第13页求前束范式实例求前束范式实例 (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)辖域收缩扩张规则辖域收缩扩张规则14第14页求前束范式实例求前束范式实例(3)xF(x)y(G(x,y)H(y)或或 xF(x)y(G(z,y)H(y)代替规则代替规则 x y(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)辖域收缩扩张规则辖域收缩扩张规则15第15页5.3 一阶逻辑推论理论一阶逻辑推论理论推理形式结构推理形式结构1.A1 A2Ak B 若次式是永真式若次式是永真式,则称推理正确则称推理正确,记作记作A1 A2Ak B2.前提前提:A1,A2,Ak 结论结论:B推理定理推理定理:永真式蕴涵式永真式蕴涵式16第16页推理定理推理定理第一组第一组 命题逻辑推理定理代换实例命题逻辑推理定理代换实例 如如,xF(x)yG(y)xF(x)第二组第二组 基本等值式生成推理定理基本等值式生成推理定理 如如,xF(x)xF(x),xF(x)xF(x)xF(x)x F(x),x F(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第17页量词消去引入规则量词消去引入规则1.全称量词消去规则全称量词消去规则(-)或或 其中其中x,y是个体变项符号是个体变项符号,c是个体常项符号是个体常项符号,且在且在A中中x不在不在 y和和 y辖域内自由出现辖域内自由出现.2.全称量词引入规则全称量词引入规则(+)其中其中x是个体变项符号是个体变项符号,且不在前提任何公式中自由出现且不在前提任何公式中自由出现 xA(x)A(y)xA(x)A(c)A(x)xA(x)18第18页量词消去引入规则量词消去引入规则3.存在量词消去规则存在量词消去规则(-)其中其中x是个体变项符号是个体变项符号,且不在前提任何公式和且不在前提任何公式和B中自由中自由出现出现 A(x)BxA(x)B19第19页量词消去引入规则量词消去引入规则4.存在量词引入消去规则存在量词引入消去规则(+)或或 或或其中其中x,y是个体变项符号是个体变项符号,c是个体常项符号是个体常项符号,且在且在A中中y和和c不不在在 x和和 x辖域内自由出现辖域内自由出现.BA(y)BxA(x)BA(c)BxA(x)A(y)xA(x)A(c)xA(x)20第20页自然推理系统自然推理系统NL定义定义5.3 自然推理系统自然推理系统NL 定义以下定义以下:1.字母表字母表.同一阶语言同一阶语言L 字母表字母表2.合式公式合式公式.同同L 合式公式合式公式3.推理规则推理规则:(1)前提引入规则前提引入规则(2)结论引入规则结论引入规则(3)置换规则置换规则(4)假言推理规则假言推理规则(5)附加规则附加规则(6)化简规则化简规则(7)拒取式规则拒取式规则21第21页自然推理系统自然推理系统NL(8)假言三段论规则假言三段论规则(9)析取三段论规则析取三段论规则(10)结构性二难推理规则结构性二难推理规则(11)合取引入规则合取引入规则(12)-规则规则(13)+规则规则(14)-规则规则(15)+规则规则推理证实推理证实22第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第23页结构推理证实实例结构推理证实实例例例6 在自然推理系统在自然推理系统NL 中结构下面推理证实中结构下面推理证实,取个体域取个体域R:不存在能表示成份数无理数不存在能表示成份数无理数.有理数都能表示成份数有理数都能表示成份数.所以所以,有理数都不是无理数有理数都不是无理数.解解 设设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第24页结构推理证实实例结构推理证实实例 x(G(x)H(x)前提引入前提引入 G(x)H(x)-H(x)F(x)置换置换 G(x)F(x)假言三段论假言三段论 x(G(x)F(x)+25第25页主要提醒主要提醒要尤其注意使用要尤其注意使用-、+、-、+规则条件规则条件.反例反例1.对对A=x yF(x,y)使用使用-规则规则,推得推得B=yF(y,y).取解释取解释I:个体域为个体域为R,在在I下下A被解释为被解释为 x y(xy),真真;而而B被解释为被解释为 y(yy),假假 原因原因:在在A中中x自由出现自由出现在在 y辖域辖域F(x,y)内内反例反例2.前提前提:P(x)Q(x),P(x)结论结论:xQ(x)取解释取解释I:个体域为个体域为Z,在在I下前提为下前提为真真,结论为假结论为假,从而推理不正确从而推理不正确26第26页反例反例2(续续)“证实证实”:P(x)Q(x)前提引入前提引入 P(x)前提引入前提引入 Q(x)假言推理假言推理 xQ(x)+错误原因错误原因:在在使用使用+规则规则,而而x在前提公式中自由出现在前提公式中自由出现.27第27页第五章第五章 习题课习题课主要内容主要内容一阶逻辑等值式一阶逻辑等值式 基本等值式，置换规则、换名规则、代替规则基本等值式，置换规则、换名规则、代替规则前束范式前束范式推理形式结构推理形式结构自然推理系统自然推理系统NL 推理定律、推理规则推理定律、推理规则28第28页基本要求基本要求深刻了解并切记一阶逻辑中主要等值式深刻了解并切记一阶逻辑中主要等值式,并能准确而熟练并能准确而熟练地应用它们地应用它们熟练正确地使用置换规则、换名规则、代替规则熟练正确地使用置换规则、换名规则、代替规则熟练地求出给定公式前束范式熟练地求出给定公式前束范式深刻了解自然推理系统深刻了解自然推理系统NL 定义，切记定义，切记NL 中各条推理规则，中各条推理规则，尤其是注意使用尤其是注意使用、+、+、4条推理规则条件条推理规则条件能正确地给出有效推理证实能正确地给出有效推理证实 29第29页练习练习11.给定解释给定解释I以下以下:(1)个体域个体域D=2,3(2)(3)(4)求下述在求下述在I下解释及其真值下解释及其真值:x y(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)1 0(1 0)030第30页练习练习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(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)x y(F(x)(G(z,y)H(z,y)31第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第32页练习练习3(续续)(2)前提：前提：x(F(x)G(x),xG(x)结论：结论：xF(x)证实：用归谬法证实：用归谬法 xF(x)结论否定引入结论否定引入 x F(x)置换置换 xG(x)前提引入前提引入 x G(x)置换置换 x(F(x)G(x),前提引入前提引入 F(c)G(c)F(c)G(c)G(c)析取三段论析取三段论 G(c)G(c)合取引入合取引入 33第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第34页练习练习44.在自然推理系统在自然推理系统NL 中，结构推理证实中，结构推理证实 人都喜欢吃蔬菜但不是全部人都喜欢吃鱼所以人都喜欢吃蔬菜但不是全部人都喜欢吃鱼所以,存在存在喜欢吃蔬菜而不喜欢吃鱼人喜欢吃蔬菜而不喜欢吃鱼人解解 令令F(x):x为人，为人，G(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第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第36页