自考离散数学期末复习

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的合取是一个复

2、合命题，记作PQ。 称作合取联结词， 在自然语言中的“并且”、“和”、“既.又.”、“不仅.而且.”、“虽然.但是.”等都可以符号化为 例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、3）析取 定义1.2.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

4、 如果我有就学机会，那么我必用功读书。 设P: 我有就学机会； 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的真值

5、为相同时，PQ 为T.其余情况，PQ 为F,1.2 复合命题与联结词,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,.P

6、n任一组真值指派，A和B的真值都相同，称A和B是等价的，记作AB。 从上述真值表的例子中，可以知道： 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 结合律 (P

7、Q)RP(QR), (PQ)RP(QR) 交换律 PQQP, PQQP 分配律 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)

8、， 因为P(PQ)P（吸收律） 故B:QP，即AB,1.4 等价变换与蕴含式,等价变换 判断命题公式是重言式或矛盾式,真值表,等价变换,1.4 等价变换与蕴含式,1.5 最小联结词组与范式,最小联结词组 （1）由PQ(PQ)(QP)，故可把包含的公式等价变换为包含“”和“”的公式。 （2）由PQPQ，故可把包含的公式等价变换为包含“”和“”的公式。 （3）由PQ(PQ)，PQ(PQ)说明“”与“”可以相互交换。 故由“”“”“”“”“”这5个联结词中若干个组成的命题公式，必可由,或,组成的命题公式所替代。 我们把,及,称为命题公式的最小联结词组。,1.5 最小联结词组与范式,范式 定义1.5.

9、1 一个命题公式称为合取范式，当且仅当它具有形式 A1 A2.An （n1） 其中A1 ，A2，.，An 都是由命题变元以其否定组成的析取式。 例如：（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个命题变元的合取式，称作布尔合取或小项，

10、其中每个变元与它的否定不能同时存在，但两者必须出现仅且出现一次。 例如：2个命题变元P和Q，其小项为： PQ, PQ, 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 最小联结词组与范式,主范式 定义

11、1.5.4 对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的主析取范式。 定理1.5.1 在真值表中，一个公式的真值为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, PQ

12、R, PQR, PQR,1.5 最小联结词组与范式,大项的表示 与小项情况类似，每个大项也可以编码。具体方法：首先将n个命题变元排序，将每个命题变元对应成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

13、最小联结词组与范式,主范式 从A的主析取范式求主合取范式步骤： （1）求出A的主析取范式中为包含小项的下标 （2）把（1）中求出的下标写成对应大项。 （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的

14、主析取范式不含2n个小项,或A的主合取范式不含2n个大项,则A为可满足式. 判断公式类型： 1，真值表 2.等值演算 3.主范式,1.4 等价变换与蕴含式,1.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

15、（7）拒取式 Q（PQ） P （8）析取三段论 P(PQ) Q （9）条件三段论 （PQ）(QR) PR （10）双条件三段论 （PQ）（QR） PR （11）合取构造二难 （PQ）（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）构造论证法 在推理

16、过程中，如果命题变元很多，用真值表、等值演算法及主范式法等作推理证明都很不方便。 表1.6.2及表1.6.3的公式可直接应用。 常用的推理规则： （1）前提引入规则：在证明的任何步骤上，都可以引入前提，简称P规则。 （2）结论引入规则：在证明的任何步骤上，所证明的结论都可作为后续证明的前提。 （3）置换规则：在证明的任何步骤上，命题公式中的任何子命题公式都可以用与之等值的命题公式置换（表1.6.2，表1.6.3），记为T规则。,1.6 推理理论,1.6 推理理论,判别有效结论的方法： （3）构造论证法 定理 1.6.2 若H1H2.Hn C为永假式，则H1H2.Hn C成立。 附加前提法： 把

17、结论的否定作为前提，推出F。,1.6 推理理论,定理1.6.3 （CP规则 ） 若H1H2.Hn R C,则H1H2.Hn RC。,2.1 谓词的概念与表示,客体：指可以独立存在的对象，一个具体的事物，一个抽象的概念 谓词：指明客体性质或指明客体之间关系,2.2 量词与合式公式,量词：表示数量的词 量词有2种： 1.全称量词：对应日常语言中的“一切”“任意的”“所有”“凡是”等词。用符号“ ”表示。 表示对个体域里所有的x，而 表示个体域里所有个体，都有性质F。 2.存在量词：对应日常语言中的“存在的”“有一个”“至少有一个”等词。用符号“ ”表示。 表示存在个体域中的个体，而 表示存在个体域

