PowerPoint 演示文稿

Size: px

Start display at page:

Download "PowerPoint 演示文稿"

娈肯宫
5 years ago
Views:

1 第二章二元关系 2-1 有序对与卡氏积 2-2 二元关系 2-3 关系矩阵和关系图 2-4 关系的性质 2-5 二元关系的幂运算 2-6 关系的闭包 2-7 等价关系和划分 2-8 序关系 Peking University 1

2 2-1 有序对与卡氏积 1. 有序对 ( 序偶 ordered pairs) 的概念 2. 卡氏 ( 笛卡儿 ) 积 3. 笛卡儿积的性质 Peking University 2

3 Ordered pairs {1,2} = {2,1} unordered pair <1,2> {2,1} order pairs How to define <.,.>? <x,y> 1 = {x,y} <x,y> 2 = {x,{y}} (<{Ф},{Ф}>=<{{Ф}},Ф>) Peking University 3

4 The first successful definition was given by Norbert Wiener in 1914 <x,y>={{{x},ф}, {{y}}} A simpler definition was given by Kazimierz Kuratowski in 1921, is in general use today <x,y>= {{x},{x,y}} Peking University 4

5 1 序偶的概念许多事物是成对出现的, 而且这种成对出现的事物, 具有一定的顺序例如 : 上下 ; 左右 ;3<4; 平面上的坐标等一般地说, 由两个具有固定次序的客体组成, 来表达两个客体之间的关系定义 2.1 称 {{a},{a,b}} 为由元素 a b 构成的有序对或序偶, 记作 <a,b> 其中 a 称为有序对的第一个元素,b 称为第二个元素, 且 a,b 可以相同注 : 有序对可以看作是具有两个元素的集合, 与一般集合不同的是有序对具有确定的次序 Peking University 5

6 定理 2.1 <a,b>=<c,d>, 当且仅当 a=c,b=d 引理 1 {x,a}={x,b}, 当且仅当 a=b 引理 2 设 A,B 是非空的集族, 若 A=B, 则 (1) A= B ; (2) A= B 推论 a b 时,<a,b> <b,a> Peking University 6

7 引理 1 的证明 {x,a}={x,b} 当且仅当 a=b 证明 :a=b {x,a}={x,b} x=a, {x,a}={x,b} {a,a}={a,b} {a}={a,b} b=a x a, a {x,a}={x,b} a=b {x,a}={x,b} a=b # Peking University 7

8 引理 2 的证明引理 2 设 A,B 是非空的集族, 若 A=B, 则 (1) A= B ; (2) A= B 证明 : (1) x, x A z(z A x z) z(z B x z) x B A = B (2) x, x A z(z A x z) z(z B x z) x B A = B # Peking University 8

9 定理证明 <a,b>=<c,d>, 当且仅当 a=c,b=d 证明 :<a,b>=<c,d> {{a},{a,b}}={{c},{c,d}} {{a},{a,b}}= {{c},{c,d}} {a,b}={c,d} {{a},{a,b}}={{c},{c,d}} {{a},{a,b}}= {{c},{c,d}} {a}={c} a=c ({a,b}={c,d}) ({a}={c}) b=d <a,b>=<c,d> a=c,b=d # Peking University 9

10 推论证明推论 : a b <a,b> <b,a> 证明 : ( 反证 ) <a,b>=<b,a> a=b, 与 a b 矛盾. # Peking University 10

11 序偶的概念可推广到三元组四元组 n 元组 : 有序三元组 (ordered triple) <x,y,z> 表示序偶 <<x,y>,z>; 有序四元组 <x,y,z,w> 表示序偶 <<x,y,z>,w>; 有序 n 元组 <x 1, x 2,,x n > 表示序偶 <<x 1,x 2,,x n-1 >,x n > Peking University 11

12 有序 n 元组定义 2.2 一个有序 n(n 2) 元组是一个有序对, 它的第一个元素为有序的 (n-1) 元组 <a 1,a 2,,a n-1 >, 第二个元素为 a n, 记为 < a 1,a 2,,a n > 即 <<a 1,a 2,,a n-1 >,a n > = < a 1,a 2,,a n > 定理 2.2 < a 1,a 2,,a n > = < b 1,b 2,,b n > 当且仅当 a i =b i, i=1,2,, n. 注 :n 元组有严格的集合定义, 但我们关注的是有序对及有序 n 元组的次序性, 不过多讨论他们的集合表示 Peking University 12

