离散数学试题库

1、15.设D的结点数大于1，D=<V,E>是强连通图，当且仅当（）A.D中至少有一条通路B.D中至少有一条回路C.D中有通过每个结点至少一次的通路D.D中有通过每个结点至少一次的回路1.设P：天下大雨,Q：他在室内运动,命题“除非天下大雨，否则他不在室内运动”可符合化为（）A.ùPQB.ùPQC.ùPùQD.PùQ2.下列命题联结词集合中，是最小联结词组的是（）A.ù， B.ù，C.ù，D.，3.下列命题为假命题的是（）A.如果2是偶数，那么一个公式的析取范式惟一B.如果2是偶数，那么一个公式的析取范式不

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.xÍx-xC.A=xx,则xA且xÍAD.A-B=ÆÛA=B7.设P=x|(x+1)24，Q=x|x2+165x,则下列选项正

3、确的是（）A.PÉQB.PÊQC.QÉPD.Q=P8.下列表达式中不成立的是（）A.A(BÅC)=(AB) Å (AC)B.A(BÅC)=(AB) Å (AC)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)，下列说法正确的是（）Ay是自由变元By是约束变元C($x)的辖域是R(x, y)D("x)的辖域是($y)(P(

4、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，则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为两个命题

5、，德摩根律可表示为_，吸收律可表示为_。19.对于公式x(P(x)Q(x)，其中P(x)x=1,Q(x)x=2,当论域为1,2时，其真值为_ ,当论域为0,1,2时，其真值为_。23.设图G<V,E>,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>，则，。20设A=Æ,B=2,4，则P(P(A

6、)=_，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.构

7、造命题公式ù（PQ） （ùPQ）的真值表。28.求下列公式的主析取范式和主合取范式：P（QP）（ùPQ）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请通过等值演算法求(PQ)(PQ)的主析取范式。28设A=1,2,3