名…… 姓… … …… … …线学号… … … … … …… 级…班订… … … … … …年级…… 装 … … … … 业……专… … 系泉州师院2009-2010学年度第一学期 2008级计算机《离散数学》期中试卷
题 序 一 二 三 四 五 总分 成 绩
签 名 一、单项选择题:（20%，每空2分）
得 分 1．设A={a,{a}}，下列命题错误的是（ B ）。
评卷人 A．{a}P(A) B．{a}P(A)
C．{{a}}P(A) D．{{a}}P(A)
2、假定全集E＝{1,2,3,4,5,6,7,8,9,10},A={3,4,5}，B＝{2,3,4,7,8,9}，则A∪B的位串是（ D ）。
A．01 B．0011100000 C．00 D．00 3、下列文氏图阴影部分所表示的集合是( A )。
A. (A-(B∪C))∪((B∪C)-A) B. (A-(B∩C))∪((B∩C)-A) C. (A-(B∩C))∪((B∪C)-A) D. (A-(B∪C))∪((B∩C)-A)
4．设p：你主修计算机科学，q：你是新生， r：你可以从校园网访问因特网。只有你主修计算机科学或不是新生，你才可以从校园网访问因特网。可符号化为( C )。 A．r→p∨q
B．r→p∧q C．r→p∨q
D．r→p∨q
5．下列是两个命题变元p，q的极小项是（ A ）
A．┐p∧q B．┐p∨q C．p∧┐p∧q
D．┐p∨p∨q
6、下列等值式不正确的是（ C ）
A．┐(x)A(x)┐A
B．(x)(B→A(x))B→(x)A(x)
C．(x)(A(x)∧B(x))(x)A(x)∧(x)B(x) D．(x)(y)(A(x)→B(y))( x)A(x)→(y)B(y) 7、若s={1,2,3,4}，S上关系R的关系图为：
则R具有（ B ）性质。
A、自反性 B、自反性、对称性 C、反自反性、反对称性 D、自反性、对称性、传递性
8．设A={a,b,c,d}，A上的等价关系R={
A．{{a},{b,c},{d}}
B．{{a,b},{c},{d}}
C．{{a},{b},{c},{d}} D．{{a,b},{c,d}}
9、设A={1，2，3}，则A上的二元关系有（ C ）个。
A. 2
3
B. 3
2
C. D.
10．下列函数是双射的为（ A ），其中：I—整数集，E—偶数集， N—自然数集，R—实数集。
A. f : IE , f (x) = 2x B. f : NNN, f (n) =
二．填空题（20%，每题2分）
1．集合的表示法有 列举法、描述法 。
2、 设A??1???0,?ii??,i?1,2,3,...,则?Ai? {0 } 。i?1得 分 3．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，评卷人 但是路不滑”可符号化为 p→q 。 4．复合命题(p→q)∨(p→
q)是___ 永真____式（永真式或永假式或可满足
式）。
5．令谓词P(x,y)表示”x爱y”,个体域是全世界所有人的集合，用P(x,y)、量词
和逻辑词符号化“所有人都爱某些人”： xyP(x,y) 。 6．
xF(x)
xG(x)的前束范式是
yx F(y)
G(x) 。 7．设
A={a,b,c,d},下列左图所示关系矩阵所表示的关系
R={
?1100??M??1001?R??0110??
?0010??
8、设某偏序集的哈斯图如下列右图，该偏序集的拓扑排序为 1,5,3,2,7,9,6,4,8 。
?1,当x为奇数9、设f：N→N，且f(x)???x，则f({1,3,4,6}= {1,2,3} ??2,当x为偶数。 10、给定函数f：S→S,S=[0,1],f(x)=x/2+1/4,f是___单射______(满射或单射或双射或都不是)。
三、计算题（20%，每题5分）
得 分 1、问A∪(BC)=(A∪B)(A∪C)吗为什么
评卷人 解：上式不成立。
设A={1,2,3},B={2,3,4},C={3,4,5} 有：
A∪(BC)= {1,2,3}∪{2,5}={1,2,3,5}
(A∪B)(A∪C)= {1,2,3,4}{1,2,3,4,5}={5}
2、求公式(p∧q)∨r的标准析取范式，再根据标准析取范式求标准合取范式。
解：(p∧q)∨r
(pqr)(pqr) (pqr)
(pqr)(pqr)(pqr)
m1
m3m5 m6m7
M0∧M2∧M4
3、设A={a,b,c,d}，其上关系R={
（2）R的对称闭包及传递闭包。 解：
(1) RS={
(2) R的对称闭包S(R)= {
4、设，偏序集的Hass图为：
求 ① A中最小元与最大元。 ② {x2,x3,x4}的极小元和极大元。
③ {x2,x3}的上界与下界。 ④ {x3,x4}的上确界与下确界。
解：
①A中无最小元，最大元为x1。 ② {x2,x3,x4}的极小元为x4，极大元为x2,x3。
③ {x2,x3}的上界为x1，下界为x4。 ④ {x3,x4}的上确界为x3，下确界为x4。
得 分 四、证明题（20%，每题5分）
评卷人
1、设A、B是任意集合，证明： (A-B)∪(B-A)= (A∪B)-(A∩B)
证：
=(A∪B)-(A∩B) =(A∪B)∩~ (A∩B) =(A∪B)∩(~A∪~B)
=A∩(~A∪~B))∪B∩(~A∪~B) =A∩~B∪B∩~A =(A-B)∪(B-A)
2、证明下列推理：
前提：(pq) r, rs, sp
结论：q
(1) (p?q )?r 前提引入 (2)r?s 前提引入 (3) (p?q )?s (1)(2)假言三段论 (4) ?s?p 前提引入(5)p (2)化简
(6)?s (2)化简(7)?(p?q) (3)(6)拒取式(8)?p??q (7)置换(9)?q (5)(8)析取三段论
3、设F，G是任意的关系，证明：(FG)-1= G
-1
F
-1
证： 任取?x,y? ?x,y??(F?G)??y,x??F?G??t(?y,t??F??t,x??G)
??t(?t,y??F?1??x,t??G?1)??t(?x,t??G?1??t,y??F?1)??x,y??G?1?F?1
4. 任何人如果他喜欢步行，他就不喜欢乘汽车，对于每个人或者喜欢乘汽车或者喜欢骑自行车，有的人不爱骑自行车，因而有的人不爱步行。逻辑推证此结论的有效性。 (设个体域是人类)
Q(x)：x喜欢步行； S(x)：x喜欢乘汽车 ； R(x)：x喜欢骑自行车。 前提：x(Q(x) S(x)), x(S(x) R(x)), xR(x) 结论：xQ(x)
证：(1)?x?R(x) 前提引入(2)?R(a) (1) ES规则(3)?x(S(x)?R(x) ) 前提引入(4) S(a)?R(a) (3)US规则(5)S(a) (2)(4)析取三段论
(6)?x(Q(x)??S(x)) 前提引入(7)Q(a)??S(a) (6)US规则(8) ?Q(a) (5)(7)拒取式(9)?x?Q(x) (8)EG规则
五、判断题（20%，每题2分）
(在括号中写“对”或“错”)
1、 gcd(21,7)的值为7，
的值为-2。( 对 )
2、 设A,B,C均为E的子集，则A
B
A∪(B-A)=A。( 错 )
3、间接证明法可形式化地表示为：A→B
B→
A。( 对 )
4、对每个最大项而言，只有与下标编码相同的赋值是成假赋值，其余都是成真赋值。（ 对 ） 5、设个体域是整数集Z，则xy
z((x+y=z)的真值为1。（ 错 ）
6、逻辑公式
(
xF(x)
yG(y)) yG(y)不是永真式。（ 对 ）7、因为若R是A上的关系，且m,nN，则Rm
Rn=Rm+n,所以R
R-1=R0=IA.（ 错 ）
8、一个关系若是自反的，则必定不是反自反的，若是对称的，则必定不是反对称的。( 错 ) 9、设
A={a,b,c,d,e},R={
，
则
A/R={{a,b},{c,d}}。 ( 对 )
10、设A={1,2,3,4}，A→A的函数f={<1,2>,<2,3>,<3,1>,<4,1>},则f的反函数不存在。( 对 )
得 分 评卷人
08计算机《离散数学》期中试卷答案
