第11章 离散结构本章要点：离散结构的研究对象及主要内容 数理逻辑与简单推理 集合论基础知识 代数结构 图论基本知识 离散概率 数值分析特点与方法 运筹学概念与步骤 数学建模与计算机模拟的概念与步骤 11.1离散结构的研究对象及 主要内容 1.研究对象 离散数量关系以及离散系统结构的数学模型以 及建模方法 。 2.研究的主要内容传统离散数学包含的数理逻辑、集合论、代数 结构和图论等四个部分，以及计算机应用对象的离 散结构的研究，离散概率、运筹学、数值计算、数 学建模与模拟等。 11.2 数理逻辑 1.命题逻辑 离散数量关系以及离散系统结构的数学模型以 及建模方法 。 命题 在数理逻辑中，称能够分辨真假、但不能同时既真又假 的陈述句为命题 。 原子命题 在命题中，有些命题是简单的陈述句，并且它们不能够 被分成更为简单的陈述语句，这样的命题称为简单命题，或 者原子命题。 11.2 数理逻辑 (2) 复合命题 一个简单命题再加上了一个表示否定的连接词形成的复合命题。简单命题与复合命题都可以用简单的英文字母来表示。例 用Q表示命题：8是奇数！用P表示命题：李平不是学生。构成复合命题的连接词 否定连接词，记作“ ” 合取连接词，也称“与”，记作“” 或取连接词，也称“或”，记作“” 蕴涵连接词，也称“条件”，记作“” 等价连接词，也称“双条件”，记作“ ” 11.2 数理逻辑 命题公式命题常元、命题变元与各种逻辑连接词组合形成的更 为复杂的命题，就可以称为命题公式，又叫做合式公式。 命题常元 单个的已知命题(可以是具体的命题、常真命题、常假 命题) 。 (2) 命题变元 不代表具体命题的、但是取值范围仍然为“真”与“假”或 “1”与“0”的符号表示的命题 。11.2 数理逻辑 等值演算 命题常元、命题变元与各种逻辑连接词组合形成的更 为复杂的命题，就可以称为命题公式，又叫做合式公式。 重言式 如果对命题公式A中命题变元的一切指派，A的真值均 为真，则称命题公式A为重言式，重言式又称永真式。 (2) 等价式 设A,B为两个命题公式，若等价式A B是重言式，则 称A逻辑等价于B，或A与B是等值的，记作A B。A B不 是命题公式。 11.2 数理逻辑 命题推理 推理是从前提出发推出结论的思维过程，前提是已知 的命题公式，结论是从前提出发应用推理规则推出的命题公 式。 真值表法 等价证明法 构造证明法 11.2 数理逻辑 例 证明PQ和 Q的结论是P。 证明：只需证明(PQ) QP是重言式。 真值表法按真值表的构造步骤，构造真值表如下：(PQ)(PQ)P QPQ Q Q Q P 0 0 0 101 0 11 001 1 01 111 1 11 00111.2 数理逻辑 例 证明PQ和 Q的结论是P。 证明：只需证明(PQ) QP是重言式。 等价证明法 (PQ) QP (P Q) Q Q)P(P Q)PPQ PTQT 11.2 数理逻辑 例证明：pr, qs, pq rs 。 证明： 构造证明法 1) pr前提 2) pr1) 等价置换 3) r p2) 等价置换 4) r p3) 等价置换 5) pq前提 6) p q5) 等价置换 7) p q6) 等价置换 8) r q4)7)假言三段论 9) qs前提 10) r s8)9)假言三段论 11) rs 10) 等价置换 11.2 数理逻辑 2.谓词逻辑 是对简单命题做进一步的分解，分析命题内部的逻辑结构和命题间的内在联系，它是命题逻辑的扩充和发展。 个体词 原子命题中所描述的对象，是可以独立存在的客体，可以是具体的，也 可以是抽象的。 谓词 用来描述个体词的性质或个体词之间关系的词。 量词 表示个体常元或变元之间数量关系的词称为量词。 11.2 数理逻辑 全称量词 全称量词表示“所有的”，“每一个”，“对任何 一个”，“一切”，“任意的”。符号为“”。 (2) 存在量词 表示“存在着”，“有一个”，“至少有一个”，“ 存在一些”，“对于一些”，“某个”等。符号为“”。 11.2 数理逻辑 例 将以下命题用谓词逻辑符号化。 (1) 所有的自然数都是大于零的。 (2) 没有不犯错误的人。 (3) 这个班有些学生请假了。 解：(1) 设A(x)：x是自然数；B(x)：x大于零。则原命题符号化为： x(A(x) B(x)。 (2) 设A(x)：x是人；B(x)：x犯错误。则原命题符号化为： x(A(x) B(x)。 (3) 设A(x)：x是这个班的学生； B(x)：x请假了。则原命题符号化为： x(A(x)B(x)。 11.2 数理逻辑 谓词推理 谓词逻辑推理是命题逻辑推理的推广。谓词逻 辑的推理也是利用命题公式间的各种等价关系、蕴 涵关系，通过一些推理规则，从已知命题公式推出 一些新的公式。 11.3 集合论 1.集合的基本概念与运算 是对简单命题做进一步的分解，分析命题内部的逻辑结构和命题间的内在联系，它是命题逻辑的扩充和发展。 集合的概念与表示 事物汇集在一起组成的一个整体叫做集合，而这些事物 就可以称为这个集合的元素或者成员。集合通常用大写的英文字母来标记。 表示一个集合的方法 列举法 ：A1,2,3,n, 描述法 ：Bx|x是大于等于8的正整数 11.3 集合论 集合间关系 设A ，B是集合，如果B中的每个元素都是A中的元素，则称B是A的子集 合，简称子集。这时也称B被A包含，或A包含B。 设A，B为集合，如果A B且B A，则称A与B相等，记作AB 。设A，B为集合，如果BA且BA，则称B是A的真子集。记作B A。 不含任何元素的集合叫做空集，记作。 给定集合A，由集合A的所有子集为元素组成的集合，称为集合A的幂集 ，记作P(A) 。在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个 集合为全集，记作E(或U)。 11.3 集合论 集合运算 (1) 定义：设A与B为集合，A与B的并运算、交运算、差运 算 - ，分别定义为，AB=x|(x A) (x B)AB=x|(x A) (x B)A - B =x|(x A) (x B) (2) 定义：设E为全集，A E，则A的补运算，记作，定义为 ，AE -AxxExA 或 AxxA (3) 定义：设A与B为集合，A与B的对称差，记作，定义为， AB(AB)(AB 11.3 集合论 2.关系与函数 笛卡儿积 (1) 序偶由两个元素x和y(允许x =y)按一定的顺序排列成的二 元组叫做一个有序对(也称序偶)，记作，其中x是它的第 一元素，y是它的第二元素。有序对的特点： 当x y时，。 两个有序对相等，即 的充分必要条件 是xu且yv。 11.3 集合论 (2)笛卡儿积 设A，B为集合，用A中元素作为第一元素，B中元素 作为第二元素，构成有序对，所有这样的有序对组成的集合 叫做A和B的笛卡儿积，记作AB。符号化表示为AB(x,y)|xAyB 例 有两个集合Aa,b，B0,1,2，则AB,BA, 11.3 集合论 二元关系 (1) 二元关系定义如果一个集合为空集或者它的元素都是有序对，则称这个集合是一 个二元关系，一般记作R。对于二元关系R，如果有序对R，则记作x R y 。设A,B为集合，AB的任何子集所定义的二元关系称作从A到B的二元关系，特别当AB时，则叫做A上的二元关系。 3种特殊的关系：其中之一就是空集，称做空关系。另外两种就是全域关系EA和恒等关系IA。对任何集合A， EAxAyAAA IAxA 11.3 集合论 (2) 关系的表示通常用关系图来表示一个关系。 例 A=1,2,3,4，R=,，可以画出如下的关系 图。11.3 集合论 (3) 关系的基本运算Dom(R)x y(R)Ran(R)y | x(R) F的逆记作：|F。 F与G的左复合记作F G，F G z(GF) F与G的右复合记作F G，F G z(FG) 11.3 集合论 (4) 关系的性质 自反性 若对于任意x属于集合A，都有 ，那么，就说R在A上是自反的。 反自反性 若对于任意x属于集合A，都不存在 ，那么，就说R在A上是反自 反的。 对称性 若对于任意x,y属于集合A，都有 R ，那么，就 称R为A上的对称关系。 反对称性 若对于任意x,y属于集合A，都不存在 R ，那么，就称R 为A上的反对称关系。 例如A上的全域关系，恒等关系，空关系都是A上的对称关系。而恒等关系和空 关系也是A上反对称关系。 传递性 若对任意的x,y,z都属于集合A，假如都存在 ，那么，就称R为A上的传递关系。 11.3 集合论 (5) 两类重要的二元关系 等价关系设R为非空集合A上的二元关系，若R具有自反性、对称 性和传递性，则称R为A上的等价关系。利用等价关系，可以对一些对象进行分类。例如，集合 上的恒等关系即是等价关系。 偏序关系 设R为非空集合A上的二元关系，若R具有自反性、反对 称性和传递性，则称R为A上的偏序关系，偏序关系可以记为 。集合A和A上的偏序关系R一起叫做偏序集，记为(A,)，如果 有(a,b)R，可以表示为ab 。根据偏序关系可以画出关系图，通常称为哈斯图。 11.3 集合论 例 已知为偏序集，集合A=a,b, c,d,e,f，关系 =(b,a),(d,b),(c,a), (e,c),(e,b),(d,a),(e,a)，画出关系的哈斯图。 解：按照偏序集哈斯图的规则，可以得到如下哈斯图。11.3 集合论 函数 (1) 函数的定义设F为二元关系，若对于任意的x，都存在惟一的让xFy成立，则称F为函数。对于任意函数F，如果都有xFy，则记做，并称y为F在x上的值。 (2) 函数的性质 设函数f :AB 若对于任何的x1,x2A，x1x2，都有f(x1)f(x2)，则称f是单射的。若Ran(f)B，则称f是满射。若f既是满射的，又是单射的，则称f是双射的。 11.3 集合论 (3) 特殊函数复合函数 设f是从集合A到集合B的函数，g是从集合B到集合C的 函数，f和g的复合用f g 表示为f g =(a,c)|aAcCb(bB)(a,b)f(b,c)g 反函数 设函数f是集合X到集合Y的一个双射函数。则f