离散数学复习资料

3.1 习题参考答案

1、写出下列集合的的表示式。

a)所有一元一次方程的解组成的集合。

A={x|x是所有一元一次方程的解组成的集合} 晓津答案：A={x| ax+b=0∧a?R∧b?R} b) x2-1 在实数域中的因式集。 B={1,(x-1),(x+1)|x?R}

c)直角坐标系中，单位圆内（不包括单位圆周）的点集。 C={x,y| x2+y2<1 }

晓津答案：C={a(x,y)|a为直角坐标系中一点且 x2+y2<1 }

d)极坐标中，单位圆外（不包括单位圆周）的点集。 D={r,θ| r>1,0<=θ<=360}

晓津答案：D={a(r,θ)|a为极坐标系中一点且 r>1,0<=θ<=2π } e)能被5整除的整数集 E={ x| x mod 5=0}

2、判定下列各题的正确与错误。 a) {x} {x}; 正确

b) {x}?{x}; 正确

晓津观点:本命题错误。理由：{x}作为一个元素是一个集合，而右边集合中的元素并不是集合。 c) {x}?{x,{x}}; 正确

d) {x} {x,{x}};

正确

3、设 A={1,2,4},B={1,3,{2}},指出下列各式是否成立。 a) {2}?A; b) {2}?B c) {2} A d) {2} B; e) ?A f) A 解：jhju、晓津和wwbnb

的答案经过综合补充，本题的正确答案是：b、c、d、f成立，a，d、e不成立。

理由：a式中，{2}是一个集合，而在A中并无这样的元素。因此不能说{2}属于A，当然如果说2?A则是正确的。对于e式也应作如此理解，空集是一个集合，在A中并无这个集合元素,如f式则是正确的。空集包含于任何集合中，但空集不一定属于任一集合。 4、设A= { } ，

B= (A),问下列各题是否正确。 a) ?B, B 正确

b) { }?B,{ } B 正确

c) {{ }}?B,{{ }} B 正确

5、设A={a,{a}},问下列各题是否正确。 a) {a}? (A),{a} (A); 正确

晓津答案：本命题不正确。 (A)={ ，{a},{{a}},{a,{a}}},在这个集合中，并无a这个元素，因此命题的后半个{a} (A)是

1

不成立的。

b) {{a}}? (A),{{a}} (A); 正确

c) 设A={a,{b}},a),b) 是否正确。 a 和 b都正确

晓津答案：如此则a),b)均不正确。此时, (A)={ ，{a},{{b}},{a,{b}}}。除了a式的前半句正确，其他的都不成立，因此a),b)式均不成立。

6、设某集合有101个元素，试问： a) 可构成多少个子集； 2n个元素 (子集吧)

b) 其中有多少个子集元素为奇数； 其中有 2n-1 个子集元素为奇数

晓津不同意见：我认为这个答案不成立,如集合有3个元素，则它的幂集中有5个子集中元素个数为奇数，而不是7个。可是我也还没找到这个式子。 sphinx提供的答案是2100

，可通过多项式分解找到规律，空集不算。 晓津想，应该算上，若算上则是2n-1+1 c) 是否有102个元素的子集。 无

3.2习题答案

1、给定自然数集合N的下列子集：

A={1,2,7,8} B={i|i^2<50}={0,1,2,3,4,5,6,7}

C={i|i可被3整除 0?i?30}, ={0,3,6,9,12,15,18,21,24,27,30} D={i|i=2^K,K?Z+,1?K?6}={2,4,8,16,32,64} 求下列各集合。 a) A∪(B∪(C∪D));

={2,4,8,16,32,64,0,3,6,9,12,15,18,21,24,27,30,1,5,7} b) A∩(B∩(C∩D)); =A∩(B∩ }= c) B-(A∪C);

=B-{0,1,2,7,8,3,6,9,12,15,18,21,24,27,30} ={4,5}

d) (～A∩B)∪D

={8}∪D={2,4,8,16,32,64}

晓津补充:这里的(～A∩B)应当等于(B-A)而不是(A-B), 所以最终的答案是：{0,3,4,5,6}∪D={0,2,3,4,5,6,8,16,32,64} 2、a)如果对于一切集合，有X∪Y=X，则Y=φ 证明： X∪Y={i|i?X∨i?Y}=X {i|i?X∨i?Y}=X

{i|i?X∨i?Y}={i|i?X} 由此可见：Y=φ 晓津的证明：

必要性：设Y≠φ 则Y中必有一个以上元素。若有一个元素y,y?Y∧y X 则有X∪Y≠X 这与前提矛盾。 充分性： 若Y=φ

则任合集合X∪Y=X成立。

2

本题要注意Y有时包含于X的，若用命题表达式论证，应用到量词。 b)证明对所有集合A，B和C，有：(A∩B)∪C=A∩(B∪C); iffC A。 (A∩B)∪C={i|(i?A∧i?B)∨i?C} A∩(B∪C)={i|i?A∧(i?B∨i?C)}

(i?A∧i?B)∨i?C = i?A∧(i?B∨i?C) 因为 iffC A

所以 i?A∨i?C=i?A

得证：(A∩B)∪C=A∩(B∪C)

晓津证明：本题也要进行双向的证明，一个是必要性，一个是充分性，这才能得出当需的结论。 证：充分性： 若C A

则(A∩B)∪C=(A∪C)∩(B∪C)=A∩(B∪C)=右边。 必要性：

假设C不包含于A内，则C中必有一个以上元素x A，则A∪C≠A可得 (A∩B)∪C=(A∪C)∩(B∪C)≠A∩(B∪C)

假设与前提矛盾，因此假设不成立，C应当包含于A内。 3、证明对任意集合A，B，C，有： a) (A-B)-C=A-(B∪C);

证明： (A-B)-C={x| x?A∧x B}-C ={x| x?A∧x B∧x C} ={x|

x?A∧x?～B∧x?～C}

={x| x?A∧x?(～B∩～C)} ={x| x?A∧x?～(B∪C)} =A-(B∪C)

我想，本题也可以直接应用集合运算来做。 b) (A-B)-C=(A-C)-B;

(A-B)-C={x| x?((A-B)-C)} ={x| x?A∧x B∧x C}

={x| x?(A-C)∧x B}

=(A-C)-B c) (A-B)-C=(A-C)-(B-C)

(A-B)-C={x| x?((A-B)-C)} ={x| x?A∧x B∧x C}

={x| x?A∧x B∧x B∧x C} ={x| x?(A-B)∧x B∧x C}

={x| x?(A-B)∧x?～B∧x?～C} ={x| x?(A-B)∧x?(～B∩～C)} ={x|

x?(A-B)∧x?～(B∪C)} ={x| x?(A-B)∧x (B∪C)}

(A-C)-(B∪C) (题目是否有误？) 晓津证明：(题目并无误) 右边=(A-C)-(B-C)

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

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

3

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

=左边

4、设A，B，C是全集E的任意子集。

a)若 A∩B=A∩C,～A∩B=～A∩C,证明：B=C 晓津证明此题如下:

证明：由 A∩B=A∩C,～A∩B=～A∩C得 (A∩B)∩(～A∩B)=(A∩C)∩(～A∩C) (A∩B)∪(~A∩B)=(A∩C)∪(~A∩C) B∩(A∪~A)=A(C∪~C) 即B∩E=C∩E

因B，C是全集E的任意子集 B=C

b)若 (A∩C) (B∩C),(A∩～C) (B∩～C),证明：A B 由(A∩C) (B∩C),(A∩～C) (B∩～C) 得： (A∩C)∪(A∩～C) (B∩C)∪(B∩～C) A∩(C∪～C) B∩(C∪～C) A∩E B∩E

