离散数学 5_2[2014_11_17]

主讲教师：常亮E-mail:[e-mail]：737059669办公室电话:2291071手机:[phone]辅导教师：周小川答疑时间：星期四上午10:20-11:50答疑地点：5教5楼软件工程教研室离散数学解释谓词逻辑中的合式公式是按照形成规则生成的符号串，没有实际的含义。只有将其中的变项(个体变项、谓词变项等)用指定的常项代替后，所得的公式才具有特定的实际含义。例.x(F(x)G(x))对个体域以及谓词F和G的含义分别指定如下：(1)个体域为全总个体域，F(x)表示“x是人”，G(x)表示“x是黄种人”，则：“所有人都是黄种人”假命题(2)个体域为实数集合，F(x)表示“x是自然数”，G(x)表示“x是整数”，则：“所有自然数都是整数”真命题解释一个解释由4个部分构成：（1）非空的个体域D；（2）将每个个体常项符号a解释成D中的一个元素；（3）将每个n元函数符号f解释成D上的一个n元函数；（4）将每个n元谓词符号P解释为D上的一个n元谓词。afP例5.10对于谓词公式(x)(y)(z)A(f(x,z),y))，说明它在如下解释中的具体含义。解释I1：个体域D1={0,1,2,…}函词f(x,y)=x+y谓词A(x,y)：x=y解：在解释I1下，谓词公式的含义为：对于D1中所有的x和y，存在D1中的某个z使得x+z=y。该命题取值为假，所以I1是谓词公式的一个成假解释。解释I2：个体域D2为正有理数集合函词f(x,y)=xy谓词A(x,y)：x=y解：在解释I2下，谓词公式的含义为：对于D2中所有的x和y，存在D2中的z使得xz=y。该命题取值为真，所以I2是谓词公式的一个成真解释。例5.12给定解释I如下：（1）个体域D为非负整数集合；（2）个体常元a指定为2；（3）函词f(x,y)=x+y,g(x,y)=xy（4）谓词Q(x,y)指定为：x=y。在解释I下，讨论下列公式的真假值。(1)(x)Q(g(x,y),x)(2)(x)(y)(Q(f(x,a),y)Q(f(y,a),x))(3)(x)(y)(z)Q(f(x,y),z)(4)(x)Q(f(x,x),g(x,x))注意：在某些解释下，谓词公式不一定是一个命题，原因在于公式中含有自由变元。假命题真命题不是命题真命题5.2.2谓词公式的分类永真式（逻辑有效式）：谓词公式A在任何解释下均为真；永假式（不可满足式）：A在任何解释下均为假；可满足式：至少存在一个解释使A为真。5.2.3谓词公式的等值式等值：设A、B为任意谓词公式，若AB是永真式，则称A与B等值，记作AB。注意：不是联结词符号AB是表示AB为永真式的一种记法。如何判断两个公式是等值的命题逻辑真值表方法等值演算：由已知的等值式推演出新的等值式。关键：16组24个基本等值式(等值模式)谓词逻辑等值演算谓词逻辑中的等值演算基本等值式：第一组命题逻辑中的基本等值式+代换实例代换实例定义5.16设P是含有命题变元p1,p2,p3,…,pn的命题公式，A1,A2,A3,…,An是n个谓词公式；用谓词公式Ai(i=1,2,…,n)替换P中命题变元pi(i=1,2,…,n)的所有出现，所得到的谓词公式称为P的代换实例。例：对于命题公式pq，以下公式是否是其代换实例？(x)F(x)(y)G(y)(x)(F(x)(y)G(y))(x)(F(x)G(x))(x)(F(x)G(x))定理5.1重言式的代换实例是重言式，矛盾式的代换实例是矛盾式。例5.17判断下列谓词公式是否为等值式。(x)F(x)(x)G(x)和(x)F(x)(x)G(x)基本等值式(命题逻辑中等值式的推广)共16组，24个等幂律：(x)A(x)(x)A(x)(x)A(x)(x)A(x)(x)A(x)(x)A(x)(x)A(x)(x)A(x)(x)A(x)(x)A(x)(x)A(x)(x)A(x)排中律：(x)A(x)(x)A(x)1(x)A(x)(x)A(x)1矛盾律：(x)A(x)(x)A(x)0(x)A(x)(x)A(x)0基本等值式(命题逻辑中等值式的推广)双重否定律：交换律：结合律：分配律：德摩根律：吸收律：零律：同一律：蕴涵等值式：等价等值式：假言移位：等价否定等值式：归谬论：注意：双向的（尤其是分配律、德.摩根律的使用）谓词逻辑中的等值演算基本等值式：第一组命题逻辑中的基本等值式+代换实例第二大组量词消去律量词与否定的交换律量词辖域收缩与扩张律量词分配律双量词交换律量词消去律设个体域为有限集D={a1,a2,…,an}，有：(1)(x)A(x)A(a1)A(a2)...A(an)(2)(x)A(x)A(a1)A(a2)...A(an)注意：A代表任意一个公式；A(x)表示该公式中含有个体变元x。练习设个体域D={a,b,c}，将下面公式中的量词消去。(1)x(F(x)G(x))(2)xyF(x,y)(3)x(F(x)yG(y))量词与否定的交换律(1)(x)A(x)(x)A(x)(2)(x)A(x)(x)A(x)注意：A代表任意一个公式；A(x)表示该公式中含有个体变元x。量词辖域收缩与扩张律如果个体变元x没有在B中出现，则：①(x)(A(x)B)(x)A(x)B②(x)(A(x)B)(x)A(x)B③(x)(A(x)B)(x)A(x)B④(x)(A(x)B)(x)A(x)B⑤(x)(A(x)B)(x)A(x)B⑥(x)(BA(x))B(x)A(x)⑦(x)(A(x)B)(x)A(x)B⑧(x)(BA(x))B(x)A(x)注意：A、B都代表任意一个公式；A(x)表示该公式中含有个体变元x。量词分配律①(x)A(x)(x)B(x)(x)(A(x)B(x))②(x)A(x)(x)B(x)(x)(A(x)B(x))③(x)A(x)(x)B(x)(x)(y)(A(x)B(y))④(x)A(x)(x)B(x)(x)(y)(A(x)B(y))⑤(x)(A(x)B(x))(x)A(x)(x)B(x)注意：A、B都代表任意一个公式；A(x)表示该公式中含有个体变元x；B(x)表示该公式中含有个体变元x。双量词交换律①(x)(y)P(x,y)(y)(x)P(x,y)②(x)(y)P(x,y)(y)(x)P(x,y)注意：P都代表任意一个公式；P(x,y)表示该公式中含有个体变元x，y。谓词逻辑中的等值演算基本等值式：第一组命题逻辑中的基本等值式+代换实例第二组量词消去律量词与否定的交换律量词辖域收缩与扩张律量词分配律双量词交换律演算规则：置换规则换名规则代替规则置换规则置换规则：设(A)是含有公式A的公式，(B)是用公式B置换(A)中所有的A之后得到的公式；那么，若AB,则(B)(A)。例：x(A(x)B(x))因为A(x)B(x)A(x)B(x)所以x(A(x)B(x))x(A(x)B(x))换名规则换名规则：将某个量词辖域中一个约束变元的所有出现以及相应的指导变项，改变成另一个在辖域中未曾出现过的个体变项符号，公式中其余部分不变，则所得公式与原公式是等值的。例：对如下公式进行换名操作，使每个个体变项在公式中只以一种形式出现。x(P(x,y)yQ(x,y,z))S(x,z)x(P(x,y)yQ(x,y,z))S(x,z)u(P(u,y)yQ(u,y,z))S(x,z)u(P(u,y)vQ(u,v,z))S(x,z)代替规则代替规则：对公式中某个自由出现的个体变项，用与原公式中所有个体变项符号均不同的个体变项符号去代替，代替时必须处处代替，所得公式与原公式是等值的。例：对如下公式进行代替操作，使每个个体变项在公式中只以一种形式出现。x(P(x,y)yQ(x,y,z))S(x,z)x(P(x,y)yQ(x,y,z))S(x,z)x(P(x,y)yQ(x,y,z))S(t,z)x(P(x,w)yQ(x,y,z))S(t,z)练习将下面公式化为等值的公式，使其中不含既是约束出现又是自由出现的个体变项。xF(x,y,z)yG(x,y,z)方法一：采用换名规则方法二：采用代替规则谓词逻辑中的等值演算基本等值式：第一组命题逻辑中的基本等值式+代换实例第二组量词消去律量词与否定的交换律量词辖域收缩与扩张律量词分配律双量词交换律演算规则：置换规则换名规则代替规则例证明下列各等值式。(1)(x)(A(x)B(x))(x)(A(x)B(x))证明：(x)(A(x)B(x))(x)(A(x)B(x))(x)(A(x)B(x))(x)(A(x)B(x))证毕。例证明下列各等值式。(2)(x)(y)(A(x)B(y)P(x,y))(x)(y)(A(x)B(y)P(x,y))证明:(x)(y)(A(x)B(y)P(x,y))(x)(y)(A(x)B(y)P(x,y))(x)(y)(A(x)B(y)P(x,y))(x)(y)((A(x)B(y))P(x,y))(x)(y)((A(x)B(y))P(x,y))(x)(y)(A(x)B(y)P(x,y))证毕。练习证明下列各等值式。(1)x(M(x)F(x))x(M(x)F(x))(2)xy(F(x)G(y)H(x,y))xy(F(x)G(y)H(x,y))注意注意：(1)x(F(x)G(x))⇎xF(x)xG(x)(2)x(F(x)G(x))⇎xF(x)xG(x)对比：量词分配等值式(1)x(A(x)B(x))xA(x)xB(x)(2)x(A(x)B(x))xA(x)xB(x)结论：x对不满足分配律x对不满足分配律5.2.4谓词公式的范式定义5.17对于谓词公式G，如果G具有如下形式：(Q1x1)(Q2x2)…(Qnxn)M(x1,x2,...,xn)其中Qi(i=1,2,…,n)为量词或，M(x1,x2,...,xn)中不含有量词；则称G为谓词公式的前束范式，简称前束范式，称M(x1,x2,...,xn)为G的母式。例：xy(F(x)Q(y)H(x,y))xyz(F(x)Q(y)H(z)L(x,y,z))x(F(x)Q(y)yH(x,y))x(F(x)Q(y)y(H(z)zL(x,y,z)))√××√前束范式定理5.2任意谓词公式都存在与之等值的前束范式注意：谓词公式的前束范式不唯一（例5.23）。对于任意谓词公式G，可通过下述步骤将其转化为与之等值的前束范式：（1）消去谓词公式中的联结词“”、“”；（2）运用量词否定律，将移到原子谓词公式的前端；（3）进行换名和代替过程，使每个变元都只以一种方式出现；（4）通过量词辖域收缩与扩张律以及量词分配律将所有量词移到公式的前端。例5.22求下列谓词公式的前束范式。(1)(x)A(x)(x)B(x)(x)A(