2022年离散数学复习知识点.docx

《2022年离散数学复习知识点.docx》由会员分享，可在线阅读，更多相关《2022年离散数学复习知识点.docx（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选学习资料 - - - - - - - - - 复习学问点：第 1 章1 命题、真命题、假命题 2 命题符号化连接词设 P：天下大雨, Q：他在室内运动,命题“ 除非天下大雨,否就他不在室内运动” 可符合化为DCPQDPQAPQBPQ设 P：只有你通过了高校英语六级考试,Q：你是英语专业的同学,R：你可以选修这门课程；命题“ 只有你通过了高校英语六级考试而且不是英语专业的同学,才可以选修这门课程” B RRBPQRAPQCPQDPQR3 什么是命题公式 4 命题公式的等价式 5 利用规律等价关系证明下面的等价关系PQQPPQPQ证明：PQQPPQPQQPPQPQQPPQPQQPPQPQQPP

2、QPQQPPPQQTPQQQPQQPQTPQ6 用真值表法求命题公式的主析取范式和主合取范式7 符号化以下语句,并推证结论的有效性；有些同学信任全部的老师,任何一个同学都不信任骗子,所以老师都不是骗子；解：设论述域为全总个体域,信 y；将前提和结论符号化为Sx：x 是同学, Tx：x 是老师, Px：x 是骗子, Lx,y：x 相名师归纳总结 1xSxyTyLx,y,xSxyPyLx,yxTxPx第 1 页,共 9 页xSxyTyLx,yP2SayTyLa,yT1,ES- - - - - - -精选学习资料 - - - - - - - - - 3 Sa T2,I4yTyLa,yLx,yT2,I

3、5TbLa,bT4,US6xSxyPyP7SayPyLa,yT6,US8yPyLa,yT3,7,I9PbLa,bT8,US10La,bPbT9,E11TbPbT5,10, I12xTxPxT11,UG侦查员在调查了某珠宝店的珠宝失窃案现场以及询问了认证之后,得到以下事实：（1）是营业员甲或营业员乙作案；（2）假如是甲作案,就案发在非营业时间；（3）假如乙供应的证词可信,就案发时货柜未上锁；（4）假如乙供应的证词不行信,就案发在营业时间；（5）货柜在案发时上锁了；侦查员推断是营业员乙作案,请用命题规律判定该推断是否正确；解：设 P：甲作案； Q：乙作案； R：发在营业时间；T：案发时货柜未上锁；

4、S乙的证词可信；由题意可知,前提为：PQ,PR,ST,SR,T推理过程：名师归纳总结 1TTRP第 2 页,共 9 页2SP3ST1,2,I4SP5R QRT3,4,I6PP7PT5,6, I8PP- - - - - - -精选学习资料 - - - - - - - - - 9PQT8,E10Q,PR,ST,T7,9,ITQ所以PQSR,第 2 章 8 谓词的定义、量词包括：9 什么是谓词公式10谓词公式的自由变元、约束变元、辖域yTx表示为 x 是狼, Cx表示为 x11自然语句的符号化：比方：全部的狼都吃人,设吃人；xTxCx是前束范式,xyPx,yQx是12判定什么是前束范式,xyGx,y

5、Hx,前束范式13证明xAxBxxAxxBx证明：xAxBxxAx Bx xAxxBx xA xxBx xAx xBx第 3 章 1.集合的元素、集合的基数、集合的子集、集合的运算 空集的问题空集的基数、空集与集合的子集、真子集的关系幂集的问题集合幂集的求法,幂集的基数下面那个命题是不正确的选项是A ABCD下面那个命题是不正确的选项是A DAB C以下命题中不正确的选项是x-xB.x x-xC.A=xx,就 x A 且 x AD.A-B=A=B设 P=x|x+124,Q=x|x2+165x,就以下选项正确的选项是QQP D.Q=P名师归纳总结 设 A=a,a,以下命题错误的选项是B 第 3

6、页,共 9 页- - - - - - -精选学习资料 - - - - - - - - - AaABaACaADaA在 0 D 之间写上正确的符号；CDA=B判定以下命题哪个为真.CA空集只是非空集合的子集B空集是任何集合的真子集C A-B=B-A A=B D假设 A 的一个元素属于 B,就 A=B判定以下命题哪几个正确？B A假设 A BAC,就 BC Ba, b=b, aC A BA B, S表示 S 的幂集D假设 A 为非空集,就 A AA 成立设 A=a, b, B=c；求以下集合：1A 0, 1 B； 2B2 解：A； 3A B 2； 4 A A；1A 0, 1 B=, , , ；2B

7、2A=, ；3A B2=, , , ；名师归纳总结 4 A A=, , , , , , , 第 4 页,共 9 页关系1. 设 A=a,b,c,就 A 上的二元关系有23*3 或 512 个 ；2. 集合 A=1, 2, , 10 上的关系 R=：x+y=10, x, yA,就 R 的性质为 BA自反的B对称的C传递的,对称的D传递的设 A= , 1, 1, 3, 1, 2, 3,就 A 上包含关系“” 的哈斯图为C1,2,31,2,311,311,3AB- - - - - - -精选学习资料 - - - - - - - - - 1,2,31,2,31,311,31CD集合 A 上的等价关系的