A，B，C是全集E的任意子集 A B

5、设 A={φ},B= ( (A)),问下列各题是否正确？ a) φ?B φ B 正确

b) {φ}?B {φ} B 正确

c) {{φ}}?B {{φ}} B 正确

本题由kavana补充： (A)={φ,{φ}} B= ( (A))={φ,{φ},{{φ}},{φ,{φ}}} 。 感谢kavana！6、在下面各题中，如果命题为真，请给证明；如果命题为假，则给出反例； a)、 A∩(B-C)=(A∩B)-(A∩C) 晓津证明如下：

A∩(B-C)={x|x?A∧(x?B∧x?～C)} ={x|x?A∧x?B∧(x?A∧x C)}

={x|x?A∧x?B∧(x?A∧x (A∩C))} ={x|x?A∧x?B∧x (A∩C)} =(A∩B)-(A∩C)

b)、 (A-B)∩(B-A)=φ

(A-B)∩(B-A)={x| x?A x B x A x?B}=φ 也可以用集合运算证明： 原式=(A∩～B)∩(B∩～A) =(A∩～A)∩(B∩～B)=Φ c)、 A-(B∪C)=(A-B)∪C 不成立

补充实例如下：设A={1,2,3,4} B={1,5} C={2,6}

则 A-(B∪C)={3,4} 而 (A-B)∪C={2,3,4,6} d)、 ～(A-B)=～(B-A)

4

不成立

补充实例：设E={1,2,3,4,5} A={1,2} B={1,3,4}

则 ～(A-B)={1,3,4,5} 而 ～(B-A)={1,2,5} e) ～(A∩B) A 不成立

补充实例如下:设E={1,2,3} A={1,2} B={2,3} 则 ～(A∩B)={1,3} 它不包含于A内。 f) (A∩B)∪(B-A)=A 不成立

补充实例如下： A={1,2} B={1,2,3,4}

则(A∩B)∪(B-A)={1,2,3,4 }≠A

7、设A，B，C是任意集，证明： a) (A∪B)-C=(A-C)∪(B-C)

证明：(A∪B)-C={x| (x?A∨x?B)∧x C}

={x|(x?A∧x C)∨(x?A∧x C)}

=(A-C)∪(B-C) b) A-(B∪C)=(A-B)∩(A-C)

证明:A-(B∪C)={x| x?A∧x (B∪C)} ={x| x?A∧(x B∧x C)}

={x| x?A∧x B∧x?A∧x C)} =(A-B)∩(A-C)

c)、(A-B)∪(A-C)=A,当需 A∩(B∩C)=φ时成立。 证明:(A-B)∪(A-C)

={x| (x?A∧x B)∨(x?A∧x C)} ={x| x?A∧(x B∨x C)} ={x| x?A∧x (B∪C)}

我怎么觉得：A∩(B∪C)=φ时，(A-B)∪(A-C)=A 题目是否出错了？

晓津认为：红色的∪其实应为∩，x B或x C 应用德摩根律，就是说x (B∩C). 以上证明并未证得结论。 现证明如下：

充分性：若A∩(B∩C)=φ

则前提的左边=(A∩～B)∪(A∩～C)=A∩(～B∪～C) =A∩～(B∩C)=A-(B∩C) =A-(B∩C)=A-(A∩(B∩C)) =A-Φ =A=右边 可得等式成立

必要性：若设A∩(B∩C)≠φ则由上面证明可知 A-(B∩C)≠A。 即前提左边≠A

左右不等，因此假设违反题意，不成立。所以必需A∩(B∩C)=φ 8、证明：

a)、 A∩(B C)=(A∩B) (A∩C)

5

??

晓津证明如下：

右边=((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

| 0 0 0 |

| 0 0 0 | MR^3= | 1 1 0 |

| 0 0 0 | | 0 0 0 |

可见： t(R)=MR ∪MR^2∪MR^3={,} 4、设 A={1,2,3,4}上的二元关系， R={<1,2>,<2,4>,<3,3>,<1,3>}，则：

r(R)={<1,1>,<2,2>,<4,4>,<1,2>,<2,4>,<3,3>,<1,3>} S(R)={<1,2>,<2,4>,<3,3>,<1,3>,<2,1>,<4,2>,<3,1>} t(R)=

MR= | 0 1 1 0 |

| 0 0 0 1 | ={<1,2>,<2,4>,<3,3>,<1,3>} | 0 0 1 0 |

| 0 0 0 0 |

MR^2= | 0 1 1 0 | | 0 1 1 0 | | 0 0 1 1 | | 0 0 0 1 | | 0 0 0 1 | =| 0 0 0 0 |

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

| 0 0 0 0 | | 0 0 0 0 | | 0 0 0 0 | ={<1,3>,<1,4>,<3,3>} MR^3= | 0 0 1 1 | | 0 1 1 0 | | 0 0 1 0 | | 0 0 0 0 | | 0 0 0 1 | =| 0 0 0 0 | | 0 0 1 0 | 。| 0 0 1 0 | | 0 0 1 0 |

| 0 0 0 0 | | 0 0 0 0 | | 0 0 0 0 | ={<1,3>,<3,3>} MR^4= | 0 0 1 0 | | 0 1 1 0 | | 0 0 1 0 | | 0 0 0 0 | | 0 0 0 1 | =| 0 0 0 0 |

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

| 0 0 0 0 | | 0 0 0 0 | | 0 0 0 0 | ={<1,3>,<3,3>} 可得t(R)={<1,2>,<2,4>,<3,3>,<1,3>} ∪{<1,3>,<1,4>,<3,3>} ∪{<1,3>,<3,3>} ∪{<1,3>,<3,3>}

={<1,2>,<1,4>,<2,4>,<3,3>,<1,3>}

5、设R、Q都是集合A上自反、对称、传递关系，则

s(R∩Q)=_________，t(R∩Q)=_________.因为_________也是自反、对称、传递的。 s(R)∩s(Q) t(R)∩t(Q) R∩Q 6、集合 A={1,2,3,4,5,6}的关系图如下所示，求： a) R,R^2，R^3及关系图

解： R={<1,3>,<1,5>,<2,5>,<3,3>,<4,5>,<5,4>} MR^2=

| 0 0 1 0 1 0 | | 0 0 1 0 1 0 | | 0 0 1 1 0 0 | | 0 0 0 0 1 0 | | 0 0 0 0 1 0 | | 0 0 0 1 0 0 | | 0 0 1 0 0 0 | | 0 0 1 0 0 0 | = | 0 0 1 0 0 0 | | 0 0 0 0 1 0 | 。| 0 0 0 0 1 0 | | 0 0 0 1 0 0 | | 0 0 0 1 0 0 | | 0 0 0 1 0 0 | | 0 0 0 0 1 0 | | 0 0 0 0 0 0 | | 0 0 0 0 0 0 | | 0 0 0 0 0 0 | R^2={<1,3>,<1,4>,<2,4>,<3,3>,<4,4>,<5,5>}

11

MR^3=

| 0 0 1 1 0 0 | | 0 0 1 0 1 0 | | 0 0 0 1 1 0 | | 0 0 0 1 0 0 | | 0 0 0 0 1 0 | | 0 0 0 0 1 0 | | 0 0 1 0 0 0 | 。| 0 0 1 0 0 0 | = | 0 0 1 0 0 0 | | 0 0 0 1 0 0 | | 0 0 0 0 1 0 | | 0 0 0 0 1 0 | | 0 0 0 0 1 0 | | 0 0 0 1 0 0 | | 0 0 0 1 0 0 | | 0 0 0 0 0 0 | | 0 0 0 0 0 0 | | 0 0 0 0 0 0 | R^3={<1,4>,<1,5>,<2,5>,<3,3>,<4,5>,<5,4>} b) r(R),s(R);

