第2~3章-习题讲解课件

P60习题2.19.设ABC是集合，如果AB和

BC，AC可能吗？AC常真吗？试举例说明。AC可能但不常真例如：A＝{a}B＝{{a}}C＝{{{a}},{a}}ACA＝{a}B＝{{a}}C＝{{{a}}}AC

*10.设ABC是集合，证明或否定以下断言：（1）〔A

B∧B

C〕A

C（3）〔A

B∧B

C〕A

C（1）假A＝{a}B＝{b}C＝{{a}}（3）假A＝{a}B＝{a,b}C＝{{a}}12.设AB且A

B可能吗？A＝{a}B＝{a,b,{a}}可能14.对任意的集合ABC，确定下列命题是真或假：（1）如果A

B及B

C

，则A

C（3）如果A

B及B

C

，则A

C（1）真（3）假

x(

xBxC)

证：B

C

ABAC反例：A＝{a}B＝{a，b}C＝{{a，b}}A

B

ACQ1I3P70习题2.2*9.（1）证明“相对补”不是一个可交换运算，即证明存在一个论述域包含集合A和B，使A－BB－A证明：举反例A＝{a}B＝{b}A－B＝{a}B－A＝{b}不相等即A－BB－A12.证明下列恒等式：（1）A∪(A∩

B)＝A（4）A∪(A∩

B)＝A∪B

_（1）证明：

∵

A∩

B

AA∪(A∩

B)＝A得证。（4）证明：A∪(A∩

B)＝(A∪

A)

∩(A

∪

B)__＝A∪B或上式＝A∩(A∪B)，再由AA∪B得A。18.指出下列集合的幂集合:（3）设A＝｛a｝，求A和（A）的幂集。解：

（A）＝｛，｛a｝｝（（A））＝｛，｛｝，｛｛a｝｝，｛,｛a｝｝｝2.如果P89习题2.5A＝{a，b}和B＝{c}，试确定下列集合：（1）A×{0,1}×B*（3）(A×B)2解：

（1）A×{0,1}×B＝{a,b}×{0,1}×{c}＝{a,0,c,a,1,c,b,0,c,b,1,c}（3）(A×B)2＝{{a，b}×{c}}

×

{{a，b}×{c}}＝{a,c,b,c}

×

{a,c,b,c}＝{

a,c,a,c

,

a,c,b,c

,

b,c,a,c

,

b,c,b,c

}3.设A＝{0，1}，构成(A)×

A(A)×

A＝｛，｛0｝，｛1｝，｛0,1｝｝×{0,1}＝{

,0,,1,｛0｝,0,｛0｝,1,｛1｝,0,｛1｝,1,｛0,1｝,0,｛0,1｝,1}解：

(A)＝｛

，｛0｝，｛1｝，｛0,1｝｝*5.试证明A×

B=B×A

A=∨B=∨A=B当A=∨B=∨A=B证明：易知A×

B=B×A““““A×

B=B×A若A

∧B

∧ABaA，但是aB，bB则

a，b

A×

B

，而a

，b

B×A

这与

A×

B=B×A矛盾反证法3.对下列关系R，求出关系矩阵MRP97习题3.1（3）A＝{5，6，7，8}，B＝{1，2，3}R＝{x,y|xA∧yB∧3

x-y7}解：R＝{5,1,5,2,6,1,6,2,6,3,7,1,7,2,7,3,8,1,8,2,8,3}

MR＝56781230111111111115.设A＝{1，2，3，4}，R＝{1,2，2,4，3,3}S＝{1,3，2,4，4,2}（1）求出R∪S，R∩S，R－S，R解：R∪S＝{1,2，2,4，3,3

，

1,3，4,2}R∩S＝{2,4}R－S＝{1,2，3,3}R＝{1,1,1,3,1,4,2,12,2

2,3,3,1,3,2,

3,4,4,1,4,2,4,3,4,4}A×A＝{1,1,1,2,1,3,1,4,2,12,2

2,3,2,4,3,1,3,2,3,3,3,4,4,1,4,2,4,3,4,4}8.写出以下各关系所具有的特性。解：(a)反对称、传递(d)反对称(b)自反、对称、传递(c)反自反、对称(e)反自反、反对称、传递(f)反自反、反对称NY10.确定整数集合I上的相等关系、关系、<关系、全域关系、空关系是否具有定义3.1－5中指出的特性。＝<I×I自反的反自反的对称的反对称的传递的YNYYYNNYYYYYYYYYNNNYYNY基数大于1≠

NNYNY*11.设A＝{1，2，3，4}，A的下列关系是否可传递？如果是不可传递的，举出反例证明，然后找出一个具有最少序偶的关系，使R包含原关系并且是可传递的。(2)R＝{1,2，2,2}(4)R＝{1,2，4,3，2,2，2,1，3,1}(2)R是可传递(4)1,22,11,14,33,14,14,11,24,23,11,23,2R＝{1,2，4,3，2,2，2,1，3,1,1,1,4,1,4,2,3,2}需反复检查！YYYYYYYYYYYY

13.考察关系原有的特性在各种运算下是否保持。如：两自反关系的并是自反的，即自反性质在并运算下是保持的。R∪SR∩SR－S

自反的反自反的对称的反对称的传递的NYYYYNNNYNRNNNR·S（后两行详见P104习8及P109习4）YNNNNP104习题3.22.设R1

和R2是A＝{0，1，2，3}上的关系，这里R1={i,j|j=i+1或j＝i/2}R2={i,j|i

=j+2}求出R1

R2,R2

R1,

R1

R2R1,R12

,R23解：

R1={0,0,0,1,1,2,2,3,2,1}R1

R2={1,0,2,1}

R2R1={2,0,2,1,3,2}R1

