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

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

2、)表示x比y快。命题“并不是所 有的火车比所有的汽车快”的符号表示中哪些是正确的？()L一x-y(F(x) G(y)r 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、若AB=AC，则B=C；B、若AB AB，则A = B；C 若AB二A C，则B二C；D、若AB且CD，则A CB D。5.设A，A - ，A3=()，A4 =，以下命题为假的是()A、A2- A4；B、AA3；C、A4A2； D、A4- A3。6设R是集合A二a,b

3、,c,d上的二元关系，R= : a,d:d,a:a,c：c,a：b, d j：d,b 。下列哪些命题为真？()I.R R是对称的II.R R是自反的III.R R不是传递的A、仅 I；B 、仅 II ； C、I 和 II ； D 、全真。7.R是二元关系且R = R4，则一定是传递的是()AR4；B、R3； C、R2； D、R。&设R1和R2是非空集合 A 上的等价关系，确定下列各式，哪些是A 上的等价关系()A A A R Y可逆的充要条件是：()A、A =B； B 、|A|=|B|； C、f为双射； D、f为满射。10.下列集合中，哪个集合的基数与其他集合的基数不同()得分离散数学

4、试卷 共3页第2页A、Nn(N为自然数集，nN)； B、NN(N为自然数集)；CR R(R为实数集)；D 、x坐标轴上所有闭区间集合；、填空题(每小题 2 分，共 32 分)1全集U二1,234,5,A =1,5,B二1,2,3,4,C =2,5，则可求出:A n B =_；(A)(C)=C二_2设A =3,| P(B) =16,| P(AU B) =64，则:B=-,A 仃 B =_,A _ B =_,A B =_。3设A二1,2,3,4,R是A上的二元关系，且R二：1,2：2,4：3,3 ，则r(R) =；s(R)=_；t(R)=4.设 A=1,2,3,4,5，贝 U A 上共有多少个二元

5、关系 _？其中有多少个等价关系_ ?5设函数f：A A,B A为A的子集。则:f(f(B)_B,fJ(f(B)_B；当f为_ 函数时f (f(B)二B；当f为_ 函数时f(f(B)二B。离散数学试卷 共3页第3页三、综合题(第 2 小题 16 分，其它各小题 8 分，共 48 分)1 求命题公式(P Q) -R) P的主析取范式与主合取范式(要求用等值演算的方法求解)。(8 分)2用推理规则证明：(每小题 8 分，共 16 分)1P (Q R),S P,Q永真蕴含S R。2前提：-x(F(x) (Q(y)R(x),xF (x)；结论：x(F(x) R(x)。3设集合A二a,b,c,r(A)是集

6、合A的幕集，试给出:：:?(A)的哈斯图，并指出子集a,b的 极大元、极小元、最大元、最小元、上界、下界、最小上界、最大下届(如果存在的话)。(8 分)4.设R是集合A上的关系，令S = 三A,使 c a, c 丘 R 且 c c,bR，证明：如果R是等价关系，则S也是等价关系。(8 分)5已知f : N N N，f x, y )=x2y2。请问：(8 分)1f是单射吗？2f是满射吗？3计算f4(0)。4计算f ( : 0,0 , : 1,2 )。得分离散数学试卷 共3页第3页安徽大学 2006-2007 学年第 1 学期离散数学期末考试试卷答案（A 卷）（时间 120 分钟）、选择题（每小题

7、 2 分，共 20 分）1. C;2.D;3.C;4.B;5.A;6.C;7.B;8.D;9.C;10.A二、填空题(每空 2 分，共 32 分)1.5; ,5；1342.4, 1, 2, 53.,254.2,525.5，满射，二，单射(P Q R) (P Q R)(P_Q R)(P.：-Q_R)=(P Q R) (一PQ R)(P_QR) (P Q R)(P Q R) (P Q R)(主析取范式)6 分A：二(一卩Q R)(一卩Q R)二Aw(Px/(P eQ eR)二(P Q R) (P Q R)(主合取范式)8 分2.证明：(1)S PP1分SP（附加前提）2分PT(1),(2)I3分P

8、 (Q R)P4分Q RT ,(4)I5分QP6分RT ,(6)I7分Au(P Q) -R) P(P Q) -R) P(P-Q) R) P(P R) (一Q R) P2 分(P R) (一Q Q)(QR） （P一卩）(P (Q -Q) (R -R)(P Q R)(一卩Q R)(P；：-Q R)(_P _Q R)三、综合题（第 2 小题 16 分，其它各小题 8 分，共 48 分）4 分；,离散数学试卷 共3页第3页(8)S RCP ,(7)8分证明:(1)xF(x)P1分F(c)ES (1) 2分-x(F(x) (Q(y)R(x)P3分F(c) (Q(y)R(c)US (3)4分(5)Q(y)

9、 R(c)T,(4) I 5分(6)R(c)T16分(7)F(c) R(c)T,(6) I 7分(8)x(F(x) R(x)EG (7)8分3解:r（A）,二的哈斯图如下图所示。*（2 分）； a, b的极大元是：a, b；极小元是：a, b（ 4 分）；最大元不存在；最小元不存在（6 分）；上界有：a,b, a,b,c；下界为： ；最小上界为：a,b；最大下界为：- （8 分）。4证明：已知R是等价关系，对S是等价关系的证明分3 步：（1）自反性R是自反的，-对一a A,有：:：a,aR，根据S的定义，有：:a,a / S，-S是自反的；（2分）（2）对称性如果：:：a,b S，则A，使：:：a,c R且：:：c,b R， R是对称的，二vb,c R且v c,a二乏R，再根据S的定义有：:b, a S，-S是对称的；（5 分）（3）传递性如果：:：a, b ES，: b, c三S，则Td A使：:：a,d R，且：:：d,b R。二R是传递的，.：:：a,b R。则-e A使：:：b,e R，且：:：e, c R。 R是传递的，.：:：b, c