一、填空题（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>⊕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的命题公式P?Q的主析取范式是 （用mi形式表示最小项）。
二、单选题（20分，每题1分，请将本题答案写在下方表格中！） ．．．．1 11 2 12 3 13 4 14 5 15 6 16 7 17 8 18 9 19 10 20 1、下面给出的符号串集合中，（ ）不是前缀码。 ? B、?01,001,000,10? A、?0,10,110,11111101,1001,101,110,?C、? D、?b,c,aa,ac,aba,abc? 2、下列( )组赋值不是命题公式C?(A??B)的成真赋值。 A、010 B、011 C、110 D、101
3、设A={a，b，c，d}，A上的等价关系R={
A、{{a，b}，{c，d}} B、{{a，b，d}，{c}} C、{{a}，{b}，{c}，{d}} D、{{a}，{b，c}，{d}} 4、二部图K3,3是( ) 。
A、欧拉图 B、 哈密顿图 C、 非连通图 D、完全图
5、令p: 我将去上网，q: 我有时间，则“我将去上网，仅当我有时间”可符号化为( )。
(A) p?q (B) p?q (C)q?p (D)?p??q
6、下面（ ）图不一定是树。
A、每对结点间都有路的图 B、无回路的连通图
C、连通但删去一条边则不连通的图 D、有n个顶点n—1条边的连通图 7、集合A = {1, 2, …, 10}上的关系R ={
(A) 自反的 (B) 传递的、对称的 (C) 对称的 (D) 反自反的、传递的 8、设G如右图，那么G不是( )。 (A)哈密顿图 (B)完全图 (C)欧拉图 (D)树
?0?19、设图D的邻接矩阵为??1??1??11111?0100??，则D的顶点数与边数分别为
1011??0101?0110??( ) 。
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阶完全无向图K4中含3条边的不同构的生成子图有( )。 (A)5 (B)4 (C)3 (D)2
14、任意12阶群的子群的阶一定不为 ( )。 (A)3 (B)6 (C)8 (D)4 15、在公式?xF(x， y)→ ? yG(x，y)中变元x是( )。
(A) 既是自由变元，又是约束变元 (B) 既不是自由变元，又不是约束变元 (C) 自由变元 (D) 约束变元
16、设图G=
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、2 B、3 C、 2 D、2
19、设Z是整数集合，“+”是数的加法运算，则
20、设R和S是集合A={1，2，3，4}上的二元关系，则S是R的（ ）闭包。
3
2
2332R = {?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＝{
(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都是群
2、要在七天安排七场考试，同一个老师监的任何两场考试不能安排在接连的两天内进行。假如每个教师最多监四场考试，请证明：安排这样的考试日程表是可以的。
3、设R是集合A上一个等价关系，
S?{?x,y?|x,y?A??z(?x,z??R??z,y??R)}，试证明S也是A
上的一个等价关系。
4、
参考答案
二、 1 C 11 C 2 B 12 B 3 B 13 C 4 B 14 C 5 A 15 A 6 A 16 C 7 C 17 B 8 D 18 D 9 B 19 D 10 C 20 B