离散数学试题库

模拟试题(一)

一、 单项选择题

在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。

1．给定命题公式如下：(?p?q)?(?q?p) 成真赋值的个数为（ ）。

A．1 Ｂ．2 Ｃ．3 Ｄ．4

2. 设个体域D={a,b}，公式?xP?x???xS?x?在A中消去量词后应为（ ） A．P?x??S?x? B．P?a??P?b???S(a)?S(b)? C．P?a??S?b? D．P?a??P?b??S(a)?S(b) 3．若R和S是集合A上的两个关系，则下述结论正确的是（ ）。 A．若R和S是自反的，则R?S也是自反的 B．若R和S是对称的，则R?S也是对称的

C．若R和S是反对称的，则R?S也是反对成的 D．若R和S是传递的，则R?S也是传递的

4．设全集U={1,2,3,...,20},A,B,C是其子集，其A?{x|x?4}，

。 B?{x|x2?6x?7?0},C?{x|x2?100}则~A?~B?~C?（ ）

A．{16,17,18,19,20} B．{1,2,3,4,5} C．{10,11,12,13,14,15} D．{1,2,3,4,5,6,7} 5．下面偏序集构成有界格的是（ ）。

A． Ｂ． Ｃ．<{2,3,4,6,12},|> Ｄ． 6．全体自然数所组成的集合的最小元为（ ）。

A．负数 Ｂ．最小的正数 Ｃ．0 Ｄ．1 7．对任何a?A，形成的A上的等价关系R的等价类[a]R为（ ）。

A．空集 Ｂ．非空集 Ｃ．空集也可以为非空集 Ｄ．{x}x?A} 8．设S=Q?Q，其中Q为有理数集合，定义S上的二元运算“*”，?,?S，有?a,b?*?x,y???ax,by?b?，则是（ ）。

A．可交换的 Ｂ．可结合的

Ｃ．既是可交换的，又是可结合的 Ｄ．不是可交换的，也不是可结合的

?1?09. 设有向图D=的邻接矩阵为A(D)???0??0200011010?0??，则D中v1到v3长度为4的通路有（ ）1??0?条。

A．4 Ｂ．6 Ｃ．8 Ｄ．9 10.下面那种描述的图不一定是树（ ）。

A．无回路的连通图 Ｂ．有n个顶点的n-1条边

Ｃ．每对顶点都有通路的图 Ｄ．连通但删去一条边则不连通的图 11. 一颗二叉树后序遍历的结果是bdeca，中序遍历的结果是badce，则 根结点的右子树有（ ）结点。

A．1 B．2 C．3 D．4 12.设函数f：N→N（N 为自然数集），f(n)=n+1，下面四个命题为真的是 ( )

A. f是单射 B. f是满射 C. f是双射的 D.f非单射非满射 13.设S={0,1},则S满足（ ）。

A. 在普通乘法下封闭，在普通加法下不封闭 B. 在普通加法和乘法下都封闭

C．在普通加法下封闭，在普通乘法下不封闭 D．在普通加法和乘法下都不封闭

1

14. 下图中（ ）是欧拉图。

A B C D

15. 设集合A={a，b，c，d，e}， 偏序关系R的哈斯图如左图所示， 则元素的关系不正确的是（ ）。

A．c?d B．a?e C．a?b D．d?e

ecabdg二、 填空题

f16.设无向图G有12条边，有6个3度顶点，其余顶点度数均小于3，则G种至少有 顶点。 17. 在彼得森图中至少添加 条边才能构成欧拉图。

18.由Huffman算法，带权1,3,4,5,6的最优二叉树的权W(T)= 。

19.设V=为代数系统，其中A={0,1,2,3,4}。?a,b?A,a*b=(ab)mod5。关于运算“*”的幺元是 。

20．设Z为整数集，?a,b?Z，有a?b=a+b-1，则a的逆元= 。

21．集合{a,b,c,d}上关系R的关系图如左所示，则R的传递 闭包（用集合表示）为 。

22.设R是由方程x+3y=12定义的正整数集N上的关系，即{?x,y?|x,y?N?x?3y?12}，则

R?{2,3,4,6}? ，{3}在R下的象是 。

23.若集合A的基数|A|=10，则其幂集|P(A)|= 。

三、计算题

24．判断正整数集合Z+和下面的二元运算是否构成代数系统。如果是，则说明这个运算是否满足交换律、结合律和幂等律，并求出单位元和零元。 (1)a*b=min(a,b) (2)a?b=(a/b)+(b/a)

25.用主析取范式判断?p?q??r与q??p?r?是否等值。 26.

设，为上关系，关系矩阵为

，

。 (3) 求

，

，

，

。

(1) 画出关系图。 (2) 求(4) 指出

具有的性质。(5)

是偏序关系吗？能否画出哈斯图？

2

27．求下图的最小生成树，写出过程，并计算权。

四、证明题

28．在命题逻辑中构造下面推理的证明。

前提：p?s，q?r，?r，p?q 结论：s

29．设无向图G是由k（k≥2）棵树组成的森林，已知G中有n个结点，m条边，证明m=n-k。

30．证明对于任意集合A,B,C，有(A-B)-C=(A-C)-(B-C)

五、应用题

31．75名儿童到公园游乐场，他们在那儿可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘过其中的两种。若每样乘坐一次的而费用是0.50元，公园游乐场总共收入70元，试确定有多少儿童没有乘过其中任何一种。

32．有四个村庄的地下各有一个防空洞甲、乙、丙、丁，相邻两个防空洞之间有地道相通，且每个防空洞各有一条地道与地面相通，如下图所示（图中表示地道）。问能否从某一个防空洞开始，每个地道走一次且仅走一次后回到该防空洞。（要求有一定的分析过程）

模拟试题(二)

三、单项选择题

在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。

1．下列是两个命题变元p，q的小项是（ ）

A．p??p?q B．?p?q C．?p?q D．?p?p?q

2．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ） A．p??q B．p??q C．p?q D．p??q 3．下列语句中是命题的只有（ ）

A．1+1=10 B．x+y=10 C．sinx+siny<0 D．x mod 3=2 4．下列等值式不正确的是（ ）

A．?(?x)A(x)?(?x)?A(x) B．(?x)(B→A(x))?B→(?x)A(x)

3

C．(?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x)

