离散数学试题库.doc

15.设D的结点数大于1，D=是强连通图，当且仅当（）A.D中至少有一条通路B.D中至少有一条回路C.D中有通过每个结点至少一次的通路D.D中有通过每个结点至少一次的回路1.设P：天下大雨,Q：他在室内运动,命题“除非天下大雨，否则他不在室内运动”可符合化为（）A.PQB.PQC.PQD.PQ2.下列命题联结词集合中，是最小联结词组的是（）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.$yx(x+y=0)C.xy(x+y=0)D.$x$y(x+y=0)6.下列命题中不正确的是（）A.xx-xB.xx-xC.A=xx,则xA且xAD.A-B=A=B7.设P=x|(x+1)24，Q=x|x2+165x,则下列选项正确的是（）A.PQB.PQC.QPD.Q=P8.下列表达式中不成立的是（）A.A(BC)=(AB) (AC)B.A(BC)=(AB) (AC)C.(AB)C=(AC) (BC)D.(A-B) C=(AC)-(BC)5对于公式(x) ($y)(P(x)Q(y)($x)R(x,y)，下列说法正确的是（）Ay是自由变元By是约束变元C($x)的辖域是R(x, y)D(x)的辖域是($y)(P(x)Q(y)($x)R(x,y)6设论域为1,2，与公式(x)A(x)等价的是（）AA(1)A(2)BA(1)A(2)CA(1)A(2)DA(2)A(1)14下列图是欧拉图的是（）15一棵树的3个4度点，4个2度点，其它的都是1度，那么这棵树的边数是（）A13B14C15D16二、填空题16.设A=1,2,3，B=3,4,5，则AA=_，AB=_。17.设A=1,2,3,4,5，RAA，R=，,，则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.设图G,V=v1,v2,v3,v4,若G的邻接矩阵，则deg-(v1)=_ _,deg+(v4)=_。25.给定集合A=1,2,3,4,5，在集合A上定义两种关系：R=,S=,，则，。20设A=,B=2,4，则P(P(A)=_，AB_。21设A=1,2,3,4, A上的二元关系R=,S=,，则R2S=_，(R-1)2=_。25若一条_中，所有的_均不相同，称为迹。三、计算题（本大题共5小题，第26、27题各5分，第28、29题各6分，第30题8分，共30分）26.设A=a,b,c,d，A上的等价关系R=,IA，画出R的关系图，并求出A中各元素的等价类。27.构造命题公式（PQ） （PQ）的真值表。28.求下列公式的主析取范式和主合取范式：P（QP）（PQ）29.设A=a, b, c, d, e，R为A上的关系，R=，, , , IA，试画的哈斯图，并求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请通过等值演算法求(PQ)(PQ)的主析