2004—2005学年第1学期试卷一、判断题：（10分，在括号内划“√”或“×”）√√（）1．“如果太阳从西边出来，则2+2=4”，此命题值为假。

（）2．(1,3,3,3)可以成为无向简单图的度数序列。

（）3．有一个函数f：X→Y，若f具有反函数，则f一定是单射。

（）4．（P∧Q）→（P∨Q）是永真式。

（）5．在某集合上二元运算中，若某元素存在左右逆元，则该元素逆元唯一。

（）6．命题公式的主析取范式为0，则其主合取范式为1。

（）7．有向图的关联矩阵中所有元素之和为该图度之和。

（）8．初级回路一定是简单回路。

（）9．若关系R具有自反性，则一定不具有反自反性。

（）10．∀x(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：A→A/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 bc e ac c b a e8.〈R，+〉为代数系统，给定b∈Z，令函数f：R→R，且f(x)＝bx，当b满足 ______________时， f是〈R，+〉的自同构。

9．若|P(A∪B)|=256，|P(A)|=64，| B |=3，则|A⊕B|= 。

10．下图为无向图，并且是平面图，画出它的一种平面嵌入。

三、（6分）设A、B、C为任意集合，证明：((A∪B∪C)∩(A∪B)) - ((A∪(B-C))∩A) = B-A四、（8分）求（⌝p∧q）→ r的主合取范式、主析取范式以及成假赋值。

五、（8分）设Z为整数,在Z上定义二元运算，对任意的x,y∈Z，定义：x△y=x+y+10证明：〈 Z, △〉是群。

六、（8分）在一阶逻辑自然推理系统中，构造下面推理的证明。

个体域是人的集合。

“每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车，有的人不喜欢骑自行车。

因而有的人不喜欢步行。

”七、（10分）设集合A= {1,2,3,4}上的二元关系R1与R2定义如下：R1={<1,1>,<1,3>,<2,2>,<2,4>,<3,3>,<4,4>}，R2={<1,1>,<1,2>,<2,1>,<2,3>,<3,4>,<4,1>}，1)写出R1的关系矩阵，并判断R1具有哪些性质？2)求出R1ｏR23)画出t(R2)的关系图。

八、（10分）已知A和A上的偏序关系R⊆，设A = {a,b,c,d,e,f }，R⊆ = {<e,f>,<d,f>, <c,f>,<c,d>,<c,e>,<b,d>,<b,f>,<a,b>,<a,c>,<a,d>,<a,e>,<a,f>}ｕI A 。

1)画出此偏序集的哈斯图。

2)找出最大元与最小元。

3)〈A, ≤>是否为分配格？是否为布尔代数？说明理由。

九、（10分）若D是具有结点v1,v2,v3,v4的有向图，它的邻接矩阵表示如下：1 2 1 00 0 2 00 0 0 10 0 1 01)画出这个图；2)D是单向连通还是强连通？说明理由。

3)该图是否存在欧拉通路？说明理由。

4)求该图中长度小于等于3的通路与回路总数。

2004～2005第一学期考试卷一、单项选择题 (本大题共10小题，每小题2分，共20分)1.下列不是命题的是[ ]。

A.7能被3整除.B.5是素数当且仅当太阳从西边升起.C.x加7小于0.D.华东交通大学位于南昌北区.2. 设p:王平努力学习，q:王平取得好成绩，命题“除非王平努力学习，否则他不能取得好成绩”的符号化形式为 [ ]。

A. p→qB. ⌝p→qC. ⌝q→pD. q→p3. 下面4个推理定律中，不正确的为 [ ]。

A.A=>(A∨B) (附加律) B。

(A∨B)∧⌝A=>B (析取三段论)C. (A→B)∧A=>B (假言推理)D. (A→B)∧⌝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. ∃x∀yF(x,y)C. ∀x∀yF(x,y)D. ⌝∃x∃yF(x,y)5. 下列四个命题中哪一个为真？ [ ]。

