离散数学期末考试题答案

北京交通大学2 0 0 7 -2 0 0 8 学年第2 学期 离散数学基础（0 6 级信科专业）期末试题 & 参考答案 第 1 页 共 7 页 北 京 交 通 大 学 2007-2008 学年第二学期 《离散数学基础（信科专业）》期末考试卷（A） 学院：____________ _专业：___________________ 班级____________ 姓名： 学号： □选修 □必修 题号 总分 得分 阅卷人 一、 填空题（共10 分，每空1 分） 1. 在推理理论中，推导过程中如果一个或多个公式重言蕴涵某个公式，则这个公式就可以引入推导过程中，这一推理规则叫做（ T 规则 ）。 2. 设A={ a，{ b} } ，则A 的幂集是P (A)= {Φ, a，{b}, {a，{b}} ； 3. 设R 是集合 A 上的二元关系，如果关系 R 同时具有自反性、 反对称性 和传递性，则称 R 是A 上的一个偏序关系。 4. 既是满射，又是 单射 的映射称为 1-1 映射（双射）。 5. 设S 为非空有限集,代数系统的单位元和零元分别为 S 和 φ 。 6. 具有 n 个顶点的无向完全图共有 n(n-1)/2 条边。 7. 简单图是指 无环、无重边 的图。 8. k-正则图是指 所有顶点的度数均为 k 的 的图。 9. Hamilton 通路是指 通过图中所有顶点一次且仅一次 的通路。 10. 设G=（E，V）是图，如果G 是连通的，则P（G）= 1 。 11. 命题公式(PQ)  (PR)的主析取范式中包含极小项（ A ） A．PQR； B．PQR； 北京交通大学2 0 0 7 -2 0 0 8 学年第2 学期 离散数学基础（0 6 级信科专业）期末试题 & 参考答案 第 2 页 共 7 页 C．PQR； D．PQR 12. 下列谓词公式中（ A ）不正确。 A．(x)(A(x) B)  (x) A(x) B； B．(x)(B A(x))  B (x) A(x)； C．(x)(B A(x))  B (x) A(x)； D．(x)(A(x)B) (x)A(x)B； 13. 设S = {2，a，{3}，4}，R ={{a}，3，4，1}，指出下面的写法中正确的是（ D ） （A）R=S； （B）{a,3}S； （C）{a}R； （D）R； 14. 下列命题公式不是重言式的是 C 。 A. Q→(P∨Q)； B.(P∧Q)→P；C.（P∧Q）；D.（P∧0）。 15. 下列谓词公式中（ ）不正确。 (A) (x)(A(x) B)  (x) A(x) B； (B) (x)(B A(x))  B (x) A(x)； (C) (x)(B A(x))  B (x) A(...