离散数学练习题
内部编号：（YUUT-TBBY-MMUT-URRUY-UOOY-DBUYI-0128）
一、填空题（10分，每空1分，请将本题答案填在原题横线．．．．
上！）
1、设集合X={0，1，2}，R 是X 上的二元关系，R={<0，0>，<0，2>，<1，2>，<2，0>，<2，1>}，则R 的关系矩阵M R = 。

2、66,Z <⊕>为模6整数加群， 则由2生成的子群<2>= ，右陪集<2>⊕65= 。

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 的命题公式PQ 的主析取范式是 （用m i 形式表示最小项）。

二、单选题（20分，每题1分，请将本题答案写在下方表格．．．．
中！）
A 、{}1111,110,10,0
B 、{}01,001,000,10
C 、{}1101,1001,101,110,
D 、{}abc aba ac aa c b ,,,,, 2、下列( )组赋值不是命题公式C ()A B →∨⌝的成真赋值。

A 、010
B 、011
C 、110
D 、101
3、设A={a ，b ，c ，d}，A 上的等价关系R={<a ，b>，<b ，d>，<d ，a>}∪R -1
∪I A ，则对应于R 的A 的划分是（ ）。

A 、{{a ，b}，{c ，d}}
B 、{{a ，b ，d}，{c}}
C 、{{a}，{b}，{c}，{d}}
D 、{{a}，{b ，c}，{d}} 4、二部图3,3K 是( ) 。

A 、欧拉图
B 、 哈密顿图
C 、 非连通图
D 、完全图
5、令p: 我将去上网，q: 我有时间，则“我将去上网，仅当我有时间”可符号化为( )。

(A) q p → (B) q p ↔ (C)p q → (D)q p ⌝∨⌝ 6、下面（ ）图不一定是树。

A 、每对结点间都有路的图
B 、无回路的连通图
C 、连通但删去一条边则不连通的图
D 、有n 个顶点n —1条边的连通图 7、集合A = {1, 2, …, 10}上的关系R ={<x, y>|x + y = 10, x, y ∈A}, 则R 的性质是( )。

(A) 自反的 (B) 传递的、对称的 (C) 对称的 (D) 反自反的、传递的 8、设G 如右图，那么G 不是( )。

(A)哈密顿图 (B)完全图 (C)欧拉图 (D)树
9、设图D
的邻接矩阵为⎥⎥⎥
⎥
⎥⎥
⎦
⎤
⎢⎢⎢⎢⎢
⎢⎣⎡01101
101011101100101
11110，则
D 的顶点数与边数分别为
( ) 。

A 、4， 5
B 、5， 16
C 、4， 10
D 、5， 8 10、下列式子中正确的是（ ）。

A 、＝1 B 、 C 、｛｝ D 、＝{}
11、由2个命题变元p 和q 组成的不等值的命题公式的个数有( )。

(A)2 (B)4 (C) 16 (D) 8 12、给定下列非负整数序列，可构成简单无向图的节点度数序列的为( )。

(A) (1， 3， 4， 4， 5) (B) (1， 1， 2， 2， 2) (C) (0， 1， 3， 3， 5) (D) (1， 1， 2， 2， 3)
13、 4阶完全无向图4K 中含3条边的不同构的生成子图有( )。

(A)5 (B)4 (C)3 (D)2
14、任意12阶群的子群的阶一定不为 ( )。

(A)3 (B)6 (C)8 (D)4 15、在公式x ∀F(x ， y)→ ∃ yG(x ，y)中变元x 是( )。

(A) 既是自由变元，又是约束变元 (B) 既不是自由变元，又不是约束变元 (C) 自由变元
(D) 约束变元
16、设图G=<V ，E>为无向图，|V|=5，|E|=20，则G 一定是( ) 。

A 、完全图 B 、正则图 C 、多重图 D 、简单图
17、给定公式)()(x xP x xP ∀→∃，当D={a,b}时，解释( )使该公式真值为0。

(a)=0、P(b)=0 (a)=0、P(b)=1 (a)=1、P(b)=1 18、设A={1 ,2 ,3 }，则A 上有（ ）个二元关系。

A 、23
B 、32
C 、 322
D 、2
32
19、设Z 是整数集合，“+”是数的加法运算，则<Z ，+>的单位元是( ) A 、1 B 、-1 C 、没有单位元 D 、0
20、设R 和S 是集合A={1，2，3，4}上的二元关系，则S 是R 的（ ）闭包。

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>}I A ，求： (1) 画出偏序集<A ，R >的哈斯图；
(2) 求子集B={c,d,e}的极大元，极小元，最大元，最小元。

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

4、设7个字母在通信中出现的频率如下：a: 35%，b: 20%，c: 15%，d: 10%，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、
参考答案
一、
1、101001110⎡⎤⎢⎥⎢⎥⎢⎥⎣⎦
2、{0，2，4}，{5，1，3}
3、2mn ，n m
4、2，3
5、d,b,c ，bade
6、(F()(x))或(F()(x))
x x G x x G ⌝∃∧⌝∀→
7、m6m7
二、。