离散数学导论.ppt

离散数学导论离散数学导论现在学习的是第1页，共21页第一、二章第一、二章2、命题及其真值的判定命题及其真值的判定.3、命题公式的符号化、命题公式的符号化1、命题逻辑的五个联结词、命题逻辑的五个联结词，,及真值表及真值表.4、命题公式的类型：（、命题公式的类型：（1）永真式；（）永真式；（2）可满足式；（）可满足式；（3）永假式）永假式.很显然，永真式是可满足式，非永真式未必是永假式很显然，永真式是可满足式，非永真式未必是永假式，而当，而当A是永真式（永假式）时是永真式（永假式）时,A必为永假式（永真必为永假式（永真式）式）.现在学习的是第2页，共21页命题公式的类型可用以下方法判定：命题公式的类型可用以下方法判定：（1）真值表的方法）真值表的方法（2）利用已知永真式及代入、替换原理进行等价推演的方）利用已知永真式及代入、替换原理进行等价推演的方法法.（3）利用主析取范式和主合取范式的方法）利用主析取范式和主合取范式的方法.5、命题公式的范式（主析取范式、主合取范式）、命题公式的范式（主析取范式、主合取范式）,求命题公式的范式的方法求命题公式的范式的方法:（1）利用真值表的方法）利用真值表的方法.（2）等价推演的方法）等价推演的方法.现在学习的是第3页，共21页例例.命题公式的范式命题公式的范式.设命题公式为设命题公式为)()()(pprprqpA (1).求出该公式的真值表求出该公式的真值表.(2).求该公式的主析取范式和主合取范式求该公式的主析取范式和主合取范式.(3).判断该公式的类型判断该公式的类型.解解 (1).公式公式A的真值表为的真值表为现在学习的是第4页，共21页(2).公式公式A的主析取范式为：的主析取范式为：)()()()()(rqprqprqprqprqp pqrA00000011010001111001101111011110现在学习的是第5页，共21页)()()(rqprqprqp (3).由真值表可知，公式由真值表可知，公式A为可满足式为可满足式.主合取范式为：主合取范式为：pqrA00000011010001111001101111011110现在学习的是第6页，共21页5、谓词公式的符号化、谓词公式的符号化.准确地从语句中提取谓词，表示性质的谓语用一元谓词准确地从语句中提取谓词，表示性质的谓语用一元谓词表示，表示关系的谓语用二元或更多元数的谓词来表示，表示，表示关系的谓语用二元或更多元数的谓词来表示，准确地使用量词和适当的逻辑联结词把原语句表示为谓词准确地使用量词和适当的逻辑联结词把原语句表示为谓词公式公式.例例：设：设N(x)：x是自然数是自然数.I(x)：x是整数是整数.则语句：则语句：“所有的所有的自然数都是整数自然数都是整数”可表示为谓词公式：可表示为谓词公式：)()(xIxNx 设设N(x)：x是自然数是自然数.E(x)：x是奇数是奇数.则语句：则语句：“有些有些自然数是奇数自然数是奇数”可表示为谓词公式：可表示为谓词公式：)()(xExNx 现在学习的是第7页，共21页当个体域当个体域D是有限集合时是有限集合时,利用下列等价式可以消去谓词公式中的量词利用下列等价式可以消去谓词公式中的量词)()()()()()(11nnapapxxpapapxxp naaaD,21 例：例：设个体域设个体域D=0，1，p(0)=1，p(1)=0，确定，确定谓词公式谓词公式的真值的真值)()(xxqxxp 现在学习的是第8页，共21页001)01()01()1()0()1()0()()(ppppxxqxxp解：解：现在学习的是第9页，共21页第四章第四章例例：设集合：设集合A=1、2、3,则则1(A)（）设集合设集合A=1、2、3,则则 1(A)（）2、集合的运算（并、交、差、补、幂集运算）及运算律、集合的运算（并、交、差、补、幂集运算）及运算律.)(A)(A)(A 1、元素和集合的关系为属于关系、元素和集合的关系为属于关系，集合和集合间的关，集合和集合间的关系为包含关系系为包含关系 现在学习的是第10页，共21页第五章第五章1、关系及其运算、关系及其运算.（1）集合的笛卡儿积）集合的笛卡儿积.（2）关系的基本运算（并、交、差、补、合成）及运算律）关系的基本运算（并、交、差、补、合成）及运算律.（3）关系的基本特性（自反、反自反、对称、反对称、）关系的基本特性（自反、反自反、对称、反对称、传递）传递）.现在学习的是第11页，共21页例例（3）设集合设集合A=0,1,2,3,4,R,S均为均为A上二元关系上二元关系,且且 R=x+y=4 =，S=y x=1 =，那么那么 R S=，=x+z=5 S R=，=x+z=3 现在学习的是第12页，共21页例例 设设A=1,2,3以下各关系以下各关系Ri(i=1,2,8)均为均为A上二元关上二元关系系.（1）R1=，是自反的，而是自反的，而R2=，不是自反的，是反自反的，存在既不自反也不是自反的，是反自反的，存在既不自反也不反自反的二元关系，例如不反自反的二元关系，例如R3=.显然非空集合显然非空集合A上的上的关系是反自反的，不是关系是反自反的，不是自反的自反的.可是值得注意的是，当可是值得注意的是，当 A=时（这时时（这时A上只有一个上只有一个关系关系）,A上空关系既是自反的上空关系既是自反的,又是反自反的又是反自反的,因为因为A=使两者定义的前提恒假使两者定义的前提恒假.现在学习的是第13页，共21页（2）R4=，不是对不是对 称的；称的；R5=，是对称的；是对称的；R6=，是反对称的是反对称的.其实其实R4既不是对称的，也既不是对称的，也不是反对称的不是反对称的.特别有意思的是，存在既对称又反对称的二特别有意思的是，存在既对称又反对称的二元关系，例如元关系，例如A上的相等关系上的相等关系EA.（3）R7=，是传递的，是传递的，但但R7 便不是传递的了便不是传递的了.应当注意，应当注意，A上的空关系上的空关系，R8等是传递的，因为传递性定义的前提对等是传递的，因为传递性定义的前提对它们而言均为假它们而言均为假.现在学习的是第14页，共21页2、等价关系及偏序关系、等价关系及偏序关系（1）等价关系的判定）等价关系的判定判定该关系是否满足自反性、对称性、传递性判定该关系是否满足自反性、对称性、传递性.（2）序关系的判定）序关系的判定判定该关系是否满足自反性、反对称性、传递性判定该关系是否满足自反性、反对称性、传递性.整数集合上的等价关系：模整数集合上的等价关系：模n的相等关系（模的相等关系（模n的同余关的同余关系）系）,确定由模确定由模n的相等关系确定的等价类的元素的相等关系确定的等价类的元素.现在学习的是第15页，共21页第六章第六章1、函数的概念及运算、函数的概念及运算2、特殊函数：单射、满射、双射的判定、特殊函数：单射、满射、双射的判定.例：例：设设R是集合是集合A=1，2，.10上的模上的模3同余关系，则同余关系，则 10,7,4,1196338522 ，现在学习的是第16页，共21页1 1、握手定理及应用、握手定理及应用.2 2、欧拉图、哈密尔顿图的判定、欧拉图、哈密尔顿图的判定3 3、二分图、完全二分图的判定、二分图、完全二分图的判定第八章第八章例例.n个人参加一个集会，已知每个人恰有个人参加一个集会，已知每个人恰有5个朋友，问个朋友，问n是奇数还是偶数是奇数还是偶数?解：解：用用n个结点代表个结点代表n个人，两个朋友对应的结点之间个人，两个朋友对应的结点之间连接一边，如此得到一个连接一边，如此得到一个5-5-正则图正则图G G的数学模型。的数学模型。现在学习的是第17页，共21页于是由握手定理，于是由握手定理，假如假如n为奇数，则所有结点度数之和也为奇数，这与为奇数，则所有结点度数之和也为奇数，这与握手定理握手定理相违，故相违，故n必为偶数。必为偶数。nvnii5)deg(1 现在学习的是第18页，共21页第九章第九章 树树1 1、树的定义及等价定义、树的定义及等价定义问题：设是具有个顶点的树，问其顶点度数之和等于多少问题：设是具有个顶点的树，问其顶点度数之和等于多少？2 2、生成树的概念、生成树的概念 任一连通图都至少有一颗生成树任一连通图都至少有一颗生成树现在学习的是第19页，共21页 第十章第十章 代数结构代数结构1 1、代数结构中特殊元素的概念及确定、代数结构中特殊元素的概念及确定2 2、群的定义、群的定义第十三章第十三章 格和布尔代数格和布尔代数1、格的概念、格的概念2、格中的表达式的化简、格中的表达式的化简3、布尔代数的概念、布尔代数的概念4、布尔代数中表达式的计算、布尔代数中表达式的计算现在学习的是第20页，共21页例例.设设B是布尔代数，是布尔代数，a,b,cB，化简以下公式，化简以下公式ccbaba )()(cacaacccaaccabbaccababaccbabaccbaba )1)()()()1()()()()()()()()()（解解：现在学习的是第21页，共21页