文档介绍：Forpersonaluseonlyinstudyandresearch;mercialuse肃一、填空20%蚁P:你努力,Q:你失败。“除非你努力,否则你将失败”的翻译为肆;“虽然你努力了,但还是失败了”的翻译为莅。螄2、论域D={1,2},指定谓词P莀P(1,1)膆P(1,2)螅P(2,1)膂P(2,2)膈T芆T膆F羄F膁则公式真值为。莆设S={a1,a2,…,a8},Bi是S的子集,则由B31所表达的子集是芃。莂设A={2,3,4,5,6}上的二元关系,则R= 羀(列举法)。蒅R的关系矩阵MR=蚄肄。蝿5、设A={1,2,3},则A上既不是对称的又不是反对称的关系R=;A上既是对称的又是反对称的关系R=。蝿*b罿6、设代数系统<A,*>,其中A={a,b,c},袇螂莀聿则幺元是;是否有幂等性;是否有对称性。肄7、4阶群必是群或群。蒃8、下面偏序格是分配格的是。聿腿9、n个结点的无向完全图Kn的边数为,欧拉图的充要条件是蒄。袁10、公式的根树表示为膁艿袅薃。袀二、选择20%(每小题2分)荿1、在下述公式中是重言式为()芆A.;B.;肁C.;D.。虿2、命题公式中极小项的个数为(),成真赋值的个数为()。;;;。莃3、设,则有()个元素。;;;。蒈设,定义上的等价关系蒈则由R产生的上一个划分共有()个分块。;;;。芁5、设,S上关系R的关系图为蒁薈则R具有()性质。、对称性、传递性;、反对称性;、反对称性、传递性;。芀6、设为普通加法和乘法,则()是域。.=N。莁7、下面偏序集()能构成格。罿螈8、在如下的有向图中,从V1到V4长度为3的道路有()条。;;;。肈9、在如下各图中()欧拉图。袄10、设R是实数集合,“”为普通乘法,则代数系统<R,×>是()。;;。袁三、证明46%袇设R是A上一个二元关系,羄试证明若R是A上一个等价关系,则S也是A上的一个等价关系。(9分)薁莈用逻辑推理证明:蚆所有的舞蹈者都很有风度,王华是个学生且是个舞蹈者。因此有些学生很有风度。(11分)肄羁若是从A到B的函数,定义一个函数对任意有,证明:若f是A到B的满射,则g是从B到的单射。(10分)肀莄若无向图G中只有两个奇数度结点,则这两个结点一定连通。(8分)膄莂设G是具有n个结点的无向简单图,其边数,则G是Hamilton图(8分)薈四、计算14%蒇设<Z6,+6>是一个群,这里+6是模6加法,Z6={[0],[1],[2],[3],[4],[5]},试求出<Z6,+6>的所有子群及其相应左陪集。(7分)芄蕿权数1,4,9,16,25,36,49,64,81,100构造一棵最优二叉树。(7分)芀膆莄羀蚈填空20%(每小题2分)羅1、;2、T3、4、R={<2,2>,<2,3>,<2,4>,<2,5>,<2,6>,<3,2>,<3,3>,<3,4>,<3,5>,<3,6>,<4,5>,<4,6>,<5,2>,<5,3>,<5,4>,<5,5>,<5,6>};5、R={<1,2>,<1,3>,<2,1>};R={<1,1>,<2,2>,<3,3>}6、a;否;有7、Klein四元群;循环群8、B9、;图中无奇度结点且连通10、莃莁蒀选择20%(每小题2分)羈题目蒃1螂2袈3螇4薃5膃6薀7薆8蚃9芀10肇答案莅B、D螃D;D蚀D蝿B莇D袃A肁B膇B膆B羃B、C蒂罿证明46%袅1、(9分)羂S自反的袃,由R自反,,莇S对称的羈肂S传递的肀聿由(1)、(2)、(3)得;S是等价关系。2、11分证明:设P(x):x是个舞蹈者;Q(x):x很有风度;S(x):x是个学生;a:王华上述句子符号化为:前提:、结论:……3分① P② P③ US②④ T①I⑤ T③④I⑥ T①I⑦ T⑤⑥I⑧ EG⑦……11分3、10分证明:。4、8分证明:设G中两奇数度结点分别为u和v,若u,v不连通,则G至少有两个连通分支G1、G2,使得u和v分别属于G1和G2,于是G1和G2中各含有1个奇数度结点,这与图论基本定理矛盾,因而u,v一定连通。5、8分证明:证G中任何两结点之和不小于n。反证法:若存在两结点u,v不相邻且,令,则G-V1是具有n-2个结点的简单图,它的边数,可得,这与G1=G-V1为n-2个结点为简单图的题设矛盾,因而G中任何两个相邻的结点度数和不少于n。%7分解:子群有<{[0]},+6>;<{[0],[3]},+6>;<{[0],[2],[4]},+6>;<{Z6},+6>{[0]}的左陪集:{[0]},{[1]};{[2]},{