谓词逻辑练习及答案

1、第二章 谓词逻辑练习一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

2、) 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是偶数

3、”：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

4、(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）xy(x y=x)2）xy (x y=1)3）xy(x+y=1)4）yx (x y=x)5

5、）yx (x+y=0)6）xy(x+y=0)解（1）xy(x y=x) 真（2）xy (x y=1) 假（3）xy(x+y=1) 真（4）yx (x y=x) 真（5）yx (x+y=0) 假6) x y(x+y=0) 真4、量词! 表示“有且仅有” ，, , 等号“ =”及谓词 P(x),表示 相同的意义。!xP(x) 表示有且仅有一个个体满足谓词P(x)。试用量词，! P(x)，即写出一个通常的谓词公式使之与!xP(x)具有解 !xP(x) 可用以下具有相同的意义的谓词公式表示x(P(x) y(P(y) y=x)5、设个体域为整数集，试确定两个谓词P(x,y) ，分别使得下列两个蕴涵式假：

6、(1) x !yP(x,y) !y x P(x,y)(2) !y x P(x,y) x !yP(x,y)解( 1)当 P(x,y)表示 x+y=0 时 x !yP(x,y) !y x P(x,y)为假。( 2)当 P(x,y)表示 x y=0 时 !y x P(x,y) x !yP(x,y) 为假 ( 表示数乘运算 )。因 为只有数 0 对一切整数 x，有 x 0=0，从而前件真；但对数 0，可有众多 y，使 0 y=0，从 而后件假。6、指定整数集的一个尽可能大的子集(如果存在)为个体域，使得下列公式为真：1) x(x>0)2) x(x=5 x=6)3) x y(x+y=3)4) y

