离散数学复习题
离散数学复习题
一、填空题
1. A，B是两个集合，A={a，b，c，d}，B={b，c，e}，则B- A = ，
ρ（A）的元素个数为。
2. 设A和B是任意两个集合，则A?B= 。A?B
的子集R称为。
3. 设R是集合A上的二元关系，如果关系R同时具有性、和
传递性，则称R是等价关系。
4. 设R是集合A上的二元关系，如果关系R同时具有性、和
传递性，则称R是偏序关系。
5. 将几个命题联结起来，形成一个复合命题的联结词主要有否定、、
、条件和双条件。
6. 设G是由5个顶点组成的无向完全图，则从G中删去条边可以得到它
的一棵生成树。
7. 设* 是集合A上的二元运算，a和b是A中的元素；如果满足，
则称a是零元；如果满足，则称b是单位元。
8. 代数系统中的结合律是，分配律
是。
9. 代数系统中的幂等律是，吸收律
是。
10. 表达式（?x）A（x）和（?y）B（y）中的个体域是{a，b，c}，将其中的
量词消除，写成与之等价的命题公式分别
为，
和。
二、选择题
1. 下列语句中，（）是命题。
A．下午有会吗？B．这朵花多好看呀！C．2是虚数。D．请把门关上。
2. 一个命题公式在逻辑等价意义下，下面哪个写法是唯一的（）。
A．析取范式B．合取范式C．主析取范式D．以上答案都不对。
3. 下面给出的谓词逻辑等价式中，（）是错的。
A．(?x)（A（x）∨ B（x））? (?x) A（x）∨ (?x) B（x）
B．A→(?x) B（x）?(?x)（A→B（x））
C．(?x)（A（x）∨ B（x））? (?x) A（x）∨ (?x) B（x）
D．?(?x) A（x）? (?x)（?A（x））
4. 设R为实数集，映射σ：R→R，σ（x）= -x2+2x-1，则σ是（）。
A．单射而非满射B．满射而非单射C．双射D．既不是单射，也
不是满射
5. 下列表达式正确的是（）。
A．φ?{φ}=φB．φ?{φ}=φC．{a}∈{a，b，c} D．φ∈{a，b，c}
三、问答题
1. 群中单位元是否唯一？
2. 群中有无幂等元？
3. 群中有无零元？
4. 群中有无消去律？
5. n阶群若有k阶子群，则k与n有何关系？
6. 12阶群是否一定有1阶，12阶子群？
7. 12阶群是否一定有2阶，3阶，4阶，6阶子群？
8. 12阶循环群是否一定有2阶，3阶，4阶，6阶子群？
四、画图题
1. 在同构意义下，给出所有的5元素格。
2. 给出一个6元素的有补格。
3. 给出一个7元素的分配格。
4. 给出一个8元素的Boole代数。
5.给出一个5顶点的无向简单图，使其为欧拉图，但非哈密顿图。
6.给出一个4顶点的无向简单图，使其为哈密顿图，但非欧拉图。
7.给出一对5顶点的无向互补图。
8. 给出一对3顶点的有向互补图。
9.给出一个4顶点的无向自补图。
10. 给出一个8顶点的自对偶平面图。
11. 给出单射而非满射的例子。
12. 给出满射而非单射的例子。
13. 给出既是单射又是满射的例子。
14. 给出既非单射又非满射的映射的例子。
15. 给出3阶群的运算表。
五、叙述题
1. 试述什么样的集合是关系。
2. 试述什么样的关系是映射。
3. 试述什么样的关系是自反关系。
4. 试述什么样的关系是对称关系。
5. 试述什么样的关系是反对称关系。
6. 试述什么样的关系是传递关系。
7. 试述什么样的关系是等价关系。
8. 试述什么样的关系是偏序关系。
9. 试述代数系统中什么样的元素是零元。
10. 试述代数系统中什么样的元素是单位元。
11. 试述代数系统中什么样的元素是幂等元。
12. 试述代数系统中什么样的元素是有负元的元。
13. 试述代数系统中什么样的元素是有逆元的元。
14. 试述什么样的代数系统是半群。
15. 试述什么样的代数系统是独异点。
16. 试述什么样的代数系统是群。
17. 试述什么样的代数系统是环。
18. 试述什么样的元素是环中的零因子。
19. 试述什么样的代数系统是域。
20. 试述什么样的偏序集是格。
21. 试述什么样的格是有补格。
22. 试述什么样的格是分配格。
23. 试述什么样的格是Boole代数。
24. 试述判定分配格的一个著名定理。
25. 试述有限Boole代数之元素的原子表示定理。
26. 试述有限Boole代数的原子表示定理。
27. 试述什么样的图是欧拉图。
28. 试述什么样的图是哈密顿图。
29. 试述什么样的图是竞赛图。
30. 试述谓词逻辑中的两条量词转换律。
31. 试述谓词逻辑中的两条量词分配律。
32. 试述谓词逻辑中的两条量词单向分配律。
六、计算题
1. R={（a，a），（b，b），（b，c），（d，d）}是集合A={a，b，c，d}上一个关系，
试写出它的自反闭包。
2．画出下面偏序集（A，≤）的哈斯图，并指出集合A的最小元、最大元、极小元和极大元。其中A={a，b，c，d，e}，≤={（a，b），（a，d），（a，e），
（b，e），（c，e），（d，e）}?I A。
3. 模7代数系统（N7，⊕7）按模7加法⊕7构成一个循环群。试写出（N7，⊕7）
的所有生成元。
4. 模8代数系统（N8，⊕8，*8）按模8加法⊕8和模8乘法*8是否构成一个
有零因子环？如果是，试写出所有的零因子对；此外，也写出所有互为负元
的元素对，以及所有互为逆元的元素对。
5. 利用真值表求命题公式(P→﹁Q)→R的主析取范式。
七、证明题
1. 试证群中有唯一的单位元。
2. 试证群中有唯一的幂等元。
3. 试证在群G中，如果ab=ac, 则一定有b=c。
4. 设G是群，a是G中一个元素。令H = { x∈G∣ax = xa }. 试证H是G的一
个子群。
5. 试证在一个简单连通平面图中，如果它有n个顶点，m条边，且每一个区域
由k条边围成，则一定有m=k(n-2)/(k-2)。
6 试证在完全2元树中，边数m=2(t-1)，其中t为树叶数。
7 试证命题公式P∧﹁Q与﹁(P→Q)是逻辑等价的。
8. 试证命题公式((P∨Q)∧(P→R)∧(Q→R))→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) ? M∧1M ? m∨3m∨4m∨5m∨6m∨7m 2 二、（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 上的二元关系，则由定理4.19知，tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?'R 。由定理4.15和由定理4.16得sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。 综上可知，tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 四、（15分）集合A ＝{a ，b ，c ，d ，e }上的二元关系R 为R ＝{，，，，，，，，
离散数学模拟题一套及答案
离散数学考试（试题及答案） 一、（10分）某项工作需要派A、B、C和D4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？ (1)若A去，则C和D中要去1个人； (2)B和C不能都去； (3)若C去，则D留下。 解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此 (ACD)∧(B∧C)∧(CD) (A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D) (A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D)) (A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧ D∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F (A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D) (A∧C)∨(B∧C∧ D)∨(C∧D) T 故有三种派法：B∧D，A∧C，A∧D。 二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。 解：论域：所有人的集合。()：是专家；()：是工人；()：是青年人；则推理化形式为： (()∧())，()(()∧())
下面给出证明： (1)() P (2)(c) T(1)，ES (3)(()∧()) P (4)( c)∧( c) T(3)，US (5)( c) T(4)，I (6)( c)∧(c) T(2)(5)，I (7)(()∧()) T(6) ，EG 三、（10分）设A、B和C是三个集合，则AB(BA)。 证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA) x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB) (x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A)) (BA)。 四、（15分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。 解 r(R)＝R∪I A＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)＝R∪R－1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>， <5，2>，<1，2>，<4，2>，<4，3>} R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2 t(R)＝R i＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，5>}。
离散数学复习题及答案
离散数学复习题及答案文件排版存档编号：[UYTR-OUPT28-KBNTL98-UYNN208]
1. 写出命题公式 ﹁（P →（P ∨ Q ））的真值表。 答案： 2.证明 答案： 3. 证明以下蕴涵关系成立： 答案： 4. 写出下列式子的主析取范式： 答案： 5. 构造下列推理的论证：p ∨q, p →r, s →t, s →r, t q 答案： ①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明：p →((r ∧s)→q), p, s q 7. 请将下列命题符号化： 所有鱼都生活在水中。 ) ()(R P Q P ∨∧∧?
答案： 令F( x )：x是鱼 W( x )：x生活在水中 8. 请将下列命题符号化： 存在着不是有理数的实数。 答案： 令 Q ( x )：x 是有理数 R ( x )：x 是实数 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令M(x)：x 是人 C(x)：x 是聪明的 则上述命题符号化为 10. 请将下列命题符号化： 对于所有的正实数x,y，都有x+y≥x。 答案： 令P(x):x是正实数 S(x,y): x+y≥x 11. 请将下列命题符号化： 每个人都要参加一些课外活动。 答案： 令P(x):x是人 Q(y): y是课外活动 S(x,y):x参加y 12. 请将下列命题符号化： 某些人对某些药物过敏。 答案：
令P(x):x是人 Q(y): y是药 S(x,y):x对y过敏13. 求) ( )) ( ) ( (y yR y Q x P y? → → ?的对偶式: 答案： 14. 求下列谓词公式的前束范式： 答案： 15. 证明： 答案： 16. 用反证法证明： x(P(x)∧Q(x)) , xP(x) xQ(x) 答案： 17. 证明： 前提： x(C(x)W(x)∧R(x)), x(C(x)∧Q(x)). 结论： x(Q(x)∧R(x)). 答案： (1) x(C(x)∧Q(x)) 前提引入 (2) C(a)∧Q(a) (1)ES (3) C(a) (2)化简规则 (4) x(C(x)W(x)∧R(x)) 前提引入 (5) C(a)W(a)∧R(a) (4)US (6) W(a)∧R(a) (3)(5)假言推理 (7) R(a) (6)化简规则 (8) Q(a) (2)化简规则 ) , , ( )) , ( ) , ( (u y x uQ z y P z x zP y x? → ∧ ? ? ?
离散数学试题与答案
试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统
二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。
离散数学期末试题及答案完整版
离散数学期末试题及答 案 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 离散数学模拟试题Ⅰ 一、单项选择题(本大题共15小题,每题1分,共15分)在每小题列出的四个备选项中只有一个就是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分 1.设 }16{2<=x x x A 是整数且,下面哪个命题为假( A )。 A 、A ?}4,2,1,0{; B 、A ?---}1,2,3{; C 、A ?Φ; D 、A x x x ?<}4{是整数且。 2.设}}{,{,ΦΦ=Φ=B A ,则B －A 就是( C )。 A 、}}{{Φ; B 、}{Φ; C 、}}{,{ΦΦ; D 、Φ。 3.右图描述的偏序集中,子集},,{f e b 的上界为 ( B )。 A 、b,c; B 、a,b; C 、b; D 、a,b,c 。 4.设f 与g 都就是X 上的双射函数,则1)(-g f ο为( C )。 A 、11--g f ο; B 、1)(-f g ο; C 、11--f g ο; D 、1-f g ο。 5.下面集合( B )关于减法运算就是封闭的。 A 、N ; B 、}2{I x x ∈; C 、}12{I x x ∈+; D 、}{是质数x x 。 6.具有如下定义的代数系统>*<,G ,( D )不构成群。 A 、G={1,10},*就是模11乘 ; B 、G={1,3,4,5,9},*就是模11乘 ; C 、G=Q(有理数集),*就是普通加法; D 、G=Q(有理数集),*就是普通乘法。 7.设 },32{I n m G n m ∈?=,*为普通乘法。则代数系统>*<,G 的幺元为( B )。 f
2 A 、不存在 ; B 、0032?=e ; C 、32?=e ; D 、1132--?=e 。 8.下面集合( C )关于整除关系构成格。 A 、{2,3,6,12,24,36} ; B 、{1,2,3,4,6,8,12} ; C 、{1,2,3,5,6,15,30} ; D 、{3,6,9,12}。 9.设},,,,,{f e d c b a V =, },,,,,,,,,,,{><><><><><><=e f e d d a a c c b b a E ,则有向图 >= 离散数学复习资料 一、填空 1. 命题“对于任意给定的正实数，都存在比它大的实数”令F(x)：x 为实数，y x y x L >:),(则命题的逻辑谓词公式为 。 2. 设p ：王大力是100米冠军，q ：王大力是500米冠军，在命题逻辑中，命题“王大力不 但是100米冠军，而且是500米冠军”的符号化形式为 。命题“存在一个人不但是100米冠军，而且是500米冠军”的符号化形式为____。 3. 选择合适的论域和谓词表达集合A=“直角坐标系中，单位元（不包括单位圆周）的点集” 则A= 。 4. 设 P （x ）：x 是素数， E(x)：x 是偶数，O(x)：x 是奇数 N (x,y)：x 可以整数y 。则谓词 (()(()(,)))x P x y O y N y x ?→?∧ 的自然语言是 对于任意一个素数都存在一个奇数使 该素数都能被整除 。 5. 设个体域是{a,b}，谓词公式()()()()x P x x P x ??∨?写成不含量词的形式是 。 6. 谓词(((,)(,))(,,))x y z P x z P y z uQ x y u ???∧→?的前束范式为 。 7. 命题公式)))(((R Q Q P P A →?∧→?∨?的主合取范式为 ，其编码表示为 。 8. 设E 为全集， ，称为A 的绝对补，记作～A ，且～（～A ）= ，～E = ， ～Φ= 。 9. 设={256},{234},{134}A B C ==，，，，，，，则A-B= ，A ⊕B = ，A ×C = 。 10. 设},,{c b a A =考虑下列子集}},{},,{{1c b b a S =，}},{},,{},{{2c a b a a S =， }},{},{{3c b a S =，}},,{{4c b a S =，}}{},{},{{5c b a S =，}},{},{{6c a a S = 则A 的覆盖有 ，A 的划分有 。 11. 设}2,121{Z x x x x M ∈≤≤=整除，被，}3,121{Z x x x x N ∈≤≤=整除，被，则 =?N M ，=-N M 。 12. 设A={<1,2>,<2 , 4 >,<3 , 3 >} , B={<1,3>,<2,4>,<4,2>},则B A ?= ，B A ο= 。 13. A={1，2，3，4，5，6}，A 上二元关系}|,{是素数y x y x T ÷><=，则用列举法 T= ； T 的关系图为 ，T 具有 性质。 《离散数学》期末考试题(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 是欧拉图. 二、单选题(每小题3分，共15分) 1.设R 是集合A 上的偏序关系，1-R 是R 的逆关系，则1 -?R R 是A 上的 (A)偏序关系 (B)等价关系 (C)相容关系 (D)以上结论都不成立 2.由2个命题变元p 和q 组成的不等值的命题公式的个数有 (A)2 (B)4 (C)8 (D)16 3.设p 是素数且n 是正整数，则任意有限域的元素个数为 (A)n p + (B)pn (C)n p (D)p n 4.设R 是实数集合，≤是其上的小于等于关系，则(R, ≤)是 (A)有界格 (B)分配格 (C)有补格 (D)布尔格 5.3阶完全无向图3K 的不同构的生成子图有 (A)2 (B)3 (C)4 (D)5 三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”. 1.若一个元素a 既存在左逆元l a ，又存在右逆元r a ，则r l a a =. ( ) 2.命题联结词→不满足结合律. ( ) 3.在Z 8 = {0，1，2，3，4，5，6，7}中，2关于“?8”的逆元为 4. ( ) 4.整环不一定是域. ( ) 北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。 2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。 3.本试卷满分100分，答题时间为90分钟。 4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。 一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。 [A] 3 [B] 8 [C]9 [D]27 2、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则（ ）。 [A] 3,8 [B]{}3 [C]{}8 [D]{}3,8 3、若X 是Y 的子集，则一定有（ ）。 [A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X 4、下列关系中是等价关系的是（ ）。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A 到集合B 的映射，下列表述中错误的是（ ）。 [A]对A 的每个元素都要有象 [B] 对A 的每个元素都只有一个象 [C]对B 的每个元素都有原象 [D] 对B 的元素可以有不止一个原象 6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为（ ）。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q 7、设A={a,b,c},则A 到A 的双射共有（ ）。 [A]3个 [B]6个 [C]8个 [D]9个 一、选择题： 1.下列句子是命题的是( )。 A. 你喜欢我吗? B. 这里的景色真美啊! C. 2x = 9。 D. 明年国庆节是晴天。 2.设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为( )。 ∧) A. ?P∧?Q B. ?(P Q C. ?(P?Q) D. ?(?P∨?Q) 3.下列语句不是 ．．命题的是( )。 A.黄金是非金属。 B.要是他不上场，我们就不会输。 C.他跑100米只用了10秒钟，你说他是不是运动健将呢? D.他跑100米只用了10秒钟，他是一个真正的运动健将。 4.若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为( )。 A.P∨Q B.P∧?Q C.P→?Q D.P∨?Q 5.下列句子不是 ．．命题的是( )。 A. 做人真难啊! B. 后天是阴天。 C. 2是偶数。 D. 地球是方的。 6.在命题演算中，语句为真为假的一种性质称为( )。 A. 真值 B. 陈述句 C. 命题 D. 谓词 7.命题公式?(P∧Q)→R的成真指派是( )。 A. 000，001，110 B. 001，011，101，110，111 C. 全体指派 D. 无 8.下列命题中，不正确的是( )。 ∈?,{{?}}} A.{?}{ ∈?,{?}} B.{?}{ C.{?}?{?,{?}} D. ??{?,{?}} 9.命题公式P∧(Q∨? R)的成真指派是( )。 A.110，111，100 B.110，101，011 C.所有指派 D.无 ∨?( )。 10.设P,Q,R是命题公式,则P→R，Q→R，P Q A. P B. Q C. R D. ?R 11.下列是两个命题变元p，q的小项是( ) ∨C．?p q ∨∨ ∧D．?p p q A．p∧?p q ∧B．?p q 12.关于命题变元P和Q的大项M01表示( )。 ∨ C.P∨?Q D.P∧?Q ∧ B.?P Q A.?P Q 13.设P：明天天晴；q：我去爬山；那么“除非明天天晴，否则我不去爬山。”可符号化为( ) ?p→?q C. ?p??q D. ?p→q A. p→?q B. 14.下列命题公式是永真式的是( ) (p→q)∨q D. (p∨p)∧(p→?p) ?(p→q)∧q C. A. (p∧?p)?q B. 一．判断题（共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?{ 离散数学试题(Ｂ卷答案１） 一、证明题(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. 已知集合A ={φ，1，2}，则A 得幂集合p （A ）=_____ _。 2. 设集合E ={a , b , c , d , e }, A = {a , b , c }, B = {a , d , e }, 则A ∪B =___ ___， A ∩ B =____ __，A －B =___ ___，～A ∩～B =____ ____。 3. 设A ，B 是两个集合，其中A = {1, 2, 3}, B = {1, 2}，则A －B =____ ___， ρ（A ）－ρ（B ）=_____ _ _。 4. 已知命题公式，则G 的析取范式为 。 5. 设P ：2＋2＝4，Q ：3是奇数；将命题“2＋2＝4，当且仅当3是奇数。”符号化 ，其真值为 。 二、单项选择题（选择一个正确答案的代号填入括号中，每小题4分，共16分。） 1. 设A 、B 是两个集合，A ＝{1,3,4}，B ＝{1,2}，则A －B 为（ ）. A. {1} B. {1, 3} C. {3,4} D. {1,2} 2. 下列式子中正确的有（ ）。 A. φ＝0 B. φ∈{φ} C. φ∈{a,b} D. φ∈φ 3. 设集合X ＝{x , y }，则ρ（X ）＝（ ）。 A. {{x },{y }} B. {φ,{x },{y }} C. {φ,{x },{y },{x , y }} D. {{x },{y },{x , y }} 4. 设集合 A ＝{1,2,3}，A 上的关系 R ＝ {(1,1),(2,2),(2,3),(3,3),(3,2)}， 则R 不具备（ ）. 三、计算题（共50分） R Q P G →∧?=)( 1．若P ：他聪明；Q ：他用功；则“他虽聪明，但不用功”可符号化为（ ） A. Q P ∨ B. Q P ～∨ C. Q P ～∧ D. Q P ～→ 2．P 、Q 为命题变元，则Q P →的对偶式为（ ） A . Q P → B . P Q → C . Q P ～∧ D . P Q ～∧ 3．谓词公式),(y x yP x ??的否定式为（ ） A .),(y x P y x ～?? B .),(y x P y x ～?? C .),(y x P y x ～?? D .),(y x P y x ～?? 4．A = {1, 2, 3}，R = { 填空10% （每小题 2 分） 1、若P，Q，为二命题，P Q 真值为0 当且仅当。 2、命题“对于任意给定的正实数，都存在比它大的实数” 令F（x）：x 为实数，L（x, y） : x y 则命题的逻辑谓词公式为。 3、谓词合式公式xP（x） xQ（x）的前束范式为。 4、将量词辖域中出现的和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为 换名规则。 5、设x 是谓词合式公式A的一个客体变元，A的论域为D，A（x）关于y 是自由的，则被称为存 在量词消去规则，记为ES。 选择25% （每小题分） 1、下列语句是命题的有（）。 A、明年中秋节的晚上是晴天； C、xy 0 当且仅当x 和y 都大于0； D 、我正在说谎。 2、下列各命题中真值为真的命题有（）。 A、2+2=4当且仅当3是奇数； B、2+2=4当且仅当 3 不是奇数； C、2+2≠4 当且仅当3是奇数； D、2+2≠4当且仅当 3 不是奇数； 3、下列符号串是合式公式的有（） A、P Q ； B、P P Q； C、( P Q) (P Q)； D、(P Q) 。 4、下列等价式成立的有（ ）。 A、P QQ P ； B、P(P R) R； C、P (P Q) Q； D 、P (Q R) (P Q) R。 5、若A1,A2 A n和B为 wff ，且A1 A2 A n B 则 （ ）。 A、称A1 A2 A n 为 B 的前 件； B 、称 B 为A1,A2 A n 的有效结论 C 、 x(M (x) Mortal (x)) ； D 、 x(M(x) Mortal (x)) 8、公式 A x(P(x) Q(x))的解释 I 为：个体域 D={2} ，P(x) ：x>3, Q(x) ：x=4则 A 的 真 值为（ ） 。 A 、 1； B 、 0； C 、 可满足式； D 、无法判定。 9、 下列等价关系正确的是（ ）。 A 、 x(P(x) Q(x)) xP(x) xQ(x)； B 、 x(P(x) Q(x)) xP(x) xQ(x)； C 、 x(P(x) Q) xP(x) Q ； D 、 x(P(x) Q) xP(x) Q 。 10 、 下列推理步骤错在（ ）。 ① x(F(x) G(x)) P ② F(y) G(y) US ① ③ xF(x) P ④ F(y) ES ③ ⑤G(y) T ②④I ⑥ xG(x) EG ⑤ A 、②； B 、④； C 、⑤； D 、⑥ 逻辑判断 30% 1、 用等值演算法和真值表法判断公式 A ((P Q) (Q P)) (P Q) 的类型。 C 、当且仅当 A 1 A 2 A n D 、当且仅当 A 1 A 2 A n B F 。 6、 A ，B 为二合式公式，且 B ，则（ ）。 7、 A 、 A C 、 A B 为重言式； B 、 B ； E 、 A B 为重言式。 人总是要死的”谓词公式表示为（ ）。 论域为全总个体域） M （x ） ： x 是人； Mortal(x) x 是要死的。 A 、 M (x) Mortal (x) ； B M (x) Mortal (x) 离散数学试题(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 离散数学考试试题(A卷及答案） 一、证明题（10分） 1) (P∧Q∧A C)∧(A P∨Q∨C ) (A∧(P Q ))C。P<->Q=(p->Q)合取（Q->p） 证明: (P∧Q∧A C)∧(A P∨Q∨C) (P ∨Q ∨A∨C)∧(A∨P∨Q∨C) ((P ∨Q ∨A)∧(A∨P∨Q))∨C反用分配律 ((P∧Q∧A)∨(A ∧P ∧Q))∨C ( A∧((P∧Q)∨(P ∧Q)))∨C再反用分配律 GAGGAGAGGAFFFFAFAF ( A∧(P Q))∨C (A∧(P Q ))C 2) (P Q)P Q。 证明：(P Q)((P∧Q))(P ∨Q))P Q。 二、分别用真值表法和公式法求(P(Q∨R))∧(P∨(Q R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。 主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。 主析取范式可由析取范式经等值演算法算得。 GAGGAGAGGAFFFFAFAF 证明： 公式法：因为(P(Q ∨R))∧(P∨(Q R)) (P∨Q∨R)∧(P∨(Q ∧R )∨(Q ∧R)) (P∨Q ∨R)∧(((P∨Q)∧(P ∨R ))∨(Q ∧R ))分配律 (P∨Q∨R)∧(P∨Q ∨Q)∧(P∨Q ∨R)∧(P∨R ∨Q)∧(P∨R ∨R) (P∨Q ∨R)∧(P∨Q ∨R )∧(P ∨Q∨R) M∧5M∧6M使（非P析取Q析取R）为0 4 GAGGAGAGGAFFFFAFAF 所赋真值，即100，二进制为4 GAGGAGAGGAFFFFAFAF离散数学复习题(全)
【浙江工商大学】《离散数学》期末考试题(B)
离散数学模拟试卷和答案
离散数学复习题
离散数学期末试卷及答案
离散数学期末考试试题及答案
离散数学模拟试题及答案
离散数学复习题
离散数学试卷及答案
离散数学期末考试试题及答案
离散数学考试试题(A、B卷及答案)
- 最新离散数学期末练习题 (带答案)
- 离散数学期末复习试题及答案(一)
- 离散数学期末复习试题及答案
- 离散数学期末考试题(附答案和含解析1)
- 离散数学期末复习题
- 淮海工学院 离散数学期末复习题答案
- 《离散数学》期末复习题答案_80011521535014977
- 离散数学本科期末复习题
- 离散数学期末考试题
- 离散数学期末考试题(附答案和含解析3)
- 离散数学期末练习题-(带标准答案)
- 离散数学期末试题
- 离散数学期末复习题
- 离散数学期末考试题答案
- 《离散数学》期末复习题答案
- 中国石油大学大学《离散数学》期末复习题及答案
- 离散数学期末练习题-(带答案)
- 【浙江工商大学】《离散数学》期末考试题(A)
- 最新离散数学期末练习题-(带答案)
- 离散数学期末试题及答案完整版