2013年上半年离散数学(数学教育)复习概要

1、2013年5月2013年上半年离散数学（数学教育）复习概要第一讲至第三讲更具体的要求：1 集合及其相关的基本概念和性质，尤其是幂集的定义要理解清楚，会求一个集合的幂集；2 关系的定义、关系的特点、会判断补关系、逆关系等；会判断一个集合上的二元关系是否有自反性、对称性、传递性、反自反性和反对称性这五个性质；3 清楚关系的合成的定义，会计算两个关系的合成；4 清楚自反闭包、对称闭包和传递闭包的定义与其求法；5 清楚等价关系的定义，会判断并证明一个关系是否为等价关系；6 清楚集合的划分的定义，并会利用一个等价关系对一个集合进行划分.第四讲至第七讲更具体的要求：1 命题的定义及判定；五个逻辑联结词的定

2、义及其真值的判定；2 会将日常语句符号化；3 命题公式、解释的定义，真值表，会求一个公式在某解释下的真值；4 会用真值表；会判断命题公式的类型；5 熟悉基本的等价式与蕴涵式并能判定一些简单的等价式和蕴涵式；6 会用多种方法证明等价式与蕴涵式；7 知道析取范式、合取范式和主析取范式的定义，会求主析取范式.第八讲至第十一讲讲更具体的要求：1 了解谓词、量词等基本概念；2 会判断约束变量和自由变量；3 熟悉谓词公式的定义；4 会对给定的解释求公式的值；5 熟悉基本的等价式；会应用推理规则证明等价式和蕴涵式；6 了解图、树、二部图等及其基本概念和结论；7 了解群的基本概念和结论，会判定一个代数系统究竟

3、是不是群，会求一个群的单位元或某元的逆元.第一讲：集合（课本第一章第一节）1 元素与集合、集合与集合之间的关系.2 幂集的定义：设A是集合，A中所有子集为元素构成的集合称为A的幂集，记为. 例如A=a,b,c，则A的幂集，显然有个元素.例1：设A是以空集作为惟一元素的集合，P(A)表示A的幂集，集合，则有（ ）A B C D E 答案：A,B,C,D. 由题知，则，.例2： 设B=，则其幂集为_. 例3： 设B=a,，则其幂集为_. 第二、三讲 关系（课本第一章第二节）一、基本概念1 设A,B是集合，则.2 二元关系：称集合的一个子集R为集合A与B上的一个二元关系，简称为关系. 3 对于，如果

4、，则称x，y有关系R，记为xRy;若，则称x，y没有关系R，记为.4 若A=B，则称R为A上的二元关系.5 例如A=a,b,c, 则R=(a,a),(a,b), S=(a,b),(b,c),(c,b)是A上的二元关系.6 自然数集上的“”关系是指集合；自然数集上的“”关系是指集合.7 关系的特点：（1）的任一个子集都是A上的关系；（2）若|A|=n，则A上的关系有个；（3）A上的3个特殊关系：空关系、全域关系、相等关系；（4）；(R的补关系)（5）序偶(a,b)=(c,d)的充要条件是a=c,b=d.8 补关系：例如自然数集“”的补关系是“” ；“”的补关系是“”.9 逆关系：设R是集合A上的

5、一个关系，令，称关系为关系R的逆关系.10 例如A=a,b,c, R=(a,a),(a,b)，则；自然数集“”的逆关系是“” ；“”的补关系是“”.二、特殊关系1 集合A上的关系R称为自反的（反身的），如果对于每个，都有2 对于自反性，有3个命题是等价的：（1）R是自反的；（2）; （3）是自反的.3 集合A上的关系R称为对称的，如果xRy，则有yRx，其中.4 对于对称性，有2个命题是等价的：（1）R是对称的；（2）.5 集合A上的关系R称为传递的，如果xRy， yRz，则有xRz， 其中.6 集合A上的关系R称为反对称的，如果xRy， yRx，则必有x=y, 其中.7 对于反对称性，有2个

