离散数学练习题

离散数学练习题

一、填空题（10分，每空1分，请将本题答案填在原题横线上！）．．．．

1、设集合X={0，1，2}，R是X上的二元关系，R={<0，0>，

<0，2>，<1，2>，<2，0>，<2，1>}，则R的关系矩

阵MR。2、则由2生成的子群<2>= ，?Z6,?6?

为模6整数加群，右陪集<2>⊕6

3、设A和B为有限集，|A|=m，|B|=n，则有个从A到B的关系，有

个从A到B的函数。

4、无向图G如下图所示，G的点连通度κ为λ

为 。

5、在上面无向图中，已给出了一棵生成树T（粗边所示），则树枝d

对应的基本割集是 ，弦b对应的基本回路

是 。

6、令F(x)：x是整数，G(x)：x是奇数，则“不存在不是奇数的整数”

符号化

为 。

7、含有三个命题变项P，Q，R的命题公式P?Q的主析取范式是

（用mi形式表示最小项）。

二、单选题（20分，每题1分，请将本题答案写在下方表格中！）

．．．．? B、?01,001,000,10?A、?0,10,110,1111

D、?b,c,aa,ac,aba,abc?2、下列

3、设A={a，b，c，d}，A上的等价关系R={<a，b>，<b，

d>，<d，a>}∪R-1∪IA，则对应于R的A的划分是

（ ）。

A、{{a，b}，{c，d}} B、{{a，b，d}，{c}}C、{{a}，{b}，{c}，

5、令p:我将去上网，q:我有时间，则“我将去上网，仅当我有时间”

B、无回路的连通图
D、有n个顶点n—1条边

?0?19、设图D的邻接矩阵为??1??1

??11111?0100??，则D的顶点数与边数分别为1011??0101?0110??

(	) 。	C、4， 10	D、5，
A、4， 5	B、5， 16

8

10、下列式子中正确的是（ ）。

A、?＝1 B、??? C、??｛?｝ D、?＝{?}

11、由2个命题变元p和q组成的不等值的命题公式的个数有

12、给定下列非负整数序列，可构成简单无向图的节点度数序列的为

( )。

(B)(1，1，2，2，2)(D) (1，1，2，2，3)

16、设图G=<V，E>为无向图，|V|=5，|E|=20，则G一定是

( )。

A、完全图 B、正则图 C、多重图 D、简单图

17、给定公式?xP(x)??xP(x)，当D={a,b}时，解释( )使该公式真值为

0。

A.P(a)=0、P(b)=0 B.P(a)=0、P(b)=1 C.P(a)=1、P(b)=1

18、设A={1,2 ,3 }，则A上有（ ）个二元关系。

A、2B、3 C、2 D、2

19、设Z是整数集合，“+”是数的加法运算，则<Z，+>的单位元

是( )

A、1 B、-1 C、没有单位元 D、0

20、设R和S是集合A={1，2，3，4}上的二元关系，则S是R的

（ ）闭包。

322332

R= {?1 ，1?，?1，2?，?2，2?，?2，3?，?4，4?}

S= {?1 ，1?，?1，2?，?2，2?，?2，3?，?3，3?，?4，4?}

A、对称

B、自反

C、传递

D、以上都

不对

三、求解题（40分，每题8分，请将本题答案写在后面答题纸上！）

1、在自然推理系统中构造证明：

已知张三或李四的彩票中奖了。如果张三的彩票中奖了，那么你会知

道张三的彩票中奖了。如果李四的彩票中奖了，那么王五的彩票也中奖了。

你不知道张三的彩票中奖了。所以，李四和王五的彩票都中奖了。

2、设A={a,b,c,d,e}，A上的偏序关系R＝{<c,a>，<c,b>，<d,a>，<d,b>，<e,a>，<e,b>，<e,c>，
<e,d>}?IA，求：
(1)画出偏序集<A，R>的哈斯图；
(2)求子集B={c,d,e}的极大元，极小元，最大元，最小元。

3、求一阶逻辑公式的前束范式：(?xF(x,y)→?yG(y))→?xH(x,y,z)。

a:35%，b:20%，c:15%，d:10%，4、设7个字母在通信中出现的频率如下：
e:10%，f:5%，g:5%，用Huffman算法求传输它们的最佳前缀码。要求画出最优二叉树，并指出传输100个按上述频率出现的字母，需要多少个二进制数字。

5、
四、证明题（30分，每题7、7、8、8分，请将本题答案写在后面答题纸上！）

1、例如，f和g都是群<G1，。>到群<G2，*>的同态映射，C={x|x∈G1∧f(x)=g(x)}。证明：<C，
。>是<G1，。>的一个子群。 2、要在七天安排七场考试，同一个老师监的任何两场考试不能安排在接连的两天内进行。假如每个教师最多监四场考试，请证明：安排这样

的考试日程表是可以的。

3、设R是集合A上一个等价关系，
S?{?x,y?|x,y?A??z(?x,z??R??z,y??R)}，试证明S也是A上的一个等价关

系。

4、
参考答案

一、

?101???1、?001?

??110??

2、{0，2，4}，{5，1，3}
3、2mn，nm
4、2，3
5、d,b,c，bade
或?x(F(x)?G(x))6、??x(F(x)??G(x))
7、m6?m7
二、