离散数学习题答案-2015(3)

（2） A⊕B=A⊕C

答：能，因为A⊕A = Φ,Φ⊕A = A⊕Φ=A,同时，（A⊕B）⊕C = A⊕（B⊕C） 所以，已知等式两端 A⊕A⊕B= A⊕A⊕C ?Φ⊕B =Φ⊕C ? B=C

16、求A={?, a, {b}}的幂集

A

解：2 = {?, {?} , {a} , {{b}} , {?,a} , {?,{b}} , {a, {b}} , {?, a, {b}}}

17、设A,B是任意两集合，证明

ABA B

（1）2 ? 2 ? 2 ?，给出等号成立的条件

ABAB

证明：X ? 2 ? 2 ? X ? 2 ? X ? 2 ? X ? A ? X ? B => X ? A ? B

A B

? X ? 2 ? 等号成立的条件: A ? B或B ? A

A B

(因为若A和B没有子集关系, 必有a ?A– B和 b ?B– A，使{a, b} ? 2 ? ，但{a,

AB

b} ? 2 ? 2 )

ABA B

（2）2? 2 = 2 ?

ABAB

证明：X ? 2? 2 ? X ? 2 ? X ? 2 ? X ? A ? X ? B ? X ? A ? B

A B

? X ? 2 ?

附加题：

证明等式(A⊕B) ⊕C = A⊕(B⊕C)

证明：A⊕(B⊕C) = A⊕((B-C)∪(C-B)) = (A - ((B-C)∪(C-B))) ∪(((B-C)∪(C-B))- A) = ~AB~C + ~A~BC + A~B~C + ABC (A⊕B) ⊕C = C⊕(A⊕B)

那么按上式的划简方式，就是把C替换为A, 把A替换为B,将B替换为C,所以 C⊕(A⊕B) = ~CA~B + ~C~AB + C~A~B + CAB = ~AB~C + ~A~BC + A~B~C + ABC

习题四

1、设A={1,2,3,4},B={0,1,4,9,12}.分别把下面定义的从集合A到集合B的二元关系R用序偶的集合表示出来

（1）xRy ?x|y

解: R = {(1,0) ,(1,1),(1,4) ,(1,9) ,(1,12) ,(2,0) ,(2,4) ,(2,12) , (3,0) ,(3,9) ,(3,12) ,(4,0) ,(4,4) ,(4,12)} （2）xRy ? x?y(mod 3)

解: R = {(1,1), (1,4) , (3,0) , (3,9) , (3,12) , (4,1) , (4,4)} （3）xRy ? y/x ? ∟(y-x)/2」

解: R = {(3,9), (3,12) , (4,9) , (4,12)}

2、用关系图和关系矩阵表示第1题中的各个关系

解：略

6、设在整数集Z上定义如下二元关系，试填写下表：

解：填表如下

R x|y x≡y(mod m) xy>0 xy≧0 x=y或|x-y|=1 x> y 22自反性 √ √ × √ √ × 反自反性 × × × × × √ 对称性 × √ √ √ √ × 反对称性 × × × × × √ 传递性 √ √ √ × × √ (1) 因为x|x成立，所以自反性成立；所以反自反性不成立；因为x≠0时，x|0成立，但

0|x不成立，所以对称性不成立，因为 1|-1，和-1|1成立，所以反对称性不成立；但x|y,y|z成立，就一定有x|z成立，所以传递性成立

(2) 因为模m相等是整数集合上的等价关系，所以具有自反、对称、传递性

(3) 因为00 = 0，所以自反性不成立；因为x ≠ 0时必有 xx>0,所以反自反性不成立；因

为xy >0 必有yx>0,所以对称性成立；因此反对称性不成立；因为xy>0,yz>0,能得到x,y,z同号且不为0，所以，xz>0,所以传递性成立

(4) 因为xx≧0,所以自反性成立；因此，反自反性不成立；因为xy≧0,所以yx≧0，因此对

称性成立；因此，反对称性不成立；因为-1*0 ≧0，0*1≧0，但-1*1 < 0,所以传递性不成立

(5) 因为 x=x，所以自反性成立；因此反自反性不成立；因为|x-y|=1，所以| y-x |=1，因

此对称性成立；所以反对称性不成立；因为|1-2|=1，|2-3|=1，但|1-3|=2，所以传递性不成立

22 22

因为 xx = xx，所以自反性不成立；反自反性成立；因为x> y成立，那么y> x就不成立，所以对称性不成立，反对称性成立；传递性成立

