离散数学(一阶逻辑等值演算与推理)课件

5.1 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则o定义定义5.1 设设A,B是两个谓词公式是两个谓词公式,如果如果AB是永真式是永真式,则称则称A与与B等值等值,记作记作AB,并称并称AB是是等值式等值式.o由定义显然可以看出：公式由定义显然可以看出：公式A，B等值的充等值的充要条件是：对要条件是：对A，B的任意解释的任意解释I，A，B在在I下的真值相同。下的真值相同。o因为对任意公式因为对任意公式A，B，在解释，在解释I下，下，A，B就就是两个命题，所以命题逻辑中给出的基本等是两个命题，所以命题逻辑中给出的基本等价式，在谓词逻辑中仍然成立。价式，在谓词逻辑中仍然成立。1基本等值式基本等值式o第一组第一组 命题逻辑中命题逻辑中16组基本等值式的代换组基本等值式的代换实例实例 例如，例如，xF(x)xF(x),xF(x)yG(y)xF(x)yG(y)等等o判断下列公式的类型：判断下列公式的类型：（1）xP(x)(x yQ(x,y)xP(x)（2）xP(x)(xP(x)yG(y)（3）(P(x,y)Q(x,y)Q(x,y)永真式永真式永真式永真式矛盾式矛盾式2基本等值式基本等值式o第二组第二组 (1)消去量词等值式消去量词等值式 设设D=a1,a2,an xA(x)A(a1)A(a2)A(an)xA(x)A(a1)A(a2)A(an)设个体域设个体域 A=a,b,公式公式(x)P(x)(x)S(x)在在A上消去量词后应为上消去量词后应为:例例P(a)P(b)(S(a)S(b)3基本等值式基本等值式(2)量词否定等值式量词否定等值式 xA(x)x A(x)xA(x)x A(x)例例设论域为人，设论域为人，P(x):x来上课，来上课，P(x):x没来上课没来上课 xP(x):所有人都来上课所有人都来上课xP(x):不是所有人都来上课不是所有人都来上课 x P(x):有人没来上课有人没来上课 xP(x):有人来上课有人来上课xP(x):没有人来上课没有人来上课 x P(x):所有人都没来上课所有人都没来上课4 xA(x)x A(x)的证明的证明o对于任意给定的解释对于任意给定的解释I，若，若I使使xA(x)为真，为真，则则I使使 xA(x)为假。则必有某一个为假。则必有某一个x0 D，A(x0)是假命题，于是是假命题，于是 A(x0)是真命题，即是真命题，即 x A(x)在在I下是真命题，故下是真命题，故I使使 x A(x)为真。为真。o若若I使使xA(x)为假，则为假，则I使使 xA(x)为真。即为真。即对任意的对任意的x D，有，有A(x)是真命题。也就是对是真命题。也就是对任意的任意的x D，A(x)是假命题，于是是假命题，于是 x A(x)是假命题，故是假命题，故I使使 x A(x)为假。为假。5实例实例o例例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实例实例(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量词否定等值式（续）量词否定等值式（续）设个体域中的客体变元为设个体域中的客体变元为a1,a2,an，则，则8基本等值式基本等值式o(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)9 x(A(x)B)xA(x)B的证明的证明o设设I是是A(x)和和B的一个解释。若的一个解释。若 x(A(x)B)在在I下取下取1值，则在值，则在I下，对任意下，对任意x D，A(x)B都是真命题。若都是真命题。若B是真命题，则是真命题，则 xA(x)B是是真命题；若真命题；若B是假命题，则必然是对每个是假命题，则必然是对每个x D，A(x)都是真命题，故都是真命题，故 xA(x)取取1值。值。所以所以 xA(x)B在在I下取下取1值。值。o若若 x(A(x)B)在在I下取下取0值，则必有一个值，则必有一个x0 D，使，使A(x0)B在在I下取下取0值。故值。故A(x0)为假命题，为假命题，并且并且B为假命题。所以为假命题。所以 xA(x)取取0值。从而值。从而 xA(x)B在在I下取下取0值。值。10基本等值式基本等值式 关于存在量词的：关于存在量词的：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)11 x(A(x)B)xA(x)B的证明的证明o设设I是是A(x)和和B的一个解释。若的一个解释。若 x(A(x)B)在在I下取下取1值，则在值，则在I下，存在下，存在x0 D，A(x0)B是真命题。若是真命题。若B是真命题，则是真命题，则 xA(x)B是真是真命题；若命题；若B是假命题，则必然有是假命题，则必然有A(x0)是真命是真命题，故题，故 xA(x)取取1值。所以值。所以 xA(x)B在在I下下取取1值。值。o若若 x(A(x)B)在在I下取下取0值，则在值，则在I下对任意下对任意的的x D，使，使A(x)B在在I下取下取0值。故值。故A(x)和和B都都为假命题，所以为假命题，所以 xA(x)B在在I下取下取0值。值。12基本等值式基本等值式o(4)量词分配等值式量词分配等值式 x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)注意：注意：对对，对对 无分配律无分配律13 x(A(x)B(x)xA(x)xB(x)o设设I是是A(x)和和B(x)的一个解释。若的一个解释。若 xA(x)xB(x)在在I下取下取1值，则在解释值，则在解释I下，下，对任意对任意x D，A(x)、B(x)都是真命题，所以都是真命题，所以A(x)B(x)是真命题，即对任意是真命题，即对任意x D，A(x)B(x)是真命题，所以是真命题，所以 x(A(x)B(x)在在I下取下取1值。值。o若若 xA(x)xB(x)在在I下取下取0值，则值，则 xA(x)为为假，或假，或 xB(x)为假，若为假，若 xA(x)为假，必有一为假，必有一个个x0 D，使，使A(x0)在在I下取下取0值，所以值，所以A(x0)B(x0)为假命题，所以为假命题，所以 x(A(x)B(x)在在I下取下取0值。值。若若 xB(x)为假，同理可证。为假，同理可证。14置换规则、换名规则、代替规则置换规则、换名规则、代替规则o1.置换规则：置换规则：设设(A)是含是含A的公式的公式,那么那么,若若AB,则则(A)(B).o2.换名规则：换名规则：设设A为一公式，将为一公式，将A中某量词辖中某量词辖域中个体变项的所有约束出现及相应的指导域中个体变项的所有约束出现及相应的指导变元换成该量词辖域中未曾出现过的个体变变元换成该量词辖域中未曾出现过的个体变项符号，其余部分不变，设所得公式为项符号，其余部分不变，设所得公式为A，则，则AA.o3.代替规则：代替规则：设设A为一公式，将为一公式，将A中某个个体中某个个体变项的所有自由出现用变项的所有自由出现用A中未曾出现过的个中未曾出现过的个体变项符号代替，其余部分不变，设所得体变项符号代替，其余部分不变，设所得 公式为公式为A，则，则AA.15约束变元的换名约束变元的换名约束变元的换名规则：约束变元的换名规则：1)换名范围换名范围:量词中的指导变元和作用域中出量词中的指导变元和作用域中出现的该变元现的该变元.公式中其余部分不变公式中其余部分不变.2)要换成作用域中没有出现的变元名称要换成作用域中没有出现的变元名称.例：例：16自由变元的代替自由变元的代替自由变元代替的规则：自由变元代替的规则：1)对该自由变元每一处进行代替对该自由变元每一处进行代替.2)代替的变元与原公式中所有变元名称不能相代替的变元与原公式中所有变元名称不能相同同.例：例：17实例实例o例例2 将公式化成等值的不含既有约束出现、将公式化成等值的不含既有约束出现、又有自由出现的个体变项又有自由出现的个体变项:x(F(x,y,z)yG(x,y,z)o解解 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)辖域扩张等值式辖域扩张等值式18实例实例o例例3 设个体域设个体域D=a,b,c,消去下述公式中的量词消去下述公式中的量词:(1)x y(F(x)G(y)(2)x yF(x,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)19实例实例解法二解法二 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)20实例实例(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)215.2 一阶逻辑前束范式一阶逻辑前束范式o定义定义5.2 设设A为一个一阶逻辑公式，若为一个一阶逻辑公式，若A具有如具有如下形式下形式 Q1x1Q2x2QkxkB则称则称A为为前束范式前束范式，其中其中Qi(1 i k)为为 或或，B为不含量词的公式为不含量词的公式.o例如，例如，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)不是前束范式，不是前束范式，22前束范式存在定理前束范式存在定理o定理定理5.1（前束范式存在定理）：（前束范式存在定理）：一阶逻辑中一阶逻辑中的任何公式都存在与之等值的前束范式的任何公式都存在与之等值的前束范式o例例4 求下列公式的前束范式求下列公式的前束范式 (1)x(M(x)F(x)o解解 x(M(x)F(x)x(M(x)F(x)（量词否定等值式）（量词否定等值式）x(M(x)F(x)o后两步结果都是前束范式，说明公式的前束范后两步结果都是前束范式，说明公式的前束范式不惟一式不惟一.23求前束范式的实例求前束范式的实例(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)辖域收缩扩张规则辖域收缩扩张规则24求前束范式的实例求前束范式的实例(3)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)辖域收缩辖域收缩 扩张规则扩张规则或或 xF(x)y(G(z,y)H(y)代替规则代替规则 x y(F(x)(G(z,y)H(y)25求前束范式的实例求前束范式的实例26求前束范式的实例求前束范式的实例27求前束范式的实例求前束范式的实例28求前束范式的实例求前束范式的实例1.否定深入。否定深入。2.改名，把量词提到前面。改名，把量词提到前面。29Skolem范式范式o设设G是一个公式，是一个公式，Q1x1QnxnM是与是与G等价的等价的前束范式，其中前束范式，其中M为合取范式形式。若为合取范式形式。若Qr是是存在量词，并且它左边没有全称量词，则取存在量词，并且它左边没有全称量词，则取异于出现在异于出现在M中所有常量符号的常量符号中所有常量符号的常量符号c，并用，并用c代替代替M中所有的中所有的xr，然后在首标中删，然后在首标中删除除Qrxr。o若若Qs1,Qsm是所有出现在是所有出现在Qrxr左边的全称左边的全称量词量词(m 1，1 s1s2smy，x yF(x,y)为真命题。为真命题。o“证明证明”x yF(x,y)前提引入前提引入 yF(y,y)-o结论为假命题。结论为假命题。o原因：在原因：在 yF(x,y)中中x自由出现在自由出现在 y的辖域的辖域F(x,y)内内39全称量词引入规则全称量词引入规则2.全称量词引入规则全称量词引入规则(+)其中其中x是个体变项符号是个体变项符号,且不在前提的任何公且不在前提的任何公式中自由出现式中自由出现 A(x)xA(x)40重要提示重要提示o反例反例2：设个体域为整数集合：设个体域为整数集合Z，P(x):x是偶是偶数，数，Q(x):x能被能被2整除，则整除，则P(x)Q(x)为真命为真命题，题，P(x)真值不定，真值不定，xQ(x)为假命题。为假命题。o“证明证明”:P(x)Q(x)前提引入前提引入 P(x)前提引入前提引入 Q(x)假言推理假言推理 xQ(x)+o错误原因错误原因:在在使用使用+规则规则,而而x在前提的公在前提的公式中自由出现式中自由出现.41存在量词消去规则存在量词消去规则3.存在量词消去规则存在量词消去规则(-)其中其中x是个体变项符号是个体变项符号,且不在前提的任何公且不在前提的任何公式和式和B中自由出现中自由出现 A(x)BxA(x)B42重要提示重要提示o反例反例3：取个体域为整数集合：取个体域为整数集合Z，A(y)：y5，显然，显然A(y)A(y)为真命题。为真命题。o“证明证明”A(y)A(y)前提引入前提引入 yA(y)A(y)-xA(x)A(y)换名换名o产生错误的原因是产生错误的原因是y在蕴涵式的后件中自由在蕴涵式的后件中自由出现。出现。43存在量词引入规则存在量词引入规则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)44重要提示重要提示o反例反例4：取个体域为整数集合取个体域为整数集合Z，B(x,y):xy,y xB(x,y)为真命题。为真命题。“证明证明”:y xB(x,y)前提引入前提引入 xB(x,y)-x xB(x,x)+xB(x,x)置换置换o得到一个假命题，原因是得到一个假命题，原因是y在在 x的辖域内自的辖域内自由出现。由出现。45自然推理系统自然推理系统NLo定义定义5.3 自然推理系统自然推理系统NL 定义如下定义如下:1.字母表字母表.同一阶语言同一阶语言L 的字母表的字母表2.合式公式合式公式.同同L 的合式公式的合式公式3.推理规则推理规则:(1)前提引入规则前提引入规则(2)结论引入规则结论引入规则(3)置换规则置换规则(4)假言推理规则假言推理规则(5)附加规则附加规则(6)化简规则化简规则(7)拒取式规则拒取式规则46自然推理系统自然推理系统NL(8)假言三段论规则假言三段论规则(9)析取三段论规则析取三段论规则(10)构造性二难推理规则构造性二难推理规则(11)合取引入规则合取引入规则(12)-规则规则(13)+规则规则(14)-规则规则(15)+规则规则推理的证明推理的证明47构造推理证明的实例构造推理证明的实例o例例5 在自然推理系统在自然推理系统NL 中构造下面推理的证中构造下面推理的证明明,取个体域取个体域R:任何自然数都是整数任何自然数都是整数.存在存在自然数自然数.所以所以,存在整数存在整数.o解解 设设F(x):x是自然数是自然数,G(x):x是整数是整数.前提前提:x(F(x)G(x),xF(x)结论结论:xG(x)48构造推理证明的实例构造推理证明的实例证明证明:x(F(x)G(x)前提引入前提引入 F(x)G(x)-F(x)xG(x)+xF(x)xG(x)-xF(x)前提引入前提引入 xG(x)假言推理假言推理49构造推理证明的实例构造推理证明的实例o例例6 在自然推理系统在自然推理系统NL 中构造下面推理的证中构造下面推理的证明明,取个体域取个体域R:不存在能表示成分数的无理不存在能表示成分数的无理数数.有理数都能表示成分数有理数都能表示成分数.所以所以,有理数都不是无理数有理数都不是无理数.o解解:设设F(x):x是无理数是无理数,G(x):x是有理数是有理数,H(x):x能表示成分数能表示成分数.前提前提:x(F(x)H(x),x(G(x)H(x)结论结论:x(G(x)F(x)50构造推理证明的实例构造推理证明的实例证明证明:x(F(x)H(x)前提引入前提引入 x(F(x)H(x)置换置换 x(F(x)H(x)置换置换 F(x)H(x)-x(G(x)H(x)前提引入前提引入 G(x)H(x)-H(x)F(x)置换置换 G(x)F(x)假言三段论假言三段论 x(G(x)F(x)+51第五章第五章 习题课习题课o一阶逻辑等值式一阶逻辑等值式n基本等值式，置换规则、换名规则、代替基本等值式，置换规则、换名规则、代替规则规则o前束范式前束范式o推理的形式结构推理的形式结构o自然推理系统自然推理系统NLn推理定律、推理规则推理定律、推理规则52基本要求基本要求o深刻理解并牢记一阶逻辑中的重要等值式深刻理解并牢记一阶逻辑中的重要等值式,并并能准确而熟练地应用它们能准确而熟练地应用它们o熟练正确地使用置换规则、换名规则、代替熟练正确地使用置换规则、换名规则、代替规则规则o熟练地求出给定公式的前束范式熟练地求出给定公式的前束范式o深刻理解自然推理系统深刻理解自然推理系统NL 的定义，牢记的定义，牢记NL 中中的各条推理规则，特别是注意使用的各条推理规则，特别是注意使用、+、+、4条推理规则的条件条推理规则的条件o能正确地给出有效推理的证明能正确地给出有效推理的证明 53练习练习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)054练习练习2o2.求下述公式的前束范式求下述公式的前束范式:xF(x)y(G(x,y)H(x,y)o解解 使用换名规则使用换名规则,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)55练习练习2o使用代替规则使用代替规则 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)56练习练习3o3.构造下面推理的证明构造下面推理的证明:(1)前提：前提：x(F(x)G(x),xF(x)结论：结论：xG(x)o证明：证明：x(F(x)G(x)前提引入前提引入 F(y)G(y)xF(x)前提引入前提引入 F(y)G(y)假言推理假言推理 yG(y)+xG(x)置换置换57练习练习3（续）（续）(2)前提：前提：x(F(x)G(x),xG(x)结论：结论：xF(x)o证明：用归谬法证明：用归谬法 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)合取引入合取引入 58练习练习3（续）（续）(3)前提：前提：x(F(x)G(x),x(G(x)H(x)结论：结论：xF(x)xH(x)o证明证明:用附加前提法用附加前提法 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)+59练习练习4o4.在自然推理系统在自然推理系统NL 中，构造推理的证明中，构造推理的证明 人都喜欢吃蔬菜但不是所有的人都喜欢吃人都喜欢吃蔬菜但不是所有的人都喜欢吃鱼所以鱼所以,存在喜欢吃蔬菜而不喜欢吃鱼的存在喜欢吃蔬菜而不喜欢吃鱼的人人o解解 令令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)60练习练习4（续）（续）o证明：用归谬法证明：用归谬法(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)前提引入前提引入(6)F(y)G(y)(5)(7)F(y)F(y)H(y)(4)(6)假言三段论假言三段论61练习练习4(续续)(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)合取合取 62xiexie!xiexie!谢谢！谢谢！xiexie!xiexie!谢谢！谢谢！