离散数学复习资料和试题文档格式.doc

1、6） 互补率：AA=E；AA=E=E7） 双重否定率：A=A8） 幂等率：AA=A；AA=A9） 吸收率：A（AB）=A；A（AB）=A10） 德摩根率：（AB）=AB；（AB）=AB交：AB；并：AB；差运算：AB（属于A不属于B）；补运算：A；对称差运算：AB；笛卡儿乘积：AB=|aA，bB设A=a，b，c，B=b，d，e则AB=a，c，AB=a，c，d，e4. 集合的计数问题：|A|=2 n （n是集合A的元素的个数） | AB |=|A|+|B| AB |；|ABC|=|A|+|B|+|C| AB | AC |BC|+| ABC |5. 关系的性质:由图写出性质有性质画图由关系集合写性

2、质（自反性，反自反性，对称性，反对称性，传递性：）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）=RIA ；s（R）=RR；t（R）=RR 1R 2R 3R n1

3、设A=a，b，c，R1、R2是A上的二元关系：R1=a，a，b，b，b，c，d，dR2=a，a，b，b，b，c，c，b，d，d试证明R1是R2的何种闭包解：R1R1 =a，a，b，b，b，c，d，d ，c，b即有R1R1= 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，ds（R）= a，b，b，a，b，c，c，b，c，d，d，ct（R）= a，a，b，b，a，b，a，c，a，d，b，a，b，c，b，d，c，d3.由

4、关系集合写性质设A=a，b，c，R=a，a，b，b，具有反对称性8. 关系的运算（复合运算） R1R21.设X=0，1，2，3，X上有两个关系：R1=i，j|j=i+1或j=i/2；R2=i，j|i=j+2求复合关系：R1R2R1= 0，1，1，2，2，3，0，0，2，1，R2= 2，0，3，1则有：R1R2= 1，0，2，12.设R1，R2是集合A=1，2，3，4上的二元关系，其中R1=1，1，1，2，2，4，R2=1，4，2，3，2，4，3，2，试求：R1R2=1，4，1，39. 特殊关系 等价关系:1.A=0,1,2,4,5,8,9,R为A上模为4的同余关系，求（1）R的所有等价类（2）

5、画出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）0R=0,4,8=4R=8R; 1R=1,5,9=5R = 9R ; 2R =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）aR=bR=a,b cR=dR=c,d （3）A/R=a,b,c,d3.A=,1,2,4,24上定义R=|x，yA，且（xy）能被12整除（1）写出R （2）画图 （3）证明R是等价

6、关系 解：（1）R=,1，132，1412，2424，12 （2） （3）（定义法）若证明R为等价关系，只需证明R具有自反性，对称性，传递性自反性： xA，则R 所以R具有自反性对称性： 若R，则12|（xy），yx=（x+y）所以12|（yx），故R，所以R具有对称性传递性： 如果R，且R，则12|（xy）且12|（yz）则xz=（xy）+（yz）能被12整除，故12|（xz），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上的整除

7、关系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，362，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）不$yB,y y，故无罪最大元，最小元是 极大元为a,b,b,c；极小元为上界和上确界均 a,b,c ；下界下确界均为 （2）无最大最小元；极大元和极小元均为a，c；上界为,a,c

8、, a,b,c ；上确界为 a,c ；下界和下确界均为2.集合A=2，3，6，12，24，36,其中“”为A上的整除关系R1） 画出一般的关系图和哈斯图 2）设B1=6,12 B2=2,3 B3=24,36 B4=2,3,6,12为A的子集试求出B1 B2 B3 B4 8种元素最大元最小元极大元极小元上界下界上确界下确界B1 12612,24,362,3,6B2 无2,36,12,24,36B3 24,362,3,6,12B43.A=a,b,c,d,e,f,g,h，对应的哈斯图如下；令B1=a,b，B2=c,d,e，求B1 B2 8种元素解B1B2ca,bd,ec,d,e,f,g,hha,b,

