離散數(shù)學(xué) 3-4 序偶與笛卡爾積3-5 關(guān)系及其表示

1、Discrete Mathematics山東科技大學(xué)山東科技大學(xué)信息科學(xué)與工程學(xué)院信息科學(xué)與工程學(xué)院上次課內(nèi)容回顧上次課內(nèi)容回顧集合的概念集合的表示集合的關(guān)系特殊的集合：空集、全集、冪集集合的運算：集合的運算：3-4 3-4 序偶與笛卡爾積序偶與笛卡爾積 1、序偶、序偶(有序有序2元組元組)：兩個具有固定次序的客體組成一個序偶(有序2元組)，記作，其中x是它的第一元素，y是它的第二元素。一、有序一、有序n元組元組例：平面直角坐標(biāo)系中的一個點的坐標(biāo)就構(gòu)成為一個有序序偶，我們可用表示。注：序偶是講究次序的。例和表示平面上兩個不同的點，這與集合不同，1，3和3，1是兩個相等的集合。2、定義、定義3-

2、4.1：兩個序偶相等，=，當(dāng)且僅當(dāng)x=u且y=v。一、有序一、有序n元組元組3、有序元組：、有序元組：是一個序偶，其第一元素本身也是一個序偶，表示為，z或。4、有序、有序n元組：元組：有序n元組也是一個序偶，其第一元素是一個n-1元組。 ，xn，通常簡記為：，其中xi稱作它的第i坐標(biāo)，i=1，2，n。n =的充要條件是xi=yi，i=1，2，n。n 序偶其元素可以分別屬于不同的集合，因此任給兩個集合A和B，我們可以定義一種序偶的集合。 1、定義、定義3-4.2：設(shè)A和B是任意兩個集合，由A中元素作第一元素，B中元素作第二元素構(gòu)成序偶，所有這樣序偶的集合稱集合A和B的笛卡爾積或直積。記作AB。即

3、AB=|xAyB二、笛卡爾積二、笛卡爾積2、n個集合的笛卡爾積：集合個集合的笛卡爾積：集合A1，A2，An，則，則特別地，約定：若A=或B=，則A B= ，B A=例題例題 若A=，B=1，2，3，求AB， BA， AA， BB以及(AB)(BA)。解：AB=， BA=， AA=，BB=， ，(AB)(BA)=若A、B均是有限集，|A|=m，|B|=n，則|AB|=mn。三、笛卡爾積的性質(zhì)三、笛卡爾積的性質(zhì)1、對于任意集合A，A=， A= 。2、笛卡爾積運算不滿足交換律，當(dāng)A，B，AB時ABBA。3、笛卡爾積運算不滿足結(jié)合律，即當(dāng)A，B，C均非空時(AB)CA(BC)。 4、定理、定理3-4.

4、1：對任意三個集合：對任意三個集合A、B、C，有，有(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)由以上兩條有：由以上兩條有：A (B C) (A B) (A C)證明兩個集合相等，可以證明它們互相包含。則aA，bBC，即aA，bB，且bc，證明：(2)A(BC)，即AB且AC，有(AB)(AC)，得A(BC)(AB)(AC)(AB)(AC)，則AB且AC，則aA，bB，且aA，bC，則bBC。所以A(BC)，所以(A B) (A C) A (B C)5、定理、定理

5、3-4.2：對于任意集合：對于任意集合A、B、C，若，若C，則，則A B A C B C C A C B證明：設(shè)A C B C 。xA，因C ，任取y C ，有AC因為ACBC，所以BC所以xB，所以A B 設(shè)A B。AC，則xA，yC，又因AB，所以xB，所以BC，所以A C B C同樣，定理的第二部分AB CACB可以類似地證明。6、定理、定理3-4.3：對任意四個非空集合，：對任意四個非空集合，A B C D的充分的充分必要條件是必要條件是A C，B D。證明：充分性。設(shè)AC，BD。由定理3-4.2，因BD，A，所以ABAD。又AC，D非空，所以ADCD，所以ABCD。必要性。設(shè) ABC

