11
河南工业大学离散数学课程组
四.证明R的反对称性 方法1 用定义1证： 任取 x,y∈A,设<x,y>∈R, <y,x>∈R.证出 x=y。 方法2 用定义2证： 任取 x,y∈A,x≠y, 设<x,y>∈R,证出<y,x>R. 方法3 用定理证：证出 R∩Rc IA . (见教材P118) 五.证明R的传递性： 方法1 用传递定义证： 任取 x,y,z∈A,设<x,y>∈R,<y,z>∈R, 证出 <x,z>∈R. 方法2 用传递闭包证：证出 t(R)=R, 即 R∪R2∪R3∪... =R. 方法3 用定理证：证出R R R ( P119 (2) a) ) 下面证明第113页 (4)
河南工业大学离散数学课程组
离散数学
河南工业大学 第三章
信息科学与工程学院
集合与关系
1
河南工业大学离散数学课程组 3-2（9）在什么条件下，下面命题为真？
a) (A-B)∪(A-C)=A (A-B)∪(A-C)= (A∩~B)∪(A∩~C)=A∩(~B∪~C) = A∩~(B∩C)=A-(B∩C)=A 所以满足此式的充要条件是： A∩(B∩C)= Φ或A ~ (B∩C) b) (A-B)∪(A-C)=Φ (A-B)∪(A-C)= A∩~(B∩C)= A-(B∩C)=Φ 所以满足此式的充要条件是：A B∩C c) (A-B)∩(A-C)=Φ (A-B)∩(A-C)= (A∩~B)∩(A∩~C)=A∩(~B∩~C) = A∩~(B∪C)=A-(B∪C)=Φ 所以满足此式的充要条件是: A B∪C d) (A-B)(A-C)=Φ 因为 当且仅当A=B ，才有AB=Φ 所以满足此式的充要条件是: A-B=A-C
5
河南工业大学离散数学课程组
第109页⑴ X={a,b,c} Y={s} X到Y的所有关系： X×Y={<a,s>,<b,s>,<c,s>} X×Y的任何一个子集都是一个 从X到Y的关系。如 果|X|=m |Y|=n则有2mn个从X到Y的关系, 故,有23=8 个关系: R0=Φ R1={<a,s>} R2={<b,s>} R3={<c,s>} R4={<a,s>,<b,s>} R5={<a,s>,<c,s>} R6={<b,s>,<c,s>} R7={<a,s>,<b,s>,<c,s>} ⑵ 设|A|=n ，有多少个A上的关系？ 因为RA×A,所以A×A有多少个子集就有多少个A上 关系,由集合的幂集就是该集合的子集构成的,所以A 上关系个数就是A×A 的幂集P(A×A)的元素个数 |P(A×A)|,而 2|A×A|=2nn= 2n 。所以有 2n 个不同的A上 关系。
19
河南工业大学离散数学课程组 P134(4). R是A上关系，
设 S={<a,b>|c∈A∧<a,c>∈R∧<c,b>∈R} 求证若R是等价关系，则S也是等价关系。 证明： a)证S自反：任取a∈A，∵R是自反的， ∴有<a,a>∈R,由 S定义得<a,a>∈S, (S定义中c就是a) ∴S自反。 b)证S对称: 任取a,b∈A，且有<a,b>∈S,由S定义得 c∈A∧<a,c>∈R∧<c,b>∈R, 由R对称得 c∈A∧<b,c>∈R∧<c,a>∈R,由S定义得<b,a>∈S, S对称。 c)证S传递:任取a,b,c∈A,有<a,b>∈S,<b,c>∈S, 由S定义得(d∈A∧<a,d>∈R∧<d,b>∈R)∧ (e∈A∧<b,e>∈R∧<e,c>∈R) , 由于R传递,所以有<a,b>∈R,<b,c>∈R,由S定义得 <a,c>∈S, 所以S传递. 所以S是A上等价关系。 20
4
河南工业大学离散数学课程组
第104页⑴b) A={0,1} B={1,2} 求A2×B。 AB={<x,y>|xA∧yB} A2 =A×A={<0,0>,<0,1>,<1,0>,<1,1> } A2×B={<<0,0>,1>,<<0,1>,1>,<<1,0>,1>,<<1,1>,1>, <<0,0>,2>,<<0,1>,2>,<<1,0>,2>,<<1,1>,2> } 注意： A2×B= (A×A)×B= A×A×B 第105页 ⑵设A={a,b},构成集合P(A) ×A P(A)={Φ,{a},{b},{a,b}} P(A) ×A={< Φ,a>, < Φ,b>, < {a},a>, <{a},b>, < {b},a>, <{b},b>, < {a,b},a>, <{a,b},b>
河南工业大学离散数学课程组
五.证明R的传递性： 方法1 用传递定义证：任取 x,y,z∈A, 设<x,y>∈R∩S,<y,z>∈R∩S, (证出<x,z>∈R∩S) <x,y>∈R∩S∧<y,z>∈R∩S <x,y>∈R∧<x,y>∈S∧<y,z>∈R∧<y,z>∈S (<x,y>∈R∧<y,z>∈R)∧(<x,y>∈S ∧<y,z>∈S) <x,z>∈R∧<x,z>∈S （因为R、S传递） <x,z>∈R∩S 所以R∩S传递。 方法2 用传递闭包证：证出 t(R∩S)=R∩S, 即 (R∩S)∪(R∩S)2∪(R∩S)3∪... =R∩S. 方法3用定理证：证出 (R∩S) o (R∩S) (R∩S) 用方法2、方法3证明此题的传递性有很大难度。 R(S∩T)(RS)∩(RT) 希望同学们灵活掌握证明关系性质的方法。
设R是A上关系， 一.证明R的自反性： 方法1 用自反定义证：任取 x∈A,证出<x,x>∈R. 方法2 用恒等关系IA证：证出IA R. ( P119 (2) b) ) 方法3 用自反闭包证：证出r(R)=R, 即R∪IA=R. 二.证明R的反自反性： 方法1 用反自反定义证：任取 x∈A,证出<x,x>R。 方法2 用R∩IA=Φ证 三.证明R的对称性： 方法1 用对称定义证： 任取 x,y∈A,设<x,y>∈R, 证出 <y,x>∈R. 方法2 用求逆关系证：证出 Rc=R. 方法3 用对称闭包证：证出 s(R)=R, 即R∪Rc =R.
2 2
6
河南工业大学离散数学课程组
P109 3-5（5）
注意：A上的关系，结点数为A中元素的个数。
7
河南工业大学离散数学课程组
第113页⑴ A={1,2,3}，A上五个关系如下：
1 1 1 1 1
。 。 。 。 。 。 。 。 。 。 。 。 。 。 。 2 3 2 3 2 3 2 3 2 3 A×A T
3
河南工业大学离散数学课程组
3-2（5）b)证明 (A-B)-C=(A-C)-B x： x∈(A-B)-C x∈(A-B)∧xC (x∈A∧xB)∧xC (x∈A∧xC)∧xB x∈(A-C)∧xB x∈(A-C)-B 所以(A-B)-C=(A-C)-B
(A-B)-C =(A∩~B)∩~ C = (A∩~C)∩~ B =(A-C)-B 所以(A-B)-C=(A-C)-B
12
河南工业大学离散数学课程组 P113(4)R和S都A上是自反、对称、传递的，求证R∩S也
是自反、对称和传递的。
证明：一.证明R∩S的自反性 方法1 用自反定义证：任取 x∈A, (证出<x,x>∈R∩S) 因R和S都自反，所以有<x,x>∈R，<x,x>∈S， 于是有<x,x>∈R∩S，所以R∩S也自反。 方法2 用恒等关系IA证：(证出IA R∩S) 因R和S都自反，所以 IA R ，IA S， 所以 IA R∩S 所以R∩S也自反。 方法3 用自反闭包证： (证出r(R∩S)=R∩S, 即 (R∩S)∪IA= R∩S) 因R和S都自反，所以r(R)=R, r(S)=S, r(R∩S)=(R∩S)∪IA= (R∪IA)∩(S∪IA) = r(R)∩r(S)=R∩S
R S Φ R S T Φ
A×A
自反 N Y N N Y
反自反 N N N Y N
对称 N Y N Y Y
反对称 Y N Y Y N
传递 Y Y N Y Y
8
河南工业大学离散数学课程组
上述五个关系中， 哪些是等价关系？如果是等价关系，求其商集。 哪些是相容关系？如果是相容关系，求其完全覆盖。 哪些是偏序关系？如是偏序关系,画Hasse图,并求Ａ的极 小(大)元、最小(大)元、上界与下界、上确界和下确界。 等价关系：S和A×A，对应的商集分别是： A/S={{1,2},{3}} A/A={{1,2,3}} 相容关系: S和A×A，对应的完全覆盖分别是： CS(A)={{1,2},{3}} CA×A(A)={{1,2,3}} 偏序关系: T 3。 Ａ的极小元、最小元、下界、下确界都是：1 Ａ的极大元、最大元、上界、上确界都是：3 2。 1 1。
18
河南工业大学离散数学课程组
第130页(1).X是集合，且|X|=4，X有多少个不同的划分？ 解.