一、填空题（10分，每空1分，请将本题答案填在原题横线．．．．
上！） 1设集合X={0，1，2}，R 是X 上的二元关系，R={<0，0>，<0，2>，<1，2>，<2，0>，<2，1>}，则R 的关系矩阵M R = 。 266,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 的命题公式P ∧Q 的主析取范式是 （用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={，，}∪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 = 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|=5，|E|=20，则G 一定是( ) 。 A 、完全图 B 、正则图 C 、多重图 D 、简单图
17给定公式)()(x xP x xP ∀→∃，当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 、23
B 、32
C 、 322
D 、2
32
19设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＝{，，，，，，，}⋃I A，求：
(1) 画出偏序集的哈斯图；
(2) 求子集B={c,d,e}的极大元，极小元，最大元，最小元。
四、证明题（30分，每题7、7、8、8分，请将本题答案写在后面答题纸上！）
1、例如，f和g都是群到群的同态映射，C={x|x∈G1∧f(x)=g(x)}。证明：是的一个子群。
2、要在七天安排七场考试，同一个老师监的任何两场考试不能安排在接连的两天内进行。假如每个教师最多监四场考试，请证明：安排这样的考试日程表是可以的。
二、单选题（20分，每题1分，请将本题答案写在下方表格
．．．．中！）