6、D。 xA，yB，所以AB，又因ABCD，所以CD，所以xC，yD，所以AC，BD證明定理3-4.3用到集合包含的傳遞性： (AB)(BC) (AC)105頁（2）設(shè)A=a，b，構(gòu)成集合(A) A。解 (A) =，a， b，a，b (A) A=， , , , , , , ,3-5 3-5 關(guān)系及其表示關(guān)系及其表示 兄弟關(guān)系 師生關(guān)系 朋友關(guān)系 戀人關(guān)系 大于關(guān)系一、關(guān)系（一、關(guān)系（Relation）1、關(guān)系、關(guān)系定義3-5.1：任一序偶的集合確定了一個二元關(guān)系R，R記作aRb，稱a與b有關(guān)系，R記作aRb，稱a與b沒有關(guān)系。例如，=|x，y是實數(shù)且xy說明：(1)把關(guān)系R這種無形的聯(lián)系用集合這

7、種“有形”的實體來描述，為今后的描述和論證帶來方便。(2)序偶是講究次序的，如果有R未必有R ，即a與b有關(guān)系R，未必b與a有關(guān)系R。例：甲與乙有父子關(guān)系，但乙與甲沒有父子關(guān)系。 定義3-5.2：二元關(guān)系R中，所有序偶的第一元素的集合dom R稱為R的前域，即： dom R=x|(y)R所有序偶的第二元素的集合ran R稱為R的值域，即：ran R=y|(x)R 。R的前域和值域一起稱作的域，記作FLD R。即：FLD R=dom Rran R例題1 設(shè)H=，求dom H，ran H， FLD H。解： dom H=1，2，3，ran H=2，4，F(xiàn)LD H=1，2，3，4定義3-5.3：令X

8、和Y是任意兩個集合，XY的子集R稱作X到Y(jié)的關(guān)系。如果R是X到Y(jié)的關(guān)系，則dom RX，ran RY。當(dāng)X=Y時，關(guān)系R是XX的子集，這時稱R為在X上的二元關(guān)系。例題2 設(shè)X=1，2，3，4，求X上的關(guān)系及dom ，ran 。解： =，dom =2，3，4，ran =1，2，3(1)全域關(guān)系：對于集合X和Y，稱XY為X到Y(jié)的全域關(guān)系。記作U。 稱為空關(guān)系。(2)二元關(guān)系：R是XX的子集，稱R是X上的二元關(guān)系(3)恒等關(guān)系：Ix稱為X上的恒等關(guān)系iff Ix=|xX例題3 若H=f，m，s，d表示一個家庭中的父、母、子、女四個人的集合，確定H上的全域關(guān)系和空關(guān)系，另外再確定H上的一個關(guān)系，指出該

9、關(guān)系的值域和前域。解：設(shè)H上的同一家庭成員的關(guān)系為H1，H上的互不相識的關(guān)系為H2，則：H1為全域關(guān)系，H2為空關(guān)系；設(shè)H上的長幼關(guān)系為H3 ， H3=，dom H3=f，m，ran H3=s，d解：H=， ，S=HS=， ，HS=XX=， ，H=， ，S-H=例題4 設(shè)X=1，2，3，4，若H=|(x-y)/2是整數(shù)，S=|(x-y)/3是正整數(shù)，求HS，HS， H，S-H。5、定理、定理3-5.1：若：若Z和和S是集合是集合X到到Y(jié)的兩個關(guān)的兩個關(guān)系，則系，則Z和和S的并、交、補、差仍是到的關(guān)系。的并、交、補、差仍是到的關(guān)系。關(guān)系的表示方法關(guān)系的表示方法 集合法 關(guān)系矩陣 關(guān)系圖二、關(guān)系的

10、表示二、關(guān)系的表示1、集合為直觀地表示A到B的關(guān)系,采用如下的圖示:用大圓圈表示集合A和B,里面的小圓圈表示集合中的元素;若aA,bB,且(a,b),則在圖示中將表示a和b的小圓圈用直線或弧線連接起來,并加上從結(jié)點a到結(jié)點b方向的箭頭。例 設(shè)A1,2,3,4,5,Ba,b,c,則1(1,a),(1,b),(2,b),(3,a)是A到B的關(guān)系,而2(a,2),(c,4),(c,5)是B到A的關(guān)系。其集合表示法如下：2、關(guān)系矩陣：設(shè)給定兩個有限集合X=x1，x2，xm， Y=y1，y2，yn，R是X到Y(jié)的關(guān)系，則R的關(guān)系矩陣MR，其中rijmn， rij =1，當(dāng)R， rij =0，當(dāng)R 。111

