《离散数学(第三版)》方世昌 的期末复习知识点总结复习进程

A到D的最短路径为ABEFCD，权为9。 [证明题] 1. 证明：

（（P?Q）?（Q?R））?（P?R） ?（（?P?Q）?（?Q?R））?（?P?R） ??（（?P?Q）?（?Q?R））?（?P?R）

?（P??Q）?（Q??R）??P?R ?（（P??Q）??P ）?（（Q??R）?R）?（1?（?Q??P ））?（（Q?R）?1） ? ?Q??P?Q?R ? （?Q?Q） ??P ?R ? 1 ??P ?R ? 1 2. 证明：

（1） P?R 规则P （2） ?R?P 规则Q ，根据（1）（3） P?Q 规则P

（4） ?R ?Q 规则Q，根据（2）（（5） ?Q?R 规则Q，根据（4）（6） R?S 规则P

（7） ?Q?S 规则Q，根据（5）（（8） Q?S 规则Q ，根据（7）

3）6） 三、 综合练习及解答

（一）填空题

1、集合的表示方法有两种： 法和 法。请把“大于3而小于或等于7的整数集合”用任一种集合的表示方法表示出来A={ }。

2、A，B是两个集合，A={1，2，3，4}，B={2，3，5}，则B-A= ，?（B）??（A）= ，?（B）的元素个数为 。 3、设A?{a,b},B?{1,2}，则从A到B的所有映射是 。

4、设命题公式G?P??(Q?R)，则使公式G为假的解释是 、 和 。

5、设G是完全二叉树，G有15个点，其中8个叶结点，则G的总度数为 ，分枝点数为 。

6、全集E={1，2，3，4，5}，A={1，5}，B={1，2，3，4}，C={2，5}， 求A??B=

，?（A）??（C）= ，

?C= 。

7、设A和B是任意两个集合，若序偶的第一个元素是A的一个元素，第二个元素是B的一个元素，则所有这样的序偶集合称为集合A和B的 ，

记作A?B，即A?B= 。A?B的子集R称为A，B上的 。

8、将几个命题联结起来，形成一个复合命题的逻辑联结词主要有否定、 、

、 和等值。

9、表达式?x?yL（x，y）中谓词的定义域是{a，b，c}，将其中的量词消除，写成与之等价的命题公式为 。

10、一个无向图表示为G=（P，L），其中P是 的集合，L是 的集合，并且要求 。

（二）单项选择题（选择一个正确答案的代号，填入括号中） 1. 设命题公式G?(P??P)?((Q?R)?P)，则G是（ ）。

A.恒真的 B.恒假的 C.可满足的 D.析取范式

2、设集合A?{a,b,c}，A上的关系R?{(a,a),(a,b),(b,c)}，则R2=（ ）。

(A){(a,a),(a,b),(a,c)};

(C){(a,b),(a,c),(b,b)};(B){(a,b),(a,c),(b,c)};

(D){(a,a),(a,b),(c,c)}.3、一个公式在等价意义下，下面哪个写法是唯一的（ ）。

A．析取范式 B．合取范式 C．主析取范式 D．以上答案都不对 4、设命题公式G=?（P?Q），H=P?（Q??P），则G与H的关系是（ ）。

A．G?H B．H?G C．G=H D．以上都不是

?0??15、已知图G的相邻矩阵为?0??1?1?1011??0001?0011?，则G有（ ）。

?0101?1110?? A.5点，8边 B. 6点，7边 C. 5点，7边 D. 6点，8边 6、下列命题正确的是（ ）。

A．??{?}=? B．??{?}=? C．{a}?{a，b，c} D．??{a，b，c} 7、设集合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．反对称

8、设R为实数集，映射?=R?R，?（x）= -x2+2x-1，则?是（ ）。

A．单射而非满射 B．满射而非单射 C．双射 D．既不是单射，也不是满射

9、下列语句中，（ ）是命题。

A．下午有会吗？ B．这朵花多好看呀！ C．2是常数。 D．请把门关上。

10、下面给出的一阶逻辑等价式中，（ ）是错的。

A． B． C． D．

?x（A（x）?B（x））=?xA（x）??xB（x） A??xB（x）=?x （A?B（x））

?x（A（x）?B（x））=?xA（x）??xB（x） ??xA（x）=?x（?A（x））

（三）计算题

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

S?{(1,2),(2,3),(2,4),(4,4)}试求： （1）写出R和S 的关系矩阵； （2）计算R?S,R?S,R?1,S?1?R?1。