7.1 关系及其性质 40 ~ 49

题目 40-42

解答 40-42

40

A = { 0, 1 }

则 A x A = { (0,0), (0,1), (1,0), (1,1) }

共有 ${2^4}$ 共16种不同的关系：

$\emptyset$
{ (0,0) }
{ (0,0), (0,1) }
{ (0,0), (1,0) }
{ (0,0), (1,1) }
{ (0,0), (0,1), (1,0) }
{ (0,0), (0,1), (1,1) }
{ (0,0), (1,0), (1,1) }
{ (0,0), (0,1), (1,0), (1,1) }
{ (0,1) }
{ (0,1), (1,0) }
{ (0,1), (1,1) }
{ (0,1), (1,0), (1,1) }
{ (1,0) }
{ (1,0), (1,1) }
{ (1,1) }

41

8个。 ### 42 自反的：5, 7, 8, 9 反自反的：1,10, 11, 14 对称的：1,2,5,6,9,11,13,16 反对称的：1,2,3,4,5,7,8,10,12,14,15,16 非对称的：1,10,14 传递的：1,2,3,4,5,7,8,9,10,12,14,15,16

题目 43

解答 43

a) 共有 ${2^{{4^2}}}$ =65536个

b) 共有 ${2^{{4^2} - 1}} = {2^{15}}$ =32768个

题目 44

解答 44

a) S上共有 ${2^{{n^2}}}$ 个关系。因为对于S上的关系来说，(a,b)有一半的机会出现，所以包含(a,b)的关系共有 ${2^{{n^2} - 1}}$ 个。

b) 同上，共有 ${2^{{n^2} - 1}}$ 个

c) 满足题意的关系，可看作是 $(S - \{ a\} ) \times S$ ，故共有 ${2^{(n - 1)n}}$ 个关系

d) ${2^{{n^2}}} - {2^{(n - 1)n}}$ 个

e) 满足题意的关系，可看作是 $(S - \{ a\} ) \times (S - \{ b\} )$ ，故共有 ${2^{{{(n - 1)}^2}}}$ 个关系

f) ${2^{{n^2}}} - {2^{{{(n - 1)}^2}}}$

题目 45

解答 45

a)

在一个对称的集合中，(a,b)和(b,a)总是成对出现，所以我们可以把它们当成一类，只考虑(a,b)出现的次数。

设集合为A，则 $A \times A$ 中的元素共有 ${n^2}$ 个。其中(a,a)这样的有n个，(a,b)且a不等于b这样的元素有 ${n^2} - n$ 个。因为对于每一个(a,b)， $A \times A$ 都有一个(b,a)，如果我们只考虑其中一种，则有 $({n^2} - n)/2$ 个。再加上(a,a)这样的，一共有 $({n^2} - n)/2 + n$ 个元素需要考虑。

所以在A上，对称的关系的总个数为 ${2^{({n^2} - n)/2 + n}}$ 个。

b)

将 $A \times A$ 中的元素分为两类考虑，一类是全等关系 ${I_A}$ 中的元素，一类是(a,b)和(b,a)，其中a不等于b。

对于 ${I_A}$ ，它可以出现，可以不出现，所以有两种情况。

对于每对(a,b)与(b,a)，它们至多出现一个，所以有三种情况。

综合起来，一共有 ${2^n}{3^{({n^2} - n)/2}}$ 个。

c)

非对称中不能出现(a,a)这样的元素，所以可考虑的元素个数为 $({n^2} - n)$ 个。其中每对(a,b)与(b,a)中，每次至多只能出现其中一个，所以有3种情况。这样就有 ${3^{({n^2} - n)/2}}$ 个

d)

反自反关系中，不能出现(a,a)这样的元素，所以需考虑的元素个数为 ${n^2} - n$ 个，关系总个数为 ${2^{{n^2} - n}}$ 个

e)

先不考虑(a,a)这样的元素，剩下的每两个(a,b)与(b,a)看作一组，则有 $({n^2} - n)/2$ 个元素需要考虑。它们的关系总个数为