11、102010310040005000M2010000000000011aMbc其關(guān)系矩陣表示為：例 設(shè)A1,2,3,4,5,Ba,b,c,則1(1,a),(1,b),(2,b),(3,a)是A到B的關(guān)系,而2(a,2),(c,4),(c,5)是B到A的關(guān)系。 關(guān)系矩陣的寫法也可以簡化, 當(dāng)約定了元素的次序后, 可以不寫最左列和最上行的元素。 如2010000000000011M1110010100000000M關(guān)于關(guān)系矩陣的幾點說明：關(guān)于關(guān)系矩陣的幾點說明：(1)空關(guān)系的關(guān)系矩陣的所有元素為0。(2)全關(guān)系的關(guān)系矩陣的所有元素為1。(3)恒等關(guān)系的關(guān)系矩陣的所有對角元為1，非對角元為0，此矩陣

12、為單位矩陣。(4)如果R是X上的二元關(guān)系時，則其關(guān)系矩陣是一個方陣。例題例題5 5 設(shè)設(shè)X=xX=x1 1,x,x2 2,x,x3 3,x,x4 4,Y=y,Y=y1 1,y,y2 2,y,y3 3,R=xR=, , , , , , , , x, , , , ，寫出關(guān)系矩陣，寫出關(guān)系矩陣M MR R。例題例題6 6 設(shè)設(shè)A=1,2,3,4A=1,2,3,4，寫出集合，寫出集合A A上大于關(guān)系上大于關(guān)系 的的關(guān)系矩陣。關(guān)系矩陣。P108 例題例題3、關(guān)系圖：、關(guān)系圖：設(shè)有限集合X=x1，x2，xm， Y=y1，y2，yn，X到Y(jié)的一個關(guān)系為R，則R的關(guān)系圖：(1)做出m個結(jié)點分別記作x1，x2，

13、xm， n個結(jié)點分別記作y1，y2，yn，(2)如果R ，則可自結(jié)點xi至yj作一有向弧;(3)如果R ，則xi至yj沒有線段聯(lián)結(jié)。例 設(shè)A-2, -1, 0, 1, 寫出A上的關(guān)系、 關(guān)系、 關(guān)系、 UA和IA, 并分別寫出這些關(guān)系的定義域和值域（這里、 、 分別表示通常的小于、 小于等于和大于）。并畫出關(guān)系圖。 解 (-2, -1), (-2, 0), (-2, 1), (-1, 0), (-1, 1), (0, 1)Dom-2, -1, 0 Ran-1, 0, 1(-2, -2), (-2, -1), (-2, 0), (-2, 1), (-1, -1), (-1, 0), (-1, 1

14、), (0, 0), (0, 1), (1, 1) DomA RanA(-1, -2), (0, -1), (0, -2), (1, -2), (1, -1), (1, 0) Dom-1, 0, 1 Ran-2, -1, 0UA(-2, -2), (-2, -1), (-2,0), (-2,1), (-1,-2), (-1,-1), (-1, 0), (-1, 1), (0, -2), (0, -1), (0, 0), (0, 1), (1, -2), (1, -1), (1, 0), (1, 1)IA(-2, -2), (-1, -1), (0, 0), (1, 1)Dom UARan UA

15、Dom IARan IAA圖 2 例題 用圖 例題例題7 7 設(shè)設(shè)X=xX=x1 1,x,x2 2,x,x3 3,x,x4 4,Y=y,Y=y1 1,y,y2 2,y,y3 3,R=xR=, , , , , , , , x, , , , ，畫出，畫出R R的關(guān)系圖。的關(guān)系圖。例題例題8 8 設(shè)設(shè)A=1,2,3,4,5A=1,2,3,4,5，在，在A A上的二元關(guān)系上的二元關(guān)系R R給定給定為：為：R=,R=,畫出畫出R R的關(guān)系圖。的關(guān)系圖。P109 例題例題如果A=|m|, |B|=n, 則：|AB|=mn，關(guān)系是AB的子集，AB的子集共有2mn個，所以，X到Y(jié)的關(guān)系共有2mn個。 X到到Y(jié)

