第7章-二元关系.pptVIP

例题 例题 设A={a,b,c}，试给出A的一个二元关系R，使其同时不满足五个性质。 分析 因为关系的各种性质的存在，都要求满足一定的条件，要做的就是创造或破坏这些条件。 从A×A出发，通过删除某些序偶，使其不满足那些性质。 解答 令R＝{a,a,b,b,b,c,c,b,c,a} c,c?R 不满足自反性 a,a∈R 不满足反自反性 c,a∈R ∧ a,c?R 不满足对称性 b,c∈R∧c,b∈R∧b≠c 不满足反对称性 b,c∈R∧c,a∈R∧b,a?R 不满足传递性 习题 设R＝{x,y|x,y∈N 且 x+3y＝12} (1)求R的集合表达式 (2)求 dom R， ran R (3)求R?R (4)求R↑{2,3,4,6} (5)求R[{3}] (6)R3 解答： {0,4,3,3,6,2,9,1,12,0} {0,3,6,9,12}， {0,1,2,3,4} {3,3,12,4} {3,3,6,2} {3} {3,3} 习题 设R是复数集合C上的关系，且满足xRy?x-y＝a+bi，a和b为给定的非负整数，试确定R的性质并证明之。 解答 （1）当a＝b＝0时，满足自反性、对称性、反对称性和传递性，不满足反自反性。 （2）当a、b不全为0时，只满足反自反性、反对称性。 习题 例题 设I为整数集，R＝{x,y|x≡y(mod k)}，证明R是等价关系。 证明 设任意a,b,c∈I (1)因为a－a＝0，所以a,a∈R。 (2)若a≡b(mod k)，a－b＝kt(t为整数)，则 b－a＝-kt，所以b≡a(mod k)。 (3)若a≡b(mod k)，b≡c(mod k)，则 a－b＝kt，b－c＝ks(t和s为整数)， a－c＝a－b＋b－c＝kt＋ks＝k(t＋s)， 所以a≡c(mod k) 因此，R是等价关系。 作业 习题七： 书本上：1、4、12、32、46 作业本上：13、14、16、22、26、31、39、42、48  * * 一个计算机网络在波士顿、芝加哥、丹佛、底特律、纽约和圣地亚哥设有数据中心。从波士顿到芝加哥、波士顿到底特律、芝加哥到底特律、底特律到丹佛和纽约到圣地亚哥，都有单向的电话线。如果存在一条从数据中心a到b的电话线，a,b就属于关系R。我们如何确定从一个中心是否有一条电话线(可能不直接)链接到另一个中心？由于所有的链接不一定是直接的，例如从波士顿可通过底特律到丹佛，因此不能直接使用R来回答这个问题。用关系的语言说，R是不传递的，因而它不包含可能链接的所有的对。正如我们将要讲述的，可以通过构造包含R的最小的传递关系来找出每一对有着联系的数据中心，这个关系叫做R的传递闭包。 定理7.14 （4）∪{[x]|x∈A}＝A。 先证 ∪{[x]|x∈A}?A 任取y，y∈∪{[x]|x∈A} ? ?x(x∈A∧y∈[x])  ? y∈A (因为[x]?A) 从而有∪{[x]|x∈A}? A。 再证 A?∪{[x]|x∈A} 任取y，y∈A ? y∈[y]∧y∈A   ? y∈∪{[x]|x∈A} 从而有A?{[x]|x∈A}成立。 综上所述得 ∪{[x]|x∈A}＝A。 商集 定义7.17 设R为非空集合A上的等价关系，以R的所有等价类作为元素的集合称为A关于R的商集(quotient set)，记做A/R，即 A/R={[x]R|x∈A} 例7.16中的商集为 {{1,4,7},{2,5,8},{3,6}} 整数集合Z上模n等价关系的商集是 {{nz+i|z∈Z}|i=0,1,…,n-1} 划分 定义7.18 设A为非空集合，若A的子集族π(π?P(A)，是A的子集构成的集合) 满足下面的条件： （1）??π （2）?x?y(x,y∈π∧x≠y→x∩y＝?) （3）∪π=A 则称π是A的一个划分(partitions)，称π中的元素为A的划分块。 说明 设集合π是A的非空子集的集合，若这些非空子集两两不相交，且它们的并等于A，则称π是集合A的划分。 例7.17 例7.17 设A＝{a,b,c,d}，给定π1,π2,π3,π4,π5,π6,如下：π1={{a,b,c},{d}}π2={{a,b},{c},{d}}π3={{a},{a,b,c,d}}π4={{a,b},{c}}π5={?,{a,b},{c,d}}π6={{a,{a}},{b,c,d}}判断哪一个是A的划分 π1和π2是A的划分，其它都不是A的划分。 因为π3中的子集{a}和{a,b,c,d}有交，∪π4≠A，π5中含