离散数学复习资料及试题.doc

离散数学复习资料和试题 集合论 集合与集合之间的关系, 元素与集合之间的关系 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为假命题幂集：ρ（A）就是集合A中子集所组成的集合 求下列集合的幂集： （1）{a，{a}}={?，{a}，{{a}}，{a，{a}}} （2）{?，a，{a}}={?，{?}，{a}，{{a}}，{?，a}，{?，{a}}，{a，{a}}，{?，a，{a}}} 集合的运算：10组集合恒等式： 交换率：A∪B=B∪A；A∩B=B∩A 结合律：A∪（B∪C）=（A∪B）∪C；A∩（B∩C）=（A∩B）∩C 分配律：A∪（B∩C）=（A∪B）∩（A∪C）；A∩（B∪C）=（A∩B）∪（A∩C） 同一律：A∪?=A；A∩E=A 零一律：A∩?=?；A∪E=E 互补率：A∪~A=E；A∩~A=?；~E=?；~?=E 双重否定率：~~A=A 幂等率：A∪A=A；A∩A=A 吸收率：A∪（A∩B）=A；A∩（A∪B）=A 德摩根率：~（A∪B）=~A∩~B；~（A∩B）=~A∪~B 交：A∩B；并：A∪B；差运算：A—B（属于A不属于B）；补运算：~A； 对称差运算：A?B；笛卡儿乘积：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} 集合的计数问题：|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 | 关系的性质:①由图写出性质 ②有性质画图 ③由关系集合写性质 （自反性，反自反性，对称性，反对称性，传递性：）P34 ##2.6 用图表示出来的在集合X={1，2，3}上的关系的6个图形，从图中可以清楚的看出： R1 是自反的、对称的、又是传递的（它是一个全关系）； R2是反自反的、反对称的 R3不是反自反的、反对称的 R4是自反的、反对称的 R5是反自反的、对称的、反对称的、传递的（它是一个空关系）  映射与关系 6．设集合A={a1，a2，a3，a4}，B={ b1，b2，b3}，σ={〈a1，b2〉，〈a2，b2〉，〈a3，b1〉，〈a4，b3〉}则σ是满射但不是单射 关系的闭包：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上的二元关系： R1={〈a，a〉，〈b，b〉，〈b，c〉，〈d，d〉} R2={〈a，a〉，〈b，b〉，〈b，c〉，〈c，b〉，〈d，d〉}试证明R1是R2的何种闭包 解：R1∪~R1 ={〈a，a〉，〈b，b〉，〈b，c〉，〈d，d }，〈c，b〉} 即有R1∪~R1= R2 根据对成闭包的定义及求解方法只R2是R1 的对称闭包 2.设集合A={a，b，c，d}，定义R={〈a，b〉，〈b，a〉，〈b，c〉，〈c，d〉}求r(R)，s(R)，t(R) 解：r(R)= {〈a，a〉，〈b，b〉，〈c，c〉，〈d，d〉，〈a，b〉，〈b，a〉，〈b，c〉，〈c，d〉} s(R)={ 〈a，b〉，〈b，a〉，〈b，c〉，〈c，b〉，〈c，d〉，〈d，c〉} t(R)={ 〈a，a〉，〈b，b〉，〈a，b〉，〈a，c〉，〈a，d〉，〈b，a〉，〈b，c〉，〈b，d〉，〈c，d〉} 3.由关系集合写性质 设A={a，b，c}，R={〈a，a〉，〈b，b〉}，具有反对称性  关系的运算(复合运算) R1R2 1.设X={0，1，2，3}，X上有两个关系：R1={〈i，j〉|j=i+1或j=i/2}；R2={〈i，j〉|i=j+2} 求复合关系：R1R2 R1={ 〈0，1〉，〈1，2〉，〈2，3〉，〈0，0〉，〈2，1〉}，R2= {〈2，0〉，〈3，1〉}则有： R1R2= {〈1，0〉，〈2，1〉} 2.设R1，R2是集合A={1，2，3，4}上的二元关系，其中R1={〈1，1〉，〈1，2〉，〈2，4〉}，R2={〈1，4〉，〈2，3〉，〈2，4〉，〈3，2〉}，试求：R1R2 解：R1R2=〈1，4〉，〈1，3〉} 特殊关系 等价关系: 1.A={0,1,2,4,5,8,9},R为A上模为4的同余关系，求(1)R的所有等价类 (2)画出R的关系图 解：R={