2004—2005学年第1学期试卷及一套练习题.doc

20042005学年第1学期试卷一、 单项选择题 (本大题共10小题，每小题2分，共20分)1.下列不是命题的是 。A. 7能被3整除. B. 5是素数当且仅当太阳从西边升起.C. x加7小于0. D. 华东交通大学位于南昌北区. 2. 设p:王平努力学习，q:王平取得好成绩，命题“除非王平努力学习，否则他不能取得好成绩”的符号化形式为 。 A. pq B. pqC. qp D. qp3. 下面4个推理定律中，不正确的为 。A. A=(AB) (附加律) B. (AB)A=B (析取三段论)C. (AB)A=B (假言推理) D. (AB)B=A (拒取式)4. 设解释I如下，个体域D=1,2,F(1,1)=(2,2)=0,F(1,2)=F(2,1)=1，在解释I下，下列公式中真值为1的是 。A.x $yF(x,y)B. $xyF(x,y) C. xyF(x,y) D. $x$yF(x,y)5. 下列四个命题中哪一个为真？ 。 A. B. aC. D. 6. 设S=a,b,c,d，R=,，则R的性质是 。 A.自反、对称、传递的 B. 对称、反对称、传递的C.自反、对称、反对称的 D. 只有对称性7. 设A=a,b,c，则下列是集合A的划分的是 。A.b,c,c B.a,b,a,c C.a,b,c D.a,b,c8. 设集合关于普通数的乘法，不正确的有 。A. 结合律成立 B. 有幺元 C. 任意元素有逆元 D. 交换律成立9. 设A是非空集合，P(A)是A的幂集，是集合交运算，则代数系统P(A),的幺元是 。A. P(A) B. C. A D. E10. 下列四组数据中，不能成为任何4阶无向简单图的度数序列的为 。A. 2,2,2,2 B. 1,1,1,3 C. 1,1,2,3 D. 1,2,2,3二、填空题（本题共10小题，每小题2分，共20分）1. 命题公式pq的真值为假，当且仅当_。2. 公式p(qr)在联结词全功能集，中等值形式之一为_。3. 谓词公式xF(x)$y G(y)的前束范式为 。4. 设集合A = 1，4，B = 2，4，则 P (A) - P (B) = _ _。5. R是非空集合上的偏序关系，当且仅当R具有_ _。6. 设函数f(x)=x + 1,g(x)= 2x2, 则f o g =_。7. 设=(134)(256)，=(25)(1643)，则=_。8. 命题“设G为任意的n阶简单的哈密尔图，则u，vV(G)，均有d(u)+d(v)n”的真值为_。9. 无向连通图G是欧拉图，当且仅当G中每一个顶点的度数都为_。10. 设树T有m个顶点，n条边，则T中顶点与边的关系为_。三、证明下式（62=12分）1、 判断下面推理是否正确。如果你学习，那么你离散数学不会不及格。如果你不热衷于玩游戏，那么你将学习。但你离散数学不及格。因此你热衷于玩游戏。2、在一阶谓词逻辑中构造下面推理的证明。 前提：$xF(x), x(F(x)G(x)H(x) 结论：$xH(x)四、用等值演算法求公式(pq)(pq)(qp)的主合取范式与主析取范式。（10分）五、设R1和R2是集合X= 0 , 1 , 2 , 3 , 4 上的关系，R1=| y = 2x ，R2=| x= y + 1写出R1、R2 ，写出R2的关系矩阵，并求出R1R2。 （8分）六、设集合A=2,3,4,6,8,12,24，R为A上的整除关系，(1)画出偏序集（A，R）的哈斯图；(2)出集合A中的最大元、最小元、极大元、极小元；（3）写出A的子集B=2,3,6,12的上界、下界、最小上界、最大下界。（8分）七、 设Z为整数集合，在Z上定义二元运算*， x,yZ有。证明：是一个群。（10分）八、平面图G有两个连通分支，其顶点数为12，边数为34，问G有多少个面？（6分）九、对下图，（1） 求其邻接矩阵；（2）长度小于3的通路和回路的总数。(6分) V2 v1 v5 v3 v4练习题一、判断题：（10分，在括号内划“”或“”）（ ）1“如果太阳从西边出来，则2+2=4”，此命题值为假。（ ）2(1,3,3,3)可以成为无向简单图的度数序列。（ ）3有一个函数f：XY，若f具有反函数，则f一定是单射。 （ ）4（PQ）（PQ）是永真式。（ ）5在某集合上二元运算中，若某元素存在左右逆元，则该元素逆元唯一。 （ ）6命题公式的主析取范式为0，则其主合取范式为1。 （ ）7有向图的关联矩阵中所有元素之和为该图度之和 。（ ）8初级回路一定是简单回路。（ ）9若关系R具有自反性，则一定不具有反自反性。 （ ）10x(A(x) $yH(x,y)在具体的解释中其值是确定的。二、填空（共30分）1 设A=1，2，P(A)表示A的幂集，,则P(A) A =_。2 在一阶逻辑中符号化命题:“所有的人都是要死的”（只能用存在量词）： _。3 P(x) y R(x,y)的前束范式是：_。4. n阶有向完全图中所有顶点的度数之和为_ 5.已知从A到A/R的函数g：AA/R为自然映射，A=1,2,3 ， R=EA,则g(1)=_。6. 设函数f(x)=2x + 1,g(x)= x2-2,则f o g =_。7. Klein四元群的运算表如下，其有_个子群。 e a b ce e a b ca a e c bb b c e ac c b a e8.R，+为代数系统，给定bZ，令函数f：RR，且f(x)bx，当b满足 _时， f是R，+的自同构。9若|P(AB)|=256，|P(A)|=64，| B |=3，则|AB|= 。10下图为无向图，并且是平面图，画出它的一种平面嵌入。V1V2V6V5V3V4三、（6分）设A、B、C为任意集合，证明： (ABC)(AB) - (A(B-C)A) = B-A四、（8分）求（pq） r的主合取范式、主析取范式以及成假赋值。五、（8分）设Z为整数,在Z上定义二元运算，对任意的x,yZ，定义： xy=x+y+10证明： Z, 是群。六、（8分）在一阶逻辑自然推理系统中，构造下面推理的证明。个体域是人的集合。 “每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车，有的人不喜欢骑自行车。因而有的人不喜欢步行。”七、（10分）设集合A= 1,2,3,4上的二元关系R1与R2定义如下：R1=,，R2=,，1) 写出R1的关系矩阵，并判断R1具有哪些性质？2) 求出R1R23) 画出t(R2)的关系图。八、（10分）已知A和A上的偏序关系R，设A = a,b,c,d,e,f ，R = , ,IA 。1) 画出此偏序集的哈斯图。2) 找出最大元与最小元。3) A, 是否为分配格？是否为布尔代数？