北大离散数学05.ppt

《北大离散数学05.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第5讲二元关系的基本概念北京大学内容提要1.有序对与卡氏积2.二元关系3.二元关系的基本运算2021/7/281《集合论与图论》第5讲有序对与卡氏积有序对(有序二元组)有序三元组,有序n元组卡氏积卡氏积性质2021/7/282《集合论与图论》第5讲有序对(orderedpair)有序对:={{a},{a,b}}其中,a是第一元素,b是第二元素.也记作(a,b)定理1:=a=cb=d推论:ab2021/7/283《集合论与图论》第5讲有序对(引理1)引理1:{x,a}={x,b}a=b证明:()显然.()

2、分两种情况.(1)x=a.{x,a}={x,b}{a,a}={a,b}{a}={a,b}a=b.(2)xa.a{x,a}={x,b}a=b.#2021/7/284《集合论与图论》第5讲有序对(引理2)引理2:若A=B,则(1)∪A=∪B(2)∩A=∩B证明:(1)x,x∪Az(zAxz)z(zBxz)x∪B.(2)x,x∩Az(zAxz)z(zBxz)x∩B.#2021/7/285《集合论与图论》第5讲有序对(定理1)定理1:=a=cb=d证明:()显然.()由引理2,=

3、{{a},{a,b}}={{c},{c,d}}∪{{a},{a,b}}=∪{{c},{c,d}}{a,b}={c,d}.又{{a},{a,b}}={{c},{c,d}}∩{{a},{a,b}}=∩{{c},{c,d}}{a}={c}a=c.再由引理1,得b=d.#2021/7/286《集合论与图论》第5讲有序对(推论)推论:ab证明:(反证)=a=b,与ab矛盾.#2021/7/287《集合论与图论》第5讲有序三元组(orderedtriple)有序三元组:=<,c>有序n(2)元组

4、:=<,an>定理2:=ai=bi,i=1,2,…,n.#2021/7/288《集合论与图论》第5讲卡氏积(Cartesianproduct)卡氏积:AB={

5、xAyB}.例:A={,a},B={1,2,3}.AB={<,1>,<,2>,<,3>,,,}.BA={<1,>,<1,a>,<2,>,<2,a>,<3,>,<3,a>}.AA={<,>,<,a>,,}.BB={<1,1>,<1

6、,2>,<1,3>,<2,1>,<2,2>,<2,3>,<3,1>,<3,2>,<3,3>}.#2021/7/289《集合论与图论》第5讲卡氏积的性质非交换:ABBA(除非A=BA=B=)非结合:(AB)CA(BC)(除非A=B=C=)分配律:A(BC)=(AB)(AC)等其他:AB=A=B=等2021/7/2810《集合论与图论》第5讲卡氏积非交换性非交换:ABBA(除非A=BA=B=)反例:A={1},B={2}.AB={<1,2>},BA={<2,1>}.2021/7/2811《集合论与图论》第5讲卡

7、氏积非结合性非结合:(AB)CA(BC)(除非A=B=C=)反例:A=B=C={1}.(AB)C={<<1,1>,1>},A(BC)={<1,<1,1>>}.2021/7/2812《集合论与图论》第5讲卡氏积分配律1.A(BC)=(AB)(AC)2.A(BC)=(AB)(AC)3.(BC)A=(BA)(CA)4.(BC)A=(BA)(CA)2021/7/2813《集合论与图论》第5讲卡氏积分配律(证明1)A(BC)=(AB)(AC).证明:,A(BC)xAy(BC)

8、xA(yByC)(xAyB)(xAyC)(AB)(AC)(AB)(AC)A(BC)=(AB)(AC).#2021/7/2814《集合论与图论》第5讲例题1例题1:设A,B,C,D是任意集合,(1)AB=A=B=(2)若A,则ABACBC.(3)ACBDABCD,并且当(A=B=)(AB)时,ABCDACBD.2021/7/