D．( ?x)( ?y)(A(x)→B(y))?( ?x)A(x)→( ?y)B(y)

5．谓词公式?xP(x,y)??t(Q(t,z)→?x?yR(x,y,t))中量词?t的辖域是（ ） A．?t(Q(t,z)→?x?yR(x,y,t)) B．Q(t,z)→?x?yR(x,y,t) C．?x?yR(x,y,t) D．Q(t,z)

6．设R为实数集，函数f：R→R，f(x)=2x，则f是（ ）

A．满射函数 B．入射函数 C．双射函数 D．非入射非满射

7．设A={a,b,c,d}，A上的等价关系R={,,,}∪IA，则对应于R的A的划分是（ ）

A．{{a},{b,c},{d}} B．{{a,b},{c},{d}} C．{{a},{b},{c},{d}} D．{{a,b},{c,d}}

8．设A={?}，B=P(P(A))，以下正确的式子是（ ）

A．{?,{?}}∈B B．{{?,?}}∈B C．{{?},{{?}}}∈B D．{?,{{?}}}∈B 9．设X，Y，Z是集合，“-”是集合相对补运算，下列等式不正确的是（ ）

A．(X-Y)-Z=X-(Y∩Z) B．(X-Y)-Z=(X-Z)-Y C．(X-Y)-Z=(X-Z)-(Y-Z) D．(X-Y)-Z=X-(Y∪Z)

10．设*是集合A上的二元运算，称z是A上关于运算*的零元，若（ ）

A． z?A，且有x*z=z*x=z B．z?A，且有x*z=z*x=x C．z?A，且有x*z=z*x=z D．z?A，且有x*z=z*x=x 11．在正整数Z+上，下列定义的运算中不可结合的只有（ ）

A．a*b=min(a,b) B．a*b=a+b

C．a*b=GCD(a,b)(a,b的最大公约数) D．a*b=a(mod b)

12．设R为实数集，R+={x|x∈R∧x>0}，*是数的乘法运算，是一个群，则下列集合关于数的乘法运算构成该群的子群的是（ ）

A．{R+中的有理数} B．{R+中的无理数} C．{R+中的自然数} D．{1，2，3} 13．设是环，则下列正确的是（ ）

A．是交换群 B．是加法群 C． 对*是可分配的 D．*对 是可分配的 14．图1所示的6个图中，强连通图为（ ）。

图 1

A. (1) (2) (3) B. (4) (5) (6) C. (1) (3) (4) (6) D. (1) (5) (6) 15．设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（ ）

A．2个面 B．3个面 C．4个面 D．5个面

二、填空题

16．前束范式具有形式(Q1V1)(Q2V2)?(QnVn)A，其中Qi(1≤ i ≤n)为 ，A为 的谓词公式。

17．某集合A上的二元关系R具有对称性，反对称性，自反性和传递性，此关系R是 。 18．设Z是整数集，在Z上定义二元运算*为a*b=a+b+a·b，其中+和·是数的加法和乘法，则代数系统的幺元是 ，零元是 。 19．图2所示平面图有3个面R0,R1和R2，其中deg(R0)= 。 20．图3中，结点v2的度数是 。

图2 图3

4

21.设R为A上的关系，则R的自反闭包为 ，对称闭包为 。 22. 公式?(p?q)?(p??q)的主析取范式为 。

三、计算题

23．求出从A={1,2}到B={x,y}的所有函数，并指出哪些是双射函数，哪些是满射函数。 24．判断下面集合对于给定运算能否构成群，并简要说明理由。 （1）实数集合R关于☆运算，其中a☆b=2(a+b) （2）非零实数集合R*关于⊙运算，其中a⊙b=2ab

25．画出5个具有5个结点5条边的非同构的无向连通简单图。

26．在偏序集中，其中Z={1,2,3,4,6,8,12,24}，≤是Z中的整除关系，画出其哈斯图，并求集合D={2,3,4,6}的极大元，极小元，最大元，最小元，上界，下界，最小上界和最大下界。 27．求图4所示平面图G的对偶图，并判断G是否为自对偶图。

图4

四、证明题

28．证明??p?q???q?r???p?s???s???r??p?q?? 图4 29．证明在无向图中顶点的连通关系是等价关系。

五、应用题

30．对100名工作人员的调查结果表明，有32人学过日语，20人学过法语，45人学过英语。其中15人既学过日语又学过英语，7人既学过日语又学过法语，10人既学过法语又学过英语，30人没有学过这3门语言中的任何一种。求至少学习过以上3种语言中两种语言的人数。

31．设有a,b,c,d,e,f,g等七个人，已知a会讲英语；b会讲英语、汉语；c会讲英、俄语；d会讲日、汉语；e会讲德语、俄语；f会讲法语、日语；g会讲法语、德语。试用图论方法安排园桌座位，使每人都能与其身边的人交谈。

模拟试题(三)

四、 单项选择题

在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。

1．一个公式在等价意义下，下面那个写法是唯一的（ ）。

A．析取范式 B．合取范式 C．主析取范式 D．以上答案都不对

2．令p：今天下雨了，q：我上学，则命题“因为今天下雨了，所以我不上学了”可符号化为（ ）

A．p??q B．p??q C．p?q D．p??q 3．谓词公式?x(P(x,y)??xQ(x,z)→R(x,y,z))中量词?的辖域是（ ）

A．Q(x,z)→R(x,y,z)) B．R(x,y,z)

C．Q(x,z) D．P(x,y)??xQ(x,z)→R(x,y,z)

x4．设R为实数集，函数f：R→R，f(x)=e，则f是（ ）

A．满射函数 B．单射函数 C．双射函数 D．非单射非满射

5．设A={a,b,c,d}，A上的等价关系R={,,,}∪IA，则对应于R的A的划分是（ ）

A．{{a},{b,c},{d}} B．{{a,b},{c},{d}} C．{{a},{b},{c},{d}} D．{{a,b},{c,d}}

5

6．设A={?}，B=P(A)，以下正确的式子是（ ） A．{?,{?}}?A B．{?,{?}}∈A

C．{?,{?}}?B D．{?,{?}}∈B

7．设?G,??是群，a,b?G,则下列结论不正确的是（ ）

A．(ab)?1?b?1a?1 B．ax?b有惟一解 C．ax?ay，则x?y D．ab?ba

8．在自然数集N上，下列定义的运算中不满足结合律的（ ）

