文档介绍：回顾上节课基本知识点:
1、集合代数中的基本概念
2、集合的运算
3、集合代数中的基本恒等式
离散数学第14讲
1
离散数学第14讲
本讲基本知识点:
1、有序对与笛卡儿乘积的概念
2、笛卡尔积的性质
3、二元关系的定义
4、二元关系的三种表示方法
2
有序对与笛卡儿乘积
由两个元素x,y(允许x=y)按一定顺序排列成的二元组叫做一个有序对或序偶,记作<x,y>,其中x是它的第一元素,y是它的第二元素。
有序对<x,y>具有以下性质:
当x≠y时, <x,y> ≠<y,x>
(2) <x,y>=<w,v> x=w ∧ y=v
3
例:已知<x+3,y-2>=<y+7,3y-x>,求x和y。
解:由有序对相等的充要条件得
x+3=y+7
y-2=3y-x
解得x=6,y=2
4
设A,B为集合,用A中元素为第一元素,B中元素为第二元素构成有序对。所有这样的有序对组成的集合叫做A和B的笛卡儿积,记作A×B。
笛卡儿积的符号化表示为:
A × B={<x,y>|x ∈ A ∧ y∈ B}
5
例如:若A={1,2}, B={a,b,c},则
A×B={<1,a>, <1,b>, <1,c>, <2,a>, <2,b>, <2,c>}
B×A={<a,1>, <a,2>, <b,1>, <b,2>, <c,1>, <c,3>}
练1:设A={1,2},求A ×P(A).
练2:设A={φ}, 求A × P(A).
易知:若|A|=m,(即集合A的元素的个数),|B|=n,则
| A×B|= |B×A|=mn
6
笛卡儿积的性质:
1、对任意集合A,根据定义有
A × φ= φ× A= φ
2、一般来说,笛卡儿积不满足交换律,即
A×B≠B×A(当A ≠φ∧ B ≠φ∧ A ≠ B时)
3、笛卡儿积不满足结合律,即
(A×B) ×C≠A×(B ×C)(当A≠φ∧B≠φ∧C≠φ时)
7
4、笛卡儿积运算对并和交运算满足分配律,即
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)
8
第七章二元关系
证明: (B∩C) × A = (B×A) ∩(C ×A)
对于<x,y>
<x,y> ∈(B∩C) × A
x∈(B ∩C) ∧y ∈ A
x∈B ∧x ∈ C ∧ y ∈ A
x∈B ∧x ∈C ∧ y ∈ A ∧ y ∈ A
(x∈B ∧y ∈A) ∧(x ∈ C ∧ y ∈ A)
<x,y>∈ B × A ∧<x,y>∈ C × A
<x,y>∈(B×A) ∩(C ×A)
∴(B∩C) × A = (B×A) ∩(C ×A)
9
5、A C ∧ B D => A×B C ×D
证明:对于<x,y>
<x,y> ∈ A×B
x∈A ∧y ∈ B
=> x∈C ∧y ∈ D (∵ A C ∧ B D )
<x,y> ∈ C×D
∴ A×B C ×D
注意:此性质的逆命题,只有当A=B= φ或A≠φ且B≠φ时才成立,其它情况不成立。详见课本P111.
10