《二元關系和函數》PPT課件

4.1 集合的笛卡兒積與二元關系一 、 有 序 對定義4.1 由兩個元素 x 和 y (允許 x=y )按一定的順序排列成的二 元 組叫做一個有 序對 (也稱序 偶 ), 記作, 其中 x 是它的第一元素, y 是它的第二元素。例：平面直角坐標系中點的坐標 例： = , 求 x, y。 解：3y 4 = 2, x+5 = y y = 2, x = 3 = x=u y=v 定義4.2 定義4.3 Aa, b, B0, 1, 2, 則 問：如果A中有m個元素, B中有n個元素, 則 AB 和 BA 中都有多少個元素?答：mn 個若AB, 則有xA 和 yB。若AB, 則有xA 或者 y B. 笛 卡 兒 積 運 算 的 性 質 性 質 的 證 明 例題 笛 卡 兒 積 運 算 的 性 質 定義4.4 例：有A, B, C三個人和四項工作, , , , 已知A可以從事工作, , B可以從事工作, C可以從事工作, 。那么人和工作之間的對應關系可以記作R, , , , 這是人的集合A, B, C 到工作的集合, , , 之間的關 系。 R 小于或等于關系：LA=| , A 。其中：AR 整除關系：DB=| , B整除, 其中：BZ* , Z*是非零整數集包含關系：R| , A , 其中：A是集合族。 設 A=1, 2, 3, Ba, b 則 L A=, , , , , DA=, , , , 設A=1, 2, 3, 4, 下面各式定義的R都是A上的關系, 試用列元素法表示R。(1) R= | x是y的倍數(2) R= | (x-y)2 A(3) R= | x/y是素數(4) R= | xy 0010 0000 1100 0011RM R2 R3 例：設 R=, , , S=, , , , 求：R1 , R S, S R解：R1 = , , , R S =, , , S R =, , S R SR 1 1 = x,y x,y N y x 定義4.10 設 A = a, b, c, d, R = , , , , 求：R的各次冪。 設 A = a, b, c, d, R = , , , , 求：R的各次冪。解：R與R2的關系矩陣分別為 0000 1000 0101 0010M 0000 0000 1010 01010000 1000 0101 00100000 1000 0101 0010 2M 1000 0100 0010 00010M 0000 0000 1010 0101,0000 0000 0101 1010 43 MM R0, R1, R2, R3, 的關 系 圖如下圖所示 三 、 集 合 運 算 對 關 系 性 質 影 響 對于的運算, 都可以經過的方法給出一般的證明。對于不 保 持 關 系 性 質的運算, 都可舉 一 反 例說明。 四 、 關 系 性 質 的 等 價 描 述 一 、 閉 包 的 定 義 二 、 閉 包 的 構 造 方 法 用 關 系 圖 、 關 系 矩 陣 求 閉 包 的 一 般 方 法 三 、 閉 包 的 主 要 性 質 表示R, 則用表示R-1, 即互 為 對 偶。 a c b, 則稱 b 蓋 住 a 。定義可知, 在 中, 可能有下述三種情況發(fā)生 a 與b 不 可 比 的。 若(x)(xB b x)為真, 則稱b為B的極 大元4. 8 7 5 3 1 2 4 6 8 7 5 3 1 2 4 6 。 8 7 5 3 1 2 4 6 說 明 既非單射又非滿射 單射雙射滿射 YXX ran f dom g = W f: XY, g: YZ, gf : XZ (5) 如果 gf 是單 射的, 則 f 是單 射的。 gf 是單 射 , 即對x1, x2X且x1x2 有 gf (x1) gf (x2) 即 g(f(x1) g(f(x2) f(x1) f(x2) f 是XY 單 射的。例：X=1, 2, Y=a, b, c, Z=x, y, z f=, g=, , gf = , 顯然, gf、f 是單 射的, 但 g 不是單 射的。f: XY, g: YZ, gf : XZg 一定單 射嗎？g 不一定單 射。 f: XY, g: YZ, gf : XZ A, 有 , -1, 逆 函 數 定 義 設 f: AB是雙 射的, 則 f- 1 f = IA, f f-1 = IB根據定理4.8可知 f- 1: BA 也是雙射的, 且 f- 1 f：AA, f f- 1：BB。 任取 xA, !yB 使 y = f(x), x = f 1(y) f- 1 f(x) = f 1(f(x) = f1(y) = x = IA同理可證： f f-1 I B