离散数学期末真题

离散数学期末真题一、填空题（共10小题，每小题2分，共20分）1.设命题p：空集是一切集合的真子集，q：日本首都是京都，r：暨大校训是忠信笃敬，则复合命题:pqrqprp的真值为_____真_____;2.设B为含命题变项p，q，r的矛盾式，则公式Bpqrprq的类型为___重言式___;3.设命题公式()Gpqr，()Hqpr，则G与H的逻辑关系是______等值______;4.设F(x)：x为实数，G(x,y)：x=y，命题“不存在最小的实数”的符号化形式为(()(()(,)))xFxyFyGyx或者(()(()(,)))xFxyFyGxy;5.设解释I如下，个体域D={a,b},F(a,a）=F(b,b)=0,F(a,b)=F(b,a）=1，在解释I下，公式(,)xyFxy的真值为_________真_________;6.设{|3,,14}AxxkkNk，则用列举法表示A=_____{3,6,9,12}________.7.设d,c,b,a代表实数区间,那么316240,,,.[3，4]__________8.321,,A,8654,,,B,R与S是从A到B的关系,且xRy当且仅当1y,xgcd,即x与y的最大公约数等于1.xSy当且仅当8yx.则SR4352615141,,,,,,,,,___________9.设R为实数集合,,RR:f,xxxf22,RR:g3xxg则xgf________12xx__________;10设c,b,aA，AIa,b,b.aR是A上的等价关系,设自然映射,R/AA:g,那么ag____{a,b}____________;得分评阅人二、求解题（共4小题，每小题6分，共24分）1.(1)求(())pqrp的主析取范式；（3分）(2)根据主析取范式直接写出主合取范式；（2分）(3)根据主析取范式直接写出真值表。（1分）解答：(1)prqpprqpprqp))(())(())((prqrp)()()()()()()(rqprqprqprqprqp)7,6,5,4,2((2))3,1,0((3)真值表pqrprqp))((000000100101011010011011110111112.写出与下列谓词公式等值的前束范式。（1）))()(())()((zzHxFyyGxxF（3分）（2）xA(x,y)→yB(y)→xD(x,y)（3分）解：))()()(())()()()((zHzxFyGyxFx(()()()())()()())xFxyGyFxzHz（11(()()()())()()())xFxyGyFxzHz（11(()()()())()()())xFxyGyFxzHz（11()()()(()())()())xyzFxGyFxHz（（2）xA(x,y)→yB(y)→xD(x,y)解：(,)()(,)(,)()(,)((,)())(,)((,)())(,)((,)()(,))((,)()(,))wwxAxyyByxDxyxAxyzBzwDwyxAxyzBzwDwyxzAxyBzwDwyxzAxyBzDwyxzAxyBzDwy3设集合A＝{1,2,3}，R和S是A上的两个关系，它们的关系矩阵为：110111111001.101000RSMM(1)写出关系R和S的集合表达式，(2)画出R和S的关系图，(3)说明R和S满足关系的哪些特性.（每小题2分）解(1)R={(1,1),(1,2),(2,1),(2,2),(2,3),(3,1),(3,3)};S={1,1),(1,2),(2,3),(1,3)}(2)R和S的关系图：(3)R满足自反性；S满足反对称性、传递性。4.设A={1,2,3,4}，在AA上定义二元关系R：x,y,u,vRx+y=u+v，求R导出的划分.解AA={1,1,1,2,1,3,1,4,2,1,2,2,2,3,2,4,3,1,3,2,3,3,3,4,4,1,4,2,4,3,4,4}根据有序对x,y中的x+y=2,3,4,5,6,7,8将A划分成等价类：A/R={{1,1},{1,2,2,1},{1,3,2,2,3,1},{1,4,2,3,3,2,4,1},{2,4,3,3,4,2},{3,4,4,3},{4,4}}得分评阅人三、证明、推理题（共5小题，每小题8分，共40分）1.证明下列等价式成立：(1)(()())()()xAxBxxAxxBx（4分）(2)AB(A∧B)∨(┐A∧┐B)（4分）解答：（1）()(()())()(()())()()()()xAxBxxAxBxxAxxBx()()()()()()()()xAxxBxxAxxBx（2）证法1：ABA∧B┐A┐B┐A∧┐BAB(A∧B)∨(┐A∧┐B)00011111010100001000100011100011证法2：AB(A→B)∧(B→A)(┐A∨B)∧(┐B∨A)(┐A∧┐B)∨(┐A∧A)∨(B∧┐B)∨(B∧A)(A∧B)∨(┐A∧┐B)证法3：先证AB(A∧B)∨(┐A∧┐B)(a)设为任一指派，使(AB)=1，那么(A)=(B)=1或(A)=(B)=0，从而(A∧B)=1或(┐A∧┐B)=1，即((A∧B)∨(┐A∧┐B))=1。(a)得证；再证(A∧B)∨(┐A∧┐B)AB(b)设为任一指派，使(AB)=0，那么(A)=1，(B)=0，或者(A)=0，(B)=1，从而(A∧B)=0且(┐A∧┐B)=0，即((A∧B)∨(┐A∧┐B))=0。(b)得证。2.在自然推理系统中证明下面推理前提：xP(x)→x((P(x)∨Q(x))→R(x))，xP(x)，xQ(x)结论：xy(R(x)∧R(y))证明：(1)(x)P(x)→(x)((P(x)∨Q(x))→R(x))P(2)(x)P(x)P(3)(x)((P(x)∨Q(x))→R(x))T(1)(2)I(4)P(c)ES(2)(5)(P(c)∨Q(c))→R(c)US(3)(6)P(c)∨Q(c)T(4)I(7)R(c)T(5)(6)I(8)(x)Q(x)P(9)Q(d)ES(8)(10)(P(d)∨Q(d))→R(d)US(3)(11)Q(d)∨P(d)T(9)I(12)R(d)T(10)(11)I(13)R(c)∧R(d)T(7)(12)I(14)(y)(R(c)∧R(y))EG(13)(15)(x)(y)(R(x)∧R(y))EG(14)3．根据推理理论证明：每个学生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有学生都将有所作为，所以，一定有些学生是聪明的。证明：设P(e)：e是学生，Q(e)：e将有所作为，A(e)：e是勤奋的，B(e)：e是聪明的，个体域：人的集合，则命题可符号化为：前提：x(P(x)(A(x)∨B(x)))，x(A(x)Q(x))，x(P(x)Q(x))结论：x(P(x)∧B(x))。(1)x(P(x)Q(x))P(2)x(P(x)∨Q(x))T(1)，E(3)x(P(x)∧Q(x))T(2)，E(4)P(a)∧Q(a)T(3)，ES(5)P(a)T(4)，I(6)Q(a)T(4)，I(7)x(P(x)(A(x)∨B(x))P(8)P(a)(A(a)∨B(a))T(7)，US(9)A(a)∨B(a)T(8)(5)，I(10)x(A(x)Q(x))P(11)A(a)Q(a)T(10)，US(12)A(a)T(11)(6)，I(13)B(a)T(12)(9)，I(14)P(a)∧B(a)T(5)(13)，I(15)x(P(x)∧B(x))T(14)，EG4.证明AB=ACAB=ACB=C答案，方法一：恒等变形法B=B(BA)=B(AB)=B(AC)=(BA)(BC)=(AC)(BC)=(AB)C=(AC)C=C方法二：反证法.假设BC，则存在x(xB且xC),或存在x(xC且xB).不妨设为前者.若x属于A，则x属于AB但是x不属于AC，与已知矛盾；若x不属于A，则x属于AB但x不属于AC，也与已知矛盾.方法三：利用已知等式通过运算得到新的等式.由已知等式①和②可以得到(AB)(AB)=(AC)(AC)，即AB=AC.从而有A(AB)=A(AC)根据结合律得(AA)B=(AA)C由于AA=,化简上式得B=C.5.设偏序集A,R和B,S，定义AB上二元关系T:x,yTu,vxRuySv证明T为偏序关系.答案证证明自反性任取x,y,x,yABxAyBxRxySyx,yTx,y证明反对称性任取x,y,u,vx,yTu,vu,vTx,yxRuySvuRxvSy(xRuuRx)(ySvvSy)x=uy=vx,y=u,v证明传递性任取x,y,u,v,w,tx,yTu,vu,vTw,txRuySvuRwvSt(xRuuRw)(ySvvSt)xRwyStx,yTw,t得分评阅人四、计算题（共2小题，每小题8分，共16分）.1.设A={1,2,3},R={x,y|x,yA且x+2y6}，S={1,2,1,3,2,2},求（1）R的集合表达式（1分）（2）R1（1分）（3）domR,ranR,fldR（2分）（4）RS,R3（2分）（5）r(R),s(R),t(R)（2分）答案（1）R={1,1,1,2,2,1,2,2,3,1}（2）R1={1,1,2,1,1,2,2,2,1,3}（3）domR={1,2,3},ranR={1,2},fldR={1,2,3}（4）RS={1,2,1,3,2,2,2,3,3,2,3,3}R3={1,1,1,2,2,1,2,2,3,1,3,2}（5）r(R)={1,1,1,2,2,1,2,2,3,1,3,3}s(R)={1,1,1,2,2,1,2,2,3,1,1,3};t(R)={1,1,1,2,2,1,2,2,3,1,3,2}2.对给定的A,B和f,判断是否构成函数f：A→B.如果是,说明f：A→B是否为单射、满射、双射的.并根据要求进行计算.（1）A={1,2,3,4,5},B={6,7,8,9,10},f={1,8,3,9,4,10,2,6,5,9}.（1分）（2）A,B同(1),f={1,7,2,6,4,5,1,9,5,10}.（1分）（3）A,B同(1),f={1,8,3,10,2,6,4,9}.（1分）（4）A=B=R,f(x)=x3.（1分）（5）A=B=