安工大离散数学试卷

1、200 9-2010 学年第一学期期末考试离散数学B 试卷（A）一单项选择题(每题2分，共30分)1下列命题公式中不是重言式的是（）A. (PQ)(QR) B. P(QQ) C. (PQ)P D. P(PQ)2在0（ ）之间写上正确的符号。A. = B. C. D. 3设个体域是整数集，则下列命题的真值为真的是（）A.x$y (xy=y) B. $xy(x+y=y)C.$xy(x+y=x) D. x$y(y=2x) 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）

2、的辖域是P（x,y）Dx是该谓词公式的约束变元5设论域D=a,b，与公式(x)A（x）等价的命题公式是（）AA（a）A（b）BA（a）A（b）CA（a）A（b）DA（b）A（a）6集合A=1,2,10上的关系R=|x+y=10,x,yA，则R 的性质（ ）。A.自反的B.对称的 C.传递的，对称的 D. 传递的7设A=a,a，下列命题错误的是（ ）。A. aP(A)B. aP(A)C. aP(A)D. aP(A)8设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

3、，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在自然数集N上，下列哪种运算是可结合的？（ ） A. a*b=a-bB. a*b=maxa,bC.a*b=a+2bD. a*b=|a-b|12、有限布尔代数的元素的个数一定等于（ ）。A . 偶数B. 奇数 C. 4的倍数 D. 2的正整数次幂13设无向图G有18条边且每个顶点的度数都是3，则图G有( )个

4、顶点。 A. 10 B.4 C. 8 D. 1214设无向图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)在哪个个体域中为真?( )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若集

5、合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=maxa,b，则在独异点中，单位元是 ，零元是 。8有n个结点的树，其结点度数之和是 。9.群的等幂元是 ，有 个。10.n阶无向完全图Kn 的边数是 ，每个结点的度数是 。三（6分）求命题公式(PR)(QR)P的主析取范式和主合取范式。四（6分）证明：A(BC)，C(DE)，F(DE),A=BF五（

6、5分）证明：(AB)(AC)=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,3,5,6,10;（3）D=1,2,7,3,5,10,4,6,8,9八（8分）I上的二元运算*定义为：a,bI，a*b=a+b-2。试证：为群。九（5分）设无向图G=，|E|=12。已知有6个3度顶点，其他顶点的度数均小于3。问G中至少有多少个顶点？2009

7、2010学年第一学期期末考试离散数学B试卷（A）一单项选择题(152=30分)1（A）；2（D）；3.(D)；4(B)；5(A) ；6.(B)；7.(B)；8.(C);9.(A)；10. (B)；11.(B) 12.(D) 13.(D); 14.(B);15.(A) 二填空题(171=17分) 1P QP;2所有人都不是大学生； 3y,m,n x,z;4. 32;5R=, 6r(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,.,，72,68.2(n-1)9.e,110n(n-1)/2,(n-1)三(6分)其中主

8、析取范式和主合取范式各占4分 (PR)(QR)P（析取范式）(P(QQ)R)(PP)QR)(P(QQ)(RR)(PQR)(PQR)(PQR)(PQR)( PQR)( PQR)(PQR)(PQR) (PQR)(PQR)(PQR)(PQR) (PQR)(PQR) (主析取范式)（(PR)(QR)P）(PQR)(PQR）（原公式否定的主析取范式）(PR)(QR)P (PQR)(PQR)（主合取范式）四(8分)(1) A P（附加前提）(2) A(BC) P (3) BC T（1），（2）(4) B P(附加前提)(5) C T（3），（4）(6) C(DE) P(7) DE T（5），（6）(8)

9、F(DE) P(9) F T（7），（8）(10) BF CP 证明方法不唯一，只要遵循逻辑规则即可。五(6分)解(A-B)(A-C)=(AB)(AC) =A (B) (C)=A(B C)= A-(BC)六（10分）证明: 验证P（A）中运算满足自反，反对称，传递；从哈斯图中证明任意两个元素都有上确界和下确界即可。 七(10分)（1）和（2）都不是A的划分。（3）是A的划分。其诱导的等价关系是I,。八(8分) 证明：（1）a,b I，a+b-2I，*满足封闭律。（2）a,b,cI，(a*b)*c=(a*b)+c-2=(a+b-2)+c-2=a+b+c-4, a*(b*c)=a+(b*c)-2=a+(b+c-2)-2=a+b+c-4。故(a*b)*c= a*(b*c)，从而*满足结合律。（3）记e=2。对aI，a*2=a+2-2=a=2+a-2=2*a.。故e=2是I关于运算*的单位元。（4）