r(R)={<1,3>,<1,5>,<2,5>,<3,3>,<4,5>,<5,4>,<1,1>,<2,2>,<4,4>,<5,5>,<6,6>} s(R)={<1,3>,<3,1>,<1,5>,<5,1>,<2,5>,<5,2>,<4,5>,<5,4>}

7、令S为从X到Y的关系，T为从Y到Z的关系，对于 A X，定义S(A)={y|?S∧x?A} 证明： a) S(A) Y

b) (S。T)(A)=T(S(A));

c) S(A∪B)=S(A)∪S(B),其中B X d) S(A∩B) S(A)∩S(B)

8、设： R1和R2是A上的关系，证明： a) r(R1∪R2)=r(R1)∪r(R2);

证明如下：因为R1，R2是A上关系，所以R1∪R2也是A上关系； 由r(R1)=R1∪IA 和r(R2)=R2∪IA可得 r(R1)∪r(R2)= R1∪R2∪IA

又因r(R1∪R2)=(R1∪R2)∪IA 所以左右相等。

b) s(R1∪R2)=s(R1)∪s(R2); 证明如下：

左边=s(R1∪R2)=(R1∪R2)∪(R1∪R2)-1 右边=s(R1)∪s(R2)=R1∪R1-1∪R2∪R2-1 =R1∪R2∪R1-1∪R2-1 =(R1∪R2)∪(R1∪R2)-1 =左边 等式成立。

c) t(R1∪R2) t(R1)∪t(R2);

因为:t(R1)=R1∪R12∪R13∪...∪R1n(n为A中元素个数) t(R2)=R2∪R22∪R23∪...∪R2n

则 t(R1)∪t(R2)=R1∪R2∪R12∪R22∪R13∪R23∪...∪R1n∪R2n 左边=t(R1∪R2)=(R1∪R2)∪(R1∪R2)2∪......∪(R1∪R2)n 设A中有任意?R1 ，任意?R2 则有?t(R1) ?t(R2)

(1)因为,?(R1∪R2) (2)则有,?t(R1∪R2)(3)

因此由(1)(2)(3)式可得：t(R1∪R2) t(R1)∪t(R2); 3.6习题答案

12

1、给定集合X={x1,x2,....,x6},ρ是X上相容关系且Mρ简化矩阵为： 试求X的覆盖，并画出相容关系图。 解：覆盖如下：

{,,,,,,,,,, ,,,,,,,} 晓津觉得覆盖中的元素应该是集合：我的答案是： S={{x1,x2,x3},{x4,x5,x6}} 当然这只是一个覆盖。

2、从下面给出的关系图中，说明哪个是相容关系。 答：图3、4是相容关系。

3、设集合A={1,2,3,4}中的一个覆盖为 B={{1,2},{2,3,4}},求出确定的相容关系。 解： S1={1,2} S2={2,3,4}

根据定理3.6.1：ρ=S1×S1∪S2×S2

={<1,1>,<1,2>,<2,1>,<2,2>}∪{<2,2>,<2,3>,<2,4>,<3,2>,<3,4>,<3,3>,<4,2>,<4,3>,<4,4>} ={<1,1>,<1,2>,<2,1>,<2,2>,<2,3>,<2,4>,<3,2>,<3,4>,<3,3>,<4,2>,<4,3>,<4,4>}

4、设αβ是A上相容关系，

a) 复合关系α。β是A上的相容关系吗？

由于自反性通过,运算可保持;但对称性不能通过,保持。所以复合关系α。β不是A上的相容关系 b) α∪β是A上相容关系吗？ 是的

晓津补充证明如下:

(1)因为α，β是A上相容关系，若有任意x?A，则?α且?β， 所以?α∪β 因此α∪β是自反的。

(2)因为α，β是A上的相容关系，若有任意x,y?A且?α 则有?α； 若有任意u,v?A且?β，则有?β， 所以有，,,?α∪β 因此α∪β是对称的。

可得α∪β是A上相容关系。 c) α∩β是A上相容关系吗？ 是的

晓津证明如下：

(1)因为α，β是A上相容关系，则若有任意x?A,就有?α∩β，因此α∩β是自反的。

(2)因为α，β是A上相容关系，则若有任意x,y?A且?α且?β则有?α且?β 即,?α∩β 因此α∩β是对称的。

可得α∩β是A上相容关系。 3.7 习题参考答案

1、设R是一个二元关系，设S={ |存在某个C，使?R且?R}，证明R是一个等价关系，则S也是一个等价关系。 证明：

如果题目反一下是：S是一个等价关系，则R也是一个等价关系。或许能证出吧 晓津看法:题中的大写C应为小写c;请学友提供您的看法。 （1）∵R是自反，

∴若有x?A就有＜x，x＞?R

13

∴＜x，x＞?S ∴S是自反的。 （2）因有＜a，b＞?S

且存在c，使＜a，c＞?R且＜c，b＞?R ∵R是对称的

∴＜c，a＞?R，＜b，c＞?R ∴＜b，a＞?S ∴S是对称的

（3）设＜a，b＞，＜b，c＞?S

则存在d,e使＜a，d＞，＜d，b＞，＜b，e＞，＜e，c＞?R ∵R是传递的

∴＜a，b＞，＜b，c>?R ∴＜a，c＞?S 即S是传递的

因此得证S是等价关系。

2、设R是A上一个自反关系，证明：R是一个等价关系，当且仅当若 ?R,?R,则?R。 证明：由于R是一个等价关系，所以R是传递的。由此可知：若?R,根据对称性，则有?R 已知： ?R且?R,根据传递性，必有 ?R

晓津认为：jhju的证明中，已经在前提中确定了R是一个等价关系，这种理解应是不正确的。我的理解是： 前提：R是A上的自反关系

结论：R是一个等价关系 iff (aRb,aRc→bRc)

等价关系的充要条件是R为自反的，对称的和传递的。但是我也无法证出来。请胖胖、sphinx、菜虫虫和ryz和其他朋友提供您的思路好吗? 下面是linuxcn

和阮允准同学给出的证明(晓津作了综合)： 证明：1）

设有a,b,c?A，若有?R，?R 因为R是对称的，所以必有?R

又因为R是传递的，由,?R，有?R

2）由(a,b)?R,(a,c)?R,则(b,c)?R。证等价关系,其实只需证传递关系和对称关系。如下： 设有任意的?R ∵R是自反的 ∴?R ∴?R ∴R是对称的

对任意的,?R 由R是对称的 ∴?R

∴由?R，?R 可得?R ∴R是传递的 ∴R是等价关系。

3、设R为集合A上一个等价关系，对任何a?A,集合 [a]R=____[a]R={x| x?A,aRx}________称为元素a形成的等价类。[a]R≠φ，因为_____ A=φ______。 阮允准给出后一空的正确答案： a?[a] 4、设R是A上的自反和传递关系， 证明：R∩R-1 是A上的一个等价关系。 证明：R是A上的自反关系，所以

14

?R 且 ?R-1 ?R∩R-1 R是A上的传递关系, 则：

若有?R 且 ?R,则有?R

由于R又具有对称性，所以?R 且 ?R,则有?R R-1 也有：?R-1

且?R-1 ,则有?R-1 可见：?R∩R-1

且?R∩R-1 ,则有?R∩R-1

R是A上的对称关系，则有 ?R、?R R-1 是A上的对称关系，也有 ?R、?R 则有： ?R∩R-1 、?R∩R-1 由于R∩R-1