A. ∅∈∅B. ∅∈{a}C. ∅∈{{∅}}D. ∅⊆∅6. 设S={a,b,c,d}，R={<a,a>,<b,b>,<d,d>}，则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,c}}8.设集合})bQ∈+=关于普通数的乘法，不正确的有[ ]。

aa2b{,)2(QA. 结合律成立B. 有幺元C. 任意元素有逆元D. 交换律成立9.设A是非空集合，P(A)是A的幂集，∩是集合交运算，则代数系统〈P(A),∩〉的幺元是[ ]。

A. P(A)B. φC. AD. E10.下列四组数据中，不能成为任何4阶无向简单图的度数序列的为[ ]。

A. 2,2,2,2B. 1,1,1,3C. 1,1,2,3D. 1,2,2,3二、填空题（本题共10小题，每小题2分，共20分）1.命题公式p→q的真值为假，当且仅当_________________。

2. 公式p→(q→r)在联结词全功能集{⌝，∧，∨}中等值形式之一为____________________。

3. 谓词公式⌝∀xF(x)→∃yG(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，v∈V(G)，均有d(u)+d(v)≥n”的真值为___________。

9. 无向连通图G是欧拉图，当且仅当G中每一个顶点的度数都为____________。

10. 设树T有m个顶点，n条边，则T中顶点与边的关系为_______________。

三、证明下式（6×2=12分）1、判断下面推理是否正确。

如果你学习，那么你离散数学不会不及格。

如果你不热衷于玩游戏，那么你将学习。

但你离散数学不及格。

因此你热衷于玩游戏。

2、在一阶谓词逻辑中构造下面推理的证明。

前提：∃xF(x), ∀x(F(x)∨G(x)→H(x))结论：∃xH(x)四、用等值演算法求公式((p∨q)∧(p→q))↔(q→p)的主合取范式与主析取范式。

（10分）五、设R1和R2是集合X={ 0 , 1 , 2 , 3 , 4 }上的关系，R 1={<x , y>| y = 2x }，R2={<x , y>| x= y + 1}写出R1、R2，写出R2的关系矩阵，并求出R1︒R2。

（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,y∈Z有2*-+=yxyx。

证明：<Z，*>是一个群。

（10分）八、平面图G有两个连通分支，其顶点数为12，边数为34，问G有多少个面？（6分）九、对下图，（1）求其邻接矩阵；（2）长度小于3的通路和回路的总数。

(6分)2004～2005第二学期补考试卷二、单项选择题 (本大题共10小题，每小题2分，共20分)1.下列不是命题的是[ ]。

A.学生要努力学习. B。

5是素数当且仅当太阳从西边升起.C．x－7>0 . D。

7能被3整除.2. 与命题p∨(q∧p)等值的公式是 [ ]。

A. pB. qC. p∨qD. p∧q3. 使命题公式p→(p∧q)为假的赋值是p，q分别为 [ ]。

A. (0,0)B. (0,1)C. (1,0)D. (1,1)4. 在命题逻辑中，任何命题公式的主析取范式都 [ ]。

A. 存在且唯一B. 存在但不唯一C. 不一定存在D. 不存在5. 对于任意集合A、B， A包含于B当且仅当A-B=Φ是 [ ]。

A.假命题B.真命题C.是一阶公式但不是命题D.均不属于A、B、C6. 设S={1,2,3,4}，R={<1,1>,<2,2>,<3,3>}，则R的性质是 [ ]A.自反、对称、传递的B.自反、对称、反对称的C.对称、反对称、传递的D.只有对称性7. 设A={a,b,c}，则下列是集合A的划分的是[ ]。

A.{{b,c},{c}}B.{{a,c},{b,c}}C.{{a,c},b}D.{{a,c },{b }}8. 下述*运算为实数集上的运算，其中可交换且可结合的运算是 [ ]A. a*b=a+2bB. a*b=a+b-abC. a*b=aD. a*b=|a+b|9. 无向连通图G是欧拉图，当且仅当G中每一个顶点的度数都为[ ]。