离散数学试卷.doc

离散数学 试卷（A）一单项选择题(每题2分，共30分)1下列命题公式中不是重言式的是（）Ap(qr)Bp(qp)Cp(pp)D(p(qr)(q(pr)2下列语句中为命题的是（）A这朵花是谁的？B这朵花真美丽啊！C这朵花是你的吗？D这朵花是他的。3设个体域是整数集，则下列命题的真值为真的是（）Ayx(xy=1)Bxy (xy0)Cxy (xy=y2)Dyx(xy=x2)4关于谓词公式（x）(y)(P(x,y)Q(y,z)(x)p(x,y),下面的描述中错误的是（）A（x）的辖域是（y）（P（x,y）Q(y,z)）Bz是该谓词公式的约束变元C（x）的辖域是P（x,y）Dx是该谓词公式的约束变元5设论域D=a,b，与公式xA（x）等价的命题公式是（）AA（a）A（b）BA（a）A（b）CA（a）A（b）DA（b）A（a）6集合A=1，2，3上的下列关系矩阵中符合等价关系条件的是（）ABCD7设A=，B=P（P（A），以下不正确的式子是（）A ， ， ， 包含于BB 包含于BC ， 包含于BD ， ， 包含于B8设Z是整数集，E=，-4，-2，0，2，4，f：ZE，f（x）=2x，则f（）A仅是满射B仅是入射C是双射D无逆函数9 设A=1，2，3，4，5，A上二元关系R=1，2，3，4，2，2，S=2，4，3，1，4，2，则S-1R-1的运算结果是（）A4，1，2，3，4，2B2，4，2，3，4，2C4，1，2，3，2，4D2，2，3，1，4，410设有代数系统G=A，*，其中A是所有命题公式的集合，*为命题公式的合取运算，则G的幺元是（）A矛盾式B重言式C可满足式D公式pq11在实数集合R上，下列定义的运算中不可结合的是（）Aa*b=a+b+2abBa*b=a+bCa*b=a+b+ab Da*b=a-b12下列集合关于所给定的运算成为群的是（）A已给实数a的正整数次幂的全体，且a0，1，-1，关于数的乘法B所有非负整数的集合，关于数的加法C所有正有理数的集合，关于数的乘法D实数集，关于数的除法13设无向图中有6条边，有一个3度顶点和一个5度顶点，其余顶点度为2，则该图的顶点数是（）A3B4C5D614设无向图G的边数为m，结点数为n，则G是树等价于（）AG连通且m=n+1BG连通且n=m+1CG连通且m=2nD每对结点之间至少有一条通路15设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式 $x(P(x)Q(x)在哪个个体域中为真?( )(1) 自然数(2) 实数 (3) 复数(4) (1)-(3)均成立二、填空题（每题2分，共20分）1不能再分解的命题称为_，至少包含一个联结词的命题称为_。2命题“2是偶数或-3是负数”的否定是_。3使公式（x）（y）（A（x）B（y）（x）A（x）（y）B（y）成立的条件是_不含有y，_不含有x。4设A为任意集合，请填入适当的运算符，使式子A_A=；A_A=成立。5设A=0，1，2，3，6，R=x,y|xy(x,yA)yx(mod 3)，则domR=_，ranR=_。6称集合S是给定非空集合A的覆盖：若S=S1，S2，Sn，其中SiA，Si，i=1，2，n，且_；进一步若_，则S是集合A的划分。7对实数的普通加法和乘法，_是加法的幂等元，_是乘法的幂等元。8在代数系统A，*中，A=a，*是A上二元运算，则该代数系统的单位元是_，零元是_。9设A，是偏序集，若A中_都有最小上界和_则称A关于偏序构成格。10若一条路中，所有边均不相同，则此路称作_；若一条路中所有的结点均不相同，则称此路为_三（8分）求命题公式（pq）（qp）的主析取范式和主合取范式。四（8分）设A是非空集合，P（A）是A的幂集，是集合的包含关系，证明：P（A），是布尔格。五（8分）设A=a,b,c,d, R=a,c，c,b，b,a，a,d，画R的关系图，并求r(R),s(R),t(R)。六（10分）设H是形如的22阶矩阵的集合，H中定义通常的矩阵乘法运算*。验证是群。七（8分）已知一棵无向树中有2个2度顶点、1个3度顶点、3个4度顶点，其余顶点度数都为1。问它有多少个1度顶点？八（8分）符号化命题并推证其结论：所有有理数是实数，某些有理数是整数，因此某些实数是整数A卷：一单项选择题(152=30分)1（A）；2（D）；3.(C)；4(B)；5(C) ；6.(B)；7.(D)；8.(C);9.(A)；10. (B)；11.(D) 12.(C) 13.(B); 14.(B);15.(A) 二填空题(102=20分) 1原子命题 复合命题22不是偶数并且-3不是负数 3A（x） B(y)4或- 50，3，6 0，3，6 6SI=A, SISJ=(ij)70,1或08.a,a9.任意两元素，下确界或最大下界10迹，通路三(8分)其中主析取范式和主合取范式各占4分 主合取范式：（pq）（qp） ( P q) (q p) (P q) (Pq) (Pq) (Pq) (PqP) (Pqq) Pq主析取范式: (Pq) (pq) (Pq)四(8分) 证明：p(A)为A的幂集，p(A)中的“”满足自反性，反对称性和传递性，并且S1,S2p(A), S1 S2为S1 S2的最小上界，S1 S2为S1，S2的最大下界，因此P（A），是格。五(8分)解：r(R)=,a,c，c,b，b,a，a,d S(R)= a,c，c,b，b,a，a,d, T(R)= a,c，c,b，b,a，a,d,，,，,六（10分）证明: 验证在H中运算*满足封闭性，可结合性，幺元为单位矩阵，并且每个元素都有逆元即可。 七(8分)解:设度 数为1的结点有K个，边的数目为E，则根据题意有：2*2+3*1+4*3+K=2E （1）（握手定理） 树中结点数目为2+1+3+K=6+K 由树的定义知：E=6+K-1 （2） 联立（1），（2）得K=9 八(8分) 解：设R（x）:x为实数，Q（x）：x为有理数，I （x）：x为整数 （x）（Q（x） R（x），（x）（Q（x） I （x）（x）（R（x）I （x） （1）（x）（Q（x） I （x） P （2）Q（a）I(a) E