离散数学复习2

1、1第二章 谓词逻辑2.1谓词演算的基本概念谓词演算的基本概念2.2谓词演算的关系式谓词演算的关系式2.3前束范式前束范式2.4谓词演算的推理22.1.1 谓词与个体考察以下考察以下2 2个原子命题：个原子命题：（1 1）李华是工程师。）李华是工程师。（2 2）何威是工程师。）何威是工程师。若对这两个原子命题进行内部结构分析，就若对这两个原子命题进行内部结构分析，就会发现它们之间既有会发现它们之间既有相异之处相异之处又有又有相同之处相同之处。相异之处：相异之处：主语不同主语不同相同之处：相同之处：谓语共享谓语共享将相同部分从这类命题中将相同部分从这类命题中分离分离（抽抽象象）出来进行研究）出来进

2、行研究并符号化并符号化。引入一个符号表示引入一个符号表示“x x是工程师是工程师”。(x) 或或( )32.1.1 谓词与个体n像像( () ) 这样抽象形式，实际上就是上述几个语句中描述主语性质的这样抽象形式，实际上就是上述几个语句中描述主语性质的谓语结构的谓语结构的抽象形式抽象形式或描述主语所涉及或描述主语所涉及对象之间的关系对象之间的关系的抽象形式的抽象形式。n上述中的上述中的抽象形式抽象形式就是就是谓词谓词。语句中的。语句中的主语或对象主语或对象称为称为个体个体。n个体个体是指可以独立存在的。是指可以独立存在的。谓词谓词是用来刻划个体的性质或关系的。通是用来刻划个体的性质或关系的。通常

3、用常用大写字母大写字母F F,G,HG,H等表示谓词等表示谓词，用，用小写字母小写字母a,b,ca,b,c等表示个体等表示个体。n在原子命题中引进谓词和个体的概念，这种以命题中的谓词为基础的在原子命题中引进谓词和个体的概念，这种以命题中的谓词为基础的分析研究，称为分析研究，称为谓词逻辑谓词逻辑( (或称或称谓词演算谓词演算) )。42.1.1 谓词与个体 个体的变化范围，称为个体的变化范围，称为个体域个体域。 将宇宙间一切事物（所有个体）所组成的个体域将宇宙间一切事物（所有个体）所组成的个体域称为称为全总个体域全总个体域。 以某一个个体域为变域的变元，称为以某一个个体域为变域的变元，称为个体变

4、元个体变元。习惯用小写的习惯用小写的x,y,zx,y,z等表示。等表示。 与个体变元相对的是与个体变元相对的是个体常元个体常元，它指某个确定的，它指某个确定的个体，习惯用小写的个体，习惯用小写的a,b,ca,b,c等表示。等表示。52.1.1 谓词与个体n仅含一个个体变元的谓词，称为一元谓词。n含有n个个体变元的谓词，称为n元谓词。n含有0个个体变元的谓词（但可能包含多个个体常元），称为0元谓词。 n一般地，一元谓词刻画了个体的性质，多元谓词刻画了个体之间的关系。n注意：谓词不是命题，只有当确定的个体“填入”后，才成为命题。 (x)(x)(x(x，y)y)(a,b,c)(a,b,c)“张华张华