6、命题是等价的：（1）R是反对称的；（2）.（注意这里若，也有，即若，也称R是反对称的）.8 集合A上的关系R称为反自反的，如果对于每个， 均不成立.9 对于反自反性，有2个命题是等价的：（1）R是反自反的；（2）.10 任意集合A上的相等关系是自反的，对称的，反对称的，传递的.11 设集合A=a,b,c，R=(b, b), (a, c), (b, c), (c, b).（1） 因为，则R不是自反的；（2） 因为，则R不是反自反的；（3） 因为，故R不是对称的；（4） 因为，而，故R不是传递的；（5） 又，但，故R不是反对称的.12 自然数集N上的“”关系是自反的，反对称的，传递的.13 自然数

7、集N上的“”关系是传递的.例1：设，上的关系，则是否具有（使用“T”表示具有，使用“F”表示不具有）：A 自反性( ) B 对称性 ( ) C 反对称性（ ） D 传递性（ ）解答：TTFF. 例2：设，是上的关系，则具有性质：自反的，对称的，传递的，反自反的，反对称的这五条中的哪几条：_例3：设A=a, b, c, d, A上的关系R=(a, a), (b, a), (d, b), (a, c), (c, d), S= (b, a), (c, b), (a,b), (c, d)。试判定R，S分别有什么性质？（即具有自反性、反自反性、对称性、反对称性和传递性这五个性质中的哪些性质）解：R具有反

8、对称性；S具有反自反性三、关系的乘积（合成）1 设R, S是集合A上的两个关系，令， 则称为关系R与S的乘积或合成.2 会计算集合上的两个关系的合成.例1：设A=a, b, c, d, A上的关系R=(a, a), (b, a), (d, b), (a, c), (c, d), 求.解：故(a,a),(b,a),(d,a),(c,b),(a,c),(b,c),(a,d).例2：设A=a, b, c, d, A上的关系R=(a, a), (b, a), (d, b), (a, c), (c, d), S= (b, a), (c, b), (a,b), (c, d)。求.解： (a,b), (b,

9、b), (d,a),(a,b),(a,d)。四、闭包1 设A是非空集合，R是A上的二元关系，R的自反闭包（对称闭包、传递闭包）满足如下条件：（1）是自反的（对称的，传递的）；（2）；（3）对A上任意包含R的自反的（对称的，传递的）关系，都有. R的自反闭包、对称闭包和传递闭包分别记为，他们分别是包含R的最小（是指元素个数最小）的自反关系、对称关系和传递关系.2 定理1.2.5：设R是集合A上的关系，则（1）；（2）；（3）.3 例如A=a, b, c, 设R=(a, c), (b, c), (b, b), 则R的自反闭包 R的对称闭包4 自然数集N上的小于关系“”的自反闭包是“”；5 自然数集

10、N上的不等关系“”的自反闭包是全域关系；6 自然数集N上的空关系“”的自反闭包是相等关系.7 整数集Z上的小于关系“”的对称闭包是“”；8 整数集Z上的不大于关系“”的对称闭包是全域关系.五、等价关系1 等价关系：设R是非空集合A上的一个关系，若R具有自反性、对称性和传递性，则称 R是一个等价关系.2 例子：设A=a, b, c，R=(a, a), (b, b), (c, c), (a, b), (b, a)是A上的等价关系.3 等价类：设A是一个非空集合，是A上的一个等价关系.A的一个非空集合M叫做一个等价类，如果（1） 若，则；（2） 若，则.（即a,b属于同一个等价类当且仅当）4 商集：

11、设R是非空集合A上的一个等价关系，以R的所有不同的等价类为元素作成的集合称为A关于R的商集，简称A的商集，记作.5 划分：当A的子集簇C满足如下条件时，称C为A的划分：（1） 若，则；（2）；（3）对任意的，且，则.6 定理：设R是非空集合A上的一个等价关系，则A的商集构成A的一个划分；反之，若C是集合A的一个划分，令，则是A的一个等价关系.7 会判定等价关系.8 会对一个非空集合A的等价关系R给出A的一个划分.例子：设，上的等价关系，求对应于的的划分.解：，所以，对应于的的划分为.第四讲：命题与命题公式（第二章第一、二节）一、命题1 命题：命题是指一句有真假意义的话，即是一句能辨真假的话.

