大学《离散数学》期末考试试卷及答案-(1)

1、安徽大学2006-2007学年第1学期离散数学期末考试试卷( A卷)(时间120分钟)开课院(系、部) 姓名 学号题号一一二四五六七得分阅卷人得分得 分一、选择题(每小题2分，共20分)1 .下列语句中，哪个是真命题()A、x +2=4;B、我们要努力学习；C如果ab为奇数，那么a是奇数，或b是偶数；D、如果时间流逝不止，你就可以长生不老。2 .下列命题公式中，永真式的是()A (Pt Q)t P ； B、(Qt P) aP； C、(P aP)1 Q; D、Pt (P vQ)。3 .在谓词逻辑中，令 F(x)表示x是火车；G(y)表示y是汽车；L(x, y)表示x比y快。命题“并不是所 有的火

2、车比所有的汽车快”的符号表示中哪些是正确的？()I. -x-y(F(x) G(y). L(x, y)II. x y(F(x) G(y) -L(x,y)III. x y(F(x) G(y) - -L(x, y)A、仅 I ; B 、仅 III ; C 、I 和 II ; D 、都不对。4 .下列结论正确的是：()A 若 aUb = aUc ,则 B = C;B 、若 aUb工 ab,则 A = B;C 若 AnB = Anc,则B=C;D 、若 AUB且 C=D,则 aDcuBnD。5 .设 Ai = e ,A = , A3= P(e),A4 = P的)，以下命题为假的是()A A2 匚 A；

3、B A1 A3 ; C、A4 A2 ； D 、A4 匚 A3。6 .设R是集合A=a,b,c,d上的二元关系，R = a,d a, d, a a, , , b, d a,。下列哪些命题为真？()I. R -R是对称的II. R R是自反的III. R R不是传递的A、仅 I ；B 、仅 II ；C、I 和 II ； D 、全真。7 . R是二元关系且R = R4,则一定是传递的是()A R4 ；B、R3；C、R2 ； D、R。8 .设Ri和R2是非空集合A上的等价关系，确定下列各式，哪些是A上的等价关系()AA-R1; B、R-R2;C、RUr2； D、R1QR2。9 .函数f : X t Y

4、可逆的充要条件是：()A、A=B; B 、|A|=|B|； C、f 为双射；D、f 为满射。10 .下列集合中，哪个集合的基数与其他集合的基数不同()A Nn (N为自然数集，nN)； B、Nn (N为自然数集)；C RMR (R为实数集)；D 、x坐标轴上所有闭区间集合；、填空题(每小题2分，共32分)得分1 .全集 U =1,2,3,4,5 , A=1,5, B=1,2,3,4, C =2,5,则可求出：a n b =；p(a)n p(c)；C = o2 .设 A =3, | P(B) =16, | P(AU B) =64 ,贝U：B=，A B =,A-B =,A B =。3 .设 A=1

5、,2,3,4 , R是 A上的二元关系，且 R=, ,则 r (R) =；s(R)=;t(R) =;4,设A=1,2,3,4,5,则A上共有多少个二元关系 ? 其中有多少个等价关系?5 .设函数f : At A , BG A为A的子集。则：f(f,(B)B,f(f(B)B;当f为 函数时f (f/(B) = B ；当f为 函数时f(f(B) = B。离散数学试卷 共3页第3页得分三、综合题(第2小题16分，其它各小题8分，共48分)1 .求命题公式(P八Q)R)t P的主析取范式与主合取范式(要求用等值演算的方法求解)。(8分)2 .用推理规则证明：(每小题8分，共16分) P (Q t R)

6、 , -SvP, Q 永真蕴含 St R。前提:Vx(F(x)t (Q(y)AR(x) , 一F (x)；结论：(F (x)八 R(x)。3 .设集合A=a,b,c, P(A)是集合A的哥集，试给出 P(A),的哈斯图，并指出子集a,b的极大元、极小元、最大元、最小元、上界、下界、最小上界、最大下届(如果存在的话)。(8分)4 .设R是集合A上的关系，令 S=a,b 三cw凡使a,cw R且c,bw R,证明：如果 R是 等价关系，则S也是等价关系。(8分)5 .已知 f : N m N t N , f(x, y a) =x2 + y2。请问：(8 分)f是单射吗？f是满射吗？计算f (0)。

7、计算 f( , )。安徽大学2006-2007学年第1学期离散数学期末考试试卷答案（A卷）（时间120分钟）、选择题(每小题2分，共20分)1. C;2.D3G4.B;5.A;6.C;7.B;8.D;9.C;10.A二、填空题(每空2分，共32分)1 5； 屯5 ； 1,3,42. 4, 1, 2, 5;,3. , ,254. 2 ,525. 三，满射，二，单射 三、综合题(第2小题16分，其它各小题8分，共48分)6.A= (P Q) -R) Pu -(P Q) -R) P=(-P -Q) R) Pu (P aRQaRP2 分=(一P R) (-Q Q) (-Q R) (P -P) (P (

8、Q -Q) (R -R)=(一P Q R) (一P-QR)(P-QR)(一P-QR)(P Q R) (P Q-R)(P-QR)(P-Q-R)=(-P Q R) (一P-QR)(P-QR)(PQ R)(P aQ aR) v(P aQ aR)(主析取范式)6 分A= (-P -Q -R) (一P Q -R)Au (一A)u 一(十 Q -R) (_P Q -R)u (PvQvR) a(P vQ vR)(主合取范式)8 分7. 证明：一S PP1分(2)SP （附加前提）2分PT ,(2) I 3分(4)P (Q R)P4分Q RT ,(4) I 5分(6)QP6分RT ,(6)I 7分(8)S R

9、CP (2),(7)8分证明:xF (x)P1分(2)F(c)ES 2分-x(F(x) (Q(y) R(x) P3分(4)F(c) (Q(y)R(c)US (3)4分Q(y) R(c)T (2),(4) I 5(6) R(c)T (5) I 6F(c)R(c)T (2),(6) I 7(8)x(F(x) R(x) EG (7)8分 分 分 分3 .解：的哈斯图如下图所示。（2分）； a, b的极大兀是：a,b；极小兀是：a, b（4分）；最大兀不存在；最小兀不存在（6分）；上界有：a,b, a,b,c；下界为：巾；最小上界为：a,b；最大下界为：巾（8分）。4 .证明：已知 R是等价关系，对

10、S是等价关系的证明分 3步：（1）自反性丫 R是自反的，二对 Va A,有 a,a R ,根据S的定义，有S ,二S是自反的；（2分）（2）对称性如果 a,bwS,则三cA,使wR且c,bAWR,丁 R是对称的，二 b,c * 且 w R ,二再根据S的定义有=S,二S是对称的；（5分）（3）传递性如果 a,b S , b, c S ,则三d w A使 w R,且 d,b R。丁 R是传递的，二 a,b M R。则三ew A使 b,e R ,且 e,c R。 丫 R 是传递的，二 w R。二根据S的定义有亡S。. S是传递的。（8分）由（1）, （2）, （3）得S是等价关系。5 .解答： ,2,1 awn mN , f（） = f（）=12 +22 = 5 ,但 1,2k