16、有多少個不同的關(guān)系？有多少個不同的關(guān)系？ 可定義n元關(guān)系。若S Ai，則稱S為 Ai上的n元關(guān)系。特別A1=A2=An時，稱S為A上的n元關(guān)系。1ni1nin n元關(guān)系元關(guān)系: :二元關(guān)系的推廣二元關(guān)系的推廣作業(yè) P105: 單號：(3)b,d (4)(5) 雙號：(3)c,e (4)(5) P110: (5)a,b,d (6)(7)(8)第二章第二章 習(xí)題課習(xí)題課作業(yè) P59: 1,2的單數(shù) P62: 3,4,6P59(1)用謂詞表達(dá)式寫出下列命題a)小張不是工人。 A(x):x是工人；c：小張 則 A(c)c)小莉是非常聰明和美麗的。A(x): x聰明；B(x): x是美麗的； c：小莉則

17、 A(c) B(c)e) 每一個有理數(shù)是實數(shù)。 Q(x): x是有理數(shù)；R(x): x是實數(shù)則 (x)(Q(x) R(x)g) 并非每一個實數(shù)都是有理數(shù)。Q(x): x是有理數(shù)；R(x): x是實數(shù)則 (x)(R(x) Q(x) )P59(2)用謂詞表達(dá)式寫出下列命題所有教練員是運動員A(x): x是教練員；B(x): x是運動員則 (x)(A(x) B(x)c）某些教練是年老的，但是健壯的。 A(x): x是教練員；B(x): x是年老的； C(x):x是健壯的 (x)(A(x) B(x) C(x)）e）不是所有運動員都是教練。 A(x): x是教練員；B(x): x是運動員則 (x)(B(

18、x) A(x) ) g) 沒有一個國家選手不是健壯的。A(x): x是國家選手；B(x): x是健壯的則 (x)(A(x) B(x) 或 (x)(A(x) B(x)沒有一位女同志既是國家選手又是家庭婦女。A(x): x是女同志；B(x): x是國家選手C(x): x是家庭婦女則 (x)(A(x) B(x) C(x)k) 所有運動員都?xì)J佩某些教練。A(x): x是運動員；B(y): y是教練；C(x，y): x欽佩y則 (x)(A(x)(y)(C(x,y )B(y)P62(3)利用謂詞公式翻譯下列命題 如果有限個數(shù)的乘積為零，則至少有一如果有限個數(shù)的乘積為零，則至少有一個因子等于零。個因子等于零

19、。 對于每一個實數(shù)對于每一個實數(shù)x，存在一個更大的實數(shù)，存在一個更大的實數(shù)y。 存在實數(shù)存在實數(shù)x,y和和z，使得，使得x與與y之和大于之和大于x與與z之積。之積。P62(3)利用謂詞公式翻譯下列命題a)如果有限個數(shù)的乘積為零，則至少有一個因子等于零。 N(x)：x是有限個數(shù)的乘積； F(y)：y是乘積的一個因子 O(x)：x 的乘積為零 E(y)：y等于0 ( x)(N(x)O(x)( y)(F(y)E(y)b)對于每一個實數(shù)x，存在一個更大的實數(shù)y。設(shè) R(x): x是實數(shù)； Q(x,y): y大于x(x)(R(x)(y)(Q(x,y)R(y)c)存在實數(shù)x,y和z，使得x與y之和大于x與

20、z之積。設(shè) R(x): x是實數(shù) G(x,y):x大于y。(x)(y)(z)(R(x) R(y)R(z)G(x+y, xz)P62(4)利用謂詞公式表示 若xy和zyz。設(shè) L(x,y): x小于y; G(x,y):x大于y。( x) ( y) ( z)（L(x,y) L(z,0)G ( xz,yz)P63(6)利用謂詞公式刻畫 那位戴眼鏡的的大大學(xué)生在看這本大大而厚厚的巨著巨著。 設(shè)A(x): x是大學(xué)生； B(x):x是戴眼鏡的； C(x): x是用功的； D(x,y):x在看y； E(y):y是大的； F(y): y是厚的 H(y): y是巨著； a：這本；b:那位B(b)C(b)A(b

21、)D(b,a)E(a)F(a)H(a)P66 (3)判斷各式的真假值a)( x)(P(x)Q(x), 其中其中P(x): x=1，Q(x):x=2，且論域是，且論域是1,2原式原式 (P(1)Q(1) ) (P(2)Q(2) (TF) (FT)Tb) ( x)(PQ(x)R(a), 其中其中P: 21，Q(x): x3, R(x): x5, 而而a:5，論域是，論域是-2,3,6 (PQ(-2) )(PQ(3)(PQ(6)R(a)(T T) (T T）（T F)FF(4) 對下列謂詞公式中的約束變元換名a)x y (P(x,z)Q(y) S(x,y) u v (P(u,z)Q(v) S(x,y

22、)b)( x(P(x)(R(x)Q(x) xR(x) zS(x,z) ( u(P(u)(R(u)Q(u) vR(v) zS(x,z)(5)對下列公式中的自由變元進(jìn)行代入 ( yA(x,y) xB(x,z) x zC(x,y,z) ( yA(x,y) xB(x,z) x zC(x,y,z) ( yA(u,y) xB(x,v) x zC(x,w,z) ( yP(x,y) zQ(x,z) xR(x,y) ( yP(x,y) zQ(x,z) xR(x,y) ( yP(u,y) zQ(u,z) xR(x,w)P72 （4）求證： ( x)(A(x)B(x) ( x)A(x)( x)B(x)右邊右邊=(

23、x)A(x)( x)B(x)( x)A(x)( x)B(x) ( x) A(x)( x)B(x)( x) (A(x)B(x)( x)(A(x)B(x)（7）求證：( x) ( y)(P(x)Q(y) ( x)P(x)( y)Q(y)右邊右邊( x)P(x)( y)Q(y) ( x)P(x)( y)Q(y) ( x) P(x)( y)Q(y)( x) ( y)(P(x)Q(y)( x) ( y)(P(x)Q(y)P75 (1) 化為前束范式( x)( y)P(x,y)( z)Q(z)R(x) ( x)( ( y)P(x,y)( z)Q(z)R(x) ( x)( ( y)P(x,y)( z)Q(z

24、)R(x) ( x)( y)( z)(P(x,y)(Q(z)R(x)(2)求前束合取范式b) ( x)(P(x)( y)( z)Q(x,y)( z)R(y,x)( x)(P(x)( y)(Q(x,y)R(y,x)(消去多余量詞）消去多余量詞）( x)(P(x)( y)(Q(x,y)R(y,x)( x)( y)(P(x)(Q(x,y)R(y,x)( x)( y)(P(x)Q(x,y)R(y,x) 前束合取范式前束合取范式(2)求前束合取范式b) ( x)(P(x)( y)( z)Q(x,y)( z)R(y,x)( x)( y)(P(x)Q(x,y)R(y,x)( x)( y)(P(x)Q(x,y

25、)R(y,x)(P(x)P(x)( x)( y)(P(x)P(x)(P(x)P(x)(Q(x,y)P(x)(Q(x,y)P(x)(R(y,x)P(x)(R(y,x)P(x)( x)( y)(P(x)P(x)(Q(x,y)P(x)(Q(x,y)P(x)(R(y,x)P(x)(R(y,x)P(x) 前束析取范式前束析取范式(2)求前束合取范式c) ( x)P(x)( x)( z)Q(x,z)( z)R(x,y,z)( x)P(x)( x)( z)Q(x,z)( z)R(x,y,z)( x) P(x)( x)( z)Q(x,z)( z)R(x,y,z)( x)(P(x)( z)Q(x,z)( u)R(x,y,u)( x)( z)( u)(P(x)Q(x,z)R(x,y,u)前束合取范式前束合取范式(2)求前束合取范式c) ( x)P(x)( x)( z)Q(x,z)( z)R(x,y,z)( x)( z)( u)(P(x)Q(x,z)R(x,y,u)( x)( z)( u)(P(x)Q(x,z)R(x,y,u) (P(x)P(x) 。前束析取范式