11离散数学a卷.docVIP

上海海洋大学试卷 学年学期 20 11 ~ 20 12学年第 1 学期 考核方式 闭卷 课程名称 离散数学A A/B卷 （ A ）卷 课程号 1108101 学分 3 学时 48 题号 一 二 三 四 五 六 七 八 九 十 总分 分数 阅卷人 姓名： 学号： 专业班名： 一、选择填空题（每空3分，共45分） 1、下列句子中有（ ）个是命题。 （1）我是老师。（2）禁止吸烟! (3) 蚊子是鸟类动物。（4）我在说谎。 （5）月亮比地球大。 A. 1 B . 2 C. 3 D. 4 2、下列公式中，哪个是永真式（ ） A B C D 3、命题公式的成真赋值为 ，主合取范式为 。 4、将命题“没有一个运动员不是强壮的”谓词符号化为 5、公式的前束范式为 6、下列命题中为假命题的是( )（其中P（A）为A的幂集） A． B. C. D. 7、设集合A=，B=[2,4) ,则 。 8、设分别表示实数、整数和自然数集， 设函数，，（除以3所得的余数）， ，，， 则上述函数中是满射的有 。 9、设集合，请写出A上的一个关系R使其既具备对称性又具备反对称性 。 10、当n 时，无向完全图既是欧拉图又是哈密顿图。 11、右边的有向图的邻接矩阵为 12、设无向树有3个3度顶点，2个2度顶点，其余都是树叶，则其有 片树叶。 13、带权4，6，8，10，12的最优二元树T的权是 ，T对应的二元前缀码是 。 三、（8分）设计一盏电灯的开关电路，要求受3个开关A、B、C的控制：当且仅当A和C同时关闭或B和C同时关闭时灯亮。设p：开关A关闭，q：开关B关闭，r：开关C关闭，G表示灯亮。求G的主析取和主合取范式。 四、（8分）在自然推理系统中，构造并证明下列推理。（命题逻辑推理证明） 若小张喜欢数学，则小李或小赵也喜欢数学。若小李喜欢数学，则他也喜欢物理。小张确实喜欢数学，但小李不喜欢物理。所以，小赵喜欢数学。 五、设集合，R为A上的二元关系，且， （1）求R的关系矩阵；（3分） （2）求R的性质；（3分） （3）求R的传递闭包t（R）；（4分） （4）设，求；（4分） （5）在关系R中添加最少的有序对使其成为A上的等价关系，不妨令该等价关系为，求及商集。（4分） 六、（10分）设集合， R为A上的整除关系，则R为偏序关系。（1）求该关系的哈斯图； （2）令，求B的最大元、最小元、极大元、极小元、上界和下界。 八、（5分）已知七人中，会讲的语言分别为： 英语、德语，英语、汉语，英语、意大利语、俄语，汉语、日语， 意大利语、德语，俄语、日语、法语，德语、法语 问能否将他们的座位安排在圆桌旁，使得每个人都能和身边的人交谈？ 九、（6分）已知无向赋权图G=V,E,W, （1）该图是否为欧拉图，如果不是， 最少添加几条边可以将其变为欧拉图？ 请在上图中画出。 （2）求该图的最小生成树。 ， 第4页，共4页