离散数学(本科)(.doc

《离散数学(本科)(.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《离散数学》复习资料2014年12月一、单项选择题（每小题3分，本题共15分）1．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是(A)．A．AÌB，且AÎBB．BÌA，且AÎBC．AÌB，且AÏBD．AËB，且AÎB2．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是(D)．图一A．（a）是强连通的B．（b）是强连通的C．（c）是强连通的D．（d）是强连通的3．设图G的邻接矩阵为则G的边数为(B)．A．6B．5C．4D．34．无向简单图G是棵树，当且仅当(A)．A．G连

2、通且边数比结点数少1B．G连通且结点数比边数少1C．G的边数比结点数少1D．G中没有回路．5．下列公式(C)为重言式．A．ØPÙØQ«PÚQB．(Q®(PÚQ))«(ØQÙ(PÚQ))C．(P®(ØQ®P))«(ØP®(P®Q))D．(ØPÚ(PÙQ))«Q6．设A={a,b}，B={1,2}，R1，R2，R3是A到B的二元关系，且R1={,}，R2={,,}，R3={,}，则（B）不是从A到B的函数．A．R1和R2B．R2C．R3D．R1和

3、R37．设A={1,2,3,4,5,6,7,8}，R是A上的整除关系，B={2,4,6}，则集合B的最大元、最小元、上界、下界依次为(B)．A．8、2、8、2B．无、2、无、2C．6、2、6、2D．8、1、6、18．若集合A的元素个数为10，则其幂集的元素个数为（A）．A．1024B．10C．100D．199．设完全图K有n个结点(n≥2)，m条边，当（C）时，K中存在欧拉回路．A．m为奇数B．n为偶数C．n为奇数D．m为偶数10．已知图G的邻接矩阵为，则G有（D）．A．5点，8边B．6点，7边C．6点，8边D

4、．5点，7边11.无向完全图K3的不同构的生成子图的个数为（C）(A)6(B)5(C)4(D)312n阶无向完全图Kn中的边数为（A）(A)(B)(C)n(D)n(n+1)13.在图G＝中，结点总度数与边数的关系是(C)Adeg(vi)=2½E½(B)deg(vi)=½E½CD二、填空题（每小题3分，本题共15分）1．命题公式的真值是　1　．2．若A={1,2}，R={

5、xÎA,yÎA,x+y<4}，则R的自反闭包为{<1,1>,<2,2>,<1,2>,<2,1>}．3．已知一棵无向树T中有

6、8个结点，4度，3度，2度的分支点各一个，T的树叶数为5．4．("x)(P(x)→Q(x)∨R(x，y))中的自由变元为R(x，y)中的y．5．设集合A＝{a，b}，那么集合A的幂集是{Æ,{a,b},{a},{b}}6．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有2个．7．设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去4条边后使之变成树．8．无向图G存在欧拉回路，当且仅当G所有结点的度数全为偶数且连通9．设连通平面图G的结点数为5，边数为6，则面数为3．10

7、．设个体域D＝{a,b}，则谓词公式("x)A(x)∧（$x）B（x）消去量词后的等值式为(A(a)∧A(b))∧(B（a）∨B（b）)．9三、逻辑公式翻译（每小题6分，本题共12分）1．将语句“雪是黑色的．”翻译成命题公式．设P：雪是黑色的，（2分）则命题公式为：P．2．将语句“他不去学校．”翻译成命题公式．解：设P：他去学校，则命题公式为：ØP．3．将语句“小王是个学生，小李是个职员，而小张是个军人．”翻译成命题公式．设P：小王是个学生，Q：小李是个职员，R：小张是个军人．（2分）则命题公式为：P∧Q∧R．

8、4．将语句“如果所有人今天都去参加活动，则明天的会议取消．”翻译成命题公式．解：设P：所有人今天都去参加活动，Q：明天的会议取消，则命题公式为：P®Q．5．将语句“他去旅游，仅当他有时间．”翻译成命题公式．解：设P：他去旅游，Q：他有时间，则命题公式为：P®Q．6．将语句“41次列车下午五点开或者六点开．”翻译成命题公式．解：设P：41次列车下午五点开，Q：41次列车下午六点开，（2分）命题公式为：（P∧ØQ）∨（ØP∧Q）7．将语句“小张学习努力，小王取得好成绩．”翻译成命题设P：小张学习努力，Q：小王取得好

9、成绩，（2分）则命题公式为：PÙQ．8．将语句“有人去上课．”翻译成谓词公式．解：设P(x)：x是人，Q(x)：x去上课，（1分）($x)(P(x)ÙQ(x)9．将语句“所有的人都学习努力．”翻译成命题公式．解：设P(x)：x是人，Q(x)：x学习努力，"x）(P(x)®Q(x))．四、判断说明题（每小题7分，本题共14分）判断下列各题正误，并说明理由．1．设集合A={1,2,3,4}