离散数学－集合论 南京大学计算机科学与技术系 关系及其运算 离散数学－集合论 南京大学计算机科学与技术系

回顾 集合的基本概念 集合运算 集合及其描述 集合相等、子集关系 幂集、笛卡尔乘积 交并补、广义交、广义并 集合恒等式 集合相关命题的证明方式

提要 关系的定义 关系的表示 关系的运算 0-1矩阵运算 关系的性质

有序对（Ordered pair） (a, b)是集合{{a}, {a, b}}的简写 次序的体现 (x,y)=(u,v) iff x=u 且 y=v 若{{x},{x,y}}={{u},{u,v}}，则{x}={u}或{x}= {u,v}, 因此x=u。 假设yv (1) 若x=y, 左边={{x}}, 而vx,右边{{x}}; (2) 若xy,则必有{x,y}= {u,v}, 但y既非u,又非v, 矛盾。

笛卡尔乘积（Cartesian Product） 对任意集合A, B 笛卡尔积 AB = {(a, b)|aA, bB} 例：{1,2,3}{a,b} = {(1, a), (3, a) , (3, a), (1, b), (2, b) , (3, b) } 若A，B是有限集合， |AB|= |A||B|

例题 A={1,2}, (A)×A=? |A|=m, |B|=n, |A×B|=?

（二元）关系的定义 若A, B是集合,从A到B的一个关系是AB的一个子集. 关系意味着什么？ 集合, 可以是空集 集合的元素是有序对 两类对象之间建立起来的联系！

从A到B的二元关系 笛卡尔乘积的子集 例子 “从A到B的关系”R；RAB 若A=B： 称为“集合A上的（二元）关系” 常用的数学关系：不大于、整除、集合包含等 网页链接、文章引用、相互认识

特殊的二元关系 集合A上的空关系: 空关系即空集 全域关系 EA: EA ={ (x, y) | x, yA } 恒等关系 IA : IA ={(x, x) | xA }

函数是一种特殊的关系 函数 f : AB R={ (x, f(x)) | xA }是一个从A到B的一个关系

关系的表示 集合表示: R1={(a, β), (b, α), (c, α),(c, γ)} 0-1矩阵 有向图 假设A={a,b,c,d}, B={α,β,γ} // 假设为有限集合 集合表示: R1={(a, β), (b, α), (c, α),(c, γ)} 0-1矩阵 有向图 a b c d    a d c b    A B

若A=B, R中存在序列：(x1,x2), (x2,x3),…,(xn-1,xn) 二元关系和有向图 关系 RAB A和B是集合 有序对集合 (x,y)R 若A=B, R中存在序列：(x1,x2), (x2,x3),…,(xn-1,xn) 有向图 (VD , ED ) 顶点集 VD= AB 有向边集ED 从x到y有一条边 图D中存在从 x1 到 xn 的长度为 n-1的通路

关系的运算（1） 关系是集合, 所有的集合运算对关系均适用 例子: 自然数集合上: “<”  “=” 等同于 “” 自然数集合上: “<”  “=” 等同于 “” 自然数集合上: “”  “”等同于“=” 自然数集合上: “<”  “>”等同于

关系的运算（2） 与定义域和值域有关的运算 例：A={1,2,3,4,5}, B={1,3,5,6}, A上关系R： dom R = {x | y (x,y)R} ran R = {y | x (x,y)R} fld R = dom R  ran R R A = {(x,y) | xA xRy}  R R[A] = {y | x (xA  (x,y)R)}= ran(RA)  ranR 例：A={1,2,3,4,5}, B={1,3,5,6}, A上关系R： R={(1,2), (1,4),(2,3),(3,5),(5,2)}, 求 RB、R[B]、R(1)和R(2)

关系的运算（3） 逆运算 R-1 = { (x, y) | (y,x)R} 注意:如果R是从A到B的关系,则R-1是从B到A的。 例子：(R1R2)-1 = R1-1R2-1 (x, y)  (R1R2)-1  (y, x)(R1R2)  (y, x)R1 或 (y, x)R2  (x, y)R1-1 或 (x, y)R2-1

关系的运算（4） 关系的复合（合成, Composition） 设 R1AB, R2BC, R1与R2的复合（合成）, 记为 R2 ⃘ R1, 定义如下： R2 ⃘ R1={(a, c) AC | bB ((a, b) R1(b, c)R2) }

