1、离散数学串讲第一章 命题逻辑 1.1 命题及其表示方法 1.2 联结词 1.3 命题公式与翻译 1.4 真值表与等价公式 1.5 重言式与蕴含式 1.6 其它联结词 1.7 对偶与范式 1.8 推理理论1.1 命题及其表示方法命题：具有确定真值的陈述句命题的类型（原子命题和复合命题）命题语句的形式（陈述句）命题的表示（一个命题标识符（比如P）表示确定的命题）1.2 联结词1. 否定 2.合取 （TT T）3. 析取 （FF F）4. 条件 (TF F)5. 双条件 (同T异F)1.3 命题公式与翻译命题公式 所谓命题的符号化就是把一个用文字叙述的句子相应地写成由命题标识符、联结词和括号表示的合
2、式公式。 符号化应该注意下列事项: 确定给定句子是否为命题。 句子中连词是否为命题联结词。 要正确地表示原子命题和适当选择命题联结词。 命题符号化的重要性 命题符号化是很重要的，一定要掌握好，在命题推理中最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。 1.4 真值表与等价公式真值表的构造方法1) 找出公式中所含的全体命题变元P1, P2, , Pn, (若无下角标就按字典顺序排列), 列出2n个赋值. 赋值从000开始, 然后按二进制加法依次写出各赋值, 直到111为止. (2) 按从低到高的顺序写出公式的各个层次. (3) 对应各个赋值计算出各层次的真值, 直到最后计算
3、出公式的真值. 等价公式 等价式的判别方法 真值表法 等价演算法基本等价式 (1)对合律（双重否定）： PP (2)幂等律：PPP，PPP (3)结合律：(PQ)RP(QR)， (PQ)RP(QR) (4)交换律：PQQP，PQQP (5)分配律：P(QR)(PQ)(PR)， P(QR)(PQ)(PR) (6)德摩根律： (PQ) PQ， (PQ) PQ (7)吸收律： P(PQ)P，P(PQ)P (8)同一律： PTP，PFP (9)零 律： PFF，PTT (10)否定律： PPF，PPT (11) 条件式转化律： PQPQ， PQQP (12) 双条件式转化律： PQ (PQ)(QP)
4、(PQ)(PQ) (PQ) PQ PQ (13) 输出律(CP规则)： P(QR) (PQ)R1.5 重言式与蕴含式 定义1-5.1 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为真，则称该命题公式为重言式或永真公式。矛盾式（永假式） 定义1-5.2 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为假，则称该命题公式为矛盾式或永假公式。可满足式 如果命题公式既不是重言式，也不是矛盾式，则称该命题公式是可满足式。定理 任何两个重言式的合取或析取，仍然是一个重言式。定理 一个重言式，对同一分量都用任何合式公式置换，其结果仍为一重言式。 （代入规则） 等价 设 A 、B 为两个
5、命题公式, A B 当且仅当 A B 为一重言式。 蕴含 定义1-5.3 当且仅当PQ 是一个重言式，我们称“P 蕴含 Q” ， 或“Q 是P 的有效结论” ，并记作 P Q. 等价与蕴含的关系 设P、Q为任意两个命题公式，P Q 的充要条件是 P Q 且 Q P.常用的蕴含式 1.附加规则： P(PQ)，Q(PQ) 2.化简规则： (PQ)P, (PQ)Q 3.合取引入规则：P ,QPQ 4.假言推理： P (PQ) Q 5.拒取式（反证法）： Q (PQ) P 6.析取三段论（排除法）：Q (PQ) P 7.假言三段论（传递性）：(PQ)(QR)(PR) 8.二难推论： (PR)(QR)(
6、PQ)R /简单型 (PR)(QS)(PQ)(RS) /复杂型 9.等价三段论：( PQ)(QR)(PR) 10. (PQ)(RS)(P R) (Q S)1.6 其它联结词1. 不可兼析取2. 条件否定3. 与非 4. 或非 全功能联结词组：任一个公式都可以用仅含联结词组中的联结词表示最小全功能联结词组：, 或,1.7 对偶与范式对偶式 定义1-7.1 在给定的命题公式 A 中，将联结词 换成 ，将 换成 ，若有特殊变元 F 和 T 亦相互取代，所得公式 A* 称为 A 的对偶式。 如果 A B, 则 A* B*。合取范式 定义1-7.2 一个命题公式称为合取范式，当且仅当它具有型式： A1
7、A2 An ( n 1) 其中，A1 , A2, , An 都是由命题变元或其否定所组成的析取式。析取范式 定义1-7.3 一个命题公式称为析取范式，当且仅当它具有型式：A1 A2 An ( n 1) 其中，A1 , A2, , An 都是由命题变元或其否定所组成的合取式。范式的求法 将公式中的联结词化归成 。 利用德摩根律将 消去或内移。 利用分配律、结合律将公式归约为合取(析取)范式。主范式 一个命题公式的合取范式或析取范式并不是唯一的。 那么，如何使任意一个命题公式化成唯一等价命题的标准形式呢？ 解决方案：主范式 （主析取范式和主合取范式） 主析取范式 定义1-7.4（小项）n 个命题变
8、元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。 定义1-7.5 对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的主析取范式。 主析取范式的求法 等价演算法 化为析取范式。 除去其中所有永假的合取式。 在合取式中合并相同的命题变元。 对合取式补入没有出现的命题变元，即添加（P P）式，然后应用分配律展开公式。 除去相同的小项，并将小项按编号由小到大的顺序排列。主析取范式的用途 判别命题公式的类型 永真式：包含所有的小项 矛盾式：没有小项 可满足式：包含部分小项 给出命题公式的成真赋值或成假赋值 成真赋值：出现的
9、小项对应的真值指派 成假赋值：没有出现的小项对应的真值指派 判别两个命题公式是否等价例 判断命题公式的类型 1. (PQ) Q 2. (PQ) Q 1. (PQ) Q (PQ) Q P Q Q P F F 2. (PQ) Q (PQ) Q (P Q) Q (P Q) (Q T) (P Q) (Q (PP) (P Q) (Q P) (Q P) (P Q) (P Q) 1,3主合取范式 定义1-7.6（大项）大项n 个命题变元的析取式，称作布尔析取或大项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。 定义1-7.7 对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成
10、，则该等价式称作原式的主合取范式。 主合取范式的求法 等价演算法 化为合取范式。 除去其中所有永真的析取式。 在析取式中合并相同的命题变元。 对析取式补入没有出现的命题变元，即添加（P P）式，然后应用分配律展开公式。 除去相同的大项，并将大项按编号由小到大的顺序排列。主合取范式的用途 判别命题公式的类型 永真式：没有大项 永假式：包含所有的大项 可满足式：包含部分大项 给出命题公式的成真赋值或成假赋值 成真赋值：没有出现的大项对应的真值指派 成假赋值：出现的大项对应的真值指派 判别两个命题公式是否等价1.8 推理理论 定义1-8.1 设 A 和 C 是两个命题公式，当且仅当 A C 是一重言
11、式，即A C，称 C 是 A 的有效结论。 论证方法： 真值表法 直接证法 间接证法1. 真值表法 从真值表上找出 H1 , H2 , , Hn 真值均为 T (1)的行，对每一个这样的行，若 C 的真值也为 T(1), 则 H1 H2 Hn C 成立。 或看 C 为 F (0) 的行, 在每个这样的行中， H1 , H2 , , Hn 真值中至少有一个为 F(0), 则 H1 H2 Hn C 也成立。2. 直接证法 由一组前提, 利用一些公认的推理规则,根据已知的等价或蕴含式, 推演得到有效的结论。 P 规则:前提在推导过程中任何时候都可引用、使用。 T 规则:在推导中,若有一个或多个公式重
12、言蕴含着公式 S, 则 S 可引入推导中。3. 间接证法 欲证H1 H2H m C, 即只要证明公式 H1 H2H m C永假 CP 规则欲证H1 H2H m（RC）, 即只要证明公式 （H1 H2H mR） C永真第二章 谓词逻辑 2.1 谓词的概念与表示 2.2 命题函数与量词 2.3 谓词公式与翻译 2.4 变元的约束 2.5 谓词演算的等价式与蕴含式 2.6 前束范式 2.7 谓词演算的推理理论2.1 谓词的概念和表示2.2 命题函数与量词全称量词 ：称为全称量词，用以表达“对所有的”，“每一个”，“对任一个”等。 对于 ，表示客体变化范围的特性谓词通常作为条件联接词的前件。例：每个学
13、生都要参加考试。 P(x): x 是学生，Q(x): x 要参加考试， (x) (P(x) Q(x)存在量词 ：称为存在量词，用以表达“存在一些”，“至少有一个”，“对于一些”等。 对于 ，表示客体变化范围的特性谓词通常作为合取项。例： 有一些人是聪明的 M(x): x 是人，R(x): x 是聪明的。 (x)(M(x) R(x)2.3 谓词公式与翻译2.4 变元的约束 给定一个谓词公式，其中有一部分公式的形式为： (x) P(x) 或 (x) P(x) 。 这里 、 后面的 x 叫做量词的指导变元（作用变元） ，P(x) 叫做相应量词的作用域（辖域） 。 在作用域中 x 的一切出现称为 x
14、在公式中的约束出现，x 称为约束变元 。 在公式中除去约束变元之外所出现的变元称作自由变元 。 约束变元的换名规则： 1) 换名范围:量词中的指导变元和作用域中出现的该变元.公式中其余部分不变. 2) 要换成作用域中没有出现的变元名称.自由变元代入的规则： 1) 对该自由变元每一处进行代入. 2) 代入的变元与原公式中所有变元名称不能相同.有限的个体域 量词作用域中的约束变元，当论域的元素是有限时, 客体变元的所有可能的取代是可枚举的。 设论域的元素是 a1,a2,an，则 xA(x) A(a1) A(an) xA(x) A(a1) A(an)2.5 谓词演算的等价式与蕴含式等价 定义2-5.
15、1 给定任何两个谓词公式wff A 和 wff B，设它们有共同的个体域 E, 若对 A 和 B的任一组变元进行赋值，所得命题的真值相同，则称谓词公式 A 和 B 在 E 上是等价的，并记作：A B永真的、不可满足的、可满足的 定义2-5.2 给定任意谓词公式wff A，其个体域为 E，对于 A 的所有赋值， wff A 都真,则称 wff A 在 E 上是永真的(有效的)。 定义2-5.3 一谓词公式 wff A，若在所有赋值下都为假，则称 wff A 是不可满足的。 定义2-5.4 一谓词公式 wff A，若至少在一种赋值下为真，则称 wff A 是可满足的。谓词演算的等价式(1) 量词分
16、配律 (x)(A(x)B(x)(x)A(x)(x)B(x) (x)(A(x)B(x)(x)A(x)(x)B(x)(2) 量词否定律 (x)A(x)A (x)A(x)A3）量词作用域的扩张与收缩律 (x)(A(x)B)(x)A(x)B (x)(A(x)B)(x)A(x)B (x)(A(x)B)(x)A(x)B (x)(BA(x)B(x)A(x) (x)(A(x)B)(x)A(x)B (x)(A(x)B)(x)A(x)B (x)(A(x)B)(x)A(x)B (x)(BA(x)B(x)A(x)（4）其他等价式谓词演算的蕴含式 (x)A(x)(x)B(x)(x)(A(x)B(x) (x)(A(x)B
17、(x)(x)A(x)(x)B(x) (x)(A(x) B(x)(x)A(x) (x)B(x) (x)(A(x)B(x)(x)A(x)(x)B(x) (x)(A(x)B(x)(x)A(x)(x)B(x) (x)A(x)(x)B(x) (x)(A(x)B(x) (x)A(x) (x)A(x)2.6前束范式 定义2-6.1 一个公式若量词均在全式的开头,作用域延伸到整个公式,则该公式叫做前束范式.前束合(析)取范式范式存在定理 定理2-6.1 任何一个谓词公式均有与其等价的前束范式。 定理2-6.2 任何一个谓词公式均可转为与其等价的前束合取范式。 定理2-6.3 任何一个谓词公式均可转为与其等价的
18、前束析取范式。前束范式的求法 通常先消去条件和双条件联结词； 把否定深入到原子公式的前面； 在需要的时候进行约束变元换名或自由变元代入； 把量词移到全式的最前面。练习 求前束范式x(F(x) yG(x,y) xH(x,y) x(F(x) yG(x,y) xH(x,u) x(F(x) yG(x,y) xH(x,u) x(F(x) yG(x,y) H(x,u) xy(F(x) G(x,y) H(x,u)2.7 谓词演算的推理理论消去(添加)量词的规则1) 全称指定规则 US xA(x) A(c) c是论域中某个任意客体. 如果个体域的所有元素都具有性质A，则个体域中的任一个元素具有性质A。2) 全
19、称推广规则 UG A(c) xA(x) 必须能够证明对于每个c, A(c)都为真. 如果个体域中任意一个个体都具有性质A，则个体域中的全体个体都具有性质A.3) 存在指定规则 ES xA(x) A(c) c是论域中使A(c)为真的客体. 如果个体域中存在有性质A的元素，则个体域中必有某一元素c具有性质A.4) 存在推广规则 EG A(c) xA(x) c是论域中使A(c)为真的客体. 如果个体域中某一元素c具有性质A，则个体域中存在着具有性质A的元素。例 设个体域为人，试证明：任何人如果他喜欢音乐，他就不喜欢体育。每个人或者喜欢体育，或者喜欢美术。有的人不喜欢美术。因此有的人不喜欢音乐。设：喜
20、欢美术，：喜欢体育，：喜欢音乐。论域：人。命题形式化为：前提：， 结论：。证明：（1） P (2) ES(1) (3) P (4) US(4) (5) T(2)(4)I (6) P (7) US(6) (8) T(5)(7)I (9) EG(8)第三章 集合与关系 3.1 集合的概念和表示法 3.2 集合的运算 3.4 序偶与笛卡儿积 3.5 关系及其表示 3.6 关系的性质 3.7 复合关系和逆关系 3.8 关系的闭包运算 3.9 集合的划分和覆盖 3.10 等价关系与等价类 3.12 序关系3.1 集合的概念和表示法 集合与元素 集合的势 集合的表示法 集合相等 子集、全集、 空集 幂集
21、3.2 集合的运算 集合的交 集合的并 集合的相对补（差） 集合的绝对补（补） 集合的对称差 3.4 序偶与笛卡儿积序偶：具有确定次序的两个元素的集合，记为笛卡尔乘积 3.5 关系及其表示关系(二元关系) : 任一序偶的集合,确定了一个二元关系R.X到Y的关系: X Y 的任何子集,都定义一种关系 R，称作 X 到 Y 的关系. 若 X=Y,则 R 为集合 X 上的关系域(前域) Dom(R)X 值域Ran(R)Y关系的表示方法关系矩阵和关系图3.6 关系的性质 1.自反性(reflexive) 2.反自反性(irreflexive) 3.对称性(symmetric) 4.反对称性(antis
22、ymmetric) 5.传递性(transitive)在关系矩阵中 自反性 对角线上的所有元素都是1. 反自反性 对角线上的所有元素都是0. 对称性 关系矩阵是对称的. 反对称性 以主对角线对称的元素不能同时为1. 传递性 较难判断.在关系图中 自反性 每点必有一闭路. 反自反性 任一结点,均无闭路. 对称性 结点间若有边,必是往返两条. 反对称性 若两点间有边,只会是一条,没有返回边. 传递性 若从结点a 到结点 b 有长度大于 1 的路,则从 a 到 b 必有长度为 1 的路存在.3.7复合关系和逆关系复合关系设 R 是从 X 到 Y 的关系, S 是从 Y 到 Z 的关系,则 RS 称为
23、 R 和 S 的复合关系(合成关系), 表示为逆关系设 R 为 X 到 Y 的二元关系,如将 R 中每一序偶的元素顺序互换,所得到的集合称为 R 的逆关系.记作 RC定理 R 为 X 上的二元关系,则a) R 为对称的充分必要条件是 R = RC; b) R 为反对称的充分必要条件是 R RC IX ;c) R是自反当且仅当 IX R；d) R是反自反当且仅当 R IX = ；e) R是传递当且仅当 R o R R.3.8 关系的闭包运算自反（对称、传递）闭包：X 上的关系 R的自反（对称、传递）闭包 就是包含 R 的 X 上最小的 自反（对称、传递）关系用Warshall算法求传递闭包3.9
24、 集合的划分和覆盖 覆盖与划分 3.10 等价关系与等价类 等价关系：自反、对称、传递的关系。 等价类：设 R 为集合 A 上的等价关系,对任何 a A, aR = x | xA aRx 商集：等价类的集合。 等价关系与划分：集合 A 上的等价关系与其划分是一一对应的。 3.12 序关系偏序关系：自反的、 反对称的、传递的关系y 盖住 x在偏序集合 中，如果 x , y A, x y, x y, 且没有其他元素 z,满足x z, z y, 则称元素 y 盖住元素 x . 并且记 COVA=| x, y A; y 盖住 x. 哈斯图是简化的关系图： (1)自反性：每个顶点都有自回路，省去自回路。
25、(2)反对称性：从小到大安置顶点，可省略箭头。(3)传递性： 由于有，R 则R，故只画，对应的边，省略边。链（反链）极大元（极小元）最大元（最小元）上界（下界）上确界（下确界）第四章 函数 4.1 函数的概念 4.2 逆函数和复合函数 4.1 函数的概念函数的概念 任何两个集合 X 和 Y , f 是 X 到 Y 的 一个关系，若对每个 x X, 有唯一y Y 使得 f, 称关系 f 为函数(映射)。函数与关系 函数的定义域是X, 而不是X 的 某个真子集； 一个 x 只能对应于唯一的 y ； X Y 的子集并不都能成为 X 到 Y 的函数。函数相等 设函数 f: A B、 g: C D,如果
26、A=C , B=D , 且对于所有 x A 和 x C有 f(x) = g(x) , 则称函数 f 和 g相等，记作 f = g 。特殊的函数：入射、满射、双射4.2 逆函数和复合函数 逆函数（反函数） 设f:XY是一个双射函数, 称Y X的双射函数f c是f的逆函数(反函数),记为f -1.复合函数第五章 代数结构 5.1 代数系统的引入 5.2 运算及其性质 5.3 半群 5.4 群和子群 5.5 阿贝尔群和循环群5.1 代数系统的引入5.2 运算及其性质运算的性质 设 , 是定义在集合 A 上的二元运算, 如果对于任意的x, y, z A, 1 若总有x y A，则称二元运算 在A上是封
27、闭的； 2 若总有 x y = y x ，则称 是可交换的； 3 若总有 (x y ) z = x (y z)，则称 是可结合的； 4 若总有 x (y z) = (x y ) (x z) (y z ) x = (y x ) (z x) 则称运算 对 是可分配的； 5 若总有 x (x y) = x x (x y) = x 则称运算 和运算 满足吸收律； 6 若总有 x x = x，则称运算 是幂等的。幺元 设 是定义在集合 A 上的二元运算, 若有e A , 对于任意的 x A , e x = x e = x定理 设 是定义在集合 A 上的二元运算, 且在 A 中有关于运算 的左幺元 el 和右幺元 er ，则 el = er = e，且 A 中的幺元是唯一的。 零元 设 是定义在集合 A 上的二元运算, 若有 A , 对于任意的 x A , x = x = 定理 设 是定义在集合 A 上的二元运算, 且在 A 中有关于运算 的左零元 l 和右零元 r
