(1.4.2)--ch2—第三讲离散数学离散数学.pdf

离散数学离散数学 Discrete Mathematics 2-6 前束范式前束范式 1.前束范式前束范式(Prenex normal form)定义定义2.6.1.如果一个谓词公式的量词均在全式的开头如果一个谓词公式的量词均在全式的开头,它们的它们的 作用域延伸至整个公式的末尾作用域延伸至整个公式的末尾,则该公式叫做则该公式叫做前束范式前束范式.前束范式记为前束范式记为:(v1)(v2)(vn)A.其中其中可能是量词可能是量词 或量词或量词,vi(i=1,n)是客体变元是客体变元，A是是不含量词不含量词的的谓词公式谓词公式.例例 (x)(y)(F(x)G(y)H(x,y)(x)(y)(F(x,y)G(y,z)(x)H(x,y,z)定理定理2.6.1 任何一个谓词公式均和一个前束范式等价任何一个谓词公式均和一个前束范式等价.例例1.求公式求公式(x)P(x)(x)Q(x)的前束范式的前束范式.解解.原式原式 (x)P(x)(x)Q(x)(x)P(x)(x)Q(x)(x)(P(x)Q(x)例例2.求求(x)(y)(z)(P(x,z)P(y,z)(u)Q(x,y,u)的前束范式的前束范式 解解.原式原式(x)(y)(z)(P(x,z)P(y,z)(u)Q(x,y,u)(x)(y)(z)(u)P(x,z)P(y,z)Q(x,y,u)(x)(y)(z)(P(x,z)P(y,z)(u)Q(x,y,u)(x)(y)A(x,y)(x)(y)B(x,y)(y)(A(y,x)B(x,y)例例3.把下面公式转化为前束范式把下面公式转化为前束范式 解解.原式原式(x)(y)A(x,y)(x)(y)B(x,y)(y)(A(y,x)B(x,y)(x)(y)A(x,y)(x)(y)B(x,y)(y)(A(y,x)B(x,y)(x)(y)A(x,y)(u)(v)B(u,v)(z)(A(z,u)B(u,z)(x)(y)A(x,y)(u)(v)(z)B(u,v)(A(z,u)B(u,z)(x)(y)(u)(v)(z)A(x,y)B(u,v)(A(z,u)B(u,z)前束范式的求法前束范式的求法:(1)消去谓词公式中的联结词消去谓词公式中的联结词和和.(2)消去消去;(5)量词前移量词前移.利用量词辖域的扩张与收缩律把量词移到前面利用量词辖域的扩张与收缩律把量词移到前面.(3)否定深入否定深入.将联接词将联接词 向内深入向内深入,使之只作用于原子式使之只作用于原子式.(4)利用换名和代入规则更换一些变元的名称以便消除混乱利用换名和代入规则更换一些变元的名称以便消除混乱.练习练习.求求(x)P(x)(y)Q(y)(x)R(x)的前束范式的前束范式.解解.原式原式 (x)P(x)(y)Q(y)(x)R(x)(x)(y)(z)(P(x)Q(y)R(z)(x)P(x)(y)Q(y)(z)R(z)(x)P(x)(y)Q(y)(x)R(x)(x)(y)(P(x)Q(y)(z)R(z)2.前束析取范式和前束合取范式前束析取范式和前束合取范式 定义定义2.6.2:一个谓词公式一个谓词公式 A,如果具有如下形式则称为如果具有如下形式则称为 前束合取范式前束合取范式(x1)(x2)(xn)(A11A12A1k1)(A21A22A2k2)(Am1Am2Amkm)其中其中可能是量词可能是量词 或量词或量词,xi(i=1，n)是客体变元是客体变元，Aij 是是原子谓词公式或其否定原子谓词公式或其否定.定理定理2.6.2.每个谓词公式都可转化为与其等价的前束合取范式每个谓词公式都可转化为与其等价的前束合取范式.例例4.将公式将公式(x)(y)P(x)(z)Q(z,y)(y)R(x,y)化为化为前束合取范式前束合取范式.解解:记原式为记原式为D,(1)取消多余量词取消多余量词 D(x)P(x)(z)Q(z,y)(y)R(x,y)(2)消去消去“”D(x)P(x)(z)Q(z,y)(y)R(x,y)(3)深入深入 D(x)(P(x)(z)Q(z,y)(y)R(x,y)(4)换名换名 D(x)(P(x)(z)Q(z,y)(w)R(x,w)(5)量词前移量词前移 D(x)(z)(w)(P(x)Q(z,y)R(x,w)(6)分配律分配律 D(x)(z)(w)(P(x)R(x,w)(Q(z,y)R(x,w)定义定义2.6.3.一个谓词公式一个谓词公式 A,如果具有如下形式如果具有如下形式,则则 称为称为前束析取范式前束析取范式:(x1)(x2)(xn)(A11A12A1k1)(A21A22A2k2)(Am1Am2Amkm)其中其中可能是量词可能是量词 或量词或量词,xi(i=1，n)是客体变元是客体变元，Aij 是是原子谓词公式或其否定原子谓词公式或其否定.定理定理2.6.3.每个谓词公式都可转化为与其等价的前束析取范式每个谓词公式都可转化为与其等价的前束析取范式.在谓词演算中在谓词演算中,推理的形式结构仍为推理的形式结构仍为 H1 H2 H3.HnC 若若 H1 H2 H3.Hn C是永真式是永真式,则称则称 由前提由前提 H1,H2,H3,.,Hn逻辑推出结论逻辑推出结论C,但在谓词逻辑中但在谓词逻辑中,H1,H2,H3,.,Hn,C 均为谓词公式均为谓词公式 2-7 谓词演算的推理理论谓词演算的推理理论 1.全称指定规则全称指定规则(US)(x)P(x)P(c)c为为任意的不在任意的不在P(x)中出现过的客体常元中出现过的客体常元;含义含义:(x)A(x)成立成立,可推出任意一个确定的可推出任意一个确定的c,使使A(c)成立成立.例如例如,设个体域为全体偶数的集合设个体域为全体偶数的集合,P(x):“x 是整数”是整数”,则则(x)P(x)表示表示“所有的偶数都是整数”所有的偶数都是整数”则由则由全称指定规则得到结论全称指定规则得到结论P(6)即即“6是整数是整数”2.7.1.推理规则推理规则(Rules of inference)作用作用:去掉全称量词去掉全称量词 一般一般特殊特殊(具体具体)的推演的推演 2.全称推广规则全称推广规则(UG):(y)P(y)P(x)此规则是要对命题量化此规则是要对命题量化,如果能够证明对个体域中的每个如果能够证明对个体域中的每个 客体客体 c,P(c)都成立都成立.根据此规则可得到结论根据此规则可得到结论(x)P(x)成立成立.例如例如,设个体域为全体人类设个体域为全体人类,P(x):“x 是要死的”是要死的”,显然显然,对于任意一个人对于任意一个人 a,P(a)都成立都成立,即任何人都是要死的即任何人都是要死的.则应用则应用全称推广规则有全称推广规则有(y)P(y).使用此规则时注意使用此规则时注意:(1)x在在P(x)中自由出现中自由出现,且且 x取任何值时取任何值时P 均为真均为真.(2)y不在不在P(x)中约束出现中约束出现.特殊特殊(具体具体)一般的推演一般的推演 作用作用:添加添加全称量词全称量词 例例 设个体域设个体域 D 为实数集为实数集,取取 F(x,y):xy,则对任意给定的则对任意给定的x,P(x)=(y)F(x,y)是真命题是真命题.但但(y)P(y)=(y)(y)(yy)是假命题是假命题.出错的原因是违背了条件出错的原因是违背了条件2.若取若取 z 取代取代 x,得得(z)P(z)=(z)(y)(zy)是真命题是真命题.3.存在指定规则存在指定规则(ES)P(c)(x)P(x)这里这里c 是个体域中是个体域中某些某些客体客体,c 并不是任意的并不是任意的.使用此规则时应注意：使用此规则时应注意：(1)c是使是使P为真的特定的客体常元；为真的特定的客体常元；(2)c 不在不在P(x)中出现中出现.(3)如果如果P(x)中有其他自由变元出现中有其他自由变元出现,那么不能使用此规则那么不能使用此规则.作用作用:去掉去掉存在量词存在量词 4.存在推广规则存在推广规则(EG)(x)P(x)P(c)此规则比较显然此规则比较显然,即当对某个客体即当对某个客体 c,P(c)为真为真,则在个体域则在个体域 中必有中必有(x)P(x)为真为真.使用此规则时注意使用此规则时注意:(1)c 是个体域中某个确定的是个体域中某个确定的客客体体.(2)代替代替c的的 x不能已在不能已在P(c)中出现中出现.作用作用:添加添加存在量词存在量词 例例 在实数集中在实数集中,取取 F(x,y):x y,并取并取 P(3)=(x)F(x,3),P(3)为真命题为真命题.在使用上式在使用上式,若用若用x取代取代 3,则得到则得到(x)P(x)=(x)(x)F(x,x)=(x)(x x)这是假命题这是假命题*其原因是违背了条件其原因是违背了条件(2)此时若用此时若用P(3)中未出现过的客体变项中未出现过的客体变项 y 取代取代 3,得得(y)P(y)=(y)(x)F(x,y)=(y)(x)(x y)量词四个规则使用时注意问题量词四个规则使用时注意问题 1.ES,US,EG,UG 四条规则都只有四条规则都只有在在量词的作用域是量词的作用域是整个公整个公式式的情况下才能使用的情况下才能使用.3.添加量词时添加量词时,要加在公式的最左边要加在公式的最左边,(即新加的量词前也无即新加的量词前也无任何符号任何符号!)且其辖域作用到公式的末尾且其辖域作用到公式的末尾.2.去量词时去量词时,该量词必须是公式的最左边的量词该量词必须是公式的最左边的量词,且此量词且此量词的前边的前边无任何符号无任何符号,它的辖域作用到公式末尾它的辖域作用到公式末尾.4.US、ES和和EG、UG的使用的使用 US(全称指定全称指定)UG(全称推广全称推广)EG(存在推广存在推广)消去量词消去量词 添加量词添加量词 ES(存在指定存在指定)EG(存在推广存在推广)添加量词添加量词 消去量词消去量词 5.指定为同一变元指定为同一变元,先先ES(存在指定存在指定)再再US(全称指定全称指定)ES(x)A(x)A(c)(y)B(y)US B(c)US(x)A(x)A(c)(y)B(y)ES B(c)6.多次使用多次使用ES 规则规则,使用一次更改一个变元使用一次更改一个变元.ES(x)A(x)A(c)(y)B(y)ES B(c)ES(x)A(x)A(c)(y)B(y)ES B(d)7.多次使用多次使用US规则规则,可以使用同一个常量可以使用同一个常量.US(x)A(x)A(c)(y)B(y)US B(c)谓词演算的推理方法谓词演算的推理方法 1.命题逻辑中的命题逻辑中的P,T,CP规则和反证法规则和反证法,都可以引用到谓词逻都可以引用到谓词逻辑的推导过程中辑的推导过程中,不过要注意对量词做适当处理；不过要注意对量词做适当处理；2.对消去量词的公式或公式中不含量词的子公式对消去量词的公式或公式中不含量词的子公式,可以引用可以引用命题演算中命题演算中的基本等价公式和基本蕴含公式的基本等价公式和基本蕴含公式.3.对含有量词的公式对含有量词的公式可以引用可以引用谓词中的谓词中的基本等价公式和基本基本等价公式和基本蕴含公式蕴含公式.4.在推理过程中在推理过程中,带量词的谓词公式只能使用带量词的谓词公式只能使用P70表表2-5.1所所列的蕴含式和等价式列的蕴含式和等价式,除表中所列的带量词公式外除表中所列的带量词公式外,一般一般不能在不能在量词后面的辖域内进行蕴含推论或等价变换量词后面的辖域内进行蕴含推论或等价变换.如如 (x)(A(x)B(x)(x)(A(x)B(x)但在推理中不能作为公式引用但在推理中不能作为公式引用,只有通过只有通过US或或ES消除量词后进消除量词后进行蕴含或等价推论行蕴含或等价推论,而后用而后用UG或或EG规则引入量词规则引入量词,以完成带量以完成带量词公式的逻辑推证词公式的逻辑推证.例例1.试证明下面苏格拉底论证试证明下面苏格拉底论证:所有人都是要死的，所有人都是要死的，苏格拉底是人，苏格拉底是人，因此，苏格拉底是要死的因此，苏格拉底是要死的 2.7.2.谓词逻辑中的推理实例谓词逻辑中的推理实例 推理方法推理方法:推理规则推理规则:T规则、规则、P规则和规则和CP规则规则,已知的等价式，已知的等价式，蕴涵式及有关量词的消去和产生规则蕴涵式及有关量词的消去和产生规则 直接证明法直接证明法和和间接证明法间接证明法(1)(x)(M(x)D(x)P 证明证明 令令M(x):x是人是人,D(x):x是要死的是要死的,S:苏格拉底苏格拉底,原题可符号化为原题可符号化为(x)(M(x)D(x),M(S)D(S)(4)D(S)T(2),(3)I(3)M(S)P,(2)M(S)D(S)US(1)例例2.前提前提:(x)(C(x)W(x)R(x),(x)(C(x)Q(x)结论结论:(x)(Q(x)R(x)证明证明(1)(x)(C(x)Q(x)P(2)C(a)Q(a)ES(1)(3)(x)(C(x)W(x)R(x)P(4)C(a)W(a)R(a)US(3)(6)W(a)R(a)T(4)(5),I (7)R(a)T(5),(8)Q(a)T(2),I(9)Q(a)R(a)T(7)(8),I(10)(x)(Q(x)R(x)EG(5)C(a)T(2),I 练习练习.前提前提:(x)(A(x)B(x),(x)A(x)结论：结论：(x)B(x)证明证明(1)(x)A(x)P(2)A(c)ES(1)(3)(x)(A(x)B(x)P(4)A(c)B(c)US(3)(5)B(c)T(2)(4)(6)(x)B(x)EG 注意：注意：引入的顺序不可更改引入的顺序不可更改！例例3.证明证明:(x)(P(x)Q(x)(x)P(x)(x)Q(x)证法证法1:(4)(x)P(x)T(3),E(3)(x)(P(x)T(2),I(2)(x)(P(x)(x)Q(x)T(1),E(1)(x)P(x)(x)Q(x)P(附加前提附加前提)(5)P(c)ES(4),I(6)(x)(P(x)Q(x)P(7)P(c)Q(c)US(6)(8)Q(c)T(5)(7),I (9)(x)Q(x)T(2),I(10)(x)Q(x)T(2),I(11)Q(c)US(11)(12)Q(c)Q(c)T(8)(11)例例3.证明证明:(x)(P(x)Q(x)(x)P(x)(x)Q(x)证法证法2：(1)(x)P(x)P(附加前提附加前提)(2)(x)P(x)T(1)E(3)P(c)ES(2)(4)(x)(P(x)Q(x)P(5)P(c)Q(c)US(4)(6)Q(c)T(3)(5)I(7)(x)Q(x)EG(6)(8)(x)P(x)(x)Q(x)CP 练习练习.前提前提:(x)(A(x)B(x),(x)(B(x)C(x),(x)C(x)结论结论:(x)A(x)(1)(x)(A(x)B(x)P(2)A(a)B(a)ES(1)(3)(x)(B(x)C(x)P(4)B(a)C(a)US(3)(5)(x)C(x)P(6)C(a)US(5)(7)B(a)T(4)(6)I(8)A(a)T(2)(7)I(9)(x)A(x)EG(8)证明证明.例例4 前提前提：(x)(y)(S(x,y)M(y)(z)(P(z)R(x,z)结论结论：(z)P(z)(x)(y)(S(x,y)M(y)(1)(x)(y)(S(x,y)M(y)(z)(P(z)R(x,z)P(2)(y)(S(b,y)M(y)(z)(P(z)R(b,z)US(1)(3)(z)P(z)P(附加前提附加前提)(4)(z)P(z)T(3)E(5)P(a)US(4)(6)P(a)R(b,a)T(5)I(7)(z)(P(z)R(b,z)UG(6)(8)(z)(P(z)R(b,z)T(7)E(9)(y)(S(b,y)M(y)T(2)(8)I(10)(y)(S(b,y)M(y)T(9)E(11)(y)(S(b,y)M(y)T(10)E(12)(x)(y)(S(x,y)M(y)UG(11)(13)(z)P(z)(x)(y)(S(x,y)M(y)CP 例例4 前提前提：(x)(y)(S(x,y)M(y)(z)(P(z)R(x,z)结论结论：(z)P(z)(x)(y)(S(x,y)M(y)(1)(x)(y)(S(x,y)M(y)(z)(P(z)R(x,z)P(2)(y)(S(b,y)M(y)(z)(P(z)R(b,z)US(1)(3)(z)P(z)P(附加前提附加前提)(4)(z)P(z)T(3)E(5)P(a)US(4)(6)P(a)R(b,a)T(5)I(7)(P(a)R(b,a)T(6)I(8)(z)(P(z)R(b,z)UG(7)(9)(z)(P(z)R(b,z)T(8)E(10)(y)(S(b,y)M(y)T(2)(9)I(11)(y)(S(b,y)M(y)T(10)E(12)(S(b,c)M(c)US(11)(13)S(b,c)M(c)T(12)E(14)S(b,c)M(c)T(13)E(15)(y)(S(b,y)M(y)UG(14)(16)(x)(y)(S(b,y)M(y)UG(15)(17)(z)P(z)(x)(y)(S(x,y)M(y)CP 原来的原来的(7)、(8)原来的原来的(10)、(11)本节介绍了谓词公式的本节介绍了谓词公式的前束范式、前束前束范式、前束析取析取范式和前范式和前束束合取合取范式、范式、谓词演算的推理规则谓词演算的推理规则,并举例说明了它们并举例说明了它们的应用的应用.重点：掌握重点：掌握前束前束析取析取范式和前束范式和前束合取合取范式求法、范式求法、深刻深刻理解四个推理规则理解四个推理规则,会应用它们推理证明会应用它们推理证明.小小 结结