7、设R是集合A上的一个二元关系，合于xRy ∧ yRz => ~xRz,称R是A上的一个反传递关系。试举一个实际的反传递关系的例子

解：例如在人群集合上，建立父子关系，那么就是一个反传递关系，因为如果 甲是乙的父亲，乙是丙的父亲，那么甲和丙就一定不存在父子关系；另外，在正整数域上建立的倍数关系，也是一个反传递关系，因为如果 a 是 b的2倍，b是c的2倍，那么a 一定不是c的2倍

8、设R和S都是集合A上的二元关系，它们经过关系运算后得到A上的一个新关系。试判别当R和S同时具有下表左列某种指定性质时，经过指定的运算后所得到新关系也仍保持这种性质，把所得结论以√，×的形式填在下表中相应的位置上 自反性 反自反性 对称性 反对称性 传递性 R∩S √ √ √ √ √ R∪S √ √ √ × × R-S × √ √ √ × R○S √ × × × × -R × × √ × × R √ √ √ √ √ -1（1） 自反性的保持情况说明： 因为R,S都具有自反性，所以IA?R, IA?S，

因此IA?R∩S, IA?R∪S,所以自反性在R∩S，R∪S上保持

因为IA?S，所以IA不是S补集的子集，因此也不是R∩-S的子集，所以自反性在R-S上不保持

因为R,S是自反的，所以对任意的a ∈A，（a,a）∈R,S，所以（a,a）∈R○S，因此自反性在R○S上保持

因为（a,a）∈R，所以（a,a）不属于-R,所以-R不具有自反性

-1-1

因为（a,a）∈R，所以（a,a）∈R，因此R具有自反性 （2） 反自反性的保持情况说明：

因为R,S都具有反自反性，等价于 IA∩R = Φ, IA∩S = Φ

因为IA∩R∩S =Φ，IA∩（R∪S）=Φ，所以R∩S，R∪S都是反自反的 因为IA∩R∩-S =Φ，所以 R-S也是自反的

对于R○S，假设（a,b）∈R,（b,a）∈S, 那么（a,a）∈R○S, 所以反自反在R○S上不一定保持

因为（a,a）不属于R，所以（a,a）一定属于-R，所以-R一定是自反的，一定不是反自反的

-1-1

因为（a,a）不属于R，所以（a,a）也不属于R，因此R一定是反自反的 （3） 对称性的保持情况说明：

-1-1 -1-1-1-1

因为R,S是对称的，所以R= R,S= S，-R = (-R)= -R, -S = (-S)= -S

-1-1-1

因为（R∩S）= R ∩ S= R∩S, 所以R∩S具有对称性

-1-1-1

因为（R∪S）= R ∪ S= R∪S, 所以R∪S具有对称性

-1-1-1-1-1-1

因为（R-S）= （R∩-S）=R ∩ （-S）= R ∩ -S = R∩-S，所以R-S具有对称性

-1-1-1

因为(R○S) = S ○ R= S○R ,但S○R通常情况下与R○S不相同，所以对称性不一定保持，例如：R = {(a,b),(b,a)}, S = {(b,c),(c,b)},则R○S = {（a,c）},并不对称

-1-1

因为（-R） = -R= -R，所以R的补是对称的

因为 R逆的逆就是R，既等于R的逆，所以R的逆是对称的 （4） 反对称性的保持情况说明：

-1-1

因为R,S是反对称的，所以R∩ R? IA S∩ S? IA

-1 -1-1

因为（R∩S）∩（R∩S）= （R∩R）∩（S∩S）? IA ，所以R∩S具有反对称性

因为如果R = {(a,b)} S = {(b,a)},都是反对称的，但 R∪S = {(a,b),(b,a)}是对称的，所以R∪S不一定再保持对称性

因为R是反对称的，而R-S在R的基础上减少集合元素，因此也一定是反对称的 因为如果 R = {(a,b),(c,a)}, S = {(b,c),(a,a)}, 那么R○S = {（a,c），（c,a）},变为对称的，所以反对称性，在复合运算下不一定保持

因为如果R = {（a,b）,(c,c)}是反对称的，但-R = {（a,a）,(b,b),(b,a),(a,c,),(c,a),(b,c),(c,b)},不是反对称的，所以反对称性在补集运算上不保持

-1-1-1-1

因为R∩ R? IA，有因为 R = (R),所以R是反对称的 （5） 传递性的保持情况说明：

22

因为R,S是传递的，所以R?R, S?S

222

