离散习题(附答案

1、习题 2.1 1将下列命题符号化。 (1) 4 不是奇数。 解：设 A(x)：x 是奇数。a：4。 “4 不是奇数。 ”符号化为：A(a) (2) 2 是偶数且是质数。 解：设 A(x)：x 是偶数。B(x)：x 是质数。a：2。 “2 是偶数且是质数。 ”符号化为：A(a)B(a) (3) 老王是山东人或河北人。 解：设 A(x)：x 是山东人。B(x)：x 是河北人。a：老王。 “老王是山东人或河北人。 ”符号化为：A(a)B(a) (4) 2 与 3 都是偶数。 解：设 A(x)：x 是偶数。a：2，b：3。 “2 与 3 都是偶数。 ”符号化为：A(a)A(b) (5) 5 大于 3。

2、 解：设 G(x,y)：x 大于 y。a：5。b：3。 “5 大于 3。 ”符号化为：G(a,b) (6) 若 m 是奇数，则 2m 不是奇数。 解：设 A(x)：x 是奇数。a：m。b：2m。 “若 m 是奇数，则 2m 不是奇数。 ”符号化为：A(a)A(b) (7) 直线 A 平行于直线 B 当且仅当直线 A 不相交于直线 B。 解：设 C(x,y)：直线 x 平行于直线 y。设 D(x,y)：直线 x 相交于直线 y。a：直线 A。b：直 线 B。 “直线 A 平行于直线 B 当且仅当直线 A 不相交于直线 B。 ”符号化为：C(a,b)D(x,y) (8) 小王既聪明又用功，但身体不

3、好。 解：设 A(x)：x 聪明。B(x)：x 用功。C(x)：x 身体好。a：小王。 “小王既聪明又用功，但身体不好。 ”符号化为：A(a)B(a)C(a) (9) 秦岭隔开了渭水和汉水。 解：设 A(x,y,z)：x 隔开了 y 和 z。a：秦岭。b：渭水。c：汉水。 “秦岭隔开了渭水和汉水。 ”符号化为：A(a,b,c) (10) 除非小李是东北人，否则她一定怕冷。 解：设 A(x)：x 是东北人。B(x)：x 怕冷。a：小李。 “除非小李是东北人，否则她一定怕冷。 ”符号化为：B(a)A(a) 2将下列命题符号化。并讨论它们的真值。 (1) 有些实数是有理数。 解：设 R(x)：x 是

4、实数。Q(x)：x 是有理数。 “有些实数是有理数。 ”符号化为：(x)(R(x)Q(x) 它的真值为：真。 (2) 凡是人都要休息。 解：设 R(x)：x 是人。S(x)：x 要休息。 “凡是人都要休息。 ”符号化为：(x)(R(x)S(x) 它的真值为：真。 (3) 每个自然数都有比它大的自然数。 解：设 N(x)：x 是自然数。G(x,y)：x 比 y 大。 “每个自然数都有比它大的自然数。 ”符号化为：(x)(N(x)(y)(N(y)G(y,x) 它的真值为：真。 (4) 乌鸦都是黑的。 解：设 A(x)：x 是乌鸦。B(x)：是黑的。 “乌鸦都是黑的。 ”符号化为：(x)(A(x)B

5、(x) 它的真值为：真。 (5) 不存在比所有火车都快的汽车。 解：设 A(x)：x 是汽车。B(x)：是火车。K(x,y)：x 比 y 快。 “不存在比所有火车都快的汽车。 ”符号化为：(x)(A(x)(y)(B(y)K(x,y) 它的真值为：真。 (6) 有些大学生不佩服运动员。 解：设 S(x)：x 是大学生。L(x)：是运动员。B(x,y)：x 佩服 y。 “有些大学生不佩服运动员。 ”符号化为：(x)(S(x)L(y)B(x,y) 它的真值为：真。 (7) 有些女同志既是教练员又是运动员。 解：设 W(x)：x 是女同志。J(x)：x 是教练员。L(x)：x 是运动员。 “有些女同志

6、既是教练员又是运动员。 ”符号化为：(x)(W(x)J(x)L(x) 它的真值为：真。 (8) 除 2 以外的所有质数都是奇数。 解：设 A(x)：x 是质数。B(x)：x 是奇数。C(x,y)：x 不等于 y。 “除 2 以外的所有质数都是奇数。 ”符号化为：(x)(A(x)C(x,2)B(x) 它的真值为：真。 3指出一个个体域，使下列被量化谓词的真值为真，该个体域是整数集合的最大子集。在 以下各题中，A(x)表示：x0，B(x)表示：x=5，C(x,y) 表示：xy=0 (1) (x)A(x) 解：正整数集合 Z+。 (2) (x)A(x) 解：整数集合 Z。 (3) (x)B(x) 解

7、：集合5 。 (4) (x)B(x) 解：整数集合 Z。 (5) (x)(y)C(x,y) 解：整数集合 Z。 4分别在全总个体域和实数个体域中，将下列命题符号化。 (1) 对所有的实数 x，都存着实数 y，使得 xy=0 解：设 R(x)：x 是实数。B(x,y)：xy=0。 在实数个体域符号化为：(x)(y)B(x,y) 在全总个体域符号化为：(x)(R(x)(y)(R(y)B(x,y) (2) 存在着实数 x，对所有的实数 y，都有 xy=0 解：设 R(x)：x 是实数。B(x,y)：xy=0。 在实数个体域符号化为：(x)(y)B(x,y) 在全总个体域符号化为：(x)(R(x)(y

8、)(R(y)B(x,y) (3) 对所有的实数 x 和所有的实数 y，都有 xy=yx 解：设 R(x)：x 是实数。B(x,y)：x=y。 在实数个体域符号化为：(x)(y)B(x+y,y+x) 在全总个体域符号化为：(x)(R(x)(y)(R(y)B(x+y,y+x) (4) 存在着实数 x 和存在着实数 y，使得 xy=100 解：设 R(x)：x 是实数。B(x,y)：xy=100。 在实数个体域符号化为：(x)( y)B(x,y) 在全总个体域符号化为：(x)(R(x)(y)(R(y)B(x,y) 习题 2.2 1. 指出下列公式中的约束变元和自由变元。 (1) (x)(P(x)Q(

9、y) 解：约束变元：x，自由变元：y (2) (x)(P(x)R(x)(x)P(x)Q(x) 解：约束变元：x，自由变元：x (3) (x)(P(x)(x)Q(x)(x)R(x,y)Q(z) 解：约束变元：x，自由变元：y，z (4) (x)(y) (R(x,y)Q(z) 解：约束变元：x，y，自由变元：z (5) (z) (P(x)(x)R(x,z)(y)Q(x,y)R(x,y) 解：约束变元：x，y，z，自由变元：x，y 2. 对下列谓词公式中的约束变元进行换名。 (1) (x)(y)(P(x,z)Q(x,y)R(x,y) 解：将约束变元 x 换成 u：(u)(y)(P(u,z)Q(u,y

10、)R(x,y) 将约束变元 y 换成 v：(x)(v)(P(x,z)Q(x,v)R(x,y) (2) (x)(P(x)(R(x)Q(x,y)(x)R(x)(z)S(x,z) 解：将前面的约束变元 x 换成 u，后面的约束变元 x 换成 v： (u)(P(u)(R(u)Q(u,y)(v)R(v)(z)S(x,z) 将约束变元 z 换成 w：(x)(P(x)(R(x)Q(x,y)(x)R(x)(w)S(x,w) 3. 对下列谓词公式中的自由变元进行代入。 (1) (y)Q(z,y)(x)R(x,y)(x)S(x,y,z) 解：将自由变元 z 用 u 代入：(y)Q(u,y)(x)R(x,y)(x)

11、S(x,y,u) 将自由变元 y 用 v 代入：(y)Q(z,y)(x)R(x,v)(x)S(x,v,z) (2) (y)P(x,y)(z)Q(x,z)(x)R(x,y) 解：将自由变元 x 用 u 代入：(y)P(u,y)(z)Q(u,z)(x)R(x,y) 将自由变元 y 用 v 代入：(y)P(x,y)(z)Q(x,z)(x)R(x,v) 4. 利用谓词公式对下列命题符号化。 (1) 每列火车都比某些汽车快。 解：设 A(x)：x 是火车。B(x)：x 是汽车。C(x,y)：x 比 y 快。 “每列火车都比某些汽车快。 ”符号化为：(x)(A(x)(y)(B(y)C(x,y) (2) 某

12、些汽车比所有火车慢。 解：设 A(x)：x 是火车。B(x)：x 是汽车。C(x,y)：x 比 y 快。 “某些汽车比所有火车慢。 ”符号化为： (x)(B(x)(y)(A(y)C(y,x) (3) 对每一个实数 x，存在一个更大的实数 y。 解：设 R(x)：x 是实数。G(x,y)：x 比 y 大。 “对每一个实数 x，存在一个更大的实数 y。 ”符号化为：(x)(R(x)(y)(R(y)G(y,x) (4) 存在实数 x，y 和 z，使得 x 与 y 之和大于 x 与 z 之积。 解：设 R(x)：x 是实数。G(x,y)：x 比 y 大。 “存在实数 x，y 和 z，使得 x 与 y

13、之和大于 x 与 z 之积。 ”符号化为： (x)(y)(z)(R(x)R(y)R(z)G(x+y,xz) (5) 所有的人都不一样高。 解：设 R(x)：x 是人。G(x,y)：x 和 y 一样高。 “所有的人都不一样高。 ”符号化为：(x)(y)(R(x)R(y)G(x,y) 5. 自然数一共有下述三条公理： a) 每个数都有惟一的一个数是它的后继数。 b) 没有一个数使数 1 是它的后继数。 c) 每个不等于 1 的数都有惟一的一个数是它的直接先驱数。 用两个谓词表达上述三条公理。 注：设 n 是不等于 1 的自然数，则 n1 是 n 的后继数，n1 是 n 的先驱数。 解：设 A(x)

14、：x 是数。B(x,y)：x 是 y 后继数(根据定义，也可理解为 y 是 x 先驱数)。 a) “每个数都有惟一的一个数是它的后继数。 ”符号化为： (x)(A(x)(y)(A(y)B(y,x)(z)(A(z)B(z,x)(z=y) b) “没有一个数使数 1 是它的后继数。 ”符号化为：(x)(A(x)B(1,x) c) “每个不等于 1 的数都有惟一的一个数是它的直接先驱数。 ”符号化为： (x)(A(x)(x=1)(y)(A(y)B(x,y)(z)(A(z)B(x,z)(z=y) 6. 取个体域为实数集 R，函数 f 在 a 点连续的定义是：对每个 0，存在一个 0，使 得对所有 x，

15、若|xa|，则|f(x)f(a)|。试把此定义用符号化的形式表达出来。 解：() (0)()( (0)(x) (|xa|)(|f(x)f(a)|) 7.若定义惟一性量词(!x)为“存在惟一的一个 x” ，则(!x)P(x)表示“存在惟一的一个 x 使 P(x)为真” 。试用量词，谓词及逻辑运算符表示(!x)P(x)。 解：(!x)P(x)(x)P(x)(y)P(y)(y=x) 习题 2.3 1. 设个体域为 D=1,2,3，试消去下列各式的量词。 (1) (x)P(x) 解：(x)P(x)P(1)P(2)P(3) (2) (x)P(x)(y)Q(y) 解：(x)P(x)(y)Q(y)(P(1)

16、P(2)P(3)(Q(1)Q(2)Q(3) (3) (x)P(x)(y)Q(y) 解：(x)P(x)(y)Q(y)(P(1)P(2)P(3)(Q(1)Q(2)Q(3) (4) (x)(P(x)Q(x) 解：(x)(P(x)Q(x)(P(1)Q(1)(P(2)Q(2)(P(3)Q(3) (5) (x)P(x)(y)Q(y) 解：(x)P(x)(y)Q(y) (P(1)P(2)P(3)(Q(1)Q(2)Q(3) 2. 求下列各式的真值。 (1) (x)(y)H(x,y) 其中 H(x,y)：xy，个体域为 D=4,2 解：(x)(y)H(x,y)(y)H(2,y)(y)H(4,y) (H(2,2)

17、H(2,4)(H(4,2)H(4,4) (00)(10)010 (2) (x)(S(x)Q(a)p 其中 S(x)：x3，Q(x)：x=5，a：3，p：53，个体域为 D=- 1,3,6 解：(x)(S(x)Q(a)p(S(-1)Q(3)(S(3)Q(3)(S(6)Q(3)(53) (00)(00)(10)1 (110)1111 (3) (x)(x2-2x+1=0) 其中个体域为 D=-1,2 解：(x)(x2-2x+1=0)(1)22(1)1=0)(22221=0) (4=0)(1=0)000 3. 证明下列各式。其中：B 是不含变元 x 的谓词公式。 (1) (x)(S(x)R(x)(x)

18、S(x)(x)R(x) 证明：(x)(S(x)R(x)(x)(S(x)R(x) (x)S(x)(x)R(x) (x)S(x)(x R(x) (x)S(x)(x)R(x) (2) (x)(y)(S(x)R(y)(x)S(x)(y)R(y) 证明：(x)(y)(S(x)R(y)(x)(y)(S(x)R(y) (x)S(x)(y)R(y) (x)S(x)(y)R(y) (x)S(x)(y)R(y) (3) (x)(A(x)B)(x)A(x)B 证明：(x)(A(x)B)(x)(A(x)B)(x)A(x)B (x)A(x)B(x)A(x)B (4) (x)(BA(x)B(x)A(x) 证明：(x)(B

19、A(x)(x)(BA(x)B(x)A(x)B(x)A(x) (5) (x)(A(x)B(x)(x)A(x)(x)B(x) 证明：因为(x)(A(x)B(x)，所以对于任意个体 c，A(c)B(c)和 A(c)，从而有 B(c)，由 c 的任意性有(x)B(x)，根据 CP 规则，(x)(A(x)B(x)(x)A(x)(x)B(x) (6) (x)(A(x)B(x)(x)A(x)(x)B(x) 证明：(x)(A(x)B(x)(x)(A(x)B(x)(B(x)A(x) (x)(A(x)B(x)(x)(B(x)A(x) (x)(A(x)B(x)(x)(B(x)A(x)(x)(A(x)B(x)(x)A

20、(x)(x)B(x) 同理，(x)(A(x)B(x)(x)(B(x)A(x)(x)B(x)(x)A(x) 所以，(x)(A(x)B(x)(x)(B(x)A(x)(x)A(x)(x)B(x)(x)B(x)(x)A(x) 而(x)A(x)(x)B(x)(x)B(x)(x)A(x)(x)A(x)(x)B(x) 故有(x)(A(x)B(x)(x)A(x)(x)B(x) 4. 判断下列证明是否正确。 (x) (A(x)B(x)(x) (A(x)B(x)(x)(A(x)B(x) (x) (A(x)B(x)(x) A(x)(x)B(x) (x) A(x)(x)B(x)(x) A(x)(x)B(x) (x)

21、A(x)(x)B(x) 解：下列的推理是错的：(x) (A(x)B(x)(x)A(x)(x)B(x) 习题 2.4 1. 求下列各式的前束范式。 (1) (x)P(x)(x)Q(x) 解：(x)P(x)(x)Q(x)(x)P(x)(x)Q(x)(x)(P(x)Q(x) (2) (x)P(x)(x)Q(x) 解：(x)P(x)(x)Q(x)(x)P(x)(x)Q(x) (x)P(x)(y)Q(y) (x)(y) (P(x)Q(y) (3) (x)(y)(z)A(x,y,z)(u)B(x,u)(v)B(x,v) 解：(x)(y)(z)A(x,y,z)(u)B(x,u)(v)B(x,v) (x)(y

22、)(z)(u)(A(x,y,z)B(x,u)(v)B(x,v) (x)(y)(z)(u)(v)(A(x,y,z)B(x,u)B(x,v) (4) (x)(y)(z)(A(x,z)B(x,z)(u)R(x,y,u) 解：(x)(y)(z)(A(x,z)B(x,z)(u)R(x,y,u) (x)(y)(z)(u)(A(x,z)B(x,z)R(x,y,u) (5) (x)(y)A(x,y)(x)(y)(B(x,y)(y)(A(y, x)B(x,y) 解：(x)(y)A(x,y)(x)(y)(B(x,y)(y)(A(y, x)B(x,y) (x)(y)A(x,y)(x)(y)(B(x,y)(z)(A(

23、z,x)B(x,z) (x)(y)A(x,y)(u)(v)(z)(B(u,v)(A(z,u)B(u,z) (x)(y)(u)(v)(z)(A(x,y)(B(u,v)(A(z,u)B(u,z) (x)(y)(u)(v)(z)(A(x,y)(B(u,v)(A(z,u)B(u,z) 2. 求下列各式的前束合取范式。 (1) (x)(P(x)(z)Q(z,y)(y)R(x,y) 解：(x)(P(x)(z)Q(z,y)(y)R(x,y) (x)(z)(P(x)Q(z,y)(y)R(x,y) (x)(z)(P(x)Q(z,y)(u)R(x,u) (x)(z)(u)(P(x)Q(z,y)R(x,u) (x)

24、(z)(u)(P(x)Q(z,y)R(x,u) (x)(z)(u)(P(x)Q(z,y)R(x,u) (x)(z)(u)(P(x)R(x,u)(Q(z,y)R(x,u) (2) (x)(y)(P(x,y)Q(y,z)(x) R(x,y) 解：(x)(y)(P(x,y)Q(y,z)(x) R(x,y) (x)(u)(P(x,u)Q(u,z)(v)R(v,y) (x)(u)(v)(P(x,u)Q(u,z)R(v,y) (x)(u)(v)(P(x,u)R(v,y)(Q(u,z)R(v,y) (3) (y)Q(z,y)(x)R(x,y)(x)S(x,y,z) 解：(y)Q(z,y)(x)R(x,y)(

25、x)S(x,y,z) (u)Q(z,u)(x)R(x,y)(v)S(v,y,z) (u)(x)(v)(Q(z,u)R(x,y)S(v,y,z) (u)(x)(v)(Q(z,u)R(x,y)S(v,y,z) 3. 求下列各式的前束析取范式。 (1) (x)(P(x)(y)(x)Q(x,y)(z)R(x,y,z) 解：(x)(P(x)(y)(x)Q(x,y)(z)R(x,y,z) (x)(P(x)(y)(x)Q(x,y)(z)R(x,y,z) (x)(P(x)(y)(u)(z)(Q(u,y)R(x,y,z) (x)(y)(u)(z)(P(x)(Q(u,y)R(x,y,z) (x)(y)(u)(z)

26、(P(x)Q(u,y)R(x,y,z) (2) (x)(y)(P(x,y)Q(y,z)(x)R(x,y) 解：(x)(y)(P(x,y)Q(y,z)(x)R(x,y) (x)(u)(P(x,u)Q(u,z)(v)R(v,y) (x)(u)(v)(P(x,u)Q(u,z)R(v,y) (x)(u)(v)(P(x,u)R(v,y)(Q(u,z)R(v,y) (3) (y)Q(z,y)(x)R(x,y)(x)S(x,y,z) 解：(y)Q(z,y)(x)R(x,y)(x)S(x,y,z) (u)Q(z,u)(x)R(x,y)(x)S(x,y,z) (u)(x)(Q(z,u)R(x,y)(x)S(x,

27、y,z) (u)(x)(Q(z,u)R(x,y)(v)S(v,y,z) (u)(x)(v)(Q(z,u)R(x,y)S(v,y,z) 习题 2.5 1证明下列各式。 (1) (x)(F(x)(G(y)R(x)，(x)F(x)(x)(F(x)R(x) 证明： (x)F(x)P F(c)ES (x)(F(x)(G(y)R(x)P F(c)(G(y)R(c)US G(y)R(c)T假言推理 R(c)T化简律 F(c)R(c)T合取引入 (x)(F(x)R(x)EG (2) (x)(F(x)G(x)，(x)(R(x)G(x)(x)(R(x) F(x) 证明： (x)(R(x)G(x)P R(c)G(c

28、)US (x)(F(x)G(x)P F(c)G(c)US G(c)F(c)T假言易位式 R(c)F(c)T假言三段论 (x)(R(x)F(x)UG (3) (x)(F(x)G(x)，(x)(G(x)R (x)，(x)R(x)(x)F(x) 证明： (x)R(x)P R(c)US (x)(G(x)R(x)P G(c)R(c)US G(c)T拒取式 (x)(F(x)G(x)P F(c)G(c)US F(c)T析取三段论 (x)F(x)UG (4) (x)F(x)(y)(F(y)G(y)R(y)，(x)F(x)(x)R(x) 证明： (x)F(x)P F(c)ES (x)F(x)(y)(F(y)G(

29、y)R(y)P (y)(F(y)G(y)R(y)T假言推理 (F(c)G(c)R(c)US F(c)G(c)T附加律 R(c)T假言推理 (x)R(x)UG 2用 CP 规则证明下列各式。 (1) (x)(F(x)R(x)(x)F(x)(x)R(x) 证明： (x)F(x)P(附加前提) F(c)US (x)(F(x)R(x)P F(c)R(c)US R(c) T假言推理 (x)R(x)UG (x)F(x)(x)R(x)CP (2) (x)(F(x)G(x)，(x)(G(x)R(x)(x)R(x)(x)F(x) 证明： (x)R(x)P(附加前提) R(c)US (x)(G(x)R(x)P (

30、x)(G(x)R(x)T量词否定等价式 (G(c)R(c) US G(c)R(c)T德摩根律 G(c)T析取三段论 (x)(F(x)G(x)P F(c)G(c)US F(c)T析取三段论 (x)F(x)UG (x)R(x)(x)F(x)CP (3) (x)(F(x)G(x)，(x)(G(x)R(x) (x)R(x)(x)F(x) 证明： (x)R(x)P(附加前提) (x)R(x) T量词否定等价式 R(c)ES (x)(G(x)R(x)P G(c)R(c)US G(c)T析取三段论 (x)(F(x)G(x)P F(c)G(c)US F(c)T拒取式 (x)F(x)EG (x)R(x)(x)F

31、(x)CP 3用归谬法证明下列各式。 (1) (x)(F(x)G(x)(x)F(x)(x)G (x) 证明： (x)F(x)(x)G (x)P(附加前提) (x)F(x)(x)G (x) T德摩根律 (x)F(x)(x)G (x)T量词否定等价式 (x)F(x)T化简律 F(c)ES (x)G(x)T化简律 G(c)US (x)(F(x)G(x)P F(c)G(c)US F(c)T析取三段论 F(c)F(c)(矛盾)T合取引入 (2) (x)(F(x)G(x)，(x)(G(x)R (x)，(x)R(x)(x)F(x) 证明： (x)F(x)P(附加前提) (x)F(x) T量词否定等价式 F(

32、c)ES (x)(F(x)G(x)P F(c)G(c)US G(c)T析取三段论 (x)(G(x)R(x)P G(c)R(c)US R(c)T假言推理 (x)R(x)P R(c)US R(c)R(c)(矛盾)T合取引入 (3) (x)(F(x)G(x)，(x)(G(x)R(x)， (x)R(x) (x)F(x) 证明： (x)R(x) P R(c)ES (x)F(x)P(附加前提) (x)F(x) T量词否定等价式 F(c)US (x)(F(x)G(x)P F(c)G(c)US G(c)T假言推理 (x)(G(x)R(x)P G(c)R(c)US R(c)T析取三段论 R(c)R(c)(矛盾)T合取引入 4证明下面推理。 (1) 每个有理数都是实数。有的有理数是整数。因此，有的实数是整数。 解：首先将命题符号化： Q(x)：x 是有理数。 R(x)：x 是实数。 Z(x)：x 是整数。 本题要证明：(x)(Q(x)R(x), (x)(Q(x)Z(x)(x)(R(x)Z(x) 证明： (x)