7141《离散数学》考试大纲及模拟试卷.doc

模拟试题及规范解答举例一、填空题（共20分）1. 设A，B是两个集合，A=1，2，3，4，B=2，3，5，则B-A= _，r（B）-r（A）= _。2. 若关系R具有自反性，当且仅当在关系矩阵中，主对角线上元素 ；若关系只具有对称性，当且仅当关系矩阵是 .3. 命题公式G=（PQ）R，则G共有 个不同的解释；把G在其所有解释下所取真值列成一个表，称为G的 ；解释（P，Q，R）或（0，1，0）使G的真值为 。4. 设G是由12个元素构成的循环群，a是G的一个生成元素，则G有_个子群。G的生成元素集合是_。5. 设G=（P，L）是图，如果G是连通的，并且 ，则G是树。如果根树T的每个点v最多有两棵子树，则称T为 。二、选择题（选择一个正确答案的代号，填入括号中。共20分）1. 由集合运算定义，下列各式正确的有（ ）。A、 B、 C、 D、2. 设集合A=a，b，c，A上的关系R=（a，b），（a，c），（b，a），（b，c），（c，a），（c，b），（c，c），则R具有关系的（ ）性质。A自反 B对称 C传递 D反对称3. 设R为实数集，映射s=RR，s（x）= -x2+2x-1，则s是（ ）。A单射而非满射 B满射而非单射 C双射 D既不是单射，也不是满射4. 设命题公式，则G是（ ）。A.恒真的 B.恒假的 C.可满足的 D.析取范式5. 一个公式在等价意义下，下面哪个写法是唯一的（ ）。A析取范式 B合取范式 C主析取范式 D以上答案都不对6. 下面给出的一阶逻辑等价式中，（ ）是错的。A、B、C、D、7. 下面的代数系统(G,*)中，( )不是群。A. G为整数集合，*为加法；B. G为偶数集合，*为加法；C. G为有理数集合，*为加法；D. G为有理数集合，*为乘法;8. 设G是由5个顶点组成的完全图，则从G中删去（ ）条边可以得到树.A4 B5 C6 D109. 无向图的关联矩阵中“关联”指的是( )。A.顶点与顶点的关联 B.边与边的关联C.边与顶点的关联 D.都不是10.I为整数集，下列系统中不是代数系统的有( )。A.(I, )B.(I, +)C.(I, )D.都不是三、计算题(共40分)1. 化简下式：（A-B-C）（A-B）C）（AB-C）（ABC）2. 通过求主析取范式判断下列命题公式是否等值。（1）（PQ）（PQR）；（2）（P（QR）（Q（PR）；3. 求图中A到其余各顶点的最短路径，并写出它们的权。 B 7 C 1 2 A 2 5 3 D4 6 E 1 F4化简布尔表达式四、证明题(共20分）1. 设Aa，b，c，R(a，a)，(a，b)，(b，c)，验证rs(R)sr(R)。2. 证明.4模拟试题答案及评分标准一、 填空题(每空2分，共20分)1、 5，5，2，5，3，5，2，3，52、 全为1 对称矩阵3、 8；真值表；14、 6，a,a3,a5,a7,a115、 无回路；二叉树二、选择题(每题2分，共20分）1、A 2、B 3、D 4、C 5、C 6、B 7、D 8、D 9、C 10、C三、计算题(共40分)1. 解： （共10分）（A-B-C）（A-B）C）（AB-C）（ABC）=（ABC）（ABC）（ABC）（ABC） =（AB）（CC）（AB）（CC） =（AB）E）（AB）E） E为全集 =（AB）（AB） = A（BB） = AE = A 2. 解：（共10分） （PQ）（PQR）（PQ（RR）（PQR）（PQR）（PQR）（PQR） m6m7m3 m3m6m7 （P（QR）（Q（PR）（PQ） （QR）（PPR）（P Q R） （分配律）（PQ（RR） （PP）QR）（P Q R）（PQR） （PQR） （PQR）（PQR）（P Q R） m6m7m3m7m3 m3m6m7 由此可见 （PQ）（PQR） （P（QR）（Q（PR）3. 解： （共10分） A到B的最短路径为AB，权为1；A到E的最短路径为ABE，权为3；A到F的最短路径为ABEF，权为4；A到C的最短路径为ABEFC，权为7；A到D的最短路径为ABEFCD，权为9。4. 解：（共10分） (2分) (6分) (10分)四、证明题(共20分)1. 证明：（共10分） rs(R)r(a，a)，(a，b)，(b，a)，(b，c)，(c，b) (a，a)，(a，b)，(b，a)，(b，c)，(c，b)，(b，b)，(c，c) sr(R)s(a，a)，(a，b)，(b，c)，(b，b)，(c，c) (a，a)，(a，b)，(b，a)，(b，c)，(c，b)，(b，b)，(c，c)于是rs(R)sr(R) (10分) 2. 证明：（共10分） QR P （2分） R P (4分)Q ，析取三段论 PQ P (7分) ，拒取式 PS P S ，