安工大离散数学试卷.doc

2010-2011学年第一学期期末考试离散数学B试卷（A）一单项选择题(每题2分，共30分)1、设A是正整数集，R=(x，y)|x，yAx+3y=12，则R (3，4，62，3，4)=（ ）.A O/BC，D，2、设有A=a,b,c上的关系R=,，则R具有( ) A. 自反性 B. 对称性 C. 传递性 D. 反对称性3、若A-B=，则下列哪个结论不可能正确？( )(A) A= (B) B=(C) AB (D) BA4、判断下列命题哪个正确？()(A) 若ABAC，则BC (B) a,b=b,a (C) P(AB)P(A)P(B) （P(S)表示S的幂集）(D) 若A为非空集，则AAA成立。5、设A=a,a，下列命题错误的是（ ）。(A) aP(A)(B) aP(A)(C) aP(A)(D) aP(A)6、集合的以下运算律不成立的是( ).A. AB=BAB. AB=BAC. AB=BAD. A-B=B-A7、下述不是命题的是( ). A. 今天天气真好啊! B. 明天下雨. C. 2是偶数. D. 这朵花是红色的8、设P,Q,R是命题公式,则（PR）( ). A. P B. PR C. R D. R9、设B是不含变元x的公式，谓词公式(x)(A(x)B)等价于( )A.(x)A(x)B B. (x)A(x)B C. A(x)B D.(x)A(x)(x)B10、谓词公式(x)(P(x)(y)R(y)Q(x)中的x( ). A.只是约束变元 B.只是自由变元 C.既非约束变元又非自由变元 D.既是约束变元又是自由变元11、设个体域A=a,b，公式xP(x)xS(x)在A中消去量词后应为（）.AP(x)S(x)BP(a)P(b)(S(a)S(b)CP(a)S(b)DP(a)P(b)S(a)S(b)12、设R为实数集，函数f：RR，f(x)=2x，则f是（ ）.A满射函数B入射函数C双射函数D非入射非满射13、下列运算中关于整数集不能构成半群的是（）.Aab=maxa, bBab=bCab=2abDab=|a-b|14、设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（ ）.A2个面B3个面 C4个面D5个面15、给定n个结点的一个图，它还是一个树的下列说法中，（）是不对的。A.无回路的连通图B.无回路但若增加一条新边就会形成回路C.连通且e=v-1，其中e是边数，v是结点数D.所有结点的度数2二、填空题（每空1分，共20分）1、命题P：若3+25，则三角形有3条边。P 的真值为_。2、命题“存在一些人是大学生”的否定是_。3、使公式(x)(y)(A(x)B(y)(x)A(x)(y)B(y)成立的条件是_不含有y，_不含有x.4、A=1,2,3,4上二元关系R=2，4，3，3，4，2，R的关系矩阵MR中m14= _5、设A=1，2，3，则A上的二元关系有 个，若R是集合A上的全域关系，则集合A关于R的商集为 。6、设X=1，2，3，函数f：XX，函数g：XX，f=,g=,，则fg=_，gf=_.7、当f:XY是_函数时，f有逆函数，且f -1。f=_。8、设A=1,5,8，A上的二元运算*定义为：a*b=maxa,b，则在独异点中，幺元是_，零元是_。9、设B,，0，1是布尔代数，其中代表补运算，对任意的aB,有aa=_,aa=_.10、设图G1=, G2=,且E2E1，如果 ，则称G2是G1的子图，如果 ，则称G2是G1的生成子图。11、下图的点连通度为 ，边连通度为_.12、在一棵有2个2度顶点，3个3度顶点，其余顶点都是树叶的无向树中应该有_片树叶。三、计算题（每5分，共20分）1、给定个体域D=a,b,A(a,a)=T,A(a,b)=F,A(b,a)=F,A(b,b)=T,试求(x)(y)A(x,y)的真值。2、设A=a,b,c,d, R=a,c，c,b，b,b，a,d，求r(R)，s(R) ，t(R)。3、已知集合A=2,3,4,6,8，B=2,3,6，R是A上的整除关系，求盖住集，画出R的哈斯图，并求B的最大元、最小元，极大元、极小元，上界、上确界，下界、下确界。4、求命题公式(PQ)(RP)的主析取范式和主合取范式。四、证明题（每题10分，共30分）1、将下列推理符号化并给出形式证明： 每一个大学生不是文科生就是理科生；有的大学生是优等生；小张不是文科生但他是优等生。因此，如果小张是大学生，他就是理科生。设P(x)：x是大学生，Q(x)：x是文科生，S(x)：x是理科生，T(x)：x是优等生，c：小张。2、设为群。若在G上定义二元运算,使得对任何元素x，yG，有xy = y*x。证明也是群。3、若R和S都是非空集A上的等价关系，证明RS是A上的等价关系。