离散数学第二次作业

第二次作业

1、使用包含排斥原理求在1~10000之间（包括1和10000在内）不能被4、5、6

整除的整数有多少个？（见书P107 24）

解:|A|=[10000/4]=2500

|B|=[10000/5]=2000

|C|=[10000/6]=1666

|A∩ B|=[1000/lcm(4,5)]=[10000/20]=500

|A∩ C|=[1000/lcm(4,6)]=[10000/12]=833

|B∩ C|=[1000/lcm(5,6)]=[10000/30]=333

|A∩ B ∩ C|=[1000/lcm(4,5,6)]=[10000/60]=166

|¯A ∩¯B ∩¯C|=|S|-(|A|+|B|+|C|)+(|A∩ B|+|A∩ C|+|B∩ C|)-|A∩ B ∩ C|

=10000-(2500+2000+1666) +(500+833+333) -166=5334

2、证明下列集合恒等式：（见书P108 33）

（1）A∩（B∪~A）= B∩A

证对任意的X ,有

X ∈A ∩(B ∪~A) ⇔x ∈A ∧X ∈(B ∪~A)

⇔X ∈A ∧(X ∈B ∨X ∈~A)

⇔X ∈A ∧(X ∈B ∨X ∉ A )

⇔X ∈A ∧(X ∈B ∨⌝X ∈A )

⇔X ∈A ∧X ∈B

⇔A ∩B

⇔B ∩A

所以 A ∩(B ∪~A) = B∩

（2）~（（~A∪~B）∩~A）=A

证~((~A∪~B)∩~A) =(~A∪~B)∩~A双重否定律

= ~A吸收律

=A双重否定律

3、设A={<1,2>,<2,4>,<3,3>}

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

求A∪B，A∩B，domA，domB，dom（A∪B），ranA，ranB, ran(A∩B), fld(A-B) A ∪B={<1,2>,<2,4>,<3,3>, <1,3>,<4,2>}

A ∩B={<2,4>}

A-B={<1,2>, <3,3>, <1,3>, <4,2>}

domA={1,2,3}

domB={1,2,4}

dom (A ∪B ) ={1,2,3,4}

ranA={2,4,3}

ranB={3,4,2}

ran(A∩B)={4}

fld(A-B)={1,2,3,4}

4、设A={a,b,c,d}, R1, R2为A上的关系，其中

R1={,,}

R2={,,,}

求R1︒ R2，R2︒ R1，R12，R23 （见书P140 16）

解: R1︒ R2={,,}

R2︒ R1={}

R12= R1︒R1{,,}

R22= R2︒ R2={,,}

R23= R2︒ R22={,,}