7 逻辑代数(下)：谓词演算 习题答案

练习5.11. 指出下列谓词公式中的量词及其辖域，指出各自由变元和约束变元，并作适当更改，同时回答它们是否是命题：（1）"x(P(x)∨Q(x))∧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)不是命题公式中x既是自由变元又是约束变元，可更改变元为如下公式："x(P(x)∧Q(x))∧$yS(y)→T(z) （3）全称量词"，辖域 P(x)→$y(B(x,y)∧Q(y))∨T(y)，其中 x为约束变元，存在量词$，辖域B(x,y)∧Q(y)，其中y为约束变元T(y) 中y为自由变元 "x(P(x)→$y(B(x,y)∧Q(y))∨T(y))不是命题公式中y既是自由变元又是约束变元，可更改变元为如下公式："x(P(x)→$y(B(x,y)∧Q(y))∨T(z))不是命题。

4）全称量词"，辖域$x(P(x)∧B(x,y))，其中y为约束变元存在量词$，辖域P(x)∧B(x,y)，其中x为约束变元不在量词辖域中的P(x)（第一个和第三个P(x)）中的x为自由变元P(x)→("y$x(P(x)∧B(x,y))→P(x))不是命题公式中x既是自由变元又是约束变元，可更改变元为如下公式：P(z)→("y$x(P(x)∧B(x,y))→P(z))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. 用谓词公式将下列语句形式化：（1）华盛顿是美国的首都2）高斯是数学家，但不是文学家3）不劳动者不得食4）人无完人 （5）发亮的东西不都是金子6）天下乌鸦一般黑。

7）一个数既是偶数又是质数，当且仅当该数为28）有的猫不捉耗子，会捉耗子的猫便是好猫9）凡成功者都努力奋斗，但反之不然10）有的汽车比有的火车跑得快11）一个人如果不相信所有其他人，那么他也就不可能得到其他人的信任12）不是所有的男人都至少比一个女人高，但至少有一个男人比所有的女人高解:（1）华盛顿是美国的首都；C(x,y)表示“x是y的首都”，w表示“华盛顿”，a表示美国，原句可表示为C(w,a)（2）高斯是数学家，但不是文学家解:M(x) 表示“x是数学家”，A(x) 表示“x是天文学家”，g表示“高斯”，原句可表示为M(g) ∧┐A(g)（3）W(x)表示“x是劳动的”，F(x)表示“x是可以得到食物的” ，原句可表示为"x(┐W (x)à ┐ F(x))（4）人无完人解:M(x) 表示“x是人”，P(x) 表示“x是完美的”，原句可表示为┐$x(M(x)∧P(x)) 或者 "x ( M(x)à┐P(x))（5）L(x) 表示“x是发亮的”，G(x) 表示“x是金子”，原句可表示为┐"x(L (x)→G(x)) （6）天下乌鸦一般黑解:W(x) 表示“x是乌鸦”，B(x) 表示“x是黑的的”，原句可表示为"x(W (x)→B(x)) 或者 ┐$x (W(x)∧┐B(x))（7）O(x) 表示“x是奇数”，E(x) 表示“x是偶数”，原句可表示为"x(O(x)∧E(x) «x=2)（8）有的猫不捉耗子，会捉耗子的猫便是好猫。

解: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))（9）S(x) 表示“x是成功”，H(x) 表示“x是努力奋斗的”，原句可表示为"x(S(x)→H(x)) ∧┐"x(H(x)→S(x))（10）有的汽车比有的火车跑得快解:C(x) 表示“x是汽车”， T(x) 表示“x是火车”，F(x,y) 表示“x比y快”，原句可表示为$x(C (x) ∧$y(T (y)∧F(x,y)))（11）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)))（12）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)))5．量词 $! 表示“有且仅有”，$!xP(x)表示有且仅有一个个体满足谓词P(x)。

试用量词，", $,等号“=”及谓词P(x),表示 $! P(x)，即写出一个通常的谓词公式使之与$!xP(x)具有相同的意义解:$!xP(x)可用以下具有相同的意义的谓词公式表示 $x（P(x) ∧"y（P(y)→y=x））6. f(x)为一实函数当且仅当对每一实数x都有且只有一个实数y满足y = f(x)（不得使用量词 $!f(x)为实函数”可译为RF(f)）解:RF(f )«"x $y(y = f(x)∧┐$z(z≠y∧z= f(x)))练习5.21. 设个体域D={d1,…,dn}，试用消去量词的方法证明下列基本逻辑等价式：（1）┐"xA(x) Û$x┐A(x)解： ┐"xA(x) Û┐（A（d1）∧A（d2）∧…∧A（dn））Û┐A（d1）∨┐A（d2）∨…∨┐A（dn）Û$x┐A(x)（2）"xA(x)∧P Û"x(A(x)∧P) （P为命题常元）解 ："xA(x)∧PÛ（A（d1）∧A（d2）∧…∧A（dn））∧PÛ（A（d1）∧P）∧（A（d2）∧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（d2）∨…∨A（dn））∨（B（d1）∨B（d2）∨…∨B（dn））Û（A（d1）∨B（d1））∨（A（d2）∨B（d2））∨…∨（A（dn）∨B（dn））Û $x(A(x)∨B(x))2. 证明下列逻辑蕴涵式及逻辑等价式：（1）$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)（2）"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)。