离散数学题集.docVIP

1.下列语句不是命题的是( C )。 A.黄金是非金属。 B.要是他不上场，我们就不会输。 C.他跑100米只用了10秒钟，你说他是不是运动健将呢? D.他跑100米只用了10秒钟，他是一个真正的运动健将。 2.关于命题变元P和Q的大项M01表示( D )。 A.┐P∧Q B.┐P∨Q C.P∨┐Q D.P∧┐Q 3.公式(x)(y)(P(x,z)→Q(y))S(x,y)中的(x)的辖域是( B )。 A.(y)(P(x,z)→Q(y)) B.P(x,z)→Q(y) C.P(x,z) D.S(x,z) 4.下列等价式不成立的是( D )。 A.┐(x)A(x)(x)┐A(x) B.┐(x)A(x)(x)┐A(x) C.(x)(A(x)∧B(x))(x)A(x)∧(x)B(x) D.(x)(A(x)∨B(x))(x)A(x)∨(x)B(x) 5.公式(x)(y)(P(x,y)∧Q(z))→R(x)中的x( )。 A.只是约束变元 B.只是自由变元 C.既是约束变元又是自由变元 D.既非约束变元又非自由变元 6.设A={a,{a}}，则下列各式正确的是( )。 A.{a}∈p(A)(A的幂集) B.{a}p(A) C.{{a}}p(A) D.{a,{a}}p(A) 7.集合的以下运算律不成立的是( )。 A.A∩B=B∩A B.A∪B=B∪A C.AB=BA D.A-B=B-A 8.设N是自然数集，R是实数集，函数f：Ｎ→R，f(n)=lgn是( )。 A.入射 B.满射 C.双射 D.非以上三种的一般函数 9.设实数集R上的二元运算o为：xoy=x+y-2xy,则o不满足( )。 A.交换律 B.结合律 C.有幂等元 D.有零元 10.若(A，*)是一个代数系统，且满足结合律，则(A，*)必为( A )。 A.半群 B.独异点 C.群 D.可结合代数 11.设S是自然数集，则下列运算中不满足交换律的是( B )。 A.a*b=|a-b| B.a*b=ab C.a*b=max{a,b} D.a*b=min{a,b} 12.设图G′=V′，E′是图的生成子图，则必须( a )。 A.V′=V B.V′≠V但E′=E C.E′=E D.E′≠E且V′≠V 13.设有向图G有5个结点，4条边，且有一条有向路经过每个结点一次，则图G满足的最大连通性是( )。 A.不连通 B.弱连通 C.单侧连通 D.强连通 14.一个连通图G具有以下何种条件时，能一笔画出：即从某结点出发，经过图中每边仅一次回到该结点。( A )。 A.G没有奇数度结点 B.G有1个奇数度结点 C.G有2个奇数度结点 D.G没有或有2个奇数度结点 二、填空题(每小题2分，共30分) 1.设P：a2+b2=a2,Q:b=0,则PQ意思是说__等价____. 2.合式公式┐(Q→P)∧P是永___假___式. 3.合式公式(PQ)∧(QR)与PR的关系是_等价_____.(等价或蕴含选一) 4.命题“所有的猫都是动物”的谓词表达式为__________. 5.公式(x)A(x)→B(y)的前束范式为______. 6.设个体域为D={-2,3,6},F(x):x3,G(x):x5.则在此解释下公式(x)(F(x)∧G(x))的真值为_ ___. 7.设R是有限集A中的关系，若其关系矩阵MR的主对角线上的元素全为0，则R至少是__反自反____关系. 8.设A={a,b,c}中的关系R={a,b,b,c}，则R的对称闭包为S(R)=______. 9.设X={1,2,3},Y={a,b}，则从X到Y的不同的函数共有___6___个. 10.设A={0,1,2,3}，A中的序关系“”定义为：aba整除b，则a的最小元是 ，最大元是______. 11.只有两个元素的群有且只有___3___个子群. 12.一个格称为布尔代数，如果它是______格和______格. 13.设图G的邻接矩阵为M=，则G的可达性矩阵为______. 14.设一个平面图有v个结点，e条边，r个面，则它们的数量关系是______. 15.一个无向树中有6条边，则它有__7____个结点. 三、计算题(每小题6分，共24分) 1.求合式公式A=P→((P→Q)∧┐(┐Q∨┐P))的主析取范式和主合取范式. 2.设集合A={a,b,c},A中的关系R={a,a,a,c,b,c,c,c}.利用矩阵方法求R的传递闭包t(R). 一、单