离散数学及应用 课件 4.1 集合的笛卡儿积和二元关系

DiscreteMathematics鄢小虎

离散数学项目化任务2在python中实现基于二元关系的智能家居系统。用于模拟基于事件和条件触发的智能家居系统。定义一些基本的设备类，并设置一个中央控制器来管理这些设备之间的交互。3第4章二元关系与函数4.1集合的笛卡儿积与二元关系4.2关系的运算4.3关系的性质4.4关系的闭包4.5等价关系和偏序关系4.6函数的定义和性质4.7函数的复合和反函数44.1集合的笛卡儿积和二元关系

有序对笛卡儿积及其性质二元关系的定义二元关系的表示5有序对定义

由两个客体x和y，按照一定的顺序组成的二元组称为有序对，记作<x,y>实例：点的直角坐标<3,

4>有序对性质有序性<x,y>

<y,x>例如：<3,

4>

<

4,3>

<x,y>与<u,v>相等的充分必要条件是

<x,y>=<u,v>

x=u

y=v例1<2,x+5>=<3y

4,y>，求x,y.解3y

4=2,x+5=y

y=2,x=3

课堂练习：第4.1（2）题6有序n元组定义一个有序n(n3)元组<x1,x2,…,xn>是一个有序对，其中第一个元素是一个有序n-1元组，即

<x1,x2,…,xn>=<<x1,x2,…,xn-1>,xn>

当n=1时,<x>形式上可以看成有序1元组.

当n=2时,有序对，例如：平面直角坐标<3,4>.

当n=3时,例如：空间直角坐标<3,4,1>.实例

n维向量是有序

n元组.笛卡儿积定义设A,B为集合，A与B的笛卡儿积记作A

B，即A

B={<x,y>|x

A

y

B}.8笛卡儿积例1A={1,2,3},B={a,b,c}

A

B={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>}

B

A={<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>,<a,3>,<b,3>,<c,3>}例2A={

},P(A)

A={

,{

}}

{

}={<

,

>,<{

},

>}课堂练习：A={

}，B={a,b}，求P(B)

A?提示：先写出来P(B)9Python编程验证集合运算的主要算律：结合律、交换律、分配律、同一律、零律、德摩根律集合元素的计数：文氏图法笛卡尔积：有序元组例1A={1,2,3},B={a,b,c}

A

B={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>}练习：

A={1,2},A

P(A)=？课前预习10课堂编程通过编程实现求给定集合A和B的笛卡儿乘积C的运算？提示：C=A

B={<x,y>|x

A

y

B

}

。输入集合为a,b，输出集合为c，即c=descartes(a,b)。(x,y)表示有序对。A={1,2,3},B={a,b,c}

A

B={<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>,<3,a>,<3,b>,<3,c>}注意：大括号表示集合(小括号不能)，小括号表示有序元组(如笛卡尔积)中括号表示列表11笛卡儿积的性质不适合交换律

A

B

B

A(A

B,A

,B

)不适合结合律

(A

B)

C

A

(B

C)(A

,B

)对于并或交运算满足分配律

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)12笛卡儿积的性质若A或B中有一个为空集，则A

B就是空集.

A

=

B=

注意：A{}不一样练习：A={0,1},B={}，求A

B?若|A|=m,|B|=n,

则|A

B|=？

13课堂练习通过Python编程证明：A

B

B

A(A

B)

C

A

(B

C)A

(B

C)=(A

B)

(A

C)A

(B

C)=(A

B)

(A

C)提示：并交用bing(),jiao()，笛卡尔积函数为:c=descartes(a,b)令A={1,2,3}，B={2,4,5}

，C={4,7,8}14性质的证明证明A

(B

C)=(A

B)

(A

C)证任取<x,y><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).15二元关系为什么要有二元关系？笛卡尔积穷举了所有的元素，但实际应用中，我们不需要知道所有的元素，只需要知道我们关心的元素，例如：选课过程中，我关心的是选离散数学的学生校运动会中，每个人关心的是自己选择的运动项目实例：同学关系、父子关系、师生关系。16二元关系的定义定义如果一个集合满足以下条件之一：（1）集合非空,且它的元素都是有序对（2）集合是空集则称该集合为一个二元关系,简称为关系，记作R.抢答：R={<1,2>,<a,b>},S={<1,2>,a,b},

