A．路径 B．迹

C．既是初级回路也是迹 D．既非初级回路也非迹

二、填空题（本大题共10小题，每小题2分，共20分）

请在每小题的空格中填上正确答案。错填、不填均无分。

16．设A={1，2}，B={2，3}，则A?A=__________，A?B=__________。

17．设A={1，2，3，4}上关系R={<1,2>,<2,4>,<3,3>,<1,3>}，则R的自反闭包r(R)= _________，对称闭包S（R）=__________。

18．命题公式（P?Q）→? P的成真指派为__________，成假指派为__________。 19．公式（?x）（F（x）→G(y)）→(?y)(H(x)?L(x,y,z))中的自由变元为_________，约束变元为__________。

20．设f :R→R,f (x)=x2-2,g :R→R,g(x)=x-1,那么复合函数

(f?g)(x)=__________，(g?f)(x)=__________。

21．有理数集Q中的*运算定义如下：a*b=a+b-ab，则*运算的单位元是__________，设a有逆元，则其逆元a-1=__________。

22．设A={<1,2>,<2,4>,<3,3>},B={<1,3>,<2,4>,<4,2>},那么dom(A∪B)=_______,ran(A∩B)= __________。

23．如下图的有补格中，c的补元是__________，b的补元是__________。

24．在根树中，若每一个结点的出度__________m,则称这棵树为m叉树。如果每一个结点的出度__________m或0，则称这棵树为完全m叉树。

25．是一个群，其中Zn={0,1,2,……,n-1},x?y=(x+y)mod n，则在中，1的阶是__________，4的阶是__________。

三、计算题（本大题共5小题，第26、27小题各5分，第28、29小题各6分，第30小题8分，共30分）

26．构造命题公式（P?Q?Q?R）→P?? R的真值表。

第 9 页

27．若集合A={1，{2，3}}的幂集为P（A），集合B={{?，2}，{2}}的幂集为P（B），求

P(A)∩P(B)。

28．设X={1，2，3，4}，R是X上的二元关系，

R={<1,1>,<3,1>,<1,3>,<3,3>,<3,2>,<4,3>,<4,1>,<4,2>,<1,2>}。 （1）画出R的关系图； （2）写出R的关系矩阵；

（3）说明R是否具有自反、反自反、对称、传递性质。

29．求下列公式的主析取范式和主合取范式：（P→（Q?R））?（? P→（? Q→R））。 30．设A={a,b,c},P(A)是A的幂集，R为A上的包含关系，试给出的哈斯图，并给出子集{{a,b},{a,c},{c}}的极大元、极小元、最大元、最小元。

四、证明题（本大题共3小题，第31、32小题各6分，第33小题8分，共20分）

?1x???31．设H是形如?01?的2×2阶矩阵的集合，H中定义通常的矩阵乘法运算。验证H?1x??1?x??01????=?01?。 是群，??132．设R为N×N上的二元关系，??a,b?,?c,d?∈N×N，?a,b?R?c,d??b?d,证明R为等价关系。

133．简单图G有n个结点，m条边，设m>2(n-1)(n-2)，证明：G是连通的。

五、应用题（本大题共2小题，第34小题7分，第35小题8分，共15分） 34．构造下面推理的证明。

只要A曾到过受害者房间并且11点以前没离开，A就犯了谋杀罪。A曾到过受害者房间。如果在11点以前离开，看门人会看见他。看门人没有看见他。所以A犯了谋杀罪。 35．在某次国际会议的预备会中，共有8人参加，他们来自不同的国家。已知他们中任何两个无共同语言的人中的每一个，与其余有共同语言的人数之和大于或等于8，问能否将这8个人排在圆桌旁，使其任何人都能与两边的人交谈。

第 10 页

2008年7月自考离散数学试题参考答案

第 11 页

第 12 页