2024年3月29日发(作者：奥迪a7轿跑)
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=E
A
,则
g(1)=____________________________。
6. 设函数f(x)=2x + 1,g(x)= x-2,则f o g =____________________。
7. Klein四元群的运算表如下，其有__________________个子群。
e a b c
e e a b c
a a e c b
b b c e a
c c b a e
8.〈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．下图为无向图，并且是平面图，画出它的一种平面嵌入。
2
√ √
1
V1
V2
V6
V5
三、（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ｏR2
3) 画出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 0
0 0 2 0
0 0 0 1
0 0 1 0
1) 画出这个图；
2) D是单向连通还是强连通？说明理由。
3) 该图是否存在欧拉通路？说明理由。
4) 求该图中长度小于等于3的通路与回路总数。
V3 V4
2004～2005第一学期考试卷
一、 单项选择题 (本大题共10小题，每小题2分，共20分)
1.下列不是命题的是[ ]。
2
A. 7能被3整除.
B. 5是素数当且仅当太阳从西边升起.
C. x加7小于0.
D. 华东交通大学位于南昌北区.
2. 设p:王平努力学习，q:王平取得好成绩，命题“除非王平努力学习，否则他不能取得
好成绩”的符号化形式为 [ ]。
A. p→q B. ?p→q C. ?q→p D. q→p
3. 下面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.自反、对称、传递的 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. 设集合
Q(2)?{a?b2a,b?Q})
关于普通数的乘法，不正确的有[ ]。
A. 结合律成立 B. 有幺元 C. 任意元素有逆元 D. 交换律成立
9. 设A是非空集合，P(A)是A的幂集，∩是集合交运算，则代数系统〈P(A),∩〉的幺元
是[ ]。
A. P(A) B. φ? C. A D. E
10. 下列四组数据中，不能成为任何4阶无向简单图的度数序列的为[ ]。
A. 2,2,2,2 B. 1,1,1,3
3
C. 1,1,2,3 D. 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)= 2x
2
, 则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分）
五、设R
1
和R
2
是集合X={ 0 , 1 , 2 , 3 , 4 }上的关系，
R
1
={
2
={
写出R
1
、R
2
，写出R
2
的关系矩阵，并求出R
1
?R
2
。 （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有
（10分）
x*y?x?y?2
。证明：
八、平面图G有两个连通分支，其顶点数为12，边数为34，问G有多少个面？（6分）
九、对下图，
（1） 求其邻接矩阵；（2）长度小于3的通路和回路的总数。(6分)
4
V2 v1
v5
v3 v4
2004～2005
第二学期补考试卷
二、 单项选择题 (本大题共10小题，每小题2分，共20分)
1.下列不是命题的是[ ]。
A. 学生要努力学习. B。5是素数当且仅当太阳从西边升起.
C．
x
－7>0 . D。7能被3整除.
2. 与命题p∨(q∧p)等值的公式是 [ ]。
A. p B. q C. p∨q D. p∧q
3. 使命题公式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、C
6. 设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+2b B. a*b=a+b-ab C. a*b=a D. a*b=|a+b|
9. 无向连通图G是欧拉图，当且仅当G中每一个顶点的度数都为[ ]。
A. 不同 B. 相同? C. 奇数 D. 偶数
5
更多推荐
运算,命题,关系,推理,通路,公式,集合,小题
发布评论