离散数学习题集十五套

20%（每小题2分设A{x|(xN)且(x5)},B{x|xE且x7}（N：自然数集，E+正偶数）则AB 。设P，Q0，R，S1(P(Q(RP)))(RS)的真值 (PRSRP。若解释I的论域D仅包含一个元素，则xP(x) 。设A={1，2，3，4}，A则R2 设A={a，b，c，d}，其上偏序关系R则 设A={a，b，c，d}，A*abcdaabcdbbcdaccdabddabc 二、选择20%（每小题2分 A．{a} D．{}{{}} A．{4，3}；B．{，3，4}；C．{4，，3，3}；D．{3，4}。3、设A={1，2，3}，则A上的二元关系有（ A23 B32；C．233；D．3224、设R，S是集合A上的关系，则下列说法正确的是 若R，SRS若R，SRS若R，SRS若R，SRSA={1，2，3，4}，P（A（R{s,t|s,tp(A)(|s||t|}则P（A）/ A．A；B．P(A)6、设A={，{1}，{1，3}，{1，2，3}}则A上包含关系“”的哈斯图为 A．f:IE f(x)=2x；B．f:N f(n)=<n,n+1>C．f:RI f(x)[x]；D．f:IN,f |x|8、图中从v1到v3长度为3的通路有（ A0；B． C． D．39、下图中既不是Eular图，也不是Hamilton图的图是（B 必要条件，如果要判断是H图，一般用充分条件)107片树叶，334度结点则该树有（A）A．1B．2；C．3；D．4三、证明１、R是集合X上的一个自反关系，求证：Ra,b>和<ac>在R中有<.bc>在R（8分２、f和g都是群<G1,★>到<G2,*>的同态映射，证明<C,★>是<G1,★>的一个子群。其中C={x|xG1且f(x)g(x)} (8分) (|V|=v，|E|=e)是每一个面至少由k（k3）条边围成的连通平ek(v 四、逻辑推演CP规则证明下题（8分1ABCDDEFA2、x(P(x)Q(x))xP(x)五、计算1、设集合A={a，b，c，d}R={<abbab,cc,d>}用矩阵运算求出Rt(R)。（9分）2、如下图所示的赋权图表示某七个城市v1v2,v7及预先算出它们之间的一些直接通一、填 20%（每小题2分5、1；6、{<1,1<1,32,2>,2,4>；7、{<a.b>,<a,c>,<a,d>,<b,d>,<c,d>}IA；89、a；abc,d；adcd；10、二、选择20%（每小题2分123456789 CADCADBA三、证明“ a,b,c 若<a,b>,<a,c> 由 对称性b,ac,aR，由R传递性得<bc“”若<a,b>R，<a,c>R有<b,c> 任 a,bX，<a,a>R若<a,b>R <b,a>R所以R是对称的a,b>R<b,c>

则<b,a>Rb,c <a,c>2、 a,b f(a)g(a),f(b) f(b1)f1(b) g(b1)g1(b)f(b1)f1(b)g1(b)f(a★b1)a★b1

f(a)*f1(b)g(a)*g(b1)g(a★b1<C, G1,★>2ed(F) r①设G有r个面， ， k。而ver22vervek

ek(vk2（8分ek(v②彼得森图为k5,e15,v10，这 k 二、逻辑推演 ②A③ABC④C

⑤ ⑥D⑦DE

⑧ ⑨A①②③x(P(x)④P(c)⑤⑥⑦xP(x)

P三、计算

1 1

，

R00

00

0 0

0 0

M

0 0

0 0

M

t(

0101

t(R)={<a,a>,<a,b>,<a,c>,<a,d>,<b,a>,<b,b>,<b,c.><b,d>,<c,d>树权C(T)=23+1+4+9+3+17=57一、填空20%（2分。2、论域D={1，2}，指定谓词PPPPTTFF xyP(y,x)真值 2S={a1，a2，…，a8}，BiS的子集，则由B31。3A={23456}上的二元关系Rxy|xyx是质数，则R的关系矩阵

。5、设A={1，2，3}，则A上既不是对称的又不是反对称的关系 ；A上既是对称的又是称的关 *abcaabcbbbc*abcaabcbbbccccb则幺元是 ；是否有幂等 7、4阶群必 群 9、n个结点的无向完全图Kn的边数 。10 (P(PQ))((PQ)R的根树表示。二、选择20%（2分 A．(PQ)(PQ)；B．(PQ)((PQ)(QP))C(PQQ DP(PQ (PQ)(QP)中极小项的个数为 为 D．33、设S{,{1},{1,2}}，则2S有 D．84S1,23SSR{a,b,c,d|a,bSS,c,dSS,adbc}则由R产生的SS上一个划分共有（ D．95S1,2,3，S上关系R则R具有 B．反自反性、称性 D．自反性6、设,为普通加法和乘法，则 ）S,,是域 S{x|xab a,b B.S{x|x2n a,b Sx|x2n n D.Sx|xZx0N 8、在如下的有向图中，从V1到V4长度为3的道路有 D．4 10设R是实数集合“”为普通乘法，则代数系统<R，×>是 C．半群三、证明1R是ASa,b|a,bA对于某一个cA有acR且c,bR)}试证明若R是AS也是A上的一个等价关系。（9分）（11分3f:AB是从A到BgB2AbB有g(bx|xAf(xb)}f是ABgB2A的单射。（10分）5Gn四、计算

G试求出<Z6,+6>的所有子群及其相应左陪集。（7分）一、填空20%（2分1、PQ；PQ2、 3、B31 {a4,a5,a6,a7,a8}4

1 101 01 100003>,<5,4>,<5,5>,<5,6>}；

5、R={<1,2>,<1,3>,<2,1>} 6、a；否； 7、Klein四元群；循环群8、 91n(n 10二 选择20%（每小题2分123456789DBDABBB三 证明1（9分aA，由R自反，(aaRaaR，aaa,ba,bS(a,cR)(c,b(a,cR)(c,bb,aa,b,ca,bSb,c

SRR(a,dR)(d,bR)(b,eR)(e,c(a,bR)(b,ca,c2、11

RS证明：设P(x)：xQ(x)：xS(x)：xa：王华前提：x(P(x)Q(x))、S(a) 结论：x(S(x) ……3①S(a)②x(P(x)③P(a)④⑤⑥⑦S(a)⑧x(S(x)３、１0

b1b2Bb1b2f满射a1a2使f(a1)b1,f(a2)b2,且f(a1)f(a2),由于f是函数 a1又g(b1){x|(xA)(f(x)b1 g(b2){x|(xA)(f(x)b2a1g(b1a2g(b2 a1g(b2a2g(b1g(b1g(b2由b1,b24、8

g为单射Guvu，vG至少有两个连点，这与图论基本定理，因而u，v一定连通。5、8Gnu，v不相邻且d(ud(vn1,令V1uv}G-m'1(n1)(n2)2(n是具有n-2个结点的简单图，它的边 m'1(n2)(n3)

可得 ，因而所以G为Hamilton图.四 计算17Z6的左陪集：Z627一 填空20%（每空2分1、设f，g是自然数集N上的函数xN f(x)x1 g(x)2x则fg(x) 2、设A={a，b，c}，A上二元关系R={<a,a>,<a,b>,<a,c>,<c, 则 3A={1，2，3，4，5，6}，A上二元关系Txy|xy是素数，则用列举 ；T具 4、 A{{,2},{2 2A 5P，Q0；R，S1wff(PRS))((PQRS真值 6、wff((PQ)R) 7P（xxE(x)：x是偶数，O(x)：xNx,y)：x可以整数y则谓词 x(P(x)y(O(y)N(y,x)))的自然语言。。二 选择20%（每小题2分 A、pqpq；B、pqpqqpC、(pq)q D、(pp)q2、 (pq)r的主析取范式中含极小项的个数为 A、2；B、 E、8①x(F(x)②F(y)G(③④F(⑤G(⑥x(F(x)G(x))

PA、①->②;BCD、④->⑤;ES5={3，5}，在条件XS1且XS3下X与（ A、X=S2或S5 B、X=S4或C、X=S1，S2或S4；D、XS1，…，S55、设 和 是 上的关系， 是所有人的集合Rxy|xyPx是y的父亲Sxy|xyPx是y的母亲则S1R表示关系 A、{xy|xyPx是y的丈夫B、{xy|xyPx是y的孙子或孙女C、；D、{xy|xyPx是y的祖父或祖母} A、f:R f(x)x22xBfZR,C、f:RZ,D、f:RR,

f(x)lnxf(x)[x],[x]表示不大于x的最大整数f(x)2x1其中R为实数集，Z为整数集，R+，Z+7S={1，2，3}，R为S则R具有 8、设S{,{1},{1,2}}，则有 ）SA、{{1,2}}；B、{1,2}；C、{1}；D、{2}9、设A={1,2,3}，则A上有 ；B、 ；C、223；D、232 A、可满足式；B、式；C、永真式；D、A，B，C都有可能三 用CP规则证明16%（每小题8分1、ABCD,DE A2、x(P(x) xP(x)集合X={<1,23,45,6>,}，R={<<x1,y1>,<x2,y2>>|x1+y2x2+y1}1R是X（10分Aa,bcd上关系R=a,bbabccd1（10分）fgfg2（10分）gS

fTS，证明fTSf

五、填空20%（2分12(x+12{aaabacccbaca3{2,1,3,1,5,1,4,2,6,2,6,346、(PQR(PQR(PQR；7xx是素数则y，yyx；8、xyzu(P(xzPyzQ(xyu六、选择20%（每小题2分123456789CCCCABDADC七、证明16%(8分1 ②A③ABC④C

⑤ ⑥D ⑦DE ⑧ ⑨A 2xP(x)xQ(x)(x)P(x)本题可证x(P(xQ(x))(xP(x)① ②③④x(P(x)⑤P(a)⑥⑦⑧(xP(x)

1 自反性：x,yX 由于xyxxyxy 2 对称性：x1,y1X,x2,y2当x1y1x2y2R时即x1y2x2y1也即x2y1x1故x2,y2,x1,y1 3 传递性：x1,y1X,x2,y2 x3,y3当x1y1x2y2R且x2y2x3y3Rx1y2x2 xx2

x1y2x2y3x2y1x3即x1y3x3 故x1,y1,x3,y3 （1（2（3）2、X/R={[12]R 01 011

0 0 0

00

2

M3M2

0 10

R M5M3,M6 t(R)={<a,a>,<a,b>,<a,c>,<a,d>,<b,ab,b>,<b,c.>,<b,d>,<c,d>}。六、fg{x,y|xdomfxdomgyf(x)y1

{x,y|xdomfdomgy

f(x)令hfdomfgdomh{x|xdomfdomg,f(x)（2）h{x,y|xdomfdomgyh(x)f(x)对x 若有y1,y2使y1h(x)f(x)g(x) y2h(x)f(x)由于f(或g)是函数,有y1y2即xdomh有唯一y使得yfg也是函数""若f有一左逆g,则对t gf(t)gf是入射,f是入射""f是入射 f:TS定义如下sf(T),由f入射 |tT,使f(t)此时令g(s)t,若sf(T 令g(s)c则对sSg(s)tc且若f(t则gf(t)g(s) 故g是f的左逆 一、填空10%（每小题2分1、若P，Q，为二命题，PQ真值为0当且仅 2、命题“对于任意给定的正实数，都存在比它大的实数”令F(x)x为实数，L(x,y):x 3、 xP(x) 4、将量词辖域中出现的 和指导变元交换为另一变元符号其余二、选择25%（每小题2.5分 B、xy0C、xy0当且仅当x和y都大于0；D、我正在说谎。2、下列各命题中真值为真题有（ APQ；BPPQ；C、(PQPQ)；D、(PQ APQQP；BPPRRC、P(PQ)Q D、P(QR)(PQ)R5、若A1,A2An和B为wff，且A1A2AnB则 A、称A1A2An为B的前件 B、称B为A1,A2An的有效结C、当且仅 A1A2AnB ；D、当且仅A1A2AnBF ，且AB，则 AAB为重言式；BA*B* D、A*B* E、AB为重言式 A、M(x)Mortal(x) B、M(x)C、x(M(xMortal(x；D、x(M(x8 Ax(P(x)Q(x))的解释I为 域D={2}，P(x)：x>3,Q(x)：x=4则 A、1；B、0；C、可满足式；D、无法判定。9、下列等价关系正确的是（ A、x(P(xQ(x))xP(xxQ(xB、x(P(xQ(x))xP(xxQ(xC、x(P(x)Q)xP(x)Q；D、x(P(x)Q)xP(x)Q。10（①x(F(x)②F(y)G(③④F(⑤G(⑥

三、1、用等值演算法和真值表法判断 A((PQ)(QP))(PQ)的类（10分）长。问：若厂方增加工资，面刚开始，是否能够停止。（10分） 五、谓词逻辑推理十、填空10%（2分1、P1，Q0；2、x(F(xL(x,0y(FyLyx；3x(P(xQ(x；4、约束变元；5、xA(xAy，y为D十一 选择25%（每小题2.5分123456789CAB十二 逻辑判断A((PQ)(QP))(PQ)(PQ)(PQ)PQPQ(PQ)(QPA1111111100100101100010011111所以A若取C 则AT BTT有ACBC但A与B不一定等价，可为任意不等价的 充要条件ABT(AB)(BA)(AB)(BBAABABBAA所以ABT AB3、解：设P：厂方增加工资；Q：停止；R超壶过一年；R：撤换厂P(RSQ①P((RS)

P

② ③(RS)④⑥(RS⑦四、计算

(1(100)))(11)(1(10) 解：(10) 1

(PQ)QR(PQ)(Q(PQ)(QR)PQQR解：M(x):x是人 F(x):x是花 G(x):x是杂草 H(x,y):x喜欢x(M(x)y(F(y)H(x,x(F(x)

x(M(x)y(G(y)H(x,y)⑴x(M(x)y(F(y)H(x,⑵M(a)y(F(y)H(a,⑶M⑷y(F(y)H(a,⑸x(M(x)y(G(y)H(x,⑹M(a)y(G(y)H(a,⑺y(G(y)H(a,⑻y(H(a,y)G(⑼F(z)H(a,⑽H(a,z)⑾F(z)⑿x(F(x)

P十三 证明xA(x)xB(x)(A(a)A(b)A(c)(B(a)B(b)(A(a)B(a))(A(a)B(b))(A(a)(A(b)B(a))(A(b)B(b))(A(b)(A(c)B(a))(A(c)B(b))(A(c)(A(a)B(a))(A(b)B(b))(A(c)x(A(x)15%（3分1、设G为9阶无向图，每个结点度数不是5就是6，则G中至少有 个5度结2、n阶完全图，Kn的点数X(Kn) 中从v1到v2长度为2的通路 条[R，+·][R·] [R，+·] 15%（3分 （2，2，2，2，2； （1，1，2，2，3（1，1，2，2，2； （0，1，3，3，32、下图中是哈密顿图的为（ 3、如果一个有向图D是强连通图，则D是欧拉图，这个命题的真值为（ 5

s

1,2

1,3

1, 。错解ABC、群；D三、证明数都是3。5（12%）设[B,,01]是布尔代数，定义运算*为a*babab)，2，3，5，7，8的最优二叉树T（5分右侧的边取1，然后进行组合2（邮局在D点一、填空（15%）每空316；2、n；3、2；4、+对·分配且·对+分配均成立；5、aaaaaa二、选择（15%）312345BCD三、证明1（10分）nv1，…，vnnV={v1，…，vn}Euv|uvV,且uv是朋友（uv）}现证G（2）若G中有一个孤立点，则G中的至少有3个顶点，既不考虑孤立点。设G中每个结1G为简单图，所以每个顶点度数都小于等于n-1，由于Gn2（8分）证：设Gu，vu，v不连通则至少有两个连通分支理。因而u，v必连通。3（8分）证：n=6,m=12欧拉n-m+f=2知f=2-n+m=2-6-由图论基本定理知：deg(F2m24，而deg(Fi3，所以必有deg(Fi3，即每个面用3条边围成。[A·][f（A，*]anamAf(anam)f(an)*f(amn=1f(a)f f(a2f(aaf(a)*f(afn=k-1时f(ak1fn=kf(ak)f(ak1a)f(ak1)*f(a)f(a))k1*f(a)f这表明，f(A)中每一个元素均可表示为f(a))n，所以[f(A),*]f(a)（1）abB有a*bababbabab*(a*b)*c((ab)(ab))*c(((ab)(ab))c)((ab)(ab))(abcabc)((ab)(ab))abcabc(aaabbabb)abcabcbacababcabcabcaba*(b*c)a*((bc)(bc))(a(bc)(bc))((a(bc)(ba(bc)(bc)abcababcabcabcab(a*b)*ca*(b*a*0(a0)(a0)a0

0*a(0a)(0a)0aa是a的逆元

a*a(aa)(aa)00四、计算1（10分1（5（2（52（12分）图中奇数点为E、F，d(E)=3,d(F)=3,d(E,F)=28道路EG、GF，得图G‘，则G‘是欧拉图。由D开始找一条欧拉回路：DEGFGEBACBDCFD。一、填空15%（每小题3分1、n 阶完全图结点v 的度数d(v) 阶是什么意 2、设n阶图G中有m条边，每个结点的度数不是k的是k+1，若G中有Nk个k度顶点，Nk+1个k+1度顶点，则Nk= 3((ab*c*de*f。 5、一组学生，用二二扳腕子比赛法来测定臂力的大小，则幺元是 二、选择15%（每小题3分1、设S={0,1,2,3},≤为小于等于关系，则{S，≤}是 2、设[{abc}，*]为代数系统，**abcaabcbbaccccc 相对于完全图K5的补图为 [A，+·] [A，+·]A、{x|x2n,n B、{x|x2n1,nZ}C、{x|x0,且x D、{x|xab4 a,bR}三、证明m1、设G是（n,m）简单二部图， 4（10分

m1(n1)(n 节点一定有边相连)（10分）[{0，1，+·+01+01001110·01000101E(x1x2x3x1x2x2x3x2x3是布尔代数[{0,1上的一个布尔表达式，试写出E(x1,x2,x3)的析取范式和合取范式（10分）如下图所示的赋权图表示某七个城市v1v2,v7及预先算出它们之间的一些直接通信答案：错误思路：寻找欧拉回路以V1为起点，正确解：寻找最小生成树（因为城市之间能一、填空15%（3分1、n-1；2、n(k+1)-2m；3、如右图；4、0；5二、选择15%（每小题3分12345DCAAD三、证明） VXY,X ,Y ,n1n2） n

mnnn(nn)

nn(nn n

4n12时，完全二部图(nm的边数m有最大值n2n故对任意简单二部图(nm有m4G2n1n2，显然n1n2n1 n21n1n n2nmn1(n11)n2(n21)(n1)(n1n22)(n1)(n 与假设。所以G连通群：（0+0）+0=0+（0+0）=0（0+0）+1=0+（0+1）=1；（0+1）+0=0+（1+0）=1； ②0，1·0（0·0·1=0（0·1）=（0·1·0=0（1·0）=00·1·1=0（1·1）=0；（1··=（·）=0 x,y 0（+）=0=0+=(0·x)+(0·)；Ⅱ1（x+y）当 1(xy)10000(10)(10)(1x) 1 xy（xy1）1(xy)11110(11)(10)(1x)(1 0 所以xyz{0,1}zxyzxz所以·对+，1+·[{0，1}，+·][{0，1}，+·]“≤” ≤自然偏序a,b ab 若ab,b 即：ab bab aabba babbcac(ab)a(baa

ab即abbc即bcbab即ab（2）x,y xxyxxyxxyx同理可证:xy若{xyc，则cxycxycycx xy是{xyxyinf{x00000011010001111000101111011111

E(x1,x2,x3)(x1x2x3)(x1x2x3)(x1x2x3(x1x2x3)(x1x2x3E(x1x2x3x1x2x3x1x2x3x1x2x3五、w(v1,v7)1w(v7,v2)4w(v7,v3)9w(v3,v4)3w(v1,v6)

选e1v1v7选e2v7v3选ev3v4选ev4v5选e树权C(T)=23+1+4+9+3+17=57（万元）即为总造价一、15（3任何(n,m)图G=(V,E),边与顶点数的关系是 度数之和等于边数的二 当n 已知一棵无向树T321则T中 个1度顶点n阶完全图Kn的点色数 一组学生,用两两扳腕子比赛来测定臂力大小,则幺元是臂力最小 二 选择15%（每小题3分1、下面四组数能构成无向图的度数列的有(B A、2,3,4,5,6,7； B、1,2,2,3,4；C、 D、3,3,5,6,02、 1

11101101010110

111

A、 ；B、1111；C、 0；D、 03、下列几个图是简单图的有( )G1=(V1,E1G=(V3,E3),其中 )5、G(2S,)，其中S{1,2,3}，为集合对称差运算，则方程{1,2}x{1,3}的解为（ B、{1,2,3}；C、 D、三 证明四 中国邮递员问题五 根树的应用0：30%、1：20%、2：15、3：10%、4：10%、5：5%、6：5%、7：5%六 B4={eabab，运算*

*eabeeabaa*eabeeabaaebbbeabaed(v)1、 十五 选择15%（每小题3分12345BCBBA十六 证明Euv|uvV,且uv是朋友（uv）}G=（V，E）现验证G（2）GG3GG1，2，…，n-1n-1n-1n个顶点的2（8分）Gu，vu，v不连通，即它们中无G1、G2u，vG1G2G1与G2中各含有一个奇数度结点，与握手定理。因而u，v必连通。3（8分）证：n=6,m=12欧拉n-m+f=2知f=2-n+m=2-6-由图论基本定理知：deg(F2m24，而deg(Fi3，所以必有[A·]*>，于是anamAf(anam)f(an)*f(amn=1f(a) f(a2

ff(aa)f(a)*f(a)(fn=k-1时f(ak1fn=kf(ak)f(ak1a)f(ak1)*f(a)f(a))k1*f(a)f这表明，f(A)中每一个元素均可表示为f(a))n，所以<f(A),*>f(a)生成元的循十七 中国邮递员问题 d(v2) d(v3)3,d(v5)求v1v2v3v5d(v1v2)pvv

d(v2v3)p2v1v2v3

,d(v1v5)p3v1v7v5

d(v2v3)p4v2v3

d(v2v5)3p5v2v6v5

d(v3v5)p6v3v7 1和最短：p3v1v7v5, p4v2v3,在原图中出p3p4G‘G‘中每个结点度数均为偶数的图G‘存在欧拉回路Cv1v7v3v2v4v5v6v2v7v5v3v2v1v7v5v1，欧拉回路C权长为43。十八、根树的应用w15,w25,w35,w410,w510,w615,w720,w8000005；000016；00017；1003；1014；0012；11传送1；01传送0（频率越高传送的前缀码越短。

十九 群：即要证明(x*y*zx*y*z43=64 (a*a)*a=e*a=a=a*(a*a)=a*e=a； (b*b)*b=e*b=b=b*(b*b)=b*e=b；(b*a)*a=ab*a=b=b*(a*a)=b*e=b； (b*a)*b=ab*b=a=b*(a*b)=b*ab=a。e逆：e1=e；a1=a；b1=b(ab)1=ab。一、填空15%（每小题3分1、n阶完全图Kn的边数 22图的接矩阵。3、图 4、完全二叉树中，叶数为nt，则边数 5a,b,c*为代数系统，**a*abcaabcbbaccccc则它的幺元 a、b、c 的逆元分别为 a，b，c 的逆元不存 二、 择15%（每小题3分1、 2、对图 k(G),(G),(G)分别为 A、2、2、2；B、1、1、2；C、2、1、2；D、1、2、2则T中有（C）片树叶。 <A，+·> ）<A，+·>A、{x|x2n,n B、{x|x2n1,nC、{x|x0,且x D、{x|xab4 a,bR} A、x*y=max(x B、x*y=质数p的个数使得xpyC、x*y=(x,y)；((x,y)表示x和y的最大公约数 （lcm(x,y)表示x和y的最小公倍数三、证明m1、设G是（n,m）简单二部图， 4（8分2、设Gn

m1(n1)(n2)则G是连通图。（8分23、设G是阶数不小于11的简单图，则G或G中至少有一个是非平图（ 反正（14分）法[{0，1，+·+01+01001110·01000101四、生成树及应用1（10分）如下图所示的赋权图表示某七个城市v1v2,v7及预先测算出它们之间的一些直接通信线路2（10分）构造H、A、P、N、E、W、R、Y对应的前缀 五、R，在下表所列的二元远算是否具有左边一列中的性质，请在相应位上填写“Y”或“N+YYYYYYNNYNNN

二十 填空15%（每小题3分

1n(n1、

二十一、选择15%（每小题3分12345AACD二十二、证明1、（8分设G=（V，E，VXY,X ,Y ,则n1n2 n

mnnn(nn)

nn(nn n

4n12时，完全二部图(nm的边数m有最大值4故对任意简单二部图(nm有m4G1G2的顶点数分别为n1n2，显然n1n2n。n1 n21n1n n2nmn1(n11)n2(n21)(n1)(n1n22)(n1)(n 与假设。所以G连通

m'1110 条，因而必有或G28G的边数m28G有k个连通分支，则G中必有回路。（G为k棵树构成的森林，每棵树的顶点数为ni，边数mi，则 mn1,i nin11,mi ,i1 k28mmi(ni1)nk11 下面用反证法证明G

mg2

(nk

28m g

(11k1) 3

而28 ，所以G为非平面图（2）n>11时，考虑G11个顶点的子图G'，则G'或G'必为非平面图。如果G'为非平面图，则G为非平面图。'如果G为非平面图，则G4（15分群：（0+0）+0=0+（0+0）=0（0+0）+1=0+（0+1）=1； （0+1）+1=0+（1+1）=0； ②<{，1}>(·0)·0=00·0）=0（0·0·1=0（0·1）=1；（0··=（·）=1（0·1·1=0（1·1）=0；（1··=（·）=0对x,y 0（x+）=0=0+0=(0·x)+(0·Ⅱ1（x+y）当 1(xy)10000(10)(10)(1x) 1 xy（xy1）1(xy)11110(11)(10)(1x)(1 0 所以xyz{0,1}zxyzxz所以·对+0+·<{0，1}，+·>[{0，1}，+·] 树的应用树权C(T)=23+1+4+9+3+17=57（10分000、00 、1英文短语HAPPYNEWYEAR的编码信息为000001010010011100101001001101001六、+YYYYYYNNYNNN一、填空30%（每空3分1、选择合适的论域和谓词表达集合A=“直角坐标系中，单位元（不包括单位圆周）的点集”则A= 2、集合A={,{}}的幂集P(A) 。4A={<1,2>,<2433则AB AB 5、设|A|=3，则A上 7、偏序集A,R的哈斯图为 R 8、设|X|=n，|Y|=m则（1）从X到Y （2）当n,m满 10 ，R：我有时间 (QR)(RQ) 11 (QP)(PQ) 12 若S{S1,S2,,Sm}是集合A的一个分划 二、选择20%（每小题2分 A、A{x|x是偶数或奇数} B、B{x|y(yIx2y)}C、Cx|yyIx2y1)}；DDx|0,1,1,2,2,3,3,4,4,} A、2N,NS则2S B、NQ,QS则NSCNQ,QRNR；D、NS与

则NS A、C和{a,b}；B、{a,b}与；C、{a,b}与{a,b}；D、C与C4、下列语句不是命题的有（ Ax=13BC、鸡有三只脚；D、系以外的星球上有生物；E、你打算考吗？5、(PQ)R的合取范式为 A、(PQC

；B、(PR)(Q (PQRPQRPQRPQRPQRPQR)D、(PQRPQRPQRPQR。6|A|=n，则A上有（）A、2n；B、n2；C、2n2 D、nn；E、2nn7r为集合A上的相容关系，其简化关系图（如图则 r产生的最大相容类为 A、{x1x2}；B、{x1x2x3}；C、{x4x5}；D、{x2x4[II]A的完为 C、{{x1x2x3},{x2x4x5D、{{x1x2x3},{x4x5 A、{xy|xyNxy10)}；B、{xy|xyRyx2C{x,y|(x,yR)(y2 D{x,y|(x,yI)(xymod3)}10、NfN则f是

f(x)(x)mod3（x3的余数三、简答题1Hass图如何？（2）偏序集{S}的极小元、最小元、极大元、最大元是什么

,2（5分）设解释R如下：DR是实数集，DR中特定元素a=0，DRf(x,y)x F(x,y):x Axyz(F(xyFf(xzfyz四、逻辑推理X={1,2,3,4,5}，X上的关系R={<1,1>,<1,2>,<2,4>,<3,5>,<4,2>}六、证明2g2>

二十四 填空20%（每小题2分1 2 4、1,22,4<3,31，3，<2,4>,<4,2>}、{<1425、 6、{<1,1>,<2,2>,<3,3>7、 8、mn、n=m、n!；9、假；10、我将去当且仅当我有空 12 二十五、选择20%（每小题2分123456789CBBCABD二十六、简答题1（10分（ ）≤ 2（5分）解：A涵义为：对任意的实数x,y,z，如果 则(x-z)<(y-A（T。证 1时 2时二十九、证明 于B是一有限集合，故一定可找出两元素x,y是无关的，由 所以x,y必有关系，。 2（8 由 又因为g是函数，必对任 ，任每个z在g作用下都是YZ的任意性，所以g一、填空10%（每小题2分 2、 (yP(x,y)zQ(x,z))xR(x,y)中自由变元进行代入 3、xF(x)

。二、选择30%（每小题3分 A、(PQ)R B、((PQ)(RS)C、PQR D、((PQ)R)S A、2是素数；B、x+5>6；C、地球外的星球上也有人；D、这朵花多好看呀。3、下列是重言式的有（ A、(PQ；B、(PQQ；C、(QPP；D、(PQ AACBCABBACBCABC、若AB，则AB D、若AB，则AB 为BC形式，那么将B作为前提，设法演绎出D、设(A)是含 ，BA，则可用B替换(A)中的A。6、命题“有的人喜欢所有的花”的逻辑符号化为（ 设D：全总域，F（x：x是花，M(x)：x是人，H(x,y)：x喜欢A、x(M(xy(FyH(xy；B、x(M(xy(FyH(xyC、x(M(xy(FyH(xy；D、x(M(xy(FyH(xy7 xy(P(x,y)Q(y,z))xP(x,y)换名 A、xu(P(xu)Q(u,z))xP(x,y)；B、xy(P(xu)Q(u,z))xP(xC、xy(P(x,yQyz))xP(x,u)；D、uy(P(u,yQyz))uP(u,y8、给定 xP(x)xP(x)，当D={a,b}时，解释（ 为0。9、下面蕴涵关系成立的是（ A、xP(xxQ(x)x(P(xQ(xB、xP(x)xQ(x)x(P(x)Q(xC、xP(x)xQ(x)x(P(x)Q(xD、xyA(xyyxA(xy ①yyF(x,②yF(z,③F(z,④xF(x,⑤yxF(x,

P三、逻辑判断1（8分）下列命题相容吗？A (B (PQ)(PR),PQR是否等价今天或者天晴或者下雨。如果天晴，我去看；若我去看，我就不看书。故我在四、计算(QR)(PR)的真值。2（7分I：D={2，3}，L（x,y）L(22L331L23L320求谓词合 yxL(x,y)的真值五、三十 填空15%（每小题3分1P，Q的真值相同；2(yP(uyzQ(uzxR(xv；3x(F(xG(x4、xA(x)A(y)；5、三十一、选择30%（每小题3分123456789BBCCDABBC三十二、逻辑判断1（8分①A ④(B⑥

P 所以AB,(B 2（10分(PQ)(PR)(PQ)(P((PQ)(RR))((PR)(Q(PQR)(PQR)(PQM100M101MPQRP(QR)(PQ)(P((PQ)(RR))((PR)(Q(PQR)(PQR)(PQ(PQR)(PQR)(PQM100M101M①P②S

PS

SR R③P⑤P⑥P⑦R

P计算(QR)(PR)(10)(11)012（7分yxL(x,y)y(L(2,y)L(3,y))(L(2,2)L(3,2))(L(2,3)(10)(01)00三十四 逻辑推理x(Q(xR(xx(Q(x)I(x))x(R(x)I①x(Q(x)I ②Q(c)I③x(Q(x)④Q(c)⑤⑥⑦I⑧R(c)I⑨x(R(x)I

x(F(xy(GyL(xy)))x(F(xy(HyL(xx(G(x)H⑴x(F(x)y(G(y)L(x,⑵F(a)y(G(y)L(a,⑶F⑷y(G(y)L(a,⑸x(F(x)y(H(y)L(x,⑹F(a)y(H(y)L(a,⑺y(H(y)L(a,⑻y(L(a,y)H(⑼G(z)L(a,⑽L(a,z)H⑾G(z)H⑿x(G(x)H

P一、填空20%（每小题2分1 P（x：xE（x：xQ（x：xD（x，y：xx(E(xy(D(xyEy。6。 = 。）8、=。 10、若 是集合 上的偏序关系，则 二、选择20%（每小题2分 AgfgfBgfg,fCgfg,f都是单射；Dgff2、设f，g是函数，当 ）时，f=gA、xdomf都有f(x)g(x) B、domgdomf且fgC、f与g的表达式相同 D、domgdomf,

rangefAfx1x2|x1x2N且x1x210}Bfx1x2|x1x2Rx1x2Cfx1x2|x1x2Nx2为小于x1的素数的个数Dfx,x|xR}4、下列函（ （ （ A、f:NN,f(x)x22 B、f:NN,f(x)x(mod3)（x除以f:N

f(x)

f:R f(x)2xC 5、集合A={1，2，3，4}上的偏序关系 ，则它的Hass图 7、设R，S是集合A上的关系，则下列（ C、若R,S传递的，则RS是传递的；D、若R,S称的，则RS是称的8、设X为集合，|X|=n，在X上有（ C、22n D、2n2 ①xy(x ②y(z③(zCz④x(x

设H（x：x是人，P（x：x犯错误。A、x(H(x)P(x)) B、(x(H(x)P(x)))C、(x(H(xP(xD、x(H(xP(x三、1（10分）用反证法证明(PQ(PR)(QS)SR2（8分）CPPQRRQSPQS3（10分）演绎推理：所有的有理数都是实数，所有的无理数也是实数，虚数不是实数。四、将 x((yP(x,y))(zQ(z)R(x)))化为与其等价的前束范式A={a,b,c,d}，R={<a,b>,<b,c>,<b,d>,<c,b>}为A上的关系，利用矩阵乘法求R的传递闭包，并画出t（R）的关系图。1（8分）设A={1，2，3，4}P（A）R{s,t|s,tP（A）(|s||t2（8）fAAf一、填空20%（2分

ff=IA7 ；8 ；9 二、选择20%（每小题2分123456789BCCAADC三、命题演绎 ⒀2（8分

x：x⑴P⑵⑶P⑷⑸P⑹⑺⑻⑼⑽⑾⑿四、五、所以1（8分证明 P（A P（A P（A所以R是传递的。由⑴⑵⑶知，R是等价关系。P（A）/R=2（8分证明：因为f 即由 a的任意性知：f=IA五、填空20%（每空2分x≤y=x|y,则xy 2、设A{x|x2n,nN}，定义A上的二元运算为普通乘法、除法和加法，则 *αβγδζααβγδζββδαγδγγαβαβδδαγδγζζδαγζ 则G {a,b|aG,bGa1*b 若|G|=n,|H|=m则m和n关系 则f的同态核Ker(f {x|xG且f(x六、选择20%（每小题2分 A、GB、GC、包含G；DG+A、(-a)·(-b)B、(-a)·bC、a·(-b)D、a·b3<A，+>是一代数系统且<A，是AbelD）}}}4、设<A，+，·>是一代数系统，+·为普通加法和乘法运算，当A为（B 时，<A，+，·>是域。{x|xa,a,bC

,且a

D、{x|x0，xI}5、设<A,>是一个格，由格诱导的代数系统为A

,，则 A、A,,满足对的分配律；B、abAababbC、a,b,cA,若aba 则bcD、a,bA,有aab)baab)b6设<A,>是偏序集“定义为：a,bA,aba|b则当A=（A 时，<A,>是格。；；；7、设A,,是由格<A,>诱导的代数系统，若对abcA，当ba有 ）<A,>是模格A、a(bc)b(ac) B、c(ac)a(bc)C、a(bc)b(ac) D、c(ac)b(ac) AB、有补格；C、分配格；D9、在布尔代数A,,,中，bc0当且仅当 A、bc；B、cb；C、bc；D、cb10、设A,,,是布尔代数，f是从An到A的函数，则 ）A、f是布尔代数；B、f能表示成析取范式，也能表示成合取范式；D、若f是布尔函数，它一定能表示成析（合）取范式。A={1，2}，A上所有函数的集合记为AA,AA上运算的运算表，并AA中是否有幺元，哪些元素有逆元。

a*bababn2<G,*>n阶循环群，G=(a)b=akkIbdd=(nk)（10分）+可能是整环。（8分）)5K={1,2,5,10,11,22,55,110}110xK,x和全下界1的代数系统<K,LCM ,ˊ>是一个布尔代数 x（10分五、布尔表达式E(x1x2x3(x1x2x2x3x1x3是布尔代数{0,1},,,上（10分）一、填空20%（2分LC（x,y26、{a,b|aG,bGa1*bH}mn；7、{x|xG且f(x)12345678123456789BDABAADC三、 AA{f,f,f,f解：因为|A|=2，所以A上共有2=4个不同函数。 4，其中f1(1)1,f1(2)2 f2(1)1,f2(2)1 f3(1)2,f3(2)2 f4(1)2,f4(2)fffffffffffffffffffff1AAf1f4四、证明1（8分 aR，0*a0a0aa,a*0a0a即0*aa*0

a,b,c(a*b)*c(abab)*cababc(abab)abcabacbcaba*(b*c)abcabacbcab(a*b*ca*(b*c)R，*〉是独异点。2（10分）证明：（1）d(nk),设ndn1kdeank1adn1k1akn1 （2）若b的阶不为n，则b阶m<n，且有n1l (l1)，则有bme， akme,

dk1e

dna1

nae

d (n, n

1

3（6分a,bA,gf(a☆b)g(f(a☆b))g(f(a)*fg(f(a))△g(f(b))gf(a)△gfg4（8分

即有aa1aa1)aaaaa+5（10分代数系统<K,LCM ,ˊ>是由格<K,| 图中不存在与五元素 （2）xK,x100/ 使得:LCM(x,x) (x,x)如221105

LCM(22,5) (22,5)<K,LCM,,’>是布尔代数五、布尔表达式00000011010101111001101111011110

E(x1,x2,x3)(x1x2x3)(x1x2x3)(x1x2x3(x1x2x3)(x1x2x3)(x1x2x3E(x1x2x3x1x2x3x1x2x3七、填空10%（每小题2分1、Z{x|xZx0}，*表示求两数的最小公倍数的运算（Z表示整数集合对于* 则e和的关系为 3、设<G,*>是一个群，<G,*>是阿贝尔群的充要条件 4为、图的完。全关联矩阵5是、—个图是平面图的。充要条件八、选择10%（每小题2分1、下面各集合都是N的子集（ 封闭的。WEI什么A也对？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乘法，则积代数G1G2的幺元是（ A、<0,0>；B、<0,1>；C、<1,0>；D、<1,1>3S={1,2,3,6}<S,≤ 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 ）个4度结点 D、410%（每小题2分1（ ）设S={1,2}，则S在普通加法和乘法运算下都不封闭2（F ）在布尔格<A,≤>中，对A中任意原子a，和另一非零元b，在ab或ab中有且仅有一个成立。T(这是原子的性质)3 ）设S{x|xZx0}N，+,·为普通加法和乘法，则<S，+·>是域4F5F）没Tmt片树叶，i个分枝点，则(m-1)it-1四、证明1（8分）对代数系统<A,*>，*A上二元运算，eA中幺元，如果*是可结合的且每个2（12分）A,,是一个布尔代数，如果在A上定义二元运算☆，为a☆babab，则<A,☆>4（8分）若GV,E ek(v k2五、应用

v

需几天？（思路：对图的问题至 七个人的座位安排在圆桌旁，使得每个人均能与他旁边的人交谈？（8分思路：仍然是找H回路）a，bcd，ef2%3%，57%，8%，9%求传输它的最佳前缀码。（8分）三十五、填空10%（2分1、1，不存在；2、e；3、abG有(a*b*(a*b)(a*a*(b*b4111000001001000三十六、选择10%（每小题2分12345BCDA三十七、判断12345YYNNN证明设abcA，ba的右逆元，c是b的右逆元，由于b*(a*b)b*ebeb*cb*(a*b)*c(b*a)*(b*c)(b*a)*eb*a有两个逆元b、cbb*eb*(a*c)(b*a)*ce*c[乘]在A上封闭，A[群]abc(((ab)(ab))c)((ab)(ab)(abc)(abc)((ab)(ab)(abc)(abc)(((ab)(ab))(abc)(abc)(abc)(ab同理可得a☆(b☆cabcabcabcab(a☆b)☆c [幺]aAa☆00☆a(0a(0a)0(1a)0a0是A[逆]aA(a☆a)aaaa)00即A[交]a☆bababbaba所以<A☆>Abel群。3、(10分)证明:设A,是一环,且由A,是群，易证

fAffA也是AbelA,是半群，易证fA),b1,b2,b3f(A),则必有相应的a1,a2,a3使得:f(ai)bi,i 于b1(b2b3)f(a1)(f(a2)f(a3))f(a1)(f(a2a3f(a1(a2a3))f((a1a2)(a1a3))f(a1a2)f(a1a3(f(a1)f(a2))(f(a1)f(a3同理可证(b2b3b1b2b1b3b1因此fA5（8分）证明：设Gr个面，rdeg(ri)

而deg(ri) (1i 2e 即

而ver 故ve2rk

即ek(vk 32%1（8分）用Welch-Powell方法对 (G)≤3

v9v1v4v6，剩余点v3v7v2v5v8v3v7v5，剩余点v2v8任v2v3v9≥3(G2（8分 A(G) 1 1 解 A

A

1 101000 01000

11i

0；i2：

1A

1 101 01i3：

1A

111111 1 11i4：

111

3（8分此图中的HamiltonHamiltonabdfgecaW(T)243453927282传输它们的最优前缀码为{0000，0001，001，01，10，11}九、填空10%（每小题2分1A,,,是由有限布尔格A诱导的代数系统，S是布尔格A, A, *αβγδαδαβγβαβγδγβγγγδαδγδ ,α的逆元 [i]3[j][(ij)mod3]，则+3的运算表 4、设G是n阶完全图，则G的边数 十、选择20%（每小题2分1、在有理数集Q上定义的二元运算*，x,yQ有x*yxyxy，则Q中满足（ C、xQx1x1；D2、设S={0，1}，*为普通乘法，则<S,*>是 3、 ABCDA,B,C3、有向图D=<V, ，则v1到v4长度为2的通路有（ A、0；B、 D、34、在Peterson EulerA、1；B、 D、5 判断10%（每小题2分ee

a1

e （e 3、设A{x|xab a,b均为有理数}，+,·为普通加法和乘法，则代<A，+·> 4、设G=<V,E>是平面图，|V|=v,|E|=e，r为其面数，则v-e+r=2（ 5、如果一个有向图D是欧拉图，则D是强连通图 四、证明1<A,*>，是半群，e是左幺元且xAxˆAxˆ*xe，则<A,*>是群。（10分）3aH和bH是子群HG中的两个左陪集，证明：要末