有对称性，传递性、自反性。所以说R∩R-1 是等价关系。

上面的红色部分有点问题，已知条件中并未给出这样的前提。晓津证明如下： (1)因为R是A上的自反关系,若有a?A，则 ?R且?R-1 即?R∩R-1

所以R∩R-1是自反的。

(2)因为R是A上的传递关系，则R-1也是A上传递关系，若有a,b,c?A,则 若?R∩R-1且?R∩R-1 必有?R∧?R 且?R-1∧ 因此有?R ∧?R-1 即?R∩R-1

所以R∩R-1是传递的。

(3)若有a,b?A 则

若?R∩R-1

就有?R且?R-1

同时因为?R，有?R-1;?R-1则有?R 因此有,?R∩R-1

________________________________________ 5、集合A={1,2,3,4,5}上划分为S={{1,2},{3,4,5}}, a) 写出由S导出的A上等价关系ρ;

b) 画出ρ的关系图，求Mρ。

解：a)ρ={{1,2}×{1,2}}∪{{3,4,5}×{3,4,5}}

={<1,1>,<1,2>,<2,1>,<2,2>}∪{<3,3>,<3,4>,<3,5>,<4,3>,<4,4>,<4,5>,<5,3>,<5,4>,<5,5>}

15

={<1,1>,<1,2>,<2,1>,<2,2>,<3,3>,<3,4>,<3,5>,<4,3>,<4,4>,<4,5>,<5,3>,<5,4>,<5,5>}

b)

上图是相容关系图（简单一些）

Mρ= 1 2 3 4 5 1| 1 1 0 0 0 | 2| 1 1 0 0 0 | 3| 0 0 1 1 1 | 4| 0 0 1 1 1 | 5| 0 0 1 1 1 |

只画黄色部分也可以。

________________________________________

6、设正整数的序偶集合A，在A上定义二元关系R如下： <,>?R,当且仅当xv=yu，证明：R是一个等价关系。 晓津证明如下：

(1)因为xv=yu，则有x/y=u/v 且有x/y=x/y,u/v=u/v

因此有<,>?R，<,>?R 所以R是自反的。

(2)因为xv=yu,则有x/y=u/v ，且有u/v=x/y,

因此有<,>?R， 所以R是对称的。

(3)设有s,t,?A

若有x/y=u/v且u/v=s/t 则s/t=x/y, 则有x/y=s/t 因此有<,>?R 所以R是传递的。

因而R是一个等价关系。

________________________________________

7、设集合A有4个元素，那么，A中有多少个划分？A上有多少个等价关系？ 解：有下列几种划分： { { } ,{ } ,{ },{ } }

四个元素的划分有 1个

{ { } ,{ } ,{ } } 三个元素的划分有 12种 { { } ,{ } } 二个元素的划分有 6种

{ { } } 一个元素的划分有 1种 总共有 20种划分。

20种划分对应20种等价关系

阮允准提醒说划分只有15种，晓津现给出确定的结果，三个元素的划分只有6种，二个元素的划分有7种。总共15种。

16

________________________________________

8、设П1与П2是非空集合A的划分，问：П1∪П2、П1∩П2、和П1-П2是A的划分吗?在什么条件下，它们能构成A的划分。

解：П1∪П2：不是A的划分。 П1∩П2：不是划分。 П1-П2: 不是划分。

在 П1=П2 的情况下，它们能构成A的划分 晓津补充证明： (1)

П1∪П2不一定是A的划分：

若有S1?Π1 ，S2?Π2， 有a?A 且 a?S1且a?S2 , 则S1∪S2 A ,S1∪S2?Π1∪Π2 但S1∩S2≠φ 所以， Π1∪Π2不一定是A的划分 其他类似。

3.8节习题参考答案

(本节习题答案由jhju提供，晓津补充。旨在抛砖引玉，不同意见请到分课论坛发表) http://jjzk.yeah.net 题号：1 2 3 4 5 6

________________________________________

1、画出A={3,9,27,54}上整除关系的哈斯图，并说明是否为全序关系。 解：

/={<3,3>,<3,9>,<3,27>,<3,54>,<9,9>,<9,27>,<9,54>,<27,27>,<27,54>,<54,54>}

哈斯图见上。其不是全序关系。

晓津认为这个关系应是全序关系,因为对于任意两个元素a,b,必有a<=b 或b<=a。 ________________________________________

2、设 A={1,2,3,4,5,6},R为A上的整除关系，试求： a) A的极大元、极小元、最大元和最小元。

b) 子集 A1={2,3,6} 和A2={2,3,5}的上界、下界、上确界、下确界。 解：

R={<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<2,4>,<2,6>,<3,6>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>,<6,6>} COVA={<1,2>,<1,3>,<1,5>,<2,4>,<2,6>,<3,6>}

a) 其极大元为 {4,5,6} 极小元 { 1 } 最大元不存在.最小元 { 1 }

从哈斯图上看出 最大元、最小元、极小元、极大元的方法:以下均就A是一个偏序集而言，B包含于A，求B中的极大元、极小元、最大元、最小元。

(1)极大元：在B的哈斯图中每一个孤立结点或只有下方连线的结点都是B的极大元。

17

(2)极小元：在B的哈斯图中每一个孤立结点或只有上方连线的结点都是B的极小元。

(3)最大元和最小元：首先找出B的极大元和极小元。若极大元或极小元只有一个，则这个极大元或极小元就是B的最大元或最小元；若不止一个，则B的最大元或最小元不存在。

b) A1的上界、上确界为 { 6 } 下界、下确界为 { 1 } A2的上界、上确界不存在， 下界、下确界为 { 1 }

从哈斯图上看出 上界、上确界、下界、下确界的方法:A是一个偏序集，B包含于A，在哈斯图中，求B的上界、上确界，下界、下确界。

在A的哈斯图中，标出B中的结点，则不低于(不高于)其中最高结点(最低结点)并有与它们均相连且只通过下方( 上方)直线相连(包括环)的结点都为B的上界(下界)；在上界集(下界集)中距B中最高结点(最低结点)路径最短的结点是上确界(下确界)。

________________________________________

3、设集合R是A上的二元关系，证明：

a) 如果R是A上拟序关系，则 r(R)=R∪IA是偏序关系。 b) 如果R是一偏序关系，则 R-IA是拟序关系。 证明：

a) R是A上拟序关系，则有：R是反自反和传递的。 R∪IA

{| ?R∧x?A∧y?A∧x x} ∪ {| x?A∧y?A∧xRx}

{ | ?R∧x?A∧y?A∧x x∨xRx} { |

?R∧x?A∧y?A∧xRx} 可见R∪IA 具有自反性

R具有传递性，则

?R 且 ?R ，则必有 ?R

?R => ?R∪IA ?R =>?R∪IA ?R => ?R∪IA

?R∪IA 且 ?R∪IA ，则必有 ?R∪IA

可见R∪IA 具有传递性

根据定理3.8.1 R是拟序，则R必有反对称性 => R={ |x,y?A∧xRy∧x≠y∧y x} R∪IA

{|x,y?A∧xRy∧x≠y∧y x} ∪ {| x?A∧y?A∧xRx}

{ |x,y?A∧xRy∧x≠y∧y x∧xRx} 可见R∪IA 具有反对称性

18

得证：r(R)=R∪IA是偏序关系

b) 如果R是一偏序关系，则 R-IA是拟序关系。

简略证明：偏序关系与拟序关系相比，区别在于自反性和反自反性 而 R

一旦失去了IA，则自反性也就丢失了。故R-IA是拟序关系 阮允准同学认为上述证明不够规范，给出证明如下： a) 如果R是A上拟序关系，则 r(R)=R∪IA是偏序关系。

