华科离散数学试题与答案试卷

1、离散数学试卷与答案试卷一 一、填空 20% （每小题2分） ?7且x?x|x?E?|(x?N)且(x?5),B?Ax+正偶N1设：自然数集，E（?BA? 数）则。 表示三个集合，文图中阴影部分的集合表达式为B，C2A， 。A B C 1，则S设P，Q 的真值为0，R，的真值为3)?S?(R?Q?(R?P)(?(P? = 。的真值P?)?R?P?R)?(S( 的主合取范式为4公式 。)xxP(xPx)? 下真值为在I5若解释I的论域D仅包含一个元素，则 。 A上关系图为3，4，设6A=1，2， 2 R。 = 则 R，其上偏序关系的哈斯图为b，c，dA=a7设， 。则 R= 的补图为。图8 上二元

2、运算如下：，设9A=abcd A 1 / 19 a b c d * a b c d a b c d a b c d a b c d a b c d 的幺元是，有逆元的元素为，它们的逆元分别为。，*那么代数系统A 下图所示的偏序集中，是格的为。10 20% 择 二、选 2分）（每小题 ）1、下列是真命题的有（ ?,?a?a B； A?,? 。；C D 、下列集合中相等的有（）2? 。 3，43，3；DBC，3，4；4， A4，3，； ，则A上的二元关系有（）个。、设A=1，2，3322?33?32 3 2 ；C。B 3； D A 2； A上的关系，则下列说法正确的是（）、设R，S是集合4SR?

3、是自反的；S 是自反的，则R A若，SR? 是反自反的；S 是反自反的，则 B若R，S?R 是对称的，则是对称的； C若R，S S?R 是传递的。若 DR，S 是传递的，则 ）（A的幂集）上规定二元系如下，4，P（A35、设A=1，2，|t?(|s|p?|s,t?(A)?,?R?st （）（A）/ R=则P ；，34，2，1，23，1211CP(A) BA A；，?A 432322D，2 / 19 ?”的哈斯图为（） 则A上包含关系“，1，2，6、设A=3，1，1，3 7、下列函数是双射的为（） ?N, f (n) = ；N；E , f (x) = 2x Bf : NAf : I ?N, f

4、(x) = | x | 。f :I I , f (x) = x ； DCf : R（注：I整数集，E偶数集， N自然数集，R实数集） 8、图中从v到v长度为3 的通路有（）条。 31 A 0； B 1； C 2； D 3。 9、下图中既不是Eular图，也不是Hamilton图的图是（） 10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（）个4度结点。 A1； B2； C3； D4 。 三、证明 26% 、R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当 和在R中有在R中。（8分） 、f和g都是群到的同态映射，证明是的一个子112, 3 / 19 x|x?G且f(

5、x)?g(x) (8分群。其中C=) 1?3k）条边围成的连通平面是每一个面至少由k（(|V| = v，|E|=e ) 、G= k(v?2)?e k?2，由此证明彼得森图（Peterson图，则）图是非平面图。（11 分） 16% 四、逻辑推演用CP规则证明下题（每小题 8分） A?B?C?D,D?E?F?A?F 1、?x(P(x)?Q(x)?xP(x)?xQ(x) 2、 五、计算 18% 1、设集合A=a，b，c，d上的关系R= , , , 用矩阵运算求出R的传递闭包t (R)。（9分） v,v,?,v及预先算出它们之间的一些直接、如下图所示的赋权图表示某七个城市2721通信线路造价，试给出

6、一个设计方案，使得各城市之间能够通信而且总造价最小。 （分） 试卷一答案： 一、填空 20% （每小题2分） (B?C)?A；3、1； 4、，1、01，23，46； 2、(?P?S?R)?(?P?S?R)； 5、1；6、, , , ；7、? I；8, 、 A 4 / 19 。 ；10、c9、a ；a , b , c ,d ；a , d , c , d 2分）二、选择 20% （每小题 题目1 2 3 4 5 6 7 8 9 10 答案C D C B、C A D C A D B A 26% 三、证明 证：1、?a,b,c?X, ? R?由R对称“性”知若,c,a? ? R ? R ，由R传递性得

7、 ? R ? R ? Ra,b?X?，任意“若”有因 ? R ? R? ? R所以若R是对称的。 ? R ? R ? R ? R ?b,c?R?则，即R若是传递的。 ?a,b?Cf(a)?g(a),f(b)?g(b)，2、 证又，有?1?1?1?1?1?1?1?1)g(b(bb)?f?(f(bb)?f),(b)g(b?g)?g(b)?f ?1?1?1?1ag()?)?g(a*gb(f)?(a)*fb(b)ba?f( ?1a?Cb? 是 的子群。 13、 证： r2e?rkF)2e?d(?ri v?e?r?2k故有设Gr个面而，即。，则1i?2ek(v?2)e?e?2?ve?rv kk?2。（8

8、即得分） k(v?2)?e k?5,e?15,v?102k?，这样 不成立，彼得森图为 5 / 19 所以彼得森图非平面图。（3分） 二、 逻辑推演 16% 1、 证明： A P（附加前提） B?AI TDC?A?B? PDC? ITDI T E?DI TF?D?E P FI T F?ACP 、证明2)?xxP( P（附加前提） )(cP US)xQ)?(?xPx P)P(Q(c?c) US )Q(cI T )xQ?(x UG )(xQ?)x(?xP?x CP 18% 三、计算 1、 解：6 / 19 01001010?01101010?MMMM?RRR2R00001000?00000000?

9、 ，0101?1001?M?MM?R23RR0000?0000?，0110?0011?M?M?M?R34RR0000?0000?1111?1111?MM?MM?M?R(R)t423RRR1000?0000? ?t (R)= , , , , , , , , ）算法求产生的最优树。算法略。结果如图： 解：用库斯克（Kruskal2、 即为总造价。树权C(T)=23+1+4+9+3+17=57 试卷二试卷与答案 分）（每小题一、填空 20% 2 Q：你失败。“除非你努力，否则你将失败”的翻译为：你努力，1、 P ；“虽然你努力了，但还是失败了”的翻译为 。P 2D=12、论域，指定谓词7 / 19

10、P (2,2) P (2,1) P (1,1) P (1,2) F T T F )x(y,?x?yP 则公式真值为。 所表达的子集是的子集，则由B，B是S、2 设S=a，a，a311 i82 。是质数?xx?y?x,y|R上的二元关系，则R= 3、 设A=2，6，3，45， （列举法）。= 的关系矩阵MRR 。上既是对称的A上既不是对称的又不是反对称的关系R= ；，2，3，则A5、设A=1 。又是反对称的关系R= c, ，b，*，其中A=a、设代数系统6A a b c * a b c a b b c b c c b c 则幺元是；是否有幂等性；是否有对称性。 4阶群必是群或群。7、 8、下面偏

11、序格是分配格的是。 K的边数为，欧拉图的充要条件是9、n个结点的无向完全图n 。R?)P?Q?()?(P(PQ? 10、公式的根树表示为 。8 / 19 分） 20% （每小题2二、选择 、在下述公式中是重言式为（）1)P(Q?P?Q)?P?Q)(P?Q)?(P?Q)?( B；A；)QP?QP?(?(P?Q) 。； DC)PQ?Q)?(?(?P?中极小项的个数为（），成真赋值的个数为、命题公式2 （）。 。3 2； DA0； B1； C,21,1S?,S2 有（）个元素。3、设，则 8 。7； D； B6； CA33 2, S? 1, SS? ，定义设上的等价关系4、 c?b?S,a?d,?S

12、?S?c,d?S?R?a,b?,c,d? | a,b产生的 R则由S?S 上一个划分共有（）个分块。 。9 6； D5A4； B； C3 2, S?1, R的关系图为5、设，S上关系 R具有（）性质。则 B反自反性、反对称性；A自反性、对称性、传递性； D自反性。C反自反性、反对称性、传递性；?,?,?S?, 6、设为普通加法和乘法，则（）是域。S?x|x?2n,a,b?Z3?S?x|xa?b,?Qa,b A Bn?1n?|S?xx2?,ZS?x|x?Z?x?0= N 。 C D7、下面偏序集（）能构成格。 9 / 19 8、在如下的有向图中，从V到V长度为3 的道路有（）条。 41 A1；

13、B2； C3； D4 。 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分） A2?g:BBf:A?B?b有的函数，定义一个函数对任意是从A3、 若到Bg(b)?x|(x?A)?(f(x)?b)，证明：若f是A到B的满射，则

14、g是从B到A2的单射。（10分） 4、 若无向图G中只有两个奇数度结点，则这两个结点一定连通。（8分） 1(n?1)(n?2m?)?2 2，则G设、5 个结点的无向简单图，其边数n是具有G是10 / 19 分）Hamilton图（8 14% 四、计算，42，3，Z+是模6加法，=0 ，1，1、 设是一个群，这里6666 分）,+的所有子群及其相应左陪集。（75，试求出Z66 781，100构造一棵最优二叉树。（25，36，49，64，2、 权数1，49，16， 分） 试卷二答案： 20%（每小题2分）一、 填空a,aa,a,a,?BB?QP?QP?、42、1、T 3；、831500011111

15、467R=,R=, 5；、 B 9 7、Klein四元群；循环群 8、 R=, 6、a ；否；有 1)?(1nn2 10 、；图中无奇度结点且连通 分） 20%（每小题 二、 2选择10 9 7 8 3 1 2 4 5 6 题目B B D A B D B C D B、D 答案 B、D； 三、 证明 46% 1、（9分） （1） S自反的 ?(?a,a?R)?(?a,a?R)?a,a?SA?a 自反，R，由，（2） S对称的 11 / 19 ?a,b?A?a,b?S?(?a,c?R)?(?c,b?R)S定义?R对称,b?R)a?,c?R)?(?c?(?R?S传递?b,a? 传递的） S（3?a,

16、b,c?A?a,b?S?b,c?S?(?a,d?R)?(?d,b?R)?(?b,e?R)?(?e,c?R)?(?a,b?R)?(?b,c?R)R传递?S定义,c?S?a? 由（1）、（2）、（3）得；S是等价关系。 2、11分 证明：设P(x)：x 是个舞蹈者； Q(x) ：x很有风度； S(x)：x是个学生； a：王华 上述句子符号化为： ?x(P(x)?Q(x)S(a)?P(a)?x(S(x)?Q(x)、3分结论：前提： S(a)?P(a) P )Q(xx(P(x)?P )a(a)?Q(PUS )aP(T I ).Q(aT I )S(aT I )(a)?QaS(TI )?x(S(x)Q(x

17、EG 11分 、0分?b,b?B,(b?b)?f满射?a,a?A 证明：212211使f(a)?b,f(a)?b,且f(a)?f(a),由于f是函数,?a?a 21212121又g(b)?x|(x?A)?(f(x)?b),g(b)?x|(x?A)?(f(x)?b)2121?a?g(b),a?g(b)但a?g(b),a?g(b)?g(b)?g(b) 2221112112为单射g任意性知,b由b, 。214、8分 证明：设G中两奇数度结点分别为u 和v，若 u，v不连通，则G至少有两个连通分支G、G，使得u和v分别属于G和G，于是G和G中各含有1个奇数度结22 2111点，这与图论基本定理矛盾，因

18、而u，v一定连通。 5、8分 证明：证G中任何两结点之和不小于n。 V?u,v1n?dd(u)?(v)?，则G-，反证法：若存在两结点uv 不相邻且,令11(n?1)(n?2)?2?m?(n?1) 2,可得是具有Vn-2个结点的简单图，它的边数11(n?2)(nm?3)?1 2，这与G=G-V为n-2个结点为简单图的题设矛盾，因而G11中任何两个相邻的结点度数和不少于n。 12 / 19 所以G为Hamilton图. 计算 14% 四、 1、 7分 解：子群有； 666660的左陪集：0，1；2，3；4，5 0，3的左陪集：0，3；1，4；2，5 0，2，4的左陪集：0，2，4；1，3，5 Z

19、的左陪集：Z。 6 6 分7 2、 试卷三试卷与答案 2分） 填空 20% （每空一、f(x)?x?1,g(,?x?Nx)?2x， N上的函数g 1、设 f，是自然数集?(x)gf? 则。2、 设A=a，b，c，A上二元关系R= , , , 则s（R）= 。 T?x,y?|x?y是素数上二元关系A65432A=1、，则用列举3 ，法 T= ； T的关系图为 ； T具有性质。 13 / 19 A?,2,2A2 = 的幂集4、 集合。wff(P?(R?S)?(P?Q)?(R?S)的；R，1。则S真值为5、 P，Q真值为0 真值为。 wff?(P?Q)?R)?R的主合取范式为。 6、 7、 设 P（

20、x）：x是素数， E(x)：x 是偶数，O(x)：x是奇数 N (x,y)：x可以整数y。wff?x(P(x)?y(O(y)?N(y,x)的自然语言是则谓词 。),uuQ(x,y?x,z)P(y,z)?zwff?x?y(?(P( 谓词8、 的前束范式为 。 分） 选择 20% （每小题 2二、 下述命题公式中，是重言式的为（）。1、 )q?pq)?(p?q)?()(p?q?(p?q)p? B；A、；q()?qp?p)?(?p?q 。 D；C、?wff(p?q)?r的主析取范式中含极小项的个数为（）。 、 2A 、2； B、 3； C、5； D、0； E、 8 。 3、 给定推理 ?x(F(x)

21、?G(x) P )G(yF(y)?US )?xF(xP )F(yES )yG(T I )?xG(xUG ?x(F(x)?G(x)?xG(x) 推理过程中错在（）。 A、-。 B、-。 C、-。 D、-。 E、- 4、 设S=1，2，8，9，S=2，4，6，8，S=1，3，5，7，9，S=3，4，41235， X?S且X?S下，在条件=3S，5X与（）集合相等。 315A、 X=S或S； B、X=S或S； 55 2414 / 19 C、X=S，S或S； D、X与S，S中任何集合都不等。 521415、 设R和S是P上的关系，P是所有人的集合，R?x,y?|x,y?P?x是y的父亲S?x,y?|x

22、,y?P?x是y的母亲，?1?SR表示关系（）。则 ?x,y?|x,y?P?x是y的丈夫、； A?x,y?|x,y?P?x是y的孙子或孙女、B； ?x,y?|x,y?P?x是y的祖父或祖母?、；、 D。 C6、 下面函数（）是单射而非满射。 2?2xx?1f?R,(x)?f:R； A、?f(x)?lnf:Z?R,x；B、 f(x)f:R?Z,?x,x表示不大于x的最大整数；C、 ff:(x)?2xR?R,?1。、 D+分别表示正实数与正整数集。 ，为整数集，R为实数集，ZRZ其中7、 设S=1，2，3，R为S上的关系，其关系图为 则R具有（）的性质。 A、 自反、对称、传递； B、什么性质也没

23、有； C、反自反、反对称、传递； D、自反、对称、反对称、传递。 S?,1,1,2?S。 ，则有（）8、 设A、1,2 ；B、1,2 ； C、1 ； D、2 。 9、 设A=1 ,2 ,3 ，则A上有（）个二元关系。 32322322 3； D、； C、。；A、2 B、 10、全体小项合取式为（）。 ，BC 都有可能。、矛盾式；A、可满足式； B C、永真式； DA， 分）规则证明三、 用CP 16% （每小题 8?EDDCBA?,?A?FF 1、15 / 19 ?x(P(x)?Q(x)?xP(x)?xQ(x) 2、四、（14%） 集合X=, , , ，R=,|x+yx+y 。 12 = 12

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

25、?,?6,2?,?6,3?； 、4 2,?,2?,?,2,2 ；、1；反对称性、反自反性；4、5)?RP?Q?P?Q?R)(P(?Q?R)?是素数，如果x7、任意x；6、8除x ；是奇数且y整存则在一个y，y)u,x,yz(y,)?Q(PzP?xy?zu(?(x,)? 。 分）（每小题 2 20%六、 选择 9 8 6 4 2 1 3 5 7 10 题目C A B C C C C A D D 答案 ) 七、 16%(证明 每小题8分16 / 19 1、 A P（附加前提） BA?TI D?B?CA?P D?CT I DT I ED?T I FE?D?P FT I FA?CP 2、?xP(x)?

26、xQ(x)?(?x)P(x)?xQ(x)?本题可证?x(P(x)?Q(x)?(?xP(x)?xQ(x) ?(?xP(x) P（附加前提） )P(x?x(TE )(a?PES )(x(?xP(x)?QP )?P(a)Q(aUS )Q(aTI )(x?xQEG )(?(?xPx)?xQ(xCP 14%八、 ）（1 证明：yx?由于yx,?X,x?y? 1、自反性：?x,y?,?x,y?R?R自反 ?x,y?X,?x,y?X 、 对称性：22121当?x,y?,?x,y?R时即x?y?x?y也即x?y?x?y 221112222111故?x,y?,?x,y?R?R有对称性 122117 / 19 ?x,y?X,?x,y?X?x,y?X