5、是大学生是大学生”可表示为可表示为F(a)62.1.2 量词)(xxF 全称量词记作 “ x ”，其含意是：“所有的x ”、“每一个x ”、“凡是x ”、“任意的x ”等等。表示表示对个体域中的所有个体其对个体域中的所有个体其谓词谓词F(x)F(x)均为真均为真。72.1.2 量词)(xxF 存在量词记作 “ ”，其含意是：“存在着x ”、“有些x ” 等等。表示表示个体域中存在个体域中存在某些个体某些个体其其谓词谓词F(x)F(x)均为真均为真。x8函数 在谓词逻辑中，在谓词逻辑中，个体与个体间有一定的关系个体与个体间有一定的关系，这种关这种关系称为函数系称为函数。)(xf),(yxf),(

6、21nxxxf一元函数一元函数二元函数二元函数 多元函数多元函数例：李平的妈妈是医生。D(x)：x是医生；a：李平；f(a)：李平的妈妈；句子符号化为：D(f(a)9用谓词和量词表示句子的步骤：n参考题目给出的个体域，如果没有指明，假设为全总个体域；n确定句子中的谓词和个体变元；在全总个体域下，句子中的名词（人、数、动物等）都需要使用特性谓词表示；多元谓词使用多个不同的个体变元。n根据句子中特性谓词前的修饰词选择量词； ：“所有的”、“凡是”、“一切”、“任意”、“每一个”等词，或省略的情况 ：“存在”、“有些”、“某些”、“几个”等词n根据量词确定谓词之间的关系； 所限定的个体变元所在的特性

7、谓词和其他谓词之间使用条件连接词。 所限定的个体变元所在的特性谓词和其他谓词之间使用合取连接词。10例1.没有不犯错的人)()(xWxMxnM(x)：x是人nW(x)：x犯错11例2.对于所有的正实数x,y，都有x+yx。),()()(yxPySxSyxnS(x)：x是正实数nP(x，y)：x+yx12练习n课后题1.29（8）（9）（10）132.1.3 谓词逻辑公式（公式 ）谓词逻辑公式中所使用的符号有以下七种:(1)个体常量符:(2)个体变量符:(3)函数符:(4)谓词符:(5)联结词符:(7)括号(,)(6)量词符:, 一个谓词逻辑公式中是由上述符号按一定上述符号按一定规则规则所组成的

8、所组成的符号串符号串。a,b,c, x,y,z f,g,h F,G,H142.1.3 谓词公式（续）例如，下列各式是谓词公式。但下列各式不是谓词公式。)()(yRxQy)P(x,y)x)()y)y)Q(x,()x(P(x)(y)x,P(y)x)(E(y)x)()x(x)P()z, y(RQ(x)z, y,x(P)(z(y)x)(15练习：n下列哪些是谓词公式：)()(.(7)()(. 6)(. 5)(),(. 4)()(. 3),(),),(. 2),(. 1xPxxyPxPxZPyxzxPxyxPxyyQxPxyxQzyyxpAyxyxP162.1.4 自由变元和约束变元由于全称量词的作用，

9、使得命题函数中的x不再起变元的作用，或者说，量词约束了x的变元作用，在这种情况下，称变量x为“约束出现”，并称x为约束变元。又如在这个谓词公式中，易见，x是约束元，但y不是约束元，称y是“自由出现”，并称y为自由变元。量词后括号括号中的内容中的内容称为量词的作用域或辖域。Q(x)x)(P(x)()Q(x)y),(P(xx)(x)Q(x)y),(P(xx17换名规则 在对约束元换名时，应遵循以下两种规则（约束元换名规则）：（1）对约束元（如x）换名时，更改的名称范围是 或中的x以及量词作用域中所出现的所有x，在量词作用域外的部分不换名。（2）换名时一定要更改为作用域中没有出现的变量名称xx18例

10、1解：在这个谓词公式中，x既是约束元又是自由元，y也是约束元又是自由元。若把约束元x换名为u，约束元y换名为v，经换名后，谓词公式可写成为于是可知，u，v是约束元，x，y是自由元。y)R(x,(Q(y)y)(Q(x)y)(P(x,x)()R(x,)(Q()()Q(y),(P()(vvvuuu19代入规则n对于谓词公式中的自由变元，也可以更改，这种更改称为代入，代入时应对谓词公式中出现该自由变元的每一处都进行。这称为自由元代入规则n例如， 可更改为y)R(x,P(x)x)(y)R(z,P(x)x)(20例1（续）n对下列谓词公式中自由元进行代入，使得一个变量在谓词公式中只呈一种形式（约束元或自由

11、元）出现。 y)R(x,(Q(y)y)(Q(x)y)(P(x,x)(21谓词关系式n将命题公式的等价关系命题公式的等价关系可以推广为谓词公式的等价关系谓词公式的等价关系：QPQP)(),(xxQxxP)()()()(xxQxxPxxQxxP例如：命题公式将P和Q分别替换为：公式就可变为：22谓词公式（等价或蕴含）关系式n由于量词的引入，谓词公式多了如下公式：)()(.8)()(.7)()(.6)()(.5)()()(.4)()()(.3)()()()(.2)()()()(.1xxBAxBAxxxBAxBAxxxBAxBAxxxBAxBAxxAxxAxxAxxAxxxBxxAxBxAxxxBxx

12、AxBxAx存在服从对的分配律全称服从对的分配律全称量词变为存在量词存在量词变为全称量词否定否定深入深入5、6、7、8其中的A是没有出现约束变元x的谓词公式。量词作用域的扩张和收缩23关系式)()(.14)()(.13)()(.12)()(.11)()()()(.10)()()()(. 9xBAxxxBAxBAxxxBABxAxBxxABxAxBxxAxxBxxAxBxAxxBxAxxxBxxA全称对不服从分配律存在对不服从分配律24对偶定义 设A是命题公式，且A中仅有联结词 ， ，量词 ， 。在A中把，F，T， ， ，分别换成，T，F， ， 后所得的命题公式称为A的对偶公式。25对偶n例：

13、的对偶式：)(BxAx)(BxAx26练习：写出对偶式)()(xyyRxP)()(xyyRxP272.3 前束范式定义定义:一个公式，如果量词均非否定地在全式的开头，且公式除量词外，最多只含，则称此公式叫前前束范式。束范式。例： xyz( Q(x,y) R(z) (前束范式)(x) P(x)(y)Q(y), (x)(P(x)(y)Q(x,y)(),()()()(zRyxQzxy)(),()()(yQyxPyxXXXX28前束范式n求解的一般步骤（不唯一）：n1.运用基本等价公式，把各种联结词转换成基本联结词： 、和n2.运用E1、E8、E9、E24、E25、E26等将公式中的深入到各谓词变元的

14、前面。n3.利用换名、代入规则，使所有的约束变元均不同名，且自由变元与约束变元也不同名。n4.利用E27、E28 、E29 、E30 、E31 、E32扩大量词的作用域至整个公式。29前束范式n例：把xP(x) R(x)变成前束范式n xP(x) R(x) yP(y) R(x) y(P(y) R(x)n例：把xP(x) xQ(x) 变成前束范式。 xP(x) xQ(x) xP(x)xQ(x) xP(x) xQ(x) x(P(x) Q(x) 30前束范式n例. 将公式(x)P(x)(y)Q(y)(x)R(x)化归为前束范式 原式 (x)P(x)(y)Q(y)(x)R(x) (x)P(x)(y)Q

15、(y)(x)R(x) (x)P(x)(y)Q(y)(z)R(z) (x)(y)(z)(P(x)Q(y)R(z) 量词前移31练习n课后题 1.32（2）32第三章 集合n3.1集合的基本概念n3.2集合的运算及基本公式n3.3幂集n3.4包含排斥原理n3.5集合的直积333.1.1 集合的表示n一般用大写的英文字母A, B, C, 来代表集合，|A|表示集合中元素的个数；n用小写的英文字母a , b , c, 来代表集合中的元素。n一些特殊集合的表示：n代表自然数集合，n代表整数集合，n代表有理数集合，n代表实数集合，n代表复数集合343.1.1 元素与集合的关系n如果b是集合A中的元素，称b

16、属于属于A，并记作n如果b不是集合A中的元素，称b不属于不属于A，并记作AbAbn例如：QNZZN2,1,1,5,135练习：列出下列集合的元素n(1) x,|xN t (t2,3 x=2t)n(2) x,|xN ts (t0,1 s 3,4 txs)n(3) x,|xN t (t整除整除2 xt)4,64,61,2,31,2,3N-1,2N-1,236空集和全集空集和全集n不含有任何元素的集合称为空集，记作n研究对象的全体称为全集，记作E。nE=x|P(x) P(x)n注意：全集是个相对性的概念，由于研究的问题不同，所取的全集也不同，即使是同一个问题也可以有不同的全集37【例】确定下列命题是

17、否正确？n(1)n(2)n(3)n(4) n(5)n(6)n(7)n(8) ,cbacbaba,b, a, c,b, aba,b, a, b, aba,b, a,b, aba,XX383.2 集合的运算及其基本公式n1.并运算n2.交运算交运算n3.差集差集n4.补集补集n5.布尔和布尔和393.2 集合的运算及其基本公式3.差集：设A，B是集合，由所有属于属于A但不属于不属于B的元素构成的集合称为A对B的差集差集，记作：A-B 例如: A = 1，2，3，4，B = 3，4，5 差集 A B = 1 , 2 , B AAB=5403.2 集合的运算及其基本公式n4.补集n集合A的补集补集 A

18、可定义为 A=E A =x| (xA)A413.2 集合的运算及其基本公式n5.布尔和（对称差）n集合A,B的布尔和（对称差）A+B 定义为： A+B=(A - B) (B - A)AB A+B=(A B) -(A B)42练习：n3.E=0,1,2,3,4,5,6,7,8,9,A=2,4,5,6,8,B=1,4,5,9,C=x|xZ+,2x5求：AB,C-B,(CB)A0,1,2,3,6,7,8,90,1,2,3,6,7,8,92,32,30,1,3,4,5,7,90,1,3,4,5,7,9433.3 幂集定义：设A是集合，由A的所有子集作为元素构成的集合称为A的幂集，记作AA2)(或幂集的

19、符号化表示幂集的符号化表示 = x| )(AAx 例：设集合例：设集合 A = 1, 2A = 1, 2，则其幂集，则其幂集2,1,2,1,)(A例：设集合例：设集合 A = aA = a，b b，c c ，则其幂集，则其幂集 ,)(AcbcabacbaA44练习练习:1,1)3(,)2(,) 1 (,)() 1 (1 ,1,1 ,1,)1 ,1()3( 分别求下列集合的幂集分别求下列集合的幂集解：它们的幂集分别为解：它们的幂集分别为 ,)()2(45幂集n2定理定理： 设集合设集合A A是由是由n n个元素个元素所组成的有所组成的有限集，则限集，则A A的幂集的幂集是有限集是有限集，且由，且

20、由个元素组成。也即个元素组成。也即|(A)|=n2将集合中元素的个数称为将集合中元素的个数称为基数基数。463.5 笛卡尔乘积n1.有序对(有序偶)和有序n元组定义定义：由两个客体由两个客体a和和b(允许允许a=b）按一定的顺序排）按一定的顺序排列成的列成的二元组二元组称为一个称为一个有序对有序对，记作，记作（a , b）,其中其中a称为有序对的称为有序对的第一客体第一客体，b称为有序对的称为有序对的第二客体第二客体如：平面直角坐标系中点的坐标如：平面直角坐标系中点的坐标(x,y)就是有序对就是有序对定义定义：有序偶有序偶(a(a，b)b)与与(c(c，d) d) ，如果有，如果有a = ca

21、 = c，b = db = d，则称，则称(a(a，b)b)与与(c(c，d)d)是是相等相等的的。 47笛卡儿乘积笛卡儿乘积定义定义：设设A, B A, B 是集合，由是集合，由所有所有以以A A中元素为中元素为第一客体，第一客体，B B中元素为第二客体的中元素为第二客体的有序对有序对构构成的成的集合集合称为称为A A到到B B的的笛卡儿乘积笛卡儿乘积( (直积直积) )，记，记作作A AB B，即，即BbA,ab)(a,BA48笛卡儿乘积笛卡儿乘积例如例如: :设设A = a, b , B = x, y,z,A = a, b , B = x, y,z,则则 A A到到B B的笛卡儿乘积的笛

22、卡儿乘积A AB =(a, x),(a,y),(a, z),(b, B =(a, x),(a,y),(a, z),(b, x),(b, y), (b, z)x),(b, y), (b, z)B到A的笛卡儿乘积BA=(x, a),(y, a),(z, a),(x, b),(y, b), (z, b)49第四章 关系n4.1关系及其运算、关系的表示方式n4.2关系的有关性质n4.3关系的闭包运算n4.4等价关系和相容关系n4.5偏序关系50关系的实质n由于二元关系就是符合某种特定要求的有序对的集合.nA上的二元关系应是A上的笛卡儿乘积A A的子集。n此A到B的二元关系应是笛卡儿乘积A B的子集51

23、n元关系的定义n定义n对于二元关系R,如果 (a, b) R，也可记作aRb，并称a 与b 有关系R。如果(a, b) R，也可记作a R b，并称a与b没有关系R。.,2121的一个子集是元关系所确定的由集合nnXXXnXXX52二元关系的二元关系的定义域定义域和和值域值域n定义 设S是A到B的二元关系，使(x, y) S的所有x组成的集合称为S的定义域，记作D(S)；n使(x, y) S的所有y组成的集合称为S的值域，记作C(S)或R(S)。易知:D(S)就是S的所有有序偶的第一个元素构成的集合, C(S)就是S的所有有序偶的第二个元素构成的集合.53求关系的求关系的定义域定义域和和值域值

24、域n例如:设 则R的定义域D(R) ， 值域C(R) )b,a(),b,a(),b,a(R,b,b,bB,a,a,a,aA3433113214321a,a,a431,31bb54三种特殊的关系n对于任意集合，空集和集合本身都是它的子集，常称这两种子集为平凡子集。n定义笛卡儿乘积A B的两个平凡子集，空集和A B本身称为集合A到B的空关系和全域关系。n定义 设R是A上的二元关系且满足则称R为A上的恒等关系，并记作。)a, a(RAa AI552 关系的表示方法n1.1.关系矩阵关系矩阵 设集合 ，R是A到B的二元关系，令则称为R的关系矩阵.b,b,bB,a,a,aAm2121nR)b,a(0R)

25、b,a(1cjijiij nm2n1nm22221m11211ijRccccccccccM56关系的表示方法n例1:设 R是A到B的二元关系，且则R的关系矩阵为 b,b,b,b,bB,a,a,a,a,a,aA54321654321)b,a(),b,a(),b,a(),b,a(),b,a(),b,a(),b,a(),b,a(R5646255433322111110000001010000001000010000011MRA是行，是行，B是列是列57复合关系n1. 复合关系的定义n定义 R是A到B的二元关系，S是B到C的二元关系，R和S的复合记作RS，它是A到C的二元关系，仅当 (a, b)R，且

26、(b , c)S时，(a, c)RS(a, c)RS。n例:设 ，R是A到B的二元关系，S是B到C的二元关系，且 则R和S的复合 c,c,cC,b,b,b,bB,a,a,aA3214321321)c,b(),c,b(),c,b(),c,b( S)b,a (),b,a (),b,a (),b,a(R2332211143232211)c,a(),c,a(),c,a(),a(SR33322111c58复合关系的矩阵表示n定理 R是A到B的二元关系，其关系矩阵为 ，S是B到C的二元关系，其关系矩阵为 ，复合关系RS是A到C的二元关系，其关系矩阵为 ，则 注意:按普通矩阵乘法求 ,只不过是将乘法改为布尔

27、乘,加法改为布尔加.RMSMSRMSRSRMMMSRMM运算法则与合运算法则与合取连接词一致取连接词一致运算法则与析取运算法则与析取连接词一致连接词一致59例1n设A = 1，2，3，B = a, b, c, d, C = x, y, z，R是A到B的二元关系，R = (1, a), (1, b), (2, b), (3, c)，S是B到C的二元关系，S = (a, x), (b, x), (b, y), (b, z)。求复合关系RS的关系矩阵.n解:因为 n所以000000111001M,010000100011SRM000111111000000111001010000100011MMMS

28、RSR604-2 关系的重要性质n关系的基本类型：自反的二元关系反自反的二元关系对称的二元关系反对称的二元关系可传递的二元关系n或称为关系的性质：自反性、反自反性、对称性、反对称性、可传递性611. 自反的二元关系n定义定义 设设R R是是A A上的二元关系，如果对于上的二元关系，如果对于A A中中每一个每一个元素元素x x ，都有都有(x, x )R(x, x )R，则称，则称R R是是自反的自反的，也称，也称R R具有具有自反性自反性。n例例1 1: A = a, b, c, A: A = a, b, c, A上的二元关系上的二元关系 R = (a, a), (b, b), (c, c),

29、 (a, c), (c, b) R = (a, a), (b, b), (c, c), (a, c), (c, b) ，则则R R是是自反的二元关系。自反的二元关系。n例例2:2:设设A=1,2,3,4,A=1,2,3,4, R=(1,1),(2,2),(3,4),(4,2), R=(1,1),(2,2),(3,4),(4,2),因为因为3A,3A,但但(3,3) , (3,3) , 所以所以R R不是不是A A上的自反关系上的自反关系. .R622. 反自反的二元关系n定义 R是A上的二元关系，如果对于A中每一个元素x,都有(x, x ) ,则称R是反自反的，也称R具有反自反性。n例1:设A

30、 = a, b, c, R = (a, c), (b, a), (b, c), (b, b) n因为(b,b)R, 则R不是A上的反自反关系。 n例2:设A = 1，2，3，R是A上的小于关系，即(1,2),(1,3),(2,3)n由于(1, 1), (2, 2), (3, 3)都不属于R，所以R是A上的反自反关系。R632. 反自反的二元关系n例例3:3:设设A=1,2,3,R=(1,2),(2,3),(3,2),(3,3),A=1,2,3,R=(1,2),(2,3),(3,2),(3,3), S=(1,1),(2,2),(2,3),(3,3), S=(1,1),(2,2),(2,3),(3

31、,3),则则 R R既不是既不是A A上的反自反关系上的反自反关系( (因因(3,3)R),(3,3)R), 也不是也不是A A上的自反关系上的自反关系( (因因(1,1) ) (1,1) ) S S是是A A上的自反关系上的自反关系, ,但不是反自反关系但不是反自反关系. .注意注意: :一个关系一个关系R R如果不是如果不是自反关系，自反关系，不一定是不一定是反自反反自反关系关系. .R643. 对称的二元关系n定义定义 R R是是A A上的二元关系，上的二元关系，每当每当(x, y) R(x, y) R时，就一定时，就一定有有(y, x) R(y, x) R，则称，则称R R是是对称的对

32、称的，也称，也称R R具有具有对称性对称性。n例例1 1: :设设A = a, b, c, R = (a, b), (b, a), (a, A = a, b, c, R = (a, b), (b, a), (a, c), (c, a) c), (c, a) ，所以，所以R R是对称的是对称的。n例例2 2: :设设A=1,2,3,4A=1,2,3,4上的二元关系上的二元关系 R=(1,1),(1,2),(2,1),(3.3),(4,3),(4,4),R=(1,1),(1,2),(2,1),(3.3),(4,3),(4,4),因为因为(4,3)R(4,3)R但但(3,4) (3,4) 。所以所以

33、R R不是对称的不是对称的。 R654. 反对称的二元关系n定义定义 R R是是A A上的二元关系，上的二元关系，当当x yx y时，如果时，如果 (x, y) R(x, y) R，则必有，则必有(y, x)(y, x) ，称，称R R是是反对称反对称的的，也称，也称R R具有具有反对称性反对称性。n例例1:1: A=1,2,3, A=1,2,3,上的关系上的关系R=(1,2),(2,2),(3,1),R=(1,2),(2,2),(3,1),则则R R是是反对称反对称的的. .但但S=(1,2),(1,3),(2,2),(3,1)S=(1,2),(1,3),(2,2),(3,1)不是反对称的不

34、是反对称的. .因因为为1313但但(1,3)S,(1,3)S,且且(3,1)S(3,1)SR664. 反对称的二元关系n例例2:2: 设设A = 2A = 2，3 3，4 4，6 6， ，R R是是A A上的整除关系上的整除关系( (即当即当a, bAa, bA且且a a能整除能整除b b时，（时，（a, ba, b）R)R)，问，问R R是否是是否是A A上的反对称关系上的反对称关系? ?n解解: :因为因为R = R = （2 2，2 2）, ,（2 2，4 4）, ,（2 2，6 6）, ,（3 3，3 3）, ,（3 3，6 6）, ,（4 4，4 4）, ,（6 6，6 6） n由

35、定义知：由定义知：R R是反对称的是反对称的. .n例例3 3: : 实数集合上的实数集合上的小于关系小于关系和和小于等于关系小于等于关系都是都是反对称反对称的的. .674. 反对称的二元关系n例4:设A=a, b, c, d上的关系 R=(a ,a) ,(b ,c) ,(c ,d) ,(d ,c) ,S=(a ,a) ,(b ,b) ,(d ,d),则R既不是对称的(因为(b ,c)R但(c ,b) ),也不是反对称的 (因为(c ,d)R且(d ,c)R) 而S既是对称的,也是反对称的.R684. 反对称的二元关系 小结n注意:对称关系和反对称关系不是两个相互否定的概念. 存在既是对称的

36、也是反对称的二元关系,也存在既不是对称的也不是反对称的二元关系.695. 可传递的二元关系n定义 设R是A上的二元关系， 每当(x, y) R且(y, z) R时，必有 (x, z) R，则称R是可传递的，也称R具有可传递性。n例1:实数集上的小于关系和小于等于关系都是可传递关系.如：ab,bc 则ac705. 可传递的二元关系n例2:设A=a ,b ,c上的关系R=(a ,a) ,(a ,b) ,(b ,c) ,(a ,c), S=(a ,b) ,(c ,b) , T=(a,b) ,(b ,b) ,(b ,c),则R,S,T是否可传递？ R,S是可传递的,T不是可传递的 因为T中有(a ,b

37、)T ,(b ,c) T但(a ,c) ,所以T不是可传递关系T71关系性质总结1n集合A上的自反关系自反关系中必包含A中由每个每个元素自身所组成的有序对自身所组成的有序对。对应关系矩阵主对角线上所有元素都为1；n恒等关系是自反关系，但自反关系不一定是恒等关系。n集合A上的反自反关系反自反关系中必不包含必不包含A中任意一个元素自身所组成的任意一个元素自身所组成的有序对有序对。对应关系矩阵主对角线上所有元素都为0.n对应关系矩阵主对角线上元素有1，但不全为1的关系，既不是自反关系，也不是反自反关系。72关系性质总结2n集合A上的对称关系要求其中每个有序对两个客体前后位置交换后的每个有序对两个客体

38、前后位置交换后的有序对仍在有序对仍在此关系中。对应关系矩阵一定是对称矩阵。n集合A上的反对称关系要求其中每个有序对两个客体前后位置交换后每个有序对两个客体前后位置交换后的有序对一定不在的有序对一定不在此关系中。对应关系矩阵一定不是对称矩阵，但是不对称的矩阵不一定就对应于反对称关系。n恒等关系即为对称关系，又为反对称关系。n关系中存在两个仅客体顺序不同的有序对，但又不全是的关系，既不是对称关系，又不是反对称关系。73等价关系的定义与实例等价关系的定义与实例定义定义 设设 R 为非空集合上的关系为非空集合上的关系. 如果如果 R 是是自反的、对自反的、对称的和传递的称的和传递的, 则称则称 R 为

39、为 A 上的上的等价关系等价关系. 设设 R 是一个等价关系是一个等价关系, 若若(x,y)R, 称称 x 等价于等价于y, 记做记做 xy. 实例实例 设设 A=1,2,8, 如下定义如下定义A上的关系上的关系 R： R = (x,y) | x,yAxy(mod 3) 其中其中 xy(mod 3) 叫做叫做 x 与与 y 模模3相等相等, 即即 x 除以除以3的余数的余数与与 y 除以除以3的余数相等的余数相等. 74 偏序关系偏序关系定义定义 非空集合非空集合A上的上的自反自反、反对称反对称和和传递传递的关系，称的关系，称为为A上的上的偏序关系偏序关系. 实例实例 集合集合A上的上的恒等关

40、系恒等关系 IA 是是A上的偏序关系上的偏序关系. 小于等于关系小于等于关系, 整除关系和包含关系也是相应集合上整除关系和包含关系也是相应集合上的偏序关系的偏序关系. 75偏序关系的定义偏序关系的定义n常常把集合A以及A上的偏序关系R合在一起统称为偏序集，记作（A，R）。n由于偏序关系是自反的、反对称的、传递的二元关系，所以一般用符号“”表示偏序。当(a, b)R，时，常记作ab，偏序集也常记作（A，）。76例：n集合A=2，3，4，6，8n关系R=(x,y)|xA, yA, x整除yn即：R=(2,2),(3,3),(4,4),(6,6),(8,8),(2,4),(2,6),(2,8),(3

41、,6),(4,8)nR为偏序关系；n(A,R)为偏序集。77线性次序线性次序n定义 设设R R是集合是集合A A上的偏序，如果对每个上的偏序，如果对每个x,yx,yA A，必有，必有x xy y或或y y x x ，则称，则称R R是是线性线性次序的次序的( (全序的全序的) )，或称，或称R R是集合是集合A A上的上的线性次线性次序关系序关系。n易知：在易知：在线性次序关系线性次序关系中，中，任意两个元素都任意两个元素都是有关系是有关系的。的。78线性次序线性次序n例在整数集合中，例在整数集合中，大于等于关系大于等于关系是线性是线性序关系。序关系。n例设例设1,3,6,12,24, 1,3

42、,6,12,24, 是是整除关整除关系系 , ,则则是线性次序的是线性次序的, ,并且对并且对A A中元素有中元素有 1 3 6 12 241 3 6 12 2479偏序关系的哈斯图表示n定义 设R是集合A上的偏序关系，a和b是A中的元素，如果(a, b) R，且在A中没有其他元素c，使得 (a, c) R，(c, b) R，则称元素b盖住a。n例1:A = 1，2，3，4，5，6，8，10，12，16，24，R是A上的整除关系，由“盖住”的定义可知，元素4盖住2；但元素8并不盖住2，因为有元素4，使得(2, 4)R和(4, 8)R，所以8不盖住2。利用元素间的盖住关系，能较方便地画出偏序关系

43、的哈斯图(即关系图的简化)80画哈斯图的方法n用平面上的点代表集合中的元素，当b盖住a时，代表b的点应画在代表a的点的上方，并用直线段连接否则不画线n上面例1:A = 1，2，3，4，5，6，8，10，12，16，24，R是A上的整除关系，的哈斯图如下：n n 24 16 12 8 6 4 10 3 2 5 181偏序集中的特殊元素n定义 设(A，)是偏序集，如果A中存在元素a，使得A中没有其他元素x，满足xa，则称a为A中的极小元。n定义 设(A，)是偏序集，如果A中存在元素a，使得A中没有其他元素x，满足ax，则称a为A中的极大元。82偏序集中的特殊元素n定义 设(A，)是偏序集，如果A中存在元素a，使得对于A中任何元素x，都有ax，则称a为A中的最小元。n定义 设(A，)是偏序集，如果A中存在元素a，使得对于A中任何元素x，都有xa，则称a为A中的最大元。n注意:最大(小)元与极大(小)元的区别83偏序集中的特殊元素n例1:A = 2，3，4，6，8，12，16,24，是A上的整除关系。其哈斯图见图1。n由定义可知，(A，)的极小元为2和3，极大元为16和24。 24 16 12 8 6 4 3 2