a)对于任意x?A,有＜x,x>?IA ∴?R∪IA ∴r(R)是自反的

对于任意(x≠y) ?R∪IA ∴?R

∵R是A上的拟序关系 ∴R 又IA

∴r(R)是反对称的

设x,y,z?A,且,?R∪IA 则,?R或,?IA ∴?R或?IA ∴?R∪IA ∴r(R）是传递的 b）证法类似

________________________________________

4、设R是集合S上的关系，S'是S的子集，定义S'上关系R'如下： R'=R∩(S'×S')

确定下述每一条断言是真还是假

a) 如果R在S上是传递的，那么R'在S'上是传递的。 b) 如果R是S上偏序关系，那么R'是S'上的偏序关系。 c)

如果R是S上的拟序关系，那么R'是S'上的拟序关系。 d) 如果R是S上的线序关系，那么R'是S'上线序关系。 解： a)

为真，因为S'×S'在S'是传递的，而R在S上是传递的，经过∩运算后仍具有传递性 b) 为假 因为S'×S'在S'是对称的 c) 为假

d) 为真

19

阮允准同学认为：a,b,c,d都是正确的 b)证明：

显然R′是自反的，传递的 现证反对称 ?R′且（x≠y) 则?R

∵R是偏序关系 ∴R ∴R′

∴R是反对称的 其它证法类似。

________________________________________

5、设偏序集 ,若有B A，如B中存在最大元（最小元），则必为惟一。 晓津证明：

设若B中有最大元a,b,则对于B中任一元素x有x a ,x b ， 对于a为最大元，应有b a 对于b为最大元,应有a b，如果a≠b,则表明B上关系不是反对称的，这个结论与B A且A上关系是偏序集的前提相矛盾，因此必有a=b，即最大元只能有一个。推广到更多的情况也是如此。对于最小元，其情形与之相同，因此最小元也只能是唯一的。

________________________________________

6、证明每一个良序集合一定是一个全序集合；反之成立吗？试说明理由？ 晓津证明：

根据定义，设为全序集,如果A的任何非空子集都含有最小元,则为良序集合,所以良序集必为全序集。 反之不一定成立，如果一个全序集合A中有一非空子集不含有最小元，则该全序集就不是良序集。 ________________________________________

阮允准同学认为书中的定义是错误的

良序的定义是：设＜A，?＞为偏序集......

现证明：设＜A，?＞为良序集，对任意的a,b?A，构造集合 ｛a,b},显然｛a,b}包含于A,

∴{a,b}有最小元，故必有a?b或b?a ∴＜A，?＞是全序集

反之也成立，因为全序集中任意两个元素都可比 所以对每一个非空子集，必有最小元

（事实上，全序的哈斯图是一条直线，从哈斯图中不难看出对每一个非空集合都有最小元） 3.9习题参考答案

(本节习题答案由jhju提供，晓津,阮允准补充。旨在抛砖引玉，欢迎到分课论坛发表不同意见) http://jjzk.yeah.net 题号：1 2 3 4

________________________________________

1、下列集合条件分别确定f是否从X到Y上的函数，并对f:X->Y指出哪些是入射，哪些是满射，哪些是双射？ a) X={1,2,3,4,5}, Y={6,7,8,9,10},

f={<1,8>,<3,10>,<2,6>,<4,9>}; 其不是满射、是入射。

20

其不满足 交换律 、满足结合律 、不满足幂等律、无零元、无单位元

晓津补充证明如下：

(1)a*b=pa+qb+r 而b*a=pb+qa+r

当p,q取值不等时，二式不相等。因此*运算不满足交换律。 (2)设a,b,c?R

则(a*b)*c=p(pa+qb+r)+qc+r=p^2a+pab+pr+qc+r 而a*(b*c)=pa+q(pb+qc+r)+r=pa+qpb+q^2c+qr+r 二式不恒等，因此*运算是不满足结合律的。 (3)a*a=pa+qa+r≠a

所以运算不满足幂等律。

(4)反证法。设有单位元e,则应有

a*e=pa+qe+r=a, e*a=pe+qa+r=a,可知e=(a-pa-r)/q 或e=(a-qa-r)/p 当p,q,r

,a取值不同时，可得不同的e,这与单位元若有时只是唯一的定理相矛盾。 (5)反证法。设有零元O,则应有 a*O=pa+qO+r=O

,O*a=pO+qa+r=O ，同上分析，零元不止一个，因此与零元唯一的定理相矛盾。 ________________________________________ 5、设代数系统,其中

A={a,b,c},*是A上的一个二元关系。对于以下定义所确定的运算，试分别讨论它们的交换性、等幂性，以及在A中关于*是否有幺元，如果有幺元，那么A中的每个元素是否有逆元。

(a) (b)

* a b c * a b c a b

c a b c b c a c a b a b

c a b c b a c c c c (c) (d)

* a b c * a b c a b

c a b c a b c a b c a b

c a b c b b c

26

c c b

(a) : 可交换、具有幂等性、有幺元 a 、 c是b的逆元

晓津答案：可交换，但不具有幂等性。幺元e=a,表中有a*a=a,b*c=a,c*b=a,则可得a的逆元是a,b有逆元c,c有逆元b. (b)

: 可交换、不具有幂等性、有幺元 a ,

因为a*a=a,b*b=a,所以a有逆元a,b有逆元b.

(c) :

不可交换、具有幂等性,无幺元。

(d) : 可交换、不具有幂等性、有幺元 a ,a有逆元a. ________________________________________

6、定义I+上两个二元运算为： a*b=a^b

a△b=a.b , a,b?I+,

证明*对△是不可分配的。 证明： 设a,b,c?I+

a*(b△c)=a^(b.c)

(a*b)△(a*c)=(a^b).(a^c)=a^(b+c)

可见：a*(b△c)≠(a*b)△(a*c) 根据：a*(b△c)≠(a*b)△(a*c) 可知*对△是不可分配的

________________________________________

7、设Zn={0,1,2,...,n-1},*是Zn上的二元运算，使得a*b=a.b/n 的余数。

构造n=4时，运算*的规则表。

并证明对于任意 n?N,*在Zn上是可结合的。 解：

Zn={0,1,2,3}

* 0 1 2 3 0 0 0 0 0 1 0 1 2 3 2 0 2 0 2 3 0 3 2 1

晓津证明如下：

(1)我们先证明n=1时,该运算*在Z1

上的运算是可结合的：此时，设有a,b,c?Z1 则有a=0,b=0,c=0 (a*b)*c=(((a.b)Mod n).c )Mod n=0

a*(b*c)=(a.((b.c)Mod n) )Mod n=0

两式相等，因此当n=1时，*运算是可结合的。

27

(2)由上可设

当n=k时，*运算是可结合的。 (3)设n=k+1时，有：

(a*b)*c= (((a.b) Mod (k+1)).c )Mod (k+1) =(a.b.c Mod (k+1) ) Mod (k+1)

a*(b*c)=(a.((b.c)Mod (k+1)) )Mod (k+1)

=(a.b.c Mod (k+1) ) Mod (k+1)

可见两式是完全相同的结果。因此有当n=k+1时，*运算满足结合律。 所以对于任意n?N,*在Zn上是可结合的。 4.2节习题参考答案

(本章习题答案由jhju提供，晓津补充。旨在抛砖引玉，欢迎发表不同意见:分课论坛) http://jjzk.yeah.net 题号：1 2 3 4 5 6 7 8 9

________________________________________

