离散数学课件 第四章 二元关系和函数

离散数学

Discrete

Mathematics第四章二元关系和函数4.1二元关系及其表示4.2关系的运算4.3关系的性质4.4关系的闭包4.5等价关系4.6偏序关系4.7函数4.8应用24.1

二元关系及其表示第4章二元关系和函数

序偶和笛卡儿积二元关系的概念关系的表示3离散数学历史人物——笛卡尔4离散数学1613年，在普依托大学学习法律与医学1618年，在荷兰入伍，随军远游1622年开始，用4年时间游历欧洲1628年移居荷兰，致力于哲学、数学、天文学、物理学、化学和生理学等领域进行研究法国哲学家、数学家物理家解析几何之父勒内·笛卡尔（1596-1650）几何图形是直观的，而代数方程是抽象的，能不能把几何图形与代数方程结合起来序偶和笛卡儿积5

离散数学序偶和笛卡儿积6

离散数学有序n元组7

离散数学笛卡儿积8

离散数学笛卡儿积9

离散数学笛卡儿积的性质10不适合交换律

A

B

B

A(A

B,A

,B

)不适合结合律

(A

B)

C

A

(B

C)(A

,B

)对于并或交运算满足分配律

A

(B

C)=(A

B)

(A

C)(B

C)

A=(B

A)

(C

A)

A

(B

C)=(A

B)

(A

C)(B

C)

A=(B

A)

(C

A)若A或B中有一个为空集，则A

B就是空集.

A

=

B=

若|A|=m,|B|=n,

则|A

B|=mn

离散数学性质的证明11证明(B

C)

A=(B

A)

(C

A)证任取<x,y><x,y>∈(B∪C)×A

x∈(B∪C)且y∈A

x∈B或x∈C且y∈A

x∈B且y∈A或x∈C且y∈A

<x,y>∈B×A或<x,y>∈C×A

<x,y>∈(B×A)∪(C×A)所以有(B

C)

A=(B

A)

(C

A).离散数学笛卡儿积的推广12

离散数学笛卡儿积的推广13

离散数学笛卡儿积的推广14定义4.4

