2007-2008学年第1学期期末考试试题(A卷)

（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、下列谓词公式中是前束范式的是（ ）

① (x)F(x)(x)G(x) ② (x)F(x)(y)G(y) ③ (x)(y)(P(x)Q(x,y)) ④ (x)(P(x)(y)Q(x,y)) 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C 4、设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-R2 6、设集合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)}

注：试题字迹务必清晰，书写工整。 本题6页，本页为第1页

教务处试题编号：

课程名称： 任课教师： 学号： 姓名：

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 ④ 4 11、实数集R的下列运算不满足交换律的是（ ）。

① ab=|a-b| ② ab=(a+b)/2 ③ ab=a+2b ④ ab=a2b2 12、下列环中是域的是（ ）。（其中S是全体偶数的集合）

① （Z，+，×） ② (z6,,.) ③ (z3,,.) ④ （S，+，×）

13、设有代数系统(R, )，其中R为非零实数，×是普通乘法，则下列映射中（ ）不是自同态。

① f(x)x ② f(x)x1 ③ f(x)x2 ④ f(x)114、k3,3图是（ ）。

① 欧拉图 ② 哈密顿图 ③ 平面图 ④ 完全图 15、12阶循环群有（ ）个不同的子群。

① 3 ② 6 ③ 9 ④ 12

二、多项选择题（本大题共5小题，每小题2分，共10分 ）在每小题列出的五个备选项中有二个至五个是符合题

目要求的，请将其代码填写在题后的括号内。错选、多选、少选或未选均无分。 1、 下列语句中，是命题的有（ ）。 1).美国的首都是纽约。

4).所有实数都是整数。

2).你喜欢日本吗？

3). 我们一定要！

x

5).如果3＞2，那么有人不死。

2、 设A＝{1,2,3}，则右图所示A上的关系具有（ ）。 1).自反性 2).反自反性

4).反对称性

3).对称性

1 2 3 5).传递性

本题6页，本页为第2页 教务处试题编号：

课程名称： 任课教师： 学号： 姓名：

3、 右图所示的图一定不是（ ）。 1).平面图

2).二部图

3).欧拉图

4).哈密而顿图 5).树

4、 设G是一个35阶群，a∈G，则a的周期不可能是（ ）。

1).1

2).2

3).3

4).4

5).5

5、 下列哈斯图中，是格的有（ ）。

1).

三、简答题（本大题共4小题，每小题2.5分，共10分） 1、试述命题的定义。

2、设f是一个函数，试述f是单射的定义。

3、试述一个简单有向图G的邻接矩阵的定义。

4、试述两个代数系统A, 和B, 是同构的定义。

2).

3).

4). 5).

本题6页，本页为第3页 教务处试题编号：

课程名称： 任课教师： 学号： 姓名：

四、演算题（本大题共5小题，每小题7分，共35分 ）

1、求公式(P(RP))(QP) 的主合取范式及主析取范式。

2、设集合A＝{a，b，c}，A上的关系

R1＝{，，，，，}， R2＝{，，，， }。

1计算R1R2,R1R2,R1,r(R1),s(R1),t(R1)。

3、设简单有向图G有21条边，三个4度结点，其余结点的度都是3，计算G有多少个结点？（写出求解过程）

本题6页，本页为第4页 教务处试题编号：

课程名称： 任课教师： 学号： 姓名：

4、剩余类加群 Z6,有子群[0],[2],[4],，计算该子群的所有左、右陪集。

5、 下图为一连通赋权图，计算该图的最小生成树和权值。

五、推理与证明题（本大题共3小题，每题10分，共30分 ）

1、试符号化下列语句，并用演绎法证明其论证是否正确？

每个自然数不是奇数就是偶数；一个自然数当且仅当它能被2整除时，它才是偶数；8是自然数且8能被2整除。因此8不是奇数。

本题6页，本页为第5页 教务处试题编号：

课程名称：

任课教师： 学号： 姓名：

2、设B是数的集合，A＝B×B，定义A上的关系R如下： (u,v)R(x,y)当且仅当u-v=x-y，证明R是A上的一

个等价关系。

3、给定代数系统I,  ,，且和定义为：abab1;ababab。

其中，I是整数集合，,,分别是通常数的加法、减法和乘法，a,bI，

证明I,  ,是具有幺元的可交换环。

本题6页，本页为第6页 教务处试题编号：