12、常用大写字母P,Q,R等来表示.2 句子分为疑问句、祈使句、感叹句与陈述句等，只有陈述句才可能是命题.3 注1：一个陈述句，它所表述的内容，可能是真的，也可能是假的，但不能是含糊不清的，只有这样的语句才能是一个命题.4 注2：一个句子本身是否能辨真假与我们是否知道它的真假是两回事. 也就是说，只要句子本身是有真假的，它就是命题.5 命题的真值：如果一个命题是真的，我们就说它的真值为1；如果此命题是假的，就说它的真值是0.也就是说，我们用1表示一个抽象的真命题，而用0表示一个抽象的假命题.二、逻辑联结词1 命题符号（原子）的定义：用大写的英文字母P,Q.等代表一个抽象的命题，称为命题符号，或原子

13、.2 复合命题的定义：若干个原子通过逻辑联结词而构成的新命题称为复合命题.3 五个逻辑联结词：否定（），析取（或者）（），合取（并且）（），蕴涵（），等价（）.4 否定（）：设P是一个命题，命题“P是不对的”称为P的否定，记为P, 读作非P. 规定：非P是真的当且仅当P是假的. 例如：P：广州是一个城市； P：广州不是一个城市. 显然：P是一个真命题，而P是假命题.5 析取（或者）（）：设P, Q是两个命题，命题“P或者Q”称为P, Q的析取，记作，读作P或Q. 规定：是真的当且仅当P, Q中至少一个是真的.6 合取（并且）（）：设P, Q是两个命题，命题“P并且Q”称为P, Q的合取，记作，

14、读作P且Q. 规定：是真的当且仅当P和 Q都是真的.7 蕴涵（）：设P, Q是两个命题，命题“若P，则Q”称为P蕴涵 Q，记作. 规定：是假的当且仅当P是真的而 Q是假的.8 等价（）：设P, Q是两个命题，命题“P当且仅当Q”称为P等价 Q，记作. 规定：是真的当且仅当P，Q或者都是真的，或者P, Q都是假的.三、命题公式1 命题公式的定义：命题逻辑中的公式，是如下定义的一个符号串：（1） 原子是公式；（2） 0，1是公式；（3） 若G,H是公式，则是公式；（4） 所有公式都是有限次使用（1），（2），（3）而得到的字符串.2 五种逻辑联结词的运算次序：，即否定（）最优，析取（或者）（）次之

15、，合取（并且）（）再次之，然后蕴涵（），最后是等价（）.3 解释的定义：设G是命题公式，是出现在G中的所有原子. 指定的一组真值，则这组真值称为G的一个解释. 4 公式G在其所有可能解释下所取真值的表，称为G的真值表. 5 请写出的真值表.例如：的真值表为：GH0010111001116 公式G称为恒真的，如果它在所有的解释下都是真的；公式G称为恒假的，如果它在所有的解释下都是假的；公式G称为可满足的，如果它不是恒假的；（即至少在某种解释下是真的）7 构造命题公式的真值表，并判断其类型（恒真的，恒假的，可满足的）PQ00101011011000111111例子：构造下列公式的真值表，并判断它们

16、的类型（恒真，恒假，可满足）：. 解： 构造真值表如下：PQRG001000111001001100011000111011001111100110010100111100110010010110011111所以上述公式是可满足的.第五、六讲 命题公式的等价关系和蕴涵关系 （第二章第三节）一、命题公式的等价关系1 公式的等价：公式G,H是等价的，记为G=H，如果G,H在其任意解释I下，其真值相同.2 注1：公式G,H等价的充要条件是公式是恒真的.3 基本的等价式如下：（1）；（2）；（3）； （等幂律）（4）； （交换律）（5）； （结合律）（6）； （吸收律）（7）； （分配律）（8）； （