1、对于正整数k,Nk={0,1,2,.....,k-1},设*k是Nk上的一个二元运算，使得a*kb为用k除 a.b所得余数，这里a,b?Nk。 a)当k=4时，试造出*k的运算表。

b)对于任意正整数k，证明是一个半群。 解： 解：

Zn={0,1,2,3}

* 0 1 2 3 0 0 0 0 0 1 0 1 2 3 2 0 2 0 2 3 0 3 2 1

(1)我们先证明k=1时,该运算*在Z1 上的运算是可结合的：此时，设有a,b,c?Z1 则有a=0,b=0,c=0 (a*b)*c=(((a.b)Mod k).c )Mod k=0 a*(b*c)=(a.((b.c)Mod k) )Mod k=0

两式相等，因此当k=1时，*运算是可结合的。 (2)由上可设 当k=k时，*运算是可结合的。 (3)设k=k+1时，有：

(a*b)*c= (((a.b) Mod (k+1)).c )Mod (k+1) =(a.b.c Mod (k+1) ) Mod (k+1) a*(b*c)=(a.((b.c)Mod (k+1)) )Mod (k+1) =(a.b.c Mod (k+1) ) Mod (k+1)

可见两式是完全相同的结果。因此有当k=k+1时，*运算满足结合律。 所以对于任意k?K,*在Zk上是可结合的。 由此可知其是个半群。

________________________________________

2、设是一个半群a?S，在S上定义一个二元运算□，使 得对于S中任意元素x和y，都有x□y=x*a*y

28

证明：二元运算□是可结合的。 根据结合律： (x□y)□z=x□(y□z) (x□y)□z=(x*a*y)*a*z

x□(y□z)=x*a*(y*a*z) 由于*满足结合律，故： (x*a*y)*a*z=x*a*(y*a*z) =>

(x□y)□z=x□(y□z)

=> 二元运算□是可结合的

________________________________________

3、设G={0，1，2，3}， 为模4乘法，即 x,y?G, x y=(xy)mod4。问: 构成什么代数系统？试证明之。

构成一个半群,证明详见第一题，其具有封闭性、结合性。 ________________________________________

4、在R中定义二元运算。 a。b=a+b+ab, a,b?R 。 证明： 是独异点。

(1)、由运算 。可知，a。b?R ，可知其在R上具有封闭性。 （2）、对于任意 a,b,c?R

(a。b)。c=(a+b+ab)。c=a+b+ab+c+ac+bc+abc

a。(b。c)=a。(b+c+bc)=a+b+c+bc+ab+ac+abc 可见： (a。b)。c=a。(b。c) 即 。

在R上是可结合的。

(3) 因为 [0]。[i]=i ,所以[0]是上一个幺元 根据上述 是独异点

晓津认为题中所给中的O应为o；答案中的(3)幺元是0,而不是[0].

________________________________________

5、设V=是个半群，若存在 a?S,使得对任意的 x?S,有 u,v?S满足： a*u=v*a=x 。证明 V是独异点。 晓津证明如下：

反证法：若V不是独异点，则V不存在幺元. 而因为x是任意的，则当x=a时，有 a*u=v*a=a

即此时u,v分别是a的右、左幺元。因为在一个系统中若同时存在左右幺元，则二者必相等，因此此时u=v=e。这与假设矛盾，因此由V是一个半群，又V具有幺元，得知V是独异点。

________________________________________

6、设 V=是半群，OL?S是一个左零元，证明： x?S , x。OL也是一个左零元。

证明： V=是半群,故 。在S上是可结合的

29

x。OL=OL。x

根据定义4.1.5可知： OL。x=OL

故x。OL也是一个左零元 晓津不同意见：可结合不等于可交换。在这里应当把(x。OL)看作一个元素，这整个元素是一个左零元。另，题中应为 证明如下：

因为V是半群，所以运算是封闭的,可结合的。 若有x,y,OL?S， 则有x。OL?S

且有(x。OL)。y=x。(OL。y)=x。OL 即x。OL是S中任意y的左零元。

________________________________________

7、V=,其中 表示模4乘法，找出V的所有子半群，并说明哪些子半群是V的子独异点。 解：子半群如下：

V1=,V2=,V3=,V4=

其中V1,V2,V3 ,V4都是V的子独异点，因为这四个半群中均有幺元e=1。 ________________________________________

8、证明在一个独异点中，左逆元集合，形成子独异点。

证明如下：设为一个独异点，则它有一个幺元.

设在中e是关于*的幺元，若对于任意a?S，存在b?S且b*a=e，则b是a的左逆元。 令左逆元的集合为L，则L S, 所以*在L上是结合的。

对任意的a，b?L,

则必存在x,y?S,使a*x=e，b*y=e; 则(a*b)*(y*x)=a*(b*y)*x=a*e*x=a*x=e;

故a*b是y*x的左逆元， ∴a*b?L

∴*在L上是封闭的 (本段证明由阮允准补充)

即是一个半群。因为e是S中关于*的幺元，所以它同时也是L中关于*的幺元。 因此是一个子独异点。

________________________________________

9、设 是代数系统，其中 S={a,b,c,}，*定义为：

* a b c a a b c

30

b b a a c c a a

则 是否为半群？是否为独异点？为什么？ 答：从表中看： (b*c)*c=a*c=c b*(c*c)=b*a=b (b*c)*c≠b*(c*c)

故不是半群(本题答案由hybina提供，感谢hybina) 4.3习题参考答案

(本章习题答案由jhju提供，晓津补充。旨在抛砖引玉，欢迎到分课论坛发表不同意见) http://jjzk.yeah.net 题号：1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

________________________________________

1、设 为群，任意a,b,c?A, 证明 a*b=a*c，则 b=c。 证明：根据定理

4.3.4，设是一个群，对于a,b?G。必存在惟一的x?G,使 a*x=b 设 a*b=g 因为 a*b=a*c

所以 a*c=g

由于 b在A中是惟一的，而c在A中也是惟一。 所以 b=c

晓津的证明如下：

已知为群，则对于任意a,必逆元a-1和幺元e，则有： a-1*(a*b)=a-1*(a*c)

即有

(a-1*a)*b=(a-1*a)*c e*b=e*c

所以有b=c

________________________________________

2、设 是独异点，且H中任意x，有x*x=e,其中e为单位元，试证明： 是交换群。 证明：根据定理

4.2.2设是独异点，对于a,b?H,且a,b均有逆元。 那么根据定义4.3.1，可知 是群

交换群就是 *运算满足交换律的情况。 满足交换律就是 a*b=b*a

将 (a*b)*(b*a) 根据结合性可得 a*(b*b)*a=a*e*a=e

将 (b*a)*(a*b) 根据结合性可得 b*(a*a)*b=b*e*b=e 由于有

x*x=e ，而上述两个运算的结果，可知 a*b=b*a 根据定义4.3.4，可知其是一个交换群。

31

晓津证法如下：

设有任意a,b?H，e为幺元，则根据已知条件有： a*b=(e*a)*(b*e)

=(b*b*a)*(b*a*a)

=b*((b*a)*(b*a))*a

=b*e*a=b*a

可见a*b=b*a,即是交换群。

________________________________________

3、设G是整数加群，在G上定义运算*如下： a,b?G,a*b=a+b-2,证明： 是群。 证明：关于此题的疑惑， 假如 a=1 b=1 那么

a*b=0,0不是正整数了。那么就不能满足封闭性了。也有可能是我把题意给理解错了。

晓津观点，整数加群是指在整数集上进行加法运算的一个代数系统。而不仅仅是正整数上进行加运算，0也是包含在这个集合中的，所以满足封闭性。

证明如下：

