离散数学试题(十五套)

1、087ynu 离散数学试题与答案试卷一一、填空20% ( 每小题 2 分）1设A x | ( xN)且( x5), B x | xE 且 x7 （ N：自然数集，E+ 正 偶2A ，B,C 表示三个集合，文图中阴影部分的集合表达式为。ABC3设 P，Q 的真值为0,R， S 的真值为1，则(P(Q(RP )( RS) 的真值 =.4公式 ( PR)(SR)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图的补图

2、为。数）则AB。.9 设 A=a ， b，c,d，A 上二元运算如下:*abcdaabcdbbcdaccdabddabc那么代数系统 的幺元是逆元分别为,有逆元的元素为。10下图所示的偏序集中,是格的为。，它们的二、选择20 （每小题2 分)1、下列是真命题的有(）A a a;B , ;C,；D 。2、下列集合中相等的有（)A 4， 3；B ,3， 4；C 4 ， 3，3 ； D3 ， 4 。 3、设 A= 1， 2，3 ,则 A 上的二元关系有(）个。A 23 ；B 32;C3 32 223;D。4、设 R，S 是集合 A 上的关系 ,则下列说法正确的是（）A 若 R,S 是自反的，则 RS

3、是自反的；B 若 R,S 是反自反的，则 RS 是反自反的；C若 R,S 是对称的，则 RS是对称的；D 若 R,S 是 传 递 的 , 则 RS是传递的。5、设 A= 1， 2，3， 4，P（ A) （ A 的幂集 )上规定二元系如下Rs,t| s, tp( 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 07、下列函数是双射的为(）A f : IE ,f (x ） = 2x；B f : NNN,f (n) = ;C f ：RI ,f (x ）

4、= x ；D f :IN，f (x)=x | 。（注： I整数集 ,E偶数集 , N自然数集 ,R实数集）8、图中 从 v1 到 v 3 长度为 3 的通路有（）条。A 0；B 3.1；C2;D9、下图中既不是Eular 图,也不是Hamilton 图的图是（)6、设 A=, 1 ， 1，3 ， 1,2 ， 3 则 A 上包含关系“”的哈斯图为（)10、在一棵树中有7 片树叶， 3 个 3 度结点 ,其余都是4 度结点则该树有（） 个 4 度结点。A 1； B 2；C 3；D 4 。三、证明26%、 R 是集合 X 上的一个自反关系,求证： R 是对称和传递的，当且仅当 a, b 和 a ,

5、c在 R 中有。 b ， c在 R 中.（ 8 分）、 f 和 g 都是群 G1 ，到G2， * 的同态映射,证明是的一个子群 .其中 C= x | xG1且f ( x)g(x)(8 分)、 G=（ V= v，|E =e ） 是每一个面至少由k（k3)条边围成的连e通平面图，则分）k(v k2)2， 由此证明彼得森图（Peterson)图是非平面图.（ 11四、逻辑推演16%用 CP 规则证明下题(每小题8 分）1、 A2、Bx(P(x)CD, D Q( x)EFxP (x)AFxQ (x)五、计算18%1、设集合A=a ，b,c，d 上的关系R=a , b ， , b, c ， c ， d

6、用矩阵运算求出R 的传递闭包t (R） .（ 9 分）2、如下图所示的赋权图表示某七个城市v1, v2 , v7 及预先算出它们之间的一些直接通信线路造价， 试给出一个设计方案，使得各城市之间能够通信而且总造价最小。（分 )试卷一答案：一、填空20%（每小题2 分)1、 0,1,2，3,4， 6 ； 2、 ( BC)A； 3、 1；4、 (PSR)(PSR) ；5、1;6、1，1, 1,.3， ， 2， 4 ； 7、 a.b，a,c， c， dIA； 8、9 、 a ； a ， b , c ,d ； a , d ，c ， d ； 10、c；二、选择20%（每小题2 分)题目1234567891

7、0答案CDB、CCADCADBA三、证明26% 1、 证：“”a, b, cX若, R由R对称性知, c, aR ,由 R 传递性得R“”若R , R 有R任 意a,bX ， 因R 若 RR所以 R 是对称的。若 R ， R则Rb, cRR即 R 是传递的。2 、 证a, bC，有f (a)g(a),f (b)g (b)，又1f (b 1)f 1(b) ,g(b 1 )g 1(b)f (b 1)f1(b)g 1 (b)g(b 1 )1f (a b)f (a) * f1 (b)g(a)*g(b 1 )g(a b)a b 1C3、 证： C , 是 G1 , 的子群。r2ed (Fi )rkr2e

8、 设G 有r个 面 , 则i 1, 即k。 而ver2 故2verve2ek 即 得ek (v k2)2。(8 分)ek(v2)彼得森图为k5, e15, v10 ，这样k2不成立 ,所以彼得森图非平面图。（ 3 分）二、 逻辑推演16%1、 证明： AP（附加前提） ABT I ABCDP CDT I DT I DE DEFT I P FT I AFCP2、证明xP( x)P（附加前提） P(c)USx(P( x)Q(x)P P(c) Q( c)Q(c)UST IxQ (x)xP (x)xQ( x)UG CP三 、 计算18%1、 解:0100101010100101M R00010000M

9、 R2，M RM R00000000M R3M R4M R2M R010110100000000010100101000000001111，M R3M RM t ( R)M RM R2M R3M R4111100010000t （ R）=a ，a , a ，b ， a , c ， ， b , a ， b ,b ， b , c 。 , ， c , d 2 、 解：用库斯克 (Kruskal ）算法求产生的最优树。算法略.结果如图：树 权 C（ T)=23+1+4+9+3+17=57即为总造价 .试卷二试题与答案一、填空20%（每小题 2 分)1、 P：你努力， Q：你失败。“除非你努力，否则你将

10、失败”的翻y 译为;“虽然你努力了,但还是失败了”的翻译为。2、论域 D= 1， 2，指定谓词PP (1,1)P （ 1，2）P (2,1）P （ 2,2)则公式TTFFx yP( y, x) 真 值为。2、 设 S=a 1 ， a2 ， ,a8 ，B i 是 S 的子集，则由B 31 所表达的子集是3 、 设A=2 ， 3,4 ， 5 ， 6 上 的 二 元 关 系 Rx, y| xyx是质数 , 则（列举法）。R 的关系矩阵M R=。5、设 A=1 ，2,3, 则 A 上既不是对称的又不是反对称的关系R=A 上既是对称的又是反对称的关系R=。6、设代数系统, 其中 A=a ， b， c ,

11、9、n 个结点的无向完全图K n 的边数为，欧拉图的充要条件是。10、公式 ( P(PQ )(PQ)R 的根树表示为。R=；abcaabcbbbc则 幺元 是; 是 否 有 幂 等cccb性；是否有对称性。7、4 阶群必是8、下面偏序格是分配格的是群或。群。二、选择20%（每小题 2 分）1、在下述公式中是重言式为()A ( PQ)( PQ) ;B (PQ)(PQ)(QP) ；C(PQ)Q ；D P( PQ) 。2、命题公式(PQ)(QP)中极小项的个数为（)，成真赋值的个数为（)。SA 0；B 1；C2；D 3 。3、设 S,1, 1,2 ， 则2有（)个元素。A 3;B 6;C 7；D 8

