四川大学离散期末考试题及答案

注：试题字迹务必清晰，书写工整。本题6页，本页为第1页教务处试题编号：四川大学期末考试试题（闭卷）（2007-2008学年第1学期）课程号：30485040、31100340课程名称：离散数学（A卷）任课教师：适用专业年级：2006级计算机科学与技术、软件工程学号：姓名：考试须知四川大学学生参加由学校组织或由学校承办的各级各类考试，必须严格执行《四川大学考试工作管理办法》和《四川大学考场规则》。有考试违纪作弊行为的，一律按照《四川大学学生考试违纪作弊处罚条例》进行处理。四川大学各级各类考试的监考人员，必须严格执行《四川大学考试工作管理办法》、《四川大学考场规则》和《四川大学监考人员职责》。有违反学校有关规定的，严格按照《四川大学教学事故认定及处理办法》进行处理。题号一二三四五卷面成绩得分阅卷教师阅卷时间一、单项选择题（本大题共15小题，每小题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分1、下列公式中，（）不是永真式。①（P∧Q）→Q②P→（P∨Q）③（P→Q）（～Q→～P）④（～P∨Q）∧（～（～P∧～Q））2、下列谓词公式中是前束范式的是（）①)()()()(xGxxFx②)()()()(yGyxFx③)),()()()((yxQxPyx④)),()()()((yxQyxPx3、对任意集合A、B、C，下列命题中为真的是（）。①若AB且B∈C，则A∈C②若AB且B∈C，则AC③若A∈B且BC，则A∈C④若AB且B∈C，则AC4、设R、S都是集合A上的二元关系，下列命题中（）不真。①若R、S都是自反的，则R∪S是自反的②若R、S都是反自反的，则R∪S是反自反的③若R、S都是对称的，则R∪S是对称的④若R、S都是传递的，则R∪S是传递的5、设R1、R2都是集合A上的等价关系，下列关系中是A上的等价关系的是（）。①（A×A）-R1②R1∩R2③r（R1-R2）④R1-R26、设集合A={1，2，3，4}，下列A上的关系构成A到A的映射的是（）。①f1={(2,1),(2,4),(3,4),(4,1)}②f2={(4,4),(3,1),(1,2),(4,2)}③f3={(1,1),(2,1),(1,2),(3,4)}④f4={(1,4),(2,1),(3,4),(4,1)}课程名称：任课教师：学号：姓名：本题7页，本页为第2页教务处试题编号：7、设集合A={1，2，3，4，6，9}，则下列子集族中构成A的一个划分的是（）。①{{1}，{3，4}，{9，6}}②{{1，2，3}，{3}，{4，9，6}}③{{1，2}，{3}，{4，9，6}}④{{1，2}，{2，3}，{6，9}}8、下列集合关于数的加法运算封闭的是（）。①A={-1，1，3}②B={x|x是奇数}③C={a+b2|a,b∈Z}④D={x|x是复数且|x|=1}9、设Z，Q，R分别是整数集，有理数集，实数集，下列代数系统中，不构成环的是（）。（其中+，-，×是普通数的加法，减法、乘法）①（Z，+，×）②（Z，-，×）③（Q，+，×）④（R，+，×）10、设G是六阶群，则其元素的阶不能是（）。①1②2③3④411、实数集R的下列运算不满足交换律的是（）。①ba=|a-b|②ba=(a+b)/2③ba=a+2b④ba=22ba12、下列环中是域的是（）。（其中S是全体偶数的集合）①（Z，+，×）②,,(6z.)③,,(3z.)④（S，+，×）13、设有代数系统),(R，其中R为非零实数，×是普通乘法，则下列映射中（）不是自同态。①xxf)(②1)(xxf③2)(xxf④xxf1)(14、3,3k图是（）。①欧拉图②哈密顿图③平面图④完全图15、12阶循环群有（）个不同的子群。①3②6③9④12二、多项选择题（本大题共5小题，每小题2分，共10分）在每小题列出的五个备选项中有二个至五个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选、少选或未选均无分。1、下列语句中，是命题的有（）。1).美国的首都是纽约。2).你喜欢日本吗？3).我们一定要解放台湾！4).所有实数都是整数。5).如果3＞2，那么有人不死。2、设A＝{1,2,3}，则右图所示A上的关系具有（）。1).自反性2).反自反性3).对称性4).反对称性5).传递性312课程名称：任课教师：学号：姓名：本题7页，本页为第3页教务处试题编号：3、右图所示的图一定不是（）。1).平面图2).二部图3).欧拉图4).哈密而顿图5).树4、设G是一个35阶群，a∈G，则a的周期不可能是（）。1).12).23).34).45).55、下列哈斯图中，是格的有（）。1).2).3).4).5).三、简答题（本大题共4小题，每小题2.5分，共10分）1、试述命题的定义。2、设f是一个函数，试述f是单射的定义。3、试述一个简单有向图G的邻接矩阵的定义。4、试述两个代数系统,A和,B是同构的定义。课程名称：任课教师：学号：姓名：本题7页，本页为第4页教务处试题编号：四、演算题（本大题共5小题，每小题7分，共35分）1、求公式)())((PQPRP的主合取范式及主析取范式。2、设集合A＝{a，b，c}，A上的关系1R＝{a，a，a，b，a，c，b，b，b，c，c，c}，2R＝{a，a，a，b，b，a，b，b，c，c}。计算)(),(),(,,,111112121RtRsRrRRRRR。3、设简单有向图G有21条边，三个4度结点，其余结点的度都是3，计算G有多少个结点？（写出求解过程）课程名称：任课教师：学号：姓名：本题7页，本页为第5页教务处试题编号：4、剩余类加群,6Z有子群],4[],2[],0[，计算该子群的所有左、右陪集。5、下图为一连通赋权图，计算该图的最小生成树和权值。五、推理与证明题（本大题共3小题，每题10分，共30分）1、试符号化下列语句，并用演绎法证明其论证是否正确？每个自然数不是奇数就是偶数；一个自然数当且仅当它能被2整除时，它才是偶数；8是自然数且8能被2整除。因此8不是奇数。课程名称：任课教师：学号：姓名：本题7页，本页为第6页教务处试题编号：2、设B是数的集合，A＝B×B，定义A上的关系R如下：(u,v)R(x,y)当且仅当u-v=x-y，证明R是A上的一个等价关系。3、给定代数系统,,I，且和定义为：bababababa;1。其中，I是整数集合，,,分别是通常数的加法、减法和乘法，Iba,，证明,,I是具有幺元的可交换环。选择题答案：433424332433222多选(1)1,4,5(2)2,4,5(3)1,2,3,5(4)2,3,4(5)3,4简答题1.能明确判断是与否的陈述句2.对于定义域中的任意a,b,如果a不等于b,那么f(a)不等于f(b)3.设此图的阶为n,那么其邻接矩阵为一个n*n的矩阵,对于矩阵中的元素a(i,j),如果有想图中有一条边从i到j,则a(i,j)=1;否则a(i,j)=0.4.如果存在一个双射函数f,满足对任意a,b属于A,有f(a*b)=f(a)of(b);那么两个代数系统同构计算题或用|表示,与用&表示,非用!表示1.主析取式(Q&P&Q)|(Q&P&!R)|(!Q&!P&R)|(!Q&!P&!R)主合取式(Q|!P|R)&(Q|!P|!R)&(!Q|P|R)&(!Q|P|!R)2.略:)课程名称：任课教师：学号：姓名：本题7页，本页为第7页教务处试题编号：3.设有n个节点,则根据握手定理,列出如下方程21*2=3*4+(n-3)*3n=134.左右配集一共有2种{[0],[2],[4]}{[1],[3],[5]}5.略:)请自行翻书查看最小生成树算法证明题:1.略:)2.(思路为分别证明R的自反,对称,传递性)证明自反性:对于任意的(a,b)属于A,明显满足a-b=a-b,所以有(a,b)R(a,b)自反性成立证明对称性:对于任意的(a,b),(x,y)属于A,如果(a,b)R(x,y)那么a-b=x-y,那么x-y=a-b,则有(x,y)R(a,b)对称性成立证明传递性:对于任意的(a,b)(c,d)(e,f)属于A,如果有(a,b)R(c,d),(c,d)R(e,f)那么有a-b=c-d=e-f,则一定有(a,b)R(e,f)传递性成立综上,R为A上等价关系3.(思路为分别证明I,*为交换群,I-θ,o为含幺可换半群)证明I,*为交换群封闭性显然成立结合性,a*b*c=a*(b*c),结合性成立含幺性,a*1=a,故含有幺元1,含幺性成立可逆性,a*(2-a)=1,故对任意a有逆元(2-a),可逆性成立可交换,a*b=b*a,可换性成立证明I-θ,o为含幺可换半群由上面证明知,θ=1封闭性首先对任意整数a,b(a,b不等于1),一定有aｏb依旧为整数现在我们证明aｏb不会等于1对任意的a,b,如果有aｏb等于1那么a+b-axb=1,则ax(1-b)=1-b上式的解只有a等于1,或者b等于1,与a,b定义矛盾.综上,封闭性成立.结合性,经过计算,成立含幺性,aｏ0=a,故有幺元0可交换,经过计算,成立综上,证毕