附录 综合练习---参考答案

附件：综合练习（一）一、单项选择题(每小题2分，共20分)【BAADDABCBC】1．下列选项中错误的是__B_____。A．ΦΦB．ΦΦC．Φ{Φ}D．Φ{Φ}2．下列语句中，____A____是假命题。A．如果时间流逝不止，你可以长生不老；B．伦敦是英国的首都；C．太阳是地球的行星吗？D．自然数存在最小值；3．设L(x,y)：x≤y，当个体域为__A_______时，公式xyL(x,y)真值为1。A．自然数集B．整数集C．有理数集D．实数集合4．三个结点最多可以构成___D____个不同的（非同构）的无向简单图。A．1B．2C．3D．45．设函数f:R→R,f(x)=x2,函数g:R→R，g(x)=x+1。则合成函数gof的性质为___D___。A．单射B．满射C．双射D．非单射非满射6．下列选项中，______A____一定满足交换律。A．Klein四元群B．半群C．独异点D．群7．无向图的关联矩阵中，每列的元素之和为_____B___。A．边数的2倍B．2C．顶点数D．顶点的度数8．4阶无向完全图（K4）是以下哪种图？__C_______。A．欧拉图B．平凡图C．平面图D．多重图9．命题公式(P∧Q)→Q的类型是___B______。A．可满足式B．永真式C．永假式D．无法确定10．集合{－1，0，1}上的____C____运算为二元运算（满足封闭性）。A．加法B．减法C．乘法D．除法二、填空题（每小题2分，共24分）1．若集合A的元素个数|A|=10，则其幂集元素个数|P(A)|=____210_______。2．设P：我生病，Q：我去上课，命题“当且仅当我生病时，我才会不去上课”符号化为_______PQ_________。3．公式xF(x)xG(x,y)的前束范式是___zx（F(z)G(x,y)）______________________。4．设A={a,b,c,d}，A上的等价关系R＝{a,c,d,b,c,a,b,d}∪IA，则商集A/R_____{{a,c},{b,d}}____________________。5．无向完全图K3含有__0_________个不同的点割集。6．设集合A＝{a,b}，B={a,c}，则ABA=___B_____________。(为对称差)7．设G为具有4个顶点m条边的无向简单图，则其补图有__6-m________条边。8．集合{1，2，3}到集合{a，b}上最多可构成____8________个不同的函数。9．设解释I为：定义域D={3，4，5}；F(x)：x≤5;G(x)：x＞3；在解释I下求公式))()((xGxFx的真值是___0_________________。10．设Z6={0,1,2,3,4,5}，为模6加法，即x，yZ6，xy=（x+y）mod6，则代数系统Z6,中元素2的逆元为___4____。11．一个无向图有4个结点，4条边，其中的3个顶点度数分别为1，2，3，则第4个结点度数一定是____2___。12．用仅含联结词{，∧}表示公式PQ的结果为___(PQ)_______________。三、综合题（每小题8分，共56分）1．设集合A＝{1,2,3,4}，R是A上的关系，且R={x,y|x,y∈A,且x+y是偶数}：(1)画出R的关系图；(2)验证R是等价关系；解：R={1,3,3,1,2,4,4,2}AIAIR，R具有自反性；1RR，具有对称性；RRRR，具有传递性。(3)写出R2的关系矩阵。10100101101001012．设A、B、C为任意集合，证明：（A∪B）－(B∪C）=A－B－C证明：()()()()()()()()()ABBCABBCABBCABCBBCABCABC3．求命题公式RQP)(的主析取范式、主合取范式以及成真赋值。解：采用真值表法（也可用等值演算法求解）：PQRP→QR(P→Q)R000111001100010111011100100010101000110111111100主合取范式：13457MMMMM(1,3,4,5,7)主析取范式：026(0,2,6)mmm成真赋值：000,010,1104．设集合A＝{1,2,3,4,6,8,9,12}，R为整除关系。(1)画出偏序集A,R的哈斯图；(2)写出A的子集B={3,6,9,12}的上界，下界，最小上界，最大下界；B={3,6,9,12}的上界：无，最小上界：无，下界：1，3，最大下界：3。(3)写出A的最大元，最小元，极大元，极小元。A的最大元：无，最小元：1，极大元：8,12,9，极小元：1。5．在一阶逻辑中证明以下推理：“软件学院的学生都要学习数据结构和离散数学课程；周杰人不要学习离散数学；因此周杰人不是软件学院的学生。”F(x)：x是软件学院的学生.G(x)：x要学数据结构课程.H(x)：x要学离散数学课程.a：周杰人前提：x(F(x)(G(x)H(x)))H(a)结论：F(a)证明：①H(a)前提引入②H(a)G(a)①附加规则③(G(a)H(a)）②置换规则④x(F(x)(G(x)H(x)))前提引入⑤F(a)(G(a)H(a))④UI⑥F(a)③⑤拒取式6．设有向图G的邻接矩阵为：0100001000011101（1）画出该图；（2）求该图中长度为2的通路总数。解：设原有向图的邻接矩阵为A，则A2=1121101110000100A2中所有元素之和，即为长度为2的通路总数：10（3）判断该图是否为强连通？说明理由。解：是强连通，该图存在一条回路经过所有的点，故任何两点均可互达。（4）判断该图是否为欧拉图？说明理由。解：不是，有向图为欧拉图的充要条件：连通且每个点的入度等于出度，而此图中V3点不满足（参见上图）。7．设在非零实数集合R*上定义运算△：对于任意的x,yR*，有x△y=5xy。证明：R*与运算△构成群。证明:①封闭性：x,yR*.x△y=5xyR*.△运算在R*上满足封闭；②可结性：x,y,zR*,x△(y△z)=x△(5yz)=25xyz；(x△y)△z=(5xy)△z=25xyz.△运算在R*上可结合；③有幺元：设幺元e.x△e=e△x=x.x△e=5xe=x.e=1/5；④每个元素都有逆元：x△y=5xy=1/5.y=1/(25x).xR*，.x逆元为1/(25x).；综上所述,R*与运算△构成群。综合练习（二）一、单项选择题(每小题2分，共20分)【BBACDCAADA】1.下列语句是命题的有___B______。A．x+y3.B．明天是2010年7月6号.C．青年学生多么朝气蓬勃呀！D．学生请勿吸烟!2.命题公式(PQ)→Q的类型是___B_____。A．永真式B．可满足式C．永假式D．无法确定3.F(x)：x自然数，H(x，y)：y是x的后继数。则“每个自然数都有后继数”的逻辑符号化为___A______。A.)),()(()((yxHyFyxFxB.)),()(()((yxHyFyxFxC.)),()(()((yxHyFyxFxD.)),()(()((yxHyFyxFx.4.设A={a,b,c}，下列二元关系中，不具有传递性的是____C_____。A．{a,b}B．{a,a，a,b}C．{a,a，a,b，b,a}D．{a,a，a,b，c,a，c,b}5.下列函数中，双射函数是____D_____。A．f：ZZ，f(x)=2xB．f：ZZ，f(x)=2C．f：ZZ，f(x)=x2+1D．f：ZZ，f(x)=x+26.集合{-1,0,1}上的______C___运算为二元运算（满足封闭性）。A．加法B．减法C．乘法D．除法7.设S={0,1,2,3}，*是普通乘法，则S，*为____A_____。A．不是代数系统B．是半群，不是独异点；C．是独异点，不是群D．是群。8.下列度数系列中，可以构成图的为______A___。A.1,2,3,4B.2,2,2,3C.1,2,3,3D.1,1,2,39.G是连通平面图，有5个顶点、5个面，则G的边数为______D__。A.5B.6C.7D.810.下列图中，是欧拉图的为_____A____。ABCD二、填空题(每小题2分，共20分)1.命题x(P(x)→Q(x))的真值为____1_____，其中，P(x)：x=2，Q(x)：x=1，定义域：D={1,2}。2.公式xF(x)→xG(x,y)的前束范式zx(F(z)G(x,y))。3.设集合A＝{1,2,3}，B={2,3,4}，则A(B-A)={1,2,3,4}。4.设A={a}，B={1,2}，则P(A)×B={,1,,2,{a},1,{a},2}。5.若A={1,2}，R为A上的二元关系，R={1,2,2,2}，则其对称闭包s(R)为{1,2,2,2,2,1}。6.设A={a,b,c,d}，A上的等价关系R＝{a,b，b,a}∪IA，则商集A/R＝{{a,b},{c},{d}}。7．设A={1,2,3,4}，x,yA，x*y=min{x,y}，则代数系统A,*中的零元为1。8.设Z6={0,1,2,3,4,5}，为模6加法，即x,yZ6，xy=(x+y)mod6，则Z6,为群，该群中元素2的阶为______3_____。9.无向完全图Kn有36条边，则其顶点数为9。10.一棵无向树T有4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有5片树叶。三、综合题（第6-7题每题10分，其余每题8分，共60分）1．图G是一个简单的连通的平面图，顶点数为6，其无限面的次数为5，其余面都为三边形，计算平面图G的边数和面数。解：设平面图G的边数为m，面数为r。由于图G顶点个数为6，由连通平面图欧拉公式可知：6–m+r=2①由平面图握手定理可知：5+3(r-1)=2m②解①②可得：m=10，r=6，即平面图G的边数为10，面数为6。2.在命题逻辑中构造下面推理的证明：前提：(pq)(us)，(st)r结论：pr.证明：①p附加前提引入②pq①附加规则③(pq)(us)前提引入④us②③假言推理⑤s④化简规则⑥st⑤附加规则⑦(st)r前提引入⑧r⑥⑦假言推理3．设A={0,1,2}，R是A上的二元关系，且R={x,y|x+yA}。(1)画出R的关系图；解：R={0,0,0,1,0,2,1,0,1,1,2,0}，其关系图如下：(2)写出R具有哪些性质？解：R具有对称性(3)求出R2。解：R2=RｏR=EA4．设A={1,2,3,4,5,6}，“”为A上的整除关系。(1)画出偏序集A,的哈斯图；(2)写出A的极小元、极大元；解：A的极小元：1极大元：4,5,6(3)B={2,3,6}，写出B的上界、下界。解：B的上界：6下界：15．设G，*是群，若在G上定义一新的运算，使得对x，yG，有：xy=y*x。证明：〈G，〉是群。证明：①x，yG.，xy=y*x，由于G，*是群，*运算在G上封闭，故运算在G上也满足封闭性。②x(yz)=x(z*y)=(z*y)*x，(xy)z=(y*x)z=z*(y*x)。由于G，*是群，*运算在G上满足可结合性，故(z*y)*x=z*(y*x)，即运算在G上满足可结合性。③设群G，*幺元为e,则xG，ex=x*e=x=e*x=xe,所以e也为G，的幺元。④每个元素都有逆元：设在