资源描述:
《离散数学复习资料(word版)》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库。
1、2008年离散数学试题一、单项选择题(本大题共15小题,每小题1分,共15分)1.设P:天下大雨,Q:他在室内运动,命题“除非天下大雨,否则他不在室内运动”可符合化为( )A.ùP∧QB.ùP→QC.ùP→ùQD.P→ùQ2.下列命题联结词集合中,是最小联结词组的是( )A.{ù,}B.{ù,∨,∧}C.{ù,∧}D.{∧,→}3.下列命题为假命题的是( )A.如果2是偶数,那么一个公式的析取范式惟一B.如果2是偶数,那么一个公式的析取范式不惟一C.如果2是奇数,那么一个公式的析取范式惟一D.如果2是奇数,那么一个公式的析取范式不惟一5.若个体域为整
2、数减,下列公式中值为真的是( )A.x$y(x+y=0)B.$yx(x+y=0)C.xy(x+y=0)D.ù$x$y(x+y=0)6.下列命题中不正确的是( )A.x∈{x}-{{x}}B.{x}Í{x}-{{x}}C.A={x}∪x,则x∈A且xÍAD.A-B=ÆÛA=B7.设P={x
3、(x+1)2≤4},Q={x
4、x2+16≥5x},则下列选项正确的是( )A.PÉQB.PÊQC.QÉPD.Q=P8.下列表达式中不成立的是( )A.A∪(BÅC)=(A∪B)Å(A∪C)B.A∩(BÅC)=(A∩B)Å(A∩C)C.(AÅB)×C=(A×C)Å
5、(B×C)D.(A-B)×C=(A×C)-(B×C)10.下列集合对所给的二元运算封闭的是( )A.正整数集上的减法运算B.在正实数的集R+上规定*为a*b=ab-a-ba,b∈R+C.正整数集Z+上的二元运算*为x*y=min(x,y)x,y∈Z+D.全体n×n实可逆矩阵集合Rn×n上的矩阵加法11.设集合A={1,2,3},下列关系R中不是等价关系的是( )A.R={<1,1>,<2,2>,<3,3>}B.R={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>}C.R={<1,1>,<2,2>,<3,3>,<1,2>}D.R={<1,1>,
6、<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>}13.设集合A={a,b,c}上的关系如下,具有传递性的是( )A.R={,,,}B.R={,}C.R={,,,}D.R={}14.含有5个结点,3条边的不同构的简单图有( )A.2个B.3个C.4个D.5个15.设D的结点数大于1,D=是强连通图,当且仅当( )A.D中至少有一条通路B.D中至少有一条回路C.D中有通过每个结点至少一次的
7、通路D.D中有通过每个结点至少一次的回路二、填空题16.设A={1,2,3},B={3,4,5},则AÅA=___________,AÅB=___________。17.设A={1,2,3,4,5},RÍA×A,R={<1,2>,<3,4>,<2,2>},则R的自反闭包r(R)=__________。对称闭包t(R)=__________。18.设P、Q为两个命题,德摩根律可表示为_____________,吸收律可表示为____________。19.对于公式x(P(x)∨Q(x)),其中P(x)∶x=1,Q(x)∶x=2,当论域为{1,2}时,其真值为___
8、__________,当论域为{0,1,2}时,其真值为_____________。21.3个结点可构成_________个不同构的简单无向图,可构成________个不同构的简单有向图。23.设图G,V={v1,v2,v3,v4},若G的邻接矩阵,则deg-(v1)=_________,deg+(v4)=____________。25.给定集合A={1,2,3,4,5},在集合A上定义两种关系:R={<1,2>,<3,4>,<2,2>},S={<4,2>,<2,5>,<3,1>,<1,3>},则,。三、计算题26.设A={a,b,c,d},A上的等价
9、关系R={,,,}∪IA,画出R的关系图,并求出A中各元素的等价类。27.构造命题公式ù(P∨Q)(ùP∧Q)的真值表。28.求下列公式的主析取范式和主合取范式:P→((Q→P)∧(ùP∧Q))29.设A={a,b,c,d,e},R为A上的关系,R={,,,,,,}∪IA,试画的哈斯图,并求A中的最大元,最小元,极大元,极小元。30.给定图G如图所示,(1)G中长度为4的路有几条?其中有几条回路?(2)写出G的可达矩阵。四、证明题31.设(L,
10、≤)是格,试证明:a,b