复合关系的图示 (a, c)R2 ⃘ R1 当且仅当 aA, cC, 且存在bB，使得(a, b)  R1, (b,c) R2

关系的复合运算：举例 设A={a, b, c, d}, R1, R2为A上的关系，其中： R1 = { (a, a), (a, b), (b, d)} R2 = {(a, d), (b, c), (b, d), (c, b)} 则： R2 ⃘ R1 = {(a, d), (a, c), (a, d)} R1 ⃘ R2 = {(c, d)} R12 = {(a, a), (a, b), (a, d)}

关系的复合运算的性质（1） 结合律 给定R1AB, R2BC, R3CD, 则： (R3 ⃘ R2) ⃘ R1 = R3 ⃘ (R2 ⃘ R1) 证明左右两个集合相等.

关系的复合运算的性质（2） 复合关系的逆关系 给定R1AB, R2BC, 则： (R2 ⃘ R1)-1 = R1-1 ⃘ R2-1 同样，证明左右两个集合相等 (x, y) (R2 ⃘ R1)-1  (y, x) R2 ⃘ R1  tB ((y, t)R1  (t, x)R2) tB ((t, y) R1-1(x, t)R2-1 ) (x, y) R2-1 ⃘ R1-1

关系的复合运算的性质（3） 对集合并运算满足分配律 给定FAB, GBC, HBC, 则： (GH) ⃘ F = (G ⃘ F)  (H ⃘ F) 对集合交运算： (G  H) ⃘ F  (G ⃘ F)  (H ⃘ F) 注意：等号不成立。 A={a}, B={s,t}, C={b}; F={(a,s), (a,t)}, G={(s,b)}, H={(t,b)}; GH=Ø, (G ⃘ F)  (H ⃘ F)={(a,b)}

0-1 矩阵运算 令0-1矩阵M1=[aij],M2=[bij]: 令rs矩阵M1=[aij]；st矩阵M2=[bij]: C=M1  M2: cij=1 iff. aij=bij=1 C=M1  M2: cij=1 iff. aij=1或bij=1 令rs矩阵M1=[aij]；st矩阵M2=[bij]: C=M1 M2: cij=1 iff.

关系运算的矩阵法（1） 命题

证明：

关系的性质：自反性 reflexivity 集合A上的关系 R 是: 自反的 reflexive：定义为：对所有的 aA, (a,a)R 反自反的 irreflexive：定义为：对所有的aA, (a,a)R 注意区分”非”与”反” 设 A={1,2,3}, RAA {(1,1), (1,3), (2,2), (2,1), (3,3)} 是自反的 {(1,2), (2,3), (3,1)} 是反自反的 {(1,2), (2,2), (2,3),( 3,1)} 既不是自反的，也不是反自反的

这里IA是集合A上的恒等关系,即: IA={(a,a)| aA } 自反性与恒等关系 R 是 A 上的自反关系  IAR, 这里IA是集合A上的恒等关系,即: IA={(a,a)| aA } 直接根据定义证明：  只需证明：对任意(a,b) ，若(a,b)IA, 则(a,b)R  只需证明：对任意的a, 若aA, 则(a,a)R

自反关系的有向图和0-1矩阵 a b c A={a,b,c}

关系的性质：对称性 Symmetry 集合A上的关系R是: 对称的 symmetric：定义为：若 (a,b)R, 则 (b,a)R 反对称的 anti-~：定义为：若(a,b)R 且(b,a)R ，则a=b 设 A={1,2,3}, RAA {(1,1),(1,2),(1,3),(2,1),(3,1),(3,3)} 是对称的 {(1,2),(2,3),(2,2),(3,1)} 是反对称的

理解对称性 关系R满足对称性：对任意(a,b)，若 (a,b)R, 则 (b,a)R 注意：是对称关系。 反对称并不是对称的否定: ( 令：A={1,2,3}, RAA) {(1,1),(2,2)} 既是对称的，也是反对称的 是对称关系，也是反对称关系。

对称性与逆关系 R 是集合A上的对称关系  R-1=R  证明一个集合等式 R-1=R 若(a,b)R-1, 则(b,a)R, 由R的对称性可知(a,b)R, 因此：R-1R; 同理可得：RR-1;  只需证明：对任意的(a,b) 若(a,b)R, 则(b,a)R

对称关系的有向图和0-1矩阵 a b c A={a,b,c}

