计算机科学中离散结构04(完成).doc

第4章 逻辑代数（下）--谓词演算

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))Ù$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 是偶数" ：
（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) 真

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、量词 $ 表示"有且仅有" $ xP(x)表示有且仅有一个个体满足谓词 P(x)。试用量词， ，
", $,等号"="及谓词 P(x),表示 $ P(x)，即写出一个通常的谓词公式使之与$ xP(x)具有相同
的意义。
解 $ xP(x) 具有相同的意义的谓词公式表示
$x P(x) Ù"y P(y)®y=x） ）

5、设个体域为整数集，试确定两个谓词 P(x,y)，分别使得下列两个蕴涵式假：
（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) 为假(*
整数 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 "x (x y<0)
解（1）对正整数集个体域，"x(x>0)为真
（2）对{5 6} "x(x=5Úx=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)）
" 。

2

解（1）"x"y(x2+y2=0®x=0y=0) 。
（2）RF(f )«"x $y(y = f(x)Ù┐$z(z

8、用谓词公式将下列语句形式化：
（1）高斯是数学家，但不是文学家。
（2）没有一个奇数是偶数。


Ùz= f(x)))

（3）一个数既是偶数又是质数，当且仅当该数为 2。
（4）有的猫不捉耗子，会捉耗子的猫便是好猫。
（5）党指向哪里，我们就奔向那里。
（6）发亮的东西不都是金子。
（7）不是所有的男人都至少比一个女人高，但至少有一个男人比所有的女人高。
（8）一个人如果不相信所有其他人，那么他也就不可能得到其他人的信任。
（9）君子坦荡荡，小人长戚戚。 （孔子）
（10）谁要是游戏人生，他就一事无成；谁不能主宰自己，他就是一个奴隶。 （歌德）
解（1）M(x) 表示"x 是数学家" 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）Q(x,y) 表示"x 指向 y" J(x,y) 表示"x 奔向 y" party 表示"党" ，we 表示"我
， ，
们",原句可表示为
"x(Q(party，x)®J(we, x))

（6）G(x) 表示"x 是金子" L(x) 表示"x 是发亮的" ,原句可表示为 ，
┐"x(L (x)®G(x))
（7）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)))
（8）M(x) 表示"x 是人" B(x,y)表示"x 相信 y", 原句可表示为 ，
"x(M (x)Ù┐$y(M(y)Ùx ÙB(x,y))®┐$y(M(y)Ùx ÙB(y,x)))
（9）M(x) 表示"x 是人" J(x) 表示"x 是君子" X(x) 表示"x 是小人" A(x) 表示
， ， ，
"x 坦荡荡" S(x) 表示"x 长戚戚"
， ，原句可表示为
"x(M (x)ÙJ(x)®A (x)) Ù"x(M (x)ÙX(x)®S (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(x,x)®N(x))

9、 利用量词意义或利用已经证明了的永真式（逻辑蕴涵式，逻辑等价式）及几个基本原
理，证明 4.2.2 节第（2）—（8）组永真式中尚未证明的各式。

3