R2R1={1,0,1,1,2,2}R22

=R12={0,0

,0,1,0,2,1,3,2,2,1,1}R23

=R2={2,0,3,1}b,d

(R2∪R3)R4c

[b,cR2∪R3∧

c,dR4]c

[(

b,cR2∨b,cR3

)

∧

c,dR4]

c

[(b,cR2∧c,dR4)∨(b,cR3∧c,dR4)]

c(

b,cR2∧c,dR4

)

∨

c(

b,cR3∧c,dR4)b,dR2R4∨

b,dR3R4b,d

R2R4∪R3R4即b,d

(R2∪R3)R4

b,d

R2R4∪R3R4a,c

所以证明：4.证明定理3.2-1(3)(R2∪R3)R4=R2R4∪R3R4(R2∪R3)R4=R2R4∪R3R4设b,c,d分别属于B,C,D8.设R1

和R2是A上的任意关系，证明或否定下列断言：（1）如果R1

和R2都是自反的，那么R1

R2是自反的（1）结论成立证明：xAx,xR1x,xR2x,xR1R28.设R1

和R2是A上的任意关系，证明或否定下列断言：（2）如果R1

和R2都是反自反的，那么R1

R2是反自反的（2）结论不成立反例：

A={0,1}R1={0,1

}R2={1,

0}R1R2={0,0

}都是反自反的不是反自反的8.设R1

和R2是A上的任意关系，证明或否定下列断言：（3）如果R1

和R2都是对称的，那么R1

R2是对称的（3）结论不成立反例：

A={0，1，2}R1={0,1

，1,

0}R2={1,

2，2,

1}R1R2={0,2

}都是对称的不是对称的8.设R1

和R2是A上的任意关系，证明或否定下列断言：（4）如果R1

和R2都是反对称的，那么R1

R2是反对称的（4）结论不成立反例：

A={0，1}R1={0,1

，1,

1}R2={1,

0，1,

1}R1R2={0,0

,0,1

,1,0,1,

1}都是反对称的不是反对称的8.设R1

和R2是A上的任意关系，证明或否定下列断言：（5）如果R1

和R2都是传递的，那么R1

R2是传递的（5）结论不成立反例：

A={0,1,2,3,4}R1={0,1

，2,

3}R2={1,

2，3,

4}R1R2={0,2

,2,4

}都是传递的不是传递的*9.设R1

、

R2和R3是A上的二元关系，证明合成运算保持集合的包含关系：10.设A＝{1,2,…,5}，R

={1,2,3,

4,2,2},S

={4,2,2,

5,3,1,1,3}试求出MR•S解：R•S={1,5,3,

2,2,5}【建议用矩阵乘法求】MR•S=12345000000010012345000000000011000P109习题3.34.关系的逆保持原关系的所有特性。按逆和各特性的定义证即可。（c）自反闭包*7.找出图3.3-2中每一个关系的自反、对称和传递闭包。（a）自反闭包对称闭包传递闭包（b）传递闭包对称闭包对称闭包传递闭包自反闭包8.设R是A＝{1,2,3,4}上的二元关系，其关系矩阵是MR=1111000010110100试求出Mr(R)，

Ms(R)，2M

R3M

R4M

R，

Mt(R)，，Mr(R)

=1111010010110101Ms(R)

=1111001110111110最好写上公式！解：要求用矩阵计算！11110000111100003M

R4M

R11110000101101002M

R=MR•MR=•=111100001011010011110000111100002M

R==MR•11110000101101001111000011110000•=1111000011110000==11110000MR=10110100要求计算步骤！=2M

R3M

R=4M

R=3M

RMt(R)=MR∪R2∪R3∪R4=MR∨2M

R3M

R∨∨4M

R1111000011110100=2M

R11110000MR=101101001111000011110000=9.设是R1和R2集合A上的关系且R1

R2，那么2)s(R1)

s(R2)证明：R1

R2R1

R2~~s(R1)=R1∪R1~R1∪R1R2∪R2~~s(R2)=R2∪R2~s(R1)

s(R2)每步有依据！*10.设R1

和R2是A上的任意关系，证明下列各式：（2）s(R1∪R2)=s(R1)∪s(

R2)s(R1∪R2)=(R1∪R2)∪(R1∪R2)

=(R1∪R2)∪(R1∪R2)

~~=(R1∪R1)∪(R2∪R2)

~~=s(R1)∪

s(R2)14.(1)画t(R)

图（5）P119习题3.4图3.4-10中给出了偏序集合A,R

的哈斯图，这里A＝{a,b,c,d,e}

（3）求出A的最小元素和最大元素，如果不存在，则指出不存在。（4）求出A的极大元素和极小元素。（5）求出子集{b,c,d}、

{c,d,e}和{a,b,c}的上界和下界，并指出这些子集的lub和glb，如果它们存在的话。

abdce（3）最小元素：最大元素：不存在a（4）极大元素极小元素ad,e上界：a下界：dlub=aglb=d上界:a、c下界:不存在lub=cglb不存在上界：a下界：dlub=aglb=d{

b,c,d}{

c,d,e}{

a,b,c}5.图3.4-11中有向图哪些代表偏序集合、拟序集合、线序集合？（a）是偏序、等价关系（b）是偏序、线序（c）是拟序（d）都不是（e）是偏序（f）是偏序（e）abcdabcd（f）abcdadbc6.将上题（e）、（f）两个有向图改成哈斯图9.证明下列断言：如果R是偏序，R也是偏序～（2）证明：①R是偏序，R必自反xA，有x,xRx,xRx,x

R～

自反R～②R是偏序，R必反对称x,yRy,x

R～y,xRx,yR～

反对称R～③R是偏序，R必传递的R～x,y∧y,zR～y,xR∧z