计算机科学与技术专业 级第二学期离散数学试题
一、单项选择题（每小题3分，本题共15分）1．C 2．C 3．B 4．A 5．D 1．若集合A的元素个数为10，则其幂集的元素个数为（ ）． A．10 B．100 C．1024 D．1
2．设A={a, b}，B={1, 2}，R1，R2，R3是A到B的二元关系，且R1={
3．设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为 ( )．
A．8、2、8、2 B．无、2、无、2 C．6、2、6、2 D．8、1、6、1
4．若完全图G中有n个结点(n≥2)，m条边，则当（ ）时，图G中存在欧拉回路． A．n为奇数 B．n为偶数 C．m为奇数 D．m为偶数 5．已知图G的邻接矩阵为
则G有（ ）．
A．6点，8边 B．6点，6边 C．5点，8边 D．5点，6边
二、填空题（每小题3分，本题共15分）
6．设集合A＝{a}，那么集合A的幂集是 {,{a}} ． 7．若R1和R2是A上的对称关系，则R1∪R2，R1∩R2，R1-R2 ，R2-R1中对称关系有 4 个． 8．设图G是有5个结点的连通图，结点度数总和为10，则可从G中删去 1 条边后使之变成树．
9．设连通平面图G的结点数为5，边数为6，则面数为 3 ．
10．设个体域D＝{a, b}，则谓词公式(?x)(A(x)∧B（x））消去量词后的等值式为 (A (a)∧B (b))∧(A（a）∧B（b）） ．
三、逻辑公式翻译（每小题6分，本题共12分）
11．将语句“今天有联欢活动，明天有文艺晚会．”翻译成命题公式．
设P：今天有联欢活动，Q：明天有文艺晚会， （2分） P∧Q． （6分） 12．将语句“如果小王来，则小李去．” 翻译成命题公式． 设 P：小王来，Q：小李去 （2分）
P → Q． （6分）
四、判断说明题（每小题7分，本题共14分） 判断下列各题正误，并说明理由．
13．若偏序集
a
d
c
错误． 图一 （3分） 对于集合A的任意元素x，均有
14．┐P∧（P→┐Q）∨P为永假式．
错误． （3分） ┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式，
如果P的值为真，则┐P∧（P→┐Q）∨P为真， （5分） 如果P的值为假，则┐P与P→┐Q为真，即┐P∧（P→┐Q）为真，
也即┐P∧（P→┐Q）∨P为真，
所以┐P∧（P→┐Q）∨P是永真式． （7分）
另种说明：
┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式，
只要其中一项为真，则整个公式为真． （5分） 可以看到，不论P的值为真或为假，┐P∧（P→┐Q）与P总有一个为真，
所以┐P∧（P→┐Q）∨P是永真式． （7分）
或用等价演算┐P∧（P→┐Q）∨P?T
b
五．计算题（每小题12分，本题共36分）
15．设集合A={1，2，3，4}，R={
（3）说明R满足自反性，不满足传递性． 15．（1）R={<1,1>,<2,2>,<3,3>,<4,4>,<1,2>,<2,1>,<2,3>,<3,2>,<3,4>,<4,3>} （3分） （2）关系图如图二：
图二 （6分）
（3）因为<1,1>,<2,2>,<3,3>,<4,4>均属于R，即A的每个元素构成的有序对均在R中，故R在A上是自反的． （9分）
因有<2,3>与<3,4>属于R，但<2,4>不属于R，所以R在A上不是传递的．
（12分）
国家开放大学电大考试计算机专业历年《离散数学》试题解析
