练习5.11•指出下列谓词公式中的量词及其辖域，指出各自由变元和约束变元，并作适当更改，同时回答它们是否是命题：(1)x(P(x)V Q(x))A R(2)x(P(x)A Q(x))A xS(x) f T(x)(3)x(P(x) f y(B(x,y)A Q(y))V T(y))(4)P(x) ( y x(P(x)A B(x,y)) P(x))解：(1)全称量词，辖域P(x)V Q(x)，其中x为约束变元，x(P(x)V Q(x))A R是命题。
不需要更改变元。
(2)全称量词，辖域P(x)V Q(x),其中x为约束变元。
存在量词，辖域S(x),其中x为约束变元。
T(x)xxx为自由变元。
x(P(x)A Q(x))A xS(x) f T不是命题。
公式中x既是自由变元又是约束变元，可更改变元为如下公式：x(P(x)A Q(x))A yS(y) f T(z)(3)全称量词，辖域P(x) f y(B(x,y)A Q(y))V T(y),其中x为约束变元,存在量词，辖域B(x,y)A Q(y)，其中y为约束变元。
T(y)xxy为自由变元。
x(P(x) f y(B(x,y)A Q(y))V T(y))不是命题。
公式中y既是自由变元又是约束变元，可更改变元为如下公式：x(P(x) -y(B(x,y)A Q(y))V T(z)不是命题。
(4)全称量词，辖域x(P(x)A B(x,y)),其中y为约束变元。
存在量词，辖域P(x)A B(x,y),其中x为约束变元。
不在量词辖域中的P(x)(第一个和第三个P(x))中的x为自由变元。
P(x) y x(P(x)A B(x,y)) - P不是命题。
公式中x既是自由变元又是约束变元，可更改变元为如下公式：P(z) -(y x(P(x)A B(x,y)) - P(z))2. 对个体域｛0,1｝判定下列公式的真值，E(x)表示“是偶数”(1)x(E(x) x=1)(2)x(E(x)A「x=1)(3)x(E(x)A x=1)(4)x(E(x) —x=1)再将它们的量词消去，表示成合取或析取命题公式，鉴别你所确定的真值是否正确。
解：(1)x(E(x) x真)x(E(x) —n可表示成命题公式(E(0) —n 0=1A (E(1) —n 1)1其中E(0) —n 0真，E(1) 1也真，故(E(0) r 0)=1A (E(1)「1)真。
(2)x(E(x)A「x=1假x(E(x)A「x=1可表示成命题公式(E(0)A n0=) A (E(1) A n1=)其中E(0)A n0二真，但E(1)A n仁假，故(E(0)A n0=) A (E(1) A q 1=)假。
(3)x(E(x)A x=1假x(E(x)A x=1)可表示成命题公式(E(0)A 0=1)V (E(1)A 仁1)其中E(0)A 0=1 假，E(1)A 1 = 1 也假，故(E(0)A 0=1)V (E(1)A 仁1)假。
(4)x(E(x) f x二真x(E(x) f x可表示成命题公式(E(0) f 0=^(E(1)f 仁1)其中E(0) f 0二假，但E(1) f仁真，故(E(0) f 0=1^ (E(1) f仁真。
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•用谓词公式将下列语句形式化:( 1) xx 是xx 的首都。
(2) xx 是数学家，但不是文学家。
(3)不劳动者不得食。
( 4)人无完人。
( 5)发亮的xx 不都是金子。
(6)天下乌鸦一般黑。
( 7)一个数既是偶数又是质数，当且仅当该数为2。
(8)有的猫不捉耗子，会捉耗子的猫便是好猫。
(9)凡成功者都xx,但反之不然。
( 10)有的汽车比有的火车跑得快。
( 11)一个人如果不相信所有其他人,那么他也就不可能得到其他人的信任。
( 12)不是所有的男人都至少比一个女人高,但至少有一个男人比所有的女人高。
解:( 1) xx 是xx 的首都；C(x,y表示“X是y的首都” w表示华盛顿” a表示美国，原句可表示为C(w,a)( 2) xx 是数学家,但不是文学家。
解:M(x)表示“X是数学家” A(x)表示“X是天文学家” g表示高斯”原句可表示为M(g)A n A(g)(3)W(x)表示“是劳动的” F(x)表示“是可以得到食物的”原句可表示为x( n W (x) n F(x))(4)人无完人。
解：M(x)表示“是人” P(x)表示“是完美的”原句可表示为n x(M(x)A P(x)或者x ( M(x)门P(x))(5)L(x)表示“是发亮的” G(x)表示“是金子”原句可表示为n x(L (x) - G(x))(6)天下乌鸦一般黑。
解：W(x)表示“是乌鸦” B(x)表示“是黑的的”原句可表示为x(W (x) - B或者n x (W(x)An B(x))(7)O(x)表示“是奇数” E(x)表示“是偶数”原句可表示为x(O(x)A E(x) x=2)(8)有的猫不捉耗子，会捉耗子的猫便是好猫。
解：C(x)表示“是猫” M(x)表示“是耗子” G(x)表示“是好的” K(x,y)表示“x 会捉y”原句可表示为x(C (x A y(M (y) -n K(x^)))x (C (x A y(M (y)- K(x,y)) - G(x))(9)S(x)表示“是成功” H(x)表示“是努力奋斗的”原句可表示为x(S(x) —H(A)n x(H(x) —S(x))(10)有的汽车比有的火车跑得快。
解：C(x)表示“是汽车” T(x)表示“是火车” F(x,y表示“X匕y快”原句可表示为x(C (x)A y(T (y)A F(x,y)))(11)M(x)表示“是人” B(x,y)表示“相信y”原句可表示为x(M (x)A n y(M(y) A x工A B(x,y)) -7(M(y) A x^y B(y,x)))(12)M(x)表示“是男人” F(x)表示“是女人” H(x,y)表示“比y高”原句可表示为n x(M (x) -y(F(y)A H(x,y)))A x(M (x)A y(F(y) - H(x,y)))5. 量词！表示有且仅有” !xP(x)表示有且仅有一个个体满足谓词P(x)b 试用量词，，，等号“圾谓词P(x)表示!P(x)，即写出一个通常的谓词公式使之与！xP(x具有相同的意义。
解：!xP(x)可用以下具有相同的意义的谓词公式表示x (P(x)A y (P(y) - y=x)6. f(x)为一实函数当且仅当对每一实数x都有且只有一个实数y满足y二f(x) (不得使用量词!b “f(＞为实函数”可译为RF(f))b解：RF(f ) x y(y = f(x)A n z(z #y z= f(x)))练习5.21•设个体域D= d1,,,dn ，试用消去量词的方法证明下列基本逻辑等价式:(1)n xA(x) x n A(x)解：n xA(x)n (A (d1) A A (d2) A , A A (dn))nA( d1) VnA(d2) V , VnA( dn)x n A(x)(2)xA(x)A P x(A(x)A P) (P 为命题常元)解：xA(x)A P(A (d1) A A (d2) A , A A (dn)) A P(A (d1) A P) A (A (d2) A P) A , A (A (dn) A P)x(A(x)A P)(3)xA(x)V x B(x)x(A(x)V B(x)) 解：xA(x)V x B(x)(A (d1) V A (d2) V , V A (dn))V( B (d1) V B (d2) V , V B (dn))(A (d1) V B (d1) )V( A (d2) V B (d2)) V , V (A (dn) V B (dn))x(A(x)V B(x))11 /102•证明下列逻辑蕴涵式及逻辑等价式：(1) x y(P(x) Q(y))x P(x —> 证明：x y(P(x) Q(y))x y( n PMQ(y))x ( n P(x )y Q(y))x n P(^) y Q(y)n x P(x)V y Q(y)x P(x) y Q(y)(2) x y(P(x) Q(y))x P(x —>证明：x y(P(x) - Q(y))x y( n P V )Q(y))x ( n P V x) y Q(y))x n P(V ) y Q(y)n x P(x)V y Q(y)x P(x) t Q(y) y Q(y) y Q(y)。