CH4二元關(guān)系和函數(shù)1二元關(guān)系的基本概念.ppt

離散數(shù)學(xué) CH4二元關(guān)系和函數(shù),回顧,用推理規(guī)則證明： |= A,證明： 設(shè)論域D=a , b , c，求證：,第4章二元關(guān)系和函數(shù),本章學(xué)習(xí) 1.集合的笛卡爾積 2.關(guān)系及其表示 3.關(guān)系的運(yùn)算 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(chēng)序偶），記做，其中x是它的第一元素，y是它的第二元素。 平面直角坐標(biāo)系中點(diǎn)的坐標(biāo)就是序偶。 例如，,.都代表坐標(biāo)系中不同的點(diǎn)。,序偶的特點(diǎn)（與集合的不同之處） 當(dāng)xy時(shí)， 兩個(gè)有序?qū)ο嗟龋?的充要條件是x=u,且y=v,定義（有序n元組）:一個(gè)有序n元組（n3）是一個(gè)有序?qū)?，記? 其中第一個(gè)元組是一個(gè)有序n-1元組， 即 =,xn, 例如，空間直角坐標(biāo)系中點(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=|xAyB 例:若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)AB且A,B都不是空集時(shí),有ABBA 笛卡兒積運(yùn)算不適合結(jié)合律: 當(dāng)A,B,C都不是空集時(shí),有(AB)CA(BC) 設(shè)xA,yB,zC,那么,z(AB) C, A(BC)。 一般情況下, ,z 所以, (AB)CA(BC),笛卡兒積運(yùn)算對(duì)或運(yùn)算滿足分配律，即 A (BC) = (A B) (A C) (BC) A = (B A) (C A) A (BC) = (A C) (A C) (BC) A = (B A) (C A) 證明A (BC) = (A B) (A C) 對(duì)于任何的x,y ， x, y A (B C) x A yBC x A (y B y C) (x A y B) (x A yC) x, y A B x, y A C x, y (A B) (A C) 所以 A (BC) = (A B) (AC),例:設(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è)集合(n2)。 它們的n階笛卡兒積 A1 A2 An =x1,x2,xn|x1A1x2A2xnAn 當(dāng)A1 = A2 = An = A時(shí)，可將它們的n階笛卡兒積 簡(jiǎn)記為An 例如，A=a，b，則 A3=a，a，a，a，a，b，a，b，a， a，b，b，b，a，a，b，a，b， b，b，a，b，b，b,關(guān)系及其表示,什么是關(guān)系 關(guān)系的表示,所謂二元關(guān)系就是在集合中兩個(gè)元素之間的某種相關(guān)性 例如：甲、乙、丙三人進(jìn)行乒乓球比賽，如果任何兩人之間都要賽一場(chǎng)，那么共要賽三場(chǎng)。假設(shè)三場(chǎng)比賽的結(jié)果是乙勝甲，甲勝丙，乙勝丙，這個(gè)結(jié)果可以記作 乙，甲，甲，丙，乙，丙 其中x，y表示x勝y。 它表示了集合甲、乙、丙中元素之間的一種勝負(fù)關(guān)系,1、什么是關(guān)系,再例如，有甲，乙，丙三個(gè)人和四項(xiàng)工作a，b，c，d。 已知甲可以從事工作a和b，乙可以從事工作c，丙可以從事工作a和d。 那么人和工作之間的對(duì)應(yīng)關(guān)系可以記作 R=, 這是人的集合甲，乙，丙到工作的集合a，b，c，d之間的關(guān)系。,除了二元關(guān)系以外還有多元關(guān)系 本書(shū)只討論二元關(guān)系。以后凡是出現(xiàn)關(guān)系的地方均指二元關(guān)系 下面給出二元關(guān)系的一般定義 定義（二元關(guān)系）如果一個(gè)集合為空集或它的元素都是有序?qū)?，則稱(chēng)這個(gè)集合是一個(gè)二元關(guān)系，一般記作R。 對(duì)于二元關(guān)系R，如果x，y R，則記作xRy。 設(shè)A，B為集合，AB的任何子集所定義的二元關(guān)系稱(chēng)作從A到B的二元關(guān)系，特別當(dāng)A=B時(shí)，則叫做A上的二元關(guān)系。,例：集合A0,1，B2,3,AB， ， ， ,AA的子集： R3=， R4=， ， 都是A上的二元關(guān)系,AA， ， ， ,AB的子集：R1= ， R2=， ， 都是A到B上的二元關(guān)系,|A|=n， AA的子集有2n2個(gè)，每個(gè)子集代表一個(gè)A上的關(guān)系， 所以A上有2n2個(gè)不同的二元關(guān)系。 A上的3種特殊的關(guān)系 空關(guān)系： 空集 全域關(guān)系:EA= AA 恒等關(guān)系:IA=x，x| x A,例：集合A0,1,為A上的空關(guān)系 EA ， ， ， 為A上的全域關(guān)系 IA ， 為A上的恒等關(guān)系,AA， ， ， ,其它一些常見(jiàn)關(guān)系: 設(shè)A為實(shí)數(shù)集R的某個(gè)子集，則A上小于等于關(guān)系定義為: LA=x，y| x，y Axy 例如： A=-1 ，3， 4，則 A上小于等于關(guān)系 LA= -1，-1,-1，3,-1，4, 3，3,3，4，4，4,設(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 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,其中 rij= 1 若 R rij= 0 若 R （i=1,n;j=1m）,MR=,例:A=1,2,3,4,B=a,b,c，A到B的關(guān)系R=, R的關(guān)系矩陣:,1,1,1,1,1,例:A=1,2,3,4,B=a,b,c，A到B的關(guān)系R=, R的關(guān)系矩陣:,例:A=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)系。 首先在平面上畫(huà)上n個(gè)結(jié)點(diǎn)分別代表x1，xn， 再畫(huà)上m個(gè)結(jié)點(diǎn)分別代表y1，y2，ym。 如果 R ，則在xi到y(tǒng)j之間畫(huà)上一 條從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)系 首先在平面上畫(huà)上n個(gè)結(jié)點(diǎn)分別代表x1，xn， 如果 R ，則在xi到xj之間