[安工大离散数学试卷.docxVIP

200 9-2010 学年第一学期期末考试《离散数学B》 试卷（A）一．单项选择题(每题2分，共30分)1．下列命题公式中不是重言式的是（　　　）A. (┐PQ)→(Q→R) B. P→(Q→Q) C. (PQ)→P D. P→(PQ)2．在0（ ）之间写上正确的符号。A. =　 B. 　 C. 　 D. 3．设个体域是整数集，则下列命题的真值为真的是（　　　）A.xy (xy=y) B. xy(x+y=y)　C.xy(x+y=x) 　 　 D. xy(y=2x)4．关于谓词公式（x）(y)(P(x,y)∧Q(y,z))∧(x)p(x,y),下面的描述中错误的是（　　　）A．（x）的辖域是（y）（P（x,y）∧Q(y,z)）B．z是该谓词公式的约束变元C．（x）的辖域是P（x,y）D．x是该谓词公式的约束变元5．设论域D={a,b}，与公式(x)A（x）等价的命题公式是（　　　）A．A（a）∧A（b）B．A（a）→A（b）C．A（a）∨A（b）D．A（b）→A（a）6．集合A={1,2,…,10}上的关系R={x,y|x+y=10,x,yA}，则R 的性质（ ）。A.自反的　　B.对称的C.传递的，对称的 D. 传递的7．设A={a,{a}}，下列命题错误的是（ ）。A. {a}P(A)　B. {a}P(A)　C. {{a}}P(A)　D. {{a}}P(A)8．设Z是整数集，E={…，-4，-2，0，2，4，…}，f：Z→E，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的运算结果是（　　　）A．{〈4，1〉，〈2，3〉，〈4，2〉}B．{〈2，4〉，〈2，3〉，〈4，2〉}C．{〈4，1〉，〈2，3〉，〈2，4〉}D．{〈2，2〉，〈3，1〉，〈4，4〉}10．设有代数系统G=〈A，*〉，其中A是所有命题公式的集合，*为命题公式的合取运算，则G的幺元是（　　　）A．矛盾式B．重言式C．可满足式D．公式p∧q11．在自然数集N上，下列哪种运算是可结合的？（） A. a*b=a-b　B. a*b=max{a,b}　C.a*b=a+2b　D. a*b=|a-b|12．、有限布尔代数的元素的个数一定等于（ ）。A . 偶数　B. 奇数 C. 4的倍数D. 2的正整数次幂13．设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。 A. 10 B.4 C. 8 D. 1214．设无向图G的边数为m，结点数为n，则G是树等价于（　　　）A．G连通且m=n+1B．G连通且n=m+1C．G连通且m=2nD．每对结点之间至少有一条通路15．设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式 x(P(x)Q(x))在哪个个体域中为真?( )A. 自然数　B.实数　C .复数　　D . (A)--(C)均成立二、填空题（每题2分，共20分）1．公式(PQ)(PQ)化简为 ，公式 Q(P(PQ))可化简为 。2．命题“存在一些人是大学生”的否定是________________________。3．公式（x）((A(x)B(y，x)) （z）（ C(m，z))D(n)）中，自由变元是 ，约束变元是 。4．若集合S的基数|S|=5，则S的幂集的基数|P(S)|= 。5．设Ａ＝｛1,2,3,4,5,6｝，B={1,2,3}，从Ａ到B的关系Ｒ＝｛〈x,y〉|x=y2｝，则R= 。6．设A={a,b,c,d}, R={〈a,c〉，〈c,b〉，〈b,a〉，〈a,d〉}，则r(R)= ,s(R)= ,t(R)= 。7．设A={2,4,6}，A上的二元运算*定义为：a*b=max{a,b}，则在独异点A,*中，单位元是 ，零元是 。8．有n个结点的树，其结点度数之和是 。9..群G,*的等幂元是 ，有 个。10.n阶无向完全图Kn 的边数是 ，每个结点的度数是 。三．（6分）求命题公式(PR)(QR)P的主析取范式和主合取范式。四．（6分）证明：A→(B→C)，C→(DE)，F→(DE),A=B→F五．（5分）证明：(A－B)(A－C)=A－(BC)六．（10分）设A=｛1，2，3｝，P（A）是A的幂集，是集合的包含关系，证明：〈P（A），〉偏序集，画出它的哈斯图，并证明该偏序集为格。七．（10分）设A={1,2,…,10}。下列哪个是A的划分？若是划分，则写出它们诱导的等价关系。（1）B={{1,3,6},{2,8,10},{4,5,7}};（2）C={{1,5,7},{2,4,8,9},