离散数学(集合论)课后总结.doc

螀第三章集合论基础葿1、设A={a,{a},{a,b},{{a,b},c}}判断下面命题的真值。螈⑴{a}∈AT⑵Ø({a}ÍA)F袄⑶c∈AF⑷{a}Í{{a,b},c}F螃⑸{{a}}ÍAT⑹{a,b}∈{{a,b},c}T蕿⑺{{a,b}}ÍAT⑻{a,b}Í{{a,b},c}F袅⑼{c}Í{{a,b},c}T⑽({c}ÍA)®(a∈Φ)T薆2、证明空集是唯一的。(性质1:对于任何集合A,都有ΦÍA。)薂证明:假设有两个空集Φ1、Φ2,则虿因为Φ1是空集,则由性质1得Φ1ÍΦ2。芆因为Φ2是空集,则由性质1得Φ2ÍΦ1。肄所以Φ1=Φ2。莁3、设A={Φ},B=P(P(A)).问:(这道题要求知道幂集合的概念)蝿a)是否Φ∈B?是否ΦÍB?蚇b)是否{Φ}∈B?是否{Φ}ÍB?螅c)是否{{Φ}}∈B?是否{{Φ}}ÍB?莄解:设A={Φ},B=P(P(A))P(A)={Φ,{Φ}}衿在求P(P(A))时,一些同学对集合{Φ,{Φ}}难理解,实际上你就将{Φ,{Φ}}中的元素分别看成Φ=a,{Φ}=b,于是{Φ,{Φ}}={a,b}肇B=P(P(A))=P({a,b})={B0,B1,B2,B3}={B00,B01,B10,B11}={Φ,{b},{a},{a,b}}芃然后再将a,b代回即可B=P(P(A))=P({Φ,{Φ}})={Φ,{Φ},{{Φ}},{Φ,{Φ}}}膂以后熟悉后就可以直接写出。罿a)Φ∈BΦÍB蒈b){Φ}∈B{Φ}ÍB羅c){{Φ}}∈B{{Φ}}ÍB袁a)、b)、c)中命题均为真。罿4、证明AÍBÛA∩B=A成立。蚅证明:A∩B=AÛ"x(x∈A∩B«x∈A)莃Û"x((x∈A∩B®x∈A)∧(x∈A®x∈A∩B))蚀Û"x((xÏA∩B∨x∈A)∧(xÏA∨x∈A∩B))肈Û"x((Ø(x∈A∧x∈B)∨x∈A)∧(xÏA∨(x∈A∧x∈B))肆Û"x(((xÏA∨xÏB)∨x∈A)∧(xÏA∨(x∈A∧x∈B)))肅Û"x(T∧(T∧(xÏA∨x∈B)))蚃Û"x(xÏA∨x∈B)Û"x(x∈A®x∈B)ÛAÍB膈5、(A-B)-C=(A-C)-(B-C)蒇证明:任取x∈(A-C)-(B-C)薃Ûx∈(A-C)∧xÏ(B-C)蒂Û(x∈A∧xÏC)∧Ø(x∈B∧xÏC)芈Û(x∈A∧xÏC)∧(xÏB∨x∈C)袈Û(x∈A∧xÏC∧xÏB)∨(x∈A∧xÏC∧x∈C)芅Ûx∈A∧xÏC∧xÏBÛx∈A∧xÏB∧xÏC芁Û(x∈A∧xÏB)∧xÏC莈Ûx∈A-B∧xÏCÛx∈(A-B)-C艿所以(A-B)-C=(A-C)-(B-C)螃6、A-(B∪C)=(A-B)∩(A-C)芄证明:任取x∈A-(B∪C)蒈Ûx∈A∧xÏ(B∪C)莆Ûx∈A∧Ø(x∈B∨x∈C)蒄Ûx∈A∧(xÏB∧xÏC)肃Û(x∈A∧xÏB)∧(x∈A∧xÏC)薈Ûx∈A-B∧x∈A-C螆Ûx∈(A-B)∩(A-C)膆所以A-(B∪C)=(A-B)∩(A-C))螁7、~(A∩B)=~A∪~B~(A∪B)=~A∩~B这两个公式称之为底-摩根定律。薈证明:任取x∈~(A∩B)膇x∈~(A∩B)蚄ÛxÏA∩BØÛ(x∈A∧x∈B)薀Û(xÏA∨xÏB)Ûx∈~A∨x∈~B蚈Ûx∈~A∪~B ∴~(A∩B)=~A∪~B薈8、AÍBÛ~BÍ~A莆证明:AÍBÛ"x(x∈A®x∈B)蚃Û"x(xÏB®xÏA)Û"x(x∈~B®x∈~A)螇Û~BÍ~A蚅9、~A=B当且仅当A∪B=E且A∩B=Φ螄证明:A∪B=E∧A∩B=Φ莂Û"x(x∈A∪B«x∈E)∧(P«TÛP)袇"x(x∈A∩B«x∈Φ)(P«FØÛP)肆Û"x(x∈A∪B«T)∧"x(x∈A∩B«F)蒆Û"x(x∈A∪B∧Ø(x∈A∩B))膁Û"x((x∈A∨x∈B)∧Ø(x∈A∧x∈B))膁Û"x((x∈A∨x∈B)∧(xÏA∨xÏB))蒇Û"x((xÏA®x∈B)∧(x∈B®xÏA))羄Û"x((x∈~A®x∈B)∧(x∈B®x∈~A))膄Û"x((x∈~A«x∈B)芁Û~A=B袈蚆关于对称差羃A、B是集合,由属于A而不属于B,或者属于B而不属于A的元素构成的集合,称之为A与B的对称差,记作AÅB。例如A={1,2,3}B={2,3,4}AÅB={1,4}莁谓词定义:AÅB=(A-B)∪(B-A)={x|(x∈A∧xÏB)∨(x∈B∧xÏA)}荿AÅB=(A∪B)-(A∩B)膃螂10、∩对Å可分配A∩(BÅC)=(A∩B)Å(A∩C)蒁证明:(A∩B)Å(A∩C)蒅=((A∩B)∪(A∩C))-((A∩B)∩(A∩C))袅=(A∩(B∪C))-(A∩B∩C)蒀=A∩((B∪C)-(B∩C))(∩对-分配)薁=A∩(BÅC)袆但是∪对Å不可分配,举反例:芃A∪(AÅB)=