离散数学课后习题合集(5)

第三章 谓词演算基础

3.1试把下列语句符号化

（1）如果我知道你不在家，我就不去找你了。

解

设A(e1,e2)表示e1知道e2不在家；

B(e1,e2)表示e1去找e2； a表示我；b表示你；

则原句表示为：

A(a,b)??B(a,b)。

（2）他送给我这只大的红气球。

解

设A(e1,e2,e3)表示e1送给e2e3；

B(e)表示e为大的； C(e)表示e为红的； D(e)表示e为气球；

a表示他，b表示我，c表示这只； 则原句译为：

A(a,b,c)?B(c)?C(c)?D(c)。

（3）苏州位于南京与上海之间。

解

设A(e1,e2,e3)表示e1位于e2与e3之间；

a表示苏州，b表示南京，c表示上海； 则原句表示为：

A(a,b,c)。

（4）他既熟悉C++语言，又熟悉PASCAL语言。

解

设A(e1,e2)表示e1熟悉e2；

a表示他，b表示C++语言，c表示PASCAL语言； 则原句译为：

21

A(a,b)?A(a,c)。

3.2 试将下列语句符号化为含有量词的谓词演算公式： （1）没有不犯错误的人。

解

设P(e)表示e为人；

M(e)表示e为错误； A(e1,e2)表示e1犯e2。

则原句译为：

??x(P(x)??y(M(y)?A(x,y)))。

（2）有不是奇数的质数。

解

设O(e)表示e为奇数；

P(e)表示e为质数。

则原句译为：

?x(?O(x)?P(x))。

（3）尽管有人能干，但未必一切人能干。

解

设P(e)表示e为人；

A(e)表示e能干。

则原句译为：

?x(P(x)?A(x))???x(P(x)?A(x))。

（4）鱼我所欲，熊掌亦我所欲。

解

设F(e)表示e为鱼；

B(e)表示e为熊掌； W(e1,e2)表示e1所欲e2。 a表示我；

则原句表示为：

?x(F(x)?W(a,x))??x(B(x)?W(a,x))。22

（5）人不犯我，我不犯人；人若犯我，我必犯人。

解

设P(e)表示e为人；

C(e1,e2)表示e1犯e2。 a表示我；

则原句译为：

?x((P(x)??C(x,a))??C(a,x))??x((P(x)?C(x,a))?C(a,x))。

（6）有一种液体可熔化任何金属。

解

设L(e)表示e为液体； M(e)表示e为金属；

C(e1,e2)表示e1熔化e2。

则原句可译为：

?x(L(x)??y(M(y)?C(x,y)))。

（7）并非“人为财死，鸟为食亡”。

解 设P(e)表示e为人；

A(e)表示e为财； B(e)表示e为鸟； F(e)表示e为食； C(e1,e2)表示e1为e2死； D(e1,e2)表示e1为e2亡。

则原句译为：

?(?x?y((P(x)?A(y))?C(x,y))??x?y((P(x)?F(y))?D(x,y)))

（8）若要人不知，除非己莫为。

解 设P(e)表示e为人；

A(e)表示e为某一事情；

23

B(e1,e2)表示e1做了e2；

C(e1,e2,e3)表示e1知道e2做了e3。

则原句译为：

?x?y((P(x)?A(y)?B(x,y))??z(P(z)?C(z,x,y)))

（9）任何一数均有一数比它大。

解 设A(e)表示e为数；

B(e1,e2)表示e1比e2大；

则原句译为：

?x(A(x)??y(A(y)?B(y,x)))

（10）每个作家均写过作品。

解 设A(e)表示e为作家；

N(e)表示e为作品； W(e1,e2)表示e1写了e2。

则原句译为：

?x(A(x)??y(N(y)?W(x,y)))

（11）有些作家没写过小说。

解 设A(e)表示e为作家；

N(e)表示e为小说； W(e1,e2)表示e1写了e2。

则原句译为：

?x(A(x)??y(N(y)??W(x,y)))

（12）天下乌鸦一般黑。

解 设A(e)表示e为乌鸦；

B(e1,e2)表示e1与e2一样黑。

24

则原句译为：

?x?y((A(x)?A(y))?B(x,y))

3.3 令P(e)表示“e为质数”；

E(e)表示“e为偶数”； O(e)表示“e为奇数”

； D(e1,e2)表示“e1除尽e2”。

试把下列语句翻译为日常语句：

（1）E(2)?P(2) 解

2为偶数且2为质数。 （2）?x(D(2,x)?E(x)) 解

任何能被2除尽的数均为偶数。 （3）?x(?E(x)??D(2,x))

解

任何不是偶数的数均不能被2除尽。 （4）?x(E(x)??y(D(x,y)?E(y)))

解

任何一个数，若能被任何偶数除尽，则该数一定是偶数。（5）?x(E(x)?P(x))

解

有是偶数的质数。

3.4 指出下列公式的约束关系、自由变元和约束变元：

（1）?x(A(x,y)??y(B(x,y)?C(z))) 解

A(x,y)中的x和B(x,y)中的x受?x约束； B(x,y)中的y受?y约束；

A(x,y)中的x为约束变元，B(x,y)中的x和y为约束变元；A(x,y)中的y和C(z)中的z为自由变元。

25