7、x (x+y<0)解 (1)对正整数集个体域，x(x>0)为真( 2)对 5，6 ， x(x=5x=6) 为真( 3)对整数集， x y(x+y=3) 为真( 4)使得 y x (x+y<0) 为真的整数集的尽可能大的子集不存在。7、以实数集为个体域 , 用谓词公式将下列语句形式化：1)如果两实数的平方和为零，那么这两个实数均为零。( 2)f(x)为一实函数当且仅当对每一实数x 都有且只有一个实数 y满足 y = f(x)(不得使用量词!。“ f(x)为实函数”可译为 RF(f)。解 ( 1) x y(x2+y2=0 x=0y=0) 。( 2) RF(f )x y(y = f

8、(x) z(z y z= f(x)8、用谓词公式将下列语句形式化：( 1)高斯是数学家，但不是文学家。(2)没有一个奇数是偶数。( 3)一个数既是偶数又是质数，当且仅当该数为2。(4) 有的猫不捉耗子，会捉耗子的猫便是好猫。(5) 发亮的东西不都是金子。(6) 不是所有的男人都至少比一个女人高，但至少有一个男人比所有的女人高。(7) 一个人如果不相信所有其他人，那么他也就不可能得到其他人的信任。(8) 如果别的星球上有人，天文学家是不会感到惊讶的。(9) 党指向哪里，我们就奔向那里。( 10)谁要是游戏人生，他就一事无成；谁不能主宰自己，他就是一个奴隶。(歌德)解(1)M(x) 表示“ x是数

9、学家”，A(x) 表示“ x是天文学家” ，g表示“高斯” ,原句可 表示为M(g) A(g)( 2) O(x) 表示“ x 是奇数”， E(x) 表示“ x 是偶数” , 原句可表示为 x(O(x) E(x)( 3) O(x) 表示“ x 是奇数”， E(x) 表示“ x 是偶数” , 原句可表示为 x(O(x)E(x) x=2)( 4)C(x) 表示“ x 是猫”，M(x) 表示“ x 是老鼠”，G(x) 表示“ x 是好的”， K(x,y)表示 “ x 会捉 y” ,原句可表示为x(C (x) y(M (y) K(x,y) x(C (x) y(M (y)K(x,y)G(x)( 5) G(

10、x) 表示“ x 是金子”， L(x) 表示“ x 是发亮的” ,原句可表示为 x(L (x) G(x)( 6) M(x) 表示“ x 是男人”， F(x) 表示“ x 是女人”， H(x,y) 表示“ x 比 y 高” ,原句 可表示为 x(M (x) y(F(y)H(x,y) x(M (x) y(F(y)H(x,y)( 7) M(x) 表示“ x 是人”， B(x,y)表示“ x 相信 y” , 原句可表示为x(M (x) y(M(y) x y B(x,y) y(M(y) x y B(y,x)(8)C(x) 表示“ x是星球”，M(x) 表示“ x是人”，A(x) 表示“ x是天文学家”

11、， e表 示“地球”， H(x,y) 表示“ x 有 y”， S(x) 表示“ x 惊讶”，原句可表示为x(C (x)xe y(M(y) H(x,y) x(A (x) S(x)( 9) Q(x,y) 表示“ x 指向 y”， J(x,y) 表示“ x 奔向 y”， party 表示“党” ，we 表示 “我们” ,原句可表示为x(Q(party ， x) J(we, x)( 10)M(x) 表示“x 是人”，K(x) 表示“x 游戏人生”，L(x) 表示“x 一事无成”， H(x,y) 表示“ x 主宰 y”， N(x) 表示“ x 是奴隶”，原句可表示为x(M(x)K(x) L(x) x(H

12、(x,x) N(x)练习二1、 利用量词意义或利用已经证明了的永真式及几个基本原理，证明永真式。解： (1) A(x)x A(x)设 U,I,s 分别是使 A(x)真的个体域、解释和指派， s(x)=d U，那么 A(d)真 ,因此对个 体域 U、解释 I, x A(x) 也真。(2) xA(x) x A(x)由 xA(x) A(x) 和 xA(x)x A(x) 立即可得。(3) xA(x)x A(x)设 U,I 是使 x A(x)真的个体域和解释，那么并非U 中的所有个体都使得解释 I下的谓词 A(x)假，因此 U 中有个体使得解释 I 下的谓词 A(x)真，故个体域 U 和解释 I 下 x

13、 A(x)真。上述证明是可逆的，所以x A(x)x A(x)得证。(4) xA(x) Bx(A(x) B)xA(x)B ( xA(x)B)( xA(x) B) ( xA(x) B) x(A(x) B) x (A(x) B) x(A(x) B)(5) x(A(x) B(x)xA(x) x B(x)设 U,I 是使 x(A(x)B(x)真的个体域和解释，那么对任意d U，A(d) B(d)真。因此，对任意 d U，A(d)真，对任意 d U，B(d)真。故 U,I是使 xA(x) x B(x)真。x(A(x) B(x)xA(x) x B(x)得证。上述证明是可逆的，所以x(A(x) B(x)xA(

14、x) x B(x)得证。(6) x(A(x) B(x)xA(x) x B(x)x(A(x)B(x) ( x(A(x) B(x)( x( A(x) B(x) ( xA(x) x B(x) ( xA(x) xB(x)xA(x) xB(x)(7) x yA(x,y) y xA(x,y)个体域和解释 U,I使 x yA(x,y)真的意义， 与个体域和解释 U,I使 y xA(x,y)真的 意义相同，因此 x yA(x,y) y xA(x,y) 。(8) x yA(x,y) y xA(x,y)由 x yA(x,y) y xA(x,y) 和 y xA(x,y) y xA(x,y) 立即可得。(9) y x

15、A(x,y) x yA(x,y)设 U,I 是使 y xA(x,y)真的个体域和解释， 那么有 c U ，使得对任意 d U ，A(c,d) 真。因此，对任以 d U，总可取 c U，使得 A(c,d) 真。故 U,I 也使 x yA(x,y)真。y xA(x,y) x yA(x,y)得证。(10)x yA(x,y)y xA(x,y)由 x yA（x,y） 出证明 ） 立即可得。x yA(x,y) 和 x yA(x,y)y xA（x,y） （ （7）之 e,下面给(11)x yA(x,y)y xA(x,y)xyA(x,y) (x yA(x,y) ( xyA(x,y) ( yxA(x,y)y x

16、A(x,y)2、证明下列逻辑蕴涵式及逻辑等价式（方法不限）（1）x P(x) x Q(x)x(P(x)Q(x)证x P(x) x Q(x) x P(x) x Q(x)x P(x) x Q(x)x( P(x)Q(x)x(P(x)Q(x)（2）P(x) x Q(x)x(P(x)Q(x)证 P(x) x Q(x) P(x) Q(x)x(P(x)Q(x)（3）x y(P(x) Q(y)x P(x)y Q(y)证xy(P(x)Q(y)x (P(x)y Q(y)x P(x) y Q(y)（4）x y(P(x) Q(y)x P(x)y Q(y)证 x y(P(x) Q(y)x (P(x) y Q(y)x P

17、(x) y Q(y)5) x y(P(x) Q(y)x P(x) y Q(y)证 x y(P(x) Q(y)x ( P(x)y Q(y)x P(x)y Q(y) x P(x)y Q(y)x y( P(x)Q(y)x P(x) y Q(y)6) x y(P(x) Q(y)x P(x) y Q(y)证 x y(P(x) Q(y)x y( P(x)Q(y)x ( P(x) y Q(y)x P(x) y Q(y) x P(x) y Q(y)x P(x) y Q(y)3、试举出一个个体域及两种解释，分别证明第2 题之( 1)( 2)的逆不能成立。取个体域为自然数集合， x(P(x)Q(x)真， x P(

18、x) P(x) x Q(x)不能成立。解 第 2 题之( 1 )：P(x)表示： x 为不等于 2 的质数， Q(x)表示： x 为奇数，那么x Q(x)假( x P(x)假，而 x Q(x)真)。故 x(P(x) Q(x) x第 2 题之( 2)：取个体域为自然数集合， P(x)表示： x 等于 2， Q(x)表示： x 为偶数，指派 P(x)中自由变元 x=3, 那么 x(P(x) Q(x)真，P(x) x Q(x)假。 x(P(x) Q(x) P(x) x Q(x) 不能成立。4、设个体域 D= d1, ,dn ，试用消去量词的方法证明下列基本逻辑等价式：( 1) xA(x)x A(x)

19、解 xA(x) ( A( d1) A( dn )A( d1) A(dn)x A(x)(2) xA(x)Px(A(x)P) ( P为命题常元)解 xA(x) P (A(d1) A(dn) P( A( d1) P) (A(dn) P) x(A(x)P)(3) xA(x) x B(x) x(A(x) B(x)解 xA(x) x B(x) (A(d1) A( dn)( B(d1) B(dn)( A( d1)( B( d1)( A( dn)( B( dn)x(A(x)B(x)4) xA(x) x B(x)x(A(x)B(x)解 xA(x) x B(x)A（d1） A（ dn）（ B（d1） B（dn）A

20、（d1） B（d1）（ A（ dn） B（dn）x(A(x)B(x)练习三1、设个体域 D= d1, d2 ,d3 ，试用消去量词的方式证明： 当 A（x）中无自由变元 y, B（y） 中 无自由变元 x 时，x y (A(x) B(y)y x (A(x)B(y)解 x y (A(x) B(y)x( A(x) B(d1)( A(x)B(d2)( A(x)B(d3)(A(d1)B(d1)(A(d1)B(d2)( A(d1)B(d3)(A(d2)B(d1)( A(d2) B(d2)( A(d2)B(d3)(A(d3)B(d1)( A(d3) B(d2)( A(d3)B(d3)( A(d1)( B(

21、d1)B(d2) B(d3)(A(d 2)( B(d1) B(d2)B(d3)(A(d3)( B(d1)B(d2)B(d3)( A(d1) A(d2)A(d3)( B(d1)B(d2)B(d3) y x (A(x)B(y)y(A(d1)B(y)(A(d2) B(y)(A(d3)B(y)(A(d1)B(d1)(A(d2)B(d1)(A(d3) B(d1)(A(d1)B(d2)(A(d2)B(d2)(A(d3)B(d2)(A(d1)B(d3)(A(d2)B(d3)(A(d3)B(d3)(A(d1)A(d2)A(d3) B(d1)(A(d1)A(d2)A(d3) B(d2)(A(d1)A(d2)A(d3) B(d3)( A(d1) A(d2)A(d3)( B(d1)B(d2)B(d3) 故 x y (A(x) B(y)y x (A(x)B(y)2、求下列各式的前束合取范式：1)x (A(x) y B(y)2)x (A(x) y B(x,y)3)x y ( zA(x,y,z)z B(x,y,z)4)x( y A(x,y) ( zB(z)C(