发布时间 : 星期二 文章离散数学习题及答案更新完毕开始阅读
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