二元关系？R是二元关系；由于a,b不是有序对，S不是二元关系17二元关系的定义如<x,y>∈R,可记作xRy；如果<x,y>

R,则记作xyR={<1,2>,<a,b>}根据上面的记法，可以写1R2,aRb,ac等.18从A到B的关系与A上的关系定义设A,B为集合,A×B的任何子集所定义的二元关系叫做从A到B的二元关系,当A=B时则叫做A上的二元关系.例

A={0,1},B={1,2,3}R1={<0,2>},R2=A×B,R3=

,R4={<0,1>}.那么，R1,R2,R3,R4是从A到B的二元关系,R3和R4同时也是A上的二元关系.注意：A到B的二元关系是笛卡尔积A

B的子集

是任何集合的二元关系

课堂提问：R5={<0,2>,<1,2>,<1,0>},R6={<1,2>,<1,1>,<1,3>}是否为从A到B二元关系？

19课堂练习A={1}，求A上的所有二元关系？A={0,1},B={2}，求A×B的所有二元关系？A={1,2},B={2,3}，求A×B的所有二元关系？提示：笛卡尔积的所有子集0元子集：1元子集：2元子集：。。。

20二元关系计数计数|A|=n,|A×A|=n2（笛卡尔积个数），

A×A的子集有个(推理见教材)所以，A上有个不同的二元关系.例如|A|=3,则A上有=512个不同的二元关系.|A|=n,|B|=m,|A×B|=mnA×B的子集有个所以，A上有个不同的二元关系.21A上重要关系的实例设A为任意集合，

是A上的关系，称为空关系EA,IA分别称为全域关系与恒等关系，定义如下：

EA={<x,y>|x∈A∧y∈A}=A×A

IA={<x,x>|x∈A}

例如,A={1,2},则

EA={<1,1>,<1,2>,<2,1>,<2,2>}

IA={<1,1>,<2,2>}

课堂练习：A={a,b,c},求EA和IA22A上重要关系的实例（续）小于等于关系LA,整除关系DA,包含关系R

定义：

LA={<x,y>|x,y∈A∧x≤y},A

R，R为实数集合

DB={<x,y>|x,y∈B∧x整除y},B

Z*,Z*为非0整数集

R

={<x,y>|x,y∈A∧x

y},A是集合族.类似的还可以定义大于等于关系,小于关系,大于关系,真包含关系等等.23实例例如A={1,2,3},B={a,b},C={

,{a},{b},{a,b}}则

LA={<1,1>,<1,2>,<1,3>,<2,2>,<2,3>,<3,3>}

DA={<1,1>,<1,2>,<1,3>,<2,2>,<3,3>}

则C上的包含关系是R

={<

,

>,<

,{a}>,<

,{b}>,<

,{a,b}>,<{a},{a}>,<{a},{a,b}>,<{b},{b}>,<{b},{a,b}>,<{a,b},{a,b}>}

课堂练习：A={1,2,3},求A上的大于关系?

A={

,{1},{1,2}},求A上的包含关系?

设A={1,2,4,7,8}，B={2,3,5,7}，定义由A到B的关系R={(a,b)|(a+b)/5是整数}，求关系R。

课程回顾二元关系的定义：笛卡尔积的子集**能够计算所有二元关系，即所有笛卡尔积的子集**步骤：0-n元子集罗列，共有2n个重要的二元关系：小于等于关系,整除关系,包含关系课堂练习：A={1,2,3,4},求A上的小于等于关系?B={{1},{1,2},{1,2,3}},求A上的包含关系

?

25课堂练习输入集合A，编程自动输出小于等于关系LA，整除关系DA，包含关系R

对应的集合.

提示：LA={<x,y>|x,y∈A∧x≤y},

DA={<x,y>|x,y