1、离散数学期末复习,1.1 命题概念,命题：具有唯一真值的陈述句,1.1 命题概念,练习：1.下列句子为命题的是（ ）A.全体起立！ B. X=0 C. 我在说谎 D.张三生于1886年的春天2.下列句子不是命题的是（ ）A.中华人民共和国的首都是北京 B.张三是学生 C.雪是黑色的 D.太好了！,D,D,1.2 复合命题与联结词,常用的联结词（1）否定定义1.2.1 设P为一命题，P的否定是一个新的命题，记作P。 “”表示命题的否定. P的真值： 若P为T， P为F；若P为F， P为T,1.2 复合命题与联结词,常用的联结词（2）合取定义1.2.2 两个命题P和Q的合取是一个复合命题，记作PQ
2、。称作合取联结词， 在自然语言中的“并且”、“和”、“既.又.”、“不仅.而且.”、“虽然.但是.”等都可以符号化为 例1 2是素数和偶数 设P：2是素数，Q:2是偶数，故上述命题可表述为PQ 例2 王乙工作努力且身体好。 设P:王乙工作努力，Q:王乙身体好，故上述命题可表述为PQ,1.2 复合命题与联结词,常用的联结词（2）合取PQ的真值 当且仅当P与Q同时为T时，PQ为T.其余情况，PQ为F,1.2 复合命题与联结词,常用的联结词（2）合取注意: 命题联结词“合取”可将两个互为否定的命题联结在一起：PP 此时其真值永为F,1.2 复合命题与联结词,常用的联结词（3）析取定义1.2.3 两个
3、命题P, Q的析取是个复合命题，记作PQ。称作析取联结词， 与自然语言中的“或”有些相似例4 王强是这次校运动会的跳高或100米短跑的冠军。 设P: 王强是这次校运动会的跳高冠军； Q:王强是这次校运动会的100米短跑的冠军。 所以本例可描述为： PQ,1.2 复合命题与联结词,常用的联结词（3）析取PQ的真值 当且仅当P与Q同时为F时，PQ为F.否则，PQ为T,1.2 复合命题与联结词,常用的联结词（4）条件定义1.2.4 给定两个命题P, Q，其条件命题是一个复合命题，记作PQ。其中P为前件，Q为后件。PQ读作“如果P那么Q”，“若P则Q”例6 如果我有就学机会，那么我必用功读书。 设P:
4、 我有就学机会； Q:我必用功读书。 所以本例可描述为： PQ,1.2 复合命题与联结词,常用的联结词（4）条件PQ的真值 当且仅当P的真值为T，Q的真值为F时，PQ 为F.其余情况，PQ为T,1.2 复合命题与联结词,常用的联结词（5）双条件定义1.2.6 给定两个命题P, Q，其复合命题PQ称作双条件命题，读作P当且仅当Q。例 两个三角形全等，当且仅当它们的三组对应边相等。 设P: 两个三角形全等； Q:它们的三组对应边相等。 所以本例可描述为： PQ,1.2 复合命题与联结词,常用的联结词（5）双条件PQ 的真值 当P与Q的真值为相同时，PQ 为T.其余情况，PQ 为F,1.2 复合命题
5、与联结词,1.2 复合命题与联结词,1.3 命题公式与真值表,真值表定义1.3.3 设P为一命题公式，P1 , P2, P3,.Pn 为出现在P中的所有命题变元， 对 P1 , P2, P3,.Pn 指定一组真值称为对P的一种指派。若指定的一种指派，使P的值为真，则称这组值为成真指派；若指定的一种指派，使P的值为假，则称这组值为成假指派。,1.3 命题公式与真值表,1.3 命题公式与真值表,等价式定义1.3.4 给定两个命题公式A和B，设P1 , P2, P3,.Pn为所有出现于A和B中的原子变元，若给P1 , P2, P3,.Pn任一组真值指派，A和B的真值都相同，称A和B是等价的，记作AB
6、。从上述真值表的例子中，可以知道： P Q PQ (PQ) ( P Q)PQ 上述二式以后经常作为等值公式直接应用。,1.3 命题公式与真值表,定义1.3.5 设A为一命题公式，若A在它的各种指派情况下，其取值均为真, 则称公式A为重言式或永真式。定义1.3.6 设A为一命题公式，若A在它的各种指派情况下，其取值均为假, 则称公式A为矛盾式或永假式。定义1.3.7 设A为一命题公式，若A在它的各种真值指派下至少存在一组成真指派，则称A是可满足式。,1.3 命题公式与真值表,对合律 PP幂等律 PPP, PPP结合律 (PQ)RP(QR), (PQ)RP(QR)交换律 PQQP, PQQP分配律
7、 P(QR)(PQ)(PR), P(QR)(PQ)(PR),1.3 命题公式与真值表,吸收律 P(PQ)P, P(PQ)P德摩根律 (PQ)PQ, (PQ)PQ同一律 PFP , PTP零律 PTT, PFF否定律 P PT, PPF,两个等值公式： P Q PQ (PQ) ( P Q)PQ,1.4 等价变换与蕴含式,等价变换定理1.4.1 设 X 是合式公式 A 的子公式，若有Y也是一个合式公式，且XY，如果将A中的X用Y置换， 得到公式B,则 AB。例：证明Q(P(PQ)QP 证：设A：Q(P(PQ)， 因为P(PQ)P（吸收律） 故B:QP，即AB,1.4 等价变换与蕴含式,等价变换判断
8、命题公式是重言式或矛盾式,真值表,等价变换,1.4 等价变换与蕴含式,1.5 最小联结词组与范式,最小联结词组（1）由PQ(PQ)(QP)，故可把包含的公式等价变换为包含“”和“”的公式。（2）由PQPQ，故可把包含的公式等价变换为包含“”和“”的公式。（3）由PQ(PQ)，PQ(PQ)说明“”与“”可以相互交换。故由“”“”“”“”“”这5个联结词中若干个组成的命题公式，必可由,或,组成的命题公式所替代。我们把,及,称为命题公式的最小联结词组。,1.5 最小联结词组与范式,范式定义1.5.1 一个命题公式称为合取范式，当且仅当它具有形式 A1 A2.An （n1）其中A1 ，A2，.，An
9、都是由命题变元以其否定组成的析取式。例如：（PQ）（PR）（PQ）是一个合取范式,1.5 最小联结词组与范式,范式定义1.5.2 一个命题公式称为析取范式，当且仅当它具有形式 A1 A2.An （n1）其中A1 ，A2，.，An 都是由命题变元以其否定组成的合取式。例如：（PQ）（PR）（PQ）是一个析取范式,1.5 最小联结词组与范式,范式一个命题公式的合取范式或析取范式不是唯一的。,1.5 最小联结词组与范式,主范式定义1.5.3 n个命题变元的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现仅且出现一次。例如：2个命题变元P和Q，其小项为： PQ, PQ,
10、PQ, PQ 3个命题变元P，Q和R，其小项为： PQR, PQR, PQR, PQR, PQR, PQR, PQR, PQR,1.5 最小联结词组与范式,小项的表示一般来说，n个命题变元有2n个小项，n个命题变元的小项，将命题变元看成1，其否定看成0，则每个小项对应着一个二进制数。例： m000= PQR m001=PQR m010=PQR m011=PQR m100=PQR m101=PQR m110=PQR m111=PQR,1.5 最小联结词组与范式,主范式定义1.5.4 对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的主析取范式。定理1.5.1 在
11、真值表中，一个公式的真值为T的指派所对应的小项的析取，即为此公式主析取范式。定理1.5.2 任意含n个命题变元的非永假命题公式，其主析取范式是唯一的。,1.5 最小联结词组与范式,主范式定义1.5.5 n个命题变元的析取式，称作布尔析取或大项，其中每个变元与它的否定不能同时存在，但两者必须出现仅且出现一次。例如：2个命题变元P和Q，其大项为： PQ, PQ, PQ, PQ 3个命题变元P，Q和R，其大项为： PQR, PQR, PQR, PQR, PQR, PQR, PQR, PQR,1.5 最小联结词组与范式,大项的表示与小项情况类似，每个大项也可以编码。具体方法：首先将n个命题变元排序，将
12、每个命题变元对应成0，其否定对应成1，则可将2n个大项按二进制数编码，记为Mi，其下标是由二进制化为十进制数。例： 2个命题变元P,Q的命题公式，应有4个大项： PQ=M00=M0 PQ=M01=M1, PQ=M10=M2, PQ=M11=M3,1.5 最小联结词组与范式,主范式定理1.5.3 在真值表中一个公式的真值为F的指派所对应的大项的合取，即为此公式主合取范式。定理1.5.2 任意含n个命题变元的非永真命题公式A，其主合取范式是唯一的。,1.5 最小联结词组与范式,主范式从A的主析取范式求主合取范式步骤：（1）求出A的主析取范式中为包含小项的下标（2）把（1）中求出的下标写成对应大项。
13、（3）做（2）中写成的大项合取，即为A的主合取范式。,1.5 最小联结词组与范式,主范式例：公式A：（pq）（qp） ，则公式A的主合取范式为例：（PQ）Q =m01m11 （PQ）Q =M00M10,1.5 最小联结词组与范式,主范式根据主范式的定义和定理,可以判定含n个命题变元的公式: （1）若A可化为与其等价的,含2n个小项的主析取范式,则A为永真式. （2）若A可化为与其等价的,含2n个大项的主合取范式,则A为永假式. （3）若A的主析取范式不含2n个小项,或A的主合取范式不含2n个大项,则A为可满足式.判断公式类型： 1，真值表 2.等值演算 3.主范式,1.4 等价变换与蕴含式,1
14、.4 等价变换与蕴含式,蕴含式定理1.4.2 设A,B为两命题公式，AB，当且仅当AB为一个重言式。定义1.4.1 当且仅当PQ是一个重言式时，我们称“P蕴含Q”，并记作P Q。P Q称作P蕴含Q或蕴含式，亦称作永真条件式。,1.4 等价变换与蕴含式,蕴含式（1）化简式 PQ P. PQ Q（3）附加式 P PQ（4）变形附加式 P PQ，Q PQ（5）变形简化式 （PQ） P;（PQ） Q （6）假言推论 P（PQ） Q（7）拒取式 Q（PQ） P（8）析取三段论 P(PQ) Q（9）条件三段论 （PQ）(QR) PR（10）双条件三段论 （PQ）（QR） PR（11）合取构造二难 （PQ）
15、（RS）（PR） QS（12）析取构造二难 （PQ）（RS）（PR） QS（13）前后件附加 PQ （PR）（QR）; PQ （PR）（QR）,1.6 推理理论,有效推理：从前提出发，根据确认的推理规则推导出一个结论，这个过程叫有效推理。定义1.6.1 设H1，H2，.，Hn，C是命题公式，当且仅当H1H2.Hn C，称C是一组前提的有效结论。,1.6 推理理论,判别有效结论的方法：（3）构造论证法在推理过程中，如果命题变元很多，用真值表、等值演算法及主范式法等作推理证明都很不方便。表1.6.2及表1.6.3的公式可直接应用。常用的推理规则：（1）前提引入规则：在证明的任何步骤上，都可以引入前
16、提，简称P规则。（2）结论引入规则：在证明的任何步骤上，所证明的结论都可作为后续证明的前提。（3）置换规则：在证明的任何步骤上，命题公式中的任何子命题公式都可以用与之等值的命题公式置换（表1.6.2，表1.6.3），记为T规则。,1.6 推理理论,1.6 推理理论,判别有效结论的方法：（3）构造论证法定理 1.6.2 若H1H2.Hn C为永假式，则H1H2.Hn C成立。 附加前提法： 把结论的否定作为前提，推出F。,1.6 推理理论,定理1.6.3 （CP规则 ） 若H1H2.Hn R C,则H1H2.Hn RC。,2.1 谓词的概念与表示,客体：指可以独立存在的对象，一个具体的事物，一个
17、抽象的概念谓词：指明客体性质或指明客体之间关系,2.2 量词与合式公式,量词：表示数量的词量词有2种：1.全称量词：对应日常语言中的“一切”“任意的”“所有”“凡是”等词。用符号“ ”表示。 表示对个体域里所有的x，而 表示个体域里所有个体，都有性质F。2.存在量词：对应日常语言中的“存在的”“有一个”“至少有一个”等词。用符号“ ”表示。 表示存在个体域中的个体，而 表示存在个体域中的个体具有性质F。,2.2 量词与合式公式,在全称量词中，特性谓词是条件式的前件。在存在量词中，特性谓词后跟一个合取项。,2.2 量词与合式公式,2.2 量词与合式公式,定义2.2.1 由一个或几个原子命题函数以
18、及逻辑联结词组合而成的表达式称为复合命题函数。定义2.2.2 谓词演算的合式公式，可由下述各条组成（合式公式A记为WffA）：（1）原子谓词公式是合式公式。（2）若A是合式公式，则A是一个合式公式。（3）若A和B都是合式公式，则（AB），（AB），（AB），（AB）是合式公式。（4）如果A是合式公式，x是A中出现的任何变元，则 和 都是合式公式。（5）只有经过有限次应用规则（1）（2）（3）（4）所得到的公式是合式公式。,2.2 量词与合式公式,2.2 量词与合式公式,定义2.2.3 给定谓词合式公式A，其中一部分公式形式为 或称量词 ， 后面所跟的x为指导变元或作用变元。称B(x)为相应量词
19、的辖域（或作用域）。 在辖域中，x的一切出现称为约束出现。B(x)中除去约束出现的其他变项的出现为自由出现。,2.3 谓词演算的等价式与蕴含式,当确定论域后 ，与 都是一个特定的命题。例如 表示x是个大学生，论域是a,b,c,则： 即是S(a)S(b)S(c) 即是S(a)S(b)S(c)例：如果论域是集合a,b,c,试消去下面公式中的量词：解：原式 (R(a)R(b)R(c)(S(a)S(b)S(c),2.3 谓词演算的等价式与蕴含式,2.3 谓词演算的等价式与蕴含式,2.3 谓词演算的等价式与蕴含式,定义2.3.1 给定任何两个谓词公式WffA和WffB，设它们有共同的个体域E，若对A和B
20、的任一组变元进行赋值，所得命题的真值相同，则称谓词公式A和B在E上是等价的，并记作,2.3 谓词演算的等价式与蕴含式,2.3 谓词演算的等价式与蕴含式,定理 2.3.1 量词与否定联结词之间有如下关系：（1）（2）,2.3 谓词演算的等价式与蕴含式,2.4 前束范式,定义2.4.1 一个公式，如果量词均在全式的开头，它们的作用域，延伸到整个公式的末尾，则该公式叫做前束范式。,2.5 谓词演算的推理理论,（1）全称指定规则（US）：由 得到P(c)。 P是谓词，而c是论域中的任意某个个体，如果论域中全部个体有P(x)，那么全称指定规则有结论P(c)（2）全称推广规则（UG）：由P(c)得到 如果
21、能够证明对论域中任一客体x断言P(x)都成立，则全称推广规则可得到结论（3）存在指定规则（ES）：由 得到P(c) C是论域中某些个体（不是任意存在的）（4）存在推广规则（EG）：由P(c)得到,2.5 谓词演算的推理理论,3.1 集合的基本概念,集合：把一些事物汇集到一起组成一个整体例：教室内的桌椅，图书馆全部藏书，直线上的点的集合，中国的全部县市的集合集合常用的表示方法：（1）列举法：将集合的元素列举出来例：A=a,b,c,d，B=桌子，灯泡，老虎，自然数，地球，E=2，4，6，.,2n，.，S=a,1,2,q,a 集合的元素可以是一个集合。以集合作为元素组成的集称为集合簇,3.1 集合的
22、基本概念,集合常用的表示方法：（2）叙述法：集合的元素，用谓词概括其所属特性例：A=X|是中国的高等学校，B=x|x是实数x2-1=0，C=x|x为小于500的质数，叙述法实际可用谓词描述属性，实际上上述各例可描述为B=x|P(x)，如果P(b)为真，即b是B的元素，记作b B，否则b B,3.1 集合的基本概念,集合常用的表示方法：（3）特定字母集：有些数集用特定字母表示N-自然数集 Z-整数集Q-有理数集 R-实数集C-复数集 Z+-正整数集Q-负有理数集 Q+-正有理数集,3.1 集合的基本概念,集合常用的表示方法：（4）图示法：用封闭曲线表示集合，封闭曲线内的点表示集合内的元素。这种图
23、常称作文氏图。,A,B,3.1 集合的基本概念,定义3.1.1 设A,B是任意两个集合，若A=B，当且仅当它们有相同的成员。定义3.1.2 设A、B为任意两个集合，如果A的每一个元素都是B的元素，则称集合A为集合B的子集，或A包含在B内或B包含A。记作： A B(或B A)根据子集的定义，显然有对任意集合A,B,C，必有,3.1 集合的基本概念,定理3.1.1 集合A和集合B相等的充分必要条件是两个集合互为子集。定义3.1.3 如果集合A的每个元素都属于B，但集合B中至少有一个元素不属于A，则称A为B的真子集。记作： A B例如，a,b a,b,d定义3.1.4 不包含任何元素的集合称为空集，
24、记为 或 定理3.1.2 对于任意集合A必有,3.1 集合的基本概念,定义3.1.5 设A为任意集合，以A的子集为元素所组成的集合，称为集合A的幂集，记为P(A),3.1 集合的基本概念,定理3.1.3 如果有限集合A有n个元素，则其幂集P(A)有2n个元素。定义3.1.6 在一定范围内，如果所有集合均为某一集合的子集，则称该集合为全集。记为E,3.2 集合的运算,（1）集合的交定义3.2.1设A，B为任意两个集合。 由集合A和 B 所共有的全部元素构成的集合S,称为A与B的交集，记为AB。,3.2 集合的运算,（2）集合的并定义3.2.2 任意两个集合A和B。 所有属于集合A又属于集合 B
25、的元素构成的集合S,称为A与B的并集，记为AUB。,3.2 集合的运算,（2）集合的并定理3.2.1 设A,B,C为三个集合，则:a.A(BUC)=(AB)U(AC)b.AU(BC)=(AUB)(AUC)并运算与交运算之间尚有下列性质：吸收律：AU(AB)=A A(AUB)=A,3.2 集合的运算,（3）集合的补定义3.2.3 任意两个集合A和B。 所有属于集合A而不属于集合 B 的元素构成的集合S,称为A与B的补集，记为A-B。例：设E=a,b,c,d,e，A=a,b.c，B=a,c,d，A-B=d，B-A=d定义3.2.4 设E为全集，对任一集合A,关于E的补E-A，称为集合A的绝对补，记
26、作A,3.2 集合的运算,（4）集合的对称差定义3.2.5 任意两个集合A和B。 所有或属于集合A或属于集合 B 但不能即属于A，又属于B的元素构成的集合S,称为A与B的对称差， 记为A B。定理3.2.3设任意集合A,B,C，则有以下性质：,3.3 笛卡尔积与关系,定义3.3.1 由两个客体x和y，按一定的顺序，组成一个二元组，称此二元组为有序对或称序偶，记作或（x，y）。其中x是该序偶的第一个元素，y是该序偶的第二个元素。定义3.3.2 两个序偶相等，=,iff x=u,y=v.定义3.3.3 设A,B为集合。用A中的元素x作为第一元素，B中的元素y作为第二元素，构成有序对，所有这样的有序
27、对组成的集合，叫做A和B的笛卡尔积，记作AB。例：A=0,1,2，B=a,b， AB=,BA=,可看出ABBA,3.3 笛卡尔积与关系,我们约定：若A=或B=，则AB=由笛卡尔积的定义：,3.3 笛卡尔积与关系,定义3.3.4 设A,B是任意两个集合，AB的子集R称为从A到B的二元关系。当A=B时，称R为A上的二元关系。 称a与b有关系R，记作aRb 称a与b没有关系R，记作aRb若R=称为空关系，若R=AB称R为全关系，当A=B时，全关系A上的恒等关系例：A=0,1,2，IA=,3.3 笛卡尔积与关系,定义3.3.5 设R为二元关系，由 R的所有x组成集合domR，称为R的前域。 使 R的所
28、有y组成的集合ranR称作R的值域，即R的前域和值域一起称作R的域，记为FLDR，FLDR=domRUranR,3.4 关系的表示与关系性质,关系的表示：（1）关系图设X=x1,x2,x3,x4,x5,x6,x7，Y=y1,y2,y3,y4,y5,y6，R=,，ranR=x3,x4,x5 ranR=y1,y2,y4,x1,x2,x6,x7,x3,x4,x5,X,y1,y2,y4,y3,y5,y6,Y,domR,ranR,3.4 关系的表示与关系性质,关系的表示：（2）布尔矩阵设给定两个有限集合X=x1,x2,x3,.,xm，Y=y1,y2,.,yn，R为X到Y的一个二元关系，则对应于R有一个关
29、系矩阵其中， 1，当 0, 当例1的R表示：,3.4 关系的表示与关系性质,定义3.4.1 设R是集合X上的二元关系，（1）如果对任意 ，必有xRx,则称关系R在X上是自反的。（2）如果对任意 ，必有xRx，则称关系R在X上的反自反的。（3）如果对任意 ，若xRy必有yRx，则称关系R在X上是对称的。（4）如果对任意 ，若xRy且yRx必有x=y，则称R在X上是反对称的。（5）如果对任意 ，xRy且yRz必有xRz，则称关系R在X上是传递。,3.4 关系的表示与关系性质,为了判别关系性质，也可以从关系矩阵和关系图上给予验证。若关系R是自反的，当且仅当在关系矩阵中，对角线上的所有元素都是1，在关
30、系图中每个结点都有自回路。若关系R是对称的，当且仅当在关系矩阵是对称的，在关系图中，任两个结点间若有定向弧线，必是成对出现。若关系R是反自反的，当且仅当在关系矩阵中，对角线上的所有元素都是0，在关系图中每个结点都没有自回路。若关系R是反对称的，当且仅当在关系矩阵以对角线为对称的元素不能同时为1，在关系图中，两个结点间若有定向弧线，不可能成对出现。,3.5 关系运算与闭包,二元关系是以序偶为元素的集合，因此可以对它进行集合的运算。定义3.5.1 设R是从X到Y的二元关系，如将R中每一序偶的元素顺序互换，所得到的集合称为R的逆关系，记作R-1例：设X=1,2,3,4,Y=a,b,c,R=,求R-1
31、R-1=,3.5 关系运算与闭包,定义3.5.2 设R为A到B的关系，S为B到C的关系，则RS称R和S的复合关系。例：设A=p,q,r,s,B=a,b,C=1,2,3,4,A到B的关系R1=,，从B到C的关系R2=,则A到C的复合关系RS=,3.5 关系运算与闭包,设R是X到Y的关系，S是Y到Z的关系，P是Z到W的关系，易证(RS)P=R(SP)，即满足结合律一般来说复合运算不满足交换律。由关系的结合律可以知道关系R本身组成的复合关系可以写成RR，RRR，.,RR.R,可分别记作R2,R3,.,Rm,m,3.5 关系运算与闭包,定理3.5.2 设A=a1,a2,.,am，B=b1,b2,.,b
32、n，C=c1,c2,.,cr从A到B的关系R1关系矩阵MR1=(xij)是mn阶矩阵。从B到C的关系R2的关系矩阵MR2=(yij)是nr阶矩阵，那么从A到C的关系矩阵:MR1R2=(Zij)是mr阶矩阵布尔运算的加法和乘法，规定0，1运算为：00=0，01=1，10=1，11=1，00=0，01=0，10=0，11=1例：设集合A=1,2,3,4,B=2,3,4,C=1,2,3,A到B的关系R1=,，B到C的关系R2=,，求A到C的关系R=R1R2,3.5 关系运算与闭包,定义3.5.3 设R是A上二元关系，如果有另一个关系R，满足：（1）R是自反的（对称的，可传递的）；（2）R R；（3）
33、对于任何自反的（对称的，可传递的）关系R,如果有R R，就有R R，则称关系R为R的自反（对称，传递）闭包，记作r(R)(S(R),t(R) 定理3.5.3 设R的非空有穷集合A上的二元关系。（1）r(R)=RUIA（2）S(R)=RUR-1（3）t(R)=RUR2U.URn,其中n是集合A中元素的数目。,3.5 关系运算与闭包,检查关系R的关系图，在每个结点上加上一个自环，即得r(R)的关系图。如果将R的关系图中，每条单向边全部改成双向边，其余不变，则得到S(R)关系图。关于传递闭包，检查R关系图的每个结点x，从x出发长度不超过n（n是图中结点个数）的所有路径终点都找到，如果x到这样的终点没
34、有边，就加上此边。例：设A=a,b,c，给定A上的二元关系R=,求r(R),S(R),t(R),3.6 相容关系与覆盖,定义3.6.1 给定集合A上的关系p，若p是自反的，对称的，则称p是A上的相容关系。,3.7 等价关系与划分,定义3.7.1 设R为定义在集合A上的一个关系，若R是自反的，对称的和传递的，则称R为等价关系。,3.7 等价关系与划分,定义 3.7.2 设给定非空集合A,若有集合S=S1,S2,.Sm,其中Si A，Si ，(i=1,2,.,m),且SiSj= ，（i j），同时有 ，称S为A的划分。例：A=a,b,c,d,B=a,b,c,d,D=a,b,c,d,E=b,a,c,
35、d,F=a,b,cd,则B,D,E,F都是A的不同划分。,3.7 等价关系与划分,定理3.7.3 集合A的一个划分确定A的元素间的一个等价关系。证明：设集合A有一个划分S=S1,S2,.Sm，先定义一个关系R，当aRb，当且仅当a，b在同一分块中，这样：（1）a与a在同一分块中，故必有aRa，即R是自反的。（2）若a，b在同一分块中，则b，a也在同一分块中，即aRb bRa，故R是对称的。（3）若a与b在同一分块中，b与c在同一分块中，故有：aRbbRc aRc，即R是传递的。从以上证明三点，说明R是A上的等价关系。,3.7 等价关系与划分,例：设A=a,b,c,d,e,f的一个划分，S=a,
36、b,c,d,e,f，由S确定A上等价关系为R，R=(a,ba,b)U(c,dc,d)U(e,fe,f)=,3.8 序关系,定义3.8.1 设A是一个集合，如果A上的关系R满足自反性，反对称性，以及传递性，则称R是A上的一个偏序关系，并记作。序偶称作偏序集。例：在实数集R上，证明小于等于关系，“”是偏序关系。证明：a)对任意实数a，都有aa，故在实数集R上是自反的。 b)对任意实数a,b,有ab,ba，必有a=b,这说明在实数集上是反对称的。 c)对任意实数a,b,c,如果ab,bc,则在实数集上必有ac，所以是传递的。从上述三点，说明在实数集上是偏序关系。,3.8 序关系,偏序集可以通过图形表
37、示。表示偏序集的图形是哈斯图。画法如下：A中每个元素可用结点表示。对于a，b A，若ab，则将结点a画在结点b下，若a与b之间不存在其他元素c，使ac，cb，则在a与b之间用一直线相连，得到的图形为哈斯图。因偏序集每个结点都有环，画哈斯图时可以省略。,3.8 序关系,定义3.8.4 在偏序集中，如果x，y A，xy，且xy，且没有其他元素z，满足xz，zy，则称元素y盖住元素x。记COVA=|x,y A;y盖住x,3.8 序关系,定义3.8.6 设是一个偏序集，且B是A的子集，对于B中一个元素b，如果没有任何元素x，满足bx，且bx，则称b为B的极大元。同理，若B中没有任何元素x，满足bx，且xb，则称b为B的极小元。,3.8 序关系,定义3.8.7 令为一偏序集，B A，若有元素b B,对B中每一个元素x有xb，则称b为的最大元，同理，若对每一个元素x都有bx，则称b为的最小元。,3.8 序关系,定义3.8.8 令为一偏序集，B A，若有元素a A,且对B中任意元素x有xa，则称a为子集B的上界，同理，若对B任意元素x都有ax，则称a为B的下界。定义3.8.9 令为一偏序集，B A，若a为B的任意上界,且、若对B的所有上界y均有ay，则称a为B的上确界，同理，若b为B的任意下界若对B的所有下界z，都有zb，则称z为B的下确界。,