A．a*b=min(a,b) B．a*b=a+b C．a*b=gcd(a,b)(a,b的最大公约数) D．a*b=a-b 9．不同构的有2条边的4阶无向简单图的个数为 ( )

A．1 B．2 C．3 D．4

10．4阶无向连通图G是欧拉图，则它的度序列可能是（ ）

A．1,2,3,4 B．2,4,6,8 C．1,2,4,6 D．5,2,3,4 11．下列命题中，（）不是真命题。。

A．海水是咸的当且仅当雪是白的

B．如果成都是直辖市，那么北京是中国的首都 C．若太阳从西边落下，则2是奇数 D．夏天冷当且仅当冬天热

12．设R是集合A＝{1,2,3,4}上的二元关系，R＝{<2,1>,<2,3>,<1,3>},则R不具有下面那种性质（）。

A．自反性 B．反自反性 C ．反对称性 D．传递性 13.下面图中，（ ）是平面图.

A． B． C． D． 14．每个非平凡的无向树至少有（）片树叶。

A．1 B．2 C．3 D．4

15．设简单图G所有结点的度之和为12，则G一定有( )。 A．3条边 B．4条边 C．5条边 D．6条边

二、填空题

16．量词否定等值式??xA(x)? ___________________。

17.关于命题变项p,q,r的命题公式的主析取范式是m1?m3?m5?m6?m7,则主合取范式是(用公式表示) _ .

18.设R={,,}，则dom(R) = 。

19.设G是连通的 n阶m条边r个面的可平面图，则反映结点数、边数、面数之间关系的欧拉公式是___________________。

20.无向图G=,V={a,b,c,d},E={e1,e2,e3,e4},其中e1=(a,a),e2=(a,d),e3=(a,c),e4=(b,c)},则它的关联矩阵为：

21．设S(x)∶x是大学生；K(x)∶x是运动员。则命题：“有些运动员不是大学生”的符号化为 。