17、同一律）（9）； （零一律）（10）. （De Morgan 律）4 证明下列等价式：.构造公式与的真值表，可见与在任意解释I 下，其值相同（真值表中第三列和第八列对应相等）.故它们等价，即.GH001011110100100010000100111100015 证明等价式：.证明：由同一律及分配律知6 证明等价式有两种方法：一是如第4点所述证明在任意解释I 下，两个公式的值相同；二是如第5点所述应用已有的基本等价式证明.例子：证明等价式 .证法一：令G表示，构造真值表如下：PQRG00000000001110010100000001100101100000001011001111000000

18、11100111可看到第三列与第八列值相同. 即两者等价.证法二：二、命题公式的蕴涵关系1 定义：设G,H是两个公式，称G蕴涵H（或称H是G的逻辑结果），当且仅当对G ，H的任意解释I，如果I满足G，则I也满足H，记作.2 注1：的充要条件是公式是恒真的.3 注2：对任意的公式P,Q，P=Q的充要条件是且.4 基本蕴涵式：（1）；（2）；（3）；（因为（4）；（因为.5 给定两个公式G,H，要证，我们有如下几种方法：（1） 真值表法；（2） 证公式是恒真的；（3） 利用一些基本等价式和蕴涵式进行证明；（4） 任取解释I，如果I满足G，往证I也满足H；（5） 反证法，设结论假，往证前提假.6 证

19、明下列蕴涵式：.证法一：公式的真值表如下：PQ00011010111000111111可见是恒真的，所以.证法二：故是恒真的，所以.证法三：利用基本蕴涵式（1）与（3）有：.证法四：设结论为假，即是假的，于是P是真的而Q是假的，从而是假的. 因此，结论成立.例子：证明蕴涵式 PQR000111111001111111010011111011111111100110011101110111110001001111111111第七讲 范式（第二章第四节）一、析取范式和合取范式1 原子或原子的否定称为文字，例如P，等.2 有限个文字的析取式称为一个子句；有限个文字的合取式称为一个短语.3 定义：有限

20、个短语的析取式称为析取范式；有限个子句的合取式称为合取范式.4 例子：P，是析取范式；而P，是合取范式.5 定理1及如何求一个公式的析取范式和合取范式.二、主析取范式1 设是n个不同的原子，一个短语如果恰好包含所有这n个原子或其否定，且其排列顺序与的顺序一致，则称此短语为关于的一个极小项.2 共有个不同的极小项.3 例子：有3个不同的原子P,Q,R，则是极小项.4 书本定义2.4.5：主析取范式的定义5 定理2.4.2：对于命题公式G，都存在等价于它的主析取范式.6 主析取范式的求法及应用例子：求下列公式的主析取范式：知识回顾：若G在一组解释下为真，则对应主析取范式中的一个极小项，具体的作法如

21、下：a) 在此解释中原子的真值是1时，极小项取它自身；b) 在此解释中原子的真值是0时，极小项取它的否定.解：应用真值表法求其主析取范式.的真值表如下：PQ00101011011000011111由上表可知G的主析取范式为：. 是可满足的.第八讲 谓词和谓词公式（第三章第一、二节）一、谓词1 个体：可以独立存在的物体称为个体（它可以是抽象的，也可以是具体的）.2 定义3.1.2（P57）：设D是非空个体名称的集合，定义在上取值于1, 0的n元函数，称为n元命题函数或n元谓词.其中表示集合D的n次笛卡儿乘积.3 谓词逻辑包括命题逻辑.二、量词1 全称量词：语句“对任意x”称为全称量词，记作“”.

22、2 存在量词：语句“存在一个x”称为存在量词，记作“”.3 设是一元谓词，任取，则是一个命题. 于是是这样一个命题“对任意，都有”.4 对的真值作如下规定：取1值对任意， 都取1值；取0值有一个， 使取0值.5 设是一元谓词，是这样一个命题“存在一个，使得成立“. 对的真值作如下规定：取1值有一个， 使取1值；取0值对任意， 都取0值.例子：设，则下列公式中，（ ）的真值为1.A B C D 6 定义3.1.4：在一个由谓词、量词、逻辑联结词和括号组成的有意义的符号串（实际是指下一节将严格定义的公式）中，变量的出现说是约束的，当且仅当它出现在使用这个变量的量词范围之内；变量的出现说是自由的，当