因为（R∩S） = （R∩S）○（R∩S）? R∩S∩(R○S)∩(S○R) ? R∩S，所以传递性保持

如果R = {(a,b)}, S={(b,c)},都是传递关系，但R∪S = {(a,b),(b,c)}不再是传递关系，所以传递性在R∪S上不一定保持

如果R={(a,b),(b,c),(a,c)},S={(a,c)},分别是两个传递关系，但R-S = {(a,b),(b,c)}不再是传递关系，所以传递性在R-S上不一定保持

如果R={(a,b),(c,d)},S={(b,c),(d,e)}, 分别是两个传递关系，但R○S = {(a,c),(c,e)}不再是传递关系，所以传递性在R○S上不一定保持

如果A = {a,b,c}, R = {(a,b)}, 那么 –R = A ×A – R,显然不是传递的，所以传递性在-R上不一定保持

22-1-1-12-1

因为R?R，所以 （R）?R ，即（R）?R，所以传递性在逆运算下保持

10、设R是集合A上的一个二元关系，证明

（1）R是自反的 ? IA?R 证明:

R是自反的 => IA?R

因为，R是自反的，所以对任意的A中元素a，有（a,a）∈R，即IA中任意元素都属于R，所以IA?R

IA?R => R是自反的

因为，对任意的A中元素a，有（a,a）∈IA，又IA?R，所以（a,a）∈R，所以R是自反的 综上所述，R是自反的 ? IA?R （2）R是反自反的 ? IA∩R = Φ 证明：

R是反自反的 => IA∩R = Φ

因为，IA中的任意元素(a,a)，都不属于R，所以IA∩R = Φ IA∩R = Φ=> R是反自反的 因为IA∩R = Φ，所以IA中的任意元素(a,a)，都不属于R，即对任意的A中元素a，有（a,a）∈IA，都不属于R，所以R是反自反的

综上所述，R是反自反的 ? IA∩R = Φ

-1

（3）R是对称的 ? R = R 证明：

-1

R是对称的 => R = R

-1

因为对R中的任意元素（a,b）,因为R是对称的，所以（b,a）∈R，那么（a,b）∈R,所以

-1

R? R

-1

因为对R中的任意元素（a,b）,那么（b,a）∈R，因为R是对称的，那么（a,b）∈R,所以-1

R? R

-1

所以 R = R

-1

R = R => R是对称的

-1-1

对R中的任意元素（a,b），因为R = R ,所以（a,b）也属于R，所以（b,a）∈R，因此R是对称的

-1

综上所述，R是对称的 ? R = R

-1

（4）R是反对称的 ? R∩R?IA 证明:

-1

R是反对称的 => R∩R?IA

-1-1

因为对任意(a,b) ∈R∩R ,那么其就同时属于R和R ，那么（b,a）也属于R，根据反对

-1

称的定义，a = b，所以（a,b）∈IA ,所以R∩R?IA

-1

R∩R?IA => R是反对称的

假设R不是反对称的，那么必定存在 a ≠b∧(a,b) ∈R ∧ (b,a) ∈R，那么（a,b）∈R-1

∩R ,但（a,b）不属于IA，矛盾；因此R必是反对称的

-1

综上所述，R是反对称的 ? R∩R?IA

2

（1） R是传递的 ? R?R 证明：

2

R是传递的 => R?R

2

因为对任意（a,b）∈R,必存在c，使得（a,c）,(c,b)属于R，因为R是传递的，所以(a,b)

2

属于R，因此R?R 2

R?R => R是传递的

2

因为对任意的R中的元素（a,b），(b,c)，那么(a,c)必定属于R,也就属于R，所以R是传递的

2

综上所述，R是传递的 ? R?R

11、设A={1,2,3,4},定义A上的关系 R = {(a,b)|a=b+2},S = {(x,y)|y=x+1∨x=2y} 求：

-12-12

R。S,R。S。R,R,(S)

解：根据题意，R={(3,1),(4,2)}，S={(4,2),(1,2),(2，3)，（3，4）} 所以：R。S = {（3，2），（4，3）}

-1

S = {（2，4），（2，1），（3，2），（4，3）}

-1

所以：R。S = {(4,4),(4,1)}

-1

R。S。R = {(4,2)}

2

R = ?

-12

(S) = {(2,3),(3,4),(3,1),(4,2)}

mn

12、设A={a,b,c,d,e,f,g,h}，A上的二元关系R对应的关系图4-5所示，求使R=R的最

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库离散数学习题答案-2015(3)在线全文阅读。