08级离散A卷
- 格式：doc
- 大小：284.00 KB
- 文档页数：6
A卷第 1 页 共 6 页 长江大学试卷 学院 班级 学号 姓名
…………….…………………………….密………………………………………封………………..…………………..线……………………………………..
2009─2010学年 第一学期
《离散数学》课程考试试卷( A卷)
注意：1、本试卷共6页； 2、考试时间:120分钟
3、姓名、学号必须写在指定地方 4、考试方式：闭卷
5、试卷适用班级：计科10801-10805、软工10801
一 判断题(每小题1分，共 15分，正确的在括号内写上T，错误的在括号内写上F)
1、 若图G是自对偶的，则e=2v-2 （ ）
2、 “离散数学是很有趣的一门课程”，这句话是命题。（ ）
3、 函数的复合既能交换也能结合。（ ）
4、 如果A∨CB∨C，则AB（ ）
5、 设G=
6、 )()(RQPQ是合式公式。（ ）
7、 任何阶数为4的群都是阿贝尔群。（ ）
8、 设G是简单连通图，且有v个结点，e条边，若G是平面图，则e3v-6。（ ）
9、 一个循环群的生成元是唯一的。（ ）
10、 有任意集合A、B，则f(A∩B)f(A)∩f(B)且f(A)∩f(B)f(A∩B)。（ ）
11、 )()()()())()()((xBxxAxxBxAx（ ）
12、 对任意集合A，B，C，如果A∈B以及BC，则AC。（ ）
13、 整数集上的同余类是对整数集的一个划分。（ ）
14、 有限半群中存在等幂元。（ ）
15、 设
题号 一 二 三 四 五 六 七 八 总分
得分
阅卷人 得分
A卷第 2 页 共 6 页
二 、选择题(每小题2分，共 22分)
1、 一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，则该树有（ ）片树叶。
A.6 B. 7 C. 8 D.9
2、图1中v1到v4 长度为2的路有（ ）条
A. 1 B. 2 C. 3 D.4
v2v4v3v1
图1
3、设A={1，2，3，4}，B={a，b，c，d}，f定义为：{<1,a>,<2,b>,<3,c>,<4,d>}，则f（ ）。
A.不是函数 B.仅为入射函数 C.仅为满射函数 D.是双射函数
4、设F(x)：x是乌鸦；G(x,y)：x与y一般黑，则“天下乌鸦一般黑”可以符号化为：( )
A.)),()()()()((yxGyFxFyx
B.)),()()()()((yxGyFxFyx
C.)),()()()()((yxGyFxFyx
D.)),()()()()((yxGyFxFyx
5、给定下列谓词公式，则是矛盾式的公式为（ ）
A.))()()((xPxPx
B. )()()()(xPxxPx
C.)()())()(()()((yQyyQyxPx
D.),())((),())((yxPyxyxPyx
6、设有下列四个集合，偏序关系为整除，则是全序关系的为（ ）
A. {3,5,15} B.{1,2,3,6,12}
C.{3,4,12} D.{3,9,27,54} 阅卷人 得分
A卷第 3 页 共 6 页 7、设集合P={x1，x2，x3，x4，x5}上的偏序关系如图2所示，则下列说法中正确的是（ ）
A、P的最大元素为x1 ，无最小元素，极小元素为x4，x5 ，极大元为素x1
B、P无最大元素，也无最小元素，极小元素为x4，x5 ，极大元为素x1
C、P的最大元素为x1 ，无最小元素，也无极小元素 ，极大元为素x1
D、P的最大元素为x1 ，最小元素为x4，x5，极小元素为x4，x5 ，极大元为素x1
x1x4x5x3x2
图2
8、集合A={a，b，c}，A上的关系R={（a，b），（a，c），（b，a），（b，c），（c，a），（c，b），（c，c）}，则R具有关系的（ ）性质。
A、自反性 B、对称性 C、反对称性 D、传递性
9、下面给出的一阶逻辑等价式中，（ ）是错的。
)).(()(.));(()(.);()())()((.);()())()((.xBAxxxBADxAxxxACxxBxxAxBxAxBxxBxxAxBxAxA
10、一个公式在等价意义下，下面哪个写法是唯一的（ ）。
A．析取范式 B．合取范式 C．主析取范式 D．以上答案都不对
11、已知图G的相邻矩阵为 A(G) 则G有（ ）。
A. 5点，8边 B. 6点，7边 C. 5点，7边 D. 6点，8边
A(G)=
三 、填空题(每空2分，共 30分)
1、 n为 时，无向完全图Kn是欧拉图。n为 时，无向完全图Kn仅存在欧拉通路而不存在欧拉回路。 阅卷人 得分
A卷第 4 页 共 6 页 2、 如图2，则k(G)= λ(G)= δ(G)=
图2
3、 假设X和Y是有穷集合，则从X到Y存在入射的必要条件是
4、 设P表示命题“8是偶数”，Q表示命题“糖果是甜的”，则命题P→Q的反换式所表示的含义是
5、 （P∨Q）∧R的对偶式为
6、设P(x)表示x是聪明的，M(x)表示x是人，则命题“尽管有人聪明，但未必一切人都聪明”可以符号化为：
7、集合{a,{a}}的幂集为：
8、令R={<1,2>,<3,4>,<2,2>}和S={<4,2>,<2,5>,<3,1>,<1,3>}，
则SR
9、设A={a,b,c}，R是A上的二元关系，且给定R={
r(R)=
10、设I是整数集合，R是同余模3的关系，则I/R=
11、设谓词的定义域为},,{cba，将表达式))()((xQxPx中的量词消除，写成与之等价的命题公式是
12、设P(x)：x是素数；E(x)：x是偶数；O(x)：x是奇数；N(x，y)：x可以整除y。则))),()()(()()((xyNyOyxPx可以译成自然语言为：
四 、证明题(第1，2题各5分，第3题8分，共
18分)
1、证明：若X×Y=X×Z，且X不为空集，则Y=Z。
阅卷人 得分
A卷第 5 页 共 6 页 2、如果马会飞或羊吃草，则母鸡就会是飞鸟；如果母鸡是飞鸟，那么烤熟的鸭子还会跑；烤熟的鸭子不会跑。所以羊不吃草。符号化该命题，并用推理理论证明之。
3、设
a) 证明：对于任意的a,b,c∈A，如果a*b=a*c，则b=c。
b) 通过证明e是A中的幺元，证明
A卷第 6 页 共 6 页
五 、应用题(第1题5分，第2题10分，共15 分)
1、 双射函数是密码学中的重要工具，因为在密码体制中大都会同时涉及加密和解密，假设f是由表1定义的，即f(A)=D,f(B)=E,F(C)=S,…等，试找出给定密文“ARDJYLRXBMB”对应的明文。
表1
A B C D E F G H I J K L M
D E S T I N Y A B C F G H
续表1
N O P Q R S T U V W X Y Z
J K L M O P Q R U V W X Z
2、设有a,b,c,d,e,f,g七个人，他们分别会讲如下各种语言：a会讲英语；b会讲汉语与英语；c会讲英语、西班牙语和俄语；d会讲日语和汉语；e会讲德语和西班牙语；f会讲法语、日语和俄语；g会讲法语和德语。能否将这七个人的座位安排在圆桌旁，使得每个人均能与他身边的人交谈？
阅卷人 得分