13 2 卡氏积 (Cartesian product) 定义 2.3 设 A B 为集合, 称由 A 中元素为第一个元素,B 中元素为第二个元素的所有有序对组成的集合为 A 与 B 的卡氏积 ( 笛卡儿积 ), 记作 A B, 即 A B={<x,y> x A y B} 例 1 设 A ={a,b}, B ={1,2,3}, 求 A B, B A 解 :A B={<a,1>,<a,2>,<a,3>,<b,1><b,2>,<b,3>} B A={<1,a>,<1,b>,<2,a>,<2,b>,<3,a>,<3,b>} 由此例可知, 笛卡儿积不满足交换律 # Peking University 13

14 卡氏积的性质非交换 : 非结合 : 分配律 : 其他 : A B B A ( 除非 A=B A= B= ) (A B) C A (B C) ( 除非 A= B= C= ) A (B C) = (A B) (A C) 等 A B= A= B= 等

15 卡氏积非交换性非交换 : 反例 : A B B A ( 除非 A=B A= B= ) A={1}, B={2}. A B = {<1,2>}, B A = {<2,1>}.

16 卡氏积非结合性非结合 : (A B) C A (B C) ( 除非 A= B= C= ) 反例 : A=B=C={1}. (A B) C = {<<1,1>,1>}, A (B C) = {<1,<1,1>>}.

17 卡氏积分配律 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)

18 卡氏积图示 D A A C B C A (B C) = (A B) (A C) B A C B D A B C D

19 笛卡儿积的性质例证明 (B C) A=(B A) (C A) 证 : 在集合 (B C) A 中任取 <x,y>, 那么 <x,y> (B C) A x (B C) y A (x B x C) y A x B y A x C y A (x B y A) (x C y A) <x,y> (B A) <x,y> (C A) <x,y> (B A) (C A) (B C) A=(B A) (C A) # ( 卡氏积图示 ) Peking University 19

20 3 笛卡儿积的性质 ( 续 1) (5) 若 C, 则 A B (A C B C) (C A C B) 证 : 证, 任取 <x,y> A C, 有 <x,y> A C x A y C x B y C <x,y> B C 因此, A C B C 证, 若 A=, 则 A B. 若 A,C, A C B C, 取 y C, 则有 x A x A y C ( 已设 y C, 故 y C 为真 ) <x,y> A C <x,y> B C x B y C x B 因此, A B 类似可证 : A B (C A C B) # (6) 设 A B C D 为任意非空集合, 则 (A B C D) A C B D ( 证明与性质 (5) 的证明方法类似, 从略 ) Peking University 20

21 3 笛卡儿积的性质 ( 续 2) 例证明 (A-B) C=(A C)-(B C) 证 :<x,y> (A-B) C x (A-B) y C x A x B y C (x A y C x B) (x A y C y C) (x A y C) (x B y C) (x A y C) ( x B y C) (x A y C) (x B y C) <x,y> A C <x,y> B C <x,y> (A C)-(B C) 所以,(A-B) C=(A C)-(B C) # Peking University 21

22 n 维卡氏积 n 维卡氏积 : A 1 A 2 A n = { <x 1,x 2,,x n > x 1 A 1 x 2 A 2 x n A n } A n = A A A A i =n i,i =1,2,,n A 1 A 2 A n = n 1 n 2 n n. n 维卡氏积性质与 2 维卡氏积类似.

23 n 维卡氏积的性质非交换 : A B C B C A ( 要求 A,B,C 均非空, 且互不相等 ) 非结合 : 分配律 : 例如 A B (C D)=(A B C) (A B D) 其他 : 如 A B C= A= B= C=.

24 小结有序对 ( 有序二元组 ) <a,b> = {{a},{a,b}} 有序三元组, 有序 n 元组卡氏积 A B = { <x,y> x A y B } 卡氏积性质 : 非结合非交换分配律等

25 2.2 二元关系事物之间存在着各式各样的关系, 例如, 三名学生 A B C 选修四门课, 设 A 选和,B 选,C 选和, 那么, 学生选课的对应关系可记作 : R={<A, >,<A, >,<B, >,<C, >,<C, >} 这个序偶的集合 R 反映了学生集合 S={A,B,C} 与课程集合 T={,,, } 之间的关系关系的概念关系的运算 ( 定理 ) Peking University 25

