离散数学期末考试

一、单项选择题（本大题共10小题，每小题2分，共20分）1、设集合M={a，}，N={{a}，}则MN=（）。A、B、{}C、{a}D、{{a}，，a}2、设关系F={1，a，2，2，b，1}，G={a，b，a，c，1，2}则FG=（）。A、{1，b，1，c，b，2}B、{a，b，a，c，1，b}C、{a，1，1，2}D、{a，1，2，2，1，b}3、设集合H={1，2，3，4}，则H上的关系R={x，yx+y是偶数}具有（）。A、自反性、反对称性和传递性B、反自反性、反对称性和传递性C、反自反性、对称性和传递性D、自反性、对称性和传递性4、设T是一棵完全二叉树，则T的每个结点都（）。A、至少有两个子结点B、至多有两个子结点C、恰有两个子结点D、可以有任意多个子结点5、设R是实数集，“+，—，，”是实数的四则运算，则下面说法正确的是A、R，是群B、R，+是群C、R，是半群D、R，—是独异点6、下面关系中，函数关系是（）。A、{x，1，y，2，y，z}B、{x，y，y，x，1，x}C、{1，y，1，x，z，z}D、{y，y，z，x，z，1}7、设S，是一个代数系统，若多任意的x，yS，都有xy=yx，则称运算在S上满足（）。A、结合律B、交换律C、分配律D、幂等律8、设Z是整数集，“—”是整数减法，则下列说法正确的是（）。A、Z，—不是代数系统B、Z，—的单位元是0C、Z，—是代数系统D、Z，—的单位元是19、设L是无向图G中的一条通路，L中的顶点各不相同，则L是一条（）。A、简单通路B、初级通路C、简单回路D、初级回路10、设G有6个3度点，2个4度点，其余顶点的度数均为0，则G的边数是（）。A、10B、13C、11D、6二、填空题(本大题共8题，共10个空，每空2分，共20分)1、设关系R={a，1，2，1，2，b}，则R逆关系R1=_______________________________。2、在代数系统Q，+（Q是有理数集，“+”是有理数加法）中，单位元是______，2的逆元是___________。3、设集合M={1，2，3，5}，则M的幂集P（M）包含___________个元素。4、设T是一棵有n(n2)个顶点的树，则T有_____________条边。5、设S，是一个代数系统，是S上的二元运算，若存在S，对任意xS，有x=x=，则称是S，的_______________。6、设S，是一个代数系统，若满足结合律且S，中有单位元，则称S，为一个___________________。7、设D是有向图，若D的基图是连通图，则称D是_________________图8、既不含________________也不含____________________的无向图称为简单图。三、计算题(本大题共3小题，每小题10分，共30分)1、用等值演算法求公式A=)()(rpqp的主析取范式。2、求公式))()(())()((zyzHyyPsxGxQx，，的前束范式。3、设集合A={1，2，3，4，5}，关系R={x，yx，yA且x整除y}，要求：（1）列出R的所有元素；（2）写出R的关系矩阵MR；（3）求偏序集A，R的极大元、极小元和最小元。四、应用题(本大题共2小题，每小题5分，共10分)1、用命题公式将下列命题符号化：2和5是偶数，当且仅当52。2、用谓词公式将下列命题符号化：每个计算机专业的学生都要学《编译原理》，但有些计算机专业的学生不学《经济学》。五、证明题（本大题共2小题，每小题10分，共20分）1、在命题逻辑系统中用归结法证明下列推理是有效的：前提：qs，qp，s结论：p2、在谓词逻辑系统中写出下列推理的（形式）证明：前提：))()((xPxMx，))()((xGxMx，))((xGx结论：)(xxP计算题6.设命题公式G=(P→Q)∨(Q∧(P→R)),求G的主析取范式。7.(9分)设一阶逻辑公式：G=(xP(x)∨yQ(y))→xR(x)，把G化成前束范式.9.设R是集合A={a,b,c,d}.R是A上的二元关系,R={(a,b),(b,a),(b,c),(c,d)},(1)求出r(R),s(R),t(R)；(2)画出r(R),s(R),t(R)的关系图.11.通过求主析取范式判断下列命题公式是否等价：(1)G=(P∧Q)∨(P∧Q∧R)(2)H=(P∨(Q∧R))∧(Q∨(P∧R))13.设R和S是集合A＝{a,b,c,d}上的关系，其中R＝{(a,a),(a,c),(b,c),(c,d)},S＝{(a,b),(b,c),(b,d),(d,d)}.(1)试写出R和S的关系矩阵；(2)计算R•S,R∪S,R－1,S－1•R－1.证明题1.利用形式演绎法证明：{P→Q,R→S,P∨R}蕴涵Q∨S。2.设A,B为任意集合，证明：(A-B)-C=A-(B∪C).3.(本题10分)利用形式演绎法证明：{A∨B,C→B,C→D}蕴涵A→D。4.(本题10分)A,B为两个任意集合，求证：A－(A∩B)=(A∪B)－B.答案：1-5BADBB6-10BBABB1.{1，a，1，2，b，2}2.0，-23.164.n-15.零元6.半群7.弱连通8.平行边环三．1.101111010011)()()()()()()()(mmmmrqprqprqprqprpqprpqp2.)),()(()),()((()),()(()),()((zyHyPsxGxQxzyzyHyPzysxGxQx3.}4,2,5,1,4,1,3,1,2,1,5,5,4,4,3,3,2,2,1,1{)1(R10000501000400100301010211111154321)2(RM（3）最小元=1极小元=1极大元=5四1.令p表示2是偶数；令q表示5是偶数；r表示52；rqp)(2.S（x）：x是计算机专业的学生；G（x）：x要学《编译原理》；F（x）：x学经济学；))()(())()((xFxSxxGxSx五1，（1）s前提引入（2）qs前提引入（3）sq置换规则（4）q1,3析取三段论（5）qp前提引入（6）p4,5拒取（1）))()((xGxMx前提引入（2）M（x）vG（x）EI规则（3）))((xGx前提引入（4）)(xGAI规则（5）M(x)2,4析取三段论（6）))()((xPxMx前提引入（7）M(x)→P（x）AI规则（8）P（x）5,7假言推理（9）)(xxPEG规则6.G=(P→Q)∨(Q∧(P→R))=(P∨Q)∨(Q∧(P∨R))=(P∧Q)∨(Q∧(P∨R))=(P∧Q)∨(Q∧P)∨(Q∧R)=(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)=(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)=m3∨m4∨m5∨m6∨m7=(3,4,5,6,7).7.G=(xP(x)∨yQ(y))→xR(x)=(xP(x)∨yQ(y))∨xR(x)=(xP(x)∧yQ(y))∨xR(x)=(xP(x)∧yQ(y))∨zR(z)=xyz((P(x)∧Q(y))∨R(z))9.(1)r(R)＝R∪IA＝{(a,b),(b,a),(b,c),(c,d),(a,a),(b,b),(c,c),(d,d)},s(R)＝R∪R－1＝{(a,b),(b,a),(b,c),(c,b)(c,d),(d,c)},t(R)＝R∪R2∪R3∪R4＝{(a,a),(a,b),(a,c),(a,d),(b,a),(b,b),(b,c),(b,d),(c,d)}；关系图:(2)bacdr(R)bacds(R)bacdt(R)bacdr(R)bacdr(R)bacds(R)bacds(R)bacdt(R)bacdt(R)11.G＝(P∧Q)∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝m6∨m7∨m3＝(3,6,7)H=(P∨(Q∧R))∧(Q∨(P∧R))＝(P∧Q)∨(Q∧R))∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝m6∨m3∨m7＝(3,6,7)G,H的主析取范式相同，所以G=H.13.(1)0000100001000101RM1000000011000010SM(2)R•S＝{(a,b),(c,d)},R∪S＝{(a,a),(a,b),(a,c),(b,c),(b,d),(c,d),(d,d)},R－1＝{(a,a),(c,a),(c,b),(d,c)},S－1•R－1＝{(b,a),(d,c)}.四证明题1.证明：{P→Q,R→S,P∨R}蕴涵Q∨S(1)P∨RP(2)R→PQ(1)(3)P→QP(4)R→QQ(2)(3)(5)Q→RQ(4)(6)R→SP(7)Q→SQ(5)(6)(8)Q∨SQ(7)2.证明：(A-B)-C=(A∩~B)∩~C=A∩(~B∩~C)=A∩~(B∪C)=A-(B∪C)3.证明：{A∨B,C→B,C→D}蕴涵A→D(1)AD(附加)(2)A∨BP(3)BQ(1)(2)(4)C→BP(5)B→CQ(4)(6)CQ(3)(5)(7)C→DP(8)DQ(6)(7)(9)A→DD(1)(8)所以{A∨B,C→B,C→D}蕴涵A→D.1.证明：A－(A∩B)=A∩~(A∩B)＝A∩(~A∪~B)＝(A∩~A)∪(A∩~B)＝∪(A∩~B)＝(A∩~B)＝A－B而(A∪B)－B=(A∪B)∩~B=(A∩~B)∪(B∩~B)=(A∩~B)∪=A－B所以：A－(A∩B)=(A∪B)－B.