18、中的个体具有性质F。,2.2 量词与合式公式,在全称量词中，特性谓词是条件式的前件。 在存在量词中，特性谓词后跟一个合取项。,2.2 量词与合式公式,2.2 量词与合式公式,定义2.2.1 由一个或几个原子命题函数以及逻辑联结词组合而成的表达式称为复合命题函数。 定义2.2.2 谓词演算的合式公式，可由下述各条组成（合式公式A记为WffA）： （1）原子谓词公式是合式公式。 （2）若A是合式公式，则A是一个合式公式。 （3）若A和B都是合式公式，则（AB），（AB），（AB），（AB）是合式公式。 （4）如果A是合式公式，x是A中出现的任何变元，则 和 都是合式公式。 （5）只有经过有限次应用

19、规则（1）（2）（3）（4）所得到的公式是合式公式。,2.2 量词与合式公式,2.2 量词与合式公式,定义2.2.3 给定谓词合式公式A，其中一部分公式形式为 或 称量词 ， 后面所跟的x为指导变元或作用变元。称B(x)为相应量词的辖域（或作用域）。 在辖域中，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)

20、R(b)R(c)(S(a)S(b)S(c),2.3 谓词演算的等价式与蕴含式,2.3 谓词演算的等价式与蕴含式,2.3 谓词演算的等价式与蕴含式,定义2.3.1 给定任何两个谓词公式WffA和WffB，设它们有共同的个体域E，若对A和B的任一组变元进行赋值，所得命题的真值相同，则称谓词公式A和B在E上是等价的，并记作,2.3 谓词演算的等价式与蕴含式,2.3 谓词演算的等价式与蕴含式,定理 2.3.1 量词与否定联结词之间有如下关系： （1） （2）,2.3 谓词演算的等价式与蕴含式,2.4 前束范式,定义2.4.1 一个公式，如果量词均在全式的开头，它们的作用域，延伸到整个公式的末尾，则该公

21、式叫做前束范式。,2.5 谓词演算的推理理论,（1）全称指定规则（US）：由 得到P(c)。 P是谓词，而c是论域中的任意某个个体，如果论域中全部个体有P(x)，那么全称指定规则有结论P(c) （2）全称推广规则（UG）：由P(c)得到 如果能够证明对论域中任一客体x断言P(x)都成立，则全称推广规则可得到结论 （3）存在指定规则（ES）：由 得到P(c) C是论域中某些个体（不是任意存在的） （4）存在推广规则（EG）：由P(c)得到,2.5 谓词演算的推理理论,3.1 集合的基本概念,集合：把一些事物汇集到一起组成一个整体 例：教室内的桌椅，图书馆全部藏书，直线上的点的集合，中国的全部县市

22、的集合 集合常用的表示方法： （1）列举法：将集合的元素列举出来 例：A=a,b,c,d， B=桌子，灯泡，老虎，自然数，地球， E=2，4，6，.,2n，.， S=a,1,2,q,a 集合的元素可以是一个集合。以集合作为元素组成的集称为集合簇,3.1 集合的基本概念,集合常用的表示方法： （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 集合的基本概念,集合常用的表示

23、方法： （3）特定字母集：有些数集用特定字母表示 N-自然数集 Z-整数集 Q-有理数集 R-实数集 C-复数集 Z+-正整数集 Q-负有理数集 Q+-正有理数集,3.1 集合的基本概念,集合常用的表示方法： （4）图示法：用封闭曲线表示集合，封闭曲线内的点表示集合内的元素。这种图常称作文氏图。,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

24、,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 不包含任何元素的集合称为空集，记为 或 定理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 在一定范围内，如果所有集合均

25、为某一集合的子集，则称该集合为全集。记为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 的元素构成的集合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 集

26、合的运算,（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的绝对补，记作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.

27、1 由两个客体x和y，按一定的顺序，组成一个二元组，称此二元组为有序对或称序偶，记作或（x，y）。其中x是该序偶的第一个元素，y是该序偶的第二个元素。 定义3.3.2 两个序偶相等，=,iff x=u,y=v. 定义3.3.3 设A,B为集合。用A中的元素x作为第一元素，B中的元素y作为第二元素，构成有序对，所有这样的有序对组成的集合，叫做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称为

28、从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的所有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，

29、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有一个关系矩阵 其中， 1，当 0, 当 例1的R表示：,3.4 关系的表示与关系性质,定义3.4.1 设R是集合X上的二元关系， （1）如果对任意 ，必有xRx,则称关系R在X上是自反的。 （2）如果对任意 ，必有xRx，则称关系R在X上的反自反的。 （3）

30、如果对任意 ，若xRy必有yRx，则称关系R在X上是对称的。 （4）如果对任意 ，若xRy且yRx必有x=y，则称R在X上是反对称的。 （5）如果对任意 ，xRy且yRz必有xRz，则称关系R在X上是传递。,3.4 关系的表示与关系性质,为了判别关系性质，也可以从关系矩阵和关系图上给予验证。 若关系R是自反的，当且仅当在关系矩阵中，对角线上的所有元素都是1，在关系图中每个结点都有自回路。 若关系R是对称的，当且仅当在关系矩阵是对称的，在关系图中，任两个结点间若有定向弧线，必是成对出现。 若关系R是反自反的，当且仅当在关系矩阵中，对角线上的所有元素都是0，在关系图中每个结点都没有自回路。 若关系

31、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 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到

32、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,.,bn，C=c1,c2,.,cr从A到B的关系R1关系矩阵MR1=(xij)是mn阶矩阵。从B到C的关系R2的关系矩阵MR2=(yij)是nr阶矩阵，那么从A到C的关系矩阵:MR1R2=(Zij)是mr阶矩阵 布尔运算的

33、加法和乘法，规定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）对于任何自反的（对称的，可传递的）关系R,如果有R R，就有R R，则称关系R为R的自反（对称，传递）闭包，记作r(R)(S(R),t(R) 定理3.5.3 设R的非空有穷集合A上的二元关系。 （1）r(

34、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到这样的终点没有边，就加上此边。 例：设A=a,b,c，给定A上的二元关系R=,求r(R),S(R),t(R),3.6 相容关系与覆盖,定义3.6.1 给定集合A上的关系p，若p是自反的，对称的，则称p是A上的相

35、容关系。,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,d,F=a,b,cd,则B,D,E,F都是A的不同划分。,3.7 等价关系与划分,定理3.7.3 集合A的一个划分确定A的元素间的一个等价关系。 证明： 设集合A有一个划分S=S1,S2,.Sm

36、，先定义一个关系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,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满足自反性

37、，反对称性，以及传递性，则称R是A上的一个偏序关系，并记作。序偶称作偏序集。 例：在实数集R上，证明小于等于关系，“”是偏序关系。 证明：a)对任意实数a，都有aa，故在实数集R上是自反的。 b)对任意实数a,b,有ab,ba，必有a=b,这说明在实数集上是反对称的。 c)对任意实数a,b,c,如果ab,bc,则在实数集上必有ac，所以是传递的。 从上述三点，说明在实数集上是偏序关系。,3.8 序关系,偏序集可以通过图形表示。表示偏序集的图形是哈斯图。画法如下： A中每个元素可用结点表示。对于a，b A，若ab，则将结点a画在结点b下，若a与b之间不存在其他元素c，使ac，cb，则在a与b之间

