计算机科学中的离散结构04(完成).doc

第4章 逻辑代数（下）-谓词演算 1、指出下列谓词公式中的量词及其辖域，指出各自由变元和约束变元，并回答它们是否是命题：（1）x(P(x)Q(x)R （R为命题常元） （2）x(P(x)Q(x)$xS(x)T(x) （3）x(P(x)$y(B(x,y)Q(y)T(y)（4）P(x)(y$x(P(x)B(x,y)P(x)解（1）全称量词，辖域 P(x)Q(x)，其中x为约束变元，x(P(x)Q(x)R是命题。（2）全称量词，辖域 P(x)Q(x)，其中 x为约束变元。存在量词$，辖域 S(x) ，其中 x为约束变元。T(x)中x为自由变元。x(P(x)Q(x)$xS(x)T(x)不是命题。（3）全称量词，辖域 P(x)$y(B(x,y)Q(y)T(y)，其中 x为约束变元，T(y)中y为自由变元。存在量词$，辖域B(x,y)Q(y)，其中y为约束变元。x(P(x)$y(B(x,y)Q(y)T(y)是命题。（4）全称量词，辖域$x(P(x)B(x,y)，其中 y为约束变元。存在量词$，辖域P(x)B(x,y)，其中 x为约束变元。不在量词辖域中的P(x)中的x为自由变元。P(x)(y$x(P(x)B(x,y)P(x)不是命题。 2、对个体域0，1判定下列公式的真值, E(x)表示“x是偶数”： （1）x(E(x)x=1) （2）x(E(x)x=1) （3）$x(E(x)x=1) （4）$x(E(x)x=1)再将它们的量词消去,表示成合取或析取命题公式，鉴别你所确定的真值是否正确。解（1）x(E(x)x=1) 真x(E(x)x=1) 可表示成命题公式（E(0)0=1）（E(1)1=1）其中E(0)0=1真，E(1)1=1也真，故（E(0)0=1）（E(1)1=1）真。 （2）x(E(x)x=1) 假 x(E(x)x=1) 可表示成命题公式（E(0) 0=1）（E(1) 1=1）其中E(0) 0=1真，但E(1) 1=1假，故（E(0) 0=1）（E(1) 1=1）假。（3）$x(E(x)x=1) 假$x(E(x)x=1) 可表示成命题公式 (E(0)0=1) (E(1)1=1)其中E(0)0=1假，E(1)1=1也假，故 (E(0)0=1) (E(1)1=1)假。（4）$x(E(x)x=1) 真$x(E(x)x=1) 可表示成命题公式 (E(0)0=1) (E(1)1=1)其中E(0)0=1假，但E(1)1=1真，故 (E(0)0=1) (E(1)1=1)真。 3、设整数集为个体域，判定下列公式的真值(*表示数乘运算)： （1）x $y(x*y=x) （2）x$y (x*y=1) （3）x $y(x+y=1) （4）$y x (x*y=x) （5）$y x (x+y=1) 解（1）x $y(x*y=x) 真 （2）x$y (x*y=1) 假 （3）x $y(x+y=1) 真 （4）$y x (x*y=x) 真 （5）$y x (x+y=1) 假4、量词 $! 表示“有且仅有”，$!xP(x)表示有且仅有一个个体满足谓词P(x)。试用量词，, $,等号“=”及谓词P(x),表示 $! P(x)，即写出一个通常的谓词公式使之与$!xP(x)具有相同的意义。解 $!xP(x)可用以下具有相同的意义的谓词公式表示 $x（P(x) y（P(y)y=x） 5、设个体域为整数集，试确定两个谓词P(x,y)，分别使得下列两个蕴涵式假： （1）x $!yP(x,y) $!yx P(x,y)（2）$!yx P(x,y) x $!yP(x,y)解（1）当P(x,y)表示x+y=0时x $!yP(x,y) $!yx P(x,y)为假。（2）当P(x,y)表示x*y=0时$!yx P(x,y)x $!yP(x,y) 为假(*表示数乘运算)。因为只有数0对一切整数x，有x*0=0，从而前件真；但对数0，可有众多y，使0*y=0，从而后件假。 6、指定整数集的一个尽可能大的子集（如果存在）为个体域，使得下列公式为真： （1）x(x0) （2）x(x=5x=6) （3）x $y(x+y=3)（4）$y x (x+y0)为真 （2）对5，6 ，x(x=5x=6) 为真 （3）对整数集，x $y(x+y=3) 为真（4）使得$y x (x+y0$（0x（| x c | f(x) k |0$（0x（| x c | f(x) k |0（0$x（| x c | f(x) k |e）可用自然语言表述为：存在正数e，对无论怎样的正数，均有x使得| x c |但| f(x) k |e。 15、判别下列公式是否是可满足的，并说明理由： （1）xP(x)$yP(y) （2）xP(x)$yP(y) （3）(P(a) $xP(x) （4）(P(a)$xP(x)（5） P(a)$xP(x) （6）xP(x) P(a)解 （1）xP(x)$yP(y) 是可满足的，因为可使xP(x)和$yP(y)之一为真。（2）xP(x)$yP(y) 是不可满足的，因为不可能使xP(x)和$yP(y)同时为真。（3）(P(a) $xP(x) 是可满足的，因为只要使$xP(x)真，P(a)假，P(a) $xP(x)便为假，从而(P(a) $xP(x)真。（4）(P(a)$xP(x) 是可满足的，因为只要使$xP(x)假，或P(a)假，P(a)$xP(x)便为假，从而(P(a)$xP(x)真。（5）P(a)$xP(x) 是可满足的，因为只要使P(a)假，P(a)$xP(x)便为真。（6）xP(x) P(a) 是可满足的，因为只要使xP(x)假，xP(x) P(a)便为真。 16、设个体域D=d1, ,dn，试用消去量词的方式证明：当A(x)中无自由变元y, B(y) 中无自由变元x时，x $y (A(x)B(y) $yx (A(x)B(y)解 x $y (A(x)B(y) x（A(x)B(d1)）（A(x)B(d2)）（A(x)B(dn)） （A(d1)B(d1)）（A(d1)B(dn)）（A(d2)B(d1)）（A(d2)B(dn)）（A(dn)B(d1)）（A(dn)B(dn)） （A(d1)（B(d1)B(dn)）（A(d2)（B(d1)B(dn)）（A(dn)（B(d1)B(dn)） （A(d1)A(dn)）（B(d1)B(dn)） $yx (A(x)B(y)$y(A(d1)B(y)(A(d2)B(y) (A(dn)B(y) (A(d1)B(d1)(A(dn)B(d1)(A(d1)B(d2)(A(dn)B(d2)(A(d1)B(dn)(A(dn)B(dn)（A(d1)A(dn)）B(d1)）（A(d1)A(dn)）B(d2)）（A(d1)A(dn)）B(dn)）（A(d1)A(dn)）（B(d1)B(dn)） 故x $y (A(x)B(y)$yx (A(x)B(y) 17、求下列各式的前束合取范式： （1）x (A(x)$y B(y) (A(x)中无自由变元) （2）x (A(x)$y B(x,y) A(x)中无自由变元) （3）xy ($zA(x,y,z) $z B(x,y,z) （4）$x($y A(x,y)($z B(z)C(x) A(x,y)中无自由变元z)（5）x($yA(x,y)$xy( B(x,y)y(A(y,x)B(x,y)解 （1）x (A(x)$y B(y)$x（A(x)yB(y)） $xy（A(x)B(y)）（2）x (A(x)$y B(x,y)x (A(x)$y B(x,y) x$y (A(x)B(x,y)（3）xy ($zA(x,y,z) $z B(x,y,z)xy（($zA(x,y,z)$z B(x,y,z)($z B (x,y,z)$z A(x,y,z)） xy（($zA(x,y,z)$zB(x,y,z)($z B (x,y,z) $z A(x,y,z)） xy（(zA(x,y,z)$zB(x,y,z)(zB (x,y,z) $z A(x,y,z)） xy（(zA(x,y,z)$uB(x,y,u)(vB (x,y,v) $w A(x,y,w)） xyz$uv$w（(A(x,y,z)B(x,y,u)(B (x,y,v) A(x,y,w)）（4）$x($y A(x,y)($z B(z)C(x)$x($y A(x,y)($z B(z)C(x) $x($y A(x,y)(zB(z)C(x) $x($y A(x,y)z (B(z)C(x) $x$y z (A(x,y)B(z)C(x)（5） x($yA(x,y)$x