(1)因为任意a,b?G，即a,b?Z，且a*b=a+b-2,可见a*b?Z，因此是封闭的。 (2)设有任意a,b,c?G，则 (a*b)*c

=(a+b-2)+c-2=a+b+c-4

a*(b*c) =a+(b+c-2)-2=a+b+c-4=(a*b)*c 可见G上关于* 运算是可结合的。

(3)在中存在幺元e=2 ，验证如下： 对于任意a?G，有a*e=a+2-2=a ，e*a=2+a-2=a

(4)对于任意a?G，存在逆元a-1 =4-a ,验证如下：a*a-1=a+(4-a)-2=2 ;a-1*a=4-a+a-2=2。

因此可证，是群。

________________________________________

4、设G= { ( 1 0 ) ( 1 0 ) (-1 0 ) (-1 0 ) ( 0 1 ) ( 0 -1) ( 0 1 ) ( 0 -1) } 证明： G关于矩阵乘法构成一个群。 运算表：

矩阵乘法 1 0 0 1 1 0 0 -1 -1 0 0 1 -1 0 0 -1 1 0

0 1 1 0

32

0 1 1 0 0 -1 -1 0 0 1 -1 0 0 -1 1 0 0 -1 1 0 0 -1 1 0 0 1 -1 0 0 -1 -1 0 0 1 -1 0

0 1 -1 0 0 1 -1 0 0 -1 1 0 0 1 1 0 0 -1 -1 0 0 -1 -1 0 0 -1 -1 0 0 1 1 0 0 -1 1 0 0 1

从运算表中可以看出其具有封闭性 并且其具有单位元 1 0 0 1

如何证明其具有结合性？晓津认为，仍旧可从表上看出。(表中色块表示(a*b)*d=a*(b*d)。*表示矩阵乘法。仅供理解用，证明时不必写出。)

另外可以每个矩阵乘以它本身，就等于其单位元，根据题二的结论

x*x=单位元，则说明是群。晓津观点：最后一步应找到每个元素有其逆元而不是单位元。仍从表上可以找到,每个元素本身就是它的逆元。因此G关于矩阵乘法构成一个群。

________________________________________ 5、设为一代数系统，*定义如下：

* α β γ δ

α α β γ δ β β α δ α γ γ δ β δ δ δ β β γ

问：是否构成群？为什么？

答：首先其满足封闭性，另外其有单位元 α 、但是其并非对每个元素均存在逆元，故其不构成群。 ________________________________________

6、设A={a,b}，试构造代数系统<(A),U>的运算表，并指出是否存在零元、幺元，并说明<(A)，U>是否构成群？为什

33

么？

∪ φ {a} {b} {a,b} φ φ {a} {b} {a,b} {a} {a} {a} {a,b} {a,b} {b} {b} {a,b} {b} {a,b} {a,b} {a,b} {a,b} {a,b} {a,b}

另外此题有印刷错误 U 应改为 ∪ 其有单位元 φ ,零元 {a,b}

，除φ外其他元素均无逆元，所以不构成群。

________________________________________

7、设 G={2m×5n | m,n?I},×:普通乘法，是否构成群？为什么？

对此不解，其没有说明 *是什么运算？所以 是否构成群也是个问题。

晓津的理解：题中的*应为×方合题意。只是这I是指什么集合倒也成问题，我且将它理解成实数吧。这样的话，则G是一个不包含0的实数集，在G上关于×运算是封闭的。 关于普通乘法，很显然它也是可结合的。

在实数集的普通乘法中，有幺元e=1,我们也可以确认，在G中对于m,n?I(现我将其理解为实数)，则必存在m，n使2m×5n=1.因此，是存在幺元的。

同样地，在实数集中的关于乘法的逆元x是x的倒数即x-1,由于G中不包含0，因此对于任一2m×5n有2-m×5-n 为其逆元。

可见构成群。

同学们有更好的理解和证法请不要独享啊。 ________________________________________

8、设 是半群，若存在左幺元，且每个元素均有右逆元，是不是群？为什么？

其是群，因为右逆元存在的条件便是先存在着单位元（参见P80定义4.1.6)，所以 存在幺元。根据定理4.1.4 ，因为是半群，所以其是可结合运算的，根据定理4.1.4，其必有 左逆元=右逆元 ，所以其是一个群。 ________________________________________

9、设G={[1],[2],[3],[4],[5],[6]},G上的二元运算×7 ,如下表所示：

×7 [1] [2] [3] [4] [5] [6] [1] [1] [2] [3] [4] [5] [6] [2] [2] [4] [6] [1] [3] [5] [3] [3] [6] [2] [5] [1] [4] [4] [4] [1] [5] [2] [6] [3] [5] [5] [3] [1] [6] [4] [2] [6] [6] [5] [4] [3] [2] [1]

问： 是循环群吗？若是，找出它的生成元。

答： 是循环群，生成元是[3], [3]=[3] [2]=[3]2 [6]=[3]3 [4]=[3]4 [5]=[3]5 [1]=[3]6

34

故G是六阶循环群。

Littletree同学指出还有一个生成元：[5] 因4=[5]2，6=[5]3,2=[5]4,3=[5]5,1=[5]6

________________________________________

10、设A={x|x?R∧x≠0,1}，在A上定义6个函数如下： f1(x)=x ,

f2(x)=x-1 ,f3(x)=1-x ,f4(x)=(1-x)-1 ,f5(x)=(x-1)x-1,

f6(x)=x(x-1)-1,令F={fi|i=1,2,....,6},函数的复合o是F上二元运算。

a) 求o的运算表。

b) 验证是一个群。

晓津答案： a)

o f1 f2 f3 f4 f5 f6

f1 x x-1 1-x (1-x)-1 (x-1)x-1 x(x-1)-1 f2 x-1 x (x-1)x-1 x(x-1)-1 1-x (1-x)-1 f3 1-x (1-x)-1 x x-1 x(x-1)-1 (x-1)x-1 f4 (1-x)-1 1-x x(x-1)-1 (x-1)x-1 x x-1 f5 (x-1)x-1 x(x-1)-1 x-1 x (1-x)-1 1-x f6 x(x-1)-1 (x-1)x-1 (1-x)-1 1-x x-1 x

b)(画完上面表格，真是头都大了)，我们可以看到，表中的所有元都在F内，因此运算是封闭的。有幺元e=f1,对于每个fi?F，都有逆元存在。因此运算是一个群。 ________________________________________

11、设G={a,b,c},在G上定义二元运算。如下表所示：

o a b c a a b c b b c a c c a b

a) 验证 为群；

b) 是否为循环群，如果是，找出它的生成元。 解： a)

从运算表中可以看 其具有封闭性。有幺元 a ，对于 b 有逆元 c ，对于 c有逆元 b 。同时可看出其具有结合性，如(a。b)。c=a。(b。c)=a

b) 其是循环群， b=b c=b2 a=b3 b是生成元。还有 c=c b=c2 a=c3 所以c也是生成元

________________________________________ 12、设是群的子群， N={x|x?G,xHx-1=H}。 证明：

是的一个子群。

35

晓津证明如下：

(1)设任意a,b?N，则必有aΔa-1和bΔb-1?H，由是的子群，可知a,b?H，且aΔb?H因此有(aΔb)Δ(aΔb)-1?H 可得aΔb?N。

(2)对应任意a?N，有aΔa-1?H，同时有a-1Δa?H，因此有a-1?N

所以(N，Δ)是(H，Δ)的子群，因为H?G,所以有N?G. ________________________________________

13、设G是交换群，证明G中一切有限阶元素所组成集合H是G的一个子群。

