离散数学导论42316

1、王元元王元元 张桂芸张桂芸科学出版社科学出版社第一、二章第一、二章2、命题及其真值的判定命题及其真值的判定.3、命题公式的符号化、命题公式的符号化1、命题逻辑的五个联结词、命题逻辑的五个联结词 ，, 及真值及真值表表. 4、命题公式的类型：（、命题公式的类型：（1）永真式；（）永真式；（2）可满）可满足式；（足式；（3）永假式）永假式. 很显然，永真式是可满足式，非永真式未必是永很显然，永真式是可满足式，非永真式未必是永假式，而当假式，而当A是永真式（永假式）时是永真式（永假式）时, A必为永假必为永假式（永真式）式（永真式）.命题公式的类型可用以下方法判定：命题公式的类型可用以下方法判定：（

2、1）真值表的方法）真值表的方法（2）利用已知永真式及代入、替换原理进行等价推）利用已知永真式及代入、替换原理进行等价推演的方法演的方法.（3）利用主析取范式和主合取范式的方法）利用主析取范式和主合取范式的方法.5、命题公式的范式（主析取范式、主合取范式）、命题公式的范式（主析取范式、主合取范式）,求命题公式的范式的方法求命题公式的范式的方法:（1）利用真值表的方法）利用真值表的方法.（2）等价推演的方法）等价推演的方法.例例. 命题公式的范式命题公式的范式. 设命题公式为设命题公式为)()()(pprprqpA (1). 求出该公式的真值表求出该公式的真值表.(2). 求该公式的主析取范式和主

3、合取范式求该公式的主析取范式和主合取范式.(3). 判断该公式的类型判断该公式的类型.解解 (1).公式公式A的真值表为的真值表为(2).公式公式A的主析取范式为：的主析取范式为：)()()()()(rqprqprqprqprqp pqrA00000011010001111001101111011110)( )()( rqprqprqp (3).由真值表可知，公式由真值表可知，公式A为可满足式为可满足式.主合取范式为：主合取范式为：pqrA000000110100011110011011110111105、谓词公式的符号化、谓词公式的符号化. 准确地从语句中提取谓词，表示性质的谓语用一准确地从

4、语句中提取谓词，表示性质的谓语用一元谓词表示，表示关系的谓语用二元或更多元数的元谓词表示，表示关系的谓语用二元或更多元数的谓词来表示，准确地使用量词和适当的逻辑联结词谓词来表示，准确地使用量词和适当的逻辑联结词把原语句表示为谓词公式把原语句表示为谓词公式.例例：设：设N(x)：x是自然数是自然数. I(x)：x是整数是整数. 则语句：则语句：“所有的自然数都是整数所有的自然数都是整数”可表示为谓词公式：可表示为谓词公式： )()(xIxNx 设设N(x)：x是自然数是自然数. E(x)：x是奇数是奇数. 则语句：则语句：“有些自然数是奇数有些自然数是奇数”可表示为谓词公式：可表示为谓词公式：

5、)()(xExNx 当个体域当个体域D是有限集合时是有限集合时, 利用下列等价式可以消去谓词公式中的量词利用下列等价式可以消去谓词公式中的量词)()()()()()(11nnapapxxpapapxxp naaaD,21 例：例：设个体域设个体域D=0，1，p(0)=1，p(1)=0，确定谓词公式确定谓词公式的真值的真值)()(xxqxxp 001)01()01()1()0()1()0()()( ppppxxqxxp解：解：第四章第四章例例：设集合：设集合A=1、2、3, 则则1 (A) （） 设集合设集合A=1、2、3, 则则 1 (A) （）2、集合的运算（并、交、差、补、幂集运算）及运算

6、、集合的运算（并、交、差、补、幂集运算）及运算律律. )(A )(A )(A 1、元素和集合的关系为属于关系、元素和集合的关系为属于关系，集合和集合间的，集合和集合间的关系为包含关系关系为包含关系 第五章第五章1、关系及其运算、关系及其运算.（1）集合的笛卡儿积）集合的笛卡儿积.（2）关系的基本运算（并、交、差、补、合成）及）关系的基本运算（并、交、差、补、合成）及运算律运算律.（3）关系的基本特性（自反、反自反、对称、反对）关系的基本特性（自反、反自反、对称、反对称、传递）称、传递）.例例（3）设集合设集合A=0, 1, 2, 3, 4, R, S均为均为A上二元上二元关系关系, 且且 R=

7、 x+y=4 =， S= y x=1 =，那么那么 R S=， = x+z=5 S R=， = x+z=3 例例 设设A=1, 2, 3以下各关系以下各关系Ri (i=1, 2, , 8)均为均为A上上二元关系二元关系.（1）R1=，是自反的，是自反的，而而R2=，不是自反的，是反自反的，存不是自反的，是反自反的，存在既不自反也不反自反的二元关系，例如在既不自反也不反自反的二元关系，例如R3=. 显然非空集合显然非空集合A上的上的关系是反自反的，关系是反自反的，不是自反的不是自反的. 可是值得注意的是，当可是值得注意的是，当 A=时（这时时（这时A上只有一个关系上只有一个关系）, A上空关系既

8、是自反的上空关系既是自反的,又是反自又是反自反的反的, 因为因为A=使两者定义的前提恒假使两者定义的前提恒假.（2）R4=，不是对不是对 称的；称的；R5=，是对称的；是对称的； R6=，是反对称的是反对称的. 其实其实R4既不是对既不是对称的，也不是反对称的称的，也不是反对称的. 特别有意思的是，存在既对特别有意思的是，存在既对称又反对称的二元关系，例如称又反对称的二元关系，例如A上的相等关系上的相等关系EA.（3）R7=，是传递是传递的，但的，但R7 便不是传递的了便不是传递的了. 应当注意，应当注意，A上的空关系上的空关系，R8等是传递的，因为传等是传递的，因为传递性定义的前提对它们而言

9、均为假递性定义的前提对它们而言均为假.2、等价关系及偏序关系、等价关系及偏序关系（1）等价关系的判定）等价关系的判定判定该关系是否满足自反性、对称性、传递性判定该关系是否满足自反性、对称性、传递性.（2）序关系的判定）序关系的判定判定该关系是否满足自反性、反对称性、传递性判定该关系是否满足自反性、反对称性、传递性. 整数集合上的等价关系：模整数集合上的等价关系：模n的相等关系（模的相等关系（模n的的同余关系）同余关系）,确定由模确定由模n的相等关系确定的等价类的的相等关系确定的等价类的元素元素.第六章第六章1、函数的概念及运算、函数的概念及运算2、特殊函数：单射、满射、双射的判定、特殊函数：单

10、射、满射、双射的判定.例：例：设设R是集合是集合A=1，2，.10上的模上的模3同余关系，同余关系，则则 10,7,4,1196338522 ，1 1、握手定理及应用、握手定理及应用. .2 2、欧拉图、哈密尔顿图的判定、欧拉图、哈密尔顿图的判定3 3、二分图、完全二分图的判定、二分图、完全二分图的判定第八章第八章例例. n个人参加一个集会，已知每个人恰有个人参加一个集会，已知每个人恰有5个朋友，个朋友，问问n是奇数还是偶数是奇数还是偶数?解：解：用用n个结点代表个结点代表n个人，两个朋友对应的结点个人，两个朋友对应的结点之间连接一边，如此得到一个之间连接一边，如此得到一个5-5-正则图正则图

11、G G的数学模的数学模型。型。 于是由握手定理，于是由握手定理，假如假如n为奇数，则所有结点度数之和也为奇数，为奇数，则所有结点度数之和也为奇数，这与这与握手定理握手定理相违，故相违，故n必为偶数。必为偶数。 nvnii5)deg(1 第九章第九章 树树1 1、树的定义及等价定义、树的定义及等价定义问题：设是具有个顶点的树，问其顶点度数之和等问题：设是具有个顶点的树，问其顶点度数之和等于多少？于多少？2 2、生成树的概念、生成树的概念 任一连通图都至少有一颗生成树任一连通图都至少有一颗生成树 第十章第十章 代数结构代数结构1 1、代数结构中特殊元素的概念及确定、代数结构中特殊元素的概念及确定2 2、群的定义、群的定义第十三章第十三章 格和布尔代数格和布尔代数1、格的概念、格的概念2、格中的表达式