离散数学试题与答案
【篇一：离散数学试题及答案】
一、填空题
1 设集合a,b，其中a＝{1,2,3}, b= {1,2}, 则a - b＝
____________________;＝ __________________________ .
3. 设集合a = {a, b}, b = {1, 2}, 则从a到b的所有映射是
__________________________ _____________, 其中双射的是
__________________________.
4. 已知命题公式g＝?(p?q)∧r，则g的主析取范式是
_______________________________
______________________________________________________ ____.
5.设g是完全二叉树，g有7个点，其中4个叶点，则g的总度数为__________，分枝点数为________________.
7. 设r是集合a上的等价关系，则r所具有的关系的三个特性是
______________________, ________________________,
_______________________________.
8. 设命题公式g＝?(p?(q?r))，则使公式g为真的解释有
__________________________，
_____________________________,
__________________________.
9. 设集合a＝{1,2,3,4}, a上的关系r1 = {(1,4),(2,3),(3,2)}, r1 = {(2,1),(3,2),(4,3)}, 则 r1?r2 = ________________________,r2?r1 =____________________________,
=________________________.
10. 设有限集a, b，|a| = m, |b| = n, 则| |?(a?b)| =
_____________________________.
11 设a,b,r是三个集合，其中r是实数集，a = {x | -1≤x≤1, x?r}, b = {x | 0≤x 2, x?r},则a-b = __________________________ , b-a = __________________________ , a∩b =
__________________________ , .
13. 设集合a＝{2, 3, 4, 5, 6}，r是a上的整除，则r以集合形式(列举法)记为___________
______________________________________________________ _.
14. 设一阶逻辑公式g = ?xp(x)??xq(x)，则g的前束范式是
__________________________ _____.
15.设g是具有8个顶点的树，则g中增加_________条边才能把g 变成完全图。
?(a) - ?(b) r12
16. 设谓词的定义域为{a, b},将表达式?xr(x)→?xs(x)中量词消除，写成与之对应的命题公式是
______________________________________________________ ____________________.
17. 设集合a＝{1, 2, 3, 4}，a上的二元关系r＝{(1,1),(1,2),(2,3)}, s ＝{(1,3),(2,3),(3,2)}。则r?s＝
_____________________________________________________, r2＝
______________________________________________________.
二、选择题
1 设集合a={2,{a},3,4}，b = {{a},3,4,1}，e为全集，则下列命题正确的是( )。
(a){2}?a(b){a}?a(c)??{{a}}?b?e (d){{a},1,3,4}?b.
2 设集合a={1,2,3},a上的关系r＝{(1,1),(2,2),(2,3),(3,2),(3,3)}，则r不具备( ).
(a)自反性 (b)传递性 (c)对称性 (d)反对称性
则元
3 设半序集(a,≤)关系≤的哈斯图如下所示，若a的子集
素6为b的( )。
(a)下界(b)上界 (c)最小上界 (d)以上答案都不对 4 下列语句中，( )是命题。
(a)请把门关上 (b)地球外的星球上也有人
(c)x + 5 6 (d)下午有会吗？
5 设i是如下一个解释：d＝{a,b}, p(a,a) p(a,b) p(b,a) p(b,b) 1 0 1 0
则在解释i下取真值为1的公式是( ).
(a)?x?yp(x,y)(b)?x?yp(x,y)(c)?xp(x,x) (d)?x?yp(x,y).
6. 若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是( ).
(a)(1,2,2,3,4,5)(b)(1,2,3,4,5,5)(c)(1,1,1,2,3) (d)(2,3,3,4,5,6).
7. 设g、h是一阶逻辑公式，p是一个谓词，g＝?xp(x), h＝?xp(x),则一阶逻辑公式g?h是( ).
(a)恒真的(b)恒假的(c)可满足的 (d)前束范式.
8 设命题公式g＝?(p?q)，h＝p?(q??p)，则g与h的关系是( )。
(a)g?h(b)h?g(c)g＝h (d)以上都不是.
9 设a, b为集合，当( )时a－b＝b.
(a)a＝b (b)a?b (c)b?a (d)a＝b＝?.
10 设集合a = {1,2,3,4}, a上的关系r＝{(1,1),(2,3),(2,4),(3,4)}, 则r 具有( )。
(a)自反性(b)传递性 (c)对称性 (d)以上答案都不对
11 下列关于集合的表示中正确的为( )。
(a){a}?{a,b,c} (b){a}?{a,b,c} (c)??{a,b,c} (d){a,b}?{a,b,c}
12 命题?xg(x)取真值1的充分必要条件是( ).
(a) 对任意x，g(x)都取真值1.(b)有一个x0，使g(x0)取真值1.
(c)有某些x，使g(x0)取真值1.(d)以上答案都不对.
13. 设g是连通平面图，有5个顶点，6个面，则g的边数是( ).
(a) 9条(b) 5条(c) 6条 (d) 11条.
14. 设g是5个顶点的完全图，则从g中删去( )条边可以得到树.
(a)6(b)5(c)10 (d)4.
1111?
0100??，则1011??0101?0110???0?1的相邻矩阵
为??1??1??115. 设图gg的顶点数与边数分别为( ).
(a)4, 5 (b)5, 6 (c)4, 10 (d)5, 8.
三、计算证明题
1.设集合a＝{1, 2, 3, 4, 6, 8, 9, 12}，r为整除关系。
(1) 画出半序集(a,r)的哈斯图；
(2) 写出a的子集b = {3,6,9,12}的上界，下界，最小上界，最大下界；
(3) 写出a的最大元，最小元，极大元，极小元。
2. 设集合a＝{1, 2, 3, 4}，a上的关系r＝{(x,y) | x, y?a 且 x ? y}, 求
(1) 画出r的关系图；
(2) 写出r的关系矩阵.
3. 设r是实数集合，?,?,?是r上的三个映射，?(x) = x+3, ?(x) = 2x, ?(x) ＝ x/4,试求复
合映射???，???, ???, ???，?????.
4. 设i是如下一个解释：d = {2, 3},
a
3 b 2 f (2) 3 f (3) 2 p(2, 2) p(2, 3) p(3, 2) p(3, 3) 0 0 1 1
试求 (1) p(a, f (a))∧p(b, f (b));
(2) ?x?y p (y, x).
5. 设集合a＝{1, 2, 4, 6, 8, 12}，r为a上整除关系。
(1) 画出半序集(a,r)的哈斯图；
(2) 写出a的最大元，最小元，极大元，极小元；
(3) 写出a的子集b = {4, 6, 8, 12}的上界，下界，最小上界，最大下界.
6. 设命题公式g = ?(p→q)∨(q∧(?p→r)), 求g的主析取范式。
7. (9分)设一阶逻辑公式：g = (?xp(x)∨?yq(y))→?xr(x)，把g化成前束范式.
9. 设r是集合a = {a, b, c, d}. r是a上的二元关系, r = {(a,b), (b,a), (b,c), (c,d)},
(1) 求出r(r), s(r), t(r)；
(2) 画出r(r), s(r), t(r)的关系图.
11. 通过求主析取范式判断下列命题公式是否等价：
(1) g = (p∧q)∨(?p∧q∧r)
(2) h = (p∨(q∧r))∧(q∨(?p∧r))
13. 设r和s是集合a＝{a, b, c, d}上的关系，其中r＝{(a, a),(a,
c),(b, c),(c, d)}, s＝{(a, b),(b, c),(b, d),(d, d)}.
(1) 试写出r和s的关系矩阵；
(2) 计算r?s, r∪s, r1, s1?r1. －－－
四、证明题
1. 利用形式演绎法证明：{p→q, r→s, p∨r}蕴涵q∨s。
2. 设a,b为任意集合，证明：(a-b)-c = a-(b∪c).
3. (本题10分)利用形式演绎法证明：{?a∨b, ?c→?b, c→d}蕴涵a→d。
4. (本题10分)a, b为两个任意集合，求证：
a－(a∩b) = (a∪b)－b .
参考答案
一、填空题
1. {3}; {{3},{1,3},{2,3},{1,2,3}}.
2. 2.n2
3. ?1= {(a,1), (b,1)}, ?2= {(a,2), (b,2)},?3= {(a,1), (b,2)}, ?4= {(a,2), (b,1)}; ?3, ?
4.
4. (p∧?q∧r).
5. 12, 3.
6. {4}, {1, 2, 3, 4}, {1, 2}.
7. 自反性；对称性；传递性.
8. (1, 0, 0), (1, 0, 1), (1, 1, 0).
9. {(1,3),(2,2),(3,1)}; {(2,4),(3,3),(4,2)}; {(2,2),(3,3)}.
10. 2m?n.
11. {x | -1≤x 0, x?r}; {x | 1 x 2, x?r}; {x | 0≤x≤1, x?r}.
12. 12; 6.
13. {(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6,
6)}.14. ?x(?p(x)∨q(x)).15. 21.
【篇二：离散数学练习题及答案】
的表示方法有两种：法。请把“奇整数集合”表示出
，k?z} 来{}。1、列举；描述；{x|x?2k?1
2、无向连通图g含有欧拉回路的充分必要条件是
2*、连通有向图d含有欧拉回路的充分必要条件是d中每个结点的
入度＝出度.
3、设r是集合a上的等价关系，则r所具有的关系的三个特性是自反性、对称性、传递性.
4、有限图g是树的一个等价定义是：.
5、设n(x)：x是自然数，z(y)；y是整数，则命题“自然数都是整数，而有的整数不是自然
数”符号化为?x(n(x)?z(x))??x(z(x)??n(x))
6、在有向图的邻接矩阵中，第i行元素之和,第j列元素之和分别为
结点v的出度和结点v的入度．
7、设a，b为任意命题公式，c为重言式，若a?c?b?c，那么命题a?b是
重言式的真值是 1．
8、命题公式?(p?q)的主析取范式为
9、设图g＝v，e和g?＝v?,e?,若g?是g的真子图，若
，则g?是g的生成子图. v??v或e??e;v??v,e??e
10、在平面图g??v,e?中,则
11、设a?{a,b},?deg(r)＝,其中r(i=1,2,…,r)是g的
面． iiri?1b?{1,2}，则从a到b的所有映射是11、?1={（a，1），（b，1）}；?2={（a，2），（b，2）}；?3={（a，1），（b，2）}；?4={（a，
2），（b，1）}
12、表达式?x?yl（x，y）中谓词的定义域是{a，b，c}，将其中的
量词消除，写成与之等价
的命题公式为
12、（l（a，a）?l（a，b）?l（a，c））?（l（b，a）?l（b，b）?l（b，c））?（l（c，a）?l（c，b）?l（c，c））
12*、设个体域d＝{a,b},公式?x(g(x)??yh(x,y))消去量词化为
13、含有三个命题变项p，q，r的命题公式p?q的主析取范式是
14、设r，s都是集合a上的等价关系，则对称闭包s(r?s)=15、设
g是连通平面图，v,e,r分别表示g的结点数，边数和面数，则v,e
和r满足的关系式
是v?r?e??
16、设g是n个结点的简单图，若g，则g一定是哈密顿图.
17、一个有向树t称为根树，若
称为树叶. 若有向图t恰有一个结点的入度为0，其余结点入度为1；入度为0的结点；出度为0的结点.
18、图的通路中边的数目称为结点不重复的通路是通路. 边不重复的
通路是通路. 通路长度；初级；简单.
19、设a和b为有限集，|a|=m，|b|=n，则有个从a到b的关系，有个从a到b的函数，其中当m?n时有个入射，当m=n时，有
个双射。 19、2m*nm,nm,cn?m!,m!
2a?{n|n?n}（是/不是）可数的。是 20、集合
21、设l??1,2,3,4,12?上的整除关系
??a1,a2a1,a2?l,a1整除a2 ??
在l上定义两个二元运算?和?：对任意a,b?l，a?b?glb(a,b)，
a?b?lub(a,b)。请填空（在横线上填是或不是）：①是②是③是
④不是
①代数系统?l,?,?? 格。②代数系统?l,?,?? 有界格。③代数系
统?l,?,?? 有补格。④代数系统?l,?,?? 分配格。
二、单项选择题（选择一个正确答案的代号，填入括号中）
1、设命题公式g= ?（p?q），h=p?（q? ?p），则g与h的关系
是（ a ）。
a．g?hb．h?g c．g=h d．以上都不是
2、下列命题公式等值的是( c )
(a)?p??q,p?q
(c)q?(p?q),?q?p?q(b)a?(a?b),?a?(a?b)(d)?a?(a?b),b
3、设v＝{a,b,c,d},与v能构成强连通图的边集e＝( a )
(a) {a,b,a,c,d,a,b,d,c,d} (b) {a,d,b,a,b,c,b,d,d,c}
(c) {a,c,b,a,b,c,d,a,d,c} (d) {a,d,b,a,b,d,c,d,d,c}
4、设l(x)：x是演员，j(x)：x是老师，a(x,y)：x佩服y. 那么命题“所有演员都佩服某些老
师”符号化为( b )
(a) ?xl(x)?a(x,y)
(b) ?x(l(x)??y(j(y)?a(x,y)))(c) ?x?y(l(x)?j(y)?a(x,y))
(d) ?x?y(l(x)?j(y)?a(x,y))
5、在由3个元素组成的集合上，可以有 (d ) 种不同的关系。
(a)3 (b)8(c) 9 (d) 512
6、设s1=?,s2={?},s3=p({?}),s4=p(?)则命题为假的是( a )．
(a)s2?s4(b) s1?s3 (c) s2?s4 (d) s4?s3
7、设g是连通平面图，有v个结点，e条边，r个面，则r= ( a )．
(a) e－v＋2(b)v＋e－2(c)e－v－2(d) e＋v＋2
8、下列命题正确的是（ a ）。
a．??{?}=? b．??{?}=?c．{a}?{a，b，c} d．??{a，b，c}
9、设a, b, c都是集合，如果a?c＝b?c，则有(c )
(a) a＝b (b) a?b (c) 当a－c＝b－c时,有a=b (d) 当c=u时, 有
a?b
10、设(b,?,?,,0,1)是布尔代数，?a,b?b,a?b，则下式不成立的是
(d ) (a)ab?0(b)a?b?1(c)a?b?a(d)a?b?1
11、下面给出的一阶逻辑等价式中，（ a ）是错的。
a． ?x（a（x）?b（x））=?xa（x）??xb（x）
b． a??xb（x）=?x （a?b（x））
c． ?x（a（x）?b（x））=?xa（x）??xb（x）
d． ??xa（x）=?x（?a（x））
三、多重选择题(每道小题都可能有一个以上的正确选项，须选出所
有的正确选项，不答不得分，多选、少选或选错都将按比例扣分。)
1、命题公式 (p∧(p→q))→q是_____式。
(1) 重言 (2) 矛盾 (3) 可满足 (4) 非永真的可满足
2、给定解释i=(d,ic)=(整数集，{f(x,y):f(x,y)=x-y；
g(x,y):g(x,y)=x+y；
p(x,y):xy})，下列公式中_____在解释i下为真。
(1) p(f(x,y),g(x,y)) (2) ?x?y p(f(x,y),g(x,y))
(3) ?x?y(p(x,y)→ p(f(x,y),x)) (4) ?x?y p(f(x,y),g(x,y))
3、Ａ是集合，a =10，则p(a)=_____。
(1) 100(2) 99 (3) 2048 (4) 1024(5) 512
4、集合Ａ={x|x是整数，x230}，Ｂ={x|x是质数，x20}，c={1,3,5}，则
①(a?b)?c=_____;
②(b?a)?c=_____;
③(c?a)?(b?a)=_____;
④(b?c)?a=_____。
(1) {1,2,3,5}(2) ? (3) {0} (4) {1,3,5,7,11,13,17,19}
(5) {1,3,5,7} (6) {7,11,13,17,19}
5、设a、b、c是集合，下列四个命题中，_____在任何情况下都是
正确的。
(1)若a?b且b∈c，则a∈c (2) 若a?b且b∈c，则a?c
(3)若a∈b且b?c，则a?c (4) 若a∈b且b?c，则a∈c
6、设集合Ａ={a,b,c,d,e,f,g}，Ａ的一个划分?={{a,b},{c,d,e},{f,g}}，则?
所对应的等价关系有_____个二元组。
(1) 14 (2) 15(3) 16 (4) 17 (5) 8 (6) 49 (7) 512
7、s ={1,2,3,4,5,6,7,8,9,10,11,12}，≤是s上的整除关系。s的子集
Ｂ＝
{2,4,6｝，则在s，≤中，Ｂ的最大元是_____；Ｂ的最小元是_____；Ｂ的上确界是_____；Ｂ的下确界是_____。
(1) 不存在的(2) 36(3) 24 (4) 12 (5) 6 (6) 1 (7) 2
8、设有有限布尔代数(b,+,*,’,0,1)，则b=_____能成立。
(1) 1 (2) 2 (3) 3 (4) 4 (5) 5(6) 8(7) 9
9、g ={0,1,2,?,n}，n ∈n，定义?为模n加法，即x?y =(x+y) mod n，则
代数系统(g，?)_____。
(1) 是半群但不是群(2) 是无限群 (3) 是循环群 (4) 是变换群
(5)是交换群
10、仅有一个结点的图称为()，当然也是( )
(1) 零图 (2) 平凡图 (3) 补图 (4) 子图
1. 1、3。
2. 4。
3. 4。
4. 1；4；2；2。
5. 4。
7. 1；7；4；7。 8. 2、4、6。 9. 3、5。 10. 2；1。
四、化简解答题
1、(1)设图g(如第1题图)，作图g 的嵌入图，说明图g是平面图.
第1题图 1、(1)
图g的嵌入图，如第12题答案图.故图g为平面图 (4分)第12题答案图
(2)在具有n个顶点的完全图kn中删去多少条边才能得到树？
解：n个顶点的完全图kn中共有6. 4。 n?(n?1)条边，n个顶点的树应有n?1条边，于是，删2
n?(n?1)(n?1)?(n?2)?(n?1)?去的边有：。 22
2、判别谓词公式?x?yf(x,y)??y?xf(x,y)的类型.
2、设i为任意一个解释，d为i的个体域. 若在解释i下，该公式的前件为0，无论?y?xf(x,y)如何取值，?x?yf(x,y)??y?xf(x,y)为1；若在解释i下，该公式的前件为1，则?x0?d,使得?yf(x,y)为1，它蕴含着?y??d,f(x0,y?)为1??xf(x,y?)为1，由y?的任意性，必
有?y?xf(x,y)为1，于是?x?yf(x,y)??y?xf(x,y)为1.
所以，?x?yf(x,y)??y?xf(x,y)是永真式．
3、化简集合表达式：((a?b?c)?(a?c))－((c?(c－b)－a)
3、((a?b?c)?(a?c))－((c?(c－b)?～a)
＝(a?c)－（c?～a）(两次用吸收律)
=((a?c)?(～c?a)
=(a?～c)?(c?～c)?a?(a?c)
=(a?～c)???a=a
4、判断下列哪些运算结果是对的？哪些是错的？请将错误的运算结果更正过来．
(1) ??{?}?? (2) ??{?}??
(3) {?}?{?,{?}}?{?} (4) {?,{?}}?{?}?{?,{?}}
（5）(a?b)?b?a （6）(a?b)?b?a
（7）a?a?a （8）(a?b)?a??
4、(1) 对．(2) 错．应为{?}．(3) 对． (4) 错．应为{{?}}
（5）错．应为a?b（6）错．应为a?b(或a?~b或a－ab)
（7）错．应为?，即a?a?a?a?a?a?? （8）对．
5、将命题公式?p?q?(?r?p)化为只含?和?的尽可能简单的等值式． 5、?p?q?(?r?p)
??(p??q)?(r?p)（优先级有误）
??(p??q)??(?p??r)不惟一.
(1) v1e5 v5e7 v2e2 v3 (2) v5e6 v2e2 v3e3 v4e8 v2e7 v5 v25
4 (3) v2e7 v5e6 v2 (4) v1e1 v2e2 v3e3 v4e8 v2e6 v5
e
v4
6、(1) 初级通路；(2) 简单回路；(3) 初级回路；(4) 简单通路 .e3
v ev 7、试问n取何值时，无向完全图kn，存在一条欧拉回路？ 6、设图g如右图.已知通路
7、由于kn有n个结点，并且每个结点的度数均为n－1，于是，
当n为奇数时，kn的每个结点的度数都是偶数，所以存在一条欧拉
回路．
8、已知(l，*，?)是格，且二元运算*和?满足分配律，?a,b,c?l，化
简表达式((a*b)?(a*c))* ((a*b)?(b*c))
解答：((a*b)?(a*c))*((a*b)?(b*c))
＝(a*b)? ( (a*c)* (b*c))(分配律)
=(a*b) ?((a*b)*c) (幂等律)
=a*b(吸收律)
9、化简(?p?(?q?r))?(q?r)?(p?r)。
9、(?p?(?q?r))?(q?r)?(p?r)=(?p??q?q?p)?r=
=(?p?q?p)?r=r
10、试将一阶逻辑公式?x??yp?x,y?????yq?y??r?x???化成前束范式。解：
【篇三：离散数学试卷及答案】
t>一、填空20% （每小题2分）
1．设 a?{x|(x?n)且(x?5)},b?{x|x?e且x?7}（n：自然数集，e+ 正
偶
数）则 a?b? 。 2．a，b，c表示三个集合，文图中阴影部分的集
合表达式为。
3．设p，q 的真值为0，r，s的真值为1，则
?
?(p?(q?(r??p)))?(r??s)的真值= 。
4．公式(p?r)?(s?r)??p的主合取范式为。
5．若解释i的论域d仅包含一个元素，则 ?xp(x)??xp(x) 在i下真值为。
6．设a={1，2，3，4}，a上关系图为
则 r2 = 。
7．设a={a，b，c，d}，其上偏序关系r的哈斯图为
则 r= 。
8．图的补图为。
9．设a={a，b，c，d} ，a上二元运算如下：
那么代数系统a，*的幺元是，它们的逆元分别为。
10．下图所示的偏序集中，是格的为。
二、选择 20% （每小题 2分）
1、下列是真命题的有（） a． {a}?{{a}}；
b．{{?}}?{?,{?}}；
c． ??{{?},?}； d． {?}?{{?}}。 2、下列集合中相等的有（）
a．{4，3}??；b．{?，3，4}；c．{4，?，3，3}；d．{3，4}。3、设a={1，2，3}，则a上的二元关系有（
）个。 a． 23 ； b． 32 ；c． 2
3?3
； d． 3
2?2
。
4、设r，s是集合a上的关系，则下列说法正确的是（）a．若r，
s 是自反的，则r?s是自反的；b．若r，s 是反自反的，则r?s是
反自反的；c．若r，s 是对称的，则r?s是对称的；d．若r，s 是
传递的，则r?s是传递的。
5、设a={1，2，3，4}，p（a）（a的幂集）上规定二元系如下
r?{?s,t?|s,t?p(a)?(|s|?|t|}则p（a）/ r=（）
a．a ；b．p(a) ；c．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}； d．{{?}，{2}，{2，3}，{{2，3，4}}，{a}}
6、设a={?，{1}，{1，3}，{1，2，3}}则a上包含关系“?”的哈斯图为（）
7、下列函数是双射的为（）
a．f : i?e , f (x) = 2x ； b．f : n?n?n, f (n) = n , n+1 ； c．f :
r?i , f (x) = [x] ； d．f :i?n, f (x) = | x | 。（注：i—整数集，e—
偶数集， n—自然数集，r—实数集） 8、图中从v1到v3长度为3 的通路有（）条。
a． 0； b． 1；
c． 2；
d． 3。
9、下图中既不是eular图，也不是hamilton图的图是（）
10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则
该树有（）个4
度结点。
a．1； b．2； c．3； d．4 。
三、证明 26%
１、r是集合x上的一个自反关系，求证：r是对称和传递的，当且仅当
a, b 和a , c在r中有.b , c在r中。（8分）
２、f和g都是群g1 ,★到 g2, *的同态映射，证明c , ★是g1, ★的一个子
群。其中c={x|x?g1且f(x)?g(x)} (8分)
３、g=v, e (|v| = v，|e|=e ) 是每一个面至少由k（k?3）条边围成的连通平面
e?
k(v?2)k?2
图，则
，由此证明彼得森图（peterson）图是非平面图。（11分）
四、逻辑推演 16%
用cp规则证明下题（每小题 8分） 1、a?b?c?d,d?e?f?a?f
2、?x(p(x)?q(x))??xp(x)??xq(x)
五、计算 18%
1、设集合a={a，b，c，d}上的关系r={a , b , b , a , b, c , c , d }用矩阵运算求出r的传递闭包t (r)。（9分）
2、如下图所示的赋权图表示某七个城市v1,v2,?,v7及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。（９分）
试卷一答案：
一、填空 20% （每小题2分）
1、{0，1，2，3，4，6}；
2、(b?c)?a；
3、1；
4、
(?p?s?r)?(?p??s?r)； 5、1；6、{1,1, 1,3, 2,2, 2,4 }；7、
{a.b,a,c,a,d,b,d,c,d} ? ia ；8、
9、a ；a , b , c ,d ；a , d , c , d ；10、
c; 二、选择 20% （每小题 2分）
三、证明 26%
1、证：
“?” ?a,b,c?x
若a,b,a,c ? r
由r对称性知
b,a,c,a? ? r，由r传递性得 b,c ? r
“?” 若a,b ? r，a,c ? r有 b,c ? r 任意 a,b?x，因
a,a ? r若a,b ? r? b,a ? r 所以r是对称的。
若a,b ? r，b,c ? r 则 b,a ? r ??b,c??r ?a,c ? r 即r是传递的。
2、证
f(b
?1
?a,b?c)?f
?1
?1
，
g(b
?1
?1
有
)?g
?1
f(a)?g(a),f(b)?g(b)
?1
，
?1
又
(b),(b)?f(b
?1
)?f
?1
(b)?g
?1
?1
(b)?g(b
)
?f(a★b
)?f(a)*f(b)?g(a)*g(b
)?g(a★b)
?a★b
?1
?c
? c , ★是 g1 , ★的子群。
3、证：
r
2e?
①设g有r个面，则
2?v?e?r?v?e?
2ek即得
e?
?d(f)?rk
i
i?1
，即
r?
2e
k。而 v?e?r?2故
k(v?2)k?2
。（8分）
e?
k(v?2)k?2
②彼得森图为k?5,e?15,v?10，这样不成立，
试卷二试题与参考答案 一、填空 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、下面偏序集( )能构成格。
《离散数学》试题及答案 一、选择题：本题共5小题，每小题3分，共15分，在每小题给出的四个选项中，只有一项是符合题目要求的。 1. 命题公式Q Q P →∨)(为 ( ) (A) 矛盾式 (B) 可满足式 (C) 重言式 (D) 合取范式 2．设P 表示“天下大雨”， Q 表示“他在室内运动”，则命题“除非天下大雨，否则他不在室内运动”符号化为（ ）。 (A)． P Q →； (B)．P Q ∧； (C)．P Q ?→?； (D)．P Q ?∨． 3.设集合A ={{1,2,3}, {4,5}, {6,7,8}}，则下式为真的是( ) (A) 1A (B) {1,2, 3}A (C) {{4,5}}A (D) A 4. 设A ＝{1,2},B ={a ,b ,c },C ={c ,d }, 则A ×(B C )= ( ) (A) {<1,c >,<2,c >} (B) {
离散数学考试题(后附详细答案) 一、命题符号化（共6小题，每小题3分，共计18分） 1.用命题逻辑把下列命题符号化 a)假如上午不下雨，我去看电影，否则就在家里读书或看报。 设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：（PQ）(PRS) b)我今天进城，除非下雨。 设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：Q→P或P→Q c)仅当你走，我将留下。 设P表示命题“你走”，Q表示命题“我留下”，命题符号化为：Q→P 2.用谓词逻辑把下列命题符号化 a)有些实数不是有理数 设R(x)表示“x是实数”，Q(x)表示“x是有理数”，命题符号化为： x(R(x) Q(x)) 或x(R(x) →Q(x)) b)对于所有非零实数x，总存在y使得xy=1。 设R(x)表示“x是实数”，E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为： x(R(x) E(x,0) →y(R(y) E(f(x,y),1)))) c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=b. 设F(f)表示“f是从A到B的函数”, A(x)表示“x∈A”, B(x)表示“x∈B”,E(x,y)表示“x=y”, 命题符号化为：F(f)a(A(a)→b(B(b) E(f(a),b) c(S(c) E(f(a),c) →E(a,b)))) 二、简答题（共6道题，共32分） 1.求命题公式(P→(Q→R))(R→(Q→P))的主析取范式、主合取范式，并写出所有成真赋值。 （5分） (P→(Q→R))(R→(Q→P))（PQR）(PQR) (（PQR）→(PQR)) ((PQR) →（PQR）). (（PQR）(PQR)) ((PQR) （PQR）) (PQR)(PQR) 这是主合取范式 公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为 （PQR（PQR（PQR（PQR（PQR（PQR 2.设个体域为{1,2,3}，求下列命题的真值（4分） a)xy(x+y=4) b)yx (x+y=4) a) T b) F 3.求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。（4分） x(F(x)→G(x))→(xF(x)→xG(x)) x(F(x)→G(x))→(yF(y)→zG(z)) x(F(x)→G(x))→yz(F(y)→G(z)) xyz((F(x)→G(x))→(F(y)→G(z))) 4.判断下面命题的真假，并说明原因。（每小题2分，共4分）
离散数学期末试题及答 案 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的补元( ).
离散数学试题（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 ＝{，，，，，，，，
《离散数学》题库答案 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q →P (2)?Q=>P →Q (3)P=>P →Q (4)?P ∧(P ∨Q)=>?P 答：（1），（4） 2、下列公式中哪些是永真式？( ) (1)(┐P ∧Q)→(Q →?R) (2)P →(Q →Q) (3)(P ∧Q)→P (4)P →(P ∨Q) 答：（2），（3），（4） 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P ∧Q (2) P ∧Q=>P (3) P ∧Q=>P ∨Q (4)P ∧(P →Q)=>Q (5) ?(P →Q)=>P (6) ?P ∧(P ∨Q)=>?P 答：（2），（3），（4），（5），（6） 4、公式 x((A(x) B(y ，x)) z C(y ，z))D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答：（1） 是，T （2） 是，F （3） 不是 （4） 是，T （5） 不是 （6） 不是 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死 7、设P ：我生病，Q ：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校 答：（1） P Q →? （2） Q P ?→ （3） Q P ?? （4）Q P →? 8、设个体域为整数集，则下列公式的意义是( )。 (1) x y(x+y=0) (2) y x(x+y=0) 答：（1）对任一整数x 存在整数 y 满足x+y=0（2）存在整数y 对任一整数x 满足x+y=0 9、设全体域D 是正整数集合，确定下列命题的真值： (1) x y (xy=y) ( ) (2) x y(x+y=y) ( ) (3) x y(x+y=x) ( ) (4) x y(y=2x) ( ) 答：（1） F （2） F （3）F （4）T 10、设谓词P(x)：x 是奇数，Q(x)：x 是偶数，谓词公式 x(P(x)Q(x))在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立 答：（1） 11、命题“2是偶数或-3是负数”的否定是（ ）。 答：2不是偶数且-3不是负数。 12、永真式的否定是（ ） (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能 答：（2） 13、公式(?P ∧Q)∨(?P ∧?Q)化简为（ ），公式 Q →(P ∨(P ∧Q))可化简为（ ）。 答：?P ，Q →P
离散数学 2^m*n 一、选择题（2*10） 1．令P：今天下雨了，Q：我没带伞，则命题“虽然今天下雨了，但是我没带伞”可符号化为（）。 （A）P→?Q （B）P∨?Q （C）P∧Q （D）P∧?Q 2．下列命题公式为永真蕴含式的是（）。 （A）Q→（P∧Q）（B）P→（P∧Q） （C）（P∧Q）→P （D）（P∨Q）→Q 3、命题“存在一些人是大学生”的否定是(A)，而命题“所有的人都是要死的”的否定 是（）。 （A）所有人都不是大学生，有些人不会死 （B）所有人不都是大学生，所有人都不会死 （C）存在一些人不是大学生，有些人不会死 （D）所有人都不是大学生，所有人都不会死 4、永真式的否定是（）。
（A）永真式（B）永假式（C）可满足式（D）以上均有可能 5、以下选项中正确的是（）。 （A）0= ? （B）0 ? （C）0∈? （D）0?? 6、以下哪个不是集合A上的等价关系的性质？（） ）。 （A）2 （B）4 （C）3 （D）5 10．连通图G是一棵树，当且仅当G中（）。 （A）有些边不是割边（B）每条边都是割边 （C）无割边集（D）每条边都不是割边
二、填空题（2*10） 1、命题“2是偶数或-3是负数”的否定是________。 2、设全体域D是正整数集合，则命题?x?y(xy=y)的真值是______。 3、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为 4 5 6、设 7 8 (1)若A去，则C和D中要去1个人； (2)B和C不能都去； (3)若C去，则D留下 五、（15分）设A={1,2,3},写出下列图示关系的关系矩阵，并讨论它们的性质：
一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选项中只有 一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路 2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( ) A.10 B.12 C.16 D.14 3.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( ) A.b∧(a∨c) B.(a∧b)∨(a’∧b) C.(a∨b)∧(a∨b∨c)∧(b∨c) D.(b∨c)∧(a∨c) 4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( ) A.<{1},·> B.〈{-1},·〉 C.〈{i},·〉 D.〈{-i},·〉 5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交 运算，下列系统中是代数系统的有( ) A.〈Z，+，/〉 B.〈Z，/〉 C.〈Z，-，/〉 D.〈P(A)，∩〉 6.下列各代数系统中不含有零元素的是( ) A.〈Q，*〉Q是全体有理数集，*是数的乘法运算 B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算 C.〈Z，ο〉，Z是整数集，ο定义为xοxy=xy,?x,y∈Z D.〈Z，+〉，Z是整数集，+是数的加法运算 7.设A={1,2,3}，A上二元关系R的关系图如下： R具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性 8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( ) A.R∪I A B.R C.R∪{〈c,a〉} D.R∩I A 9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的 等价关系，R应取( ) A.｛〈c,a〉，〈a,c〉｝ B.{〈c,b〉，〈b,a〉} C.{〈c,a〉，〈b,a〉} D.{〈a,c〉，〈c,b〉} 10.下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x 常熟理工学院20 ～20 学年第学期 《离散数学》考试试卷（试卷库01卷） 试题总分： 100 分考试时限：120 分钟 题号一二三四五总分阅卷人得分 一、单项选择题（每题2分，共20分） 1.下列表达式正确的有( ) （A）（B）（C）（D） 2.设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列( )命题的真值为 真。 （A）（B）（C）（D） 3.集合A={1,2,…,10}上的关系R={ 1．n个命题变元组成的命题公式共有种不同的等价公式。 2．设〈L，≤〉为有界格，a为L中任意元素，如果存在元素b∈L,使，则称b是a 的补元。 3．设*，Δ是定义在集合A上的两个可交换二元运算，如果对于任意的x,y∈A,都有 ,则称运算*和运算Δ满足吸收律。 4．设T是一棵树，则T是一个连通且的图。 5．一个公式的等价式称作该公式的主合取范式是指它仅由组成。 6．量词否定等价式? ("x)P(x) ?，? ($x)P(x) ?。 7．二叉树有5个度为2的结点，则它的叶子结点数为。 8．设 试卷二十三试题与答案 一、单项选择题：（每小题1分，本大题共10分） 1．命题公式)(P Q P ∨→是（ ）。 A 、 矛盾式； B 、可满足式； C 、重言式； D 、等价式。 2．下列各式中哪个不成立（ ）。 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 ∧??∧?)())((。 3．谓词公式)())()((x Q y yR x P x →?∨?中的 x 是（ ）。 A 、自由变元； B 、约束变元； C 、既是自由变元又是约束变元； D 、既不是自由变元又不是约束变元。 4．在0 Φ之间应填入（ ）符号。 A 、= ； B 、?； C 、∈； D 、?。 5．设< A ， > 是偏序集，A B ?，下面结论正确的是（ ）。 A 、 B 的极大元B b ∈且唯一； B 、B 的极大元A b ∈且不唯一； C 、B 的上界B b ∈且不唯一； D 、B 的上确界A b ∈且唯一。 6．在自然数集N 上，下列（ ）运算是可结合的。 （对任意N b a ∈,） A 、b a b a -=*； B 、),max(b a b a =*； C 、b a b a 5+=*； D 、b a b a -=*。 7．Q 为有理数集N ，Q 上定义运算*为a*b = a + b – ab ,则 大学2013—2014学年度第二学期期末考试《离散数学》试卷 A 第一部分 选择题（共20 分） 一、单项选择题（本大题共10小题，每题只有一个正确答案，答对一题得2分共20分） 1、对任意集合A 、B 、和C ，下列论断中正确的是： 【 】 A. 若A ∈B ，B ?C ，则A ∈C B. 若A ∈B ，B ?C ，则A ?C C. 若A ?B ，B ∈C ，则A ∈C D. 若A ?B ，B ∈C ，则A ?C 2、设A={a,{a}},下列式子中正确的有： 【 】 A. {a}∈ρ(A) B. a ∈ρ(A) C. {a}?ρ(A) D. 以上都不是 3、P ：我将去镇上。Q ：我有时间。命题“我将去镇上，当且仅当我有时间”符号化为： 【 】A. P →Q B. Q →P C. P ?Q D. Q ∨?P 4、命题公式：（P ∧（P →Q ））→Q 是 【 】 A ．矛盾式 B. 可满足式 C. 重言式 D. 不能确定 5、谓词公式)())()((x Q y yR x P x →?∨?中，量词x ?的辖域是： 【 】 A. ))()((y yR x P x ?∨? B. )(x P C. )(),(x Q x P D. )()(y yR x P ?∨ 6、在如下各图中，哪一个是欧拉图？ 【 】 7、设|V|>1，G= < V , E >是强连通图，当且仅当： 【 】 A ．G 中至少有一条通路 B ．G 中至少有一条回路 C ．G 中有通过每个结点至少一次的通路 D ．G 中有通过每个结点至少一次的回路 8、设}}2,1{},1{,{Φ=S ，则 ρ(S) 有多少个元素？ 【 】 A ．3； B ．6； C ．7； D ．8 ； 9、集合A={1，2，3，4，5，6，7，8，9，10}上的关系R={ 精品文档 离散数学 10.设仃限集丸 B. |A|■申 p|p |p(AxB)| = 带伞”可符号化为( ) (C ) P A Q (D ) P A Q 2 ?下列命题公式为永真蕴含式的是( ) (A ) C H( P A Q ) ( B ) P -( P A Q ) (C ) (P A Q — P ( D (P V Q)— Q 3、 命题“存在一些人是大学生”的否定是(A)，而命题“所有的人都是要死 的”的否定是( )。 (A) 所有人都不是大学生，有些人不会死 (B) 所有人不都是大学生，所有人都不会死 (C) 存在一些人不是大学生，有些人不会死 (D) 所有人都不是大学生，所有人都不会死 4、 永真式的否定是()。 (A )永真式 (B )永假式 (C )可满足式 (D )以上均有可能 5、以下选项中正确的是()。 (A ) 0= ? (B ) 0 ? (C 0€ ? (D ) 0?? 6、以下哪个不是集合A 上的等价关系的性质？( ) (A )自反性 (B )有限性 (C )对称性 (D ) 传递性 7、集合 A={1,2,…;10}上的关系 R={ 离散数学图论部分综合练习 一、单项选择题 1．设无向图G 的邻接矩阵为 ??????? ? ??? ?? ???010 1010010000 011100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝ A．{(a, e)}是割边B．{(a, e)}是边割集 C．{(a, e) ,(b, c)}是边割集D．{(d, e)}是边割集 图三 7．设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是( )． 图四 A．（a）是强连通的B．（b）是强连通的 C．（c）是强连通的D．（d）是强连通的 应该填写：D 8．设完全图K n 有n个结点(n≥2)，m条边，当（）时，K n 中存在欧拉 回路． A．m为奇数B．n为偶数C．n为奇数D．m为偶数9．设G是连通平面图，有v个结点，e条边，r个面，则r= ( )． A．e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v＋2 10．无向图G存在欧拉通路，当且仅当( )． A．G中所有结点的度数全为偶数 B．G中至多有两个奇数度结点 C．G连通且所有结点的度数全为偶数 D．G连通且至多有两个奇数度结点 11．设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树． A．1 m n-+B．m n-C．1 m n++D．1 n m -+ 12．无向简单图G是棵树，当且仅当( )． A．G连通且边数比结点数少1 B．G连通且结点数比边数少1 一、判断正误20% （每小题2分） 1、设A.B. C是任意三个集合。 （1）若A∈B且B?C，则A?C。（） （2）若A?B且B∈C，则A?C。（） （3）若A?B且B∈C，则A?C。（） （4）A) ( ) ( ) (C A B A C B ⊕ = ⊕。（） （5）(A–B)?C=(A?C)-(B?C)。（） 2、可能有某种关系，既不是自反的，也不是反自反的。（） ３、若两图结点数相同，边数相等，度数相同的结点数目相等，则两图是同构的。（） ４、一个图是平面图，当且仅当它包含与Ｋ 3， 3 或Ｋ 5 在２度结点内同构的子图。（） ５、代数系统中一个元素的左逆元并一定等于该元素的右逆元。（） ６、群是每个元素都有逆元的半群。（） 二、8% 将谓词公式)) , ( ) ( ) ( ) (( )) , ( ) ( )( (z y Q z y P y y x Q x P x? ∧ ? → → ?化为前束析取范式与前束合取范式。 三、8% 设集合Ａ＝{a,b,c,d}上的关系Ｒ＝{ 五、10% 证明：若图Ｇ是不连通的，则Ｇ的补图G 是连通的。 六、10% 证明：循环群的任何子群必定也是循环群。 七、12% 用ＣＰ规则证明： １．F A F E D D C B A →?→∨∧→∨,。 ２．?∨??∨?(()()())()()((x P x x Q x P x )()x Q x 。 八、10% 用推理规则证明下式： 前提: ))()()(()),()()(())()()(((y W y M y y W y M y x S x F x ?∧?→?→∧? 结论：?→?)()((x F x S ))(x 九、13% 若集合Ｘ＝｛（１，２），（３，４），（５，６），……｝ }|,,,{12212211y x y x y x y x R +=+>><><<= 1、证明R 是X 上的等价关系。 2、求出X 关于R 的商集。 一、 填空 20%（每小题2分） 安徽大学20 09 — 20 10 学年第 1 学期 《 离散数学 》考试试卷（A 卷） （时间120分钟） 院/系 专业 姓名 学号 一、单项选择题（每小题2分，共20分） 1. 设:P 天没下雪，:Q 我去镇上，则命题“天正在下雪，我没去镇上”可符号化为（ D ） A.Q P ?→?； B. P Q ?→?； C.Q P ?∧； D. Q P ?∧?。 2.下列命题是重言式的是（ C ） A.)()(P Q Q P →∧→； B. )()(Q P P Q P ???∧； C. )(Q P Q P →→∧； D. Q P R Q P ∧?∧?∨→))((。 3. 设解释R 如下：论域D 为实数集，a=0, f(x,y)=x-y, A(x,y):x 离散数学试题与答案试卷一 一、填空 20% （每小题2分） 1．设 }7|{)},5()(|{<∈=<∈=+ x E x x B x N x x A 且且（N ：自然数集，E + 正偶数） 则 =?B A 。 2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 。 3．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 4．公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为 。 6．设A={1，2，3，4}，A 上关系图为 则 R 2 = 。 8．图的补图为 。 二、选择 20% （每小题 2分） 1、下列是真命题的有（ ） A ． }}{{}{a a ?； B ．}}{,{}}{{ΦΦ∈Φ； C ． }},{{ΦΦ∈Φ； D ． }}{{}{Φ∈Φ。 2、下列集合中相等的有（ ） A B C ?；B．{Φ，3，4}；C．{4，Φ，3，3}；D．{3，4}。 A．{4，3}Φ 3、设A={1，2，3}，则A上的二元关系有（）个。 A．23 ；B．32 ；C．332?；D．223?。 4、设R，S是集合A上的关系，则下列说法正确的是（） Rο是自反的； A．若R，S 是自反的，则S Rο是反自反的； B．若R，S 是反自反的，则S Rο是对称的； C．若R，S 是对称的，则S Rο是传递的。 D．若R，S 是传递的，则S 5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下 t s t s p A R= ∧ =则P（A）/ R=（） < > ∈ s (| || |} {t ) , ( | , A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}} 7、下列函数是双射的为（） A．f : I→E , f (x) = 2x ；B．f : N→N?N, f (n) = 离散数学试题(A卷答案） 一、证明题（10分） 1) (P∧Q∧A→C)∧(A→P∨Q∨C)? (A∧(P?Q))→C。 证明: (P∧Q∧A→C)∧(A→P∨Q∨C) ?(?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 ??( 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分）。 证明： 公式法：因为(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 4 ? m∨1m∨2m∨3m∨7m 所以，公式(P→(Q∨R))∧(?P∨(Q?R))为可满足式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。 真值表法： 式，其相应的成真赋值为000、001、010、011、111：成假赋值为：100、101、110。 三、推理证明题（10分） 1）?P∨Q，?Q∨R，R→S P→S。 证明：(1)P附加前提 一、填空 20% （每小题2分） 1．设 }7|{)},5()(|{<∈=<∈=+x E x x B x N x x A 且且（N ：自然数集，E + 正偶数） 则 =?B A 。 2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 。 3．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 4．公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为 。 6．设A={1，2，3，4}，A 上关系图为 则 R 2 = 。 7．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为 则 R= 。 8．图的补图为 。 9．设A={a ，b ，c ，d} ，A 上二元运算如下： 那么代数系统的幺元是 ，有逆元的元素为 ，它们的逆元分别为 。 10．下图所示的偏序集中，是格的为 。 二、选择 20% （每小题 2分） 1、下列是真命题的有（ ） A ． }}{{}{a a ? ； B ．}}{,{}}{{ΦΦ∈Φ； C ． }},{{ΦΦ∈Φ； D ． }}{{}{Φ∈Φ。 2、下列集合中相等的有（ ） A ．{4，3}Φ?； B ．{Φ，3，4}； C ．{4，Φ，3，3}； D ． {3，4}。 3、设A={1，2，3}，则A 上的二元关系有（ ）个。 A．23 ；B．32 ；C．332?；D．223?。 4、设R，S是集合A上的关系，则下列说法正确的是（） R 是自反的； A．若R，S 是自反的，则S R 是反自反的； B．若R，S 是反自反的，则S R 是对称的； C．若R，S 是对称的，则S R 是传递的。 D．若R，S 是传递的，则S 5、设A={1，2，3，4}，P（A）（A的幂集）上规定二元系如下 t s p R= t s ∈ =则P（A）/ R=（） < > ∧ A ) (| || |} ( , {t , | s A．A ；B．P(A) ；C．{{{1}}，{{1，2}}，{{1，2，3}}，{{1，2，3，4}}}；D．{{Φ}，{2}，{2，3}，{{2，3，4}}，{A}} 6、设A={Φ，{1}，{1，3}，{1，2，3}}则A上包含关系“?”的哈斯图为（） 7、下列函数是双射的为（） A．f : I→E , f (x) = 2x ；B．f : N→N?N, f (n) = 离散数学题库
离散数学试卷二十三试题与答案
的幺元为（ ）。 A 、a ； B 、b ； C 、1； D 、0。 8．给定下列序列，（ ）可以构成无向简单图的结点度数序列。 A 、（1，1，2，2，3）； B 、（1，1，2，2，2）； C 、（0，1，3，3，3）； D 、（1，3，4，4，5）。 9．设G 是简单有向图，可达矩阵P(G)刻划下列 （ ）关系。 A 、点与边； B 、边与点； C 、点与点； D 、边与边。 10．一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（ ）。 A 、5； B 、7； C 、9； D 、8。
离散数学试卷
离散数学试题及解答
上海大学-离散数学2-图部分试题
离散数学试卷及答案(17)
《离散数学》(上)试卷(A卷)及参考答案
离散数学全部试卷
最新离散数学试卷及答案 (1)
离散数学试卷及答案(1)
相关主题
文本预览