关系的性质：传递性 transitivity 集合A上的关系R是 传递的 transitive: 若 (a,b)R, (b,c)R, 则 (a,c) R 设 A={1,2,3}, RAA {(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,3)} 传递的 {(1,2),(2,3),(3,1)} 是非传递的 {(1,3)}? ?

传递性与关系的乘幂 关系的复合(乘)运算满足结合律，可以用 Rn 表示 R◦ R◦…◦ R (n是正整数) 命题：(a,b)Rn 当且仅当：存在t1,t2,…,tn-1A, 满足：(a,t1),(t1,t2),…,(tn-2,tn-1),(tn-1,b)R。 对n>=1用数学归纳法：n=1, trivial. 奠基n=2,直接由关系复合的定义可得；归纳基于：Rn=Rn-1 ◦R 集合A上的关系R是传递关系  R2R 必要性：任取(a,b) R2 ,根据上述命题以及R的传递性可得(a,b)R 充分性： 若(a,b)R, (b,c)R, 则(a,c)R2, 由R2R可得： (a,c)R，则 R是传递关系

传递关系的有向图和0-1矩阵 a b c A={a,b,c}

一些常用关系的性质 =  < | 3  E 自反   反自反 对称 反对称 传递

关系运算与性质的保持 自反 反自反 对称 反对称 传递 R1-1  R1R2 R1R2  R1R2

习题举例一 下列关系是否自反的、对称的、反对称的或可传递的？关系S为：r1≤ | r2| (r1,r2∈R)时

小结 关系：笛卡尔积的子集 关系的运算 0-1矩阵运算 关系的性质 集合运算；复合运算；逆 reflexivity, ir-~; symmetry, anti-~; transitivity 图特征；矩阵特征

作业 教材内容：[Rosen] 2.1.3、8.1 节 8.3节 课后习题： 见课程主页

离散数学－集合论 南京大学计算机科学与技术系 函数及其运算 离散数学－集合论 南京大学计算机科学与技术系

回顾 关系：笛卡尔积的子集 关系的运算 0-1矩阵运算 关系的性质 集合运算；复合运算；逆 reflexivity, ir-~; symmetry, anti-~; transitivity 图特征；矩阵特征

提要 函数的定义 子集的像 单射与满射 反函数 函数的复合 函数加法与乘法

函数(function)的定义 设 A 和 B 为非空集合，从集合A到B的函数 f 是对元素的一种指派，对A的每个元素恰好指派B的一个元素。记作 f :AB。 Well defined(良定义) f :AB：函数的型构 f 的定义域（domain）是A，f 的伴域（codomain）是B 如果 f 为A中元素a指派的B中元素为b，就写成 f(a)=b。此时，称 b是a的像，而a是b的一个原像。 A中元素的像构成的集合称为f的值域 range （ f的像 image）。 函数也称为映射(mapping)或变换(transformation)

函数的集合定义

函数的集合定义（续）

函数举例 下取整函数 x: R → Z 函数 f 的图像: {(a, b) | aA  f(a)=b} y x Java Program int floor(float real) {…} floor: float → int 函数 f 的图像: {(a, b) | aA  f(a)=b}

函数举例 函数原型 某课程成绩 Program CourseGrade grade(StudentName sname，CourseName cname) {…} 函数型构 (signature) Function： Grade: StudentName ×CourseName→ CourseGrade 姓名 课程 成绩 张明 离散数学 A 李宁 程序设计 B 王琴 数据结构 …

函数举例 设A为非空集合，A上的 恒等函数A:AA定义为 设U为非空集合，对任意的AU, 特征函数A:U{0,1} 定义为： A(x)=x，xA 设U为非空集合，对任意的AU, 特征函数A:U{0,1} 定义为： A(x)=1，xA A(x)=0，xU-A

函数的集合

函数(function)的相等 函数相等 f=g if 若A和B皆是非空的有限集合，从A到B的不同的函数有？个 dom(f)=dom(g) codom(f)=codom(g) x(xdom(f) →f(x)=g(x)) 若A和B皆是非空的有限集合，从A到B的不同的函数有？个 |B||A|个。(a1, a2,…, a|A|的像, 均有|B|种选择)

函数的相等

子集在函数下的像 设 f 是从集合A到B的函数，S 是A的一个子集。 S 在 f 下的像，记为f(S)，定义如下： f (S)={ t | sS (t= f (s)) } 备注：f (A) 即为 f 的值域。

S的像和逆像 b的逆像 c a b f(S):T S T的逆像是什么？ B A S的像:T f