12、 .4 、 设 S 1,2, 3 ，定义 SS上的等价关系Ra,b,c, d|a,bSS,c, dSS, adbc则由R 产生的 SS上一个划分共有(）个分块。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 | xab3 ,a,bQS x | x2n ,a,bZS x | x2 n1,nZS x | xZx0= N。7、下面偏序集（)能构成格。8、在如下的有向图中，从V 1 到 V

13、4 长度为 3 的道路有 (）条。A 1;B 2;C 3；D 4 。9、在如下各图中(）欧拉图。设 R 是实数集合 ,“”为普通乘法，则代数系统R , 是(） .A 群 ;B独异点；C半群.三、证明461、 设 R 是 A 上一个二元关系，10、Sa, b| (a, bA)(对于某一个 cA, 有a, cR且c, bR) 试 证明若 R 是 A 上一个等价关系，则S 也是 A 上的一个等价关系。 （ 9 分）2、 用逻辑推理证明：所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。（ 11 分)3 、 若f : AB 是从A到B的函数 , 定义一个函数g : B2 A 对任

14、意bB 有g(b) x | ( x(f ( x)b)，证明 :若 f 是 A 到 B 的满射 ,则 g 是从 B 到2 A的单射。（ 10 分）4、 若无向图G 中只有两个奇数度结点,则这两个结点一定连通。（ 8 分）5 、 设 G 是 具有n 个结点的无向简单图，其边数Hamilton 图（ 8 分）四、计算14m1 ( n 21)( n2)2,则G 是1、 设Z6，+6是一个群 ,这里 +6 是模 6 加法， Z6= 0 ， 1 ，2， 3,4 ， 5,试求出 Z6 ,+6的所有子群及其相应左陪集。（ 7 分）2、 权数 1,4， 9， 16,25,36， 49， 64， 81， 100

15、构造一棵最优二叉树.(7 分)试卷二答案：一 、 填空20% （每小题2 分）1、PQ ； PQ 2 、T3 、B31B00011111 a4 , a5 , a6 , a7 , a84、 R= 2,2 ，2,3,2,6, ，3， 3 ,3， 4， 3,5 ， 3， 6,4,5， 4,6 ，,5， 4, ，5,6 ；2， 1 ； R=1， 1,2,2,3,35、R= 1,2,1,3 ，11111111110001111111000006、 a；否；有7、Klein四元群；循环群8、B9、1 n(n21)；图中无奇度结点且连通10 、二、选择20（每小题2 分)题目12345678910答案B 、

16、DD ； DDBDABBBB 、C三、证明46%1、(9 分）（ 1）S 自反的aA ，由 R 自反，(a, aR)(a, aR) ,a, aS（ 2）S 对称的a, bAa, bS(a, cR)(c,bR)S 定义(a, cR)(c, bR)R 对称b, aSR 传递（ 3）S 传递的a, b, cAa, bSb, cS(a, dR)(d , bR)(b, eR)(e, cR)(a, bR)(b, cR)R 传递a, cSS定义由（ 1)、（ 2）、(3)得； S 是等价关系 .2、11 分证明：设P(x）： x 是个舞蹈者；Q（ x) ： x 很有风度；S（x ）： x 是个学生；a：王华

17、上述句子符号化为：前提 :x(P( x)Q(x)、 S( a)P(a)结论：x(S( x)Q(x) 3 分 S( a)P(a)Px(P( x)Q(x)P P( a) P( a) Q(a). S( a) S( a)Q(a)Q(a)US T IT I T IT Ix(S(x)Q(x)EG 11 分、 0 分证明:b1, b2B , (b1b2 )f 满 射a1 ,a2A使f (a1 )b1, f(a2 )b2 , 且f (a1)f (a2 ), 由于f是函数 ,a1a2又 g(b1) x | (x(f ( x)b1),g(b2 ) x| ( x(f (x)b2 )a1g(b1), a2g(b2 )

18、但 a1g(b2 ), a2g(b1 )g(b1 )g(b2 )由b1, b2任意性知,4、8 分g为单射 。证明: 设 G 中两奇数度结点分别为u 和 v，若u， v 不连通，则G 至少有两个连通分支 G1、 G2 ,使得 u 和 v 分别属于G1 和 G2，于是 G1 和 G2 中各含有1 个奇数度结点 ,这与图论基本定理矛盾，因而u,v 一定连通。5、8 分证明：证 G 中任何两结点之和不小于n.反证法： 若存在两结点u,v不相邻且d (u)d (v)n1 ,令 V1 u, v ,则 G-V 1 是mn 2个 结 点 的 简 单 图 ， 它 的 边 数121 (n2)(n3)1(n1)(

19、 n2)具 有m2(n1), 可 得2,这与 G1=G-V 1 为 n-2 个结点为简单图的题设矛盾，因而G 中任何两个相邻的结点度数和不少于n。所 以 G 为 Hamilton 图 。四、计算14%d 1 、 7 分解：子群有 ； ； Z 6,+ 6 0 的左陪集：0, 1 ； 2 ， 3 ； 4 ， 5 0 ， 3 的左陪集： 0 ， 3; 1， 4 ； 2， 5 0 ，2 ， 4 的左陪集： 0 ， 2， 4 ；1 ， 3 ， 5 Z6 的左陪集： Z 6 。2 、 7 分试卷三试题与答案一、填空 20% （每空 2 分）1、 设 f， g 是自然数集N 上的函数xN ,f (x)x1

20、,g(x)2 x ，则 fg ( x)。2、 设 A= a,b，c ， A 上二元关系R= , a ， b , a， c , ， 则 s（ R）=.3、 A=1,2 ，3， 4,5，6 ， A 上二元关系Tx, y| xy 是素数，则用列举法T=；T 的关系图为；T 具有性质 .4、 集合A, 2, 2 的幂集2 A =。5、 P,Q真值为0 ；R,S 真值为 1。则 wff ( P(RS)( P(RS) 的真值为。6 、 wff( PQ)R)R的主合取范式为。7、设P(x）：x 是素数，E（ x）：x 是偶数， O(x) ：x 是奇数N （ x,y) ：x 可以整数y。则谓词wffx(P(

21、x)y(O( y)N ( y, x)的自然语言是。8、 谓词wffxy(z( P( x, z)P( y, z)uQ (x,y, u)的前束范式为。二、选择 20 （每小题2 分)1、 下述命题公式中，是重言式的为（)。A 、 ( pq)( pq) ；B、 ( pq)( pq )(qp ) ;C、( pq)q ；D、 ( pp)q 。2 、 wff( pq)r 的主析取范式中含极小项的个数为（）。A 、2；B 、 3；C、5；D、0；E 、 8 。3、 给定推理x(F ( x)G(x)P F ( y)G( y)USxF( x)P F ( y) G( y)EST IxG (x) x( F ( x)

22、G( x)xG( x)UG 推理过程中错在（）。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，在条件XS1 且 XS3 下 X 与（）集合相等。A 、 X=S 2 或 S5 ；B 、X=S 4 或 S5；C、X=S 1， S2 或 S4；D、X 与 S1， S5 中任何集合都不等.5、 设R和S是P上的关系，P是所有人的集合,Rx, y| x, yPx是y的父亲，Sx, y| x, yPx是y的母亲 则 S 1R表示关系(）.A 、B 、x, y

23、x, y| x, y| x, yPx是y的丈夫 ;Px是y的孙子或孙女 ；C、；D 、x, y| x, yPx是y的祖父或祖母 .;6、 下面函数（)是单射而非满射。A 、 f : RR,f ( x)x22 x1B 、 f : ZR,f ( x)ln x ;C 、 f : RZ,f (x) x, x表示不大于 x的最大整数 ；D 、 f : RR,f( x)2x1。其中 R 为实数集， Z 为整数集， R+， Z+分别表示正实数与正整数集. 7、 设 S= 1， 2， 3 ,R 为 S 上的关系，其关系图为则 R 具 有（)的性质。A 、 自反、对称、传递;B、什么性质也没有；C、反自反、反对

24、称、传递；D 、自反、对称、反对称、传递。8 、 设 S,1 , 1,2，则有（）S 。A 、 1,2； B、 1， 2 ；C、1；D 、 2。9 、 设 A= 1 ,2 ， 3 ， 则 A 上 有（）个二元关系。A 、23; B、 32; C、223；D 、322。10、全体小项合取式为（）。A 、可满足式；B、矛盾式 ; C、永真式 ; D 、A ， B， C 都有可能。三、用 CP 规则证明16 （每小题8 分）1、 ABCD , DEFAF2、x(P( x)Q(x)xP(x)xQ( x)四、（ 14）集 合 X= ，3,4, 5 ， 6, ,R= ,x 2,y2 x1+y2 = x 2

25、+y 1。1、 证明 R 是 X 上的等价关系。(10 分）2、 求出 X 关于 R 的商集。 (4 分）五、（ 10%）设集合 A= a，b ， c ， d 上 关系R= , ， c ,d 要求1、写出 R 的关系矩阵和关系图.（ 4 分）2、用矩阵运算求出R 的传递闭包 .（ 6 分）六、(20 ）1、（ 10 分）设 f 和 g 是函数 ,证明 fg 也是函数。2、（ 10 分）设函数入射函数。答案：g : STf : TS ，证明f : TS 有一左逆函数当且仅当f 是五 、 填空20%( 每空 2 分）1 、 2(x+1) ； 2 、 a, a,a , b,a ,c,c , c,b

26、,a,c , a ;3 、2,1,4、3,1,5,1,4,2,6,2,6,3;反对称性、反自反性；4、,2, 2, ,2, 2；5、 1;6 、 (PQR)(PQ( PQR) ； 7、任意x，如果x 是素数则存在一个y ，y 是奇数且y 整 除 x ；8 、六 、 选择20 (每小题2 分）xyz u(P( x, z)P( y, z)Q( x, y,u ) .题目12345678910答案CCCCABDADC七、证明16%( 每小题8 分)1、 AP（附加前提） ABT I ABCDP CDT I DT I DE DEFT I P FT I AFCP2、xP( x)xQ (x)(x) P(x)

27、xQ( x)本题可证x( P( x)Q( x)(xP (x)xQ(x)(x(xP( x)P(x)P（附加前提） T EP(a)x(P( x)Q(x)ES P P( a) Q( a)Q( a)US T IxQ( x)EG(xP( x)xQ(x)CP八 、 14%（ 1）证明：1、自反性 :x, yX ,由于xyxyx, y2、对称性：,x, yRx1, y1X ,R自反x2 , y2X当x1, y1,x2, y2R 时 即x1y2x2y1 也即x2y1x1y2故x2 , y2,x1, y1RR有对称性3、传递性：x1, y1X ,x2, y2Xx3 , y3X当即x1 x2x1, y1y2 y3

28、,x2 , y2x2y1x3y2R 且(1)( 2)x2 , y2,x3, y3R时(1)(2)x1y2x2即 x1y3y3x2x3y1y1x3y2故x1, y1,x3, y3RR有传递性由(1 ）（ 2)（ 3）知 :R 是 X 上的先等价关系。2、 X/R= 九 、 10%1 ,2 R 0100101000010000M R1010010100000000010110100000000010100101000000001、；关系图M R22、M RM RM R3M R2M RM R4M R3M RM R 2M R5M R3, M R6M R4 ,M t ( R)M RM R2M R3M R

29、41111111100010000t （ R)= a , a ， a , b ， a , c ， , , b ， c . ， ，c , d 。六、20fgx, y| xdomfxdomgyf ( x)yg ( x)1、（ 1）令hfx, y| xgdomfdomgyf ( x)g(x)domfgdomh x | xdomfdomg,f (x)g( x)(2） hx, y| xdomfdomgyh(x)f ( x)g( x)对xdomh若有y1, y2使得y1h(x)f ( x)g( x) ,y2h( x)f ( x)g(x)由于f (或g)是函数,有y1y2 即xdomh 有唯一y使得yh(

30、x)fg也是函数 。2、证明： 若f有一左逆 g,则对tTgf (t )t故 gf是入射, 所以f 是入射 . f是入射,f : TS定义如下 :sf (T ),由 f入射,| tT,使f (t)s此时令g(s)t , 若sf (T)令g(s)cT则对sS, g(s)只有一个值t 或 c且若f(t )s则gf(t )g(s)t ,故g 是f的左逆元即若f入射, 必能构造函数 g,试卷四试题与答案使g为f左逆函数 。一、填空10 （每小题2 分）1、 若 P， Q，为二命题，PQ 真值为 0 当且仅当.2、 命题“对于任意给定的正实数，都存在比它大的实数”令F（ x):x为实数，L( x, y)

31、 : xy则命题的逻辑谓词公式为。3、 谓词合式公式xP (x)xQ( x)的前束范式为。4、 将量词辖域中出现的和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为换名规则。5、 设 x 是谓词合式公式A 的一个客体变元，A 的论域为D， A(x ）关于y 是自由的， 则ES。二、选择25 (每小题2。 5 分）1、 下列语句是命题的有（)。A 、 明年中秋节的晚上是晴天；B、 x被称为存在量词消去规则，记为y0 ；C、 xy0 当且仅当x 和 y 都大于 0；D、我正在说谎.2、 下列各命题中真值为真的命题有（).A 、 2+2=4 当且仅当3 是奇数； B、2+2=4 当且仅当

32、3 不是奇数 ; C、2+2 4 当且仅当3 是奇数 ; D、 2+2 4 当且仅当3 不是奇数；3、 下列符号串是合式公式的有()A 、 PQ ;B、 PPQ ； C、 (PQ)( PQ) ;D 、(PQ) 。4、 下列等价式成立的有(）。A 、 PQQP ； B、 P( PR)R ;C、P(PQ)Q ；D、 P(QR)( PQ)R 。5 、 若A1, A2An 和 B 为 wff ， 且 A1A2AnB 则（） .A 、称 A1A2An 为 B 的前件；B、称 B 为A1, A2An 的有效结论C、当且仅当A1A2AnBF；D、当且仅当A1A2AnBF 。6、 A,B 为二合式公式，且AB

33、 ，则（)。A 、 AC、 AB 为重言式；B 、B ；D 、A*B*A*B*；E 、 AB 为重言式。7、 “人总是要死的 谓词公式表示为（）。(论域为全总个体域）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)8、 公式 Ax( P( x)Q( x) 的解释 I 为：个体域D= 2 ，P（ x)：x3, Q（ x）：x=4则 A 的真值为（）。A 、1；B、 0；C、可满足式；D、无法判定。9、 下列等价关系正

34、确的是（)。A 、x( P(x)B、x( P( x)C、x( P( x)D、x( P( x)Q( x)Q( x) Q)Q)xP (x)xP( x)xP(x)xP (x)xQ( x) ；xQ (x) ； Q ；Q .10、 下列推理步骤错在(） .x( F (x)G( x)P F ( y)G ( y)USxF ( x)P F ( y) G( y)ES T IxG( x)EGA 、； B 、； C、 ;D、三、逻辑判断30%1、 用等值演算法和真值表法判断公式型。 (10 分）A( P(QP)( PQ) 的类2、 下列问题，若成立请证明，若不成立请举出反例：（ 10 分）已知 ACBC ， 问 A

35、B 成立吗？已知AB ，问 AB 成立吗 ?3、 如果厂方拒绝增加工资,那么罢工就不会停止,除非罢工超过一年并且工厂撤换了厂长.问：若厂方拒绝增加工资,面罢工刚开始,罢工是否能够停止。 （ 10 分）四、计算10%1、 设命题 A 1， A2 的真值为1， A3， A 4 真值为 0，求命题( A1( A2( A3A1)( A2A4 ) 的真值。（ 5 分）2、 利用主析取范式，求公式( PQ)QR的类型。（5 分）五、谓词逻辑推理15%符号化语句：“有些人喜欢所有的花，但是人们不喜欢杂草，那么花不是杂草. 并推证其结论。六、证明 :(10 ）设论域 D= a ， b , c，求证：答案：xA

36、( x)xB( x)x( A(x)B( x) 。十 、 填空10（每小题2 分）1、P 真值为1,Q 的真值为0； 2 、x(F ( x)L( x,0)y(F ( y)L( y, x)； 3 、x(P( x)Q( x) ； 4、约束变元 ;5、xA( x)A( y) ， y 为 D 的某些元素。题目12345678910十一、选择25% （每小题2。5 分）答案A,CA,DC，DA,DB,CA ， B， C， D,ECAB(4）十二、逻辑判断30% 1、（ 1)等值演算法A( PQ)(QP )( PQ)( PQ)( PQ)T（ 2） 真值表法PQPQQP( PQ)(QP)PQA11111111

37、00100101100010011111所以 A 为重言式。2、(1）不成立。若取 CT则ATTBTT 有 ACBCT但 A 与 B 不一定等价 ,可为任意不等价的公式。(2) 成 立 。 证明：AB充要条件ABTT即 ： 所 以 A(A(BA)BTB)( (A故ABA)( AB 。( AB)( B( BA)AB3、解：设P：厂方拒绝增加工资；Q：罢工停止；R 罢工超壶过一年；R：撤换厂长前提 : P P(RS) ( RS)Q) ,P,Q)R结论：QP PP(RS)QT IRPRS(RS)T I T EQT I罢工不会停止是有效结论。四、计算10（ 1）解：(1(10(10)0)11(11)(

38、1(10)111（ 2）( PQ)QR(P( PQ)(QR)P(QR)QQRF它无成真赋值，所以为矛盾式。五、谓词逻辑推理15%解： M ( x) : x是人;F ( x) : x是花;G(x) : x是杂草;H ( x, y) : x喜欢yx(M(x)y( F ( y)H ( x, y)x(M( x)y(G( y)H ( x, y)x(F ( x)证明：G( x)x(M M (a) M (a)(x)y( F ( y)y( F ( y)HH ( x,(a, y)y)PES T Iy( F ( y)x(M ( x) M (a)y(G( y)H (a, y)y(G( y)y(G( y)H ( a,

39、 y)H ( x, y)H (a, y)T I PUST Iy( H (a, y)G( y)T E F (z) H (a, z) F ( z)x( F ( x)H ( a, z)G( z)G( z)G(x)US US T I UG 十三、证 明 10%xA( x)( A(a)xB(x) B( a)( A(a)( A(a)A(b) B(b )A(c) ( A(a)( B(a)B( c)B(b)B(c)( A(b)( A(c)( A(a)B(a)B(a )B( a)( A(b)( A(c)( A(b)B(b)B(b)B(b )( A(b)( A(c)( A(c)B(c)B(c) B(c)x( A(

40、 x)B(x)试卷五试题与答案一、填空15%( 每空 3 分)1、设 G 为 9 阶无向图， 每个结点度数不是5 就是 6，则 G 中至少有个 5 度结点。2、n 阶完全图， Kn 的点数 X (K n）=。3、有向图中从 v 1 到 v2 长度为 2 的通路有条。4、设 R， +， 是代数系统，如果R， + 是交换群 R, 是半群则称 R， +， 为环。5、设 L, 是代数系统 ,则 L, 满足幂等律，即对aL 有。二、选择15 （每小题3 分)1、 下面四组数能构成无向简单图的度数列的有()。A 、（ 2,2，2， 2， 2）；B、（ 1， 1， 2， 2，3）；C、 (1， 1， 2，

41、2， 2）；D、（ 0， 1,3,3， 3）。 2、 下图中是哈密顿图的为(）。3、 如果一个有向图D 是强连通图，则D 是欧拉图，这个命题的真值为（）A 、真;B 、假。4、 下列偏序集（）能构成格。s5 、 设1,1, 2,21, 3,31, 44,为普通乘法，则S, 是（） .A 、代数系统；B 、半群；C、群；D 、都不是。三、证明48 1、（ 10%)在至少有2 个人的人群中，至少有2 个人，他们有相同的朋友数。2、（ 8%）若图 G 中恰有两个奇数度顶点，则这两个顶点是连通的。3、（ 8%）证明在6 个结点12 条边的连通平面简单图中, 每个面的面数都是3.4、(10）证明循环群的

42、同态像必是循环群。5、(12）设 B,0 ,1 是布尔代数，定义运算* 为 a * b(ab)(ab) ，求证 B,* 是阿贝尔群。四、计算22 1、在二叉树中1） 求带权为2,3， 5， 7， 8 的最优二叉树T.（ 5 分）2） 求 T 对应的二元前缀码。 （5 分）2、 下图所示带权图中最优投递路线并求出投递路线长度(邮局在 D 点） .答案：一、填空（ 15%）每空 3 分1、6； 2、n； 3、 2； 4、+对分配且对+分配均成立；5、 aaa 且 aaa .二、选择（ 15% ）每小题 3 分题目12345答案A,BB ，DBCD三、证明（ 48）1、（ 10 分）证明：用n 个

43、顶点v1， vn 表示n 个人，构成顶点集V=v 1， v n ，设E uv | u, vV, 且u,v是朋友（uv），无向图G=（ V ，E）现证 G 中至少有两个结点度数相同。事实上 ,(1）若 G 中孤立点个数大于等于2，结论成立 .（2） 若 G 中有一个孤立点，则G 中的至少有3 个顶点，既不考虑孤立点。设G 中每个结点度数均大于等于1,又因为G 为简单图，所以每个顶点度数都小于等于n-1，由于G 中 n 顶点其度数取值只能是1， 2,， n-1，由鸽巢原理,必然至少有两个结点度数是相同的。2、（ 8 分)证: 设 G 中两个奇数度结点分别为u,v.若 u， v 不连通则至少有两个连

44、通分支G1、G2,使得 u， v 分别属于G1 和 G2。于是 G1 与 G2 中各含有一个奇数度结点,与握手定理矛盾。因而 u， v 必连通。3（ 8 分）证： n=6 ，m=12欧拉公式n m+f=2 知 f=2 n+m=2-6 12=8由图论基本定理知： 每个面用3 条边围成。deg(F )2m24 ，而 deg(Fi )3 ，所以必有deg(Fi )3，即4(10 分） 证:设循环群A ，的生成元为a,同态映射为f, 同态像为 f(A ）,*, 于是an , amA都有f (anam )f (an ) *f (am )对 n=1 有f ( a)f (a)n=2,有f (a2 )f (a

45、 a)f ( a) *f (a)( f (a) 2若 n=k 1 时有f ( ak 1 )( f (a) k 1对 n=k 时 ，f (ak )f (ak 1 a)f (ak1) *f (a)( f (a) k 1 *f (a)( f (a) k这表明， f（ A) 中每一个元素均可表示为5、证：( f (a) n ，所以 f（A ）， 为 f(a ） 生成的循环群。（ 1）交换律 :a,bB 有a * b( ab)(ab)(ba )(ba)b * a（ 2）结合律：a, b,cB 有(a * c( ab)(ab ) * c( ab)(ab)c)( ab)(ab )c(abcabc)( a(

46、ab)cabcabcabc而:abc(aabcbabcaabba acabc bcabcb )ca * (b * c)a * ( bc)(bc)( a(bc)(bc)( a(bc)(bc)a(bab(bc)abcabcabcabcabc(a * ca * (b * c)（ 3）幺：aB 有a * 0( a0)( a0)a0a0* a( 0a)(0a)0aa0是 B，*幺元。（ 4）逆：aBa * a( aa)(aa)000a是a的逆元 。综上所述： B ， * 是阿贝尔群 .四、计算（ 22% ）1、（ 10 分）（1） (5 分)由 Huffman 方法，得最佳二叉树为:（2）（ 5 分）最

47、佳前缀码为:000， 001,01， 10， 11 2、（ 12 分）图中奇数点为E、F ，d（E)=3,d(F ）=3，d（ E,F）=28 p=EGF复制道路 EG、GF，得图 G ，则 G 是欧拉图。由 D 开始找一条欧拉回路 :DEGFGEBACBDCFD 。道路长度为：35+8+20+20+8+40+30+50+19+6+12+10+23=281。试卷六试题与答案一、填空15 （每小题3 分）1、 n 阶完全图结点v 的度数 d（ v) =。2、 设 n 阶图 G 中有 m 条边，每个结点的度数不是k 的是 k+1 ，若 G 中有 Nk 个 k 度顶点,Nk+1 个 k+1 度顶点，

48、则N k =.3、 算式(a(b * d)( e*f ) 的二叉树表示为。4、 如图给出格L，则 e 的补元是。5 、 一 组 学 生 ， 用 二 二 扳 腕 子 比 赛 法 来 测 定 臂 力 的 大 小 , 则 幺 元是。二、选择15 （每小题3 分）1、设 S= 0，1,2,3 ,为小于等于关系，则S，是（）。A 、群;B、环； C、域； D、格。2、设 a， b ，c，* 为代数系统，运算如下：abcaabcbbac则零元为 (） .ccccA 、a；B 、b；C、 c;D 、没有。3、如右图相对于完全图K 5 的补图为（)。4、一棵无向树T 有 7 片树叶， 3 个 3 度顶点，其余

49、顶点均为4 度。则 T 有（）4 度结点。A 、1；B、2；C、 3；D、 4。5、设 A,+ ，是代数系统,其中 +，为普通加法和乘法，则A= （）时， A ，+, 是整环。A 、 x | x2n, nZ ;B 、 x | x2 n1 , nZ ;C、 x | x0, 且xZ ;D、 x | xab4 5,a ,bR .三、证明50n 2m1、设 G 是（ n,m）简单二部图，则4。（10 分）m2、设 G 为具有 n 个结点的简单图,且1 (n21)( n2)，则 G 是连通图。 (10 分）3、记“开”为1，“关 为 0，反映电路规律的代数系统0,1 ， +， 的加法运算和乘法运算。如下

50、：+0101001000110101证明它是一个环，并且是一个域。（ 14 分)4 、 L , 是一代数格， “”为自然偏序，则L ，是偏序格。 （ 16 分）四、 10设 E(x1, x2 , x3 )( x1x2 )( x2x3 )( x 2x3 ) 是布尔代数 0,1, 上的一个布尔表达式，试写出E( x1 , x2 , x3 ) 的析取范式和合取范式（10 分）五、 10%如下图所示的赋权图表示某七个城市v1,v2 , v7 及预先算出它们之间的一些直接通信成路造价（单位：万元），试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。答案：一、填空15 (每小题 3 分）1、 n

51、 1； 2、n（ k+1)-2m;3 、如右图；4 、0 ； 5、臂力小者二、选择15（每小题3 分)题目12345三、证明50答案DCAAD（ 1）证：设 G=（ V ， E） VXY , Xn1, Yn2, n1n2n2nn 2m对完全二部图有nn1n2n1 (nn1)1n1nn22n( n1)24n当12时，完全二部图(n , m)的边数 m 有最大值4 n 2故对任意简单二部图( n , m) 有 m4 .（ 2）证:反证法：若G 不连通，不妨设G 可分成两个连通分支G1、G2，假设 G1 和G2 的顶点数分别为n1 和 n2，显然 n1n2nn11n21n1n1n2n1mn1(n11

52、)2n2 (n21)2(n1)(n1n22)2( n1)( n2)2与假设矛盾 .所以 G 连通。（ 3）（ 1） 0 ， 1 ， +， 是环 0， 1 ，+ 是交换群乘:由“ +”运算表知其封闭性。由于运算表的对称性知:+运算可交换。群: （ 0+0） +0=0+ （0+0 ） =0 ；（ 0+0 ） +1=0+ （ 0+1） =1;（0+1 ） +0=0+ （ 1+0 ）=1 ; (0+1 ） +1=0+ （ 1+1 ）=0；（1+1 ） +1=1+(1+1 ） =0结合律成立。幺：幺元为0。逆： 0， 1 逆元均为其本身。 0， 1 ,是半群乘：由“运算表知封闭群: （ 0 0） 0=0

53、 （ 0 0）=0 ；（ 00) 1=0 （ 0 1） = 0；（ 0 1) 0=0（ 10） =0 ; （ 01) 1=0 （ 1 1） =0； (1 1） 1=1（ 1 1） =0 。对 +的分配律x, y 0,10（ x+y ）=0=0+0= （ 0 x)+(0 y);1（ x+y ）当 x=y(x+y ）=0则1 ( x00y)1 0011(1 0)(1 1)(1 0)(1 1)(1 x)(1 y)；当 xy ( xy1 )则10(1 1)(1 0)1 (xy)1 1101(1 0)(1 1)(1 x)(1 y)所以x, y, z 0,1 均 有 z (xy)( z x)( zy)同理

54、可证：( xy) z(xz)( yz)所以对 + 是可分配的 .由得， 0,1,+ ， 是环。 (2） 0 ， 1 ，+,是域因为 0 ， 1， +， 是有限环 ,故只需证明是整环即可。乘交环 : 由乘法运算表的对称性知，乘法可交换。含幺环：乘法的幺元是1无零因子：1 1=1 0因此 0,1 ， +, 是整环 ,故它是域。4、证：（ 1 )“”是偏序关系， 自然偏序a,bLaba反自反性：由代数格幂等关系: aaaaa。反对称性：a, bL若ab , b即： aa,bb ，则aababba传递性：ab , bc 则:ac(ab)cab即abaa(bc)结合律abbaaacc即bcbb即aba(

55、2）x, yL在 L 中存在 x，y的下（上）确界设 x, y事实上：L 则: x x( xyinfy)( xx, yx)yxyxyx 同理可证 : xyy若 x ，y 有另一下界c，则 c( xy)(cx)ycyccxyxy 是x， y 最大下界，即xyinfx, y同理可证上确界情况.四、 14%解:函数表为：x1x2x3E( x1 , x2 , x3 )00000011010001111000101111011111E( x1, x2 , x3)( x1x 2(x1x3)(x1x2x3 )x2( x1x3 )( x1x2x3 )x2x3 )析取范式：合取范式：E( x1, x2 , x3

56、)( x1x2x3 )(x1x2x3)( x1x2x3 )五、 10解：用库斯克 (Kruskal ）算法求产生的最优树。算法为：w(v1, v7 )1w(v7, v2 )4w(v7, v3 )9w(v3 , v4 )3 w(v4, v5 )17 w(v1, v6 )23 结果如图：选 e1 选e2 选e3 选e选e选ev1v7 v7 v2 v7v3 v3v4v4 v5 v1v6树权 C(T)=23+1+4+9+3+17=57 （万元）即为总造价试卷七试题与答案一、填空 15% （每小题 3 分）任何 (n,m)图 G = (V,E ）， 边与顶点数的关系是。当 n 为时, 非平凡无向完全图K

57、n 是欧拉图 .已知一棵无向树T 有三个 3 顶点，一个2 度顶点 , 其余的都是1 度顶点， 则 T 中有个 1 度顶点。n 阶完全图Kn 的点色数X(KN)=。一组学生，用两两扳腕子比赛来测定臂力大小，则幺元是。二、选择 15% （每小题3 分）1、下面四组数能构成无向图的度数列的有（)。A 、 2,3,4， 5， 6， 7；B、 1,2 ， 2,3 ， 4；2、图的邻接矩阵为（）。A.G1=(V1， E1),其中 V 1=a ，b,c,d， e,E 1= ab,be ， eb,ae ， de;B.G2=(V2， E2) 其中 V2=V1,E 2= a，b，b， c, c， a，a,d ，

58、d,a ，d,e ；C.G=(V3,E 3) ，其中 V3=V1,E 3= ab,be ， ed，cc ；D.G=（ V4， E4） , 其中 V4=V1,E 4= （ a， a） , （a,b),（ b， c ），（ e， c） ,(e,d）。4、下列图中是欧拉图的有（)。C、 2,1,1,1,2；D、 3 ， 3， 5，6， 0。1000111101000100010111110011010111011111110111011000 ;B、1111 ； C、1000 ； D 、10005、 G(2S ,) ，其中 S1,2,3 ,为集合对称差运算，则方程 1,2x1,3 的解为（）。A 、

59、 2,3;B 、1,2,3 ；C、 1,3;D、。A、。3、下列几个图是简单图的有(）。三、证 明 341、 证明：在至少有2 个人的人群中,至少有2 个人，他的有相同的朋友数。（ 8 分）2、 若图 G 中恰有两个奇数顶点，则这两个顶点是连通的。（ 8 分）3、 证明：在6 个结点 12 条边的连通平面简单图中,每个面的面度都是3.（ 8 分）4、 证明循环群的同态像必是循环群。(10 分）四、中国邮递员问题13%求带权图G 中的最优投递路线。邮局在v 1 点。五、根树的应用 13 5、 7： 5在通讯中 ,八进制数字出现的频率如下：0:30% 、1：20%、2:15% 、3：10、 4：

60、10、 5：5、 6：求传输它们最佳前缀码（写出求解过程）。六、10*eababeeababaaeabbbbabeaababbae答案 :设 B 4= e ，a ， b , ab ，运算 * 如下表 ,则B 4,是一个群（称作Klein 四元群十四、填空15 (每小题 3 分）1、 vd(v)V2m； 2、奇数； 3、5； 4、 n；5、臂力小者十五、选择15（每小题3 分）题目12345答案BCBBA十六、证明341、（ 10 分) 证明：用n 个顶点v1， ,vn 表示n 个人,构成顶点集V= v 1, ,vn，设E uv | u, vV, 且u,v是朋友（uv），无向图G=（ V ， E