离散数学 第2章习题答案

《离散数学 第2章习题答案》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第2章谓词逻辑第2章习题答案1.解(1)设F(x)表示“x犯错误”，N(x)表示“x为人”，则此语句符号化为：Ø$x(N(x)∧ØF(x))。(2)设F(x)表示“x是推理”，M(x)表示“x是计算机”，H(x，y)表示“x能由y完成”，则此语句符号化为：Ø"x(F(x)®$yM(y)∧H(x，y))。(3)设C(x)表示“x是计算机系的学生”，D(x)表示“x学习离散数学”，则此语句符号化为："x(C(x)®D(x))。(4)因原语句与“一切自然数x，都有一个自然数y，使得y是x的后继数；并且对任意自然数x，当y和z都是x的后继时

2、，则有y＝z”的意思相同，所以原语句可符号化为："x(N(x)®$y(N(y)∧M(x，y)))∧"x"y"z(N(x)∧N(y)∧N(z)®(M(x，y)∧M(x，z)®(y＝z)))其中N(x)表示x是自然数，M(x，y)表示y是x的后继数。(5)设S(x，y，z)表示“x＋y＝z”，则此语句符号化为："x"y$zS(x，y，z)。(6)设Z(x)表示“x是整数”，S(x，y)表示“xy＝0”，T(x，y)表示“x＝y”，则此语句符号化为："x"y(Z(x)∧Z(y)®(S(x，y)®T(x，0)∨T(y，0)))。(7)设E(

3、x)表示“x是偶数”，P(x)表示“x是素数”，S(x，y)表示“x＝y”，则此语句符号化为："x(E(x)∧P(x)®"y(E(y)∧P(y)®S(x，y)))。(8)设E(x)表示“x是偶数”，O(x)表示“x是奇数”，N(x)表示“x是自然数”，则此语句符号化为：Ø$x(E(x)∧O(x)∧N(x))。(9)设R(x)表示“x是实数”，Q(x)表示“x是有理数”，Z(x)表示“x是整数”，则此语句符号化为：$x(R(x)∧Q(x)∧ØZ(x))。(10)设R(x)表示“x是实数”，Q(x，y)表示“y大于x”，则此语句符号化为

4、："x(R(x)®$Øy(R(y)∧Q(x，y)))。2.解(1)符号化为："y(E(1，y)®"xP(x，y，x))。(2)符号化为："x"y(ØP(x，y，0)®(ØE(x，0)∧ØE(0，y)))。(3)符号化为："x"y(ØP(x，y，0)®(E(x，0)∧E(0，y)))。(4)符号化为："x"y(((E(x，y)∨G(y，x))∧((E(x，y)∨G(x，y)))®E(x，y))。3.解(1)存在x，x是偶数，且x整除6。(2)对任意x，如果x是奇数，则对任意y，若y是素数，则x不整除y。(3)对任意x，如果x不是偶数，

5、则2不整除x。(4)对任意x，如果x是偶数，则对任意y，若x整除y，则y是偶数。4.解(1)在公式"x(P(x)∧$xQ(x))∨("x(P(x)®Q(x))中，第一次出现的"x的辖域为P(x)∧$xQ(x)，$x的辖域为Q(x)，而第二次出现的"x的辖域为P(x)®Q(x)。公式中只出现了变元x，所有x都是约束变元。(2)在公式"x(P(x，y)∧$yQ(y))∧("xR(x)®Q(x))中，第一次出现的"x的辖域为P(x，y)∧$yQ(y)，12第2章谓词逻辑而第二次出现的"x的辖域为R(x)，$y的辖域为Q(y)。P(x，y)

6、中的y是自由变元，x是约束变元。Q(y)中的y是约束变元。R(x)中的x是约束变元，而Q(x)中的x是自由变元。(3)在公式"x(P(x，y)∨Q(z))∧$y(R(x，y)®"zQ(z))，"x的辖域为P(x，y)∨Q(z)，$y的辖域为R(x，y)®"zQ(z)，"z的辖域为Q(z)。公式中第一次出现的x是约束变元，第二次出现的x是自由变元，第一次出现的y和z都是自由变元，而第二次出现的y和z都是约束变元。5.解"x(P(x，y)∧$yQ(y)∧M(x，y))∧("xR(x)®Q(x))Û"u(P(u，y)∧$yQ(y)∧M(u

7、，y))∧("xR(x)®Q(x))Û"u(P(u，y)∧$vQ(v)∧M(u，y))∧("xR(x)®Q(x))Û"u(P(u，y)∧$vQ(v)∧M(u，y))∧("wR(w)®Q(x))6.解$y(P(x，y)®("zQ(x，y)∧R(x，y，z)))∧"x$zS(x，y，z)Û$y(P(u，y)®("zQ(u，y)∧R(u，y，z)))∧"x$zS(x，y，z)Û$y(P(u，y)®("zQ(u，y)∧R(u，y，z)))∧"x$zS(x，v，z)Û$y(P(u，y)®("zQ(u，y)∧R(u，y，z)))∧"x$wS(x

8、，v，w)7.解(1)"xF(f(a，x)，a)Û"x(f(a，x)＜a)Û"x(a－x＜a)Û"x(0－x＜0)Û"x(0＜x)ÛF(2)"x"y(ØF(f(x，y)，x))Û"x"y(Ø(f(x，y)＜x))Û"x"y(Ø(x－y