离散数学复习资料和试题.doc
《离散数学复习资料和试题.doc》由会员分享，可在线阅读，更多相关《离散数学复习资料和试题.doc（13页珍藏版）》请在冰点文库上搜索。
离散数学复习资料和试题
集合论
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|=2n（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∪R1∪R2∪R3……∪Rn
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〉}，具有反对称性
8.关系的运算（复合运算）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〉}
9.特殊关系等价关系:
1.A={0,1,2,4,5,8,9},R为A上模为4的同余关系，求
（1）R的所有等价类
（2）画出R的关系图
解：
R={〈0，0〉，〈1，1〉，〈2，2〉，……，〈9，9〉，〈0，4〉，〈4，0〉，〈1，5〉，〈5，1〉，〈4，8〉，〈8，4〉，〈5，9〉，〈9，5〉，〈0，8〉，〈8，0〉，〈1，9〉，〈9，1〉}
（1）[0]R={0,4,8}=[4]R=[8]R;[1]R={1,5,9}=[5]R=[9]R;[2]R={2}
（2）
2.A={a,b,c,d}A的等价关系R={〈a，a〉，〈b，b〉，〈c，c〉，〈d，d〉，〈a，b〉，〈b，a〉，〈8，4〉，〈c，d〉，〈d，c〉}求
（1）图
（2）A的等价类（3）A/R（商集）
解：
（1）
（2）[a]R=[b]R={a,b}[c]R=[d]R={c,d}（3）A/R={{a,b},{c,d}}
3.A={,1,2,4,……,24}上定义R={|x，y∈A，且（x—y）能被12整除}
（1）写出R
（2）画图（3）证明R是等价关系
解：
（1）R={<1，1>,<2，2>,……<24，24>,<1，13>,<2，14>,……<12，24>,<24，12>}
（2）
（3）（定义法）若证明R为等价关系，只需证明R具有自反性，对称性，传递性
①自反性：
"x∈A，则∈R所以R具有自反性
②对称性：
若∈R，则12|（x—y），y—x=（—x+y）
所以12|（y—x），故∈R，所以R具有对称性
③传递性：
如果∈R，且∈R，则12|（x—y）且12|（y—z）
则x—z=（x—y）+（y—z）能被12整除，故12|（x—z），∈R
所以R具有传递性
综上所述，R为等价关系
偏序关系
1.集合X={2,3,6,8},上的整除关系R={〈2，2〉，〈3，3〉，〈6，6〉，〈8，8〉，〈2，6〉，〈2，8〉，〈3，6〉}是偏序的，求其哈斯图
2.集合A={2，3，6，12，24，36}上的整除关系R是偏序的，它可用哈斯图表示
R={〈2，2〉，〈3，3〉，〈6，6〉，〈12，12〉，〈24，24〉，〈36，36〉，
〈2，6〉，〈3，6〉，〈6，12〉，〈12，24〉，
〈2，12〉，〈3，12〉，〈6，24〉，〈12，36〉
〈2，24〉，〈3，24〉，〈6，36〉，
〈2，36〉，〈3，36〉}
求特殊关系
1.设A={a,b,c}的幂集ρ（A）={Æ,{a},{b},{c},{a,b},{b,c},{a,c},{a,b,c}}上的“Í”是偏序关系，则
（1）B={{a,b},{b,c},{b},{c},Æ}
（2）B={{a}，{c}}，求8种特殊关系
解：
（1）不$y∈B,"y’Íy，故无罪最大元，最小元是Æ；
极大元为{a,b},{b,c}；极小元为Æ；上界和上确界均{a,b,c}；下界下确界均为Æ
（2）无最大最小元；极大元和极小元均为{a}，{c}；
上界为,{a,c},{a,b,c}；上确界为{a,c}；下界和下确界均为Æ；
2.集合A={2，3，6，12，24，36},其中“≤”为A上的整除关系R
1）画出一般的关系图和哈斯图2）设B1={6,12}B2={2,3}B3={24,36}B4={2,3,6,12}为A的子集试求出B1B2B3B48种元素
最大元
最小元
极大元
极小元
上界
下界
上确界
下确界
B1
12
6
12
6
12,24,36
2,3,6
12
6
B2
无
无
2,3
2,3
6,12,24,36
无
6
无
B3
无
无
24,36
24,36
无
2,3,6,12
无
12
B4
12
无
12
2,3
12,24,36
无
12
无
3.A={a,b,c,d,e,f,g,h}，对应的哈斯图如下；令B1={a,b}，B2={c,d,e}，求B1B28种元素
解
B1
B2
最大元
无
无
最小元
无
c
极大元
a,b
d,e
极小元
a,b
c
上界
c,d,e,f,g,h
h
下界
无
a,b,c
上确界
c
h
下确界
无
c
代数系统
1.代数系统单位元逆元素零元素
1.在实数集R上定义二元关系“*”：
“”如下：
x*y=x+y—xy，xy=1/2（x+y）
（1）x*y是否满足结合律、交换率？
是否有单位元及逆元？
（2）xy是否满足结合律、交换率？
是否有单位元及逆元？
解：
因为
（1）（x*y）*z=（x+y—xy）*z=x+y—xy+z—xz—yz+xyz
x*（y*z）=x*（y+z—yz）=x+y—xy+z—xz—yz+xyz满足结合率
x*y=x+y—xy；y*x=y+x—xy满足交换率
x*0=x+0—x0=0+x—0x=x所以单位元是0
x*x—1=x+x—1—xx—1=0所以x—1=—x/（1—x）（x≠1）
所以对于R—{1}的所有x均有逆元素—x/（1—x）
（2）因为（xy）z=1/2（x+y）z=1/2（1/2（x+y）+z）=1/4x+1/4y+1/2z
x（yz）=x1/2（y+z）=1/4y+1/4z+1/2x所以不满足结合律
又因为xy=1/2（x+y），yx=1/2（x+y）所以满足交换率；不存在单位元素和逆元素
2.在代数系统中的单位元是：
0
3.设A是非空集合<ρ（A），∪，∩>中,ρ（A）对运算∪的单位元是Æ，ρ（A）对运算∩的单位元是Ａ
2.找子群证明交换群
1.试证阶为偶数的循环群中周期为2的元素个数一定是奇数
证明：
设（G，*）是阶为n的循环群，即|G|=n（n是偶数）。
任取a∈G，an=e（m>2）,a的阶为m,a的逆元素a—1∈G，故（a—1）m=（am）—1=e—1=e，由群的性质，知a—1的阶也是m，则必定有a≠a—1
反证法，若a≠a—1，则a2=e，所以a的阶不大于2，这与m>2矛盾，所以a≠a—1，即当a的阶数大于2时，a与它的逆元素总是成对出现的
又因为群中唯一的单位元素e的阶为1，此时阶大于2的元素个数是偶数，加上单位元e，个数为奇数了，剩下的那些阶为2的元素个数必须是奇数，才能满足所给条件n是偶数，得证
2.找出（Z12,Å12）的所有子群
解：
（1）1阶子群（[0],Å12）
（2）2阶子群（{[0],[6]}Å12）
（3）3阶子群（{[0],[4],[8]},Å12）
（4）4阶子群（{[0],[3],[6],[9]},Å12）
（5）6阶子群（{[0],[2],[4],[6],[8],[10],}Å12）
（6）12阶子群（Z1.2,Å1.2）
3.设群中每个元素的逆元素是其自身的，则G是一个交换群
证明：
对于任意的a，b∈G由a*b∈G,因为一个元素的逆元素就是其自己，于是
a*b=（a*b）—1=b—1*a—1=b*a，所以G是交换群
3.计算置换
设M={1,2,3}，σ与Τ是M的置换：
σ=123，Τ=123
231321
求σ—1，σΤ，Τσ，Τ—1
σ—1=123σΤ=123123=123
312231321213
Τσ=123123=123
321231132
Τ—1=123
321
4.证明两代数系统同构
1.证明和同构
证：
设g：
R+→R，g（x）=lnx显然g（x）=lnx为一一对应的函数ln（x1x2）=lnx1+lnx2
得g（x1x2）=g（x1）+g（x2）（x1，x2∈x）所以证明和同构
2.证明两个代数系统之间的同构关系就是等价关系
证：
设和为任意的三个代数系统
首先，≌，所以满足自反性
其次，如果≌，即存在g：
X→Y，使得,"x1，x2∈X，
有g（x1x2）=g（x1）*g（x2）由g为一一对应的函数，所以存在g—1：
Y→X，
"y1y2∈Y1g—1（y1）=x1g—1（y2）=x2x1x2=g—1（y1）g—1（y2）；
x1x2=g—1（g（x1x2））=g—1（g（x1）*g（x2））=g—1（y1*y2）
所以g—1（y1*y2）=g—1（y1）g—1（y2）Þ≌
最后，如果≌，≌只需要证≌
即存在g：
X→Y，使得"x1，x2∈X，均有g（x1x2）=g（x1）*g（x2）
存在h：
Y→Z，使得"y1，y2∈Y，均有h（y1*y2）=h（y1）+h（y2）
建立一个一一对应的函数f：
hg：
X→Z
"x1，x2∈Xf（x1x2）=hg（x1x2）=h（g（x1）*g（x2））=hg（x1）+hg（x2）=f（x1）*f（x2）
综上所述同构关系就是等价关系
3.任何一个群与一个变换群同构
证明：
设群为,"a∈G,可定义变换τa（x）→x*a,做集合G＇
下面证明≌
即找出Φ：
Ｇ→G＇使得"a，ｂ∈G有Φ（a*b）=Φ（a）Φ（b）
①a=b，τa=τb说明是映射
②"τa∈G＇$a∈G,使得τa（x）=x*a说明是漫射
③"a，ｂ∈G，且a≠bÞx*a≠x*b（x∈G）一一映射下的函数就是一一对应函数
④Φ（a*b）=τ（a*b）=x*（a*b）=（x*a）*b=τb（τa（x））=（τa*τb）（x）=Φ（a）Φ（b）
所以是同构
/*这里额外说明一下：
设f：
A→B，g：
B→Cfg：
A→C（fg）（x）=g[f（x）]*/
4.设G为群，若"x∈G，又x2=e证G为交换群
证明：
由"x∈G，有x2=e，所以x=x—1，存在逆元素
（xy）（y—1x—1）=e得xx—1=e满足结合律
"x，y∈G，xy=（xy）—1=y—1x—1=yx满足交换律
5.若为可交换半群，则"a，b∈G，必有（a*b）n=an*bn
证明：
（a*b）2=a2*b2"a，b∈G，
（a*b）2=（a*b）*（a*b）=a*（b*a）*b=a*（a*b）*b=（a*a）*（b*b）=a2*b2
根据数学归纳法得出（a*b）n=an*bn
6.设Ｇ为群，H，K为G的子群，证H∩K也为G的子群
1）首先证明G是非空的，
由于H,K均为G的子集，e∈H∩K，所以H∩K非空
2）"a，b∈H∩K，
a∈H，a∈K，b∈H，b∈K
又因为H为G的子群，则ab—1∈H，且在H中有唯一解，
同理得，ab—1∈K，根据群的第二定义
综上所述，得出，H，K为G的子群，证H∩K也为G的子群
图论
1.数量积
基本通路:
：
（n，m）图,基本通路的长度——≤n—1
①通路
基本回路：
（n，m）图，基本回路的长度——≤n
②（n，m）的完全图Kn，m和n的关系
2.生成子图：
则V＇=V且E＇=E
子图：
则V＇ÍV且E＇ÍE＜V＇，E＇＞是＜V，E＞
真子图：
则V＇ÍV且E＇ÌE
3.应用：
欧拉图 欧拉通路
1.邮递员从邮局v1出发沿由路投递信件，其邮路图所示，试问是否存在一条投递路线使邮递员从邮局出发通过所有路线而不重复且最后回到邮局
解：
由于图中每个结点的次数均为偶次数，由定理知这样的路线一定是存在的
C（v1,v5v11v7v12v8v10v6v9v11v12v10v9v5v2v6v4v8v3v7v1）
2.晒水车从A点出发执行晒水任务，城市街道图形如图所示，试问是否存在一条晒水路线，是晒水车从A点出发通过所有街道且不重复最后回到车库B15
解：
问题的变形是问AB之间是否存在欧拉通路，由于图中每个结点除、了A、B为奇数外其余均为偶次数，由定理可知这样一条晒水路线使存在的
P=（A,C,D,E,F,B,G,C,F,G,A,B）
命题逻辑
1.判断何为命题
2.判断命题真假①
②公式真值表
逻辑演算
3.命题符号化
4.公式的真值指派
1.下列命题公式┐（P∧（Q→┐P））记做G，使G的真值指派为F的P，Q的真值是：
（T，F）
2.设命题公式G=P∧（┐Q∨R）,则使G得真值指派为T的是：
TTT,TFT,TTF
3.（┐p∧q）→┐r
p,q,r
┐p
（┐p∧q）
┐r
（┐p∧q）→┐r
000
1
0
1
1
001
1
0
0
1
010
1
1
1
1
100
1
1
0
0
101
0
0
1
1
110
0
0
0
1
110
0
0
1
1
111
0
0
0
1
4.
（1）（p→┐p）∧q→┐q均为成真赋值
（2）┐（p→q）∧q∧r均为成假赋值
5.化简公式：
化简下列公式
（1）（┐P∧Q）∨（┐P∧┐Q）
（2）Q→（P∨（P∧Q）
解：
（1）（┐P∧Q）∨（┐P∧┐Q）
（2）Q→（P∨（P∧Q）
=（Q∧┐P）∨（┐Q∧┐P）=（┐Q∨P）∨P
=（Q∨┐Q）∧┐P=Q→P
=1∧┐P
=┐P
6.求主范式
1.命题公式┐（（P∧（Q→┐P））记做G，使G的真值指派为F的P，Q的真值是：
（T，F）
2.设命题公式G=P∧（┐Q∨R）,则使G得真值指派为T的是：
TTT,TFT,TFF
3.（┐p∧q）→┐r
p,q,r
┐p
（┐p∧q）
┐r
（┐p∧q）→┐r
000
1
0
1
1
001
1
0
0
1
010
1
1
1
1
100
1
1
0
0
101
0
0
1
1
110
0
0
0
1
110
0
0
1
1
111
0
0
0
1
4.
（1）（p→┐p）∧q→┐q均为永真式
（2）┐（p→q）∧q∧r均为永假式
21．（p→q）r
法一：
（┐p∨q）r
=（（┐p∨q）→r）∧（r→（┐p∨q））
=（┐（┐p∨q）∨r）∧（┐r∨（┐p∨q））
=（（p∨┐q）∨r）∧（┐r∨┐p∨q）
=（（p∨r）∧（┐q∨r）∧（┐p∨q∨┐r）——含有三个简单析取式的合取范式（式子①）
=（（p∧┐q）∧┐r）∨（p∧┐q∧┐p）∨（p∧┐q∧q）∨（r∧┐r）∨（r∧┐p）∨（r∧q）
=（p∧┐q∧┐r）∨（┐p∧r）∨（q∧r）——含有三个简单合取式的析取范式（式子②）
根据式子②先求主析取范式（p∧┐q∧┐r）∨（┐p∧r）∨（q∧r）
=（p∧┐q∧┐r）∨（┐p∧（q∨┐q）∧r）∨（r∧（p∨┐p）∧q）
=（p∧┐q∧┐r）∨（┐p∧q∧r）∨（┐p∧┐q∧r））∨（r∧p∧q）∨（r∧┐p∧q）
=（p∧┐q∧┐r）∨（┐p∧q∧r）∨（┐p∧┐q∧r））∨（r∧p∧q）
100（m4）011（m3）001（m1）111（m7）
根据式子①先求合取取范式（（p∨r）∧（┐q∨r）∧（┐p∨q∨┐r）
=（（p∨（q∧┐q）∨r）∧（┐q∨（p∧┐p）∨r）∧（┐p∨q∨┐r）
=（（p∨q∨r）∧（p∨┐q∨r）∧（┐q∨p∨r）∧（┐q∨┐p∨r）∧（┐p∨q∨┐r）
=（（p∨q∨r）∧（p∨┐q∨r）∧（┐q∨┐p∨r）∧（┐p∨q∨┐r）
000（M0）010（M2）110（M6）101（M5）
法二：
真值表
p,qr
（p→q）r
主析取范式
=m4∨m3∨m1∨m7
主合取范式
=M0∧M2∧M6∧M5
000
10
001
11
0
升级会员 