山东师范大学成人高等教育
《离散数学》书面作业
一、填空 （每空2分，共20分）
1、给定命题公式A 、B ，若 ，则称A 和B 是逻辑相等的。

2、命题公式)(Q P →⌝的主析取范式为 ，主合取范式用极大项表示为 。

3、设E 为全集， ，称为A 的绝对补，记作～A ，
且～（～A ）= ，～E = ，～Φ= 。

4、n 阶完全图结点v 的度数d(v) = 。

5、 设n 阶图G 中有m 条边，每个结点的度数不是k 就是k+1，若G 中有N k 个k 度顶点，N k+1个k+1度顶点，则N k = 。

二、选择 （每题4分，共20分）
1、设[{a , b , c}，*]为代数系统，*运算如下：
则零元为（ ）。

A 、a ；
B 、b ；
C 、c ；
D 、没有。

2、如右图 相对于完全图K 5的补图为（ ）。

3、一棵无向树T 有7片树叶，3个3度顶点，其余顶点均为4度。

则T 有（ ）4度结点。

A 、1；
B 、2；
C 、3；
D 、4。

4、设>=<E V G ,为无向图，23,7==E V ，则G 一定是（ ）。

A 、完全图；
B 、树；
C 、简单图；
D 、多重图。

5、给定无向图>=<E V G ,，如下图所示，下面哪个边集不是其边割集（ ）。

A 、},,,{4341><><v v v v ；
B 、},,,{6451><><v v v v ；
C 、},,,{8474><><v v v v ；
D 、},,,{3221><><v v v v 。

三、综合 （每题12分，共60分）
1、用等值演算法和真值表法判断公式)())()((Q P P Q Q P A ↔↔→∧→=的类型。

2、用推理规则证明：
C A F E F
D
E B D C B A →∧⌝∨⌝∧∨⌝→∧→,
)(,)()(,)()(├ A
3、 设A={1，2，3，4，5}，A 上的偏序关系为
求A 的子集{3，4，5}和{1，2，3}，的上界，下界，上确界和下确界。

4、有n 个药箱，若每两个药箱里有一种相同的药，而每种药恰好在两个药箱中，问共有多少种药品？
5、设有a 、b 、c 、d 、e 、f 、g 七个人，他们分别会讲的语言如下：a ：英，b ：汉、英，c ：英、西班牙、俄，d ：日、汉，e ：德、西班牙，f ：法、日、俄，g ：法、德，能否将这七个人的座位安排在圆桌旁，使得每个人均能与他旁边的人交谈？（8分）。