离散数学复习资料(2)

??

晓津证明如下：

右边=((A∩B)∪(A∩C)) ∩ ～((A∩B)∩(A∩C))

=(A∩(B∪C))∩～(A∩(B∩C)) =(A∩(B∪C))∩(～A∪～(B∩C))

=((A∩(B∪C))∩～A)∪(A∩(B∪C)∩～(B∩C)) =Φ∪(A∩(B∪C)∩～(B∩C)) =A∩(B C) =左边 证毕

我想，有时候从右边化到左边会更简便些吧。 b)、 A∪(B C)=(A∪B) (A∪C)，不一定成立。 ??

晓津证明如下:设有集合A={1,2,3} B={4,5} C={5,6}

则A∪(B C)={1,2,3,4,6} 且 (A∪B) (A∪C)={1,2,3,4,6} 左右相等。等式成立。 又设有集合A={1,2,3,5} B={4,5} C={5,6}则

则A∪(B C)={1,2,3,4,5,6} 而 (A∪B) (A∪C)={1,2,3,4,6}

左右不等，因此证得原式不一定成立。 3.3

习题答案

题号：1 2 3 4 5 6 7

1、设A={0,1},B={1,2},确定下面集合。 a) A×{1}×B

={<0,1>,<1,1>}×{1,2}

={<<0,1>,1>,<<1,1>,1>,<<0,1>,2>,<<0,1>,2>} b) A2×B

={<0,1>,<0,2>,<1,1>,<1,2>}×{1,2}

={<<0,1>,1>,<<0,1>,2>,<<0,2>,1>,<<0,2>,2>,<<1,1>,1>,<<1,1>,2>,<<1,2>,1>,<<1,2>,2>} c) (A×B)2

={<0,1>,<0,2>,<1,1>,<1,2>}2

={<<0,1>,<0,1>>,<<0,1>,<0,2>>,<<0,1>,<1,1>>,<<0,1>,<1,2>>, <<0,2>,<0,1>>,<<0,2>,<0,2>>,<<0,2>,<1,1>>,<<0,2>,<1,2>>, <<1,1>,<0,1>>,<<1,1>,<0,2>>,<<1,1>,<1,1>>,<<1,1>,<1,2>>, <<1,2>,<0,1>>,<<1,2>,<0,2>>,<<1,2>,<1,1>>,<<1,2>,<1,2>>}

2、下列各式中哪些成立？哪些不成立？为什么？ a) (A∪B)×(C∪D)=(A×C)∪(B×D)

不成立，因为笛卡尔积中。在左半式中，x的成分在A与B两个集合中，而右半式中，x的成分在A与C两个集合中。

b) (A-B)×(C-D)=(A×C)-(B×D)

不成立，比如设A与B中都含有含有元素 a 。在左半式中，a是不会出现在 x 中。假设

(A×C)出现(a,b),(a,e),而(B×D)出现了(a,b),(a,d)，那么(a,e)将被保留下来，从而 左半式 不等于 右半式。 c) (A B)×(C D)=(A×C) (B×D)

不成立。因为左半式 x不可能含有

A∩B的成分，而在右半式 x 就包含有A∩B的成分。

6

d) (A-B)×C=(A×C)-(B×C)

成立，因为左半式 x 不会出现B的成分，而右半式中 x 包含有 B的成分，也会被过滤掉的。 e) (A B)×C=(A×C) (B×C)

成立。左半式中 x 不会出现 A∩B 的成分，而右半式中A∩B也会被过滤掉的。 d)证明：(1)设任意的＜x，y＞?(A－B)×C ∴x?(A－B)∧y?C ∴x?A∧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)

(2)设任意的＜x，y＞?(A×C)－(B×C)； 则＜x，y＞?(A×C)∧＜x，y＞ (B×C) ∴x?A∧y?C∧(x B∨y C)

∴x?A∧((y?C∧x B)∨(y?C∧y C)) ∴x?A∧y?C∧x B ∴(x?A∧x B)∧y?C ∴x?(A－B)∧y?C ∴＜x，y＞?(A－B)×C

