离散数学练习题及答案

=(A?～C)?(C?～C)?A?(A?C)

=(A?～C)???A=A

4、判断下列哪些运算结果是对的？哪些是错的？请将错误的运算结果更正过来．

(1) ??{?}?? (2) ??{?}?? (3) {?}?{?,{?}}?{?} (4) {?,{?}}?{?}?{?,{?}} （5）(A?B)?B?A （6）(A?B)?B?A

（7）A?A?A

（8）(A?B)?A??

4、(1) 对． (2) 错．应为{?}． (3) 对． (4) 错．应为{{?}}

（5）错．应为A?B （6）错．应为A?B(或A?~B或A－AB) （7）错．应为?，即A?A?A?A?A?A?? （8）对． 5、将命题公式?P?Q?(?R?P)化为只含?和?的尽可能简单的等值式． 5、?P?Q?(?R?P)

??(P??Q)?(R?P)（优先级有误） ??(P??Q)??(?P??R)不惟一.

v1 e1 e5 (1) v1e5 v5e7 v2e2 v3 (2) v5e6 v2e2 v3e3 v4e8 v2e7 v5 v2 e6 v5

e7 e4 (3) v2e7 v5e6 v2 (4) v1e1 v2e2 v3e3 v4e8 v2e6 v5

e2 e8 试回答它们各是简单通路、简单回路、初级通路还是初级回路? v3 v4

6、(1) 初级通路；(2) 简单回路；(3) 初级回路；(4) 简单通路 . e3

v e v

7、试问n取何值时，无向完全图Kn，存在一条欧拉回路？ 6、设图G如右图.已知通路

7、由于Kn有n个结点，并且每个结点的度数均为n－1，于是，当n为奇数时，Kn的每个结点的度数都是偶数，所以存在一条欧拉回路．

8、已知(L，*，?)是格，且二元运算*和?满足分配律，?a,b,c?L，化简表达式

((a*b)?(a*c))* ((a*b)?(b*c))

解答：((a*b)?(a*c))*((a*b)?(b*c)) ＝(a*b)? ( (a*c)* (b*c))(分配律) =(a*b) ?((a*b)*c) (幂等律) =a*b(吸收律)

9、化简(?P?(?Q?R))?(Q?R)?(P?R)。

9、(?P?(?Q?R))?(Q?R)?(P?R)=(?P??Q?Q?P)?R=

=(?P?Q?P)?R=R

10、试将一阶逻辑公式?x??yP?x,y?????yQ?y??R?x???化成前束范式。 解：

G??x??yP?x,y?????yQ?y??R?x?????x??yP?x,y????y?Q?y??R?x???

??x??yP?x,y???z?Q?z??R?x????x?y?z?P?x,y???Q?z??R?x??11、指出有向图D(如下图)中各图是强连通，单侧连通还是弱连通？

(1) (2) (3) (4) (5)

a b

12、找出无向图G（如右图所示）中的 c

一个点割集，三条边和四条边的边割集各一个． e d 11、强连通图为：图 (1),(4),(5)；

单侧连通图为：如图 (1),(2),(4),(5)；

弱连通图为：图 (1)～(5).

3. 点割集：{a,c,d}(不惟一) 三条边的边割集：{(b,c),(c,e),(c,d)}(不惟一) 四条边的边割集：{(a,b),(a,d),(d,e),(c,e)}(不惟一) 13、答案图如下图的虚线图.

13、求图13图G的对偶 图.

14、给定三个图如下图所示，试判断它们是否

为欧拉图、哈密顿图、或平面图？并说明理由．

a b c d e f g 图G1 图G2 图G3

14、图G1是欧拉图，因为每个结点度数均 为偶数． 图G2是哈密顿图，存在哈密顿回路，如 cdgfebac．(不惟一) 图G3是平面图．可以改画成可平面图，

图6－7

如图．

五、计算题

1、设R和S是集合A?{1,2,3,4}上的关系，其中

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

S?{?1,2?,?2,3?,?2,4?,?4,4?}R?S,R?1,S?1?R?1。

试求：（1）写出R和S 的关系矩阵；（2）计算R?S,1、解：（1）

?1?0MR???0??0010?010??,001??000??0?0MS???0??0100?011?? 000??001?（2）R?S={<1，3>，<2 ，4>}

R?S={<1，1>，<1，2>，<1，3>，<2，3>，<2，4>，<3，4>，<4，4>} R={<1，1>，<3，1>，<3，2>，<4，3>} S?1?1?R?1={<3，1>，<4，2>}

2、 设A={a，b，c，d}，R1，R2是A上的关系，其中R1={（a，a），（a，b），（b，a），（b，

b），（c，c），（c，d），（d，c），（d，d）}，R2={（a，b），（b，a），（a，c），（c，a），（b，c），（c，b），（a，a），（b，b），（c，c）}。 （1）画出R1和R2的关系图；

（2）判断它们是否为等价关系，是等价关系的求A中各元素的等价类。 2、解： R1和R2的关系图如下：（略）

由关系图可知，R1是等价关系。R1不同的等价类有两个，即{a，b}和{c，d}。 由于R2不是自反的，所以R2不是等价关系。

3、设集合A＝{1, 2, 3, 4, 6, 8, 12}，R是A上的整除关系，

a) 画出偏序集(A, R)的哈斯图；

b) 写出A的子集{2, 4, 6, 8}的上界，下界，最小上界，最大下界； (3) 写出集合A的最大元，最小元，极大元，极小元。 3、 集合A＝{1, 2, 3, 4, 6, 8, 12}(1) 半序集(A, R)的哈斯图

8 12 4 2 1 6 3

(2) 子集{2, 4, 6, 8}无上界，下界是1,2，无最小上界，最大下界是2. (3) A无最大元，最小元是1，极大元是8, 12，极小元是1。

4、用迪克斯特拉算法求下面有限权图中从A到B的最短路，要求用图示给出求解过程，并计算它们的权值。

2 1 A 4 6

4、 (本题12分) 求有限权图的最短路

2 1 A B 2 4 1 3 9 1 8 B

2

2 1 A 4 2 B