离散数学复习资料和试题

离散数学复习资料和试题 集合论 1. 集合与集合之间的关系, 元素与集合之间的关系 1．判别下列各题是否正确： （1）{1，2}{1，2，3，{1，2，3}} 正确 （2）{p，q，r}{ p，q，r ，{ p，q，r }} 正确 2．设有集合Ａ＝｛a,b,c｝，为空集，则｛a｝Ａ 3．设S1=，S2={}，S3=ρ({})，S3=ρ()，则：S2 ∈S4 为假命题 2. 幂集：ρ（A ）就是集合A 中子集所组成的集合 求下列集合的幂集： （1）{a，{a}}={，{a}，{{a}}，{a，{a}}} （2）{，a，{a}}={，{}，{a}，{{a}}，{，a}，{，{a}}，{a，{a}}，{，a，{a}}} 3. 集合的运算：10 组集合恒等式： 1） 交换率：A∪B=B∪A；A∩B=B∩A 2） 结合律：A∪（B∪C）=（A∪B）∪C；A∩（B∩C）=（A∩B）∩C 3） 分配律：A∪（B∩C）=（A∪B）∩（A∪C）；A∩（B∪C）=（A∩B）∪（A∩C） 4） 同一律：A∪=A；A∩E=A 5） 零一律：A∩=；A∪E=E 6） 互补率：A∪~A=E；A∩~A=；~E=；~=E 7） 双重否定率：~~A=A 8） 幂等率：A∪A=A；A∩A=A 9） 吸收率：A∪（A∩B）=A；A∩（A∪B）=A 10） 德摩根率：~（A∪B）=~A∩~B；~（A∩B）=~A∪~B 交：A∩B；并：A∪B；差运算：A—B（属于A 不属于B）；补运算：~A； 对称差运算：AB；笛卡儿乘积：A×B={|a∈A，b∈B} 设A={a，b，c}，B={b，d，e}则A—B={a，c}，AB={a，c，d，e} 4. 集合的计数问题：|A|=2 n (n 是集合A 的元素的个数) | A∪B |=|A|+|B|—| A∩B |；|A∪B∪C|=|A|+|B|+|C|—| A∩B |—| A∩C |—|B∩C|+| A∩B∩C | 5. 关系的性质:①由图写出性质 ②有性质画图 ③由关系集合写性质 （自反性，反自反性，对称性，反对称性，传递性：）P34 ##2.6 用图表示出来的在集合X={1，2，3}上的关系的6 个图形，从图中可以清楚的看出： （1）R1 是自反的、对称的、又是传递的（它是一个全关系）； （2）R2 是反自反的、反对称的 （3）R3 不是反自反的、反对称的 （4）R4 是自反的、反对称的 （5）R5 是反自反的、对称的、反对称的、传递的（它是一个空关系） 6. 映射与关系 6．设集合A={a1，a2，a3，a4}，B={ b1，b2，b3}，σ={〈a1，b2〉，〈a2，b2〉，〈a3，b1〉，〈a4，b3〉}则σ 是满射但不是单射 7. 关系的闭包：r(R)=R∪IA┎ ；s(R)=R∪~R；t(R)=R∪R 1∪R 2∪R 3„„∪R n 1．设A={a，b，c}，R1、R2 是A 上的二...