23、且仅当这个出现不是约束的.7 例子：，从左到右算起，变量x的第一、二次出现是约束的，第三次出现是自由的；变量y, z的出现是自由的.8 定义3.1.5：变量说是约束的，如果至少一个它的出现是约束的；变量说是自由的，如果至少一个它的出现是自由. 例如上例中，x既是约束变量也是自由变量，y, z是自由变量.9 会判断一个变量的出现是约束的还是自由的.三、谓词公式1 在形式化中，我们将使用如下4种符号：（1） 常量符号：用小写英文字母a, b, c, .表示. 当个体名称集合D给出时，它可以是D中的某个元素；（2） 变量符号：用小写英文字母x, y, z, .表示. 当个体名称集合D给出时， D中任

24、何元素可代入变量符号；（3） 符号函数：用小写英文字母f, g，.表示. 当个体名称集合D给出时， n元函数符号可以是到D的任意一个映射；（4） 谓词函数：用大写英文字母P, Q, R,.表示. 当个体名称集合D给出时， n元谓词符号可以是上的任意一个谓词.2 定义3.2.1：谓词逻辑种的项，被递归定义为：（1） 常量符号是项；（2） 变量符号是项；（3） 若是n元函数符号，是项，则是项；（4） 所有项都是有限次使用（1），（2），（3）生成的符号串.3 定义3.2.2：若是n元谓词符号，是项，则是原子.4 定义3.2.3：谓词逻辑中的公式，被递归的定义为：（1） 原子是公式；（2） 若G,

25、H是公式，则是公式；（3） 若G是公式，x是G中的自由变量，则是公式；（4） 所有公式都是有限次使用（1），（2），（3）生成的符号串.5 定义3.2.4：谓词逻辑中公式G的一个解释I，是由非空区域D和对G中常量符号、函数符号、谓词符号以下列规则进行的一组指定组成：（1） 对每个常量符号，指定D中一个元素；（2） 对每个n元函数符号，指定一个函数，即指定到D的一个映射；（3） 对每个n元谓词符号，指定一个谓词，即指定到0, 1的一个映射.6 公式G在解释I下的真值记作.7 定义3.2.5：公式G 称为是可满足的，如果存在解释I，使G在I下取1值，简称I满足G. 若I不满足G，则称I弄假G.8

26、定义3.2.6：公式G称为恒真的，如果G的所有解释I都满足G.；公式G称为恒假的（或不可满足的），如果不存在解释I满足G.9 例子：对公式，给出如下的解释I：D=2, 3； 于是，公式在I下的值为：.第九讲 谓词公式的等价关系与蕴涵关系（第三章第三节）1 定义3.3.1：公式G, H称为等价，记作G=H，如果公式是恒真的.2 公式G, H等价的充要条件是：对G, H的任意解释I，G, H在I下的真值相同.3 定义3.3.2：设G, H是公式，称G蕴涵 H，或H是G的逻辑结果，如果公式是恒真的，记作.4 公式G蕴涵H的充要条件是：对任意解释I，若I满足G，则I必满足H.5 G=H的充要条件是且.6 两个基本等价式：（1）；（2）.7 证明等价式：. 证明： 第十讲 图 （第四章第一、二、六节）一、基本概念1 图：称G=(P.,L)为图，如果P是点的非空集合，L是连接不同点对的边集合，并且任意一对不同点对之间最多有一条边. P(G)表示G的点集合，L(G)表示G的边集.2 点相邻的定义3 空图4 完全图：若G中任两点之间恰有一条边，则称G为完全图. N个顶点的完全图恰有条边.5 任意图G，其边数|L(G)|满足.6 度：设G是图，则L(G)中以v为端点的边的条数称为点v的度，记为.7 定理4.1.1： 设G=(P.,L)是有限图，设|L(G)|m，于是.8