9、c代数系统1. 代数系统 单位元 逆元素 零元素1.在实数集R上定义二元关系“*”：“”如下：x*y=x+yxy，xy=1/2（x+y）（1）x*y是否满足结合律、交换率？是否有单位元及逆元？ （2）xy是否满足结合律、交换率？因为（1）（x*y）*z=（x+yxy）*z=x+yxy+zxzyz+xyzx*（y*z）= x*（y+zyz）=x+yxy+zxzyz+xyz满足结合率x*y= x+yxy；y*x= y+xxy满足交换率x*0= x+0x 0= 0+x0 x=x所以单位元是 0x*x 1=x+ x 1x x 1 =0所以x 1 = x /（1x） （x1）所以对于R1的所有x均有逆元

10、素x /（1x） （2）因为（xy）z=1/2（x+y）z=1/2（1/2（x+y）+z）=1/4 x+1/4 y+1/2 zx（yz）= x1/2（y+z）=1/4 y+1/4 z+1/2 x 所以不满足结合律又因为xy=1/2（x+y），yx=1/2（x+y）所以满足交换率；不存在单位元素和逆元素2.在代数系统中的单位元是：3.设A是非空集合 中, （A）对运算的单位元是，（A）对运算的单位元是2. 找子群 证明交换群1.试证阶为偶数的循环群中周期为2的元素个数一定是奇数证明：设（G，*）是阶为n的循环群，即|G|=n（n是偶数）。任取aG，an=e（m2）,a的阶为m,a的逆元素a 1G

11、，故（a 1）m=（a m）1=e1=e，由群的性质，知a 1 的阶也是m，则必定有 aa 1反证法，若aa 1，则a2 =e，所以a的阶不大于2，这与m2矛盾，所以aa 1，即当a的阶数大于2时，a与它的逆元素总是成对出现的又因为群中唯一的单位元素e的阶为1，此时阶大于2的元素个数是偶数，加上单位元e，个数为奇数了，剩下的那些阶为2的元素个数必须是奇数，才能满足所给条件n是偶数，得证2.找出（Z12 , 12）的所有子群（1）1阶子群（0, 12）（2）2阶子群（0,6 （3）3阶子群（0,4,8, （4）4阶子群（0,3,6,9, （5）6阶子群（0,2,4,6,8,10, （6）12阶子

12、群（Z1.2 , 1.2）3.设群中每个元素的逆元素是其自身的，则G是一个交换群对于任意的a，bG由a*bG,因为一个元素的逆元素就是其自己，于是a*b=（a*b）1 = b1 *a1=b*a，所以G是交换群3. 计算置换设M=1,2,3，与是M的置换：= 1 2 3 ，= 1 2 3 2 3 1 3 2 1求1，1 1= 1 2 3 = 1 2 3 1 2 3 = 1 2 33 1 2 2 3 1 3 2 1 2 1 3= 1 2 3 1 2 3 = 1 2 3 3 2 1 2 3 1 1 3 21= 1 2 3 3 2 14. 证明两代数系统同构1.证明和同构证：设g：R+ R，g（x）=

13、ln x 显然g（x）=ln x为一一对应的函数ln （x1 x2）= ln x1+ ln x2得 g（x1 x2）= g（x1）+ g（x2） （x1， x2x） 所以证明2.证明两个代数系统之间的同构关系就是等价关系设 Z ,+为任意的三个代数系统首先， 所以满足自反性其次，如果 ，即存在g：XY，使得, x1 ， x2X， 有g（x1 x2）= g（x1） * g（x2） 由g为一一对应的函数，所以存在g1：YX， y1 y2Y1 g1（y1） =x1 g1（y2）=x2 x1 x2= g1（y1）g1（y2）；x1 x2= g1（g（x1 x2）= g1（g（x1） * g（x2）=

14、g1（y1 * y2）所以 g1（y1 * y2） = g1（y1）g1（y2） 最后，如果， 只需要证 即存在g：XY，使得 x1 ， x2X，均有g（x1 x2）= g（x1） * g（x2） 存在h：YZ，使得 y1 ， y2Y，均有 h（y1* y2）= h（y1） + h（y2） 建立一个一一对应的函数 f：hg：XZ x1 ， x2X f（x1 x2）= hg（x1 x2）= h （g（x1） * g（x2） = h g（x1） +h g（x2） = f（x1）*f（ x2） 综上所述同构关系就是等价关系3.任何一个群与一个变换群同构设群为, a G,可定义变换a（x） x*a,做