晓津提问：对于G中有限阶的理解 (1)是指G中的有限阶群，题意是指任何一个有限阶群都是G的一个子群?(2)还是指G中所包含的元素的阶是有限的且这些元素组成的集合是G的一个子群? 请兄弟MM们提供高见。 下面是阮允准同学的证明: 我认为是第2种理解。 证明如下：

设e是＜G，＊＞的幺元 显然e?H,

所以H是G的非空子集。

设任意的a,b?H，则必有正整数m,n使am=e, bn=e

由b*b-1=e,

所以(b*b-1)n=en 所以bn*(b-1)n=e e*(b-1)n=e

所以(b-1)n=e

(a*b-1)mn=amn*(b-1)mn=(am)n*((b-1)n)m=en*em=e 所以a*b-1?H 所以H?G

________________________________________

14、设G是一个群，～是G的元素间的等价关系，对任意 a,x,y?G,ax～ay=>x～y 证明：

H={x|x?G,x～e}是G的子群，其中e是G的幺元。

晓津证明如下：

我的理解是ax就是指a与x之间进行某种运算的意思。这里我且用*夹在其中表示.

(1)因为e?G，e～e,所以e?H, 若有任意a,x?H

则a,x?G，x～e，a～e可得x～a, 同时有x-1?G，所以有 a*x-1=x*x-1=e a*e＝e*e=e

36

即有a*x-1～a*e =〉x-1～e 因此有x-1?H

(2)设任意x,y?H，则有x,y?G，x～e,y～e

又因x*y?G，同上分析，若有任意a?H，有a～e,则 a*(x*y)=e*(e*e)=e； a*e= e；

即有a*(x*y)～a*e => (x*y)～e 所以x*y?H,

因此是的子群

________________________________________

15、 设,是两个群。在G1×G2上定义☆为：

☆=, 证明： 是一个群。

晓津证明如下：

(1)设有任意,?G1×G2 因为a1*a2?G1，b1Δb2?G2 所以?G1×G2 即☆?G1×G2 因此是封闭的。

(2)设有任意?G1×G2 则有(☆)☆ =☆ =

且☆(☆) =☆ =

可见，在G1×G2上关于☆运算是可结合的。

(3)因为在中有幺元e1,中有幺元e2, 所以在G1×G2上，对任意有

☆== 因此存在幺元e=.

(4)因为在中对每个元素a有逆元a-1，在中对每个元素b有逆元b-1,则 在G1×G2中，对任意有

☆===e

可得是一个群。 4.4习题参考答案

(本节习题答案由jhju提供，晓津补充。旨在抛砖引玉，欢迎请到分课论坛发表不同意见) http://jjzk.yeah.net

37

题号：1 2 3 4 5 6 7 8

________________________________________

1、已知一个环<{a,b,c,d},+,△>,它的运算如表4.4.2所示。

+ a b c d △ a b c d a a b c d a a a a a b b c d a b a c a c c c d a b c a a a a d d a b c d a c a c

请回答：

它是一个交换环吗？它有乘法幺元吗？这个环中的零元是什么？并求出每个元素的加法逆元。

解：<{a,b,c,d},+△>少了个逗号。应该是<{a,b,c,d},+,△>

解：它是一个交换环。因为

可以发现△运算在运算表中关于主对角线对称，所以<{a,b,c,d},△>是可交换的，所以根据定理4.4.2得知其是一个交换环。

此处没有乘法幺元。

环中的零元是根据后半部分运算来得到的。可以发现 a△x=a x△a=a，那么就可以判断 a是零元

每个元素的加法逆元： b元素的加法逆元是 d c元素的加法逆元是 c a的加法逆元是a。

________________________________________

2、设是一个环，并且对于任意的a?A，都有 a.a=a ,这个环称布尔环， 证明：a)对于任意的a?A,都有 a+a=θ，其中θ是加法幺元。 b) 是可交换环。 解： a)

jhju对教材一点看法： 环的定义中有这么一句：

是阿贝尔群，可是阿贝尔群是什么群呢？我翻了半天左孝凌的教材，没有这个名词的解释。无奈之中，只好翻了一下清华版教材，上面写着“若群G中的二元运算是可交换的，则称群G为交换群，也叫做阿贝尔群(Abel)群。而左孝凌的教材只写了一个abel群，并没有注明阿贝尔群。有的读者不是要被弄糊涂了？

浙江省考办在《计算机应用及教育》专业中《线性代数和离散数学》中指定的教材正是清华版的教材，而全国考办指定的教材不如省考办指定的教材。质量是生命，我觉得全国考办也应该反思一下。

根据环的定义： 是个交换群。 根据题意θ是幺元， a+θ=a θ+a=a a+a=(a+θ)+(θ+a)

根据交换律与结合律： a+a=(θ+θ)+(a+a)

38

晓津看法，上面的证明并没有完成。我觉得题目中的a+a=θ是不是应该改为a+a=a?

b) a.(b+c)=a.b+a.c

________________________________________

3、在整数环中定义*和o两个二元运算，对任意 a,b?Z 有： a*b=a+b-1

aob=a+b-ab

证明：是一个含幺环。

证明：可以很明显的看出 a*b 满足交换律、封闭性、结合律，故其是一个阿贝尔群

而 aob在Z中满足封闭性、结合律，故其是一个半群。

xo(y*z)=xo(y+z-1)=x+y+z-1-x(y+z-1)=x+y+z-1-xy-xz+x

xoy*xoz=(x+y-xy)*(x+z-xz)=x+y+z-1-xy-xz+x 得:xo(y*z)=(xoy)*(xoz)

同理可得： (x*y)oz=(xoy)*(xoz) 可见： o对于*是可分配的 是一个环

在Z中，aob=a+b-ab 0ob=b bo0=b 可见0是o运算中的幺元。 含有幺元，则 是含幺环。

________________________________________

4、设R1，R2是环，在R1×R2中定义两个二元运算*和o，对任意,?R1×R2，

*=

o=。

a) 证明 构成一个环； b) 若R1和R2是交换环（或含幺环），则R1R2也是交换环(或含幺环）。

c) 若R1和R2都是整环，R1×R2是整环吗？证明你的结论。

晓津证明如下： a)

因为R1，R2是环，则对于任意a1,a2?R1有

39

a1+a2?R1,a1*a2?R1 ，R2同理。所以： (1)

对于任意,?R1×R2 有

*=?R1×R2 并有

*=

再设任意?R1×R2，则显然有

*(*)=(*)* 同时有幺元e=<0,0>,使得： *<0,0>=

对任一元素有逆元<-a1,-b1>存在，使得 *<-a1,-b1>=<0,0>

可见在R1×R2中关于*运算是封闭的、可结合的、可交换的、存在幺元和各元素的逆元，因此它是一个阿贝尔群。 (2)对于任意的,?R1×R2，有 o=?R1×R2 若有?R1×R2，则显然地有：

o(o)=(o)o 可见是一个半群。

(3)对于任意的,,?R1×R2，则 o(*) =o =

可见o对*是可分配的。

因此是一个环。

b)要证明R1×R2是交换环(含幺环)只需在以上证明的基础上证明 可交换或含幺元。 如下：

因为R1，R2是交环，则对于a1,a2?R1及b1,b2?R2，有a1a2=a2a1、b1b2=b2b1, 因此若有任意,?R1×R2 则

o= o=

它们是相等的，即o运算可交换。

同样的，R1有幺元e1,R2有幺元e2,则对于任意?R1×R2，有 o=

即有幺元e=

可见，R1×R2是交换环(或含幺环)

(c)要证其为整环，则还需证明中无零因子。如下： 任取,?R1×R2，且≠<0，0>

40

本文来源：https://www.bwwdw.com/article/zq16.html