∴(A×C)－(B×C) (A－B)×C ∴(A－B)×C=(A×C)－(B×C)

e)(A B)×C＝((A－B)∪(B－A))×C

＝((A－B)×C))∪((B－A)×C) ＝(A×C－B×C)∪(B×C－A×C) ＝(A×C) (B×C)

3、证明若 X×Y=X×Z,且 X≠φ，则 Y=Z 证明： X×Y={| x?X,y?Y}

X×Z={| x?X,z?Y}

如果 X=φ 那么 X×Y=φ X×Z=φ 因为

X≠φ，所以 Y=Z

4、设 X={0,1,2,3,4,5,6},上关系为 R={

}(x

}(x,<0,2>,<0,3>,<0,4>,<0,5>,<0,6>, <1,2>,<1,3>,<1,4>,<1,5>,<1,6>, <2,3>,<2,4>,<2,5>,<2,6>, <3,4>,<3,5>,<3,6>, <4,5>,<4,6>, <5,6>, }

晓津补充：若按jhju的讨论来做，应把红色三行去掉，0和1、4都不是质数,相应的，在下面的答案里，也应把红色字去掉。

domR= {0,1,2,3,4,5}

7

ranR= {1,2,3,4,5,6} FLDR= {0,1,2,3,4,5,6}

5. 设 P={<1,2>,<2,4>,<3,3>} Q={<1,3>,<2,4>,<4,2>} 求出

P∪Q，P∩Q,domP,domQ,ranP,ranQ,dom(P∩Q),ran(P∩Q) 解： P∪Q={<1,2>,<1,3>,<2,4>,<3,3>,<4,2>} P∩Q={<2,4>} domP={1,2,3} domQ={1,2,4} ranP={2,4,3} ranQ={2,4,3} dom(P∩Q)={2} ran(P∩Q)={4} 6、设 A={1,2,3,4},定义A上二元关系R：R,iff(a-b)/2是整数，称R为模2同余系，亦可称?R,iffa≡b(mod2),求出R的序偶表达式， domR，ranR.

解： R={<4,2>,<3,1>,<2,4>,<1,3>} domR={4,3,2,1} ranR={2,1,4,3}

7、设A={1,2,3,4,5,6,7,8,9,10} R={ |

x,y?A∧x是y的因子∧x<=5},求 domR,ranR 解： R={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>，

<1，6><1，7>，<1，8>，<1，9>，<1，10>， <2,2><2,4>,<2,6>,<2,8>,<2,10>, <3,3>,<3,6>,<3,9>, <4,4>,<4,8>, <5,5>,<5,10>}

domR={1,2,3,4,5}

ranR={1,2,3,4,5,6,7,8,9,10}

3.4节习题答案

1、给定A={1,2,3,4},考虑A上的关系R,若R={<1,3>,<1,4>,<2,3>,<2,4>,<3,4>}, a) 在A×A的坐标图上标出R，并给出关系图。 b) R是自反的？对称的？可传递的?反对称吗？ 解：我以表格形式表示坐标： 关系图如下：

由图中可见，R不是自反的，不是对称的，是可传递的，是反对称的。 2、举出A={1,2,3}上关系R的例子，使它有下列性质。 a) 既是对称的又是反对称的。

b) R既不是对称的，又不是反对称的； c) R是可传递的。 解：a)R={<1,1>}

b)R={<1,3>,<2,3>,<3,1>} c)R={<1,2>,<2,3>,<1,3>}

3) 说明下列关系是否是自反的，对称的，传递的或反对称的。 a) 在 {1,2,3,4,5}上定义的关系。

8

{

| a-b 是偶数}。

b) 在 {1,2,3,4,5}上定义的关系。 { | a+b 是偶数 }。

c) 在所有人集合P上的关系， { | a,b 是同一祖先 } 解：a)先列出其关系集合如下： R={<1,1>，<1，3>,<1,5>, <2,2>,<2,4>,

<3,3>,<3,5>,<3,1>, <4,4>,<4,2>,

<5,5>,<5,3>,<5,1>}

