笛卡爾積和二元關(guān)系課件(離散數(shù)學(xué))

第七章二元關(guān)系2/1/202317.1～7.2笛卡兒積和二元關(guān)系

有序?qū)Φ芽▋悍e及其性質(zhì)二元關(guān)系的定義二元關(guān)系的表示22/1/2023

引例中涉及的概念有序?qū)﹃P(guān)系集合A上的關(guān)系集合A到B的關(guān)系32/1/2023一、有序?qū)?/p>

定義：由兩個客體x和y，按照一定的順序組成的二元組稱為有序?qū)?，記?lt;x,y>一般情況下<x,y><y,x><x,y>與<u,v>相等的充要條件是：

<x,y>=<u,v>x=uy=v有序性42/1/2023二、笛卡兒積

定義：設(shè)A和B是兩個集合，A到B的笛卡爾乘積用A×B表示，它是所有形如<a,b>的有序?qū)ψ鳛樵氐募?，其中。AB={<x,y>|xAyB}B到A的笛卡爾乘積B×ABA={<x,y>|xByA}52/1/2023二、笛卡兒積

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

BA={<a,1>,<b,1>,<c,1>,<a,2>,<b,2>,<c,2>,<a,3>,<b,3>,<c,3>}ABBA62/1/2023二、笛卡兒積例2：已知A={,{}},則A

P(A)。P(A)={,{},{{}},{,{}}}A

P(A)={<,>,<,{}>,<,{{}}>,<,{,{}}>,<{},>,<{},{}>,<{},{{}}>,<{},{,{}}>}72/1/2023二、笛卡兒積

特別的，當(dāng)A=B時，A×A稱為集合A上的笛卡爾乘積，也可簡寫作A2。當(dāng)|A|=m,|B|=n時,|A×B|=m×n|A×A|=n282/1/2023二、笛卡兒積

例3：設(shè)A={a,b},B={0,1},C={}。試求出A×A,A×B,B×A,(A×B)×C,A×(B×C)A×A={<a,a>,<a,b>,<b,b>,<b,a>}A×B={<a,0>,<a,1>,<b,0>,<b,1>}B×C={<0,>,<1,>}(A×B)×C={<<a,0>,>,<<a,1>,>,<<b,0>,>,<<b,1>,>}A×(B×C)={<a,<0,>>,<a,<1,>>,<b,<0,>>,<b,<1,>>}92/1/2023二、笛卡兒積

笛卡兒積的性質(zhì)：A=B=當(dāng)AB,A,B時，ABBA

當(dāng)A,B時，(AB)CA(BC)

102/1/2023二、笛卡兒積對于并或交運(yùn)算滿足分配律

A(BC)=(AB)(AC) (BC)A=(BA)(CA) A(BC)=(AB)(AC) (BC)A=(BA)(CA)

思考:A

(B

C)=(AB)(AC)成立嗎?

P(A)P(A)=P(A

A)成立嗎?112/1/2023二、笛卡兒積例4：(1)證明A=BC=DAC=BD

(2)AC=BD是否能推出A=BC=D?為什么？解：

(1)任取<x,y><x,y>AC

xAyC

xByD

<x,y>BD

(2)不一定。反例如下：

A={1}，B={2},C=D=,則AC=BD但是AB.122/1/2023二、笛卡兒積證：對于任意的x，例5：設(shè)A、B為任意集合，證明：若

AA=BB,則A=B。132/1/2023三、二元關(guān)系

定義：A和B是兩個集合,R是笛卡爾乘積A×B的子集，則稱R為A到B的一個二元關(guān)系。e.g.A={a1,a2,a3,a4,a5},B={b1,b2,b3}，<a1,b1>可以寫作a1Rb1,稱a1,b1以R相關(guān)。R={<a1,b1>,<a2,b1>,<a4,b3>}是A到B的一個二元關(guān)系。142/1/2023三、二元關(guān)系

例6：列出從集合A={1,2}到B={1}的所有的二元關(guān)系.解：A×B的所有子集都是A到B的二元關(guān)系。R1=

,R2={<1,1>},R3={<2,1>},R4={<1,1>,<2,1>}二元關(guān)系是一個集合，其元素是有序?qū)Α?52/1/2023三、二元關(guān)系

定義：A是集合，R是笛卡爾乘積A×A的子集，則稱R為A上的二元關(guān)系。當(dāng)|A|=n時,A上有多少個不同的二元關(guān)系？|A×A|=n2A×A的子集有個所以，A上有個不同的二元關(guān)系162/1/2023三、二元關(guān)系

定義：如果一個集合滿足以下條件之一：（1）集合非空,且它的元素都是有序?qū)Γ?）集合是空集

則稱該集合為一個二元關(guān)系,簡稱為關(guān)系，記作R。如果<x,y>∈R,記作xRy；如果<x,y>R,則記作xRy。172/1/2023三、二元關(guān)系引例：A={a,b},B={4,5,8}R1={<a,a>,<a,b>,<b,a>,<b,b>}R2={<a,a>,<b,b>}R3={<4,4>,<4,5>,<4,8>,<5,5>,<5,8>}R4={<4,4>,<4,8>,<5,5>,<8,8>}=A×A恒等關(guān)系小于等于關(guān)系整除關(guān)系182/1/2023三、二元關(guān)系

設(shè)A為任意集合，稱為A上的空關(guān)系；EA={<x,y>|x∈A∧y∈A}=A×A稱為A上的全域關(guān)系；IA={<x,x>|x∈A}稱作A上的恒等關(guān)系。192/1/2023三、二元關(guān)系LA={<x,y>|x,y∈A∧x≤y}稱作A上的小于等于關(guān)系，其中AR，R為實(shí)數(shù)集合；DA={<x,y>|x,y∈A∧x整除y},稱作A上的整除關(guān)系A(chǔ)Z*,Z*為非0整數(shù)集；R={<x,y>|x,y∈A∧xy}稱作A上的包含關(guān)系，A是集合族。202/1/2023例7:A={,{1},{2},{1,2}},求A上的包含關(guān)系。

三、二元關(guān)系R={<,>,<,{1}>,<,{2}>,<,{1,2}>,<{1},{1}>,<{1},{1,2}>,<{2},{2}>,<{2},{1,2}>,<{1,2},{1,2}>}

212/1/2023四、關(guān)系的表示

常見的關(guān)系的表示方式有三種：集合表示法；矩陣表示法；關(guān)系圖表示法。222/1/2023四、關(guān)系的表示e.g.A={a1,a2,a3}B={b1,b2,b3,b4}R={<a1,b1>,<a2,b3>,<a2,b4>,<a3,b1>,<a3,b4>}關(guān)系R的關(guān)系矩陣如下：b1b2b3b4a1a2a3232/1/2023四、關(guān)系的表示

關(guān)系矩陣：若A={x1,x2,…,xm}，B={y1,y2,…,yn}，R是從A到B的關(guān)系，R的關(guān)系矩陣MR=[rij]mn,其中rij

=1<xi,yj>R.242/1/2023四、關(guān)系的表示

例8：A={1,2,3,4,6}，R是A上的整除關(guān)系，求R的矩陣表示。1234612346252/1/2023四、關(guān)系的表示例9：A={0,1,2,3}R={<0,0>,<0,3>,<2,0>,<2,1>,<2,3>,<3,2>}

給出R的關(guān)系矩陣和關(guān)系圖。262/1/2023