离散数学复习资料

发布时间：2024-11-10

自考离散数学复习资料

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); 正确

自考离散数学复习资料

不成立的。

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=φ

自考离散数学复习资料

本题要注意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∩～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}

自考离散数学复习资料

不成立

补充实例：设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∩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不可能含有

自考离散数学复习资料

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,y>| x X,y Y}

X×Z={<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,y>

}(x<y)∨(x是质数)},写出R各元素，并求出 domR,ranR及FLDR。解：议论一下R={<x,y>

}(x<y)∨(x是质数)} ,我认为∨应改为∧。不然的话(x是质数)这个条件将不起作用。 R={<0,1>,<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都不是质数,相应的，在下面的答案里，也应把红色字去掉。

自考离散数学复习资料

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：<a,b>R,iff(a-b)/2是整数，称R为模2同余系，亦可称<a,b> 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> |

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,b>

| a-b 是偶数}。

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

c) 在所有人集合P上的关系， {<a,b> | 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={<x,x>,<y,y>,<z,z>,<u,u>,<v,v> <z,u>,<u,z>,<u,v>,<v,u>,<z,v>,<v,z>}

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

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

且<y,x> S因此 <y,x> R∩S 即R∩S是对称的。

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

所以R∩S是可传递的。

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

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

即有<a,a>，<b,b> S，因此S是自反的。

若R是对称的和传递的，则由<a,c> R,<c,b> R

必有<a,b> R，同时有<c,a>，<b,c> R则必有<b,a> R 所以S是对称的，也是传递的。 6、设Z是整数集 R={<x,y)| x≡y(mod.K)},证明 R是自反、对称和传递的。证明：设任意a,b,c Z，

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

K)成立，<b,a> R,故R是对称的。若<a,b> R且<b,c> R，即

自考离散数学复习资料

且b≡c(mod K)

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

即<a,c> R，故R是传递的。

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

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

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

必要有<a,c> R，所以应有<a,b>,<b,a>,<a,c>,<b,c>在R中。

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

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

1、设： A={1,2,3}上关系R={<x,y>| 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 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={<a,a>,<a,b>}

r(R)={<a,a>,<a,b>,<b,b>,<c,c>} s(R)={<a,a>,<a,b>,<b,a>} 为了求：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 |

自考离散数学复习资料

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

| 0 0 0 | | 0 0 0 |

可见： t(R)=MR ∪MR^2∪MR^3={<a,a>,<a,b>} 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>}

自考离散数学复习资料

| 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|<x,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中有任意<x1,y1> R1 ，任意<x2,y2> R2 则有<x1,y1> t(R1) <x2,y2> t(R2)

(1)因为<x1,y1>,<x2,y2> (R1∪R2) (2)则有<x1,y1>,<x2,y2> t(R1∪R2)(3)

因此由(1)(2)(3)式可得：t(R1∪R2) t(R1)∪t(R2);

自考离散数学复习资料

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

{<x2,x1>,<x1,x2>,<x3,x1>,<x1,x3>,<x3,x2>,<x2,x3>,<x4,x3><x5,x2>,<x2,x5>,<x5,x3>,<x3,x5>,<x5,x4> ,<x4,x5>,<x6,x1>,<x1,x6>,<x6,x3>,<x3,x6>,<x6,x5>,<x5,x6>} 晓津觉得覆盖中的元素应该是集合：我的答案是： 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，则<x,x> α且<x,x> β，所以<x,x> α∪β 因此α∪β是自反的。

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

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

晓津证明如下：

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

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

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

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

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

自考离散数学复习资料

∴＜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是一个等价关系，当且仅当若 <a,b> R,<a,c> R,则<b,c> R。证明：由于R是一个等价关系，所以R是传递的。由此可知：若<a,b> R,根据对称性，则有<b,a> R 已知： <b,a> R且<a,c> R,根据传递性，必有 <b,c> R

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

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

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

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

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

又因为R是传递的，由<b,a>,<a,c> R，有<b,c> R

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

对任意的<a,b>,<b,c> R 由R是对称的 ∴<b,a> R

∴由<b,a> R，<b,c> R 可得<a,c> 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上的一个等价关系。

自考离散数学复习资料

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

若有<a,b> R 且 <b,c> R,则有<a,c> R

由于R又具有对称性，所以<b,a> R 且 <c,b> R,则有<c,a> R R-1 也有：<b,a> R-1

且<c,b> R-1 ,则有<c,a> R-1 可见：<b,a> R∩R-1

且<c,b> R∩R-1 ,则有<c,a> R∩R-1

R是A上的对称关系，则有 <a,b> R、<b,a> R R-1 是A上的对称关系，也有 <a,b> R、<b,a> R 则有： <a,b> R∩R-1 、<b,a> R∩R-1 由于R∩R-1

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

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

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

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

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