计算机科学导论第12章 离散结构

第12章离散结构2计算机科学导论学习目标了解离散结构的研究对象及主要内容、代数结构、离散概率。掌握数理逻辑与简单推理、集合论基础知识、图论基本知识。第12章离散结构3计算机科学导论12.1离散结构的研究对象及主要内容离散结构(DiscreteStructure)是现代数学的一个重要学科，它所涉及的概念、方法和理论，被大量应用于计算机科学与技术的研究。本章将系统介绍传统离散数学包含的数理逻辑、集合论、代数结构、图论等4部分的基本内容，使读者初步了解离散结构的基本知识。4计算机科学导论12.1.1离散结构的研究对象离散结构的研究对象是离散量的结构和相互关系，以及离散系统结构的数学模型以及建模方法。5计算机科学导论12.1.2离散结构研究的主要内容离散结构研究的内容主要有传统离散数学包含的数理逻辑、集合论、代数结构和图论等4个部分，另外还包括计算机应用对象的离散结构的研究，离散概率、运筹学、数值计算、数学建模与模拟等。6计算机科学导论12.2数理逻辑12.2.1命题逻辑命题在数理逻辑中，称能够分辨真假、但不能同时既真又假的陈述句为命题。原子命题在命题中，有些命题是简单的陈述句，并且它们不能够被分成更为简单的陈述语句，这样的命题称为简单命题，或者原子命题。7计算机科学导论例如：8是奇数！李平是学生。这两个命题都属于简单命题。再看另外一个例子：李平不是学生。该命题就不是简单命题。因为这个命题不是最简单的陈述句，还可以从这个句子里面分离出来一个“不”字，把“不”字分出来以后，它依然是命题。因此可以把这个命题看作是由一个简单命题再加上了一个表示否定的连接词形成的复合命题。8计算机科学导论12.2.1命题逻辑复合命题一个简单命题再加上了一个表示否定的连接词形成的复合命题。简单命题与复合命题都可以用简单的英文字母来表示。[例]用Q表示命题：8是奇数！用P表示命题：李平不是学生。构成复合命题的连接词①否定连接词，记作“”②合取连接词，也称“与”，记作“∧”③或取连接词，也称“或”，记作“∨”④蕴涵连接词，也称“条件”，记作“→”⑤等价连接词，也称“双条件”，记作“”9计算机科学导论2．命题公式由命题常元、命题变元与各种逻辑连接词组合形成的更为复杂的命题，称为命题公式，又称为合式公式。3．等值演算(1)重言式如果对命题公式A中命题变元的一切指派，A的真值均为真，则称命题公式A为重言式，重言式又称永真式。(2)等价式设A,B为两个命题公式，若等价式AB是重言式，则称A逻辑等价于B，或A与B是等值的，记作AB。AB不是命题公式。12.2.1命题逻辑10计算机科学导论4．命题推理推理是从前提出发推出结论的思维过程，前提是已知的命题公式，结论是从前提出发应用推理规则推出的命题公式。推理常用的方法:真值表法等价证明法构造证明法12.2.1命题逻辑11计算机科学导论[例]证明P∨Q和Q的结论是P。证明：只需证明(P∨Q)∧Q→P是重言式。①真值表法按真值表的构造步骤，构造真值表如下：PQP∨QQQQ→P00010101100110111111100112.2.1命题逻辑12计算机科学导论[例]证明P∨Q和Q的结论是P。证明：只需证明(P∨Q)∧Q→P是重言式。②等价证明法(P∨Q)∧Q→P(P∧Q)∨(Q∧Q)→P(P∧Q)∨0→P(P∧Q)→P(P∧Q)∨PP∨Q∨P1∨Q112.2.1命题逻辑13计算机科学导论[例]证明：p→r,q→s,p∨q⇒r∨s。证明：③构造证明法1)p→r前提2)p∨r1)等价置换3)r∨p2)等价置换4)r→p3)等价置换5)p∨q前提6)p∨q5)等价置换7)p→q6)等价置换8)r→q4)7)假言三段论9)q→s前提10)r→s8)9)假言三段论11)r∨s10)等价置换12.2.1命题逻辑14计算机科学导论12.2.2谓词逻辑对简单命题做进一步的分解，分析命题内部的逻辑结构和命题间的内在联系，它是命题逻辑的扩充和发展。1.个体词原子命题中所描述的对象，是可以独立存在的客体，可以是具体的，也可以是抽象的。2.谓词用来描述个体词的性质或个体词之间关系的词。3.量词表示个体常元或变元之间数量关系的词称为量词。15计算机科学导论[例]将以下命题用谓词逻辑符号化。(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))。12.2.2谓词逻辑16计算机科学导论4．谓词推理(1)全称量词消去规则。如果谓词公式∀xA(x)为真，则可推出A(c)为真，即∀xA(x)⇒A(c)式中，c是个体域中任意一个确定的个体。(2)存在量词消去规则。如果谓词公式∃xA(x)为真，则可推出A(c)为真，即∃xA(x)⇒A(c)式中，c是个体域中满足条件A的个体常元。12.2.2谓词逻辑17计算机科学导论(3)全称量词引入规则。如果谓词公式A(x)中的自由个体变元x无论取个体论域中的任何值，A(x)都为真，则可推出∀xA(x)为真，即A(x)⇒∀xA(x)式中，x是个体域中任意一个个体。(4)存在量词引入规则。如果谓词公式A(c)为真，则可推出∃xA(x)为真，即A(c)⇒∃xA(x)式中，c是个体域中满足条件A的个体常元。12.2.2谓词逻辑18计算机科学导论12.3集合论集合论(SetTheory)产生于16世纪末，并于19世纪末由德国数学家格奥尔格•康托尔(Cantor，1845-1918)建立，从而奠定了集合论的基础，康托尔也因此被公认为是集合论的创始人。康托尔出生于俄国圣彼得堡（今俄罗斯列宁格勒），父亲是犹太血统的丹麦商人，母亲出身艺术世家，他对数学的贡献是集合论和超穷数理论。19计算机科学导论12.3集合论12.3.1集合的基本概念与运算对简单命题做进一步的分解，分析命题内部的逻辑结构和命题间的内在联系，它是命题逻辑的扩充和发展。1.集合的概念与表示事物汇集在一起组成的一个整体叫做集合，而这些事物就可以称为这个集合的元素或者成员。集合通常用大写的英文字母来标记。表示一个集合的方法：列举法：A＝{1,2,3,…,n,…}描述法：B＝{x|x是大于等于8的正整数}20计算机科学导论12.3.1集合的基本概念与运算2.集合间关系设A，B是集合，如果B中的每个元素都是A中的元素，则称B是A的子集合，简称子集。这时也称B被A包含，或A包含B。设A，B为集合，如果AB且BA，则称A与B相等，记作A＝B。设A，B为集合，如果BA且B≠A，则称B是A的真子集。记作BA。不含任何元素的集合叫做空集，记作。给定集合A，由集合A的所有子集为元素组成的集合，称为集合A的幂集，记作P(A)。在一个具体问题中，如果所涉及的集合都是某个集合的子集，则称这个集合为全集，记作E(或U)。21计算机科学导论3.集合运算(1)定义：设A与B为集合，A与B的并运算、交运算、差运算-，分别定义为，A∪B={x|(x∈A)∨(x∈B)}A∩B={x|(x∈A)∧(x∈B)}A-B={x|(x∈A)∧(xB)}(2)定义：设E为全集，AE，则A的补运算，记作~，定义为，~A＝E-A＝{xx∈E∧xA}或~A＝{xxA}(3)定义：设A与B为集合，A与B的对称差，记作，定义为AB＝(A∪B)—(A∩B)12.3.1集合的基本概念与运算22计算机科学导论12.3.2关系与函数1.笛卡儿积(1)序偶由两个元素x和y(允许x=y)按一定的顺序排列成的二元组叫做一个有序对(也称序偶)，记作x,y，其中x是它的第一元素，y是它的第二元素。有序对的特点：①当xy时，x,yy,x。②两个有序对相等，即x,y＝u,v的充分必要条件是x＝u且y＝v。23计算机科学导论(2)笛卡儿积设A，B为集合，用A中元素作为第一元素，B中元素作为第二元素，构成有序对，所有这样的有序对组成的集合叫做A和B的笛卡儿积，记作A×B。符号化表示为A×B＝{(x,y)|x∈A∧y∈B}[例]有两个集合A＝{a,b}，B＝{0,1,2}，则A×B＝{a,0,a,1,a,2,b,0,b,1,b,2}B×A＝{0,a,0,b,1,a,1,b,2,a,2,b}12.3.2关系与函数24计算机科学导论2.二元关系(1)二元关系定义如果一个集合为空集或者它的元素都是有序对，则称这个集合是一个二元关系，一般记作R对于二元关系R，如果有序对x,y∈R，则记作xRy设A,B为集合，A×B的任何子集所定义的二元关系称作从A到B的二元关系，特别当A＝B时，则叫做A上的二元关系12.3.2关系与函数25计算机科学导论3种特殊的关系：①其中之一就是空集，称做空关系。②另外两种就是全域关系EA和恒等关系IA。对任何集合A，EA＝{x,y｜x∈A∧y∈A}＝A×AIA＝{x,x｜x∈A}12.3.2关系与函数26计算机科学导论(2)关系的表示通常用关系图来表示一个关系。[例]A={1,2,3,4}，R={1,1,1,2,2,3,2,4,4,2}，可以画出如下的关系图。12.3.2关系与函数27计算机科学导论(3)关系的基本运算Dom(R)＝{xy(x,y∈R)}Ran(R)＝{y|x(x,y∈R)}①F的逆记作：{x,y|y,x∈F}。②F与G的左复合记作G◦F，G◦F＝{x,y｜z(x,z∈G∧z,y∈F)}③F与G的右复合记作F◦G，F◦G＝{x,y｜z(x,z∈F∧z,y∈G)}12.3.2关系与函数28计算机科学导论(4)关系的性质①自反性若对于任意x属于集合A，都有，那么，就说R在A上是自反的。②反自反性若对于任意x属于集合A，都不存在，那么，就说R在A上是反自反的。③对称性若对于任意x,y属于集合A，都有∧x,y∈R，那么，就称R为A上的对称关系。④反对称性若对于任意x,y属于集合A，都不存在x,y∈R，那么，就称R为A上的反对称关系。例如A上的全域关系，恒等关系，空关系都是A上的对称关系。而恒等关系和空关系也是A上反对称关系。⑤传递性若对任意的x,y,z都属于集合A，假如都存在∧∧，那么，就称R为A上的传递关系。,xAxxR,xAxxR,xyA,yxR,yxR,,xyzA,yzR,xyR,xzR29计算机科学导论(5)两类重要的二元关系①等价关系设R为非空集合A上的二元关系，若R具有自反性、对称性和传递性，则称R为A上的等价关系。利用等价关系，可以对一些对象进行分类。例如，集合上的恒等关系即是等价关系。②偏序关系设R为非空集合A上的二元关系，若R具有自反性、反对称性和传递性，则称R为A上的偏序关系，偏序关系可以记为≤。集合A和A上的偏序关系R一起叫做偏序集，记为(A,≤)，如果有(a,b)∈R，可以表示为a≤b。根据偏序关系可以画出关系图，通常称为哈斯图。12.3.2关系与函数30计算机科学导论[例]已知A,≤为偏序集，集合A={a,b,c,d,e,f}，关系≤={(b,a),(d,b),(c,a),(e,c),(e,b),(d,a),(e,a)}，画出≤关系的哈斯图。解：按照偏序集哈斯图的规则，可以得到如下哈斯图12.3.2关系与函数31计算机科学导论4.函数函数(Functions)也称映射(Mapping)。函数也是一种二元关