《离散数学复习知识点.docx》由会员分享，可在线阅读，更多相关《离散数学复习知识点.docx（9页珍藏版）》请在金锄头文库上搜索。
1、复习知识点：第1章1 命题、真命题、假命题2 命题符号化（连接词）设P：天下大雨，Q：他在室内运动，命题“除非天下大雨，否则他不在室内运动”可符合化为（D）A B CD设P：只有你通过了大学英语六级考试，Q：你是英语专业的学生，R：你可以选修这门课程。命题“只有你通过了大学英语六级考试而且不是英语专业的学生，才可以选修这门课程”( B )A B CD3 什么是命题公式4 命题公式的等价式5 利用逻辑等价关系证明下面的等价关系证明：6 用真值表法求命题公式的主析取范式和主合取范式7 符号化以下语句，并推证结论的有效性。有些学生相信所有的老师，任何一个学生都不相信骗子，所以老师都不是骗子。解：设论
2、述域为全总个体域，S(x)：x是学生，T(x)：x是老师，P(x)：x是骗子，L(x,y)：x相信y。将前提和结论符号化为（1） P（2）T1，ES（3）T2，I（4）T2，I（5）T4，US（6）P（7）T6，US（8）T3,7，I（9）T8，US（10）T9，E（11）T5,10，I（12）T11，UG侦查员在调查了某珠宝店的珠宝失窃案现场以及询问了认证之后，得到以下事实：（1） 是营业员甲或营业员乙作案。（2） 如果是甲作案，则案发在非营业时间。（3） 如果乙提供的证词可信，则案发时货柜未上锁。（4） 如果乙提供的证词不可信，则案发在营业时间。（5） 货柜在案发时上锁了。侦查员推断是营业
3、员乙作案，请用命题逻辑判断该推断是否正确。解：设P：甲作案；Q：乙作案；R：发在营业时间；S乙的证词可信；T：案发时货柜未上锁。由题意可知，前提为：，推理过程：（1） P（2）P（3）T1，2，I（4）P（5）R T3，4，I（6）P（7） T5，6，I（8）P（9）T8，E（10）QT7，9，I所以，第2章8 谓词的定义、量词包括：9 什么是谓词公式10 谓词公式的自由变元、约束变元、辖域11 自然语句的符号化：比如：所有的狼都吃人，设T(x)表示为x是狼，C(x)表示为x吃人。12 判断什么是前束范式，是前束范式，是前束范式13 证明证明：第3章1.集合的元素、集合的基数、集合的子集、集合
4、的运算空集的问题（空集的基数、空集与集合的子集、真子集的关系）幂集的问题（集合幂集的求法，幂集的基数）下面那个命题是不正确的是（ A ）ABCD下面那个命题是不正确的是（ A ）ABCD下列命题中不正确的是（）A.xx-xB.xx-xC.A=xx,则xA且xAD.A-B=A=B设P=x|(x+1)24，Q=x|x2+165x,则下列选项正确的是（）A.PQB.PQC.QPD.Q=P设A=a,a，下列命题错误的是（ B ）Aar(A)Bar(A)Car(A)Dar(A)在0（ D ）之间写上正确的符号。A=B C D判断下列命题哪个为真?（C）A空集只是非空集合的子集B空集是任何集合的真子集C
5、A-B=B-AA=B D若A的一个元素属于B，则A=B判断下列命题哪几个正确？（ B ）A若ABAC，则BCBa, b=b, aCr（AB）r（A）r（B），（r(S)表示S的幂集）D若A为非空集，则AAA成立设A=a, b， B=c。求下列集合：（1）A0, 1B； （2）B2A； （3）(AB)2； （4）r (A)A。解：（1）A0, 1B=, , , ；（2）B2A=, ；（3）(AB)2=, , , ；（4）r (A)A=, , , , , , , 。关系1. 设A=a,b,c，则A上的二元关系有 23*3 或512 个 。2. 集合A=1, 2, , 10上的关系R=：x+y=10
6、, x, yA，则R 的性质为（B）A自反的 B对称的 C传递的，对称的 D传递的设A=, 1, 1, 3, 1, 2, 3，则A上包含关系“”的哈斯图为（C）A BCD集合A上的等价关系的三个性质是 自反性 、 对称性 和 传递性 。 集合A上的偏序关系的三个性质是自反性 、 反对称性 和 传递性 。 A上的偏序关系的Hasse图如下。（1）下列哪些关系式成立：ab，ba，ce，ef，df，cf；（2）分别求出下列集合关于的极大（小）元、最大（小）元、上（下）界及上（下）确界（若存在的话）：（a）A； （b）b, d； （c）b, e； （d）b, d, e。 解：（1） ba，ce，df，
7、cf成立；（2）（a）的极大元为a, e, f，极小元为c；无最大元，c是最小元；无上界，下界是c；无上确界，下确界是c。（b）的极大元为b, d，极小元为b, d；无最大元和最小元； 上界是e，下界是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的关系，试给出的关系图和关系矩阵，并说明此关系及其逆关系是否为函数？为什么？ A234B2471012解：，则的关系
8、图为：的关系矩阵为 关系不是到的函数，因为元素2，4的象不唯一逆关系也不是到的函数因为元素7的象不存在下列函数是双射的为（A）。Af : ZE , f (x) = 2x Bf : NNN, f (n) =nCf : RZ , f (x) = x Df : ZN, f (x) = | x |（注：Z整数集，E偶数集， N自然数集，R实数集）设分别为整数集，自然数集，偶数集，则下列函数是双射的为（ A ）A : , B : , C: , D : , 设，则下列关系中能构成到函数的是（ C ）A BC D设函数，都是单射，则（ A ）A是单射 B是满射 C是双射 D既非单射又非满射设函数，都是满射，
9、则（ B ）A是单射 B是满射 C是双射 D既非单射又非满射设是自然数集上的函数,，则，关系F=,是函数 （对 ）关系F=,是函数 （错 ）设图G的邻接矩阵为则G的边数为( B )A6 B5 C4 D3已知图G的邻接矩阵为 ，则G有（ D ） A5点，8边 B6点，7边 C6点，8边 D5点，7边设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是 ( D ) 图四 A（a）是强连通的 B（b）是强连通的C（c）是强连通的 D（d）是强连通的在自然数集N上，运算 C 是不可结合的。Aa*b=a+b+3 Ba*b=mina,b Ca*b=a+2b Da*b=ab(mod 3)Q是
10、有理集，（其中*为普通乘法）不能构成（ A ）。A群 B独异点 C半群 D交换半群设是个含幺半群，则对任意的有，其中是幺元.试证明是个阿贝尔群.证明: 首先来证明是个群（只需证明每个元素均可逆），由条件知，对任意的元素，有，所以.其次，来证明运算可交换.对任意的，所以 .因此，是个阿贝尔群.有理数集中的定义如下： （1）是半群吗？是可交换的吗？ （2）求单位元. （3）中是否有可逆元？若有，指出哪些是可逆元，并指出其逆元是什么？解:（1），因 ，是半群.因，故*是可交换的.(2)设为其单位元，则应有: ，即，由的任意性，有.所以单位元为0.（3）设是可逆的，其逆元为，则应有：，所以当时，有逆元，其逆元为：，当时，没有逆元.设是群，则，则(a*b)-1=b-1*a-1。证明：由于是群，则,设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。
