离散数学试题与答案试卷一
一、填空 20% (每小题2分)
1.设 A?{x|(x?N)且(x?5)},B?{x|x?E且x?7}(N:自然数集,E+ 正偶
数) 则 A?B? 。 2.A,B,C表示三个集合,文图中阴影部分的集合表达式为 。
3.设P,Q 的真值为0,R,S的真值为1,则
A B C ? ?(P?(Q?(R??P)))?(R??S)的真值= 。
4.公式(P?R)?(S?R)??P的主合取范式为 。
5.若解释I的论域D仅包含一个元素,则 ?xP(x)??xP(x) 在I下真值为 。
6.设A={1,2,3,4},A上关系图为
则 R2 = 。
7.设A={a,b,c,d},其上偏序关系R的哈斯图为
则 R= 。
8.图的补图为 。
9.设A={a,b,c,d} ,A上二元运算如下:
* a b c d a b c d a b c d b c d a c d a b d a b c 那么代数系统的幺元是 ,有逆元的元素为 ,它们的逆元分别为 。
10.下图所示的偏序集中,是格的为 。
二、选择 20% (每小题 2分)
1、下列是真命题的有( ) A. {a}?{{a}};
B.{{?}}?{?,{?}};
C. ??{{?},?}; D. {?}?{{?}}。 2、下列集合中相等的有( )
A.{4,3}??;B.{?,3,4};C.{4,?,3,3};D. {3,4}。 3、设A={1,2,3},则A上的二元关系有( )个。 A. 23 ; B. 32 ; C. 23?32?2; D. 3。
4、设R,S是集合A上的关系,则下列说法正确的是( ) A.若R,S 是自反的, 则R?S是自反的; B.若R,S 是反自反的, 则R?S是反自反的; C.若R,S 是对称的, 则R?S是对称的; D.若R,S 是传递的, 则R?S是传递的。
5、设A={1,2,3,4},P(A)(A的幂集)上规定二元系如下
R?{?s,t?|s,t?p(A)?(|s|?|t|}则P(A)/ R=( )
A.A ;B.P(A) ;C.{{{1}},{{1,2}},{{1,2,3}},{{1,2,3,4}}}; D.{{?},{2},{2,3},{{2,3,4}},{A}}
6、设A={?,{1},{1,3},{1,2,3}}则A上包含关系“?”的哈斯图为( )
7、下列函数是双射的为( )
A.f : I?E , f (x) = 2x ; B.f : N?N?N, f (n) =
A. 0; B. 1;
C. 2;
D. 3。
9、下图中既不是Eular图,也不是Hamilton图的图是( )
10、在一棵树中有7片树叶,3个3度结点,其余都是4度结点则该树有( 度结点。
A.1; B.2; C.3; D.4 。
三、证明 26%
1、R是集合X上的一个自反关系,求证:R是对称和传递的,当且仅当
< a, b> 和在R中有<.b , c>在R中。(8分)
4
)个2、f和g都是群
群。其中C={x|x?G1且f(x)?g(x)} (8分)
3、G=
图,则
e?k(v?2)k?2, 由此证明彼得森图(Peterson)图是非平面图。(11分)
四、逻辑推演 16%
用CP规则证明下题(每小题 8分) 1、A?B?C?D,D?E?F?A?F 2、?x(P(x)?Q(x))??xP(x)??xQ(x)
五、计算 18%
1、设集合A={a,b,c,d}上的关系R={ ,< b , a > ,< b, c > , < c , d >}用矩阵运算求出R的传递闭包t (R)。 (9分)
2、如下图所示的赋权图表示某七个城市v1,v2,?,v7及预先算出它们之间的一些直接通信线路造价,试给出一个设计方案,使得各城市之间能够通信而且总造价最小。 (9分)
试卷二
一、填空 20% (每小题2分)
1、 P:你努力,Q:你失败。“除非你努力,否则你将失败”的翻译为 ;
“虽然你努力了,但还是失败了”的翻译为 。 2、论域D={1,2},指定谓词P
P (1,1) T P (1,2) T P (2,1) F P (2,2) F 则公式?x?yP(y,x)真值为 。 2、 设S={a1 ,a2 ,?,a8},Bi是S的子集,则由B31所表达的子集是 。
},则R= 3、 设A={2,3,4,5,6}上的二元关系R?{?x,y?|x?y?x是质数 (列举法)。
R的关系矩阵MR=
。
5、设A={1,2,3},则A上既不是对称的又不是反对称的关系
R= ;A上既是对称的又是反对称的关系R= 。
6、设代数系统,其中A={a,b,c},
* a b c a b c a b c b b c c c b
则幺元是 ;是否有幂等 性 ;是否有对称性 。
7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。
9、n个结点的无向完全图Kn的边数为 ,欧拉图的充要条件是
。 10、公式(P?(?P?Q))?((?P?Q)??R的根树表示为
二、选择 20% (每小题2分)
1、在下述公式中是重言式为( )
A.(P?Q)?(P?Q);B.(P?Q)?((P?Q)?(Q?P)); C.?(P?Q)?Q; D.P?(P?Q)。
2、命题公式 (?P?Q)?(?Q?P) 中极小项的个数为( ),成真赋值的个数为( )。
A.0; B.1; C.2; D.3 。
S
3、设S?{?,{1},{1,2}},则 2 有( )个元素。
A.3; B.6; C.7; D.8 。 4、 设S?{ 1, 2, 3 },定义S?S上的等价关系
R?{??a,b?,?c,d? | ?a,b??S?S,?c,d??S?S,a?d?b?c}则由 R产 生
的S?S上一个划分共有( )个分块。
A.4; B.5; C.6; D.9 。 5、设S?{ 1, 2, 3 },S上关系R的关系图为
则R具有( )性质。
A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ?,? 为普通加法和乘法,则( )?S,?,??是域。 A.S?{x|x?a?b3,C.S?{x|x?2n?1,a,b?Q} B.S?{x|x?2n,a,b?Z}
n?Z} D.S?{x|x?Z?x?0}= N 。
7、下面偏序集( )能构成格。
8、在如下的有向图中,从V1到V4长度为3 的道路有( )条。
A.1; B.2; C.3; D.4 。 9、在如下各图中( )欧拉图。
10、
设R是实数集合,“?”为普通乘法,则代数系统
A.群; B.独异点; C.半群 。
三、证明 46%
1、 设R是A上一个二元关系,
S?{?a,b?|(a,b?A)?(对于某一个c?A,有?a,c??R且?c,b??R)}试证
明若R是A上一个等价关系,则S也是A上的一个等价关系。(9分)
2、 用逻辑推理证明:
所有的舞蹈者都很有风度,王华是个学生且是个舞蹈者。因此有些学生很有风度。(11分)
3、 若f:A?B是从A到B的函数,定义一个函数g:B?2对任意b?B有
Ag(b)?{x|(x?A)?(f(x)?b)},证明:若f是A到B的满射,则g是从B到 2
A的单射。(10分)
4、 若无向图G中只有两个奇数度结点,则这两个结点一定连通。(8分)
5、 设G是具有n个结点的无向简单图,其边数
Hamilton图(8分)
m?1(n?1)(n?2)?22,则G是
四、计算 14%
1、 设
试求出
2、 权数1,4,9,16,25,36,49,64,81,100构造一棵最优二叉树。(7分)
试卷三试题与答案
填空 20% (每空 2分)
1、 设 f,g是自然数集N上的函数?x?N,f(x)?x?1,g(x)?2x,
则f?g(x)? 。
2、 设A={a,b,c},A上二元关系R={< a, a > , < a, b >,< a, c >, < c, c>} ,
则s(R)= 。
3、 A={1,2,3,4,5,6},A上二元关系T?{?x,y?|x?y是素数},则用列举法 T= ; T的关系图为
; T具有 性质。 4、 集合A?{{?,2},{2}}的幂集
2A= 。
5、 P,Q真值为0 ;R,S真值为1。则wff(P?(R?S))?((P?Q)?(R?S))的真值
为 。
6、 wff?((P?Q)?R)?R的主合取范式为 。 7、 设 P(x):x是素数, E(x):x 是偶数,O(x):x是奇数 N (x,y):x可以整数y。
则谓词wff?x(P(x)??y(O(y)?N(y,x)))的自然语言是
。 8、 谓词wff?x?y(?z(P(x,z)?P(y,z))??uQ(x,y,u))的前束范式为
。
二、 选择 20% (每小题 2分)
1、 下述命题公式中,是重言式的为( )。
A、(p?q)?(p?q); B、(p?q)?((p?q))?(q?p)); C、?(p?q)?q; D、(p??p)?q。 2、 wff?(p?q)?r的主析取范式中含极小项的个数为( )。
A 、2; B、 3; C、5; D、0; E、 8 。 3、 给定推理
①?x(F(x)?G(x)) ②F(y)?G(y) ③?xF(x)
P US① P
④F(y) ⑤G(y) ⑥?xG(x)
ES③ T②④I UG⑤
??x(F(x)?G(x))??xG(x)
推理过程中错在( )。
A、①->②; B、②->③; C、③->④; D、④->⑤; E、⑤->⑥
4、 设S1={1,2,?,8,9},S2={2,4,6,8},S3={1,3,5,7,9},S4={3,4,5},
S5={3,5},在条件X?S1且X?S3下X与( )集合相等。 A、 X=S2或S5 ; B、X=S4或S5;
C、X=S1,S2或S4; D、X与S1,?,S5中任何集合都不等。
},5、 设R和S是P上的关系,P是所有人的集合,R?{?x,y?|x,y?P?x是y的父亲S?{?x,y?|x,y?P?x是y的母亲}则S?1?R表示关系 ( )。 }; A、{?x,y?|x,y?P?x是y的丈夫}; B、{?x,y?|x,y?P?x是y的孙子或孙女}。 C、 ?; D、{?x,y?|x,y?P?x是y的祖父或祖母6、 下面函数( )是单射而非满射。
A、f:R?R,B、f:Z?R,C、f:R?Z,D、f:R?R,?f(x)??x2?2x?1;
f(x)?lnx;
f(x)?[x],[x]表示不大于x的最大整数;
f(x)?2x?1。
其中R为实数集,Z为整数集,R+,Z+分别表示正实数与正整数集。 7、 设S={1,2,3},R为S上的关系,其关系图为
则R具有( )的性质。
A、 自反、对称、传递; B、什么性质也没有;
C、反自反、反对称、传递; D、自反、对称、反对称、传递。 8、 设S?{?,{1},{1,2}},则有( )?S。
A、{{1,2}} ;B、{1,2 } ; C、{1} ; D、{2} 。 9、 设A={1 ,2 ,3 },则A上有( )个二元关系。
A、2 ; B、3 ; C、2; D、2。
3
2
233210、全体小项合取式为( )。
A、可满足式; B、矛盾式; C、永真式; D、A,B,C 都有可能。
三、 用CP规则证明 16% (每小题 8分)
1、A?B?C?D,D?E?F?A?F
2、?x(P(x)?Q(x))??xP(x)??xQ(x)
四、(14%)
集合X={<1,2>, <3,4>, <5,6>,? },R={<
五、(10%)
设集合A={ a ,b , c , d }上关系R={< a, b > , < b , a > , < b , c > , < c , d >} 要求 1、写出R的关系矩阵和关系图。(4分) 2、用矩阵运算求出R的传递闭包。(6分)
六、(20%)
1、(10分)设f和g是函数,证明f?g也是函数。 2、(10分)设函数g:S?T数。
f:T?S,证明 f:T?S有一左逆函数当且仅当f是入射函
试卷四试题与答案
1填空 10% (每小题 2分)
1、 若P,Q,为二命题,P?Q真值为0 当且仅当 。 2、 命题“对于任意给定的正实数,都存在比它大的实数”令F(x):x为实数,
L(x,y):x?y则命题的逻辑谓词公式
为 。 3、 谓
词
合
式
公
式
?xP(x)??xQ(x)的前束范式
为 。
4、 将量词辖域中出现的 和指导变元交换为另一变元符号,公式其余
的部分不变,这种方法称为换名规则。
5、 设x是谓词合式公式A的一个客体变元,A的论域为D,A(x)关于y是自由的,则
被称为存在量词消去规则,记为
ES。
2选择 25% (每小题 2.5分)
6、 下列语句是命题的有( )。
A、 明年中秋节的晚上是晴天; B、x?y?0; C、xy?0当且仅当x和y都大于0; D、我正在说谎。
7、 下列各命题中真值为真的命题有( )。
A、 2+2=4当且仅当3是奇数;B、2+2=4当且仅当3不是奇数; C、2+2≠4当且仅当3是奇数; D、2+2≠4当且仅当3不是奇数;
8、 下列符号串是合式公式的有( )
A、P?Q;B、P?P?Q;C、(?P?Q)?(P??Q);D、?(P?Q)。 9、 下列等价式成立的有( )。
A、P?Q??Q??P;B、P?(P?R)?R;
C、 P?(P?Q)?Q; D、P?(Q?R)?(P?Q)?R。 10、 若A1,A2?An和B为wff,且A1?A2???An?B则( )。 A、称A1?A2???An为B的前件; B、称B为A1,A2?An的有效结论 C、当且仅当
A1?A2???An?B?F;D、当且仅当
A1?A2???An??B?F。
11、 A,B为二合式公式,且A?B,则( )。
A、A?B为重言式; B、A*?B*;
**C、A?B; D、A?B; E、A?B为重言式。
12、 “人总是要死的”谓词公式表示为( )。 (论域为全总个体域)M(x):x是人;Mortal(x):x是要死的。 A、M(x)?Mortal(x); B、M(x)?Mortal(x) C、?x(M(x)?Mortal(x));D、?x(M(x)?Mortal(x))
13、 公式A??x(P(x)?Q(x))的解释I为:个体域D={2},P(x):x>3, Q(x):x=4则A
的真值为( )。
A、1; B、0; C、可满足式; D、无法判定。 14、 下列等价关系正确的是( )。 A、?x(P(x)?Q(x))??xP(x)??xQ(x); B、?x(P(x)?Q(x))??xP(x)??xQ(x); C、?x(P(x)?Q)??xP(x)?Q; D、?x(P(x)?Q)??xP(x)?Q。 15、 下列推理步骤错在( )。 ①?x(F(x)?G(x)) ②F(y)?G(y) ③?xF(x) ④F(y) ⑤G(y) ⑥?xG(x)
P US① P ES③ T②④I EG⑤
A、②;B、④;C、⑤;D、⑥
3逻辑判断30%
16、 用等值演算法和真值表法判断公式A?((P?Q)?(Q?P))?(P?Q)的类
型。(10分)
17、 下列问题,若成立请证明,若不成立请举出反例:(10分)
(1) 已知A?C?B?C,问A?B成立吗? (2) 已知?A??B,问A?B成立吗?
18、 如果厂方拒绝增加工资,那么罢工就不会停止,除非罢工超过一年并且工厂撤换了
厂长。问:若厂方拒绝增加工资,面罢工刚开始,罢工是否能够停止。(10分)
四、计算10%
1、 设命题A1,A2的真值为1,A3,A4真值为0,求命题
(A1?(A2?(A3??A1)))?(A2??A4)的真值。(5分)
2、 利用主析取范式,求公式?(P?Q)?Q?R的类型。(5分)
五、谓词逻辑推理 15%
符号化语句:“有些人喜欢所有的花,但是人们不喜欢杂草,那么花不是杂草”。并推证其结论。
六、证明:(10%)
设论域D={a , b , c},求证:?xA(x)??xB(x)??x(A(x)?B(x))。
试卷五试题与答案
一、填空15%(每空3分)
1、设G为9阶无向图,每个结点度数不是5就是6,则G中至少有 个5度结点。 2、n阶完全图,Kn的点数X (Kn) = 。
3、有向图 中从v1到v2长度为2的通路有 条。
4、设[R,+,·]是代数系统,如果①[R,+]是交换群 ②[R,·]是半群
③ 则称[R,+,·]为环。 5、设[L,?,?]是代数系统,则[L,?,?]满足幂等律,即对?a?L有 。
二、选择15%(每小题3分)
1、 下面四组数能构成无向简单图的度数列的有( )。 A、(2,2,2,2,2); B、(1,1,2,2,3); C、(1,1,2,2,2); D、(0,1,3,3,3)。 2、 下图中是哈密顿图的为( )。
3、 如果一个有向图D是强连通图,则D是欧拉图,这个命题的真值为( )
A、真; B、假。
4、 下列偏序集( )能构成格。
5、 设
s?{1,111,2,,3,,4}234,*为普通乘法,则[S,*]是()。
A、代数系统; B、半群; C、群; D、都不是。
三、证明 48%
1、(10%)在至少有2个人的人群中,至少有2 个人,他们有相同的朋友数。
2、(8%)若图G中恰有两个奇数度顶点,则这两个顶点是连通的。
3、(8%)证明在6个结点12条边的连通平面简单图中, 每个面的面数都是3。 4、(10%)证明循环群的同态像必是循环群。 5、(12%)设[B,?,?,?,0,1]是布尔代数,定义运算*为a*b?(a?b)?(a?b),
求证[B,*]是阿贝尔群。
四、计算22%
1、在二叉树中
1) 求带权为2,3,5,7,8的最优二叉树T。(5分) 2) 求T对应的二元前缀码。(5分)
2、 下图所示带权图中最优投递路线并求出投递路线长度(邮局在D点)。
试卷六试题与答案
一 填空 15% (每小题 3分)
1、 n阶完全图结点v的度数d(v) = 。
2、 设n阶图G中有m条边,每个结点的度数不是k的是k+1,若G中有Nk个k度顶
点,Nk+1个k+1度顶点,则N k = 。 3、 算式 ((a?(b*c)*d)?(e*f)的二叉树表示为
。 4、 如图
给出格L,则e的补元是 。
5、 一组学生,用二二扳腕子比赛法来测定臂力的大小,是 。
二、选择 15% (每小题 3分)
1、设S={0,1,2,3},≤为小于等于关系,则{S,≤}是( )。
A、群;B、环;C、域;D、格。 2、设[{a , b , c},*]为代数系统,*运算如下:
* a b c a a b c b b a c c c c c 则零元为( )。
A、a; B、b; C、c; D、没有。
3、如右图 相对于完全图K5的补图为( )。
则幺元
4、一棵无向树T有7片树叶,3个3度顶点,其余顶点均为4度。则T有( )
4度结点。
A、1; B、2; C、3; D、4。
5、设[A,+,·]是代数系统,其中+,·为普通加法和乘法,则A=( )时,[A,
+,·]是整环。
A、{x|x?2n,n?Z}; B、{x|x?2n?1,n?Z};
4C、{x|x?0,且x?Z}; D、{x|x?a?b5,a,b?R}。
三、证明 50%
n2m?4。1、设G是(n,m)简单二部图,则(10分) 2、设G为具有n个结点的简单图,且
m?1(n?1)(n?2)2,则G是连通图。(10分)
3、记“开”为1,“关”为0,反映电路规律的代数系统[{0,1},+,·]的加法运算和乘法运算。如下:
+ 0 1 0 0 1 1 1 0
· 0 0 1 0 0 1 0 1 证明它是一个环,并且是一个域。(14分) 4、 [L,?,?]是一代数格,“≤”为自然偏序,则[L,≤]是偏序格。(16分)
四、10%
设E(x1,x2,x3)?(x1?x2)?(x2?x3)?(x2?x3)是布尔代数[{0,1},?,?,?]上的一个布尔表达式,试写出E(x1,x2,x3)的析取范式和合取范式(10分)
五、10%
如下图所示的赋权图表示某七个城市v1,v2,?,v7及预先算出它们之间的一些直接通信成路造价(单位:万元),试给出一个设计方案,使得各城市之间既能够通信又使总造价最小。
试卷七试题与答案
一、填空 15% (每小题 3分)
1. 任何(n,m) 图G = (V,E) , 边与顶点数的关系是 。 2. 当n为 时,非平凡无向完全图Kn是欧拉图。 3. 已知一棵无向树T有三个3顶点,一个2度顶点,其余的都是1度顶点,
则T中有 个1度顶点。
4. n阶完全图Kn的点色数X(KN)= 。
5. 一组学生,用两两扳腕子比赛来测定臂力大小,则幺元
是 。
二、 选择 15% (每小题 3分)
1、下面四组数能构成无向图的度数列的有( )。 A、 2,3,4,5,6,7; B、 1,2,2,3,4; C、 2,1,1,1,2; D、 3,3,5,6,0。
2、图 的邻接矩阵为( )。
?1??0?1??A、?1
01100000
0??1??1??1?11????0?;B、??1111111111??0??1??0
?11????1?;C、??1
1
0100100
0??0??1??0
?11????0?;D、??1
1
1100000
0??1?1??0??。
3、下列几个图是简单图的有( )。
A. G1=(V1,E1), 其中 V1={a,b,c,d,e},E1={ab,be,eb,ae,de};
B. G2=(V2,E2)其中V2=V1,E2={,,
D. G=(V4,E4),其中V4=V1,E4={(a,a),(a,b),(b,c),(e,c),(e,d)}。
4、下列图中是欧拉图的有( )。
5、G?(2,?),其中S?{1,2,3},?为集合对称差运算,
则方程{1,2}?x?{1,3}的解为( )。
A、{2,3}; B、{1,2,3}; C、{1,3}; D、?。
S三、 证明 34%
1、 证明:在至少有2 个人的人群中,至少有2 个人,他的有相同的朋友数。(8分) 2、 若图G中恰有两个奇数顶点,则这两个顶点是连通的。(8分)
3、 证明:在6个结点12条边的连通平面简单图中,每个面的面度都是3。(8分) 4、 证明循环群的同态像必是循环群。(10分)
四、 中国邮递员问题13%
求带权图G中的最优投递路线。邮局在v1点。
根树的应用 13%
在通讯中,八进制数字出现的频率如下:
0:30%、1:20%、2:15% 、3:10%、4:10%、5:5%、6:5%、7:5%
求传输它们最佳前缀码(写出求解过程)。
10%
设B4={e , a , b , ab },运算*如下表, *
证明
e e a a b b ab ab ab b e a b ab a b ab e ab b e a a e 试卷八试题与答案
一、 填空 15% (每小题 3分)
1、 n阶完全图Kn的边数为 。
2、 右图
的邻接矩阵
A= 。
3、 图
的对偶图为:
4、 完全二叉树中,叶数为nt,则边数m= 。 5、 设< {a,b,c}, * >为代数系统,* 运算如下:
* a b c a a b c b b a c c c c c 则它的幺元为 ;零元为 ; a、b、c的逆元分别为 。
二、 选择 15% (每小题 3分)
1、 图 相对于完全图的补图为( )。 2、 对
图
G 则 k ( G ), ? (G),?(G)分别为
( )。
A、2、2、2; B、1、1、2; C、2、1、2; D、1、2、2 。
3、 一棵无向树T有8个顶点,4度、3度、2度的分枝点各1个,其余顶点均为树叶,
则T中有( )片树叶。
A、3; B、4; C、5; D、6
4、 设是代数系统,其中+,·为普通的加法和乘法,则A=( )时 +,·>是整环。 A、{x|x?2n,n?Z}; B、{x|x?2n?1,n?Z}; 4C、{x|x?0,且x?Z}; D、{x|x?a?b5,a,b?R}。 5、 设A={1,2,?,10 },则下面定义的运算*关于A封闭的有( )。 A、 x*y=max(x ,y); B、x*y=质数p的个数使得x?p?y; C、x*y=gcd(x , y); (gcd (x ,y)表示x和y的最大公约数); D、x*y=lcm(x ,y) (lcm(x ,y) 表示x和y的最小公倍数)。 三、 证明 45% n2m?4。1、设G是(n,m)简单二部图,则(8分) 2、设G为具有n个结点的简单图,且 m?1(n?1)(n?2)2则G是连通图。(8分) 3、设G是阶数不小于11的简单图,则G或G中至少有一个是非平图。(14分) 4、记“开”为1,“关”为0,反映电路规律的代数系统[{0,1},+,·]的加法运算和乘法运算。如下: + 0 1 证明它是一个环,并且是一个域。(15分) 0 0 1 1 1 0 · 0 0 1 0 0 1 0 1 四、 生成树及应用 10% 1、(10分)如下图所示的赋权图表示某七个城市 v1,v2,?,v7及预先测算出它们之间的一些直接通信线路 造价,试给出一个设计方案,使得各城市之间既能够通信而且总造价最小。 2、(10分)构造H、A、P、N、E、W、R、对应的前缀码, 并画出与该前缀码对应的二叉树,写出英文短语HAPPY NEW YEAR的编码信息。 五、 5% 对于实数集合R,在下表所列的二元远算是否具有左边一列中的性质,请在相应位上填写“Y” 或“N”。 可结合性 可交换性 存在幺元 存在零元 Max Min + 试卷九试题与答案 一、 填空 30% (每空 3分) 1、 选择合适的论域和谓词表达集合A=“直角坐标系中,单位元(不包括单位圆周) 的点集”则A= 。 2、 集合A={?,{?}}的幂集P(A) = 。 3、 设A={1,2,3,4},A上二元关系R={<1,2>,<2,1>,<2,3>,<3,4>}画出R 的关系图 。 4、 设A={<1,2>,<2 , 4 >,<3 , 3 >} , B={<1,3>,<2,4>,<4,2>}, 则A?B= 。 A?B= 。 5、 设|A|=3,则A上有 个二元关系。 6、 A={1,2,3}上关系R= 时,R既是对称的又是反对称的。 7、 偏序集?A,R??的哈斯图为 则 , R?= 。 8、 设|X|=n,|Y|=m则(1)从X到Y有 个不同的函数。 (2)当n , m满足 时,存在双射有 个不同的双射。 9、 2是有理数的真值为 。 10、 Q:我将去上海,R:我有时间,公式(Q?R)?(R?Q)的自然语言 为 。 11、 公 式 (Q?P)?(?P?Q)的主合取范式 是 。 12、 若S?{S1 ,S2 ,?, Sm}是集合 A 的一个分划,则它应满 足 。 二、 选择 20% (每小题 2分) 1、 设全集为I,下列相等的集合是( )。 }; B、B?{x|? y(y?I?x?2y)}; A、A?{x|x是偶数或奇数C、C?{x|? y(y?I?x?2y?1)}; D、D?{x|0,1,?1,2,?2,3,?3,4,?4,?}。 2、 设S={N,Q,R},下列命题正确的是( )。 A、2?N,N?S 则2?S; B、N?Q,Q?S 则N?S; C、N?Q,Q?R 则N?R; D、??N,??S 则??N?S。 S与?S?3、 设C={{a},{b},{a,b}},则分别为( )。 S?CS?CA、C和{a,b};B、{a,b}与?;C、{a,b}与{a,b};D、C与C 4、 下列语句不是命题的有( )。 A、 x=13; B、离散数学是计算机系的一门必修课; C、鸡有三只脚; D、太阳系以外的星球上有生物; E、你打算考硕士研究生吗? 5、 (P?Q)?R的合取范式为( )。 A、(P??Q)?R ;B、(P?R)?(?Q?R) ; C、 (P??Q?R)?(P??Q??R)?(P?Q?R)?(P??Q?R)?(?P?Q?R)?(?P??Q?R) D、(P?Q?R)?(P??Q?R)?(P??Q?R)?(?P??Q?R)。 6、 设|A|=n,则A上有()二元关系。 A、2n ; B、n2 ; C、2; D、nn ; E、2。 7、 设r为集合A上的相容关系,其简化关系图(如图), n2nn则 [I] r产生的最大相容类为( ); A、{x1,x2}; B、{x1,x2,x3}; C、{x4,x5}; D、{x2,x4,x5} [II] A的完全覆盖为( )。 A、{x1,x2,x3,x4,x5}; B、{{x1,x2},{x1,x2,x3},{x4,x5}}; C、{{x1,x2,x3},{x2,x4,x5}}; D、{{x1,x2},{x3},{x4,x5}}。 8、 集合A={1,2,3,4}上的偏序关系图为 则它的哈斯图为( )。 9、 下列关系中能构成函数的是( )。 A、{?x,y?|(x,y?N)?(x?y?10)};B、{?x,y?|(x,y?R)?(y?x)}; 2{?x,y?|(x,y?I)?(x?ymod3)}。{?x,y?|(x,y?R)?(y?x)};C、 D、 10、N是自然数集,定义f:N?N, f(x)?(x) mod3(即x除以3的余数), 则f是( )。 A、满射不是单射;B、单射不是满射;C、双射;D、不是单射也不是满射。 2三、 简答题 15% 1、(10分)设S={1 , 2 , 3 , 4, 6 , 8 , 12 , 24},“?”为S上整除关系,问:(1)偏序集?S ,??,?}的极小元、最小元、极大元、最大元是什么? 的Hass图如何?(2)偏序集{S 2、(5分)设解释R如下:DR是实数集,DR中特定元素a=0,DR中特定函数 f(x,y)?x?y,特定谓词 F(x,y):x?y,问公式 A??x?y?z(F(x,y)?F(f(x,z),f(y,z)))的涵义如何?真值如何? 四、 逻辑推理 10% 或者逻辑难学,或者有少数学生不喜欢它;如果数学容易学,那么逻辑并不难学。因此,如果许多学生喜欢逻辑,那么数学并不难学。 五、10% 设X={1,2,3,4,5},X上的关系R={<1,1> , < 1 , 2 > , <2 , 4 > , < 3 , 5 > , < 4 , 2 > },用Warshall方法,求R的传递闭包t (R)。 六、证明 15% 1、 每一有限全序集必是良序集。(7分) 2、 设g?f是复合函数,如果g?f满射,则g也是满射。(8分) 试卷十试题与答案 一、 填空 10% (每小题 2分) P?Q真值为1,1、 若P,Q为二命题,当且仅当 。 2、 对公式(?yP(x,y)??zQ(x,z))??xR(x,y)中自由变元进行代入的 公式为 。 3、 ?xF(x)??(?xG(x))的前束范式为 。 4、 设x是谓词合式公式A的一个客体变元,A的论域为D,A(x)关于y的自由的, 则 被称为全称量词消去规则,记为US。 5、 与非门的逻辑网络为 。 二、 选择 30% (每小题 3分) 1、 下列各符号串,不是合式公式的有( )。 A、(P?Q)??R; B、((P?Q)?(R?S); C、P?Q??R; D、(?(P?Q)?R)?S。 2、 下列语句是命题的有( )。 A、2是素数;B、x+5 > 6;C、地球外的星球上也有人;D、这朵花多好看呀!。 3、 下列公式是重言式的有( )。 A、?(P?Q);B、(P?Q)?Q;C、?(Q?P)?P;D、(P?Q)?P 4、 下列问题成立的有( )。 A、 若A?C?B?C,则A?B; B、若A?C?B?C,则A?B; C、若?A??B,则A?B; D、若A?B,则?A??B。 5、 命题逻辑演绎的CP规则为( )。 A、 在推演过程中可随便使用前提; B、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果; C、如果要演绎出的公式为B?C形式,那么将B作为前提,设法演绎出C; D、设?(A)是含公式A的命题公式,B?A,则可用B替换?(A)中的A。 6、 命题“有的人喜欢所有的花”的逻辑符号化为( )。 设D:全总个体域,F(x):x是花,M(x) :x是人,H(x,y):x喜欢y A、?x(M(x)??y(F(y)?H(x,y)));B、?x(M(x)??y(F(y)?H(x,y))); C、?x(M(x)??y(F(y)?H(x,y)));D、?x(M(x)??y(F(y)?H(x,y)))。 7、 公式?x?y(P(x,y)?Q(y,z))??xP(x,y)换名( )。 A、?x?u(P(x,u)?Q(u,z))??xP(x,y);B、?x?y(P(x,u)?Q(u,z))??xP(x,u); ?x?y(P(x,y)?Q(y,z))??xP(x,u);?u?y(P(u,y)?Q(y,z))??uP(u,y)。C、D、 8、 给定公式?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)=0;D、P(a)=1、P(b)=1 9、 下面蕴涵关系成立的是( )。 A、?xP(x)??xQ(x)??x(P(x)?Q(x)); B、?xP(x)??xQ(x)??x(P(x)?Q(x)); C、?xP(x)??xQ(x)??x(P(x)?Q(x)); D、?x?yA(x,y)??y?xA(x,y)。 10、下列推理步骤错在( )。 ①?y?yF(x,y) ②?yF(z,y) ③F(z,c) ④?xF(x,c) ⑤?y?xF(x,y) P US① ES② UG③ EG④ A、①→②;B、②→③;C、③→④;D、④→⑤。 三、 逻辑判断 28% 1、(8分)下列命题相容吗?A?B, ?(B?C), A 2、(10分)用范式方法判断公式 (P?Q)?(P?R),P?Q?R 是否等价。 3、(10分)下列前提下结论是否有效? 今天或者天晴或者下雨。如果天晴,我去看电影;若我去看电影,我就不看书。故我在看书时,说明今天下雨。 四、 计算 12% 1、(5分)给定3个命题:P:北京比天津人口多;Q:2大于1;R:15是素数。 求复合命题:(Q?R)?(P??R)的真值。 2、(7分)给定解释I:D={2,3},L(x,y)为L( 2 , 2 ) = L ( 3 , 3 ) = 1 , L ( 2 , 3 ) = L (3 , 2 )=0 , 求谓词合式公式?y?xL(x,y)的真值。 五、 逻辑推理20% 1、(10分)所有有理数是实数,某些有理数是整数,因此某些实数是整数。 2、(10分)符号化语句:“有些病人相信所有的医生,但是病人都不相信骗子,所以医生都不是骗子”。并推证其结论。 试卷十一试题与答案 一、 填空 20% (每小题 2分) 1、 称为命题。 2、命题P→Q的真值为0,当且仅当 。 3、一个命题含有4个原子命题,则对其所有可能赋值有 种。 4、所有小项的析取式为 。 5、令P(x):x是质数,E(x):x是偶数,Q(x):x是奇数,D(x,y):x除尽y. 则 ?x(E(x)??y(D(x,y)?E(y)))的汉语翻译为 。 6、设S={a,b, c} 则S6的集合表示为 。 7、P(P(?))= 。 8、A?B= 。 9、设R为集合A上的关系,则t(R)= 。 10 、 若 R 是 集 合 A 上 的 偏 序 关 系 , 则 R 满 足 。 二、 选择 20% (每小题 2分) 1、 下列命题正确的有( )。 A、 若g,f是满射,则g?f是满射; B、若g?f是满射,则g,f都是满射; C、若g?f是单射,则g,f都是单射;D、若g?f单射,则f是单射。 2、 设f,g是函数,当( )时,f=g 。 A、?x?domf 都有 f(x)?g(x); B、domg?domf 且 f?g; C、f与g的表达式相同; D、domg?domf,rangef?rangef。 3、 下列关系,( )能构成函数。 A、f?{?x1,x2?|x1,x2?N且x1?x2?10}; B、f?{?x1,x2?|x1,x2?R,x1?x2}; 2}; C、f?{?x1,x2?|x1,x2?N,x2为小于x1的素数的个数 D、 f?{?x,x?|x?R}。 4、 下列函数( )满射;( )单射;( )双射( ); 一般函数( )。 A、f:N?N,f(x)?x?2; B、f:N?N,f(x)?x(mod3)(x除以3的余数); 2f:N?{0,1},C、 ?1x?偶数集f(x)???0x?奇数集;D、f:R?R,f(x)?2x?5。 5、 集合A={1,2,3,4}上的偏序关系为,则它的Hass图为( )。 6、 设集合A={1,2,3,4,5}上偏序关系的Hass图为 则子集B={2,3,4}的最大元( );最小元( );极大元( );极小元( );上界( );上确界( );下界( );下确界( )。 A、 无,4,2、3,4,1,1,4,4; B、无,4、5,2、3,4、5,1,1,4,4; C、无,4,2、3,4、5,1,1,4,4; D、无,4,2、3,4,1,1,4,无。 7、 设R,S是集合A上的关系,则下列( )断言是正确的。 A、 R,S自反的,则R?S是自反的;B、若R,S对称的,则R?S是对称的; C、若R,S传递的,则R?S是传递的;D、若R,S反对称的,则R?S是反对称的 8、 设X为集合,|X|=n,在X上有( )种不同的关系。 A、n; B、2; C、2; D、2。 9、 下列推导错在( )。 ①?x?y(x?y) ②?y(z?y) P US① 2 n 2nn2③(z?Cz) ④?x(x?x) ES② UG③ A、②; B、③; C、④; D、无。 10、“没有不犯错误的人”的逻辑符号化为( )。 设H(x):x是人, P(x):x犯错误。 A、?x(H(x)?P(x)); B、?(?x(H(x)??P(x))); C、?(?x(H(x)??P(x))); D、?x(H(x)?P(x))。 三、 命题演绎28% 1、(10分)用反证法证明(P?Q)?(P?R)?(Q?S)?S?R。 2、(8分)用CP规则证明P?(Q?R),R?(Q?S)?P?(Q?S)。 3、(10分)演绎推理:所有的有理数都是实数,所有的无理数也是实数,虚数不是实数。 因此,虚数既不是有理数,也不是无理数。 四、 8% 将wff?x(?(?yP(x,y))?(?zQ(z)?R(x)))化为与其等价的前束范式。 五、8% A={a,b,c,d},R={,,, 六、证明16% 1、 (8分)设A={1,2,3,4},在 P(A)上规定二元关系如下: R?{?s,t?|s,t? P(A)?(|s|?|t|)} 证明R是P(A)上的等价关系并写出商集P(A)/R。 2、 (8分)设f是A到A的满射,且f?f?f,证明f=IA 。 试卷十二试题与答案 五、 填空 20% (每空 2分) 1、 设集合A={1,2,3,4,5,6,7,8,9,10},定义A上的二元关系“≤”为 x ≤ y = x|y , 则x?y= 。 2、 设A?{x|x?2,n?N},定义A上的二元运算为普通乘法、除法和加法,则代 数系统中运算*关于 运算具有封闭性。 3、 设集合S={α,β,γ,δ,δ},S上的运算*定义为 * α β γ δ δ 则代数系统 4、 在群坯、半群、独异点、群中 满足消去律。 5、 设 则G = 。 6、 拉格朗日定理说明若 R= 。 若|G|=n, |H|=m 则m和n关系为 。 7、 设f是由群 则f的同态核Ker(f )= 。 α α β γ δ δ β β δ α α δ γ γ α β γ α δ δ γ α δ γ δ δ δ β γ δ n六、 选择 20% (每小题 2分) 1、设f是由群 A、G?的子群; B、G的子群 ; C、包含G?; D、包含G。 2、设 是环,?a,b?A,a·b的关于“+”的逆元是( )。 A、(-a)·(-b); B、(-a)·b; C、a·(-b); D、a·b 。 B、 4、设是一代数系统,+、·为普通加法和乘法运算,当A为( ) 时,是域。 } ;{x|x?a?b35,a,b均为有理数};A、 {x|x?a?b5,a,b均为有理数B、 C、 {x|x?a,a,b?I?,且a?kb}b ; D、{x|x?0,x?I}。 5、设是一个格,由格诱导的代数系统为?A ,? ,??,则( )成立。 A、?A,?,??满足?对?的分配律;B、?a,b?A,a?b?a?b?b; C、 ?a,b,c?A,若a?b?a?c 则b?c ; D、?a,b?A,有a?(a?b)?b且 a?(a?b)?b。 6、设是偏序集,“?”定义为:?a,b?A,a?b?a|b,则当A=( ) 时,是格。 A、{1,2,3,4,6,12}; B、{1,2,3,4,6,8,12,14}; C、{1,2,3,?,12}; D、{1,2,3,4}。 7、设?A ,? ,??是由格诱导的代数系统,若对?a,b,c?A,当b?a时, 有( )是模格。 A、a?(b?c)?b?(a?c); B、c?(a?c)?a?(b?c); C、a?(b?c)?b?(a?c); D、c?(a?c)?b?(a?c)。 8、在( )中,补元是唯一的。 A、有界格; B、有补格; C、分配格; D、有补分配格。 9、在布尔代数?A ,? ,?,??中,b?c?0当且仅当( )。 A、b?c; B、c?b; C、b?c; D、c?b。 10、设?A ,? ,?,??是布尔代数,f是从An到A的函数,则( ) 。 A、 f是布尔代数; B、f能表示成析取范式,也能表示成合取范式; C、若A={0,1},则f一定能表示成析取范式,也能表示成合取范式; D、若f是布尔函数,它一定能表示成析(合)取范式。 三、8% 设A={1,2},A上所有函数的集合记为AA, ?是函数的复合运算,试给出AA上运算?的运算表,并指出AA中是否有幺元,哪些元素有逆元。 四、证明42% 1、 设 a*b?a?b?a?b,则0 n2、 设 k )。(10分) 3、 证明如果f是由到的同态映射,g是由到 4、 设是一个含幺环,且任意a?A都有a·a=a,若|A|≥3则不 可能是整环。(8分) 5、 K={ 1, 2 , 5 , 10 , 11 , 22 , 55 ,110 }是110的所有整因子的集合,证明:具有全上界110 和全下界1的代数系统< K , LCM , GCD , ˊ >是一个布尔代数。((10分) ?x?K,x??110x)。 五、布尔表达式 10% },?,?,设E(x1,x2,x3)?(x1?x2)?(x2?x3)?(x1?x3)是布尔代数?{0,1的一个布尔表达式,试写出其析取范式和合取范式。(10分) ?上 试卷十三试题与答案 七、 填空 10% (每小题 2分) 1、Z?{x|x?Z?x?0},*表示求两数的最小公倍数的运算(Z表示整数集合),对于* 运算的幺元是 ,零元是 。 2、代数系统中,|A|>1,如果e和?分别为的幺元和零元, 则e和?的关系为 。 3、设 ?4、图的完全关联矩阵为 。 5、一个图是平面图的充要条件是 。 八、 选择 10% (每小题 2分) 1、 下面各集合都是N的子集,( )集合在普通加法运算下是封 闭的。 A、{x | x 的幂可以被16整除}; B、{x | x 与5互质}; C、{x | x是30的因子}; D、{x | x是30的倍数}。 2、 设G1??{0,1,2},??,G2??{0,1},*?,其中?表示模3加法,*表示模2乘法, 则积代数G1?G2的幺元是( )。 A、<0,0>; B、<0,1>; C、<1,0>; D、<1,1> 。 3、 设集合S={1,2,3,6},“≤”为整除关系,则代数系统< S , ≤ >是( )。 A、域; B、格,但不是布尔代数; C、布尔代数; D、不是代数系统。 4、 设n阶图G有m条边,每个结点度数不是k就是k+1,若G中有Nk个k度结点, 则Nk=( )。 A、n·k; B、n(k+1); C、n(k+1)-m; D、n(k+1)-2m 。 5、 一棵树有7片树叶,3个3度结点,其余全是4度结点, 则该树有( )个4度结点。 A、1; B、2; C、3; D、4 。 三、判断10% (每小题 2分) 1、( )设S={1,2},则S在普通加法和乘法运算下都不封闭。 2、( )在布尔格中,对A中任意原子a,和另一非零元b,在a?b或a?b中 有且仅有一个成立。 3、( )设S?{x|x?Z?x?0}?N,+,·为普通加法和乘法,则 5、( )没T是一棵m叉树,它有t片树叶,i个分枝点,则(m-1)i = t-1。 四、证明 38% 1、(8分)对代数系统,*是A上二元运算,e为A中幺元,如果*是可结合的且每个元素都有右逆元,则(1)中的每个元素在右逆元必定也是左逆元。 (2)每个元素的逆元是唯一的。 2、(12分)设?A ,? ,?,??是一个布尔代数,如果在A上定义二元运算☆,为 a☆b?(a?b)?(a?b),则是一阿贝尔群。 3、(10分)证明任一环的同态象也是一环。 4、(8分)若 G??V,E?e?(V?v,E?e)是每一个面至少由k(k≥3)条边围成的连通 平面图,则 k(v?2)k?2。 五、应用 32% 1、 (8分)某年级共有9门选修课程,期 末考试前必须提前将这9门课程考完,每人每天只在下午考一门课,若以课程表示结点,有一人同时选两门课程,则这两点间有边(其图如右),问至少需几天? 2、 用washall方法求图的可达矩阵,并判断图的连通性。(8分) 3、 设有a、b、c、d、e、f、g七个人,他们分别会讲的语言如下:a:英,b:汉、英,c: 英、西班牙、俄,d:日、汉,e:德、西班牙,f:法、日、俄,g:法、德,能否将这七个人的座位安排在圆桌旁,使得每个人均能与他旁边的人交谈?(8分) 4、 用 Huffman算法求出带权为2,3,5,7,8,9的最优二叉树T,并求W(T)。 若传递a ,b, c, d ,e,输它的最佳前缀码。(8分)f 的频率分别为2%,3% ,5 %,7% ,8% ,9%求传 试卷十四试题与答案 一、 填空 10% (每小题 2分) 1、 设?A,?,?,??是由有限布尔格?A,??诱导的代数系统,S是布尔格 ?A,??,中所有原子的集合,则 ?A,?,?,??~ 。 2、 集合S={α,β,γ,δ}上的二元运算*为 * α β γ δ 那么,代数系统 α δ α β α β α β γ δ γ β γ γ γ δ γ δ γ δ [i]?3[j]?[(i?j)mod3],则+3的运算表为 ; 4、 设G是n阶完全图,则G的边数m= 。 5、 如果有一台计算机,它有一条加法指令,可计算四数的和。现有28个数需要计算 和,它至少要执行 次这个加法指令。 二、 选择 20% (每小题 2分) 1、 在有理数集Q上定义的二元运算*,?x,y?Q有x*y?x?y?xy, 则Q中满足( )。 A、 所有元素都有逆元; B、只有唯一逆元; C、?x?Q,x?1时有逆元x; D、所有元素都无逆元。 ?1 2、 设S={0,1},*为普通乘法,则< S , * >是( )。 B、 半群,但不是独异点; B、只是独异点,但不是群; C、群; D、环,但不是群。 3、图 给出一个格L,则L是( )。 A、分配格; B、有补格; C、布尔格; D、 A,B,C都不对。 3、 有向图D= ,则v1到v4长度为2的通路有( )条。 A、0; B、1; C、2; D、3 。 4、 在Peterson图中,至少填加( )条边才能构成Euler图。 A、1; B、2; C、4; D、5 。 三、 判断 10% (每小题 2分) 1、 在代数系统中如果元素a?A的左逆元ae存在, ?1?1a?ae则它一定唯一且。( ) ?12、 设 4、 设G= 四、证明 46% ??A,使得x?*x?e, 1、 设,是半群,e是左幺元且?x?A,?x则是群。(10分) 2、 循环群的任何非平凡子群也是循环群。(10分) 3、 设aH和bH是子群H在群G中的两个左陪集,证明:要末aH?bH??,要末 aH?bH。(8分) 4、 设,是一个含幺环,|A|>3,且对任意?a?A,都有a?a?a,则 不可能是整环(这时称是布尔环)。(8分) 5、 若图G不连通,则G的补图G是连通的。(10分) 五、布尔表达式 8% 设 E(x1,x2,x3)?(x1?x2)?(x2?x3)?(x2?x3)是布尔代数 ?{0,1},?,?,?上的一个布尔表达式,试写出其的析取范式和合取范式。 六、图的应用 16% 1、 构造一个结点v与边数e奇偶性相反的欧拉图。(6分) 2、 假设英文字母,a,e,h,n,p,r,w,y出现的频率分别为12%,8%,15%,7%,6%, 10%,5%,10%,求传输它们的最佳前缀码,并给出happy new year的编码信息。(10分) 试卷十五试题与答案 一、 填空 20% (每空 2分) 1、 如果有限集合A有n个元素,则|2A|= 。 2、 某集合有101个元素,则有 个子集的元素为奇数。 3、 设S={a1,a2,?,a8},Bi是S的子集,由B17表达的子集为 , 子集{a2,a6,a7}规定为 。 4、 由A1,A2,?,An,生成的最小集的形式为 ,它们的并为 集,它们的交为 集。 5、 某人有三个儿子,组成集合A={S1,S2,S3},在A上的兄弟关系 具有 性质。 6、每一个良序集必为全序集,而 全序集必为良序集。 7、若f:A?B是函数,则当f是A?B的 ,f:B?A是f的逆函数。 c二、 选择 15% (每小题 3分) 6、 集合B?{?,{?},{?,{?}}}的幂集为( )。 A、{{?},{{?},?},?}; {?,{?},{{?}},{{?,{?}}},{?,{?}},{?,{?,{?}}},{{?},{?,{?}}},B};B、 C、{?,{?},{{?}},{?,{?}},{?,{?}},{?,{?,{?}}},{{?},{?,{?}}},B}; {?}}},{{?},{?,{?}}},?,B} D、{{?}{?,{?}},{?,{?,7、 下列结果正确的是( )。 A、(A?B)?A?B;B、(A?B)?A??;C、(A?B)?B?A; D、??{?}??;E、??{?}??;F、A⊕A=A 。 8、 集合A?B的最小集范式为( )(由A、B、C生成)。 (A?B?C)?(A?B?C)?(A?B?C)?A、(A?B?C)?(A?B?C)?(A?B?C)(A?B?C)?(A?B?C)?(A?B?C)? ; B、(A?B)?(A?B)?(A?B); C、(A?B?C)?(A?B?C)?(A?B?C) ; D、(A?B)?(A?B)?(A?B)。 9、 在( ) 下有A?B?A。 A、A?B;B、B?A;C、A?B;D、A??或B?? 10、 下列二元关系中是函数的有( )。 A、R?{?x,y?|x?N?y?N?x?y?10}; B、R?{?x,y?|x?R?y?R?y?x}; C、R?{?x,y?|x?R?y?R?x?y}。 22三、 15% 用Warshall算法,对集合A={1,2,3,4,5}上二元关系R={<1,1>,<1,2>,<2,4>,<3,5>,<4,2>}求t(R)。 四、15% ,a?0},C*上定义关系 集合C?{a?bi|i??1,a,b是任意实数R?{?a?bi,c?di?|ac?0},则R是C*上的一个等价关系,并给出R等价类的几何 说明。 *2五、计算 15% 1、 设A={1,2,3,4},S={{1},{2,3},{4}},为A的一个分划,求由S导出的等价关 系。 (4分) 2、 设Z为整数集,关系R?{?a,b?|a,b?Z?a?b(modk)}为Z上等价关系,求R的 模K等价关系的商集Z/R,并指出R有秩。(5分) 3、 设A={1,2,3,4,5},A上的偏序关系为 求A的子集{3,4,5}和{1,2,3},的上界,下界,上确界 和下确界。(6分) 六、证明 20% 1、 假定f:A?B,g:B?C,且g?f是一个满射,g是个入射,则f是满射。(10分) 2、 设f,g是A到B的函数,f?g且domg?domf,证明f?g。(10分) 试卷十六试题与答案 一、 判断正误 20% (每小题 2分) 1、设A,B, C是任意三个集合。 (1)若A?B且B?C,则A?C。 ( ) (2)若A?B且B?C,则A?C。 ( ) (3)若A?B且B?C,则A?C。 ( ) (4)A?(B?C)?(A?B)?(A?C)。 ( ) (5)(A?B)?C=(A?C) ? (B?C)。 ( ) 2、可能有某种关系,既是对称的,又是反对称的。( ) 3、若平面图共有v个结点,e条边和r个面,则v-e+r=2。( ) 4、任何有向图中各结点入度之和等于边数。( ) 5、代数系统中一个元素若有左逆元,则该元素一定也有右逆元。( ) 6、任何一个循环群必定是阿贝尔群。( ) 二、 8% 将谓词公式((?x)P(x)?(?y)Q(y))?(?y)R(y)化为前束析取范式与前束合取范式。 三、 8% 设集合A={a,b,c,d,e}上的关系R={,,, 四、10% 设 333a4*b4?(a*b)4,a5*b5?(a*b)5, 则 五、8% 根据库拉托夫斯基定理,证明下图为非平面图,要求用两种证法。 法(1)是找出与K3,3在2度结点内同构的子图。 法(2)是找出与K5在2度结点内同构的子图。 六、10% 证明:每个结点的度数至少为2的图必包含一个回路。 七、12% 用CP规则证明: 1、(S?Q)?R,?R?P,?P?S??Q 2、(?x)(P(x)?Q(x))?(?x)P(x)?(?x)Q(x) 八、12% 用推理规则证明下式: 前提: (?x)P(x)??x((P(x)?Q(x))?R(x)),(?x)P(x),(?x)Q(x) 结论:(?x)(?y)(P(x)?R(y)) 九、12% 若集合X={(0,2),(1,2),(2,4),(3,4),(5,6),??} R?{??x1,y1?,?x2,y2??|x1?y2?x2?y1} 1、 证明R是X上的等价关系。 2、 求出X关于R的商集。 试卷十七试题与答案 一、 判断正误 20% (每小题 2分) 1、设A.B. C是任意三个集合。 (1)若A?B且B?C,则A?C。 ( ) (2)若A?B且B?C,则A?C。 ( ) (3)若A?B且B?C,则A?C。 ( ) (4)A?(B?C)?(A?B)?(A?C)。 ( ) (5)(A–B)?C=(A?C)-(B?C)。 ( ) 2、可能有某种关系,既不是自反的,也不是反自反的。( ) 3、若两图结点数相同,边数相等,度数相同的结点数目相等,则两图是同构的。( ) 4、一个图是平面图,当且仅当它包含与K3,3或K5在2度结点内同构的子图。( ) 5、代数系统中一个元素的左逆元并一定等于该元素的右逆元。( ) 6、群是每个元素都有逆元的半群。( ) 二、 8% 将谓词公式(?x)(P(x)?Q(x,y))?((?y)P(y)?(?z)Q(y,z))化为前束析取范式与前束合取范式。 三、 8% 设集合A={a,b,c,d}上的关系R={,,, 四、9% 1、画一个有一条欧拉回路和一条汉密尔顿回路的图。 2、画一个有一条欧拉回路,但没有一条汉密尔顿回路的图。 3、画一个有一条欧拉回路,但有一条汉密尔顿回路的图。 五、10% 证明:若图G是不连通的,则G的补图G是连通的。 六、10% 证明:循环群的任何子群必定也是循环群。 七、12% 用CP规则证明: 1.A?B?C?D,D?E?F?A?F。 2.(?x)(P(x)?Q(x))?(?x)P(x)?((?x)Q(x)。 八、10% 用推理规则证明下式: 前提: ((?x)(F(x)?S(x))?(?y)(M(y)?W(y)),(?y)(M(y)??W(y)) 结论:(?x)(F(x)??S(x)) 九、13% 若集合X={(1,2),(3,4),(5,6),??} R?{??x1,y1?,?x2,y2??|x1?y2?x2?y1} 1、证明R是X上的等价关系。 2、求出X关于R的商集。 试卷十八试题与答案 一、 选择:(满分20分,每小题2分) 1.下列语句中不是命题的有( ) ⑴ 9+5?12 ; ⑵ x+3=5; ⑶我用的计算机CPU主频是1G吗?; ⑷ 我要努力学习。 2.命题“我不能一边听课,一边看小说”的符号化为( ) ⑴ P??Q ; ⑵ ?P?Q; ⑶ ?Q??P ; ⑷ ?(P?Q)。 3.下列表达式正确的有( ) ⑴ ?(P?Q)??Q; ⑵ P?Q?P ; ⑶ (P?Q)?(P??Q)?P; ⑷ P?(P?Q)?T。 4.n个命题变元可产生( )个互不等价的小项。 ⑴ n ; ⑵ n2 ; ⑶ 2n ; ⑷ 2n。 5.若公式(P?Q)?(?P?R)的主析取范式为 m001?m011?m110?m111则它的主合取范式为( ) ⑴ m001?m011?m110?m111 ; ⑵ M000?M010?M100?M101 ; ⑶M001?M011?M110?M111; ⑷ m000?m010?m100?m101 。 6.命题“尽管有人聪明,但未必一切人都聪明”的符号化 (P(x):x是聪明的,M(x):x是人) ( ) ⑴ ?x(M(x)?P(x))??(?x(M(x)?P(x))) ⑵ ?x(M(x)?P(x))??(?x(M(x)?P(x))) ⑶ ?x(M(x)?P(x))??(?x(M(x)?P(x))) ⑷?x(M(x)?P(x))??(?x(M(x)?P(x))) 7.设A={?} ,B=Р(Р(A)) 下列( )表达式成立。 ⑴ ??B ; ⑵ ????B; ⑶ ??????B;??????B。 ⑷ 8.A是素数集合,B是奇数集合,则A-B=( ) ⑴ 素数集合; ⑵ 奇数集合; ⑶ ?; ⑷ {2}。 9.集合A={2,3,6,12,24,36}上偏序关系R的Hass图为 则集合B={2,3,6,12}的上确界 。 B={2,3,6,12}的下界 。 B={6,12,24,36}的下确界 。 B={6,12,24,36}的上界 。 ⑴ 2; ⑵ 3; ⑶ 6; ⑷ 12; ⑸ 无。 10.若函数g和f的复合函数gf 是双射,则( )一定是正确的。 ⑴ g是入射; ⑵ f是入射; ⑶ g是满射; ⑷ f是满射。 二、 填空:(满分20,每小题2分) 1.设P:它占据空间,Q:它有质量,R:它不断运动, S:它叫做物质。命题“占据空间的,有质量的而且不断运动的叫做物质”的符号化为 。 2.设A,B是两命题公式,A?B当且仅当 。 3.要证R?C为前提H1,H2,?,Hm的有效结论,运用CP规则 是 。 4.对谓词公式??yP(x,y)??zQ(x,z)???xR(x,y)的自由变元代入 得 。 5.设S={a1,a2,…,a8},Bi是S的子集,则 B31= 。 6.设I为整数集合,R={ [1]= 。 7.偏序集〈Ρ({a,b}),?〉的Hass图为 。 8.对集合X和Y,设|X|=m ,|Y|=n ,则从X到Y的函数有 个。 9.设R为实数集,S={x|0 f(x)= 为双射。 10.设K[N]= 0 ,K[(0,1)]= ,则 K[N×(0,1)]= 。 三、 证明:(48分) 1.不构造真值表证明蕴涵式 (Q?(P??P))?(R?(R?(P??P)))?R?Q (7分) 2.用逻辑推演下式 (A?B)?C ,?D,?C?D? ?A??B (7分) 3.用CP规则证明 ?x(P(x)?Q(X))??xP(x)??xQ(x) (7分) 4.符号化并证明其结论:“所有有理数是实数,某些有理数是整数,因此某 些实数是整数”(设R(x):x是实数,Q(x):x是有理数,I(x):x是整数) (7分) 5.设R是集合X上的一个自反关系,求证:R是对称的和传递的当且仅当<a,b>和<a,c>在R中,则有<b,c>在R中 (8分)。 6.设f和g是函数,则f∩g也是函数。 (6分) 7.证明 [0,1]~(0,1) (6分) 四、(6分)集合S={1,2,3,4,5},找出S上的等价关系, 此关系能产生划分{{1,2},{3},{4,5}},并画出关系图。 五、(6分)求(Q?P)?(?P?Q)的主合取范式。 中幺元是 ,β左逆元是 , 无左逆元的元素是 。 是域。 4、( )一条回路和任何一棵生成树至少有一条公共边。 中的幺元是 , α的逆元是 。 3、 设I是整数集合,Z3是由模3的同余类组成的同余类集,在Z3上定义+3如下: 是群中幺元。( ) 3、 设A?{x|x?a?b3,a,b均为有理数}, +,·为普通加法和乘法,则代数系