由此可看出：A上关系R为自反的，对称的，传递的但不是反对称的。 b)仍列出其关系集合：我们发现它和上面的集合是一样的： R={<1,1>，<1，3>,<1,5>, <2,2>,<2,4>,

<3,3>,<3,5>,<3,1>, <4,4>,<4,2>,

<5,5>,<5,3>,<5,1>}

可知：A上关系R也是自反的，对称的，传递的但不是反对称的。。

c)这个集合不便列举，就拿一个家庭来举例吧，家里有5个人，老爸x,老妈y,哥哥z,姐姐u,我v,则列出 R={,,,, ,,,,,}

4、如果关系R和S是自反的、对称的和可传递的，证明 R∩S也是自反的、对称和可传递的。 证明：设有任意x,y,有?R 且?S

因为 R是自反的,则有,?R,又因为S是自反的，则有,?S 所以 ,?(R∩S) 即R∩S是自反的。 因为 R和S都是对称的，则有?R

且?S因此 ?R∩S 即R∩S是对称的。

再设有任意z,因为R是可传递的，则当xRy且yRz时必有xRz,同样当xSy且ySz时必有xSz,即有：,，?R∩S

所以R∩S是可传递的。

5、设 S={|对任一C有?R,?R},其中R是二元关系，证明若R是自反、对称和传递的，则S也是自反的、对称和传递的。

证明：因为对于任一c有?R且?R，若R是自反的，则有,,?R 因为?S

即有，?S，因此S是自反的。

若R是对称的和传递的，则由?R,?R

必有?R，同时有，?R则必有?R 所以S是对称的，也是传递的。 6、设Z是整数集 R={

因为a-a=K?0,即a≡a(mod K)成立 ?R，故R是自反的。 设a-b=Kt(t为整数)，则b-a=-Kt 所以b≡a(mod

K)成立，?R,故R是对称的。 若?R且?R，即 a≡b(mod K)

9

且b≡c(mod K)

a-b=Kt b-c=Ks( t,s 为整数) 则 a-c=Kt+Ks=K(t+s) 所以a≡c(mod K)

即?R，故R是传递的。

7、设R是集合X上的一个自反关系。求证R是对称和传递的，当且仅当,在R中，且有在R中。 证明：充分性：设任意a,b,c?X，

因为R是自反关系，则,,?R，当有,,?R时....我发现充分性无法证明。

必要性：要使R为对称的，则对任意a,b?X，必须有,?R，要使R为传递的，对任意a,b,c?X 若有,?R

必要有?R，所以应有,,,在R中。

(实际上对于此题，少给出一个或或在R中的条件，故导致充分性不足。 所以

此题我没能证出来。 3.5习题答案

1、设： A={1,2,3}上关系R={| x?y}，试求： R-1, ~R 解： R={<1,1>,<1,2>,<1,3>,(2,2>,<2,3>,<3,3>} R-1={<1,1>,<2,1>,<3,1>,<2,2>,<3,2>,<3,3>} ~R={<2,1>,<3,1>,<3,2>}

2、设： A={0,1,2},B={0,2,4}的关系为： R={|a,b?A∩B} 求：R^-1,并求MR^-1

解： R={<0,0>,<0,2>,<2,2>,<2,0>} R-1={<0,0>,<2,0>,<2,2>,<0,2>} Mr^-1= | 0 0 1 | | 1 1 1 | | 0 0 1 |

应为：Mr^-1= ０ ２ ４

０| 1 1 0 | １| 1 1 0 | ２| 0 0 0 |

3、集合 A={a,b,c}上关系R的关系图下图所示，求 r(R),s(R),t(R)，并分别画出各闭包的图形。 R={,}

r(R)={,,,} s(R)={,,} 为了求：t(R) MR= | 1 1 0 | | 0 0 0 | | 0 0 0 | MR^2= | 1 1 0 | | 0 0 0 |

| 0 0 0 | 。 | 1 1 0 | | 0 0 0 | | 0 0 0 | = | 1 1 0 |

10

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