， 2， 3， 4， 5 }，R?A?A，R?{ ?1， 2?， ? 3， 4?， ? 2， 2? }求22．设A?{ 1r(R)= ，s(R)=

23．设G是完全二叉树，G有15个点，其中8个叶点，则G的总度数为__________，分枝点数为________________。

三、计算题

24． A={a,b,c}, R1={,,,}, R2={,,},求：(1) R1 (2)

-1

6

25.已知图G有10条边,4个3度结点,其余结点的度数均小于等于2,问该图至少有几个结点?为什么?

26.下图是偏序集的哈斯图， 求

hgebafcdR2?R1 (3) R1在A上的限制

（1）写出集合A,R;

（2）求A的极大元和极小元；

（3）求B={e,f}的上确界和下确界。

27.命题公式F含有3个命题变项p,q,r，其所有成真赋值为：000，001，110，111，求：(1)画出真值表；(2)写出主析取范式；(3)指出公式的类型 28．求下图的最小生成树，写出过程，并计算权。

5a5bf127h664c8e6d3

四、证明题

29．证明对于具有k（k≥2）个连通分支的平面图G，有n-m+r=k+1。其中n,m,r分别为G的顶点数，边数和面数。

30．设A={1，2，3，4}，关系R?(A?A)?(A?A)，

R?{??a,b?,?c,d??|a?d?b?c，a,b,c,d?A}，证明：R是等价关系 五、应用题

31．下述逻辑推理是否有效？证明你的结论。

所有羊都吃草，所有死羊都不吃草。所以，所有死羊都不是羊。

32．已知英文字符串adacatedecade，试用二进制字符串代替此英文字符串，并保证该英文字符串与二进制串构成一一对应。

模拟试题(四)

一、单项选择题

在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。

1．设命题公式G=?(p→q), H=p→(q→?p)，则G与H的关系是( )

A.G?H B.H?G C.可满足 D.以上都不是

2．设集合A={1,2,3,…,10}，关于集合A为不封闭的运算是（ ）。 A.x*y=max{x,y} B. x*y=min{x,y}

C.x*y=x与y的最大公约数 D. x*y=x与y的最小公倍数 3．设论域E={a,b}，且P(a,a)=T，P(a,b)=F，P(b,a)=T，P(b,b)=F 则在下列公式中真值为T的是( )

A.?x?yP(x,y) B.?x?yP(x,y) C.?xP(x,x) D. ?x?yP(x,y) 4．设A={a,{a}},下列式子中正确的有（ ）。

A. {a}?P(A) B. a?P(A) C. {a}?P(A) D. 以上都不是

5．设R,S是集合X={1,2,3,4}上的两个关系，其中R={<1,1>,<2,2>,<2,3>,<4,4>}, S={<1,1>,<2,2>,<2,3>,<3,2>,<4,4>}。则S是R的（ ）闭包。

A.自反 B.对称 C.传递 D.以上都不是

6．设S={1,1/2,2,1/3,3,1/4,4}，“*”为普通乘法，则是（ ）。

A.半群，但不是独异点 B.是独异点，但不是群 C.群 D. 不是代数系统 7．设集合A={a,b}，A上的关系R={,}，则R是（ ）

7

A. 是等价关系但不是偏序关系 B.是偏序关系但不是等价关系

C. 既是等价关系又是偏序关系 D. 既不是等价关系又不是偏序关系 8．G是连通的平面图，有5个结点，6个面，则G的边数为（ ）

A. 6 B. 5 C.11 D. 9 9．下面命题中，为真的是（ ）。

A. 完全图Kn(n≥1)都是欧拉图 B.完全二部图Kn,m(n≥1,n≥1)都是欧拉图 C. 完全图Kn(n≥3)都是哈密顿图 D.完全二部图Kn,m(n≥1,n≥1)都是哈密顿图

10．设集合A={a,b,c,d},B={1,2,3,4},则从A到B的函数f={,,,}是（ ）。

A. f是双射函数 B. f是入射函数

C. f是满射函数 D. f即不是满射又是不是入射函数 11．设?G,??是群，a,b?G,则下列结论不正确的是（ ）

A．(ab)?1?b?1a?1 B．ax?b有惟一解 C．ax?ay，则x?y D．ab?ba

12．在自然数集N上，下列定义的运算中不满足结合律的（ ）

A．a*b=min(a,b) B．a*b=a+b C．a*b=gcd(a,b)(a,b的最大公约数) D．a*b=a-b 13．在简单无向图G = (V, E) 中，如果V中的每个结点都与其余的所有结点邻接，则该图称为( )。 A．连通图 B．强连通图 C．完全图 D． 平凡图。

14．对一阶逻辑公式?x?y(P(x,y)?Q(y,z))??xP(x,y)的说法正确的是( ).

A．x是约束的，y是约束的，z是自由的;

B．x是约束的，y既是约束的又是自由的，z是自由的; C．x是约束的，y既是约束的又是自由的，z是约束的; D．x是约束的，y是约束的，z是约束的. 15.下面图中，（ ）是平面图.

A． B． C． D． 二、填空题

16．已知集合A={?,1, 2}，则A的幂集为____________________。

17．已知命题公式G=(?p→q)?r,则G的主合取范式是______ __。

18．在有理数集合Q上定义二元运算“*”，?x,y?Q有x*y=x+y-xy，则当?x?Q，当x?-1时，其逆元为 。

-1

19．设集合A={a,b,c,d}，A上关系R={,,,} ,则关系RoR=_____________。 20．设A={0,2,3,4,5,8 },B={10,12,13,14,15,16},则A到B的一个双射函数为_______________。 21．无孤立结点的有限有向图是欧拉图的充要条件是___________ _。 22．具有16个结点的完全有向图其边数一定为______________。 23．设a是群的幂等元，则a一定是 。

24．设G是完全正则二叉树，G有15个点，其中8个叶点，则G的总度数为__________，分枝点数为________________。

三、计算题

25．设集合A={1,2,3}，试写出A上的所有等价关系。 26.是否可以分别画出一个图，使各点的度与下面给出的序列一致。如可能，画出符合条件的图，如不可能，说明原因。

（1）3，3，3，3，3，3 （2）3，4，7，7，7，7 （3）1，2，3，4，5，5

27.设T是如下的二叉树，写出对T进行先序遍历、中序遍历和后序遍历时访问节点的顺序。

8

28.设R是实数集，At={x|x?R?Kt≤x≤t+1}，其中K0= K2=0，K1= K3=-1，K4=-2，令S={ At |t=0,1,2,3,4}。画出偏序集的哈斯图，并求它的极大元、极小元、最大元和最小元。说明该偏序集构成什么格？

29．给定解释如下：

（1）D?{2,3} （2）a?2 （3）f(2)?3,f(3)?2

（4）F(x):F(2)?0,F(3)?1 G(x,y):G(i,j)?1,i,j?2,3

L(x,y):L(2,2)?L(3,3)?1 L(2,3)?L(3,2)?0 求下列各式的值，并说明理由：

（1）?x?F(x)?G(x,a)? （2）?x?F(f(x)?G(x,f(x))? （3）?x?yL(x,y)

四、证明题

30．设A,B为任意集合，E为全集，证明：B?~((~A?B)?A) = E。 31．证明：任何图（无向图或有向图）中，奇度顶点的个数是偶数。 32．设函数f：A→B，g：B→C，f、g都是双射函数。求证(fog)=gof。

-1

-1

-1

五、应用题

33．在谓词逻辑中构造下面推理的证明：所有不守信用的人都是不可信赖的，有些可以信赖的人是受过教育的。因此，有些受过教育的人是守信用的。（个体域：所有人的集合）

34．构造欧拉图，其结点数v和边数e满足下述条件：（1）v,e的奇偶性一样；（2）v,e的奇偶性相反。如果可能，分别画出两个欧拉图；如果不可能，说明原因。

模拟试题(五)

一、单项选择题

在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。

1．设p:天下大雨，q:小王乘公共汽车上班，命题“只有天下大雨，小王才乘公共汽车上班”的符号化形式为（ ）。

A．p→q B．q→p C．p→?q D．?p→q

2．设解释I如下，个体域D={a,b},F(a,a)=(b,b)=0,F(a,b)=F(b,a)=1，在解释I下，下列公式中真值为1的是（ ）。

A．?x?yF(x,y) B．?x?F(x,y) C．?x?yF(x,y) D．??x?yF(x,y) 3．设G为n阶m条边的无向简单图，下列命题为假的是（ ）。 A．G一定有生成树 B．m一定大于n

C．G的边色数χ'≥Δ(G) D．G的最大度Δ(G)≤n-1 4．设G为完全二部图K2,3，下面命题中为真的是（ ）。

A．G为欧拉图 B．G为哈密尔顿图 C．G为平面图 D．G为正则图 5．对于任意集合X,Y,Z，则（ ）。

9

A．X?Y=X?Z?Y=Z B．X?Y=X?Z?Y=Z C．X－Y=X－Z?Y=Z D．X?Y=X?Z?Y=Z 6．设Z是整数集合，“+”是一般加法，则下述函数中不是群的自同态的是（ ）。 A．f(x)=x B．f(x)=1000x C．f(x)=|x| D．f(x)=0

7．设R为实数集，定义*运算如下：a*b=|a+b+ab|，则*运算满足（ ）。 A．结合律 B．交换律 C．有幺元 D．幂等律 8．设G是一个哈密尔顿图，则G一定是( )。

A．欧拉图 B．树 C．平面图 D．连通图 9．下面给出的集合中，哪一个是前缀码？( )

A．{0，10，110，101111} B．{01，001，000，1}

C．{b，c，aa，ab，aba} D．{1，11，101，001，0011}

10．设G是有n个结点m条边的连通平面图，且有k个面，则k等于( )。

A.m-n+2 B．n-m-2 C．n+m-2 D．m+n+2。 11．在自然数集N上，下列哪种运算是可结合的？（ ）

A．a*b=a-b B．a*b=max{a,b} C．a*b=a+2b D．a*b=|a-b|

12．集合A={1,2,?,10}上的关系R={|x+y=10,x,y?A}，则R满足（ ）。 A．自反性 B．对称性 C．传递性，对称性 D．传递性

2213．设P={x|(x+1)?4且x?R},Q={x|5?x+16且x?R},则下列（ ）正确。 A．Q?P B．Q?P C．P?Q D．P=Q

14．Q是有理数集，（其中*为普通乘法）不能构成( )。

A．群 B．独异点 C．半群 D. 交换半群

15．若一棵完全二元（叉）树有2n-1个顶点，则它（ ）片树叶。

A．n B．2n C．n-1 D．2

二、填空题

16．含n个命题变项的重言式的主合取范式含_______个极大项。

17．在有理数集Q上定义二元运算“*”，?x,y?Q有x*y=x+y-xy，则关于运算“*”的幺元是 。?x?Q，当x?1时，其逆元为 。 18．以1，1，1，2，2，3为度数序列的非同构的无向树共有___________棵。 19．已知n阶无向简单图G有m条边，则G的补图G有__________条边。 20．设R={<{1},1>，<1,{1}>，<2,{3}>，<{3},{2}>}，则ranR=_____________。 21．设A={1,2,3,4}，则A上有____________个不同的双射函数。 22．任一有向图中，度数为奇数的结点有_____________个。

23．令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为 。

24．设G={0,1,2,3}，?为模4加法，群中的4阶元是 。

三、计算题

x?yx?y?25．设X={1,2,3,4}，若H??是正整数}，求 是整数? ，S?{?x,y???x,y?|?2?3H?S,~H,S?H。

26.有向图D=如下图所示，

10

求：（1）D中v1到v4的长度为1,2,3的通路各有几条？ （2）D中长度≤3的通路共有几条？其中几条是回路？

27.设A={x|x?R?x?0,1}。在A上定义6个函数如下：

?1?1f1?x??x,f2?x??x?1,f3?x??1?x,f4?x???1?x?,f5?x???x?1?x?1,f6?x??x?x?1?令F为

这6个函数构成的集合，?运算为函数的复合运算。

（1）给出?运算的运算表。 （2）验证是一个群。

28．（5分）设图G有一棵树，它有n2个2度分支点，n3个3度分支点，…,nk个k度分支点，求G中叶结点数。

四、证明题

29．设正整数的序偶集合A，在A上定义的二元关系R如下：<,>?R?xv=yu。证明R是一个等价关系。

30．证明在任何n阶有向完全图中，所有结点入度的平方之和等于所有结点的出度平方之和。

五、应用题

31．将下列推理符号化并给出形式证明：

鸟会飞，猴子不会飞，所以，猴子不是鸟。

32．）某城市拟在六个区之间假设电话网，其网点间的距离如下带权矩阵给出，试给出架设线路的最优方案，请画出图并计算出线路长。

模拟试题(六)

五、

单项选择题

在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。 1、若p：他聪明；q：他用功；则“他虽聪明，但不用功”，可符号化为??( )

A. p∨q B. p∧┐q C. p→┐q D. p∨┐q

2、以下命题公式中，为永假式的是?????????????? ( )

A.p→(p∨q∨r) B.(p→┐p)→┐p

11

C.┐(q→q)∧p D.┐(q∨┐p)→(p∧┐p)

3、关于命题变元p和q的大项M01表示????????????( )。

A. ┐p∧q

B. ┐p∨q C. p∨┐q

D. p∧┐q

4、下列式子正确的是?????????????????? ( ) A. ?∈? B. ??? C. {?}?? D.{?}∈? 5、设R,S是集合X={1,2,3,4}上的两个关系，其中 R={<1,1>,<2,2>,<2,3>,<4,4>},S={<1,1>,<2,2>,<2,3>,<3,2>,<4,4>}。

则S是R的（ ）闭包。

A.自反 B.对称 C.传递 D.以上都不是 6、设A={a,b,c}，则下列是集合A的划分的是???????? ( )

A.{{b,c},{c}} B.{{a,b},{a,c}} C.{{a,b},c} D.{{a},{b,c}}

7、.下列不是平面图的是?????????????? ( )

8、G是连通的平面图，有9个结点，11个面，则G的边数为??（ ）

A. 16 B. 15 C.17 D. 18

9、在自然数集N上，下列哪种*运算是可结合的??????（ ） A. a*b=a-b B. a*b=max{a,b} C. a*b=a+2b D. a*b=|a-b| 10、不能构成代数系统的是???????????????（ ）

A.有理数集合Q，x*y=(x+y)/2 B.自然数集合N，x*y=2xy C.A＝R，x*y=|x-y| D.A={1,-2,3,2,-4}, x*y=|y|

六、

填空题

11、已知公式A含有3个命题变项p，q，r，并且它的成假赋值为000，011，110， 则A的主析取范式为___________________________________________________， A的主合取范式为 __________________________________．

12、令p: a能被4整除，q：a能被2整除，则命题“只有a能被4整除，a才能被2整除”符号化为_____________________。

13、集合{{?，2},{2}}的幂集为_________________________________________。 14、设f：R→R,f(x)=x2-3x+2,，其中R为实数集，则f ({1,3})－f-1({6})=______ 15、完全二部图K3,4中，点连通度κ为_______，边连通度λ为______，点色数? 为_________，边色数?’为________，匹配数?1为_______。

12

七、 解答题

16、使用容斥原理解题：

某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有两人会打这三种球。已知6个会打网球的人都会打篮球或排球。求不会打球的人数。 17、给出偏序集上偏序关系R的关系图（如下图所示）。 （1）求偏序集的哈斯图。

b a c d （2）指出A的最大、最小元（如果有的话），极大、极小元。 （3）指出该偏序集是格吗？请说明理由

e 18、一棵树有n2个结点度数为2 ，n3个结点度数为3，? ，nk个结点度数为k ，问它有几个度数为1的结点。

19、已知某系统在通讯联络中只可能出现5种字符{a,b,c,d,e}，其概率分别为0.10，0.22，0.27，0.15，0.26，试画出赫夫曼树并设计赫夫曼编码。

20、若S={1,2,3,…… ,19,20,21}，设R为S上的等价关系，且由x?y (mod 5)所定义，即x ? y 能被10整除。（1）写出由R导出的S的划分∏；（2）求出商集S/R； （3）设I为S上的恒等关系，试求R⊕I。

四、证明题

21．如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C++语言。只要他学过DELPHI语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。（10分） 22、设A，B，C是任意集合，证明：（A-B）∪(B-A)=(A∪B)-(A?B)（5分）

23．设R是实数集合，S={（a, b）︱a≠0,a,b ∈R},利用通常的加法和乘法在S定义“*”如下：对S

中的任意元素(a, b)，(c, d)

(a, b)* (c, d)=(ac, ad+b)

证明S对“*”运算做成群.（10分）

模拟试题(七)

八、 单项选择题

在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。 1、已知：已知|G|=18，其某一子群|H|=6，则|G：H|为???（ ） A、18 B、6 C、3 D、不确定值

2、公式p∧┐(q→p)的类型为??????????????? ( )。

13

A. 永真式 B. 永假式 C. 可满足式 D. 一般命题公式

3、设解释R： 论域D为实数集，a=0，f(x,y)=x-y，A(x,y)：x

在R下为真的是????????????????( ) A. ?x?y?z (A(x,y)→A(f(x,z),f(y,z)) C. ?x?y（A(f(x,y),x))

B. ?x A(f(a,x),a)

D.?x?y (A(x,y)→A(f(x,a),a))

4、设A={a,{a}},下列式子中正确的有?????????（ ）。 A. {a}∈ρ(A) B. a∈ρ(A) C. {a}?ρ(A) D. 以上都不是

5、设集合A={1, 2, 3 }，A上的关系R={<1, 1 >,<2, 2 > }，则R不具有（ ）性质。

A.自反性 B.对称性 C.传递性 D. 反对称性

6、无向图G中有16条边，且每个结点的度数均为2，则结点数是???( )

A.8 B.16 C.4 D.32

7、?xF(y,x) →?yG(y)的前束范式为?????????????( )

A.?x?y(F(z,x)?G(y))； B.?x?y(F(z,x)?G(y))； C.?x?y(?F(z,x)?G(y))； D.?x?y(F(z,x)?G(x))；

8、设S??a,b,c,d?，在S上定义等价关系R?IS???a,b?,?b,a??，那么该等价关系对应的划分中有 ( )个划分块。 A. 1

B. 2

C. 3

D. 4

9、下列各图不是欧拉图的是???????????????（ ）

10、设Z为整数集合，*为Z上的二元运算，x*y=x+y-3, 则Z 关于*运算构成群，已知5*x = 4，则 x 为??????????????????( )

A.5/4 B.4/5 C.2 D.3

九、 填空题

11、已知公式A含有3个命题变项p，q，r，并且它的成假赋值为001,010,100,101,111, 则A的主析取范式为___________________，A的主合取范式为 ________________． 12、符号化命题：除非a能被2整除，否则a不能被4整除。_____________________。 13、 在一个群〈G,*〉中，若G中的元素a的阶是k，则a的阶是__________.

-1

14

14、集合{{?，2},?}的幂集为_________________________________________。 15、设A=?，B={1,2,3}，则A×B= 。

16、Q为有理数集，Q上定义运算 * 为a*b=a+b-ab，则的单位元是 。 17、完全二部图K4,5中，点连通度κ为_______，边连通度λ为______，点色数? 为_________，边色数?’为________，匹配数?1为_______。

十、 解答题

18、对60个学生参加课外活动的情况进行调查。结果发现，25人参加物理小组，26人参加化学小组，26人参加生物小组。9人既参加物理小组又参加生物小组，11人既参加物理小组又参加化学小组，8人既参加化学小组又参加生物小组。8人什么小组也没参加，请回答：（1）有多少人参加了3个小组？（2）只参加一个小组的有多少人？。

19、无向树T有1个2度顶点，3个3度顶点, 4个4度顶点, 1个5度顶点,其余的都是树叶，则T有几片树叶？ 20、设A={1,2,3,4,5},A上偏序关系R={<1,2>,<3,2>,<4,1>,<4,2>,<4,3>,<3,5>,<4,5>}∪IA; (1)作出偏序关系R的哈斯图 (2)令B={1,2,3,5}，求B的最大、最小元，极大、极小元，上界，上确界，下界，下确界。 21、画出如下所示图的一棵最小生成树，并计算最小生成树的权重。(10分)

22、设为模6加群，求商群Z6/<2>。

四、证明题

23、对任意集合A，B，C，证明：（A － B）? B = A ∪B

24、在一阶逻辑自然推理系统F中构造下面推理的证明 每个喜欢步行的人都不喜欢骑自行车，每个人或者是喜欢骑自行车或者喜欢乘汽车，有的人不喜欢乘汽车，所以有的人不喜欢步行。（个体域为人的集合）。

25、设正实数集合R+和实数集合R，+和x是普通加法和乘法，定义映射f:R??R，

?x?R?,f(x)?lnx，证明f是从?R?,??到?R,??的同构。

模拟试题(八)

十一、 单项选择题

在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。 1、若p：天下大雨；q：他乘公共汽车上班；则“除非天下大雨，否则他不乘公共汽 车上班。”可符号化为?????????????? ( )

A. p∨q B. p∧┐q C. p→┐q D . q→p

2、?xF(y,x)??yG(y)的前束范式为?????????????( )

15

A.?x?y(F(y,x)?G(y))；B.?x?y(F(z,x)?G(y))； C.?y?x(?F(z,x)?G(y))；D.?x?y(F(x,z)?G(x,y))；

3、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式 ?x (P(x)?Q(x)) 在哪个个体域中为真( ) A. 自然数 B. 实数 C.复数 D. A--C均成立

4、令 F(x): x是兔子，G(x): x是乌龟，H(x,y): x比y跑得快，命题“并不是所有的兔子比乌龟跑得快”可以符号化为 ???????????????（ ）

A. ??x?y(F(x)?G(y)?H(x,y))；B. ??x?y(F(x)?G(y)?H(x,y))； C.??x?y(F(x)?G(y)?H(x,y))；D. ??x?y(F(x)?G(y)?H(x,y)) 5、设S?{?,{1},{1,2}}，则P(S)有( )个元素

A. 3

B. 16

C. 6

D. 8

6、设S?{1,2,3}，左图是S上关系R1的关系图，

则它具有( )性质.

A. 自反的，对称的，传递的；B. 反自反的，反对称的；C. 自反的，传递的； D. 自反的； 7、设V??R?,··?，其中·为普通乘法，对任意x?R令?1(x)?2x，?2(x)??x2，

?(x)?31，

x?(x)??x，则其中有（ ）个是V的自同态，

4A. 0 B.1 C.2 D.3

8、设Z是整数集合，则下面定义的二元运算不能使Z与?构成代数系统的是( ) A. i?j=|i-j|,?i,j∈Z B. i?j=i·j-j2，?i,j∈Z C. i?j=i/j,?i,j∈Z D. i?j=i2+j2+1,?i,j∈Z 9、设?G,??是群，a,b?G,则下列结论不正确的是??????????（ ）

A.(ab)?1?b?1a?1 B.ax?b有惟一解 C.ax?ay,则x?y D.ab?ba

10、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。

A. 10 B. 4 C. 17 D. 16

十二、 填空题

11、命题公式 ?(p?q)?r的主析取范式中含极小项的个数为_____，成真赋值为________。 12、令F(x)：x是人。G(x)：x犯错误。则命题“没有不犯错误的人”符号化为_________________ 13、设n阶无向简单图G中，?(G)?n?1，问?(G)为____________. 14、素数阶群一定是______________群, 它的生成元是_________________。 15、全二部图Kn,m(n?1,m?1)都是欧拉图，这个命题的真值为_________________;

16

16、群 ，?为模6加法运算，则子群H＝{0,2,4}的所有的右陪集为_______, _________. 17、集合A的一个划分，确定A的元素间的关系为___________

18、设Z是整数集，在Z上定义二元运算*为a*b=a+b+a·b，其中+和·是数的加法和乘法，则代数系统的幺元是 ，零元是 。

十三、 解答题

19、求?(p?q)?r 的主析取范式和主合取范式。

20、用容斥原理解题：

某班级有学生四十名，共有三门选修课可供选择，选修课课程名称分别为A、B、C，其中有15名学生选A课程，有10名学生选B课程，6名学生选C课程，而且其中有5名学生三门课程都选。问至少有多少学生三门选修课一门也没选？

,22,55,110}是110的正因子集，?A,??构成偏序集，其中?为整除关系。21、设A?{1,2,5,10,11（1）画出偏序集?A,??的哈斯图。

（2）说明该偏序集是否构成布尔代数，为什么？

22、设某编码系统中只出现A,B,C,D,E,F,G,H等八个字符，它们的使用频率相应为

0.05,0.07,0.25,0.15,0.08,0.12,0.06,0.22，画出相应的哈夫曼树，然后给出各字符的哈夫曼编码。

24、今有工人甲、乙、丙要完成三顶任务a,b,c，已知工人甲能胜任a,b,c三项任务；工人乙能胜任a,b,两项任务；工人丙能胜任b,c两项任务，给出一种可能的安排方案，使得每个工人各完成一项他们能胜任的任务。

四、证明题

25、构造推理证明。

前提：(P→Q)?(R→S)，(Q→W)?(S→X)，?(W?X)，P→R 。 结论：

?p。

26、设正整数集合

I?上的二元关系

R?{?x,y?|x,y?I?,x?y?I}2，证明：R为等价关系。

27、设G1＝,G2=,其中R*为非零实数的集合，＋和 . 分别表示数的加法和乘法。 f：Z－>R*, f(x)= 1

1 x是偶数

－1 x是奇数 （1）验证f为同态映射。（4分） （2）说明f是否为单同态和满同态。（4分） （3）计算 kerf。(2分)

模拟试题(九)

17

十四、 单项选择题

在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。 1、若p：天下大雨；q：他乘公共汽车上班；则“仅当天下雨的时候他才乘公共汽车上班。”，可符

号化为( ) ，

A. p∨q B. p∧┐q C. p→┐q D . q→p 2、使命题公式p→(p∧q)为假的赋值是( )

A.10 B.01 C. 00 D.11 3、设S?{1,2,4,8,16}，?是S上的整除关系，则?S,??的哈斯图是( )

A. 一棵树；B. 一条链；C. 一些独立的点； D. 以上都不对

4、设函数f：N→N（N 为自然数集），f(n)=n+1，下面四个命题为真的是( ) A. f是单射 B. f是满射 C. f是双射的 D.f非单射非满射 5、设S?{1,2,3}，左图是S上关系R的关系图， 则它具有( )性质.

A. 自反的，对称的，传递的；B. 反自反的，反对称的；

C. 自反的，传递的； D. 自反的，对称的，反对称的，传递的。 6、设X，Y，Z是集合，下列结论不正确的是（ ） ．．．

A．若X?Y,则X∩Y=X B．(X-Y)-Z=X-(Y∩Z) C．X?X?? D．X?Y?X?(~Y) 7、设G?{0,1,2,3}，若?为模4加法，则中的4阶元是（ ）。

A.0;

B.1和3

C.2；

D.不存在。

8、4阶无向连通图G是欧拉图，则它的度序列可能是（ ）

A.1,2,3,4 B.2,4,6,8 C.1,2,4,6 D.5,2,3,4 9、下面给出的符号串集合中，( )是前缀码：

B1?{0,10,110,1111}

B2?{1,01,001,0011}B3?{1,11,101,001,0011}

B4?{a,c,,aa,ac,aba,abb,abc} B5?{b,c,a,aa,ac,aba,abb,abc}

A.B1 B. B1、B2和B3

C.B4和B5

D.以上都不对

10.G??1,?1,i,?i?　,?是一个群(其中?是数的乘法运算,i?下列代数系统为G的子群的是(　　　　)

?1),

A.<{-1},×> B. <{i},×> C. <{i,-i},×> D. <{1,-1},×>

11、以下系统是代数系统的是（ ）

B.，其中A={a,b}，*运算定义为 C. ，其中Z为整数集，÷是数的除法运算 D. ，其中R为实数集，÷是数的除法运算

12、设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（ ） A．2 B．3 C．4 D．5

十五、 填空题

13、量词否定等值式??xA(x)? ___________________。

14、设F(x):x是人，H(x):x呼吸，在一阶逻辑中，命题“凡是人都呼吸”的符号化形式为________

18

15、设D是n阶有向简单图，D'是D的子图，已知D'的边数m'?n(n?1)，则D的边数m为_______.

16、完全二部图Kr,s中，边数m为_______________________ 17、 设S?{1,2,3,4}，R为S上的关系，其关系矩阵是：??1001??1000?，则R的关系表达式是??0001???1000??_____;R的对称闭包是_____, domR?_____，ranR?_____; R?R中有_____有序对;R?1的关系图中有_____个环。

十六、 判断系统是否具有右边的性质,有(√)，没有(×).

17、 性 名 质 运算满足运算满足一定有一定有每个元素运算满足称 封闭性 结合律 零元 单位元 都有逆元 交换律 代数系统 半群 独异点 群 Abel群

十七、 简答题

18、求公式(r→q)?p的主析取范式和主和取范式。

19．求公式(?x F(x,y) ??y G(y)) ? ?x H(x,y,z) 的前束范式。 20、给定算式{[(a?b)*c]*(d?e)}?[f?(g*h)]. （1）用二叉有序正则树表示上述算式

（2）给出此算式的逆波兰符号（即前缀符号法）表示式和波兰符号表示式（即后缀符号法）。 21、今有a,b,c,d,e,f,g7个人，已知：a会讲英语；b会讲英语和汉语；c会讲英语、意大利语和俄语；d会讲日语和汉语；e会讲德语和意大利语；f会讲法语、日语和俄语；g会讲法语和德语；试问这7个人应如何排座位，才能使每个人都能和他身边的人交谈？ 22、对于下图，利用克鲁斯克尔算法求一棵最小生成树，并计算权重W(T)。

四、证明题

23、在自然推理系统F中，构造下列推理的证明。 前提： ?x(A(x)?B(x)∧J(x))，?x (A(x)∧H(x)) 结论： ?x (A(x) ∧ B(x)∧H(x))

24、对任意集合A,B，证明：若A??，A?B=A?C，则B=C。

25、设自然数集N上的关系R定义为：R??nnm1,n21,n2?N,n1/n2?2,m?I?，

19

其中I为整数集合，证明：R是N上的等价关系

模拟试题(十)

十八、 单项选择题

在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。 1、若p：他怕困难；q：他战胜困难；则“他战胜困难是因为他不怕困难。”，可符号化为 ( ) A. p∨q B. p∧┐q C. p→┐q D . q→p 2、?x(F(x,y)??yG(x,y))的前束范式为???????（ ）

A.?x?y(F(x,z)?G(x,y))；B.?x?y(F(x,z)?G(x,y))； C.?y?x(F(x,z)?G(x,y))；D.?x?y(F(x,y)?G(x,y))；

3、设A={a,b,c,d}，A上的等价关系R={,,,}∪IA，则对应于R的A的划分是（ ）

A.{{a},{b,c},{d}} B.{{a,b},{c},{d}} C.{a},{b},{c},{d}} D.{{a,b},{c,d}}

4、设S??a,b,c?，则集合T??a,b?的特征函数是( )

A. {?a,a?,?b,b?,?c,c?}; B.{?a,b?}; C. {?a,1?,?b,1?,?c,0?};

D.{?a,{a}?,?b{b}?,?c{c}?};

5、设X={1, 2, 3}，Y={a, b}，作f：X→Y，则不同的函数的个数为（ ）个。

A、2+3 B、23 C、2×3 D、32

6、设R,S是集合X={1,2,3,4}上的两个关系，其中 R={<1,1>,<2,2>,<2,3>,<4,4>},S={<1,1>,<2,2>,<2,3>,<3,2>,<4,4>}。则S是R的（ ）闭包。

A.自反 B.对称 C.传递 D.以上都不是

7、一棵树有5个2度顶点，2 个3度顶点，1个4度顶点，则其1度顶点为（ ）。

A. 5 B. 6 C.12 D. 19 8、 设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（ ）

A．2 B．3 C．4 D．5

9、在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( ) A. b∧(a∨c) B. (a∧b)∨(a’∧b) C. (a∨b)∧(a∨b∨c)∧(b∨c) D.(b∨c)∧(a∨c) 10、完全二部图Kr,s,中，点色数为 ( )个

A.2 B.r C.s D.rs

11、设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交运

20

算，下列系统中是代数系统的有 ( )

A.〈Z，+，/〉 B.〈Z，/〉

C.〈Z，-，/〉 D.〈P(A)，∩〉 12、下列各代数系统中不含有零元素的是 ( )

A.〈Q，*〉Q是全体有理数集，*是数的乘法运算

B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算 C.〈Z，?〉，Z是整数集，?定义为x?xy=xy,?x,y∈Z D.〈Z，+〉，Z是整数集，+是数的加法运算

十九、 填空题

13、 给定命题公式如下：p→(p?(q→p))，该公式的成真赋值为_____，成假赋值为____,公式的类型为_____。

14、 令 F(x)：x是人。G(x)：x喜欢吃馒头，H（x）：x喜欢吃米饭。

命题“虽然有人不喜欢吃馒头，但也不是所有的人都喜欢吃米饭”的符号化为______ 15、 集合{?, {?，2}}的幂集为___________。

16、集合A={1,2,?,10}上的关系R={|x+y=10,x,y?A},则R的性质为__________ 17、A = {a,b,c,d}, B ={0, 1, 2}, 则cardBA＝__________

18、.若G是6阶12条边连通简单的平面图，则G有____个面，每个面的次数为_____ 19、设T为n(n>=2)阶，m条边的无向连通图G的生成树，若T无弦，则G为_____ 20、. 设〈B,∧,∨,′，0，1〉是布尔代数，对任意的a∈B,有a∨a′=____,a∧a′=______。

二十、 解答题

21、求公式?(p→q)?(r?p)的主合取范式和主析取范式.

22、求带权2、3、5、7、11、13的最优二叉树,并给出每个结点的huffman编码。 23、设A?{1,2,3,4,5},?P(A),??构成群，其中?为集合的对称差。

（1）求解群方程{1,3}?X?{3,4,5}。 （2）令B?{1,4,5}，求由B生成的循环子群?B? 24、分设A?{1,2,3,4,5},A上二元关系R?{?1,1?,?2,3?,?2,4?,?3,2?,?3,4?}，请画出关系矩阵，并求R自反闭包、对称闭包、传递闭包（方法不限）。

25、（6分）一次学术会议的理事会共有20个人参加，他们之间有的相互认识但有的相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于20。问能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人?为什么?

四、证明题

26、在一阶逻辑中构造下面推理的证明。

已知今天下雨或刮风；如果今天下雨，那么我在家看书；如果今天刮风，那么我去放风筝；今

天我没有在家看书。所以今天刮风并且我去放风筝了。

27、设A，B，C是任意集合，证明：(A-B)-C?A-(B-C)

28、设A={?,{1},{1,2},{1,2,3}}，?是集合A上的包含关系。

（1）证明：是偏序集。

（2）在（1）的基础上证明是全序集

21

（3）指出该偏序集能构成布尔代数吗？为什么？

22

本文来源：https://www.bwwdw.com/article/nqlw.html