南京大学：《离散数学 Discrete Mathmatics》课程教学资源（课件讲稿，2018）关系——第12章 关系及其运算

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

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

我粤 回顾 ·良序公理 ·数学归纳法 ·强数学归纳法 。递归定义与结构归纳法

回顾  良序公理  数学归纳法  强数学归纳法  递归定义与结构归纳法

最售 提要 ●关系的定义 (复习) ·关系的表示 (复习) ·关系的运算 (复习) ·0-1矩阵运算（复习） ●关系的性质

提要  关系的定义 （复习）  关系的表示 （复习）  关系的运算 （复习）  0-1矩阵运算 （复习）  关系的性质

我粤 有序对(Ordered pair） ●(ab)是集合{a},{a,b}}的简写 ·次序的体现 ●(x,y)=(u,)ifx=w且=v 若{x},{x,y}={u},{w,},则{x}={u}或{x}={u,v以，因此x=u。 假设yy (1)若x=y,左边={x},而V≠X,.右边≠{x)}; (2)若xy,则必有{x,y}={u,v以，但y既非u,又非v,矛盾

有序对（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=AxB

笛卡尔乘积（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(AXA=? ●A=m,IB=n,AXB=?

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

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

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

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

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

最售 特殊的二元关系 ·集合A上的空关系☑：空关系即空集 。全域关系EA:EA={(x,y)|x,y∈A} ●恒等关系I4:I4={(x,x)|x∈A}

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

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

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