离散数学试题库

15.设D的结点数大于1，D=V,E是强连通图，当且仅当（）A.D中至少有一条通路B.D中至少有一条回路C.D中有通过每个结点至少一次的通路D.D中有通过每个结点至少一次的回路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是奇数，那么一个公式的析取范式不惟一4.谓词公式x(P(x)∨yR(y))→Q(x))中变元x是（）A.自由变元B.约束变元C.既不是自由变元也不是约束变元D.既是自由变元也是约束变元5.若个体域为整数集，下列公式中值为真的是（）A.xy(x+y=0)B.yx(x+y=0)C.xy(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|(x+1)2≤4}，Q={x|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)(B×C)D.(A-B)×C=(A×C)-(B×C)5．对于公式(x)(y)(P(x)∧Q(y))→(x)R(x,y)，下列说法正确的是（）A．y是自由变元B．y是约束变元C．(x)的辖域是R(x,y)D．(x)的辖域是(y)(P(x)∧Q(y))→(x)R(x,y)6．设论域为{1,2}，与公式(x)A(x)等价的是（）A．A(1)∨A(2)B．A(1)→A(2)C．A(1)∧A(2)D．A(2)→A(1)14．下列图是欧拉图的是（）15．一棵树的3个4度点，4个2度点，其它的都是1度，那么这棵树的边数是（）A．13B．14C．15D．16二、填空题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}时，其真值为_____________,当论域为{0,1,2}时，其真值为_____________。23.设图GV,E,V={v1,v2,v3,v4},若G的邻接矩阵0001001111011010A，则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}，则_______________SR，_______________RS。20．设A=,B={2,4}，则P(P(A))=___________，A×B___________。21．设A={1,2,3,4},A上的二元关系R={1,2,2,4,3,3},S={1,3,2,4,4,2}，则R2S=___________，(R-1)2=___________。25．若一条___________中，所有的___________均不相同，称为迹。三、计算题（本大题共5小题，第26、27题各5分，第28、29题各6分，第30题8分，共30分）26.设A={a,b,c,d}，A上的等价关系R={a,b,b,a,c,d,d,c}∪IA，画出R的关系图，并求出A中各元素的等价类。27.构造命题公式（P∨Q）（P∧Q）的真值表。28.求下列公式的主析取范式和主合取范式：P→（（Q→P）∧（P∧Q））29.设A={a,b,c,d,e}，R为A上的关系，R={a,d，a,c，a,b,a,e,b,e,c,e,d,e}∪IA，试画A，R的哈斯图，并求A中的最大元，最小元，极大元，极小元。30.给定图G如图所示，（1）G中长度为4的路有几条？其中有几条回路？（2）写出G的可达矩阵。三、计算题（本大题共6小题，每小题5分，共30分）26．给定论域D={1,2}，f(1)=2,f(2)=1,S(1)=F,S(2)=T,G(1,2)=T,G(2,1)=T,在该赋值下，求式子x(S(f(x))∧G(x,f(x)))的真值。27．请通过等值演算法求┐(P∧Q)→(P∨Q)的主析取范式。28．设A={1,2,3,4}，给定A上二元关系R={1,1,1,2,2,4,4,2}，求R的传递闭包。30．用矩阵的方法求题30图中结点ui，u5之间长度为2的路径的数目。31．求题31图的最小生成树。