并集的像 设函数 f: AB，且X，Y是A的子集，则 f (XY) = f(X)f (Y) 证明: 对任意的t，若tf (XY) , 则存在sXY, 满足f(s)=t; 假设sX, 则tf(X), 假设sY, 则tf(Y), tf (X)f(Y) f(X)f (Y)  f (XY) 对任意的t，若tf (X)f(Y) 情况1：tf (X), 则存在sX XY, 满足f(s)=t, t f (XY) 情况2： tf (Y), 同样可得t f (XY)  t f (XY)

 交集的像 设函数 f : AB，且X，Y是A的子集，则 f (XY)  f(X)f (Y) B A f 在f(X)f (Y)中，但不在f (XY)中 X a1  c Y B A a2 f

函数性质 :AB是单射（一对一的） :AB是满射（映上的） :AB是双射（一一对应） injection, injective function, one-to-one function x1, x2A, 若x1x2，则(x1) (x2) //等价的说法：x1, x2A, 若(x1) =(x2)，则x1=x2 //另一种等价的说法？ :AB是满射（映上的） surjection, surjective function, onto function yB, xA, 使得(x)=y //等价的说法：f (A)=B :AB是双射（一一对应） bijection, bijective function, one-to-one correspondence 满射+单射

函数性质的证明 判断:RRRR, (<x,y>) = <x+y, x-y>的性质 单射？ 满射？ x1+y1=x2+y2且x1-y1=x2-y2,易见： x1=x2且y1=y2 <x1, y1>=<x2, y2> 满射？ 任取<a, b> R×R，总存在<(a+b)/2,(a-b)/2>,使得 (<(a+b)/2,(a-b)/2>)=<a, b>

函数性质的证明 设A有限集合，f 是从A到A的函数。f 是单射当且仅当 f 是满射。

反函数 设f 是从A到B的一一对应，f 的反函数是从B到A的函数，它指派给B中元素b的是A中满足f(a)=b的（唯一的）a。 f 的反函数记作f -1。 f(a)=b 当且仅当 f -1(b)=a 任何函数都有反函数吗？ 例子 :RRRR, (<x,y>) = <x+y, x-y> f -1:RRRR, -1 (<x,y>) = <?, ?>

函数的复合 设g是从A到B的函数，f是从B到C的函数，f和g的复合用f  g表示，定义为： (f  g) (x)= f(g(x))， xA f g g f a g(a) f(g(a)) C A B

复合运算的性质 函数的复合满足结合律 满射的复合是满射 单射的复合是单射 双射的复合是双射 设f 是从A到B的双射 (f  g)  h = f  (g  h) 满射的复合是满射 单射的复合是单射 双射的复合是双射 设f 是从A到B的双射 f -1  f = A f  f -1 = B

复合运算

复合运算

但是… 若f  g是满射，能推出f 和g是满射吗？ 若f  g是单射，能推出f 和g是单射吗？ f一定是满射， g不一定是满射。

B A C g f

B A C g f

函数的加法、乘法 设f和g是从A到R的函数，那么 f+g 和 f g也是从A到R的函数，其定义为 (f+g)(x) = f(x) + g(x) ， xA f g(x) = f(x) g(x) ， xA

递增（递减）函数 设f的定义域和伴域都是实数(或其子集)， f是递增的 f是严格递增的 x y (xy  f (x)f(y))

练习

练习

一个有趣的例子 反证法：给定任一种排列，假设严格递增与递减序列最大长度均不大于n： 自然数1,2,3,…,n2+1的任何一种排列中，必然含一个长度不小于n+1的严格递增链或严格递减链。 7,4,3,5,2,1,9,8,6,10//////10,3,2,6,4,7,5,9,1,8 在所给的序列中，以k开始的严格递增序列长度为I(k), 以k开始的严格递减序列长度为D(k)。 f: k  (I(k), D(k)), k{1,2,…, n2+1} f(7)=(3,5),f(4)=(4,4),f(3)=(4,3),f(5)=(3,3),f(2)=(3,2),f(1)=(3,1) f(9)=(2,3),f(8)=(2,2),f(6)=(2,1),f(10)=(1,1) f是单射：对于k1k2，如果k1排在k2前面，则I(k1)I(k2)，如果k2排在k1前面，则D(k2)D(k1)。 反证法：给定任一种排列，假设严格递增与递减序列最大长度均不大于n： f的值域最多有n2个元素 f不可能是单射

作业 教材[2.3] 见课程主页