《CH4二元關(guān)系和函數(shù)1二元關(guān)系的基本概念.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《CH4二元關(guān)系和函數(shù)1二元關(guān)系的基本概念.ppt（36頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、離散數(shù)學(xué)CH4二元關(guān)系和函數(shù) 回 顧 用推理規(guī)則證明： |= A CAFEFDEBDCBA ,)(,)()(,)()( 證明：設(shè)論域D=a , b , c，求證： )()()()( xBxAxxxBxxA )()( )()()()()()( )()()()()()( )()()()()()( )()()()()()( )()()()()()()()( xBxAx cBcAbBbAaBaA cBcAbBcAaBcA cBbAbBbAaBbA cBaAbBaAaBaA cBbBaBcAbAaAxxBxxA 第 4章 二 元 關(guān) 系 和 函 數(shù)本章學(xué)習(xí)1.集合的笛卡爾積2.關(guān)系及其表示3.關(guān)系的運(yùn)算
2、4.關(guān)系的性質(zhì)5.關(guān)系的閉包6.等價(jià)關(guān)系和偏序關(guān)系7.函數(shù)的定義和性質(zhì)8.函數(shù)的復(fù)合和反函數(shù) 今 日 內(nèi) 容集合的笛卡爾積關(guān)系及其表示關(guān)系的運(yùn)算 笛 卡 爾 乘 積定義：由兩個(gè)元素x和y（允許x=y）按一定的順序排列成的二元組叫做一個(gè)有序?qū)Γㄒ卜Q序偶），記做，其中x是它的第一元素，y是它的第二元素。平面直角坐標(biāo)系中點(diǎn)的坐標(biāo)就是序偶。 例如，,.都代表坐標(biāo)系中不同的點(diǎn)。 序偶的特點(diǎn)（與集合的不同之處）當(dāng)x y時(shí)， 兩個(gè)有序?qū)ο嗟?，?的充要條件是x=u,且y=v 定義（有序n元組）:一個(gè)有序n元組（n3）是一個(gè)有序?qū)?，記? 其中第一個(gè)元組是一個(gè)有序n-1元組， 即 =,xn,例如，空間直角坐標(biāo)
3、系中點(diǎn)的坐標(biāo) 1,-1,3,2,4,0等都是有序3元組。 N維空間中點(diǎn)的坐標(biāo)或n維向量都是有序n元組 定義（笛卡兒積）: 設(shè)A，B為集合，用A中元素作為第一元素，B中元素作為第二元素，構(gòu)成序偶。所有這樣的序偶組成的集合叫做A和B的笛卡兒積，記作AB。符號(hào)化表示為 AB=|x Ay B 例:若A=a,b,B=0,1,2,則 AB=, , BA=, , , , , 笛卡兒積中元素的個(gè)數(shù)如果A中有m個(gè)元素,B中有n個(gè)元素, 則AB和BA中都有mn個(gè)元素 笛卡兒積運(yùn)算的性質(zhì)若A,B中有一個(gè)空集,則它們的笛卡兒積是空集.即 B=A = 笛卡兒積運(yùn)算不適合交換律: 當(dāng)A B且A,B都不是空集時(shí),有AB B
4、A笛卡兒積運(yùn)算不適合結(jié)合律: 當(dāng)A,B,C都不是空集時(shí),有(AB)C A(BC) 設(shè)x A,y B,z C,那么,z (AB) C, x, A(BC)。 一般情況下, ,z x, 所以, (AB)C A(BC) 笛卡兒積運(yùn)算對(duì)或運(yùn)算滿足分配律，即 A (B C) = (A B) (A C) (B C) A = (B A) (C A) A (B C) = (A C) (A C) (B C) A = (B A) (C A)證明A (B C) = (A B) (A C) 對(duì)于任何的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
5、)x, y A B x, y A C x, y (A B) (A C) 所以 A (B C) = (A B) (A C) 例 :設(shè) A=1， 2， 求 P（ A） A 解 : P（ A） A = ， 1， 2， 1,2, 1， 2 = ,1, , , ， ， 2， 2 ， 1， 2， 1 ,1， 2， 2 定義 (n階笛卡兒積) 設(shè)A1, A2, An是n個(gè)集合(n 2)。 它們的n階笛卡兒積 A1 A2 An=x1,x2,xn|x1 A1 x2 A2 xn An 當(dāng)A1 = A2 = An = A時(shí)，可將它們的n階笛卡兒積 簡(jiǎn)記為An 例如，A=a，b，則 A3=a，a，a，a，a，b，a，
6、b，a， a，b，b，b，a，a，b，a，b， b，b，a，b，b，b 關(guān) 系 及 其 表 示 l什 么 是 關(guān) 系l關(guān) 系 的 表 示 l所 謂 二 元 關(guān) 系 就 是 在 集 合 中 兩 個(gè) 元 素 之 間 的某 種 相 關(guān) 性l例 如 ： 甲 、 乙 、 丙 三 人 進(jìn) 行 乒 乓 球 比 賽 ， 如果 任 何 兩 人 之 間 都 要 賽 一 場(chǎng) ， 那 么 共 要 賽 三 場(chǎng) 。假 設(shè) 三 場(chǎng) 比 賽 的 結(jié) 果 是 乙 勝 甲 ， 甲 勝 丙 ， 乙 勝丙 ， 這 個(gè) 結(jié) 果 可 以 記 作 乙 ， 甲 ， 甲 ， 丙 ， 乙 ， 丙 其 中 x， y 表 示 x勝 y。它 表 示
7、了 集 合 甲 、 乙 、 丙 中 元 素 之 間 的 一 種勝 負(fù) 關(guān) 系 1、 什 么 是 關(guān) 系 l再例如，有甲，乙，丙三個(gè)人和四項(xiàng)工作a，b，c，d。 已知甲可以從事工作a和b，乙可以從事工作c，丙可以從事工作a和d。 那么人和工作之間的對(duì)應(yīng)關(guān)系可以記作 R=, 這是人的集合甲，乙，丙到工作的集合a，b，c，d之間的關(guān)系。 l除了二元關(guān)系以外還有多元關(guān)系 本書只討論二元關(guān)系。以后凡是出現(xiàn)關(guān)系的地方均指二元關(guān)系 下面給出二元關(guān)系的一般定義l定義（二元關(guān)系）如果一個(gè)集合為空集或它的元素都是有序?qū)?，則稱這個(gè)集合是一個(gè)二元關(guān)系，一般記作R。 對(duì)于二元關(guān)系R，如果x，y R，則記作xRy。l設(shè)A
8、，B為集合，A B的任何子集所定義的二元關(guān)系稱作從A到B的二元關(guān)系，特別當(dāng)A=B時(shí)，則叫做A上的二元關(guān)系。 例 ： 集 合 A 0,1， B 2,3A B ， ， ， A A的 子 集 ： R3=， R 4=， ， 都 是 A上 的 二 元 關(guān) 系A(chǔ) A ， ， ， A B的 子 集 ： R1= ， R2=， ， 都 是 A到 B上 的 二 元 關(guān) 系 l|A|=n， A A的子集有2n2個(gè)，每個(gè)子集代表一個(gè)A上的關(guān)系， 所以A上有2n2個(gè)不同的二元關(guān)系。lA上的3種特殊的關(guān)系空關(guān)系： 空集全域關(guān)系:EA= A A恒等關(guān)系:IA=x，x| x A 例 ： 集 合 A 0,1為 A上 的 空 關(guān)
9、 系EA ， ， ， 為 A上 的 全 域 關(guān) 系IA ， 為 A上 的 恒 等 關(guān) 系A(chǔ) A ， ， ， 其它一些常見關(guān)系:l設(shè)A為實(shí)數(shù)集R的某個(gè)子集，則A上小于等于關(guān)系定義為: LA=x，y| x，y A x y例如： A=-1 ，3， 4，則 A上小于等于關(guān)系 LA= -1，-1,-1，3,-1，4, 3，3,3，4，4，4 l設(shè)B為實(shí)數(shù)集Z+的某個(gè)子集，則B上整除關(guān)系定義為: DB=x，y| x，y B x|y例：B=1，2，3，6，則B上整除關(guān)系DB=1,1,1,2,1,3,1,6, 2,2,2,6, 3,3,3,6, 6,6 集合A的冪集P(A)上的包含關(guān)系： R=x，y| x，y
10、 P(A) x y 例:設(shè)A=a，b，則有: P(A)=, a，b，A R=, , , 2、關(guān)系的表示方法集合表示法關(guān)系矩陣法（A是有窮集時(shí)） 設(shè)A=x1，x2，xn， B=y1，y2，ym， R是A到B的關(guān)系，則R的關(guān)系矩陣是MR=（rij)n*m, 其 中 r ij= 1 若 R rij= 0 若 R （ i=1,n;j=1m）11 12 121 22 21 2 mmn n nmr r rr r rr r r MR= 例:A=1,2,3,4,B=a,b,c，A到B的關(guān)系R=, R的關(guān)系矩陣: 11 111 例:A=1,2,3,4,B=a,b,c，A到B的關(guān)系R=, R的關(guān)系矩陣: 例:A=
11、1,2,3,4,A上的關(guān)系R=, R的關(guān)系矩陣: 關(guān)系圖法（A是有窮集時(shí)） 集合A=x1，x2，xn， B=y1，y2，ym， R是A到B上的關(guān)系。 首先在平面上畫上n個(gè)結(jié)點(diǎn)分別代表x1，xn， 再畫上m個(gè)結(jié)點(diǎn)分別代表y1，y2，ym。 如果 R ，則在xi到y(tǒng)j之間畫上一 條從xi指向 yj的帶箭頭的直線 。 這樣得到的圖就是R的關(guān)系圖。 例:A=1,2,3,4,B=a,b,c，A到B的關(guān)系R=, R的關(guān)系圖: A上關(guān)系R的關(guān)系圖： 集合A=x1，x2，xn，R是A上的關(guān)系 首先在平面上畫上n個(gè)結(jié)點(diǎn)分別代表x1，xn， 如果 R ，則在xi到xj之間畫上一 條從xi指向 yj的有向邊 。 這樣得到的圖就是R的關(guān)系圖。 例如：設(shè) A=1，2，3，4, A 上的關(guān)系 R=1,1,1,2,2,3,2,4, 4,2 R的關(guān)系圖: 課 堂 練 習(xí) ：集合A=1，2，3寫出A上的恒等關(guān)系，全域關(guān)系，小于等于關(guān)系，整除關(guān)系，并畫出關(guān)系圖 Q & A 36
CH4二元關(guān)系和函數(shù)1二元關(guān)系的基本概念.ppt