26 定义 2.5 若集合 F 中的全体元素均为有序的 n(n 2) 元组, 则称 F 为 n 元关系当 n=2 时, 称 F 为二元关系, 简称为关系对于二元关系 F, 若 <x,y> F, 记作 xfy 表示方法 :( 中缀, 前缀, 后缀 ) 规定空集 Ø 为 n 元空关系, 简称空关系 Peking University 26

27 n 元关系 ( 续 ) 例 1: F1={<a,b,c,d>,<1,2,3,4>,< 物理, 化学, 生物, 数学 >},F1 是 4 元关系. # 例 2:F2={<a,b,c>,<α,β,γ>,< 大李, 小李, 老李 >}, F2 是 3 元关系. # 例 3:R1={<1,2>,<α,β>,<a,b>}, R1 是 2 元关系. # 例 4:R2={<1,2>,<3,4>,< 白菜, 小猫 >}, R2 是 2 元关系. # 例 5:A={<a,b>,<1,2,3>,a,α,1}, A 不是关系. # Peking University 27

28 关系的概念 ( 续 1) 定义 2.6 设 A 和 B 是两个任意集合, 卡氏积 A B 的任一子集 R 称为 A 到 B 的二元关系 R A B R P(A B) 若 A =m, B =n, 则 A B =mn, 故 P(A B) =2 mn 即 A 到 B 不同的二元关系共有 2 mn 个 Peking University 28

29 关系举例例设 A={1,2,3,4}, 求 A 上的小于等于关系 L A 解 :L A ={<x,y> x,y A x y} ={<1,1>,<1,2>,<1,3>,<1,4>, <2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} # Peking University 29

30 关系举例设 A={a1,a2}, B={b}, 则 A 到 B 的二元关系共有 4 个 : R 1 =, R 2 ={<a1,b>}, R 3 ={<a2,b>}, R 4 ={<a1,b>,<a2,b>}. B 到 A 的二元关系也有 4 个 : R 5 =, R 6 ={<b,a1>}, R 7 ={<b,a2>}, R 8 ={<b,a1>,<b,a2>}. # Peking University 30

31 A 上的二元关系 A 上的二元关系 : 是 A A 的任意子集 R 是 A 上的二元关系 R A A R P(A A) Peking University 31

32 关系的概念 ( 续 4) 例设集合 A 有 n 个元素, 问 A 上可能的二元关系有多少个? 解 : 集合 A 上的二元关系与 A A 的子集个数相同若 A =n, 则 A A =n 2, A A 的子集个数就有 2 的 n 2 次方个所以 A 上不同的二元关系有 2 的 n 2 次方个例如, 集合 A={a,b} 上的二元关系有 16 个 Peking University 32

33 关系的概念 ( 续 3) 求 : 集合 A={a,b} 上的 16 个二元关系 R 1 = ( 空关系 ) ; R 2 ={<a,a>}, R 3 ={<b,b>}, R 4 ={<a,b>}, R 5 ={<b,a>}; R 6 ={ <a,a>,<b,b> }( 恒等关系 I A ), R 7 ={<a,a>,<a,b>}, R 8 ={<a,a>,<b,a>}, R 9 ={<b,b>,<a,b>}, R 10 ={<b,b>,<b,a>}, R 11 ={<a,b>,<b,a>}; R 12 ={<a,a>,<b,b>,<a,b>}, R 13 ={<a,a>,<b,b>,<b,a>}, R 14 ={<a,a>,<a,b>,<b,a>}, R 15 ={<b,b>,<a,b>,<b,a>}; R 16 ={ <a,a>,<b,b>,<a,b>,<b,a> } ( 全域关系 E A ) Peking University 33

34 几种特殊的关系称 E A = {(<x,y> x A y A) }=A A 是 A 上的全域关系称 I A = {(<x,x> x A) } 是 A 上的恒等关系若 A 是实数集或其子集, 称 D A = {(<x,y> x A y A x y) } 是 A 上的整除关系称 L A = {(<x,y> x A y A x y) } 是 A 上的小于等于关系若 A 为任意的集合称 A = {(<x,y> x A y A x y) } 是 P(A) 上的包含关系称 A = {(<x,y> x A y A x y) } 是 P(A) 上的真包含关系 Peking University 34

