泉州师院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 ．1000000001B ．0011100000C ．0111001110D ．0111101110 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 ∨qB ．r →p ∧qC ．r →p ∨⌝qD ．r →p ∨⌝q5．下列是两个命题变元p ，q 的极小项是（ A ）A ．┐p ∧qB ．┐p ∨qC ．p ∧┐p ∧qD ．┐p ∨p ∨q6、下列等值式不正确的是（ C ）A ．┐(∀x)A ⇔(∃x)┐AB ．(∀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,b>,<b,a>,<c,d>,<d,c>}∪I A ，则对应于R 的A 的划分是（ D ）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. 23B. 32C. 332⨯D. 223⨯10．下列函数是双射的为（ A ），其中：I —整数集，E —偶数集， N —自然数集，R —实数集。

A. f : I →E , f (x) = 2xB. f : N →N ⨯N, f (n) = <n , n+1>C. f : R →I , f (x) = [x]D. f :I →N, f (x) = | x |二．填空题（20%，每题2分）1．集合的表示法有 列举法、描述法 。

则设、 } {0 A 1==⎥⎦⎤⎢⎣⎡=∞= i i i A ii,...,,,,,3211023．令p ：今天下雪了，q ：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为 p →⌝q 。

4．复合命题(p →⌝q)∨(⌝p →⌝q)是___ 永真____式（永真式或永假式或可满足式）。

5．令谓词P(x,y)表示”x 爱y ”,个体域是全世界所有人的集合，用P(x,y)、量词和逻辑词符号化“所有人都爱某些人”： ∀x ∃yP(x,y) 。

6．∃xF(x)∧∀xG(x)的前束范式是 ∃y ∀x F(y)∧ G(x) 。

7．设A={a,b,c,d},下列左图所示关系矩阵所表示的关系R={ <a,a>,<a,b>,<b,a>,<b,d>,<c,b>,<c,c>,<d,c> }。

⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=0100011010010011RM8、设某偏序集的哈斯图如下列右图，该偏序集的拓扑排序为 1,5,3,2,7,9,6,4,8 。

9、设f ：N →N ，且⎪⎩⎪⎨⎧=为偶数当为奇数当x 2x x ,,)(1x f ，则f({1,3,4,6}= {1,2,3} 。

10、给定函数f ：S →S,S=[0,1],f(x)=x/2+1/4,f 是___单射______(满射或单射或双射或都不是)。

三、计算题（20%，每题5分）1、问A ∪(B ⊕C)=(A ∪B)⊕(A ∪C)吗？为什么？解：上式不成立。

设A={1,2,3},B={2,3,4},C={3,4,5} 有：A ∪(B ⊕C)= {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⇔ (p ∧q ∧⌝r)∨(p ∧q ∧r) ∨(⌝p ∧⌝q ∧r)∨ (⌝p ∧q ∧r)∨(p ∧⌝q ∧r)∨(p ∧q ∧r) ⇔ m 1∨m 3∨m 5∨ m 6∨m 7 ⇔M 0∧M 2∧M 43、设A={a,b,c,d}，其上关系R={<b,b>，<b,c>，<c,a>}，S={<b,a><c,d>,<d,a>}，求（1）R S（2）R 的对称闭包及传递闭包。

解：(1) R S={<b,a>,<b,d>}(2) R 的对称闭包S(R)= {<b,b>，<b,c>，<c,a>，<c,b>，<a,c>} (3) R 的传递闭包t(R)= {<b,b>，<b,c>，<c,a>，<b,a>}4、设},,,,{54321x x x x x A =，偏序集><R A ,的Hass 图为：求 ① A 中最小元与最大元。

② {x 2,x 3,x 4}的极小元和极大元。

③ {x 2,x 3}的上界与下界。

④ {x 3,x 4}的上确界与下确界。

解：①A 中无最小元，最大元为x1。

② {x 2,x 3,x 4}的极小元为x4，极大元为x2,x3。

③ {x 2,x 3}的上界为x1，下界为x4。

④ {x 3,x 4}的上确界为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、证明下列推理：前提：(p ∧q) →r, r →s, ⌝s ∧p 结论：⌝q析取三段论置换拒取式化简化简前提引入假言三段论前提引入前提引入(5)(8) q (9)(7) q p (8)(3)(6) q)(p (7)(2) s (6)(2) (5)p p s (4) (1)(2) s ) (p (3)s (2)r r ) (p )(⌝⌝∨⌝∧⌝⌝∧⌝→∧→→∧q q 13、设F ，G 是任意的关系，证明：(F ︒G)-1= G -1︒F -1111111------>∈⇔<>∈<∧>∈<∃⇔>∈<∧>∈<∃⇔>∈<∧>∈<∃⇔>∈⇔<>∈<><F G y x F y t G t x t G t x F y t t G x t F t y t ,),,(),,(),,(GF x y,G)(F y x, y x, 任取证：4. 任何人如果他喜欢步行，他就不喜欢乘汽车，对于每个人或者喜欢乘汽车或者喜欢骑自行车，有的人不爱骑自行车，因而有的人不爱步行。

逻辑推证此结论的有效性。

(设个体域是人类)Q(x)：x 喜欢步行； S(x)：x 喜欢乘汽车 ； R(x)：x 喜欢骑自行车。

前提：∀x(Q(x) →⌝S(x)), ∀x(S(x) ∨ R(x)), ∃x ⌝R(x) 结论：∃x ⌝Q(x)规则拒取式规则前提引入析取三段论规则前提引入规则前提引入证：(8)EG Q(x)x (9)(5)(7) Q(a) (8)(6)US S(a)(7)Q(a) S(x))x(Q(x)(6)(2)(4) (5)S(a)(3)US R(a)S(a) (4) ) R(x)x(S(x)(3)ES (1) R(a)(2) R(x)x (1)⌝∃⌝⌝→⌝→∀∨∨∀⌝⌝∃五、判断题（20%，每题2分）(在括号中写“对”或“错”)1、 gcd(21,7)的值为7，⎡-2.3⎤的值为-2。

( 对 )2、 设A,B,C 均为E 的子集，则A ⊆B ⇔A ∪(B-A)=A 。

( 错 )3、间接证明法可形式化地表示为：A →B ⇔⌝B →⌝A 。

( 对 )4、对每个最大项而言，只有与下标编码相同的赋值是成假赋值，其余都是成真赋值。

（ 对 ）5、设个体域是整数集Z ，则∃x ∀y ∀z((x+y=z)的真值为1。

（ 错 ）6、逻辑公式⌝ (∀xF(x) →∃yG(y)) ∧ ∃yG(y)不是永真式。

（ 对 ）7、因为若R 是A 上的关系，且m,n ∈N ，则R m ︒R n =R m+n ,所以R ︒R -1=R 0=I A. （ 错 ）8、一个关系若是自反的，则必定不是反自反的，若是对称的，则必定不是反对称的。

( 错 )9、设A={a,b,c,d,e},R={<a,b>,<b,a>,<c,d>,<d,c>}∪I A ，则A/R={{a,b},{c,d}}。

( 对 )10、设A={1,2,3,4}，A →A 的函数f={<1,2>,<2,3>,<3,1>,<4,1>},则f 的反函数不存在。

( 对 )。