《四川大学离散期末考试题附标准答案》由会员分享，可在线阅读，更多相关《四川大学离散期末考试题附标准答案（8页珍藏版）》请在金锄头文库上搜索。
1、课程名称： 任课教师： 学号：姓名： 四川大学期末考试试题（闭卷）（2007-2008学年第1学期）课程号： 30485040、31100340 课程名称： 离散数学（A卷）任课教师：适用专业年级：2006级计算机科学与技术、软件工程 学号：姓名：考试须知四川大学学生参加由学校组织或由学校承办的各级各类考试，必须严格执行四川大学考试工作管理办法和四川大学考场规则。有考试违纪作弊行为的，一律按照四川大学学生考试违纪作弊处罚条例进行处理。四川大学各级各类考试的监考人员，必须严格执行四川大学考试工作管理办法、四川大学考场规则和四川大学监考人员职责。有违反学校有关规定的，严格按照四川大学教学事故认定及
2、处理办法进行处理。题 号一二三四五卷面成绩得 分阅卷教师阅卷时间一、单项选择题（本大题共15小题，每小题1分，共15分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分矚慫润厲钐瘗睞枥庑赖。1、下列公式中，（ ）不是永真式。（PQ）Q P（PQ） （PQ）（QP ） （PQ）（PQ）2、下列谓词公式中是前束范式的是（ ）3、对任意集合A、B、C，下列命题中为真的是（ ）。 若AB 且 BC，则AC 若AB 且 BC，则AC 若AB 且 BC，则AC 若AB 且 BC，则AC 4、设R、S 都是集合A上的二元关系，下列命题中（ ）不真。 若
3、R、S 都是自反的，则RS是自反的 若R、S 都是反自反的，则RS是反自反的 若R、S 都是对称的，则RS是对称的 若R、S 都是传递的，则RS是传递的5、设R1、R2都是集合A上的等价关系，下列关系中是A上的等价关系的是（ ）。 （AA）-R1 R1R2 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) 残
4、骛楼諍锩瀨濟溆塹籟。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+b|a,bZ D=x|x是复数且|x|=19、设Z，Q，R分别是整数集，有理数集，实数集，下列代数系统中，不构成环的是（ ）。 （其中+，-，是普通数的加法，减法、乘法） （Z，+，） （Z，-，） （Q，+，） （R，+，）酽锕极額閉镇桧猪訣锥。10、设G是六阶群，则其元素的阶不能是（ ）。 1 2 3 41
5、1、实数集R的下列运算不满足交换律的是（ ）。=|a-b| =(a+b)/2 =a+2b =12、下列环中是域的是（ ）。（其中S是全体偶数的集合） （Z，+，） .) .) （S，+，）13、设有代数系统，其中为非零实数，是普通乘法，则下列映射中（ ）不是自同态。14、图是（ ）。 欧拉图 哈密顿图 平面图 完全图15、12阶循环群有（ ）个不同的子群。 3 6 9 12二、多项选择题（本大题共5小题，每小题2分，共10分 ）在每小题列出的五个备选项中有二个至五个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选、少选或未选均无分。彈贸摄尔霁毙攬砖卤庑。1、 下列语句中，是命题的有（
6、 ）。 1).美国的首都是纽约。2).你喜欢日本吗？3). 我们一定要解放台湾！4).所有实数都是整数。5).如果32，那么有人不死。3122、 设A1,2,3，则右图所示A上的关系具有（ ）。謀荞抟箧飆鐸怼类蒋薔。1).自反性 2).反自反性 3).对称性4).反对称性 5).传递性3、 右图所示的图一定不是（ ）。1).平面图2).二部图3).欧拉图4).哈密而顿图5).树4、 设G是一个35阶群，aG，则a的周期不可能是（ ）。1).12).23).34).45).55、 下列哈斯图中，是格的有（ ）。1).2). 3).4). 5).三、简答题（本大题共4小题，每小题2.5分，共10分
7、）1、试述命题的定义。2、设f是一个函数，试述f是单射的定义。3、试述一个简单有向图G的邻接矩阵的定义。4、试述两个代数系统和是同构的定义。四、演算题（本大题共5小题，每小题7分，共35分 ）1、求公式 的主合取范式及主析取范式。2、设集合Aa，b，c，A上的关系， 。计算。3、设简单有向图G有21条边，三个4度结点，其余结点的度都是3，计算G有多少个结点？（写出求解过程）4、剩余类加群有子群，计算该子群的所有左、右陪集。5、 下图为一连通赋权图，计算该图的最小生成树和权值。五、推理与证明题（本大题共3小题，每题10分，共30分 ）1、试符号化下列语句，并用演绎法证明其论证是否正确？每个自然数
8、不是奇数就是偶数；一个自然数当且仅当它能被2整除时，它才是偶数；8是自然数且8能被2整除。因此8不是奇数。厦礴恳蹒骈時盡继價骚。 2、设B是数的集合，ABB，定义A上的关系R如下： (u,v)R(x,y)当且仅当u-v=x-y，证明R是A上的一个等价关系。茕桢广鳓鯡选块网羈泪。3、给定代数系统，且和定义为：。其中，I是整数集合，分别是通常数的加法、减法和乘法， 证明是具有幺元的可交换环。选择题答案：4 3 3 4 24 3 3 2 43 3 2 2 2多选(1)1,4,5 (2)2,4,5 (3)1,2,3,5 (4)2,3,4 (5)3,4鹅娅尽損鹌惨歷茏鴛賴。简答题1. 能明确判断是与否的
9、陈述句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. 略 :)3. 设有n个节点
10、,则根据握手定理,列出如下方程21*2 = 3*4+(n-3)*3n=134. 左右配集一共有2种 0,2,4 1,3,55. 略 :) 请自行翻书查看 最小生成树 算法证明题: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
11、(e,f)那么有a-b=c-d=e-f,则一定有(a,b)R(e,f)传递性成立综上,R为A上等价关系3. (思路为分别证明为交换群,为含幺可换半群)证明为交换群封闭性显然成立结合性,a*b*c=a*(b*c),结合性成立含幺性,a*1=a,故含有幺元1,含幺性成立可逆性,a*(2-a)=1,故对任意a有逆元(2-a),可逆性成立可交换,a*b=b*a,可换性成立证明为含幺可换半群由上面证明知,=1封闭性首先对任意整数a,b(a,b不等于1),一定有ab依旧为整数现在我们证明ab不会等于1对任意的a,b,如果有ab等于1那么a+b-axb = 1 ,则 ax(1-b)=1-b上式的解只有a等于1,或者b等于1,与a,b定义矛盾.综上,封闭性成立.结合性,经过计算,成立含幺性,a0=a,故有幺元0可交换,经过计算,成立综上,证毕本题8页，本页为第8页教务处试题编号：