15、集合G下面证明即找出： G使得 a，G有（a*b）=（a） （b）a=b，a=b 说明是映射aG$ aG,使得a（x）=x*a 说明是漫射 a，G，且ab x*ax*b （xG） 一一映射下的函数就是一一对应函数（a*b）= （a*b）=x*（a*b）=（x*a）*b=b（a（x）=（ a*b）（x）= （a） （b）所以是同构 /*这里额外说明一下：设f：AB，g：BC fg：AC （fg）（x）=gf（x） */4.设G为群，若xG，又x2=e 证G为交换群由xG，有x2=e，所以x=x1 ， 存在逆元素 （xy）（y1x1）=e 得x x1=e 满足结合律x，yG，xy=（xy）1=y1

16、x1=yx 满足交换律5.若为可交换半群，则a，bG，必有（a*b）n= an * bn（a*b）2= a2 * b2 a，bG，（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 * bn6.设为群，H，K为G的子群，证HK也为G的子群 1）首先证明G是非空的，由于H, K均为G的子集，eHK，所以HK非空 2）a，bHK，aH，aK，bH，bK 又因为H为G的子群，则a b1H，且在H中有唯一解， 同理得，a b1K，根据群的第二定义 综上所述，得出，H

17、，K为G的子群，证HK也为G的子群图论1. 数量积 基本通路:：（n，m）图,基本通路的长度n1通路 基本回路：（n，m）图，基本回路的长度n（n，m）的完全图Kn，m和n的关系2. 生成子图：则V=V且E=E 子图：则VV且EE V，E是V，E 真子图：V且EE3. 应用：欧拉图欧拉通路1. 邮递员从邮局v1出发沿由路投递信件，其邮路图所示，试问是否存在一条投递路线使邮递员从邮局出发通过所有路线而不重复且最后回到邮局由于图中每个结点的次数均为偶次数，由定理知这样的路线一定是存在的C（v1, v 5 v 11 v 7 v 12 v 8 v 10 v 6 v 9 v 11 v 12 v 10 v

18、 9 v 5 v 2 v 6 v 4 v 8 v 3 v 7 v 1） 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（QP） ）记做G，使G的真值指派为F的P，Q的真值是：（T，F）2. 设命题

19、公式G=P （QR）,则使G得真值指派为T的是：TTT,TFT,TTF3. （pq）rp, q, rp（pq）r（pq）r0 0 010 0 10 1 01 0 01 0 11 1 01 1 14. （1）（pp） qq 均为成真赋值 （2）（pq） qr 均为成假赋值5. 化简公式：化简下列公式（1）（PQ） （PQ） （2）Q（P（PQ）（1）（PQ） （PQ） （2） Q（P（PQ） =（QP） （QP） =（QP） P =（Q Q）P = QP =1P =P 6. 求主范式1.命题公式 （P（QP）记做G，使G的真值指派为F的P，Q的真值是：2.设命题公式G=P （QR）,则使G得真值

20、指派为T的是：TTT,TFT,TFF3.（pq）r4.（1）（pp） qq 均为永真式 （2）（pq） qr 均为永假式21（ pq） r法一： （pq） r=（pq） r）（r （pq）=（pq） r）（r （pq）=（pq） r）（r pq）=（pr）（qr ）（pq r） 含有三个简单析取式的合取范式 （式子） =（pq） r）（pqp）（pqq）（rr）（rp） （rq）=（pqr）（pr）（qr） 含有三个简单合取式的析取范式 （式子）根据式子先求主析取范式 （pqr）（pr）（qr ）=（pqr）（p（qq）r）（r（pp）q）=（pqr）（pqr） （pqr）（rpq） （rpq）=（pqr） （pqr） （pqr） （rpq） 1 0 0 （m4） 0 1 1（m3） 0 0 1（m1） 1 1 1（m7）根据式子先求合取取范式 （pr）（qr ）（pq r）=（p（qq）r）（q（pp）r ）（pq r）=（pqr）（pqr）（qpr ）（qpr）（pq r）=（pqr）（pqr）（qpr）（pq r） 0 0 0（M0） 0 1 0（M2） 1 1 0（M6） 1 0 1（M5）法二：真值表p, q r（ pq） r 主析取范式=m4m3m1m7主合取范式= M0M2M6M5 0 0 0 1 0 0 0 1 1 10