离散数学二元关系.ppt

文档介绍：该【离散数学二元关系 】是由【duzw466】上传分享，文档一共【141】页，该文档可以免费在线阅读，需要了解更多关于【离散数学二元关系 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。2025/5/5
1
第四章 二元关系
单击此处添加正文，文字是您思想的提炼，为了演示发布的良好效果，请言简意赅地阐述您的观点。
主要内容：
关系的概念及表示方法
关系的性质
关系的运算:
－关系的复合，求逆关系，关系的闭包。
三种关系:
－等价关系，相容关系， 次序关系。
2
4-1 序偶与集合的笛卡尔积
序偶与有序n元组
定义:由两个对象x、y组成的序列称为有序二元组，也称之为序偶，记作<x,y>；称x、y分别为序偶<x,y>的第一，第二元素。
注意，序偶<x,y>与集合{x,y}不同：
序偶<x,y>：元素x和y有次序；
集合{x,y}：元素x和y的次序无关紧要。
2025/5/5
3
定义：设<x,y>，<u,v>是两个序偶，
如果x=u和y=v则称<x,y>和<u,v>相等，
记作<x,y>=<u,v>。
.定义：有序3元组是一个序偶,其第一个元素也是个序偶。
有序3元组<< a,b>, c>可以简记成<a,b,c>， 但<a,<b,c>>不是有序3元组。
2025/5/5
4
定义：有序n元组是一个序偶,其第一个元素本身是个有序n-1元组,
记作<<x1 , x2 , , xn-1>, xn>。且可以简记成<x1 , x2 , , xn-1, xn>。
定义<x1, x2 ,…, xn>=<y1 , y2 ,…, yn>
( x1= y1) ( x2= y2) ( xn= yn)
2025/5/5
5
豹
猫
虎
象
狮
狗
鼠
虎
象
狮
豹
狼
鼠
猫
狗
狼
设：A={红,蓝}
B={象,狮,虎,豹,狼,狗,猫,鼠}
每个棋子可以看成一个序偶，斗兽棋可记成集合AB ：
{<红,象>,<红,狮>,<红,虎>,<红,豹>,<红,狼>,<红,狗>,
<红,猫>,<红,鼠>,<蓝,象>,<蓝,狮>,<蓝,虎>,<蓝,豹>,
<蓝,狼>,<蓝,狗>, <蓝,猫>,<蓝,鼠> }
2025/5/5
例如“斗兽棋”的16颗棋子，
6
定义:设A、B是集合，由A的元素为第一元素，B的元素为第二元素组成序偶的集合，称为A和B的笛卡尔积，记作A×B，即
AB={<x,y>|xA∧yB}
例1 设A={0,1}，B={a,b}，求AB ， BA， AA 。
解： AB={<0,a>,<0,b>,<1,a>,<1,b>}
BA={<a,0 >,<b,0>,<a,1>,<b,1>}
AA={<0,0>,<0,1>,<1,0>,<1,1>}
可见 A×B≠B×A
所以，集合的笛卡尔积运算不满足交换律。
2025/5/5
7
另外
#2022
2025/5/5
8
对∪和∩满足分配律。
设A,B,C是任意集合，则
A(B∪C)= (AB)∪(AC)；
A(B∩C)= (AB)∩(AC)；
(A∪B)C= (AC)∪(BC)；
(A∩B)C= (AC)∩(BC)；
证明⑴ ：任取<x,y>A(B∪C)
xA yB∪C xA(yB∨yC)
( xA yB)∨(xAyC)
<x,y>AB∨<x,y>AC
<x,y>(AB)∪(AC)
所以⑴式成立。（其余可以类似证明）
2025/5/5
9
若C, 则 AB(ACBC) (CACB)
证明：充分性： 设AB，求证 ACBC
任取<x,y>AC
xAyC xByC (因AB)
<x,y>BC 所以, ACBC。
必要性：若C, 由ACBC 求证 AB
取C中元素y, 任取 xA
xAyC <x,y>AC
<x,y>BC (由ACBC )
xByC xB 所以, AB。
所以 AB(ACBC)
类似可以证明 AB (CACB)。
2025/5/5
10
2025/5/5
5) 设A、B、C、D为非空集合，则
ABCDAC∧BD
证明：首先,由ABCD 证明AC∧BD
任取xA，任取yB，所以
xAyB<x,y>A×B
<x,y>C×D (由ABCD )
xCyD 所以, AC∧BD。
其次, 由AC，BD 证明ABCD
任取<x,y>A×B
 xAyB
 xCyD (由AC，BD)
<x,y>C×D 所以, ABCD
证毕。