离散数学期末复习提要（同济）2009

《离散数学》期末复习

一、各章复习要求与重点

第一章 命题逻辑

[复习知识点]

１、命题与联结词（否定、析取、合取、蕴涵、等价），复合命题 ２、命题公式与解释，真值表，公式分类（永真、永假、可满足），公式的等价 ３、析取范式、合取范式，极小（大）项，主析取范式、主合取范式 ４、公式类别的判别方法（真值表法、等值演算法、主析取/合取范式法） ５、公式的蕴涵与逻辑结果 ６、形式演绎

本章重点内容：命题与联结词、公式与解释、析取范式与合取范式、公式永真性的判定、形式演绎 [复习要求]

１、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。

２、理解公式与解释的概念；掌握求给定公式真值表的方法，用基本等价式化简其他公式，公式在解释下的真值。

３、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等价式或真值表将公式化为主析取（合取）范式的方法。

４、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价的方法。

５、理解公式蕴涵与逻辑结果的概念，掌握基本蕴涵式。 6、掌握形式演绎的证明方法。 [本章重点习题]

P93，1； P98，2，3； P104，2，3； P107，1，3； P112，5； P115，1，2，3。 [疑难解析]

1、公式永真性的判定

判定公式的永真性，包括判定公式是永真的或是永假的。具体方法有两种，一是真值表法，对于任给一个公式，主要列出该公式的真值表，观察真值表的最后一列是否全为1（或全为0），就可以判定该公式是否永真（或永假），若不全为0，则为可满足的。二是推导法，即利用基本等价式推导出结果为1，或者利用永真（永假）判定定理：公式G是永真的（永假的）当且仅当等价于它的合取范式（析取范式）中，每个子句（短语）均至少包含一个原子及其否定。

这里要求的析取范式中所含有的每个短语不是极小项，一定要与求主析取范式相区别，对于合取范式也同样。

2、范式

求范式，包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点：一是准确理解掌握定义；另一是巧妙使用基本等价式中的分配律、同一律和互补律，结果的前一步适当使用等幂律，使相同的短语（或子句）只保留一个。

另外，由已经得到的主析取（合取）范式，根据G??G?1,???G??G原理，参阅

《离散数学学习指导书》P71例15，可以求得主合取（析取）范式。

3、形式演绎法

掌握形式演绎进行逻辑推理时，一是要理解并掌握14个基本蕴涵式，二是会使用三个规则：规则P、规则Q和规则D，需要进行一定的练习。 [例题分析]

例1 求G???P?Q???R??P的主析取范式与主合取范式。

1

解 （1）求主析取范式， 方法1：利用真值表求解 PQR P?Q 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 因此

0 0 0 0 0 0 1 1 ?P?Q???R 1 0 1 0 1 0 1 1 G 0 1 0 1 1 1 1 1 G???P??Q?R????P?Q?R???P??Q??R???P??Q?R???P?Q??R?

??P?Q?R?方法2：推导法

G???P?Q?R??R??P????P?Q???R??P????P??Q??R??P???P?R????Q?R??P????P?R????Q?Q??????Q?R???P??P??

??P??Q??Q???R??R??

???P?Q?R????P??Q?R???P??Q?R????P??Q?R???P?Q?R???P?Q??R???P??Q?R???P??Q??R????P?Q?R????P??Q?R???P??Q?R???P?Q?R???P?Q??R???P??Q??R?（2）求主合取范式

方法1：利用上面的真值表

??P?Q???R??P为0的有两行，它们对应的极大项分别为P?Q?R,因此，??P?Q???R??P??P?Q?R???P??Q?R? 方法2：利用已求出的主析取范式求主合取范式

已用去6个极小项，尚有2个极小项，即 ?P??Q??R与?P?Q??R 于是

P??Q?R

?G???P??Q??R????P?Q??R? G????G??????P??Q??R????P?Q??R??

??P?Q?R???P??Q?R?例2 试证明公式G???P?Q???Q?R????P?R?为永真公式。 证 ： G=?（（?P?Q）?（?Q?R））?（?P?R） =（P??Q）?（Q??R）??P?R =（（（P?Q）?（P??R）?（?Q?Q）?（?Q??R））??P）?R =（（P?Q??P）?（P??R??P）?（?Q??R??P））?R =（1?（?Q??R??P））?R =?Q??R??P?R =1

2

故G为永真公式。

例3 利用形式演绎法证明 { P?（Q?R），?S?P，Q}蕴涵S?R。 证明：

（1）?S?P 规则P （2）S 规则D

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

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

（7）R 规则 Q，根据（5），（6） （8）S?R 规则D，根据（2），（7）

第三章 集 合

[复习知识点]

1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集

2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、 De Morgan律等

本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明 [复习要求]

1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。 2、掌握集合的表示法和集合的交、并、差、补等基本运算。 3、掌握集合运算基本规律，证明集合等式的方法。 [本章重点习题] [疑难解析]

1、集合的概念

因为集合的概念学生在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为2n。

2、集合恒等式的证明

通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在A?B?A?~B证明中的特殊作用。 [例题分析]

