离散数学全部试卷 下载本文

离散数学试题与答案试卷一

一、填空 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) = ; C.f : R?I , f (x) = [x] ; D.f :I?N, f (x) = | x | 。 (注:I—整数集,E—偶数集, N—自然数集,R—实数集) 8、图 中 从v1到v3长度为3 的通路有( )条。

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都是群到< G2, *>的同态映射,证明的一个子

群。其中C={x|x?G1且f(x)?g(x)} (8分)

3、G= (|V| = v,|E|=e ) 是每一个面至少由k(k?3)条边围成的连通平面

图,则

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、 设是一个群,这里+6是模6加法,Z6={[0 ],[1],[2],[3],[4],[5]},

试求出的所有子群及其相应左陪集。(7分)

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={<,>|x1+y2 = x2+y1} 。 1、 证明R是X上的等价关系。 (10分) 2、 求出X关于R的商集。(4分)

五、(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={,,,,,}; C. G=(V3,E3), 其中V3=V1,E3={ab,be,ed,cc};

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 },运算*如下表, *

证明是一个群(称作Klein四元群

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={,,,}为A上的关系,利用矩阵乘法求R的传递闭包,并画出t(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、 设是由元素a?G生成的循环群,且|G|=n,

则G = 。 6、 拉格朗日定理说明若是群的子群,则可建立G中的等价关系

R= 。

若|G|=n, |H|=m 则m和n关系为 。 7、 设f是由群到群的同态映射,e?是G?中的幺元,

则f的同态核Ker(f )= 。

α α β γ δ δ β β δ α α δ γ γ α β γ α δ δ γ α δ γ δ δ δ β γ δ n六、 选择 20% (每小题 2分)

1、设f是由群到群的同态映射,则ker (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 。

3、设 是一代数系统且是Abel群,如果还满足( )是域。

A、是独异点且·对+可分配;

B、是独异点,无零因子且·对+可分配; C、是Abel群且无零因子 ; D、是Abel且·对+可分配。

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、 设是一个代数系统,*是R上二元运算,?a,b?R是幺元且是独异点。(8分)

a*b?a?b?a?b,则0

n2、 设是n阶循环群,G=(a),设b=ak,k?I?则 元素b的阶为d,这里d=GCD ( n ,

k )。(10分)

3、 证明如果f是由的同态映射,g是由的同态映射,则g?f是由的同态映射。(6分)

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,+,·为普通加法和乘法,则是域。 4、( )一条回路和任何一棵生成树至少有一条公共边。

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={α,β,γ,δ}上的二元运算*为

* α β γ δ

那么,代数系统中的幺元是 , α的逆元是 。 3、 设I是整数集合,Z3是由模3的同余类组成的同余类集,在Z3上定义+3如下:

α δ α β α β α β γ δ γ β γ γ γ δ γ δ γ δ [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、 设是群的子群,则中幺元e是中幺元。( ) 3、 设A?{x|x?a?b3,a,b均为有理数}, +,·为普通加法和乘法,则代数系

是域。( )

4、 设G=是平面图,|V|=v, |E|=e,r为其面数,则v-e + r=2。( ) 5、 如果一个有向图D是欧拉图,则D是强连通图。( )

四、证明 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={,,,}写出它的关系矩阵和关系图,并用矩阵运算方法求出R的传递闭包。

四、10%

是一个群,证明:若对任意的a,b?G,都有a*b?(a*b),

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={,,,}写出它的关系矩阵和关系图,并用矩阵运算方法求出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={∣x?y(mod3) 则

[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)的主合取范式。