模拟试题(一)
一、 单项选择题
在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。
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．
A．负数 Ｂ．最小的正数 Ｃ．0 Ｄ．1 7．对任何a?A，形成的A上的等价关系R的等价类[a]R为（ ）。
A．空集 Ｂ．非空集 Ｃ．空集也可以为非空集 Ｄ．{x}x?A} 8．设S=Q?Q，其中Q为有理数集合，定义S上的二元运算“*”，?
A．可交换的 Ｂ．可结合的
Ｃ．既是可交换的，又是可结合的 Ｄ．不是可交换的，也不是可结合的
?1?09. 设有向图D=
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=
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={
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．
图 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，其中+和·是数的加法和乘法，则代数系统
图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．在偏序集
图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={
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={
19.设G是连通的 n阶m条边r个面的可平面图，则反映结点数、边数、面数之间关系的欧拉公式是___________________。
20.无向图G=
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={
-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={
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={
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是整数集合，“+”是一般加法，则下述函数中不是群
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={
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加法，群
三、计算题
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如下：<
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、给出偏序集
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，则 十、 解答题 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、设 四、证明题 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、群 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＝ 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加法，则 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. 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={ 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={ 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