昆明理工大学离散数学2008考研试题研究生入学考试试题考研真题
● 摘要
昆明理工大学 2008 年硕士研究生招生入学考试试题(A 卷) 考试科目代码：606 考试科目名称 ：离散数学 试题适用招生专业 ：计算机软件与理论 考生答题须知 1． 所有题目（包括填空、选择、图表等类型题目）答题答案必须做在考点发给的答题纸上，做在本试题册上无效。 请考生务必在答题纸上写清题号。 2． 评卷时不评阅本试题册，答题如有做在本试题册上而影响成绩的，后果由考生自己负责。 3． 答题时一律使用蓝、黑色墨水笔或圆珠笔作答（画图可用铅笔） ，用其它笔答题不给分。 4． 答题时不准使用涂改液等具有明显标记的涂改用品。 一、选择题（共 14 小题。每个选项 2 分，共 30 分） 1、由互不相同的命题变元 P1，P2，……，Pn 可构造出（ （A） ）个互不等值的命题公式。 n 1 n（n+1） （B）2n 2 （C）n （D） 2 2 2、设 A，B 是任意的命题公式，则要使命题公式 A→B 是一个永真式，必须（ ） 。 （A）A 是一个永真式 （B）A 是一个永假式 （C）A 是一个等值式 （D）A 是一个蕴涵式 3、下列各式中哪个正确？（ ） （A）∀x ∀yA（x，y） ⇔ ∀x ∃ yA（x，y） （B）∀x ∃ yA（x，y） ⇒ ∃ y ∀x A（x，y） （C） ∃ x∀yA（x，y） ⇒ ∀y ∃ xA（x，y） （D）∀y ∃ xA（x，y） ⇒ ∃ x∀yA（x，y） 4、对一个由 n 个前提 A1，A2，……，An 推出结论 B 的推理，只要满足条件（ 值必为 1。 (A) A1，A2，……，An 都真 (B) B 是 A1，A2，……，An 的有效结论 (C) 推理方式符合人的思维习惯 (D) A1，A2，……，An 都真且 B 是 A1，A2，……，An 的有效结论 5、设任意的集合 A、B、C 是任意的集合，则下列命题中正确的是（ (A) 若 (B) 若 (C) 若 (D) 若 且 且 且 且 ，则 ，则 ，则 ，则 。 。 。 。 ） 。 （C）对称性 （D）传递性 ）。 ） ，则 B 的真 6、非空集合 A 上的空关系无性质（ （A）反自反性 （B）自反性 第 1 页 共 3 页
7、设集合 A={1，2，3，4}上的二元关系 R={<1,1>,<2,2>,<2,3>,<4,4>}， S={<1,1>,<3,2>,<2,2>,<2,3>,<4,4>}，则 S 是 R 的（ (A) 自反 (B) 对称 (C) 传递 ） 。 （D）幂等律 ）闭包。
(D) 以上都不对
8、二元关系之间的合成运算满足（ （A）交换律 （B）分配律
（C）结合律
9、设 A={1，2，3， 。 。 。 。 。 。 ，9}，定义 A 上的二元关系 R={
合取范式为
。 。
）∧P）可化简为 3、命题公式（ （ （┓P∨Q） ↔ （┓Q→┓P）
） ，消去其中的所有量词后可得与 4、设个体域 D={1，2}，则对谓词公式 ∃ x∀y（P（x）→Q（y） 之等值的谓词公式 5、设 A={a1，a2，a3}，则对集合 A 共有 。 种不同的划分。
6、如果 R、S 分别表示人与人之间的“父子”关系、 “母子”关系，那么合成关系 R οS 和 S οR 就分别为 关系和 关系。 。 。
7、设集合 A={{2}}，则 A 的幂集的幂集 P（P（A） ）= 8、对 4 阶图 G，如果其中的 3 个结点的度分别为 2，3，3，则第四个结点的度不可能是
9、设 G=
四、证明题（共 4 小题，总分 36 分） 1、证明下述推理的有效性。 如果甲弃权，则乙或丙将获得出线权；如果乙获得出线权，那么甲必没有弃权；如果丁获得 了出线权，那么丙肯定未获出线权。所以，若甲弃权，则丁不能获得出线权。 （12 分） 2、对任意的集合 A，B，试证：A−B=B−A iff（当且仅当） A=B。 （10 分） 3、设 R 是非空集合 A 上的等价关系，求证：对任意的 a，b∈A ，有 aRb iff [a]R=[b]R。 （6 分） 4、证明：若 G 是含有奇数个结点的二部图（偶图） ，则 G 必不是哈密尔顿图。 （8 分） 第 4 页 共 3 页
第 5 页 共 3 页
昆明理工大学 2008 年硕士研究生招生入学考试试题 第 6 页 共 3 页
第 7 页 共 3 页