${2^{_{({n^2} - n)/2}}}$ 个。然后在每个关系里加上 ${I_A}$ ，即满足要求。所以共 ${2^{_{({n^2} - n)/2}}}$ 个。

f)

先不考虑 ${I_A}$ ，则元素个数为 ${n^2} - n$ 个，关系个数为 ${2^{{n^2} - n}}$ 个。然后再考虑 ${I_A}$ 中的元素，除去全选和全不选的情况，配合前面的关系，就能满足题意。所以共有 ${2^{{n^2} - n}} \times ({2^n} - 2){\rm{ = }}{{\rm{2}}^{{n^2}}} - {2^{{n^2} - n + 1}}$ 个关系。

题目 46

解答 46

a)

当n=1时，集合上的关系总数为2个：空集和{{1,1}}，这两个都是传递的，所以有2个传递关系

b)

用图的方式说明方便一些。一个图上有两个点a和b，如下：

可以分为三种情况考虑：

A与B之间没有边。此时不论A与B上有没有环，都是传递的，所以4种2. A与B之间有单边。从A到B或者从B到A，不论A与B上有没有环，都是传递的，所以有2×4=8种。3. A与B之间有双边。此时只有A与B都有环，才是传递的，有1种。

共有13种。

c)

如下图，有三个点A,B,C：

分多种情况考虑：

没有任何边。此时不论这三点上有没有环，都是传递的，所以有2x2x2共8种。 2. 有一条单边。共有6种单边，此时不论三点有没有环，都是传递的，有6×8=48种。3. 有一条双边。有3种双边。当两点间有双边时，此两点上都必须有环，另一点上有没有环都行。所以共有3×2=6种。4. 有两条单边。共有12种情况。其中有6种情况类似于(a,b),(b,c)，这时不论点上有没有环，都不是传递的。另外6种情况，不论点上有没有环，都是传递的。所以共有6×8=48种。5. 有两边双边。此时不论点上有没有环，都不是传递的。6. 有一条单边一条双边。此时不可能传递。
有三条单边。共有8种情况。回路有2种，此时不是传递的。其它情况有6种，不论点上有没有环，都是传递的。所以共有6×8=48种。8. 有三条双边。此时只有三点上都有环，才是传递的，共有1种情况。9. 有一条单边，两条双边。都不是传递的。
有一条双边，两条单边。分12种情况。其中当两条单边顺次相连（如(a,b),(b,c)），不论点上有没有环，都不是传递的，少了一半。其它6情况，双边的两点必须有环，另一点有没有环都一样传递。所以共6×2=12种。

综上，共有171种。

不用程序来做会死人。

题目 47

解答 47

有问题的地方在于这一句“取元素 $b \in A$ ，使得 $(a,b) \in R$ ”。因为对于A上的任意一个点，可能并不存在一个b使 $(a,b) \in R$ 。

题目 48

解答 48

因为R是A上的自反关系，所以R包含了所有 $(x,x) \in R$ ，所以 $R \cup S$ 包含了所有 $(x,x) \in R$ ，所以它是自反的。
因为R和S都是A上的自反关系，所以R和S都包含了所有 $(x,x) \in R$ ，所以 $R \cap S$ 是自反的
因为 $R \oplus S$ 不包含它们的交集，所以不包含(x,x)，所以它是反自反的。
因为R-S不包含它们的交集，所以不包含(x,x)，所以它是反自反的。
因为R和S都是A上的自反关系，所以 $S \circ R$ 也包含所有的 $(x,x) \in R$ ，所以它也是自反的。

题目 49

解答 49

若R是对称的，则对于 $(a,b) \in R$ ，有 $(b,a) \in R$ ，所以 $(a,b) \in {R^{ - 1}}$ ，所以 $R \subseteq {R^{ - 1}}$ 。类似的，由于R是对称的，则 ${R^{ - 1}}$ 也是对称的，可以求出 ${R^{ - 1}} \subseteq R$ ，所以 $R = {R^{ - 1}}$ 。