设A1,A2,…,An是n个集合（n≥2），它们的n阶笛卡儿积记作，A1×A2×…×An其中A1×A2×…×An={<x1,x2,…,xn>|x1∈A1∧x2∈A2∧…xn∈An}当A1=A2=…=An=A时，有A1×A2×…×An=An。说明：（1）笛卡尔积是两个集合中元素的有序对，对有限集，可以进行多次笛卡尔积运算。A×A×·····×A=An（2）笛卡尔积的多次运算是前结合。((((A×A)×A)·····×A=An离散数学二元关系的概念15引例：设甲、乙、丙三人进行乒乓球比赛，假设比赛结果是乙胜甲，甲胜丙，乙胜丙，则结果可记作{<乙,甲>,<甲,丙>,<乙,丙>}，其中<x,y>表示x胜y。它表示了集合{甲,乙,丙}中元素之间的一种胜负关系。离散数学二元关系的概念16

离散数学二元关系的概念17

离散数学二元关系的概念18

离散数学二元关系的推广19

离散数学关系的表示20离散数学

注意：A,B为有穷集，关系矩阵适于表示从A到B的关系或者A上的关系，关系图适于表示A上的关系。A={1,2,3,4},R={<1,1>,<1,2>,<2,3>,<2,4>,<4,2>},R的关系图GR如下：关系的表示21

离散数学关系的表示22

离散数学二元关系的概念23

离散数学4.2关系的运算第4章二元关系和函数

关系的逆运算关系的复合运算关系的幂运算24离散数学关系的基本运算定义25

离散数学关系的基本运算定义26

离散数学关系的基本运算定义27

离散数学关系的逆运算28

离散数学关系的逆运算29

离散数学逆运算的性质30

离散数学性质的证明31

离散数学关系的复合运算32

离散数学关系的复合运算33

离散数学关系的复合运算34

离散数学证明

对关系的复合运算35

离散数学

关系的幂运算36

离散数学

关系的幂运算37

离散数学

4.3

关系的性质第4章二元关系和函数

自反性与反自反性对称性与反对称性传递性38离散数学自反性与反自反性39

离散数学自反性与反自反性40

离散数学

(a)(b)(c)自反性与反自反性41

离散数学对称性与反对称性42

离散数学对称性与反对称性43

离散数学对称性与反对称性44

离散数学其关系图如下所示对称性与反对称性45显然，对称性和反对称性这两个性质既不互补，也不互相排斥，即不是对称的，不一定是反对称的，反对称的也不一定不是对称的，一个关系即可以是对称的，也可以是反对称的，也可以即不是对称的，也不是反对称的。从关系矩阵上看，对称关系的关系矩阵是一对称矩阵，反对称关系的关系矩阵在以主对角线为轴的对称位置上不能同时为1。从关系图上看，对称关系的关系图，如果两个不同结点间有边，则一定有方向相反的两条边，反对称关系的关系图中，两个不同结点间不能有方向相反的两条边。离散数学传递性46

离散数学传递性47

离散数学

传递性48

离散数学

传递性49

离散数学定理的证明50

离散数学定理的证明51

离散数学关系性质的判定方法52离散数学4.4关系的闭包第4章二元关系和函数

自反闭包对称闭包传递闭包53离散数学关系的闭包

54

离散数学关系的闭包

55

离散数学

关系的闭包

56

离散数学

关系闭包

57离散数学

关系的闭包

58

离散数学

关系的闭包

59

离散数学关系的性质与运算的关系

60离散数学运算原有性质

自反性反自反性对称性反对称性传递性PPPPPPPPPPPPPOOOPPPOPOOOO关系的闭包

61

离散数学

4.5

等价关系第4章二元关系和函数

等价关系定义集合的划分等价类与商集62离散数学等价关系定义63定义4.17

设R为非空集合A上的关系.如果R是自反的、对称的和传递的,则称R为A上的等价关系.设R是一个等价关系,若<x,y>∈R,称x等价于y,记做x～y.

例如，实数集上的相等关系，平面上三角形集合上三角形的相似关系等都是等价关系。但是直线间的平行关系不是等价关系，因为它不是自反的。以人为集合上的同性别关系是等价关系，但朋友关系不是等价关系，因为朋友关系不具有传递性，父子关系也不是等价关系，因为它不具有对称性。离散数学等价关系64

离散数学等价关系65

离散数学等价关系66

离散数学集合的划分67

离散数学集合的划分68

离散数学等价类与商集69

离散数学

由定义知，等价类依托于A上的等价关系，没有等价关系，就没有等价类。A中每个元素都有与之对应的等价类。等价类与商集70

离散数学等价类与商集71定义4.20

设R为非空集合A上的等价关系,以R的不交的等价类为元素的集合称作A在R下的商集,记做A/R,即A/R={[x]R

|x∈A}.离散数学等价类与商集72

离散数学4.6

偏序关系第4章二元关系和函数

偏序关系偏序集中特殊元素73离散数学偏序关系定义74

离散数学偏序关系定义75

离散数学偏序关系定义76

离散数学盖住关系定义77

离散数学盖住关系定义78例4.31设偏序集的哈斯图如下所示，求集合A的偏序关系R。

离散数学

偏序集中特殊元素79

离散数学偏序集中特殊元素80

离散数学偏序集中特殊元素81

离散数学

偏序集中特殊元素82

离散数学偏序集中特殊元素83

离散数学4.7

函数第4章二元关系和函数

函数的基本概念与性质重要函数函数的复合与逆函数函数的逆运算84离散数学函数定义85

离散数学函数定义86

离散数学函数的性质87

离散数学函数的性质88

离散数学常函数、恒等函数、单调函数89

离散数学常函数、恒等函数、单调函数90

离散数学常函数、恒等函数、单调函数91

离散数学函数复合的定理92

离散数学函数复合运算的性质93

离散数学

函数的逆运算94

离散数学函数的逆运算95

离散数学函数的逆运算96

离散数学函数的逆运算97离散数学

4.8应用第4章二元关系和函数

关系的计算机表示偏序关系在项目管理中的应