计算机离散数学期中试卷答案
系 专业 年级 班级 学号 姓名
……………………装……………………订……………………线……………………
泉州师院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. 23
B. 32
C. 3
32
?
D. 2
23?
10．下列函数是双射的为（ A ），其中：I —整数集，E —偶数集， N —自然数集，R —实数集。
A. f : I →E , f (x) = 2x
B. f : N →N ?N, f (n) =
C. f : R →I , f (x) = [x]
D. f :I →N, f (x) = | x |
二．填空题（20%，每题2分）
1．集合的表示法有 列举法、描述法 。
。则设、 } {0 A 1
==??????=∞
=I i i i A i i ,...,,,,,3211023．令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={
?
?
??
?
????
???=0100
011010010011R M
8、设某偏序集的哈斯图如下列右图，该偏序集的拓扑排序为 1,5,3,2,7,9,6,4,8 。
9、设f ：N →N ，且???
??=为偶数当为奇数当x 2
x 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 ∪(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) m 1?m 3?m 5? m 6?m 7 M 0∧M 2∧M 4
3、设A={a,b,c,d}，其上关系R={
求（1）R οS
（2）R 的对称闭包及传递闭包。 解：
(1) R οS={
(2) R 的对称闭包S(R)= {
得 分 评卷人
4、设
}
,
,
,
,
{
5
4
3
2
1
x
x
x
x
x
A=，偏序集>
A,的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 析取三段论 置换 拒取式 化简 化简 前提引入 假言三段论 前提引入 前提引入 (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 1 3、设F，G是任意的关系，证明：(FG)-1= G-1?F-1 1 1 1 1 1 1 - - - - - - >∈ ?< >∈ < ∧ >∈ < ? ? >∈ < ∧ >∈ < ? ? >∈ < ∧ >∈ < ? ? >∈ ?< >∈ < > < 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 ο ο ο , ) , , ( ) , , ( ) , , ( G F 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)), xR(x) 结论：xQ(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。( 对 ) 2、 设A,B,C 均为E 的子集，则ABA ∪(B-A)=A 。( 错 ) 3、间接证明法可形式化地表示为：A →BB →A 。( 对 ) 4、对每个最大项而言，只有与下标编码相同的赋值是成假赋值，其余都是成真赋值。（ 对 ） 5、设个体域是整数集Z ，则xyz((x+y=z)的真值为1。（ 错 ） 6、逻辑公式 (xF(x) yG(y)) yG(y)不是永真式。（ 对 ） 7、因为若R 是A 上的关系，且m,nN ，则R m R n =R m+n ,所以RR -1=R 0=I A. （ 错 ） 8、一个关系若是自反的，则必定不是反自反的，若是对称的，则必定不是反对称的。( 错 ) 9、设A={a,b,c,d,e},R={ 10、设A={1,2,3,4}，A →A 的函数f={<1,2>,<2,3>,<3,1>,<4,1>},则f 的反函数不存在。( 对 ) 离散数学试题(A卷及答案） 一、证明题（10分） 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R)?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R)?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R?T∧R(置换)?R 2)?x(A(x)→B(x))??xA(x)→?xB(x) 证明：?x(A(x)→B(x))??x(?A(x)∨B(x))??x?A(x)∨?xB(x)???xA(x)∨?xB(x)??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分） 证明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题（10分） 1）C∨D, (C∨D)→?E, ?E→(A ∧?B), (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E (2) ?E→(A∧?B) (3) (C∨D)→(A∧?B) (4) (A∧?B)→(R∨S) (5) (C∨D)→(R∨S) (6) C∨D (7) R∨S 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明（1）?xP(x) (2)P(a) (3)?x(P(x)→Q(y)∧R(x)) (4)P(a)→Q(y)∧R(a) (5)Q(y)∧R(a) (6)Q(y) (7)R(a) (8)P(a) (9)P(a)∧R(a) (10)?x(P(x)∧R(x)) (11)Q(y)∧?x(P(x)∧R(x)) 四、设m是一个取定的正整数，证明：在任取m＋1个整数中，至少有两个整数，它们的差是m的整数倍 证明设 1 a，2a，…，1+m a为任取的m＋1个整数，用m去除它们所得余数 只能是0，1，…，m－1，由抽屉原理可知， 1 a，2a，…，1+m a这m＋1个整 数中至少存在两个数 s a和t a，它们被m除所得余数相同，因此s a和t a的差是m的整数倍。 五、已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C) （15分）证明∵x∈ A-（B∪C）? x∈ A∧x?（B∪C）? x∈ A∧（x?B∧x?C）?（x∈ A∧x?B）∧（x∈ A∧x?C）? x∈（A-B）∧x∈（A-C）? x∈（A-B）∩（A-C）∴A-（B∪C）=（A-B）∩（A-C） 六、已知R、S是N上的关系，其定义如下：R={ 离散数学考试试题（A 卷及答案） 一、（10分）求(P ↓Q )→(P ∧?(Q ∨?R ))的主析取范式 解：(P ↓Q )→(P ∧?(Q ∨?R ))??(?( P ∨Q ))∨(P ∧?Q ∧R )) ?(P ∨Q )∨(P ∧?Q ∧R )) ?(P ∨Q ∨P )∧(P ∨Q ∨?Q )∧(P ∨Q ∨R ) ?(P ∨Q )∧(P ∨Q ∨R ) ?(P ∨Q ∨(R ∧?R ))∧(P ∨Q ∨R ) ?(P ∨Q ∨R )∧(P ∨Q ∨?R )∧(P ∨Q ∨R ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解 设设P ：王教授是苏州人；Q ：王教授是上海人；R ：王教授是杭州人。则根据题意应有： 甲：?P ∧Q 乙：?Q ∧P 丙：?Q ∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P ，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?' R 。则sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 系 专业 年级 班级 学号 姓名 ……………………装……………………订……………………线…………………… 泉州师院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={ 离散数学及其应用重要名词中英对应以及重要概念解释与举例 1 The Foundations: Logic and Proofs（逻辑与证明） 1.1 Propositional Logic（命题逻辑） Propositions（命题）——declarative sentence that is either true or false, but not both.判断性语句，正确性唯一。 Truth Table（真值表） Conjunction（合取，“与”，and），Disjunction（析取，or，“相容或”），Exclusive（异或），Negation（非，not），Biconditional（双条件，双向，if and only if） Translating English Sentences 1.2 Propositional Equivalences（命题等价） Tautology（永真式、重言式），Contradiction（永假式、矛盾式），Contingency（偶然式） Logical Equivalences（逻辑等价）——Compound propositions that have the same truth values in all possible cases are called logical equivalent.（真值表相同的式子，p<->q是重言式） Logical Equivalences——Page24 Disjunctive normal form(DNF，析取范式) Conjunctive normal form(CNF，合取范式) 见Page27～29 1.3 Predicates and Quantifiers（谓词和量词） Predicates——谓词，说明关系、特征的修饰词 Quantifiers——量词 ? Universal Quantifier(全称量词) " 离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ). 习题1.1 2. 指出下列命题是原子命题还是复合命题。 （3）大雁北回，春天来了。 （4）不是东风压倒西风，就是西风压倒东风。 （5）张三和李四在吵架。 解：（3）和（4）是复合命题，（5）是原子命题。 习题1.2 1. 指出下列命题的真值： （1）若224+>，则太阳从西方升起。 解：该命题真值为T （因为命题的前件为假）。 （3）胎生动物当且仅当是哺乳动物。 解：该命题真值为F （如鸭嘴兽虽是哺乳动物，但不是胎生动物）。 2. 令P ：天气好。Q ：我去公园。请将下列命题符号化。 （2）只要天气好，我就去公园。 （3）只有天气好，我才去公园。 （6）天气好，我去公园。 解：（2）P Q →。 （3）Q P →。 （6）P Q ?。 习题1.3 2. 将下列命题符号化（句中括号内提示的是相应的原子命题的符号表示）： （1）我去新华书店（P ），仅当我有时间（Q ）。 （3）只要努力学习（P ），成绩就会好的（Q ）。 （6）我今天进城（P ），除非下雨（Q ）。 （10）人不犯我（P ），我不犯人（Q ）；人若犯我，我必犯人。 解：（1）P Q →。 （3）P Q →。 （6）Q P ?→。 （10）()()P Q P Q ?→?∧→。 习题1.4 1. 写出下列公式的真值表： （2）()P Q R ∨→。 解：该公式的真值表如下表： 2. 证明下列等价公式： （2）()()()P Q P Q P Q ∨∧?∧???。 证明： ()(()()) ()()) ()() ()() P Q P Q P Q P Q P Q P Q P Q P Q P Q ????∧∨?∧???∧∧??∧???∧∧∨?∨∧?∧ （4）()()()P Q P R P Q R →∧→?→∧。 证明： ()()()() () () P Q P R P Q P R P Q R P Q R →∧→??∨∧?∨??∨∧?→∧ 3. 甲、乙、丙、丁4人参加考试后，有人问他们谁的成绩最好，甲说，不是我。乙说：是丁。丙说：是乙。丁说：不是我。已知4个人的回答只有一个人符合实际，问成绩最好的是谁？ 解：设A ：甲成绩最好。B ：乙成绩最好。C ：丙成绩最好。D ：丁成绩最好。 四个人所说的命题分别用P Q R S 、、、表示，则 P A ??；Q A B C D ??∧?∧?∧；R A B C D ??∧∧?∧?；S D ??。 则只有一人符合实际的命题K 符号化为 ()()()() K P Q R S P Q R S P Q R S P Q R S ?∧?∧?∧?∨?∧∧?∧?∨?∧?∧∧?∨?∧?∧?∧ 《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???. 2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？ 一．判断题（共10小题，每题1分，共10分） 在各题末尾的括号内画 表示正确，画 表示错误： 1．设p、q为任意命题公式，则(p∧q)∨p ? p ( ) 2．?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3．初级回路一定是简单回路。( ) 4．自然映射是双射。( ) 5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。( ) 6．群的运算是可交换的。( ) 7．自然数集关于数的加法和乘法 列为。 19．n阶无向简单连通图G的生成树有条边。 20．7阶圈的点色数是。 三、运算题（共5小题，每小题8分，共40分） 21．求?xF(x)→?yG(x,y)的前束范式。 22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。 23．设A={a,b,c,d,e,f}，R=I A?{ 泉州师院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 ．1000000001 B ．0011100000 C ．0111001110 D ．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 ∨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={ 离散数学试题(Ｂ卷答案１） 一、证明题(10分） 1）(P∧（Ｑ∧Ｒ）)∨(Q∧R）∨（Ｐ∧R)R 证明: 左端(P∧Q∧Ｒ）∨((Q∨P）∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((Ｐ∨Ｑ）∧R）∨((Ｑ∨P)∧Ｒ) (（P∨Q）∨（Ｑ∨P))∧Ｒ （(P∨Ｑ)∨(Ｐ∨Q))∧R T∧Ｒ(置换)Ｒ 2) x (A(x)B(ｘ）)xA(x)xＢ(ｘ) 证明：x(A(ｘ)B(x))x(Ａ(ｘ)∨B(x)） x A(ｘ)∨xB（ｘ) xA(x)∨xB(x） xＡ(x)xB(x) 二、求命题公式(P∨（Q∧R)）(P∧Q∧R)的主析取范式和主合取范式(10分）。 证明：(P∨（Q∧R))(P∧Q∧R)（P∨(Q∧R)）∨(P∧Q∧R)) (P∧(Q∨Ｒ))∨（P∧Q∧Ｒ） （Ｐ∧Q)∨（P∧R)）∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧Ｒ)∨(P∧Q∧Ｒ))∨(P∧Ｑ∧R）)∨(Ｐ∧Q∧R） m0∨ｍ1∨m２∨ｍ７ Ｍ３∨M４∨Ｍ５∨M6 三、推理证明题（１0分) 1）Ｃ∨D，（C∨D)E, E(A∧B)，(A∧Ｂ)(R∨S)R∨Ｓ证明：(１） (C∨D) E ?P (2) E（A∧Ｂ) ??P （3) (Ｃ∨D）（A∧B) Ｔ（1）(2），I (4) （A∧B)(R∨S）??P (5) (Ｃ∨D)(Ｒ∨S) ? T(3)(4)，I (6） C∨Ｄ P (7) R∨S T(5)，I 2) x(P(ｘ)Ｑ(y)∧R(ｘ)），xＰ(ｘ)Q（y)∧x(Ｐ(x)∧R(x)) 证明(1)ｘP(x) Ｐ （2)Ｐ(ａ） T(1），ＥS (3)ｘ（P(x)Q（y)∧R(x）) Ｐ (４)P(a)Q（y)∧R(a） T(3)，ＵS (５)Q（ｙ)∧R(a） T(2)（4），I （6）Q(y) Ｔ(５)，I （7)R(ａ) T(5),I (8)P(a)∧Ｒ（ａ) T(2)(7),I （9)x(Ｐ(x）∧R(x)) Ｔ(8),ＥG (10)Q(ｙ)∧x(P(x)∧R(ｘ)) Ｔ(６）(9)，I 四、某班有２5名学生,其中14人会打篮球,１2人会打排球，6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。 解：A，B,C分别表示会打排球、网球和篮球的学生集合。则｜A|=1２，|Ｂ|＝6,｜Ｃ|=14，｜A∩C|=6，｜B∩C｜=5，|Ａ∩Ｂ∩C｜=２。 先求|A∩B|。 ∵6＝|（Ａ∪C)∩B|=|（A∩B）∪（Ｂ∩C)|=|（A∩B）|＋|（B∩C）｜-|A∩B∩C|=|(Ａ∩B)|+5-２，∴|(A∩B）|=３。 于是|A∪Ｂ∪C｜=12+6+14-6-5－３＋２=20。不会打这三种球的人数25-20=5。五、已知Ａ、B、Ｃ是三个集合,证明A-(B∪Ｃ)=(A-B)∩(Ａ-C）(10分)。 证明：∵x A-（B∪C） x A∧x（B∪C） xＡ∧(xＢ∧x C） （x A∧x B）∧(x A∧ｘC） x（A-B）∧x(Ａ-C） ｘ（Ａ-Ｂ）∩(A-C） ∴Ａ-（B∪Ｃ)=（Ａ－B）∩(A－Ｃ） 六、已知R、S是Ｎ上的关系,其定义如下：R={ 《离散数学》期末考试试题 一、 填空题（每空2分，合计20分） 1. 设个体域为{2,3,6}D =-, ():3F x x ≤，():0G x x >。则在此解释下公式 ()(()())x F x G x ?∧的真值为______。 2. 设:p 我是大学生，:q 我喜欢数学。命题“我是喜欢数学的大学生”为可符合化 为 。 3. 设{1,2,3,4}A =，{2,4,6}B =，则A B -=________，A B ⊕=________。 4. 合式公式()Q P P ?→∧是永______式。 5. 给定集合{1,2,3,4,5}A =，在集合A 上定义两种关系： {1,3,3,4,2,2}R =<><><>, {4,2,3,1,2,3}S =<><><>， 则_______________S R =ο，_______________R S =ο。 6. 设e 是群G 上的幺元，若a G ∈且2a e =,则1a -=____ , 2a -=__________。 7． 公式))(()(S Q P Q P ?∧?∨∧∨?的对偶公式为 。 8. 设{2,3,6,12}A =, p 是A 上的整除关系，则偏序集,A <>p 的最大元是________，极小元是_ _。 9. 一棵有6个叶结点的完全二叉树，有_____个内点；而若一棵树有2个结点度数为2，一 个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_____个叶结点。 10. 设图,G V E =<>, 1234{v ,v ,v ,v }V =，若G 的邻接矩阵????????????=0001001111011010A ，则1()deg v -=________, 4()deg v +=____________。 二、选择题（每题2分，合计20分） 1．下列各式中哪个不成立（ ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨? ； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。 离散数学及应用课后习题答案 【篇一：离散数学及其应用图论部分课后习题答案】 p165:习题九 1、给定下面4个图（前两个为无向图，后两个为有向图）的集合 表示，画出它们的图形表 示。 （1）g1??v1,e1?，v1?{v1,v2,v3,v4,v5}， e1?{(v1,v2),(v2,v3),(v3,v4),(v3,v3),(v4,v5)} （2）g2??v2,e2?， v2?v1，e1?{(v1,v2),(v2,v3),(v3,v4),(v4,v5),(v5,v1)} （3） d1??v3,e3?,v3?v1,e3?{?v1,v2?,?v2,v3?,?v3,v2?,?v4,v5?,?v5,v 1?} （4） d2??v4,e4?,v4?v1,e3?{?v1,v2?,?v2,v5?,?v5,v2?,?v3,v4?,?v4,v 3?} 解答：（1） （2） 10、是否存在具有下列顶点度数的5阶图？若有，则画出一个这样 的图。 （1）5，5，3，2，2；（2）3，3，3，3，2；（3）1，2，3，4，5；（4）4，4，4，4，4 解答：（1）（3）不存在，因为有奇数个 奇度顶点 。 14、设g是n(n?2)阶无向简单图，g是它的补图，已 知?(g)?k1,?(g)?k2，求?(g)， ?(g)。 解答：?(g)?n?1?k2；?(g)?n?1?k1。 15、图9.19中各对图是否同构？若同构，则给出它们顶点之间的双 射函数。 解答： （c）不是同构，从点度既可以看出，一个点度序列为4，3，3，3，3而另外一个为4，4，3，3，1 （d）同构，同构函数为 ?1?2??f(x)??3 ?4???5 解答： （1）三条边一共提供6度；所以点度序列可能是 离散数学试题(B卷答案1） 一、证明题（10分） 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R) ?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R) ?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R ?T∧R(置换)?R 2) ?x (A(x)→B(x))??xA(x)→?xB(x) 证明：?x(A(x)→B(x))??x(?A(x)∨B(x)) ??x?A(x)∨?xB(x) ???xA(x)∨?xB(x) ??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分）。 证明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题（10分） 1）C∨D， (C∨D)→?E，?E→(A∧?B)， (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E P (2) ?E→(A∧?B) P (3) (C∨D)→(A∧?B) T(1)(2)，I (4) (A∧?B)→(R∨S) P (5) (C∨D)→(R∨S) T(3)(4)， I (6) C∨D P (7) R∨S T(5)，I 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明(1)?xP(x) P 《离散数学》复习题 一、单项选择题（每小题2分，共20分） 1、下列命题中是命题的是（ ） A 、 7>+y x B 、雪是黑色的 C 、严禁吸烟 D 、我正在说谎 2下列命题联结词集合中,哪个不是极小全功能集( )。 A 、{,}刭 B 、{,}刳 C 、{}- D 、{,}佼 3、下列公式中哪个不是简单析取式（ ）。 A 、p B 、p q ∨ C 、()p q ?∨ D 、p q ?∨? 4、设个体域{,}A c d =，公式()()x P x x S x ?∧?在A 中消去量词后应为（ ） A ()()P x S x ∧ B (()())(()( P c P d S c S d ∧∧∨ C ()()P c S d ∧ D ()() () (P c P d S c S d ∧ ∧∨ 5、下列是命题公式p ∧(q ∨┓r)的成真指派的是( ) A.110，111，100 B.110，101，011 C.所有指派 D.无 6、下列命题中（ ）是正确的。 A. 若图G 有n 个顶点，则G 的各顶点的度和为2n; B. 无向树中任意两点之间均相互可达； C. 若有向图G 是弱连通的，则它必定也是单向连通； D. 若无向带权图G 是连通的，则其最小生成树存在且唯一。 7、正整数集合Z +的以下四个划分中，划分块最多的是（ ） A ．1π={{x }︱x ∈Z + } B ．2π= {Z + } C. 3π={12,S S },1S 为素数集，21S Z S + =- D ．3π={12,S S ,3S },i S 为Z +中元素除以3的余数 8、给定下列各图： ⑴G 1= 北京工业大学经管学院期末试卷 《离散数学》（A） 学号姓名：成绩 一、单项选择题（每题2分，共18分） 1．令P：今天下雪了，Q：路滑，则命题“虽然今天下雪了，但是路不．滑”可符号化为（D）A．P→Q B．P∨Q C．P∧Q D．P∧Q p→q，蕴涵式，表示假设、条件、“如果，就”。 “→”与此题无关 2. 关于命题变元P和Q的极大项M1表示( C )。书P15-P20，此题换作p、q更容易理解 A.┐P∧Q B.┐P∨Q p∨┐q ---- 01---- 1 ----- M1 C.P∨┐Q D.P∧┐Q 3.设R（x）：x是实数；S（x,y）：x小于y。用谓词表达下述命题：不存在最小的实数。其中错误的表达式是：（D） 4.在论域D={a,b}中与公式（x?）A（x）等价的不含存在量词的公式是（B） A.)b( )a( A∨ A A )a( A∧ B. )b( C. )b( )b( A→ A A )a( A→ D. )a( 5．下列命题公式为重言式的是（C） A．Q→（P∧Q）B．P→（P∧Q） C．（P∧Q）→P D．（P∨Q）→Q 牢记→真假条件，作为选择题可直接代入0、1，使选项出现1→0，排除。熟练的可直接看出C不存在1→0的情况 6. 设A=｛1，2，3｝，B=｛a,b｝，下列二元关系R为A到B的函数的是( A ) A. R=｛<1,a>,<2,a>,<3,a>｝ B. R=｛<1,a>,<2,b>｝ C. R=｛<1,a>,<1,b>,<2,a>,<3,a>｝ D. R=｛<1,b>,<2,a>,<3,b>,<1,a>｝ 7.偏序关系具有性质（D）背 A.自反、对称、传递 B.自反、反对称 C.反自反、对称、传递 D.自反、反对称、传递 8.设R 为实数集合，映射:,R R σ→2 ()21,x x x σ=-+-则σ 是( D ). (A) 单射而非满射 (B) 满射而非单射 (C) 双射 (D) 既不是单射也不是满射. 书P96.设函数f ：A→B （1）若ranf=B ，则f 是满射的【即值域为B 的全集，在本题中为R ，该二次函数有最高点，不满足】 （2）若对于任何的x 1,x 2∈A , x 1≠x 2,都有f(x 1)≠f(x 2)，则称f 是单射的【即x,y 真正一一对应，甚至不存在一个y 对应多个x 。显然，本题为二次函数，不满足】 （3）若f 既是满射的，又是单射的，则称f 是双射的【本题中两个都不满足，既不是单射也不是满射】 二、填空题（每空2分，共22分） １.设Q 为有理数集，笛卡尔集S=Q×Q ，*是S 上的二元运算，? 广东技术师范学院 模拟试题 科 目：离散数学 考试形式：闭卷 考试时间: 120 分钟 系别、班级： 姓名： 学号： 一．填空题（每小题2分，共10分） 1. 谓词公式)()(x xQ x xP ?→?的前束范式是__ ?x ?y?P(x)∨Q(y) __________。 2. 设全集{}{}{},5,2,3,2,1,5,4,3,2,1===B A E 则A ∩B =__{2}__，=A _{4,5}____， =B A __ {1,3,4,5} _____ 3. 设{}{}b a B c b a A ,,,,==，则=-)()(B A ρρ__ {{c},{a,c},{b,c},{a,b,c}} __________， =-)()(A B ρρ_____Φ_______。 4. 在代数系统（N ，+）中，其单位元是0，仅有 _1___ 有逆元。 5．如果连通平面图G 有n 个顶点，e 条边，则G 有___e+2-n ____个面。 二．选择题（每小题2分，共10分） 1. 与命题公式)(R Q P →→等价的公式是（ ） （A ）R Q P →∨)( （B ）R Q P →∧)( （C ）)(R Q P ∧→ （D ）)(R Q P ∨→ 2. 设集合{}c b a A ,,=,A 上的二元关系{}><><=b b a a R ,,,不具备关系( )性质 （A ） (A)传递性 (B)反对称性 (C)对称性 (D)自反性 3. 在图>=离散数学期末考试试题(有几套带答案)
离散数学期末试题
计算机《离散数学》期中试卷答案
离散数学及其应用 重要名词中英对应以及重要概念解释与举例
离散数学期末试题及答案完整版
(完整版)离散数学及其应用(课后习题)
离散数学期末试卷A卷及答案
离散数学期末试卷及答案
08计算机《离散数学》期中试卷答案
离散数学期末考试试题及答案
《离散数学》期末考试试题
离散数学及应用课后习题答案
离散数学期末考试试题及答案
离散数学期末考试题
离散数学期末试卷
离散数学期末考试试题(配答案)
相关文档
- 离散数学期末考试及答案
- 离散数学期末测验试题(有几套带答案1)
- 离散数学期末考试试题(有几套带答案)
- 离散数学期末考试试题及答案
- 离散数学期末考试题答案
- 离散数学期末考试试题(有几套带答案)
- 离散数学期末考试试题及答案
- 离散数学期末试卷A卷及答案
- 离散数学试题及答案
- 离散数学期末考试题及答案
- 离散数学期末复习试题及答案(一)
- 离散数学期末试题及答案完整版
- 离散数学期末测试卷I及答案
- 离散数学期末考试试题及答案
- 离散数学期末考试试题及答案
- 《离散数学》期末复习题答案_80011521535014977
- 山东大学离散数学期末试题答案
- 大学《离散数学》期末考试试卷及答案-(1)
- 06级离散数学期末试题B答案
- (精选)离散数学期末考试试题(配答案)