离散数学第二章.ppt

第二章关系
笛卡尔积
关系 关系的运算 复合关系的关系矩阵和关系图
关系的性质与闭包运算
等价关系
偏序关系
2018/6/13
1

定义:有n个具有给定次序的个体a1,a2,…,an组成的序列,称为有序n元组,记作(a1,a2,…,an)。
其中第i个元素ai称为该有序n元组的第i个坐标。
例{a,b,c,d}={b,a,d,c},但(a,b,c,d)(b,a,d,c)
{4,4,3,2}={4,3,2} ,但(4,4,3,2)(4,3,2)
当n=2时,有序二元组(a,b)又称为序偶。
2018/6/13
2
定义:设(a1,a2,…,an) 和(b1,b2,…,bn)是两个有序n元组,若a1= b1, a2=b2,…,an=bn,则称这两个有序n元组相等,并记作(a1,a2,…,an)=(b1,b2,…,bn)。
定义:设A1, A2,..., An为任意集合, 称集合{(a1,a2,…,an)|aiAi, i=1,2,...,n}为A1, A2,..., An的笛卡尔积,记为A1×A2×...×An。
2018/6/13
3
例:设A={0,1}, B={a,b,c}
A×B={(0,a), (0,b), (0,c), (1,a), (1,b), (1,c)}
B×A={(a,0), (a,1), (b,0), (b,1), (c,0), (c,1)}
注意:(1)一般情况下A×B≠B×A,
当A=或者B=时,A×B =,即×B = A×=。
笛卡尔积A×A,我们常记作A2。
例:A={0,1}
A×A={(0,0), (0,1), (1,0), (1,1)}
2018/6/13
4
(2) 笛卡尔积的基数
当A和B是有限集时,A×B必有限,而且
#(A×B)= #A×#B
当其中有一个无限集时,A×B必为无限集
2018/6/13
5
(3)笛卡尔积的性质
非交换: AB  BA
(除非 A=或 B=)
非结合: (AB)C  A(BC)
(除非 A=或 B=或 C=)
分配律: A(BC) = (AB)(AC)等
其他: AB= A=或B=等
2018/6/13
6
分配律
设A、B、C是任意的集合,则有
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
C
A(BC) = (AB)(AC)
2018/6/13
7
以第一个等式为例,给出其证明。
A×(BC)=( A×B)( A×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)
故A×(BC)(A×B)( A×C)
2018/6/13
8
又设(x,y)(A×B)( A×C)
即xA且y(BC)
即xA且(yB或yC)
于是xA且yB或者xA且yC
因此(x,y)  A×(BC)
故(A×B)( A×C)  A×(BC)
则(x,y)(A×B)或者(x,y) (A×C)
由上得证: A×(BC)=( A×B)( A×C)
2018/6/13
9
例: 设A,B,C,D是任意集合,
若A, 则 ABAC  BC.
证明: () 若 B=, 则 BC.
设 B, 由A, 设xA.
y, yB(x,y)AB
(x,y)AC
 xA且yC yC.
BC
2018/6/13
10