--
计算机科学与技术专业 级第二学期离散数学试题
2012年1月
一、单项选择题（每小题3分,本题共1５分)1．C ２.Ｃ 3.B 4.A 5．D 1.若集合Ａ的元素个数为10，则其幂集的元素个数为（ ).
A.1０ B.1０0 C.1０2４ D．1
2．设A＝{a, ｂ},B＝{1, ２},Ｒ１，R2,R３是A到Ｂ的二元关系,且R１＝{＜ａ,2>,
A．R１和R2 B．Ｒ２ Ｃ．R３ D.Ｒ１和R3
3.设Ａ={1, 2， 3, 4, ５, 6, 7， ８},R是Ａ上的整除关系,B={２, ４， 6}，则集合B的最大元、最小元、上界、下界依次为 （ )．
A.8、2、8、２ B.无、2、无、２ C.６、2、6、2 D.８、1、6、1
４．若完全图G中有n个结点(n≥2),m条边,则当( )时，图G中存在欧拉回路． A.n为奇数 B.n为偶数 C．m为奇数 Ｄ．m为偶数 ?５．已知图G的邻接矩阵为
则G有( ）.
A．6点,8边 Ｂ．6点,6边 C．5点,8边 Ｄ．5点，６边
?二、填空题（每小题3分,本题共15分)
6.设集合A＝{a｝,那么集合A的幂集是 ｛?,｛a}} . 7．若R１和R2是A上的对称关系，则R1∪R２,R1∩R2,R1-R2 ，R2－Ｒ1中对称关系有 4 个． ８．设图G是有5个结点的连通图，结点度数总和为1０,则可从Ｇ中删去 1 条边后使之变成树．
９.设连通平面图Ｇ的结点数为5,边数为6,则面数为 ３ .
10．设个体域D＝{a, ｂ}，则谓词公式(?ｘ)(A(x)∧B(x))消去量词后的等值式为 (A （a）∧Ｂ (ｂ))∧(Ａ(a)∧B（b)） .
三、逻辑公式翻译(每小题6分,本题共１2分)
１1.将语句“今天有联欢活动，明天有文艺晚会.”翻译成命题公式.
设P:今天有联欢活动，Ｑ：明天有文艺晚会， (2分) P∧Q． (6分)
--
--
12．将语句“如果小王来,则小李去．” 翻译成命题公式．
设 P:小王来,Q:小李去 （2分）
P → Q． (6分）
四、判断说明题（每小题7分,本题共1４分） 判断下列各题正误，并说明理由．
１3.若偏序集
?
b ? c
? ? d 错误. 图一 （3分）对于集合A的任意元素x，均有 １4．┐P∧(P→┐Q）∨P为永假式. 错误. （3分）┐P∧(P→┐Q）∨Ｐ是由┐P∧（Ｐ→┐Ｑ)与P组成的析取式， 如果P的值为真，则┐P∧（P→┐Ｑ)∨P为真， (５分) 如果P的值为假，则┐P与P→┐Q为真，即┐P∧（P→┐Q）为真， 也即┐P∧(P→┐Q）∨P为真， 所以┐P∧（P→┐Q）∨P是永真式. (７分） 另种说明: ┐Ｐ∧(P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式, 只要其中一项为真，则整个公式为真. （5分) 可以看到,不论P的值为真或为假,┐P∧（P→┐Q）与P总有一个为真， 所以┐P∧(P→┐Q)∨P是永真式． (7分) 或用等价演算┐P∧(P→┐Q)∨P?Ｔ 五．计算题（每小题１2分，本题共36分) １５．设集合A={1，2，3，4｝，Ｒ={ （3）说明R满足自反性，不满足传递性． 1５．(1）R={<1,1>,<2，2>,<3,３>，<4，4>，＜1,２>,<2,1>,＜2,3＞，＜３,2＞,<３,4>,＜4，3＞} 分） (2）关系图如图二: 图二 (6分) -- 3 （-- （３）因为<1,1>,<2，2＞,＜3，3>，＜4,4>均属于R，即A的每个元素构成的有序对均在Ｒ中,故Ｒ在A上是自反的. (9分) 因有<２，３>与<3,4>属于Ｒ，但<2,4>不属于R,所以R在A上不是传递的． (12分) １6．设图G=＜V，E>，V={ v1,v２,v３,v4，v5｝，E＝{ (ｖ1， v2），(v１， v3)，(v2, v4)，(v3, v5),(v4, v5) },试 (1) 画出Ｇ的图形表示； (2) 写出其邻接矩阵； (3) 求出每个结点的度数; (4) 画出图G的补图的图形. v1 16.（1）关系图如图三： ? v2 ? ? v 5 ? ? v3 v4 图三 分） (2）邻接矩阵 ??01100??10010? ? ?10001?? ?01001????00110??分） (3）deg(v1)=2 deg(ｖ2）=2 dｅｇ（v３)=2 ｄeg(v4)=2 ｄeｇ（ｖ５）=2 分） v1 （4)补图如图四 ? v2 ? ? v5 v3 ? ? v4 图四 分) 17．求P?Q∧R的合取范式与主析取范式． P→（R∧Q） ?┐P∨(R∧Q) ? （┐P∨Q)∧（┐P∨R) （合取范式） P→（R∧Q) ?┐P∨（R∧Q) -- (3 （6 (９ （1２ （４分） 6分) （
电大历年离散数学试题汇总
