[工學(xué)]第三章集合與關(guān)系(編輯修改稿)

　

【文章內(nèi)容簡介】 5 化簡 ((A∪ B∪ C)∩(A∪ B)) – (( A∪ (B – C))∩A) 解： 因 A∪ B ? A∪ B∪ C， A ? A∪ (B – C), 故 ((A∪ B∪ C) ∩(A∪ B)) – (( A∪ (B – C)) ∩A) =(A∪ B) – A =(A∪ B) ∩～ A =(A ∩～ A) ∪ (B∩～ A) = 216。∪ (B－ A) =B－ A 例 16 已知 A?B = A?C, 證明 B=C 證： A?(A?B) = A?(A?C) （ 已知 ） ? (A?A)?B＝ (A?A)?C) ? 216。?B= 216。?C ? B=C 第三章 集合與關(guān)系 序偶與笛卡兒積 *重點(diǎn)：序偶表示兩個(gè)有順序的對(duì)象； 笛卡爾積中也有順序的概念。 第三章 集合與關(guān)系 序偶與笛卡兒積 兩個(gè)具有固定次序的客體組成一個(gè) 序偶 ，它常表達(dá)兩個(gè)客體間的關(guān)系。 定義 1： 設(shè) a， b為任意對(duì)象，稱集合｛｛ a｝，｛ b｝｝為 二元有序組 ，或 序偶 （ ordered pairs），簡記為 a， b。稱 a為 a， b的第一元素，稱 b為第二元素。 第三章 集合與關(guān)系 序偶與笛卡兒積 對(duì)任意序偶 a， b 、 c, d ,a， b = c, d 當(dāng)且僅當(dāng) a＝ c且 b = d 。 當(dāng) x?y時(shí)， x, y ?y, x。 定義 2： 遞歸定義 n元序組 a1， …a n a1， a2 =｛｛ a1｝，｛ a2｝｝ a1， …a n = a1， …a n1, an 第三章 集合與關(guān)系 序偶與笛卡兒積 對(duì)任意對(duì)象 a1， … ， an， b1， … ， bn， a1， … ， an = b1， … ， bn 當(dāng)且僅當(dāng) a1 = b1 ， … ， an= bn 第三章 集合與關(guān)系 序偶與笛卡兒積 對(duì)任意集合 A1， A2 , … ， An， （ 1） A1 ? A2，稱為集合 A1 , A2的 笛卡兒積 或 直積 (Cartesian product)，定義為 A1 ? A2=｛ u,v ? u ?A1∧ v?A2｝ （ 2） 遞歸地定義 A1 ? A2 ? … ? An A1 ? A2 ? … ? An= (A1 ? A2 ? … ? An1 )? An 當(dāng) A1 = A2 = … =An =A時(shí)， A1 ? A2 ? … ? An簡記為 An 定義 3： 第三章 集合與關(guān)系 序偶與笛卡兒積 對(duì)任意集合 A1， A2 , … ， An， A1 ? A2 ? … ? An= ｛ a1, …, an ? a1 ?A1∧ … ∧ an ?An｝｝ 約定： 若 A= ?或 B= ? ，則 A ? B= ?。 第三章 集合與關(guān)系 序偶與笛卡兒積 設(shè) A, B, C為任意集合則有： A?(B?C)＝ (A?B)?(A?C) A?(B?C)＝ (A?B)?(A?C) (B?C)?A＝ ( B?A)?(C?A) (B?C)?A＝ ( B?A)?(C?A) 定理 1： 第三章 集合與關(guān)系 例 1 證明 A (B∪ C)=(A B)∪ (A C)。 證：任取 x,y ?A (B∪ C) x, y?A (B∪ C) ? x?A ∧ y?(B∪ C) ? x?A ∧ (y?B ∨ y?C) ? (x?A ∧ y?B)∨ (x?A ∧ y?C) ? (x, y ? A B)∨ (x, y ? A C) ? x, y ? (A B) ∪ (A C) ∴ A (B∪ C) = (A B) ∪ (A C) 第三章 集合與關(guān)系 例 2 設(shè) A= {1, 2} ,求 P(A) A。 解： P(A) A ={216。,{1},{2},{1,2}} {1,2} ={216。, 1, 216。, 2, {1}, 1, {1},2, {2},1, {2},2, {1,2},1, {1,2},2} 第三章 集合與關(guān)系 例 3 設(shè) A, B, C, D為任意集合 ， 判斷下列命題是否為真 。 （ 1） A B＝ A C ? B=C （ 2） A – (B C) = (A – B) (A – C) （ 3） (A=B)∧ (C=D) ? A C=B D （ 4） 存在集合 A,使 A?A A 解 :(1) 不一定為真， 當(dāng) A=?, B={1}, C={2,3}時(shí)，便不真。 (2) 不一定為真， 當(dāng) A=B={1},C={2}時(shí)， A–(B C) = {1}–{1,2} = {1}, 而 (A–B) (A–C)= ? {1}= ?. 第三章 集合與關(guān)系 例 3 設(shè) A, B, C, D為任意集合 ， 判斷下列命題是否為真 。 （ 1） A B＝ A C ? B=C （ 2） A – (B C) = (A – B) (A – C) （ 3） (A=B)∧ (C=D) ? A C=B D （ 4） 存在集合 A,使 A?A A 解 : (3) 為真。 (4) 為真。 等量代入。 當(dāng) A = ?時(shí) ,使 A?A A. 第三章 集合與關(guān)系 序偶與笛卡兒積 若 C≠ ? ，則 A ? B = ( A?C ? B?C) =(C?A ? C?B) 定理 2： 第三章 集合與關(guān)系 序偶與笛卡兒積 定理 3： 設(shè) A、 B、 C、 D為四個(gè)非空集合，則： A?B ? C?D的充要條件為 A ? C， B ? D 關(guān)系的基本概念 關(guān)系的基本運(yùn)算 第三章 集合與關(guān)系 關(guān)系 關(guān)系的表示 重點(diǎn)：關(guān)系的概念及表示方法。 第三章 集合與關(guān)系 關(guān)系 第三章 集合與關(guān)系 關(guān)系 關(guān)系的基本概念 定義 1: 任一序偶的集合確定了一個(gè)二元關(guān)系 R， R中任一序偶 x,y可記作 x,y?R或 xRy。不在 R中的任一序偶記作 x,y?R或 xRy。 父子、兄弟、師生、電影票與座位間的對(duì)號(hào)關(guān)系等。 第三章 集合與關(guān)系 關(guān)系 關(guān)系的基本概念 定義 2： 令 X和 Y是任意集合 ， 直積 X Y的子集 R稱作X到 Y的關(guān)系 。 當(dāng) X=Y時(shí)， R稱為在 X上的二元關(guān)系。 第三章 集合與關(guān)系 關(guān)系 關(guān)系的基本概念 設(shè) R為 A到 B的二元關(guān)系。 （ 1）稱 DomR為關(guān)系 R的 前域 （ domain）， DomR=｛ x|x?A∧ ?y(x,y?R)｝ （ 2）稱 RanR為關(guān)系 R的 值域 （ range）， RanR＝｛ y| y ?B∧ ?x(x,y?R)｝ （ 3） R的前域和值域一起稱作 R的域，記作 FLDR FLDR=DomR ? RanR 定義 3: 第三章 集合與關(guān)系 關(guān)系 關(guān)系的基本概念 例 1 R={ 1, 2,1, 3,2, 4,4, 3}, 則 DomR={1, 2, 4}， RanR={2, 3, 4}, FLD R={1, 2, 3, 4}。 第三章 集合與關(guān)系 關(guān)系 關(guān)系的基本概念 ? ? A?B, 稱 ?為 A到 B的 空關(guān)系 。 A?B ? A?B ，稱 A?B 為 A到 B的 全關(guān)系 。 兩個(gè)特殊的二元關(guān)系： 第三章 集合與關(guān)系 關(guān)系 關(guān)系的基本運(yùn)算 設(shè) Ix是 X上的二元關(guān)系且滿足 Ix={x,x|x?X}， 則稱 Ix是 X上的恒等關(guān)系。 定義 4： 第三章 集合與關(guān)系 關(guān)系 關(guān)系的基本運(yùn)算 定理 1： 若 Z和 S是從集合 X到 Y的兩個(gè)二元關(guān)系，則 Z、 S的并、交、補(bǔ)、差仍是 X到 Y的關(guān)系。 第三章 集合與關(guān)系 關(guān)系的表示： 1. 集合表達(dá)式 ：列出關(guān)系中的所有有序?qū)?。 例 2 設(shè) A=?1,2,3,4?, 試列出下列關(guān)系 R的元素 。 (1)R=?x,y?x是 y的倍數(shù) ? (2)R=?x,y?(x－ y)2?A? (3)R=?x,y?x/y是素?cái)?shù) ? (4)R=?x,y?x?y? (5)R=?x,y? (x,y?A)∧ (x?y)? 解 :(1) R={ 4, 4,4, 2, 4, 1,3,3,3,1,2,2,2,1,1,1} (2) R={2, 1,3, 2,4, 3,3,1,4,2, 2,4,1,3,3,4, 2,3,1,2} (3) R={ 2, 1,3, 1,4, 2} (4) R=EAIA={1, 2,1, 3, 1, 4, 2,1,2,3,2,4, 3,1,3,2, 3,4,4,1,4,2,4,3} (5) R={ 1, 2,1, 3,1, 4,2,3,2,4,3,4} 第三章 集合與關(guān)系 關(guān)系 關(guān)系的表示 如果 X、 Y是有限集，則二元關(guān)系 R除可用序偶集合的形式表達(dá)外還可用 矩陣 或 圖形 表示。 矩陣： 如 R是從有限集 X到 Y的一個(gè)二元關(guān) 系，則對(duì)應(yīng) R有一個(gè)關(guān)系矩陣 MR=[rij]m n 其中 rij=1當(dāng) xi R yj, rij=0當(dāng) xiRyj 第三章 集合與關(guān)系 關(guān)系的表示 2. 關(guān)系矩陣法： 設(shè) A={x1,x2,… xn},R 是 A 上 的關(guān)系 。 令： ??? ?? ),2,1,(,01 njiRxxr jiij ?否則若????????????????nnnnnnijRrrrrrrrrrrM???????212222111211)(則矩陣 稱為 R 的 關(guān)系矩陣 。 第三章 集合與關(guān)系 關(guān)系的表示 例 3 設(shè) A={1, 2, 3, 4}, R={1,1, 1,2, 2, 3, 2, 4, 4, 2}, 則 R的關(guān)系矩陣為 ???????????????0010000011000011RM第三章 集合與關(guān)系 關(guān)系 關(guān)系的表示 關(guān)系圖： R為 X到 Y的關(guān)系， R的圖形表示 是先在平面上畫 n個(gè)點(diǎn)分別表示 X 中的元素，再畫 m個(gè)點(diǎn)分別表示 Y 中的元素， 當(dāng) xiRyj，則自 xi到 yj 畫一條有向邊，箭頭指向 yj，否 則不畫 。 如果 X、 Y是有限集，則二元關(guān)系 R除可用序偶集合的形式表達(dá)外還可用 矩陣 或 圖形 表示。 第三章 集合與關(guān)系 關(guān)系 關(guān)系的表示 3. 關(guān)系圖法 設(shè) A={x1,x2,… xn}, R是 A上的關(guān)系 。 以 A的元素作為