35 整除关系举例例 : A={1,2,3,4,5,6}, 则 D A ={<1,1>, <1,2>, <1,3>, <1,4>, <1,5>, <1,6>, <2,2>,<2,4>,<2,6>, <3,3>,<3,6>,<4,4>,<5,5>,<6,6>}. # Peking University 35

36 二元关系相关概念定义域, 值域, 域逆, 合成 ( 复合 ) 限制, 象单根, 单值 Peking University 36

37 关系相关的概念定义 2.7 设 R 为任一集合, 称 domr = { x y (<x,y> R) } 为 R 的定义域, 称 ranr = { y x (<x,y> R) } 为 R 的值域, 称 fldr = domr ranr 为 R 的域 Peking University 37

38 例 : 设 R 1 ={a,b},r 2 ={a,b,<c,d>,<e,f>}, R 3 ={<1,2>,<3,4>,<5,6>} 解 : 当 a,b 不是有序对时, R 1 和 R 2 不是关系. 由定义得 domr 1 =, ranr 1 =, fldr 1 =, domr 2 ={c,e},ranr 2 ={d,f},fldr 2 ={c,e,d,f}, domr 3 ={1,3,5},ranR 3 ={2,4,6},fldR 3 ={1,2,3,4,5,6} # Peking University 38

