离散数学模拟题及答案_第1页
离散数学模拟题及答案_第2页
离散数学模拟题及答案_第3页
离散数学模拟题及答案_第4页
离散数学模拟题及答案_第5页
全文预览已结束

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、一、 填空1不能再分解的命题称为_,至少包含一个联结词的命题称为_。2一个命题公式A(P, Q, R)为真的所有真值指派是000, 001, 010, 100,则其主析取范式是_,其主合取范式是_。3设 A=a,b,c,B=b,c,d,e,C=b,c,则( A È B ) Å C _。4幂集 P(P(Æ) _。5设A为任意集合,请填入适当运算符,使式子A_A=Æ;A_A=Æ成立。6设A=0,1,2,3,6,R=x,y|xy(x,yA)yx(mod 3),则D(R)=_,R(R)=_。7称集合S是给定非空集合A的覆盖:若S=S1,S2,Sn,其中

2、SiA,SiØ,i=1,2,n,且_ _;进一步若_ _,则S是集合A的划分。8两个重言式的析取是_ _式,一个重言式和一个永假式的合取式是 式。9公式 (PQ) (PQ)的主析取范式是 。10. 已知=ab,c是A=a,b,c的一个划分,由决定的A上的一个等价关系是 。二、 证明及求解1求命题公式(PQ)(QP)的主析取范式。2推理证明题1)ØPQ,ØQR,R®SÞP®S。2) ("x)(P(x)®Q(y)R(x),($x)P(x)ÞQ(y)($x)(P(x)R(x)3设A=0,1,2,3,R=x,y|

3、x,yA(y=x+1y=),S=x,y|x,yA(x=y+2)。试求RSR。4证明:R是传递的ÛR*RÍR。5设R是A上的二元关系,S=<a, b>| 存在cA,使<a, c>R,且<c, b>R。证明:若R是等价关系,则S也是等价关系。6若f:AB和g:BC是双射,则(gof)-1=f-1og-1。7符号化下列命题,并证明结论的有效性。只要今天天气不好,就一定有考生不能提前进入考场,当且仅当所有考生提前进入考场,考试才能准时进行。所以,如果考试准时进行,那么天气就好。8画出集合S=1,2,3,4,5,6在偏序关系“整除”下的哈斯图,并讨

4、论:1)写出 1,2,3,4,5,6的最大(小)元和极大(小)元;2)分别写出2,3,6和2,3,5的上(下)界、上(下)确界。9. 设R是A=1,2,3,4,5上的二元关系,R=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,求r(R)、s(R)和t(R),并作出它们及R的关系图。参考答案一、填空1原子命题;复合命题2;3a,d,e4Æ,Æ5Å;60,3,6;0,3,67S1S2SnS; SiSjÆ,1i<jn8重言;永假910. <a,a>

5、;,<b,b>,<b,c>,<c,b>,<c,c>二、证明及求解1解:(Øp®q)®( Øqp)ÛØ(Øp®q)(pØq)ÛØ(pq)(pØq)Û(ØpØq)(pØq) Û(ØppØq)(ØqpØq)Û(pØq)ÛM1Ûm0m2m321)证明:(1)P 附加前提(2)ØPQ P(3)Q T(

6、1)(2),I(4)ØQR P(5)R T(3)(4),I(6)R®S P(7)S T(5)(6),I(8)P®S CP2) 证明(1)$xP(x)P(2)P(a)ES(1)(3)"x(P(x)®Q(y)R(x)P(4)P(a)®Q(y)R(a)US(3)(5)Q(y)R(a)T(2)(4),I(6)Q(y)T(5),I(7)R(a)T(5),I(8)P(a)R(a)T(2)(7),I(9)$x(P(x)R(x)EG(8)(10)Q(y)$x(P(x)R(x)T(6)(9),I3解:R=<0,1>,<1,2>,

7、<2,3>,<0,0>,<2,1>,S=<2,0>,<3,1>,RS=<1,0>,<2,1>,RSR=<1,1>,<1,0>,<2,2>4证明 若R是传递的,则<x,y>R*RÞ$z(xRzzSy)ÞxRccSy,由R是传递的得xRy,即有<x,y>R,所以R*RÍR。反之,若R*RÍR,则对任意的x、y、zA,如果xRz且zRy,则<x,y>R*R,于是有<x,y>R,即有xRy,所以R

8、是传递的。5证明 由R是A上的等价关系,知<a,a>R,故存在aA,使<a,a>R,且<a,a>R,故<a,a>S。若<a, b>S,则存在cA,使<a,c>R,且<c,b>R,由R的对称性,<b,c>R,且<c,a>R,故<b,a>S。若<a, b>S,<b,c>S,存在dA,使<a,d>R,且<d,b>R,存在eA,使<b,e>R,且<e,c>R,由R的传递性,故存在eA,使<a,e>R,

9、且<e,c>R,所以<a, c>S。故S是等价关系。6证明:1)因为f:AB和g:BC均是双射,故f-1和g-1均存在,且f-1:BA,g-1:CB,所以f-1og-1:CA。由f和g是双射,可知gof也是双射,故(gof)-1存在且(gof)-1:CA。D(f-1og-1)=D(gof)-1=C2) 对任意cC存在唯一bB,使得g(b)=c存在唯一aA,使得f(a)=b,故 (f-1og-1)(c)= (f-1(g-1(c)=f-1(b)=a 但(gof)(a)=g(f(a)=g(b)=c 故(gof)-1(c)=a 因此对任意cC有:(gof)-1(c)= (f-1

10、og-1)(c) 由1),2)可知 f-1og-1(gof)-17解 设P:今天天气好,Q:考试准时进行,A(e):e提前进入考场,个体域:考生的集合,则命题可符号化为:ØP®$xØA(x),"xA(x)«QÞQ®P。(1)ØP®$xØA(x) P(2)ØP®Ø"xA(x) T(1),E(3)"xA(x)®P T(2),E (4)"xA(x)«Q P(5)("xA(x)®Q)(Q®&qu

11、ot;xA(x) T(4),E(6)Q®"xA(x) T(5),I(7)Q®P T(6)(3),I81)最大元:无;最小元:1;极大元:4,5,6;极小元:12)2,3,6的上界:6;下界:1;上确界:6;下确界:1。2,3,5的上界:无;下界:1;上确界:无;下确界:1。9. 解:r(R)=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,1>,<2,2>,<3,3>,<5,5>s(R)=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<1,2>,<4,2>,<4,3>R2=R5=<2,2>,<2,4>,<3,4>,<4,4>,<5,1>,<5,5>,<5,4>R3=<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<5,4>R4=<2,2>,<2,4>,<

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论