11离散数学b卷

上海海洋大学试卷

学年学期 课程名称 课程号 题号 分数 阅卷人

姓名： 学号： 专业班名：

一 1108101 二 三 四 20 11 ~ 20 12学年第 1 学期 离散数学A 学分 五 六 3 七 考核方式 A/B卷 学时 八 九 闭卷 （ B ）卷 48 十 总分 一、选择填空题（每空3分，共30分） 1、下列公式中，哪个是永真式（ ）

A (p?q)?(q?p) B ?(p?q) C (p?q)?p D (?p?q)??(?p?q) 2、命题公式(p??q)?(?p??q)的成假赋值为 ，主析取范式为 。 3、将命题“有的人用左手写字”谓词符号化

4、公式?xP(x)??yQ(y)的前束范式为 5、设集合A={1,2,4,5,6}，B={1，3，4，7，9} ,则A?B? 。 6、集合A?{1,2,3,4,5,6,7,8,9,10}上的关系R?{?x,y?|x?y?10,x,y?A}，则R的性质为（ ）

A.自反的 B. 对称的 C.对称的、传递的 D.反自反的、传递的 7、设A={1,2,3},B={a,b},则从A到B能构成 个不同的函数。 8、6阶无向完全图K6的边的条数 。

9、设无向树有2个2度顶点，1个3度顶点，3个4度结点，其余都是树叶，则其有 片树叶。

第1页，共4页

二、（8分）求公式(p?q)?(q?r)的主析取范式和主合取范式。

三、（8分）在自然推理系统中，构造并证明下列推理。（命题逻辑推理证明） 如果小王是理科生，则他的数学成绩一定很好。如果小王不是文科生，则他一定是理科生。小王的数学成绩不好。所以，小王是文科生。

四、设集合A?{1,2,3,4}，R为A上的二元关系，且R?{(1,2),(2,3),(2,1),(3,4)}， （1）求R的关系矩阵；（3分） （2）求R的性质；（3分）

（3）求R的自反闭包r（R），对称闭包s（R），传递闭包t（R）（9分） 。

第2页，共4页

五、（10分）设集合A?{1,2,3,4,5,6,7,8,9}， R为A上的整除关系，则R为偏序关系。（1）求该关系的哈斯图； （2）令B?{2,3,6}，求B的最大元、最小元、极大元、极小元。

六、（6分）设集合A?{1,2,3,4},R为A上的等价关系，

R?{?1,2?,?2,1?,?1,3?,?3,1?,?2,3?,?3,2?,?3,3?,?1,1?,?2,2?}

（1）求商集A/R；

（2）求自然映射g:A?A/R。

七、（8分）写出哈密顿图的定义，并画一个哈密顿图。（图中至少含有5个结点，2条回路）

第3页，共4页

八、（9分）已知无向赋权图G=,

v 2 v 3 （1）该图是否为欧

6 拉图，如果不是，3 3 2 请说明理由，如果v6 4 是，请给出一条欧v7 6 2 拉回路； v1 8 （2）求从v1到v7的3 最短路径。 v 4 v

52 1 8

九、（6分）画一棵权为3，4，5，6，7，8，9的最优二元树T，并求T对应的二元前缀码。

第4页，共4页