8、三个性质是 自反性、 对称性 和 传递性；集合 A 上的偏序关系的三个性质是自反性、 反对称性 和 传递性；A 上的偏序关系 的 Hasse图如下；1以下哪些关系式成立：a b,b a,c e,e f,d f,c f；2分别求出以下集合关于 界假设存在的话 ：的极大小元、最大小元、上下界及上下确aA； bb, d； cb, e； db, d, e；afeb dc解：1 b a,c e,d f,c f 成立；2a的极大元为 a, e, f,微小元为 c；无最大元, c 是最小元；无上界,下界是 c；无上确界,下确界是 c；b的极大元为 b, d,微小元为 b, d；无最大元和最小元；上界是 e,

9、下界是 c；上确界是 e,下确界是 c；c的极大元为 e,微小元为 b；最大元是 e, b 是最小元；上界是 e,下界是 b；上确界是 e,下确界是 b；d的极大元为 e,微小元为 b,d；最大元是 e,无最小元；上界是 e,下界是 c；上确界是 e,下确界是 c；设 A=2,3,4,B=2,4,7, 10,12从 A 到 B 的关系名师归纳总结 Ra,baA,bB,且a整除b ,试给出 R 的关系图和关系矩阵,并说明此关第 5 页,共 9 页系 R 及其逆关系R1是否为函数？为什么？- - - - - - -精选学习资料 - - - - - - - - - 解：R2,2,2,4,2,10,2

10、,12,3,12,4,4,4,12,就 R 的关系图为：2ABR 的关系矩阵为21101134MR00001740100110关系 R 不是 A 到 B 的函数,12由于元素 2,4 的象不唯独逆关系R1也不是 B 到 A 的函数由于元素 7 的象不存在以下函数是双射的为A；Bf : NN N, f n =nAf : ZE , f x = 2xCf : RZ , f x = xDf : ZN, f x = | x |注： Z整数集, E偶数集,N自然数集, R实数集设 Z、N、E 分别为整数集,自然数集,偶数集,就以下函数是双射的为A A f : Z E , f x 2 x B f : Z E

11、 , f x 8 xC f : Z Z , f x 8 D f : N N N , f n n n 1设 A a b c , B 1, 2 , 3,就以下关系中能构成 A到B函数的是C Af 1 a ,1 , a ,2 , a ,3 Bf 2 a ,1 , b ,1 , b ,2 Cf 4 a ,1 , b ,1 , c ,1 Df 1 a ,1 , a ,2 , b , 2 , c ,3 设函数 f : B C ,g A B 都是单射 ,就 f g A C A A是单射 B是满射 C是双射 D既非单射又非满射设函数 f : B C ,g A B 都是满射 ,就 f g A C B A是单射

12、B是满射 C是双射 D既非单射又非满射设 f g 是自然数集 N 上的函数 , x N , f x x 1 , g x 2 x,就 f g x 2 x 1,g f x 2 x 1关系 F=,是函数对关系 F=,是函数错设图 G 的邻接矩阵为名师归纳总结 - - - - - - -第 6 页,共 9 页精选学习资料 - - - - - - - - - 01100就 G 的边数为 B 10011D3100000100101010A6 B5 C4 已知图 G 的邻接矩阵为,就 G 有D D A5 点, 8 边B6 点, 7 边C6 点, 8 边D5 点, 7 边设有向图 a、b、c与 d如图四所示,

13、就以下结论成立的是图四Aa是强连通的Bb是强连通的bmod 3是Cc是强连通的Dd是强连通的在自然数集N 上,运算C 是不行结合的；Aa*b=a+b+3 Ba*b=mina,b Ca*b=a+2b Da*b=a Q 是有理集, 其中 * 为一般乘法不能构成A ；G,A群B独异点C半群D交换半群设G,是个含幺半群,就对任意的aA有aae,其中 e 是幺元 . 试证明个阿贝尔群 . 名师归纳总结 证明 : 第一来证明G,是个群只需证明每个元素均可逆,由条件知,对任意的第 7 页,共 9 页- - - - - - -精选学习资料 - - - - - - - - - 元素aG,有aaaae,所以a1a

14、. 其次,来证明运算a,bG,所以ba1ba. aba1b1b因此,G,是个阿贝尔群 . ab有理数集 Q 中的定义如下：aba1Q,是半群吗？是可交换的吗？2求单位元 . 3 Q 中是否有可逆元？假设有,指出哪些是可逆元,并指出其逆元是什么？名师归纳总结 解 : 1a,b ,cQ,第 8 页,共 9 页因a*b*ca*bcbc abcbca bcbc abcabbccaabca*b*cabab*cababcababcabcabbccaabca bcabc,Q,abba,a,bQ,故 * 是可交换的 . 2 设 e 为其单位元, 就应有 : aQ,aeeaa,即aeaea,由 a 的任意性,有e0. 所以单位元为0.3设 a 是可逆的,其逆元为b ,就应有：ababab0,所以当a1时,有逆元,其逆元为：a1aa1,当a1时,没有逆元 .设G,是群,就a,bG,就 a*b-1=b-1*a-1；证明：由于G,是群,就a,bG, 设 a 的逆元为 a-1,b 的逆元为 b-1, 就a*b* b-1*a-1=a*b*b-1*a-1 =a*e*a-1- - - - - - -精选学习资料 - - - - - - - - - =a*a-1 =e 名师归纳总结 所以, a*b-1=b-1 *a-1；第 9 页,共 9 页- - - - - - -