南京大学：《离散数学》课程教学资源（PPT课件讲稿）集合论（关系及其运算、函数及其运算）

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

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

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

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

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

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

有序对( Ordered pair) (a,b)是集合{a},{a,b}的简写 ●次序的体现 (xy)=(ly)ifx=且y=v 若{x},{xy}={l},txy},则{x}={l}或{x}={ly},因此x=l 假设y≠ (1)若xy左边={{x},而wx:右边共{x}; (2)若x,则必有{xy}={u,v},但y既非n,又非,矛盾

有序对（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 produc 对任意集合A,B 笛卡尔积AxB={(anb)a∈A,b∈B} 例:{1,2,3}×{a,b}={(1,a),(3,a),(3,a), (1,b),(2,b),(3,b) 若A,B是有限集合,MxB|=×B

笛卡尔乘积（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},p(4)×A=? ●|=m,|B=n,A×B=?

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

(二元)关系的定义 ●若A,B是集合,从A到B的一个关系是AxB的 个子集 ●集合,可以是空集 集合的元素是有序对 ●关系意味着什么? ●两类对象之间建立起来的联系

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

从A到B的二元关系 ●笛卡尔乘积的子集 “从4到B的关系”R; RcAxB °若A=B:称为“集合A上的(二元)关系” ●例子 常用的数学关系:不大于、整除、集合包含等 网页链接、文章引用、相互认识

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

特殊的二元关系 ●集合A上的空关系必空关系即空集 全域关系EAEA={(x,y)|x,y∈A} 恒等关系1:l={(x,x)|x∈A}

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

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

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