指出下列谓词公式中的量词及其辖域

练习 2.11、指出下列谓词公式中的量词及其辖域，指出各自由变元和约束变元，并回答它们是 否是命题：(1) Vx(P(x)VQ(x)AR(R 为命题常元)(2) Vx(P(x)AQ(x)A3xS(x)-T(x)(3) Vx(P(x)f my(B(x,y) A Q(y) VT(y)(4) P(x)(Vy3x(P(x)AB(x,y)f P(x)解(1)全称量词V,辖域P(x)VQ(x),其中x为约束变元，Vx(P(x)VQ(x)AR是命题。(2)全称量词V,辖域P(x)VQ(x)，其中x为约束变元。存在量词3,辖域S(x)，其中x为约束变元。T(x)中 x 为自由变元。Vx(P(x)AQ(x) A3xS(x)f T(x)不是命题。(3)全称量词V,辖域P(x)-3y(B(x,y)AQ(y)VT(y),其中x为约束变元，T(y)中y为自 由变元。存在量词3,辖域B(x,y)AQ(y),其中y为约束变元。Vx(P(x)3y(B(x,y)AQ(y) VT(y)是命题。(4)全称量词V,辖域3x(P(x)AB(x,y),其中y为约束变元。存在量词3,辖域P(x)AB(x,y),其中x为约束变元。不在量词辖域中的P(x)中的x为自由变元。P(x)-(Vy3x(P(x)AB(x,y)-P(x) 不是命题。2、对个体域0,1判定下列公式的真值,E(x)表示“x是偶数”：(1) Vx(E(x)fx=1)(2) Vx(E(x)Aq x=1)(3) 3x(E(x)Ax=1)(4) 3x(E(x)fx=1) 再将它们的量词消去,表示成合取或析取命题公式，鉴别你所确定的真值是否正确。解(1) Vx(E(x)fx=1)真Vx(E(x)fx=1)可表示成命题公式(E(0)f0=1)A(E(1)f1=1) 其中玖0)f0=1 真，玖 1)f1=1 也真，故(E(0)f0=1)A(E(1)f1=1)真。(2) Vx(E(x)An x=1)假Vx(E(x)An x=1)可表示成命题公式(E(0) An 0=1)A(E(1) An 1=1) 其中 E(0) An 0=1 真，但玖1) An 1=1 假，故(E(0) An 0=1)A(E(1) An 1=1)假。(3) 3x(E(x)Ax=1) 假3x(E(x)Ax=1) 可表示成命题公式 (E(0)A0=1) V (E(1)A1=1) 其中 E(0)A0=1 假，玖 1)A1=1 也假，故(E(0)A0=1) V (E(1)A1=1)假。(4) 3x(E(x)x=1)真3x(E(x)f x=1)可表示成命题公式(E(0)f 0=1) V (E(1)f 1=1) 其中 E(0)-0=1 假，但 E(1)-1=1 真，故(E(0)-0=1) V (E(1)-1=1)真。3、设整数集为个体域，判定下列公式的真值(*表示数乘运算):(1) Vx 3y(x*y=x)(2) Vx3y (x*y=1)(3) Vx 3y(x+y=1)(4) 3y Vx (x*y=x)( 5) 3y Vx (x+y=0)(6) Vx 3y(x+y=0)解(1) Vx my(x*y=x)真(2) Vx3y (x*y=1)假(3) Vx 3y(x+y=1)真(4) 3y Vx (x*y=x)真(5) 3y Vx (x+y=0)假(6) Vx 3y(x+y=0)真4、量词3!表示“有且仅有”，3!xP(x)表示有且仅有一个个体满足谓词P(x)。试用量 词，V, 3,等号“=”及谓词P(x)，表示3! P(x)，即写出一个通常的谓词公式使之与3!xP(x)具 有相同的意义。解3!xP(x)可用以下具有相同的意义的谓词公式表示3x (P(x) AVy (P(y)fy=x)5、设个体域为整数集，试确定两个谓词P(x,y)，分别使得下列两个蕴涵式假：(1) Vx 3!yP(x, y) 3!yVx P(x, y)(2) 3 !yVx P(x, y) Vx 3!yP(x, y)解(1)当 P(x,y)表示 x+y=0 时Vx 3!yP(x, y) 3!yVx P(x, y)为假。(2)当 P(x,y)表示 x*y=0 时3 !yVx P(x, y)Vx 3!yP(x, y)为假(*表示数乘运算)。因 为只有数0对一切整数x,有x*0=0，从而前件真；但对数0,可有众多y,使0*y=0，从而 后件假。6、指定整数集的一个尽可能大的子集(如果存在)为个体域，使得下列公式为真 ( 1 )Vx(x0)(2) Vx(x=5Vx=6)( 3)Vx 3y(x+y=3)( 4)3 y Vx (x+y0)为真(2) 对5, 6 , Vx(x=5Vx=6)为真(3) 对整数集， Vx 3y(x+y=3) 为真(4) 使得3y Vx (x+y0)为真的整数集的尽可能大的子集不存在。7、以实数集为个体域, 用谓词公式将下列语句形式化：(1) 如果两实数的平方和为零，那么这两个实数均为零。(2) f(x)为一实函数当且仅当对每一实数x都有且只有一个实数y满足y = f(x)(不得 使用量词3!。“f(x)为实函数”可译为RF(f)。解(1) VxVy(x2+y2=0x=0y=0)。(2) RF(f )oVx 3y(y = f(x)Aq 3z(z#yAz= f(x)8、用谓词公式将下列语句形式化：( 1)高斯是数学家，但不是文学家。( 2)没有一个奇数是偶数。(3) 一个数既是偶数又是质数，当且仅当该数为2。(4) 有的猫不捉耗子，会捉耗子的猫便是好猫。( 5)发亮的东西不都是金子。(6) 不是所有的男人都至少比一个女人高，但至少有一个男人比所有的女人高。(7) 一个人如果不相信所有其他人，那么他也就不可能得到其他人的信任。(8) 如果别的星球上有人，天文学家是不会感到惊讶的。( 9 )党指向哪里，我们就奔向那里。(10)谁要是游戏人生，他就一事无成；谁不能主宰自己，他就是一个奴隶。(歌德)解(1) M(x)表示“x是数学家”，A(x)表示“x是天文学家” g表示“高斯”，原句可 表示为M(g) An A(g)(2) O(x)表示“x是奇数”，E(x)表示“x是偶数”，原句可表示为n 3x(O(x)AE(x)(3) O(x)表示“x是奇数”，E(x)表示“x是偶数”，原句可表示为Vx(O(x) AE(x) ox=2)(4) C(x)表示“x是猫” M(x)表示“x是老鼠”，G(x)表示“x是好的”，K(x,y) 表示“x会捉y”，原句可表示为3x(C (x)AVy(M (y)n K(x,y)AVx(C (x)AVy(M (y)f K(x,y)f G(x)(5) G(x)表示“x是金子”，L(x)表示“x是发亮的”，原句可表示为n Vx(L (x)f G(x)(6) M(x)表示“x是男人”，F(x)表示“x是女人”，H(x，y)表示“x比y高”源 句可表示为n Vx(M (x)-my(F(y)AH(x，y)Ax(M (x)AVy(F(y)-H(x，y)(7) M(x)表示“x是人” B(x，y)表示“x相信y”，原句可表示为 Vx(M (x)An my(M(y)Ax#yAB(x，y)-n 3y(M(y)AxyAB(y，x)(8) C(x)表示“x是星球”，M(x)表示“x是人” A(x)表示“x是天文学家” e 表示“地球” H(x,y)表示“x有y” S(x)表示“x惊讶”原句可表示为3x(C (x) A xe A 3y(M(y) A H(x,y)-Vx(A (x)-n S(x)(9) Q(x,y)表示“x指向y” J(x,y)表示“x奔向y” party表示“党”，we表示 “我们” ，原句可表示为Vx(Q(party， x)-J(we， x)(10) M(x)表示“x是人”,K(x)表示“x游戏人生”,L(x)表示“x事无成”，H(x,y) 表示“x主宰y” N(x)表示“x是奴隶”，原句可表示为Vx(M(x)AK(x)-L(x)AVx(n H(x，x)-N(x)练习 2.2 1、1、利用量词意义或利用已经证明了的永真式及几个基本原理，证明2.2.2节第(2) (8)组永真式中尚未证明的各式。解证(3)之 b A(x)卜 3x A(x)设U,I,s分别是使A(x)真的个体域、解释和指派，s(x)=deU,那么A(d)真，因此对个 体域U、解释I, 3x A(x)也真。证(3)之 cVxA(x)卜 3x A(x)由 VxA(x)卜A(x)和 VxA(x)卜3x A(x)立即可得。证(4)之 b n Vxn A(x) |-1 3x A(x)设U,I是使n Vxn A(x)真的个体域和解释，那么并非U中的所有个体都使得解释I 下的谓词A(x)假,因此U中有个体使得解释I下的谓词A(x)真，故个体域U和解释I 下 3x A(x)真。上述证明是可逆的，所以n Vxn A(x) | 3x A(x)得证。证(4)之 cVxn A(x) |-1 n 3x A(x)在(4)之a中取A(x)为n A(x)即可得本式。证(4)之 d n VxA(x) |-1 3xn A(x) 在(4)之b中取A(x)为n A(x)即可得本式。证(5)之 aVxA(x)VB | Vx(A(x)VB)设U,I是使VxA(x)VB真的个体域和解释，那么1) U,I使B真。于是U,I使A(x)VB对一切x均真，因此U,I使Vx(A(x)VB)。2) U,I使VxA(x)真。于是U,I使A(x)对一切x均真，从而对一切x , A(x)VB真, 因此 U,I 使Vx(A(x)VB)。故 VxA(x)VB 卜 Vx(A(x)VB)。上述证明是可逆的，所以VxA(x)VB | Vx(A(x)VB)得证。证(5)之 bVxA(x)AB | Vx(A(x)AB)仿(5)之 a 可证。证(5)之 d3xA(x)AB H 3x(A(x)AB)3xA(x)AB H n 鬥(3xA(x)AB)(据( 4)之 c )(据( 5)之 a )(据( 4)之 d )H n 鬥 3xA(x)Vn B)H n (Vxn A(x)Vn B)H n Vx(n A(x)Vn B)H 3xn 鬥 A(x)Vn B)H 3x(A(x)AB)证(6)之 aVx(A(x)AB(x) |-1 VxA(x)A Vx B(x)设U,I是使Vx(A(x)AB(x)真的个体域和解释，那么对任意deU, A(d)AB(d)真。 因此，对任意deU, A(d)真，对任意deU, B(d)真。故U,I是使VxA(x)AVx B(x)真。 Vx(A(x)AB(x)卜 VxA(x)AVx B(x)得证。上述证明是可逆的，所以Vx(A(x)AB(x) | VxA(x)A Vx B(x)得证。证(6)之 b3x(A(x)VB(x) |-1 3xA(x)V3x B(x)(据( 4)之 c ) (据( 6)之 a ) (据( 4)之 d )3x(A(x)VB(x) | n 鬥 3x(A(x)VB(x)H n (Vx(n A(x)An B(x)H n (Vxq A(x)AVxq B(x)H n 鬥 3xA(x)An 3xB(x) H 3xA(x)V3xB(x)证(7)之 aVxVyA(x,y) |-1 VyVxA(x,y)个体域和解释U,I使VxVyA(x,y)真的意义，与个体域和解释U,I使VyVxA(x,y)真的 意义相同，因此VxVyA(x,y) | VyVxA(x,y)。证(7)之 bVxVyA(x,y)卜 3yVxA(x,y)由 VxVyA(x,y) |-1 VyVxA(x,y)和 VyVxA(x,y) | 3yVxA(x,y)立即可得。证(7)之 c 3yVxA(x,y)卜 Vx3yA(x,y)设U,I是使3yVxA(x,y)真的个体域和解释，那么有ceU,使得对任意deU，A(c,d) 真。因此，对任以deU，总可取ceU，使得A(c,d)真。故U,I也使Vx3yA(x,y)真。3yVxA(x,y) 卜 Vx3yA(x,y)得证。证(7)之 dVx3yA(x,y)卜 3y3xA(x,y)由 Vx3yA(x,y) |3x3yA(x,y)和 3x3yA(x,y) | 3y3xA(x,y) ( (7)之 e,下面给出 证明) 立即可得。证 (7) 之 e3x3yA(x,y) |-1 3y3xA(x,y)3x3yA(x,y)卜| q 鬥 3x3yA(x,y)H q (VxVyq A(x,y) | q (VyVxq A(x,y)H 3y3xA(x,y)(据( 4)之 c )(据( 7)之 a )(据( 4)之 b )证(8)之 aVx(Cf A(x) |-1 Cf Vx A(x) (C 中无自由变元 x )设U,I是使Vx(Cf A(x)真的个体域和解释，那么对任意deU, C-A(d)真。此时1) C 彳假，贝 U CfVx A(x)真。2) C真，那么对任意deU, A(d)真，即Vx A(x)真，因此CVx A(x)真。 故个体域和解释 U,I 使 Cf Vx A(x)真, Vx(Cf A(x) | Cf Vx A(x)得证。 上述证明是可逆的，所以Vx(Cf A(x) | Cf Vx A(x)得证。证(8)之 b3x(Cf A(x) | Cf3x A(x) (C 中无自由变元 x )仿(8)之 a 可证。2、证明下列逻辑蕴涵式及逻辑等价式(方法不限)：(1) 3x P(x)f Vx Q(x) | Vx(P(x)f Q(x)证 3x P(x)f Vx Q(x) |1 3x P(x)VVx Q(x)| Vx q P(x) VVx Q(x)卜 Vx (q P(x)VQ(x)| Vx(P(x)fQ(x)(2) P(x)AVx Q(x)卜 3x(P(x)AQ(x)证 P(x)AVx Q(x)卜 P(x)AQ(x)卜 3x(P(x)AQ(x)(3) VxVy(P(x)VQ(y) | Vx P(x)VVy Q(y)证 VxVy(P(x)VQ(y) | Vx (P(x)VVy Q(y)H Vx P(x)VVy Q(y)(4) 3x3y(P(x)AQ(y) H 3x P(x)A3y Q(y)证 3x3y(P(x)AQ(y) H 3x (P(x)A3y Q(y)H 3x P(x)A3y Q(y)(5) 3x3y(P(x)f Q(y) | Vx P(x)f 3y Q(y)证 3x3y(P(x)f Q(y) | 3x3y(q P(x)VQ(y)H 3x (q P(x)V3y Q(y)H 3x q P(x)V3y Q(y)H q Vx P(x)V3y Q(y) H Vx P(x)f 3y Q(y)(6) VxVy(P(x)f Q(y) |-1 3x P(x)f Vy Q(y)证 VxVy(P(x)f Q(y)卜| VxVy(q P(x)VQ(y)H Vx (q P(x)VVy Q(y)H Vx q P(x)VVy Q(y)H q 3x P(x)VVy Q(y) H 3x P(x)f Vy Q(y)3、试举出一个个体域及两种解释，分别证明第2题之(1)(2)的逆不能成立。解 第2题之(1)。取个体域为自然数集合，P(x)表示：x为不等于2的质数，Q(x)表示：x为奇数，那么 Vx(P(x)f Q(x)真，3x P(x)f Vx Q(x)假(女 P(x)假，而Vx Q(x)真)。故Vx(P(x)f Q(x)卜 3x P(x)f Vx Q(x)不能成立。第2 题之(2)取个体域为自然数集合，P(X)表示：x等于2, Q(x)表示：x为偶数，指派P(x)中自由 变元 x=3,那么3x(P(x)AQ(x)真，P(x)AVx Q(x)假。3x(P(x) AQ(x)卜 P(x)AVx Q(x)不能 成立。4、设个体域D=d,d，试用消去量词的方法证明下列基本逻辑等价式:(1) n VxA(x)匚3xq A(x)解VxA(x) |-1 q(A (d)AAA(dn)|- q A (d,)VVq A (d )1nH 3xn A(x)(2) VxA(x)AP H Vx(A(x)AP) (P 为命题常元)解 VxA(x)AP H (A (d1)AAA (dn)APH (A (d)AP)AA：A (dn)AP)H Vx(A(x)AP)n( 3)VxA(x)VVx B(x)| Vx(A(x)VB(x)解 VxA(x)VVx B(x) H (A (d ) AAA (d )V(B (d ) AAB (d ) 1n1n卜(A (d,)V(B (d,)AA(A (d )V(B (d ) 11nn| Vx(A(x)V B(x)(4) 3xA(x)V3x B(x) H 3x(A(x)VB(x)解 3xA(x)V3x B(x) H (A (d,)VVA (d )V(B (d,)VVB (d ) 1n1nH (A (d)VB (d,)VV(A (d )VVB (d )11nnH 3x(A(x)VB(x)练习2.31、设个体域D=d,d2 ,d3,试用消去量词的方式证明：当A(x)中无自由变元y, B(y)中 无自由变元 x 时，Vx 3y (A(x)AB(y) | 3yVx (A(x)AB(y)解 Vx 3y (A(x)AB(y) H Vx (A(x)AB(d1)V (A(x)AB(d2)V (A(x)AB(d3) |(A(d1)AB(d1)V(A(d1)AB(d2)V(A(d1)AB(d3)A ( A(d2)AB(d1)V( A(d2)AB(d2)V( A(d2)AB(d3)A( A(d3)AB(d1)V( A(d3)AB(d2)V( A(d3)AB(d3)|( A(d1)A(B(d1)VB(d2)VB(d3)A( A(d2)A(B(d1)VB(d2)VB(d3)A( A(d3)A(B(d1)VB(d2)VB(d3)|( A(d1)AA(d2)AA(d3)A(B(d1)VB(d2)VB(d3)3yVx (A(x)AB(y) H 3y(A(d1)AB(y)A(A(d2)AB(y)A(A(d3)AB(y)2333A B(d1)VA B(d2)V A B(d3) A(B(d1)VB(d2)VB(d3)|故Vx 3y (A(x)AB(y) | 3yVx (A(x)AB(y)| (A(d1)AB(d1)A(A(d2)AB(d1)A(A(d3)AB(d1)V (A(d1)AB(d2)A(A(d2)AB(d2)A(A(d3)AB(d2)V (A(d1)AB(d3)A(A(d2)AB(d3)A(A(d3)AB(d3) A(d1)AA(d2)AA(d3) A(d1)AA(d2)AA(d3) A(d1)AA(d2)AA(d3) A(d1)AA(d2)AA(d3)2、求下列各式的前束合取范式(1)q Vx (A(x)f 旳 B(y)(2) Vx (A(x)f 旳 B(x,y)(3) VxVy (3zA(x,y,z)3z B(x,y,z)(4) 3x(q 3y A(x,y)(3z B(z)C(x)(5) q Vx(3yA(x,y)3xVy( B(x,y)AVy(A(y,x)B(x,y)解(1)Vx (A(x)fy B(y)卜】3x (A(x)AVyq B(y) H 3xVy (A(x)An B(y)(2) Vx (A(x)f 旳 B(x,y) | Vx 鬥 A(x)V3y B(x,y) H Vx3y 鬥 A(x)VB(x,y)(3) VxVy (3zA(x,y,z)3z B(x,y,z) -1 VxVy (3zA(x,y,z)3z B(x,y,z)A(3z B (x,y,z)3zA(x,y,z)H VxVy (鬥 3zA(x,y,z)V3zB(x,y,z)A (n 3z B (x,y,z) V3z A(x,y,z)| VxVy (Vzq A(x,y,z)V3zB(x,y,z)A (Vzq B (x,y,z) V3z A(x,y,z)H VxVy(Vzq A(x,y,z)V3uB(x,y,u)A(Vvq B (x,y,v) V3w A(x,y,w)| VxVyVz3uVv3w (q A(x,y,z)V B(x,y,u)A (n B (x,y,v) VA(x,y,w)(4) 3x(q 3y A(x,y)(3z B(z)C(x) | 3x(3y A(x,y)V(q 3z B(z)VC(x)H 3x(3y A(x,y)V(Vzq B(z)VC(x) H 3x(3y A(x,y)VVz (q B(z) V C(x) | 3x3y Vz (A(x,y)Vq B(z)VC(x)(5) q Vx(3yA(x,y)3xVy( B(x,y)AVy(A(y,x)B(x,y) H 3 x(3yA(x,y)A3xVy( B(x,y)AVu (q A(u,x)VB(x, u) H 3 x(3yA(x,y)A3xVyVu ( B(x,y)A(q A(u,x)VB(x, u)|3 x(3yA(x,y)A 3vVwVu ( B(v, w)A (q A(u, v)VB(v, u)|3 x3y3vVwVu (A(x,y)A B(v, w)A (q A(u, v)VB(v, u)