《离散数学》习题集.docx

本文格式为Word版，下载可任意编辑《离散数学》习题集 《离散数学》习题集 目 录 第一章 数理规律 .................................................................. 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页 — 5 —。