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

练习2.11、指出下列谓词公式中的量词及其辖域，指出各自由变元和约束变元，并回答它们是否是命题：_Vx(P(x)VQ(x))AR(R为命题常元)Vx(P(x)AQ(x))A3xS(x)-T(x)Vx(P(x)^3y(B(x,y)AQ(y))VT(y))P(x)f(Vy^x(P(x)AB(x,y))fP(x))解(1)全称量词V,辖域P(x)VQ(x),其中x为约束变元，Vx(P(x)VQ(x))AR是命题。(2)全称量词V,辖域P(x)VQ(x)，其中x为约束变元。存在量词土辖域S(x)，其中x为约束变元。T(x)中x为自由变元。Vx(P(x)AQ(x))A3xS(x)-T(x)不是命题。(3)全称量词V,辖域P(x)f^y(B(x,y)AQ(y))VT(y),其中x为约束变元，T(y)中y为自由变元。存在量词土辖域B(x,y)AQ(y),其中y为约束变元0Vx(P(x)^3y(B(x,y)AQ(y))VT(y))是命题。(4)全称量词V,辖域女(P(x)AB(x,y)),其中y为约束变元。存在量词3,辖域P(x)AB(x,y),其中x为约束变元。不在量词辖域中的P(x)中的x为自由变元。P(x)f(Vy3x(P(x)AB(x,y))fP(x))不是命题。2、对个体域｛0，1｝判定下列公式的真值,E(x)表示“x是偶数”：Vx(E(x)f「x=1)Vx(E(x)Anx=1)3x(E(x)Ax=1)3x(E(x)fx=1)再将它们的量词消去，表示成合取或析取命题公式，鉴别你所确定的真值是否正确。解(1)Vx(E(x)f「x=1)真Vx(E(x)f「x=1)可表示成命题公式(E(0)f「0=1)A(E(1)f「1=1)其中E(0)f「0=1真，E(1)f「1=1也真，故(E(0)f「0=1)A(E(1)f「1=1)真。Vx(E(x)Anx=1)假Vx(E(x)Anx=1)可表示成命题公式(E(0)An0=1)A(E(1)An1=1)其中E(0)An0=1真，但E(1)An1=1假，故(E(0)An0=1)A(E(1)An1=1)假。3x(E(x)Ax=1)假3x(E(x)Ax=1)可表示成命题公式(E(0)A0=1)V(E(1)A1=1)其中E(0)A0=1假，E(1)A1=1也假，故(E(0)A0=1)V(E(1)A1=1)假。3x(E(x)fx=1)真3x(E(x)fx=1)可表示成命题公式(E(0)f0=1)V(E(1)f1=1)其中E(0)f0=1假，但E(1)f1=1真，故(E(0)f0=1)V(E(1)-1=1)真。3、设整数集为个体域，判定下列公式的真值(*表示数乘运算)：Vx3y(x*y=x)Vx3y(x*y=1)Vx3y(x+y=1)3yVx(x*y=x)3yVx(x+y=0)xy(对y=0)解(1)xy(xy=x)真xy(xy=1)假xy(x+y=1)真yx(xy=x)真yx(+y=0)假xy(对y=0)真4、量词！表示“有且仅有”，!xP(x)表示有且仅有一个个体满足谓词P(x)。试用量词，，，等号“=”及谓词P(x)表示！P(x)即写出一个通常的谓词公式使之与！xP(x)M有相同的意义。解!xP(x)可用以下具有相同的意义的谓词公式表示x(P(x)Ay(P(yAy=x))5、设个体域为整数集，试确定两个谓词P(x,y)分别使得下列两个蕴涵式假：x!yP(x,y)f!yxP(xy)!yxP(xy)fx!yP(x,y)解(1)当？&,尸表示x+y=0时x!yP(x,y)f!yxP(xy)为假。当P(x,y表示xy=0时!yxP(xy)fx!yP(x,y)为假(表示数乘运算)。因为只有数0对一切整数乂，有x0=0,从而前件真；但对数0,可有众多尸，使0y=0,从而后件假。6、指定整数集的一个尽可能大的子集(如果存在)为个体域，使得下列公式为真：x(x>0)x(x=5Vx=6)xy(x+y=3)yx(+y<0)解(1)对正整数集个体域，x(x>0)为真对5,6,x(x=5Vx=6)为真对整数集，xy(x+y=3)为真使得yx(+y<0)为真的整数集的尽可能大的子集不存在。7、以实数集为个体域，用谓词公式将下列语句形式化：如果两实数的平方和为零，那么这两个实数均为零。f(x为一实函数当且仅当对每一实数x都有且只有一个实数y满足y=f(x)(不得使用量词！。“f(x为实函数”可译为RF(f))。解(1)xy(建+y2=0fx=0y=0)。(2)RF(f)xy(y=f(A)nz(*yAz=f(x)))8、用谓词公式将下列语句形式化：高斯是数学家，但不是文学家。没有一个奇数是偶数。一个数既是偶数又是质数，当且仅当该数为2。有的猫不捉耗子，会捉耗子的猫便是好猫。发亮的东西不都是金子。不是所有的男人都至少比一个女人高，但至少有一个男人比所有的女人高。一个人如果不相信所有其他人，那么他也就不可能得到其他人的信任。如果别的星球上有人，天文学家是不会感到惊讶的。党指向哪里，我们就奔向那里。谁要是游戏人生，他就一事无成；谁不能主宰自己，他就是一个奴隶。(歌德)解(1)M(x)表示“x是数学家”，A(x)表示“x是天文学家”，g表示“高斯”，原句可表示为M(g)AnA(g)O(x)表示“x是奇数”，E(x)表示“x是偶数”，原句可表示为n3x(O(x)AE(x))O(x)表示“x是奇数”，E(x)表示“x是偶数”，原句可表示为Vx(O(x)AE(x)0x=2)C(x)表示“x是猫”，M(x)表示“x是老鼠”，G(x)表示“x是好的”，K(x,y)表示“x会捉y”，原句可表示为3x(C(x)AVy(M(y)f「K(x,y))AVx(C(x)AVy(M(y)fK(x,y))fG(x))G(x)表示“x是金子”，L(x)表示“x是发亮的”，原句可表示为nVx(L(x)fG(x))M(x)表示“x是男人”，F(x)表示“x是女人”，H(x,y)表示“x比y高”，原句可表示为nVx(M(x)-3y(F(y)AH(x,y)))A3x(M(x)AVy(F(y)fH(x,y)))M(x)表示“x是人”，B(x,y)表示“x相信y”,原句可表示为Vx(M(x)An^y(M(y)Ax手yAB(x,y))f「3y(M(y)Ax^yAB(y,x)))C(x)表示“x是星球”，M(x)表示“x是人”，A(x)表示“x是天文学家”，e表示“地球”，H(x,y)表示“x有y”，S(x)表示“x惊讶”，原句可表示为3x(C(x)Ax手eA^y(M(y)AH(x,y)))fVx(A(x)^nS(x))Q(x,y)表示“x指向y”，J(x,y)表示“x奔向y”，party表示“党”，we表示“我们”，原句可表示为Vx(Q(party，x)fJ(we,x))M(x)表示“x是人”，K(x)表示“x游戏人生”，L(x)表示“x一事无成”，H(x,y)表示“x主宰y”，N(x)表示“x是奴隶”，原句可表示为Vx(M(x)AK(x)fL(x))AVx(nH(x,x)-N(x))练习2.21、1、利用量词意义或利用已经证明了的永真式及几个基本原理，证明2.2.2节第(2)-(8)组永真式中尚未证明的各式。解证(3)之bA(x)卜3xA(x)设U,I,s分别是使A(x)真的个体域、解释和指派，s(x)=deU，那么A(d)真，因此对个体域U、解释I,3xA(x)也真。证(3)之cVxA(x)卜3xA(x)由VxA(x)|-A(x)和VxA(x)\-3xA(x)立即可得。证(4)之bnVxnA(x)|--13xA(x)设U,I是使nVxnA(x)真的个体域和解释，那么并非U中的所有个体都使得解释I下的谓词A(x)假，，因此U中有个体使得解释I下的谓词A(x)真，故个体域U和解释IT3xA(x)真o上述证明是可逆的，所以nVxnA(x)|―|3xA(x)得证。证(4)之cVxnA(x)|--1n3xA(x)在(4)之a中取A(x)为nA(x)即可得本式。证(4)之dnVxA(x)|--13xnA(x)在(4)之b中取A(x)为nA(x)即可得本式。证(5)之aVxA(x)VB|--1Vx(A(x)VB)设U,I是使VxA(x)VB真的个体域和解释，那么1)U,I使B真。于是U,I使A(x)VB对一切x均真，因此U,I使Vx(A(x)VB)o

2)U,I使VxA(x)真。于是U,I使A(x)对一切x均真，从而对一切x,A(x)VB真，因此U,I使Vx(A(x)VB)0故VxA(x)VB卜Vx(A(x)VB)。上述证明是可逆的，所以VxA(x)VB|—|Vx(A(x)VB)得证。证(5)之bVxA(x)AB|--1Vx(A(x)AB)仿(5)之a可证。证(5)之d3xA(x)AB||3x(A(x)AB)3xA(x)ABHn(n(3xA(x)AB))（据（4）之c）（据（5）之a）

（据（4）之d）Hn㈠3xA(x)VnB)Hn(VxnA(x)VnB)HnVx㈠A(x)VnB)H3xn㈠A(x)Vn（据（4）之c）（据（5）之a）

（据（4）之d）设U,I是使Vx(A(x)AB(x))真的个体域和解释，那么对任意deU,A(d)AB(d)真。因此，对任意deU，A(d)真，对任意deU，B(d)真。故U,I是使VxA(x)AVxB(x))真。Vx(A(x)AB(x))|VxA(x)AVxB(x)得证。上述证明是可逆的，所以Vx(A(x)AB(x))|—|VxA(x)AVxB(x)得证。证(6)之b3x(A(x)VB(x))|--13xA(x)V3xB(x)3x(A(x)VB(x))||n㈠3x(A(x)VB(x)))（据（4）之c）（据（6）之a）（据（4）之d）Hn(Vx㈠A(x)AnB(x)))Hn(VxqA(x)AVxqB(x))Hn㈠3xA(x)An3（据（4）之c）（据（6）之a）（据（4）之d）个体域和解释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)|--1VyVxA(x,y)和VyVxA(x,y)|3yVxA(x,y)立即可得。证(7)之c3yVxA(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)|--13y3xA(x,y)3x3yA(x,y)||q(n3x3yA(x,y))（据（4）之c）（据（7）之a）（据（4）之b）Hq(VxVyqA(x,y))Hq(VyVxqA(x,y))H林xA(x,y)证(8)之aVx(Cf（据（4）之c）（据（7）之a）（据（4）之b）C真，那么对任意deU,A(d)真，即VxA(x)真，因此CfVxA(x)真。故个体域和解释U,I使CfVxA(x)真，Vx(CfA(x))卜C-VxA(x)得证。上述证明是可逆的，所以Vx(CfA(x))|—|CfVxA(x潞证。证(8)之b3x(C-A(x))HC-3xA(x)(C中无自由变元x)仿(8)之a可证。2、证明下列逻辑蕴涵式及逻辑等价式(方法不限)：3xP(x)fVxQ(x)|-Vx(P(x)fQ(x))证女P(x)fVxQ(x)|13xP(x)VVxQ(x)|-Vx-|P(x)VVxQ(x)\-Vx(-|P(x)VQ(x))I-Vx(P(x)fQ(x))P(x)AVxQ(x)卜3x(P(x)AQ(x))证P(x)AVxQ(x)\-P(x)AQ(x)卜3x(P(x)AQ(x))VxVy(P(x)VQ(y))|—|VxP(x)VVyQ(y)证VxVy(P(x)VQ(y))HVx(P(x)VVyQ(y))HVxP(x)VVyQ(y)3x3y(P(x)AQ(y))H3xP(x)A3yQ(y)证3x3y(P(x)AQ(y))H3x(P(x)A3yQ(y))H3xP(x)A3yQ(y)3x3y(P(x)-Q(y))HVxP(x)-3yQ(y)证3x3y(P(x)-Q(y))H3x3y(nP(x)VQ(y))H3x(-|P(x)V3yQ(y))H3x-|P(x)V3yQ(y)HIVxP(x)V3yQ(y)HVxP(x)TyQ(y)VxVy(P(x)fQ(y))H3xP(x)^VyQ(y)证VxVy(P(x)fQ(y))HVxVy(-|P(x)VQ(y))HVx(-|P(x)VVyQ(y))HVx-|P(x)VVyQ(y)HI3xP(x)VVyQ(y)H女P(x)fVyQ(y)3、试举出一个个体域及两种解释，分别证明第2题之(1)(2)的逆不能成立。解第2题之(1)0取个体域为自然数集合，P(x)表示：x为不等于2的质数，Q(x)表示：x为奇数，那么Vx(P(x)fQ(x))真，女P(x)fVxQ(x)假<3xP(x)假，而VxQ(x)真)。故Vx(P(x)fQ(x))卜3xP(x)fVxQ(x)不能成立。第2题之(2)—取个体域为自然数集合，P(x)表示：x等于2,Q(x)表示：x为偶数，指派P(x)中自由变元x=3,那么3x(P(x)AQ(x))真，P(x)AVxQ(x)假。3x(P(x)AQ(x))卜P(x)AVxQ(x)不能成立。4、设个体域D={d…,dj,试用消去量词的方法证明下列基本逻辑等价式：qVxA(x)曰3xqA(x)解qVxA(x)|--1q(A(d1)A„AA(dn))|--qA(d1)V„VqA(dn)H3xnA(x)VxA(x)APHVx(A(x)AP)(P为命题常元)解VxA(x)APH(A(d1)A„AA(dn))APH(A(d1)AP)A„A1(A(dn)AP)HVx(A(x)AP)nVxA(x)VVxB(x)|Vx(A(x)VB(x))解VxA(x)VVxB(x)H(A(d1)A„AA(d「)V(B(d1)A„AB(d「)|(A(d1)V(B(d1))A„A(A(dn))V(B(d：))|Vx(A(x)VB(x))3xA(x)V3xB(x)H3x(A(x)VB(x))解3xA(x)V3xB(x)H(A(d1)V„VA(dn))V(B(d1)V„VB(d「)H(A(d1)VB(d1))V„V(A(dn))V„VB(dn))H3x(A(x)VB(x))nn练习2.31、设个体域D={d],d2,d3},试用消去量词的方式证明：当A(x)中无自由变元y,B(y)中无自由变元x时，Vx3y(A(x)AB(y))|―|3yVx(A(x)AB(y))解Vx3y(A(x)AB(y))HVx((A(x)AB(dJ)V(A(x)AB(d2))V(A(x)AB(d3)))H((A(d])AB(d]))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乙_L乙乙乙J((A(d3)AB(d1))V(A(d3)AB(d2))V(A(d3)AB(d3)))H(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)))H(A(d1)AA(d2)AA(d3))A(B(d1)VB(d2)VB(d3))3yVx(A(x)AB(y))||3y((A(d1)AB(y))A(A(d2)AB(y))A(A(d3)AB(y)))H((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)))H(A(d1)AA(d2)AA(d3))AB(d1))VH(A(d1)AA(d2)AA(d3))AB(d2))VH(A(d1)AA(d2)AA(d3))AB(d3))H(A(d1)AA(d2)AA(d3))A(B(d1)VB(d2)VB(d3))故Vx3y(A(x)AB(y))|―|3yVx(A(x)AB(y))2、求下列各式的前束合取范式:(1)qVx(A(x)f对B(y))Vx(A(x)f对B(x,y))VxVy(3zA(x,y,z)^3zB(x,y,z))3x(n3yA(x,y)-(3zB(z)-C(x)))qVx(3yA(x,y)^3xVy(B(x,y)AVy(A(y,x)fB(x,y))))解(1)「Vx(A(x)