39 关系的运算定义 2.8 设 F,G,A 为 3 个集合, (1) F 的逆 (inverse): 称 F -1 ={<x,y> <y,x> F} (2) F 与 G 的合成或复合 (composite): F G={<x,y> z(<x,z> G <z,y> F) x G z F y Peking University 39

40 注意 (1) 当 R 中无有序对时,domR,ranR,fldR 均为 Ø (2) F G 的合成为逆序合成 Peking University 40

41 限制和像 F A={<x,y> <x,y> F x A} 为 F 在 A 上的限制 (restriction) F[A]=ran(F A) 为 A 在 F 下的像 F[A]={y x(x A xfy) } Peking University 41

42 单根若对于任意的 y ranf, 唯一地存在着 x domf, 使得 <x,y> F, 则称 F 是单根 (single rooted) 的 y( y ran F!x( x domf xfy) ) ( y ran F)(!x domf)(xfy)! 表示存在唯一的 Peking University 42

43 单值 (single valued) 若对于任意的 x domf, 唯一地存在着 y ranf, 使得 <x,y> F, 则称 F 是单值的 x( x domf!y( y ran F xfy) ( x domf)(!y ran F)(xFy) Peking University 43

44 例 2.2 设 A={a,b,c,d}, B={a,b,<c,d>}, R={ <a,b>, <c,d> }, F={ <a,b>, <a,{a}>, <{a},{a,{a}}> }, G={ <b,e>,<d,c> }. 求 : (1) A -1, B -1,R -1. (2) BoR -1, GoB, GoR, RoG. (3) F {a}, F {{a}}, F {a,{a}}, F -1 {{a}}. (4) F[{a}], F[{a,{a}}], F -1 [{a}], F -1 [{{a}}]. 44

45 例 2.2(1) A={a,b,c,d}, B={a,b,<c,d>}, R={ <a,b>, <c,d> }, 求 : (1) A -1, B -1,R -1. 解 : (1) A -1 =, B -1 = {<d,c>}, R -1 = {<b,a>,<d,c>}. 45

46 例 2.2(2) B={a,b,<c,d>}, R={<a,b>,<c,d>}, G={<b,e>,<d,c>}. 求 : (2) BoR -1, GoB, GoR, RoG. 解 : (2) BoR -1 ={<d,d>}, GoB={<c,c>}, GoR={<a,e>,<c,c>}, RoG={<d,d>}. 46

47 例 2.2(3) F={<a,b>,<a,{a}>,<{a},{a,{a}}>}, 求 : (3) F {a}, F {{a}}, F {a,{a}}, F -1 {{a}}. 解 : (3) F {a}={<a,b>,<a,{a}> }, F {{a}}={<{a},{a,{a}}>}, F {a,{a}} = F, F -1 {{a}}={<{a},a>}. 47

48 例 2.2(4) F={<a,b>,<a,{a}>,<{a},{a,{a}}> }, 求 : (4) F[{a}], F[{a,{a}}], F -1[ {a}], F -1[ {{a}}]. 解 : (4) F[{a}] = { b, {a} }, F[{a,{a}}] = { b, {a}, {a,{a}} }, F -1 [{a}] =, F -1 [{{a}}] = { a }. # 48

49 例 2.3 设 R={<x,y> x,y Z y= x }, A={0,1,2}, B={0,-1,-2} 求 : (1) R[A B] 和 R[A] R[B]; (2) R[A]-R[B] 和 R[A-B]. 解 : (1) R[A B]=R[{0}]={0}, R[A] R[B]={0,1,2} {0,1,2}={0,1,2}; (2) R[A]-R[B]={0,1,2}-{0,1,2}=, R[A-B]=R[{1,2}]={1,2}. # 49

50 定理 2.3 定理 2.4 定理 2.5 定理 2.6 定理 2.7 定理 2.8 定理 2.9 定义域和值域相关的定理逆的定义域和值域相关定理合成的结合律合成相关的分配律逆合成定理限制相关的定理像相关的定理 Peking University 50

51 定理 2.3 设 F,G 为二集合, 则 (1) dom(f G) = domf domg; (2) ran(f G) = ranf rang; (3) dom(f G) domf domg; (4) ran(f G) ranf rang; (5) domf domg dom(f G); (6) ranf rang ran(f G). Peking University 51

52 定理 2.3 的证明证 :dom(f G) = domf domg 证明 : x, x dom(f G) y(<x,y> F G) y((<x,y> F) (<x,y> G)) y(<x,y> F) y(<x,y> G) x dom(f) x dom(g) x (dom(f) dom(g)) dom(f G) = domf domg # Peking University 52

53 定理 2.3 的证明 ( 续 ) 证 :ran(f G) ranf rang 证明 : y, y ran(f G) x(<x,y> F G) x(<x,y> F <x,y> G) x(<x,y> F) x(<x,y> G) (P7) y ran(f) y ran(g) y (ranf rang) ran(f G) ranf rang # Peking University 53

54 定理 2.3 的证明 ( 续 ) 证 :domf domg dom(f G) 证明 : x, x (domf-domg) (x domf) (x domg) y(<x,y> F) z(<x,z> G) y(<x,y> (F-G)) x dom(f-g) domf domg dom(f G) Peking University 54

55 逆的定义域和值域相关定理定理 2.4 设 F 为任一集合, 则 (1) domf -1 =ranf; (2) ranf -1 =domf; (3) (F -1 ) -1 F, 当 F 为关系时, 等号成立 Peking University 55

56 定理 2.4(1) 的证明 (1) 证明 : x, x domf -1 y{<x,y> F -1 } y{<y,x> F} x ranf domf -1 =ranf # Peking University 56

57 定理 2.4(3) 的证明 (3) (F -1 ) -1 F, 当 F 是关系时, 等号成立. 证明 : (1) 设 F 是关系, 则 <x,y>, <x,y> (F -1 ) -1 x(f -1 ) -1 y yf -1 x xfy. 这时 (F -1 ) -1 = F. 当 F 不是关系时, (F -1 ) -1 F, 例如, 设 F={<b,c>,a}, 则 F -1 ={<c,b>}, (F -1 ) -1 ={<b,c>} F (F -1 ) -1 F. # Peking University 57

58 合成运算的结合律定理 2.5 设 R 1,R 2,R 3 为三个集合, 则 (R 1 R 2 ) R 3 = R 1 (R 2 R 3 ) 证明 : <x,y>, <x,y> (R 1 R 2 ) R 3 z(<x,z> R 3 <z,y> (R 1 R 2 )) z(<x,z> R 3 t(<z,t> R 2 <t,y> R 1 )) z t(<x,z> R 3 <z,t> R 2 <t,y> R 1 ) t( z (<x,z> R 3 <z,t> R 2 <t,y> R 1 )) t(<x,t> R 2 R 3 <t,y> R 1 ) <x,y> R 1 (R 2 R 3 ) (R 1 R 2 ) R 3 = R 1 (R 2 R 3 ) # Peking University 58

59 R3 R2 R1 x z t y Peking University 59

60 合成运算的分配律定理 2.6 设 R 1,R 2,R 3 为三个集合, 则 (1) R 1 (R 2 R 3 )=R 1 R 2 R 1 R 3 ; (2) (R 1 R 2 ) R 3 =R 1 R 3 R 2 R 3 ; (3) R 1 (R 2 R 3 ) R 1 R 2 R 1 R 3 ; (4) (R 1 R 2 ) R 3 R 1 R 3 R 2 R 3. Peking University 60

61 分配律的证明 R 1 (R 2 R 3 )=R 1 R 2 R 1 R 3 证明 : <x,y>, <x,y> R 1 (R 2 R 3 ) z(<x,z> (R 2 R 3 ) <z,y> R 1 ) z((<x,z> R 2 <x,z> R 3 ) <z,y> R 1 ) z((<x,z> R 2 <z,y> R 1 ) (<x,z> R 3 <z,y> R 1 )) z(<x,z> R 2 <z,y> R 1 ) z(<x,z> R 3 <z,y> R 1 ) <x,y> R 1 R 2 <x,y> R 1 R 3 <x,y> (R 1 R 2 R 1 R 3) R 1 (R 2 R 3 )=R 1 R 2 R 1 R 3 # Peking University 61

62 分配律的证明 ( 续 ) R 1 (R 2 R 3 ) R 1 R 2 R 1 R 3 证明 : <x,y>, <x,y> R 1 (R 2 R 3 ) z(<x,z> (R 2 R 3 ) <z,y> R 1 ) z((<x,z> R 2 <x,z> R 3 ) <z,y> R 1 ) z((<x,z> R 2 <z,y> R 1 ) (<x,z> R 3 <z,y> R 1 )) z(<x,z> R 2 <z,y> R 1 ) z(<x,z> R 3 <z,y> R 1 ) <x,y> R 1 R 2 <x,y> R 1 R 3 <x,y> R 1 R 2 R 1 R 3 R 1 (R 2 R 3 )=R 1 R 2 R 1 R 3 # Peking University 62

63 合成的逆运算定理 2.7 设 F,G 为二集合, 则 (F G) -1 =G -1 F -1 证明 : <x,y>, <x,y> (F G) -1 <y,x> F G z(<y,z> G <z,x> F) z(<z,y> G -1 <x,z> F -1 ) <x,y> G -1 F -1 (F G) -1 =G -1 F -1 # Peking University 63

64 G z F (F G) -1 =G -1 F -1 (F G) -1 x y G -1 z F -1 x G -1 F -1 y Peking University 64

65 定理 2.8 定理 2.8 设 R,S,A,B,A 为集合,A, 则 (1)R (A B)=(R A) (R B); (2)R A = {R A A A} ; (3)R (A B)=(R A) (R B); (4)R A = {R A A A} ; (5)(R S) A=R (S A). Peking University 65

66 定理 2.8(2) 的证明 (2) R A = { R A A A}; 证明 : <x,y>, <x,y> (R A) xry x A xry A( A A x A ) A( xry x A A A ) A( <x,y> (R A) A A ) <x,y> { R A A A}. R A = { R A A A} # Peking University 66

67 定理 2.8(4) 的证明 (4) R A = { R A A A}; (A ) 证明 : <x,y>, <x,y> (R A) xry x A xry A(A A x A) A(xRy ( A A x A)) A((xRy A A) (xry x A)) A( (<x,y> R A A) (<x,y> R A)) A( A A (<x,y> R A)) A(A A <x,y> R A) <x,y> { R A A A} R A = { R A A A} # Peking University 67

68 定理 2.8(5) 的证明 (5) (R S) A = R (S A) 证明 : <x,y>, <x,y> ((R S) A) <x,y> (R S) x A z(xsz zry ) x A z(xsz zry x A) z((xsz x A) zry ) z( <x,z> (S A) zry ) <x,y> R (S A) (R S) A = R (S A). # Peking University 68

69 像的运算定理定理 2.9 设 R,S,A,B,A 为集合,A, 则 (1) R[A B]=R[A] R[B]; (2)R[ A] = {R[A] A A} ; (3)R[A B] R[A] R[B]; (4)R[ A] {R[A] A A} ; (5)R[A]-R[B] R[A-B]; (6)(R S)[A]=R[S[A]]. Peking University 69

70 例 2.3 设 R={<x,y> x,y Z y= x }, A={0,1,2}, B={0,-1,-2}. 求 :(1)R[A B] 和 R[A] R[B];(2) 求 R[A]-R[B] 和 R[A-B] 解 :(1) R[A B]=R[{0}]={0} R[A] R[B]={0,1,2} {0,1,2}={0,1,2} (2)R[A]-R[B]={0,1,2}-{0,1,2}= R[A-B]=R[{1,2}]={1,2} # Peking University 70

71 定理 2.9(2) 的证明 (2) R[ A] = { R[A] A A } 证明 : y, y R[ A] x(xry x A) x( xry A( A A x A) ) A( A A x( xry x A ) ) A(A A y R[A]) y { R[A] A A }. R A = { R A A A}. # Peking University 71

72 定理 2.9(4) 的证明 (4) R[ A] { R[A] A A}; 证明 : y, y R[ A] x(xry x A) x(xry A(A A x A)) x A(xRy (A A x A)) A x(xry (A A x A)) (1?) A x(a A (xry x A)) (2?) A(A A x(xry x A)) A(A A y R[A]) y { R[A] A A }. R[ A] { R[A] A A}. Peking University 72

73 定理 2.9(4) 的证明 ( 续 ) (4) R[ A] { R[A] A A}; 证明 : y, y R[ A] x(xry x A) x(xry A(A A x A)) x A(xRy (A A x A)) A x(xry (A A x A)) (1?) A x(a A (xry x A)) (2?) A(A A x(xry x A)) A(A A y R[A]) y { R[A] A A }. R[ A] { R[A] A A}. Peking University 73

74 (1) x A(xRy (A A x A)) A x(xry (A A x A)) (2) A x(xry (A A x A)) A x(a A (xry x A)) 即, 证明 : (1) x ya(x,y) y xa(x,y) (2) r (p q) p (r q) Peking University 74

75 定理 2.9(4) 的证明 ( 续 ) (1) x ya(x,y) y xa(x,y) 证明 : 在任何解释下, 若左 1, 则右 1. Peking University 75

76 多量词 x ya(x,y) y xa(x,y) x ya(x,y) y xa(x,y) x ya(x,y) y xa(x,y) x ya(x,y) y xa(x,y) x ya(x,y) y xa(x,y) Peking University 76

77 定理 2.9(4) 的证明 ( 续 ) (2) r (p q) p (r q) 方法 1: (r (p q)) (p (r q)) 是永真式真值表, 等值演算方法 2: ( 反证 ) 设左 1 且右 0 即 r (p q) 1 且 p (r q) 0. 由 r (p q) 1 得 r=1, p q=1; 由 p (r q) 0 得 p=1, r q=0; 所以 q=0, p q=0, 矛盾! # Peking University 77

78 定理 2.9(5) 的证明 (5) R[A]-R[B] R[A-B]; 证明 : y, y R[A]-R[B] y R[A] y R[B] x(xry x A) x(xry x B) x(xry x A) x( xry x B) x(xry x A) x(xry x B)? x(xry x A x B) x(xry x A-B) y R[A-B]. R[A]-R[B] R[A-B]. # Peking University 78

79 定理 2.9(5) 的证明 ( 续 ) x(xry x A) x(xry x B) x(xry x A x B) 前提 : x(xry x A), x(xry x B) 结论 : x(xry x A x B) Peking University 79

80 定理 2.9(5) 的证明 ( 续 ) 前提 : x(xry x A), x(xry x B) 结论 : x(xry x A x B) 证明 : (1) x(xry x A), 前提 (2) cry c A, 存在指定规则 (3) x(xry x B), 前提 (4) cry c B, 全称指定规则 (5) cry, 由 (2) 得出 (6) c B, (4)(5) 假言推理 (7) cry c A c B, (2)(6) 合取 (8) x(xry x A x B), (7) 存在推广规则. # Peking University 80

81 定理 2.9(6) 的证明 (6) (R S)[A] = R[S[A]]. 证明 : y, y (R S)[A] x( <x,y> (R S) x A ) x( z( xsz zry ) x A ) z( zry x( xsz x A ) ) z( zry z S[A]) y R[S[A]]. (R S)[A] = R[S[A]]. # Peking University 81

82 小结有序对卡氏积二元关系相关的基本概念二元关系相关的运算基本概念和运算相关的定律 Peking University 82

83 P53: 1 P54: 6, 7(1), 9, 11(2,4,5),12 Peking University 83

untitled

untitled 8.1 f G(f) 3.1.5 G(f) f G(f) f = a 1 = a 2 b 1 = b 2 8.1.1 {a, b} a, b {a} = {a, a}{a} 8.1.2 = {{a}, {a, b}} a, b a b a, b {a}, {a, b}{a} {a, b} 8.1.3