例1 设A，B是两个集合，A={1，2，3}，B={1，2}，则?(A)??(B)? 。 解 ?(A)?{?,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

?(B)?{?,{1},{2},{1,2}}

于是?(A)??(B)?{{3},{1,3},{2,3},{1,2,3}} 例2 设A??a,b,?a,b?,??，试求：

(1)A??a,b?； (2)A??； (3)A????； (4)??a,b???A； (5)??A； (6)????A。

?a,b?,?? (2)A???A (3)A??????a,b,?a,b?? 解 (1)A??a,b???

3

(4)??a,b???A?? (5)??A?? (6)????A?? 例3 试证明?A?~B???~A?B???A?B???~A?~B? 证明

?A?~B???~A?B????A?~B??~A????A?~B??B????A?~A???~B?~A?????A?B???~B?B??

?????~A?~B?????A?B??????A?B???~A?~B?

第四,五章 二元关系与函数

本部分重点：关系概念与其性质，等价关系和偏序关系，函数.

一、重点内容

1. 关系的概念 包括定义、关系的表示方法：集合表示、矩阵表示、图形表示. ?二元关系，是一个有序对集合，设集合A,B，R?{?x,y?x?A?y?B}，记作xRy 二元关系的定义域：Dom(R)?A； 二元关系的值域：Ran(R)?B ?关系的表示方法：

集合表示法：关系是集合，有类似于集合的表示方法.

列举法，如R＝{<1,1>,<1,2>}；描述法：如R?{?x,y?x?A?y?B}

??1 关系矩阵： R?A×B，R的矩阵MR?(rij)m?n,rij????0aiRbj?i?1,2...,m,???? aiR?bj?j?1,2,...,n??关系图： R是集合上的二元关系，若?R，由结点aI画有向弧到bj构成的图形.

2. 几个特殊的关系

空关系?；唯一是任何关系的子集的关系. 全关系EA?{?a,b?a,b?A}?A?A

恒等关系IA?{?a,a?a?A}，MI是单位矩阵. 3. 关系的运算

?关系的集合运算，有并、交、补、差和对称差.

?复合关系 R?R1?R2?{?a,c??b使?a,b??R1??b,c??R2}，有 复合关系矩阵：MR?MR1?MR2(布尔运算)，有结合律：(R?S)?T＝R?(S?T) ?逆关系R?1－－－T，(R?S)1=S1?R1. ?{?y,x??x,y??R}，MR?1?MR4. 关系的性质

?自反性 ?x?A,?x,x??R；矩阵MR的主对角线元素全为1；关系图的每个结点

都有自回路.

?反自反性 ?x?A,?x,x??R；矩阵MR的主对角线元素全为0；关系图的每个结点都没有自回路.

4

?对称性 若?x,y??R，则?y,x??R；矩阵MR是对称矩阵，即rij?rji；关系图中有向弧成对出现,方向相反.

?反对称性 若?x,y??R且?y,x??R，则x=y或若?x,y??R,x?y，则

?y,x??R；矩阵MR不出现对称元素.

?传递性 若?a,b??R且?b,c??R，则?a,c??R；在关系图中，有从a到b的弧，有从b到c的弧，则有从a到c的弧. 判断传递性较为困难. 可以证明：R是集合A上的二元关系，

(1)R是自反的?IA?R; (2)R是反自反的?IA?R＝?;

－1－1

(3)R是对称的 ?R＝R； (4)R是反对称的?R?R?IA； (5)R是传递的?R?R?R.

关系的性质所具有的运算见表4－1.

表4－1 二元运算的并、交、补、差、逆、复合具有的性质表

反自反性 对称性 反对称性 传递性 R ? ? ? ? ? R1?R2 ? ? ? ? ? R1?R2 ? ? ? ? ? R1－R2 ? ? ? ? ? R1?R2 ? ? ? ? ? IA ? ? ? ? ? ? ? ? ? 由表可见，IA具有自反性，对称性、反对称性和传递性.EA具有自反性，对称性和传递性.故IA，EA是等价关系.?具有反自反性、对称性、反对称性和传递性。?是偏序关系.

关系性质的判定，可以用定义、关系矩阵或关系图.

传递性的判定，难度稍大. 也常如下判定：不破坏传递性的定义，可认为具有传递性. 例如?可认为具有传递性，同时具有对称性和反对称性，但是不具有自反性； 5. 关系的闭包

设R是非空集合A上的二元关系，在关系R中，添加最少的有序对，新关系用R?表示，使得R?具有关系的自反(对称、传递)性质，R?就是R的自反(对称、传递)闭包，记作r(R) ，s(R)和t(R)。闭包的求法：

－1 运算 关系性质 自反性 定理12：r(R)?R?IA；定理13：s(R)?R?R；定理14的推论：t(R)?

6. 等价关系和偏序关系 极大(小)元、最大(小)元问题 ?等价关系和偏序关系是具有不同性质的两个关系.

??等价关系对称性? 自反性?? ?传递性????反对称性???偏序关系?1?Ri?1ni

?等价关系图的特点：每一个结点都有一个自回路；两个结点间如有有向弧线，则是双向弧线，如果从a到b，从b到c各有一条有向弧线，则从a到c一定有有向弧线。 ?等价类，若R是等价关系，与R中的某个元素等价的元素组成的集合，就是R的一个等价类，[a]R={b?b?A?aRb}. ?偏序集的哈斯图 偏序集概念和偏序集的哈斯图。哈斯图的画法：(1) 用空心点表示结点，自环不画；(2) 若a?b，则结点b画在上边，a画在下边，并画a到b的无向弧；(3) 若,?,则?R，此时，a到c的有向弧不画出.

5

本文来源：https://www.bwwdw.com/article/fvr2.html