《离散数学》习题集

《离散数学》习题集

目 录

第一章 数理逻辑 .................................................................. 2 第二章 集合 ....................................................................... 14 第三章 第三章 第五章 二元关系 ................................................................ 22 二元关系 ................................................................ 36 无限集合 ................................................................ 50

第1页 共53页

第一章 数理逻辑

1.1 命题

1. 设P是命题“天下雪”；Q是命题“我去镇上”；R是命题“我有时间”。 (a) 用逻辑符号写出以下命题：

(i) 如天不下雨和我有时间，那么我去镇上； (ii) 我去镇上，仅当我有时间； (iii) 天不下雪；

(iv) 天正在下雪，我也没去镇上。 (b) 对下述命题用中文写出语句： (i) Q?(R??P)； (ii) R?Q；

(iii) (Q?R)?(R?Q)； (iv) ?(R?Q)。 2. 否定下列命题： (a) 上海处处清洁； (b) 每一个自然数都是偶数。

3. 说出下述每一命题的逆命题和逆反命题： (a) 如果天下雨，我将不去； (b) 仅当你去我将逗留；

(c) 如果n是大于2的正整数，则方程xn?yn?zn无正整数解（费尔马最后定理）； (d) 如果我不获得更多帮助，我不能完成这个任务。

4. 给P和Q指派真值T，给R和S真值F，求下列命题的真值： (a) P?Q?R??((P?Q)?(R?S))； (b) ?(P?Q)??R?((Q??P)?R??S)； (c) P?(Q?R??P)?Q??s。 5. 构成下列公式的真值表： (a) Q?(P?Q)?P；

第2页 共53页

(b) (P?Q?Q?R)?P??R。

6. 证明下列公式的真值与它们的变元值无关： (a) P?(P?Q)?Q；

(b) (P?Q)?(Q?R)?(P?R)。

7. 对P和Q的所有值，证明P?Q与?P?Q有同样的真值。证明(P?Q)?(?P?Q)总是

真的。

8. 设?是具有两个运算对象的逻辑运算符，如果(x?y)?z与x?(y?z)逻辑等价，那么运算

符?是可以结合的，

(a) 确定逻辑运算符?、?、?、?哪些是可结合的； (b) 用真值表证明你的断言。

9. 指出一下各式哪些不是命题公式，如果是命题公式，请说明理由：

((?P)?(P?Q))?R)； (a) ((Q?(P?Q))?P)。 (b) (

1.2 重言式

10．指出下列那些命题是重言式、偶然式和矛盾式： (a) P??P； (b) P??P； (c) P??(?P)；

(d) ?（P?Q)?(?Q??P)；

（P?Q)?(?P??Q)； (e)

(f) （P?Q)?(Q?P)； (g) P?(Q?R)?(P?Q?P?R)；

（P?Q?P)?(P?Q)； (h)

(i) (（P?Q)?(R?S))?((P?R)?(Q?S))。

11. 对下述每一表达式，找出仅用?和?的等价表达式，并尽可能简单： (a) P?Q??R； (b) P?(?Q?R?P)； (c) P?(Q?P)。

第3页 共53页

对下述每一表达式，找出仅用?和?的等价表达式，并尽可能简单： (a) P?Q??P；

(b) (P?(Q??R))??P?Q； (c) ?P??Q?(?R?P)。

12. 用化简联结词?的左边成右边的方法，证明以下是重言式：

(P?Q)?P)?T； (a) ((b) (Q?P)?（?P?Q)?(Q?Q)?P。 13. 证明下列等价关系：

(a) P?（Q?P)??P?(P??Q)； (b) (P?Q)?(R?Q)?(P?R?Q)；

(c) ?（P?Q)?(P?Q)??(P?Q)?(P??Q)?(?P?Q)； (d) ?（P?Q)?P??Q。 14. 求出下列公式的最简等价式：

(P?Q)?(?Q??P))?R； (a) ((b) P??P?(Q??Q)；

(c) （P?（Q?S))?(?P?(Q?S))。 15. 证明下列蕴含式： (a) P?Q?(P?Q)； (b) P?(Q?P)；

(c) （P?（Q?R))?(P?Q)?(P?R)；

（P?Q)?Q?P?Q； (d)

（(P??P)?Q)?（(P??P)?R)?(Q?R)。 (e)

16. (a) 与非运算符（又叫悉菲（Sheffer）记号）用下述真值表定义，可以看出

P?Q??（P?Q)，试证明

（i）P?P??P；

（ii）；(P?P)?(Q?Q)?P?Q； （iii）（P?Q）?(P?Q)?P?Q。

第4页 共53页

(b) 或非运算符（又叫皮尔斯（Peirce）箭头）用下述真值表定义，它与?（P?Q)逻辑等价。对下述每一式，找出仅用?表示的等价式。 （i）?P； （ii）P?Q； （iii）P?Q。

0 0 0 1 1 0 1 1 P Q P?Q 1 1 1 0 P Q 0 0 0 1 1 0 1 1 P?Q 1 0 0 0 17. (a) 用真值表证明?和?互相可分配；

(b) ?、?和?对自己可分配吗？ 18. 求出下列各式的代入实例：

(a) (((P?Q)?P)?P)：用P?Q代P，用((P?Q)?R)代Q； (b) ((P?Q)?(Q?P))；用Q代P，用P??P代Q。

1.3 范式

19. 对任一指派，i?j时，为什么mi和mj不能同时为真？为什么Mi和Mj不能同时为假？ 20. 求下列各式的主合取范式：

(a) P?Q?R??P?Q?R??P??Q??R； (b) P?Q??P?Q?P??Q； (c) P?Q??P?Q?R。

21. 求下列各式的主析取范式和主合取范式： (a) ； （?P??Q）?（P??Q）(b) P?(?P?(Q?(?Q?R)))； (c) （P?Q?R)?(?P?(?Q??R))； (d) P??Q?S??P?Q?R。

1.4 联结词的扩充与归约

第5页 共53页

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《离散数学》习题集在线全文阅读。