离散数学复习知识点

复习知识点：第1章1．命题、真命题、假命题2．命题符号化（连接词）设P：天下大雨，Q：他在室内运动，命题“除非天下大雨，否则他不在室内运动”可符合化为（D）A．QPB．QPC．QPD．QP设P：只有你通过了大学英语六级考试，Q：你是英语专业的学生，R：你可以选修这门课程。命题“只有你通过了大学英语六级考试而且不是英语专业的学生，才可以选修这门课程”(B)A．RQ)(PB．RQ)(PC．RQ)(PD．RQ)(P3．什么是命题公式4．命题公式的等价式5．利用逻辑等价关系证明下面的等价关系QPQ)(PP))(QQ)((P证明：6．用真值表法求命题公式的主析取范式和主合取范式7．符号化以下语句，并推证结论的有效性。有些学生相信所有的老师，任何一个学生都不相信骗子，所以老师都不是骗子。解：设论述域为全总个体域，S(x)：x是学生，T(x)：x是老师，P(x)：x是骗子，L(x,y)：x相信y。将前提和结论符号化为P(x))x(T(x)y)))L(x,y(P(y)x(S(x)y))),L(x,y(T(y)x(S(x)（1）y)))L(x,y(T(y)x(S(x)P（2）y))L(a,y(T(y)S(a)T1，ESQ)(PTQ)(PQ)Q(Q)(PQQ)(PT)(QQ)(PP))P((QQ)(PQ)(PP)(QQ)(PQ)(PP)Q(Q)P(Q)(PP))Q(Q)P((Q)(PP)Q(Q)P(Q)(PP))(QQ)((P（3）S(a)T2，I（4）y))L(a,y(T(y)T2，I（5）b)L(a,T(b)T4，US（6）y)))L(x,y(P(y)x(S(x)P（7）y))L(a,y(P(y)S(a)T6，US（8）y))L(a,y(P(y)T3,7，I（9）b)L(a,P(b)T8，US（10）P(b)b)L(a,T9，E（11）P(b)T(b)T5,10，I（12）P(x))x(T(x)T11，UG侦查员在调查了某珠宝店的珠宝失窃案现场以及询问了认证之后，得到以下事实：（1）是营业员甲或营业员乙作案。（2）如果是甲作案，则案发在非营业时间。（3）如果乙提供的证词可信，则案发时货柜未上锁。（4）如果乙提供的证词不可信，则案发在营业时间。（5）货柜在案发时上锁了。侦查员推断是营业员乙作案，请用命题逻辑判断该推断是否正确。解：设P：甲作案；Q：乙作案；R：发在营业时间；S乙的证词可信；T：案发时货柜未上锁。由题意可知，前提为：QP，RP，TS，RS，T推理过程：（1）TP（2）TSP（3）ST1，2，I（4）RSP（5）RT3，4，I（6）RPP（7）PT5，6，I（8）QPP（9）QPT8，E（10）QT7，9，I所以QP，RP，TS，RS，TQ第2章8．谓词的定义、量词包括：9．什么是谓词公式10．谓词公式的自由变元、约束变元、辖域11．自然语句的符号化：比如：所有的狼都吃人，设T(x)表示为x是狼，C(x)表示为x吃人。C(x))x(T(x)12．判断什么是前束范式，y)H(x,y)yG(x,x是前束范式，Q(x))y)y(P(x,x是前束范式13．证明xB(x)xA(x)B(x))x(A(x)证明：第3章1.集合的元素、集合的基数、集合的子集、集合的运算空集的问题（空集的基数、空集与集合的子集、真子集的关系）幂集的问题（集合幂集的求法，幂集的基数）下面那个命题是不正确的是（A）A．B．{}C．D．{}下面那个命题是不正确的是（A）A．{}B．{}{}C．{{}}D．{}下列命题中不正确的是（）A.x{x}-{{x}}B.{x}{x}-{{x}}C.A={x}∪x,则xA且xAD.A-B=A=B设P={x|(x+1)2≤4}，Q={x|x2+16≥5x},则下列选项正确的是（）A.PQB.PQC.QPD.Q=P设A={a,{a}}，下列命题错误的是（B）)()()()()()())()((B(x))x(A(x)xxBxxAxxBxxAxxBxAxxBxAxA．{a}(A)B．{a}(A)C．{{a}}(A)D．{{a}}(A)在0（D）之间写上正确的符号。A．=B．C．D．判断下列命题哪个为真?（C）A．空集只是非空集合的子集B．空集是任何集合的真子集C．A-B=B-AA=BD．若A的一个元素属于B，则A=B判断下列命题哪几个正确？（B）A．若A∪B＝A∪C，则B＝CB．{a,b}={b,a}C．（A∩B）（A）∩（B），（(S)表示S的幂集）D．若A为非空集，则AA∪A成立设A={a,b}，B={c}。求下列集合：（1）A{0,1}B；（2）B2；（3）(AB)2；（4）(A)A。解：（1）A{0,1}B={a,0,c,a,1,c,b,0,c,b,1,c}；（2）B2A={c,c,a,c,c,b}；（3）(AB)2={a,c,a,c,a,c,b,c,b,c,a,c,b,c,b,c}；（4）(A)A={Ф,a,Ф,b,{a},a,{a},b,{b},a,{b},b,a,a,a,b}。关系1.设A={a,b,c}，则A上的二元关系有23*3或512个。2.集合A={1,2,…,10}上的关系R={x,y：x+y=10,x,yA}，则R的性质为（B）A．自反的B．对称的C．传递的，对称的D．传递的设A={Ф,{1},{1,3},{1,2,3}}，则A上包含关系“”的哈斯图为（C）A．{1,2,3}{1,3}{1}B．{1,2,3}{1,3}{1}C．{1,2,3}{1,3}{1}D．{1,2,3}{1,3}{1}集合A上的等价关系的三个性质是自反性、对称性和传递性。集合A上的偏序关系的三个性质是自反性、反对称性和传递性。A上的偏序关系的Hasse图如下。（1）下列哪些关系式成立：ab，ba，ce，ef，df，cf；（2）分别求出下列集合关于的极大（小）元、最大（小）元、上（下）界及上（下）确界（若存在的话）：（a）A；（b）{b,d}；（c）{b,e}；（d）{b,d,e}。abcdef解：（1）ba，ce，df，cf成立；（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的关系},,,{baBbAabaR整除且，试给出R的关系图和关系矩阵，并说明此关系R及其逆关系1R是否为函数？为什么？解：}12,4,4,4,12,3,12,2,10,2,4,2,2,2{R，则R的关系图为：R的关系矩阵为110110000101001RM关系R不是A到B的函数，因为元素2，4的象不唯一逆关系1R也不是B到A的函数因为元素7的象不存在．下列函数是双射的为（A）。A．f:ZE,f(x)=2xB．f:NNN,f(n)=nC．f:RZ,f(x)=[x]D．f:ZN,f(x)=|x|（注：Z—整数集，E—偶数集，N—自然数集，R—实数集）设ZNE、、分别为整数集，自然数集，偶数集，则下列函数是双射的为（A）A．f:ZE,()2fxxB．f:ZE,()8fxxC．f:ZZ,()8fxD．f:NNN,(),1fnnn设{,,},{1,2,3}AabcB，则下列关系中能构成A到B函数的是（C）A．1{,1,,2,,3}faaaB．2{,1,,1,,2}fabbC．4{,1,,1,,1}fabcD．1{,1,,2,,2,,3}faabc设函数:fBC，:gAB都是单射，则:fgAC（A）A．是单射B．是满射C．是双射D．既非单射又非满射设函数:fBC，:gAB都是满射，则:fgAC（B）A．是单射B．是满射C．是双射D．既非单射又非满射设,fg是自然数集N上的函数,xxgxxfNx2)(,1)(,，则()fgx21x，()gfx2(1)x．关系F={x1,y1,x2,y2,x3,y2}是函数（对）关系F={x1,y1,x1,y2}是函数（错）设图G的邻接矩阵为A234B24710120101010010000011100100110则G的边数为(B)．A．6B．5C．4D．3已知图G的邻接矩阵为，则G有（D）．A．5点，8边B．6点，7边C．6点，8边D．5点，7边设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是(D)．图四A．（a）是强连通的B．（b）是强连通的C．（c）是强连通的D．（d）是强连通的在自然数集N上，运算C是不可结合的。A．a*b=a+b+3B．a*b=min{a,b}C．a*b=a+2bD．a*b=a·b(mod3)Q是有理集，Q,*（其中*为普通乘法）不能构成（A）。A．群B．独异点C．半群D．交换半群设,G是个含幺半群，则对任意的Aa有eaa，其中e是幺元.试证明,G是个阿贝尔群.证明:首先来证明,G是个群（只需证明每个元素均可逆），由条件知，对任意的元素Ga，有eaaaa，所以aa1.其次，来证明运算可交换.对任意的Gba,，所以ababbaba111)(.因此，,G是个阿贝尔群.有理数集Q中的定义如下：abbaba（1）,Q是半群吗？是可交换的吗？（2）求单位元.（3）Q中是否有可逆元？若有，指出哪些是可逆元，并指出其逆元是什么？解:（1）Qcba,,，因)(*)*(*bccbacba)()(bccbabccbaabccabcabcbacabbacba*)()*(*cabbacabba)()(abccabcabcbacbacba)()(，,Q是半群.因Qbaabba,,，故*是可交换的.(2)设e为其单位元，则应有:aaeeaQa,，即aaeea，由a的任意性，有0e.所以单位元为0.（3）设a是可逆的，其逆元为b，则应有：0abbaba，所以当1a时，有逆元，其逆元为：11aaa，当1a时，没有逆元.设,G是群，则Gba,，则(a*b)-1=b-1*a-1。证明：由于,G是群，则Gba,,设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。