38、用一直线相连，得到的图形为哈斯图。因偏序集每个结点都有环，画哈斯图时可以省略。,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

39、，则称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的下确界。,3.9 函数的概念,定义3.9.1 设X和Y是任意两个集合，而f是X到Y的一个关系，如果对于每一个x X，有唯一的y Y，使得 f，称关系f为函数，记作： f：XY。 函数与其他关系有别于两点： （1）函数的定义域为X，而

40、不能是X的某个真子集。domf=X。 （2）一个x X只能对应唯一的y Y。 假如 f,则称x为自变量，y称为在f作用下x的像。 f，可记为y=f(x),f(X)=f(x)|x X 如果 f, f,必有y=z，函数y=f(x)的定义域记作domf=X，f的值域ranf Y,3.9 函数的概念,从X到Y的函数，有时也称作X到Y的映射。 定义3.9.4 给定函数f:XY, 若randf=Y，称f是满射的或f为到上的。 若函数f满足x1，x2 X，若x1x2时必有f(x1)f(x2),则称f为入射的。 若函数f即是满射又是入射，则称f为双射。,3.10 复合函数与逆函数,定义3.10.1 设f：XY

41、，g：YZ，合成关系gf=|(x X)(z Z)( y)(y Y)(y=f(x)z=g(y),称gf为f，g的左复合运算或复合运算。 定理3.10.1 设f：XY，g：YZ是两个函数，合成运算gf是XZ的函数，且对每一个x X有(gf)(x)=g(f(x),3.10 复合函数与逆函数,定义3.10.1 设f：XY，g：YZ，合成关系gf=|(x X)(z Z)( y)(y Y)(y=f(x)z=g(y),称gf为f，g的左复合运算或复合运算。 定理3.10.1 设f：XY，g：YZ是两个函数，合成运算gf是XZ的函数，且对每一个x X有(gf)(x)=g(f(x) 例：设集合X,Y,Z，X=x

42、1,x2,x3,x4，Y=y1,y2,y3,y4,y5，Z=z1,z2,z3，函数f：XY，g：YZ定义为：f=,g=,则gf：XZ为：gf=,4.1 代数系统,世界上各种事物的作用，实际上都可以看作是运算。 定义4.1.1 设A，B为任意集合，一个从An到B的映射，称为集合A上的一个n元运算。如果B A，则称该n元运算是封闭的。 在n元运算中，经常遇到的是二元运算。而且在A上对该运算是封闭的。 例：整数集合上的加法、减法、乘法是Z上的二元运算。 例：设A为任意集合，则U,，-、 为A的幂集P(A)上的二元运算。 定义4.1.2 一个非空集合A，连同若干个定义在该集合上的运算f1,f2,f3,

43、.,fk所组成的系统，就称为一个代数系统，记作,4.1 代数系统,定义4.1.3 设A为任意非空集合，*是集合A上二元运算。 封闭性：对任意a，b A，若有a*b A,则称运算*关于集合是封闭的。 结合律：对任意a，b，c A，若有a*(b*c)=(a*b)*c,则称运算*在集合A上是可结合的，或称运算*在A上满足结合律。 交换律：对任意a，b A，若有a*b=b*a,则称运算*在集合A上是可交换的，或称运算*在A上满足交换律。 幂等率：若对 a A，有a*a=a,则称运算*在A上是幂等的，或称运算*在A上满足幂等律。 分配律：若对任意a，b，c A，若有a(b*c)=(ab)*(ac)和(b

44、*c)a=(ba)*(ca),则称运算对*在集合A上是可分配的，或称运算对*在A上满足分配律。 吸收律：若和*满足交换律且有：任意a，b A，并有a(a*b)=a,a*(ab)=a,则称运算对*在集合A上是可吸收的，或称运算对*在A上满足吸收律。,4.1 代数系统,定义4.1.4 设*为集合A上二元运算，若存在eL A（或er A），使得对于任意x A，都有eL*x=x（x*er=x）,则称eL（或er）是A中关于*运算的左（或右）幺元（或单位元）。 如果A中一个元素e，它既是左幺元，又是右幺元，则称e是A中关于运算*的幺元。,4.1 代数系统,定义4.1.5 设*为集合A上二元运算，若有一个

45、元素OL A（或Or A），使得对于任意x A，都有OL*x=OL（x*Or=Or）,则称OL（或Or）是A中关于*运算的左（或右）零元。 如果A中一个元素O，它既是左零元，又是右零元，则称O是A中关于运算*的零元。 定理4.1.1 设*是集合A上的二元运算，且在A中有关于运算*的左幺元eL和右幺元er，则eL=er=e，且A中幺元是唯一的。 定理4.1.2 设*是定义在集合A上的二元运算，在A中有关于运算*的左零元OL和右零元Or，则OL=Or=O，且A中零元是唯一的。,4.1 代数系统,定义4.1.6 设代数系统中，e是关于*运算的单位元，若对A中某个元素a，存在A的一个元素b，使得b*a

46、=e,则称b是a的左逆元；a*b=e,则称b是a的右逆元。如果一个元素b，它既是a的左逆元，又是a的右逆元，则称b是a的一个逆元，记作b-1 一个元素的左逆元不一定等于它的右逆元，而且一个元素可以有左（右）逆元而没有右（左）逆元。一个元素的左右逆元也不一定是唯一的。,4.2 半群与独异点,定义4.2.1 设*是集合S的上的二元运算，若运算*是封闭的，并且*是可结合的，则称这个代数系统为半群。 这个定义包括两点，即对任意a，b，c S， （1）a*b S （2）a*(b*c)=(a*b)*c,4.2 半群与独异点,定理4.2.1 设为一个半群，B S，且运算*在B上是封闭的，那么也是一个半群，通

47、常称是半群的子半群。 定义4.2.2 若半群中存在一个幺元，则称为独异点。（或含幺半群） 定理4.2.2 设是独异点，对于a，b S，且a，b均有逆元，则： (1)(a-1)-1=a (2)若a*b有逆元，则(a*b)-1=b-1*a-1,4.3 群与子群,定义4.3.1 设为一个代数系统，其中G是非空集合，*是G上一个二元运算， 如果*是封闭的； 运算*是可结合的； 存在幺元e； 对于每一个元素x G，存在它的逆元x-1； 则称是一个群。,4.3 群与子群,定义4.3.2 设为一个群，如果G是有限集合，则称是有限群。G中元素的个数通常称为有限群的阶数，记为|G|。,4.3 群与子群,定义4.3.4 设为一个群，若运算*在G上满足交换律，则称G为交换群或Abel群。 定义4.3.5 设为一个群，若a G，使得ak=e成立的最小正整数k称为a的阶，记作|a|。,4.3 群与子群,定理4.3.1 设为一个群，任意a,b G，有： (a-1)-1=a (ab)-1=b-1a-1 anam=an+m (an)m=anm 若G为Abel群，(ab)n=anbn,n Z,4.3 群与子群,定义4.3.6 在代数系统中，如果存在