在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???化成前束范式。 解：

【篇三：离散数学课后习题答案一】

txt>习题1.1

1. 下列哪些语句是命题，在是命题的语句中，哪些是真命题，哪些是假命题，哪些命题的真值现在还不知道？ （1）中国有四大发明。

（2）你喜欢计算机吗？ （4）请回答这个问题！ （6）x?7?10。

（3）地球上海洋的面积比陆地的面积大。 （5）2?3?6。

（7）园的面积等于半径的平方乘以圆周率。 （8）只有6是偶数，3才能是2的倍数。 （9）若x?y，则x?z?y?z。 （11）2020年元旦下大雪。 解

（10）外星人是不存在的。

（12）如果1?1?3，则血就不是红的。

是真命题的有：（1）、（3）、(7)、 (9) 、（12） ；是假命题的有：（5）、 (8) ；是命题

但真值现在不知道的有： (10)、 (11)；不是命题的有：（2）、（4）、（6）。

2. 令p、q为如下简单命题：p：气温在零度以下。q：正在下雪。用p、q和逻辑联接词符号化下列复合命题。

（1）气温在零度以下且正在下雪。 （2）气温在零度以下，但不在下雪。 （3）气温不在零度以下，也不在下雪。（4）也许在下雪，也许气温在零度以下，也许既下雪气温又在零度以下。 （5）若气温在零度以下，那一定在下雪。（6）也许气温在零度以下，也许在下雪，但如果气温在零度以上就不下雪。 （7）气温在零度以下是下雪的充分必要条件。 解 （1）p?q；（2）p??q；（3）?p??q；（4）p?q； （5）p?q；（6）(p?q)?(?p??q)；（7）p?q。

3. 令原子命题p：你的车速超过每小时120公里，q：你接到一张超速罚款单，用p、q和逻辑联接词符号化下列复合命题。

（1）你的车速没有超过每小时120公里。（2）你的车速超过了每小时120公里，但没接到超速罚款单。 （3）你的车速若超过了每小时120公里，将接到一张超速罚款单。 （4）你的车速不超过每小时120公里，就不会接到超速罚款单。

（5）你接到一张超速罚款单，但你的车速没超过每小时120公里。 （6）只要你接到一张超速罚款单，你的车速就肯定超过了每小时120公里。 解 （1）?p；（2）p??q；（3）p?q；（4）?p??q； （5）q??p；（6）q?p。

4. 判断下列各蕴涵式是真是假。

（2）若1?1?2，则2?2?5。 f （4）若1?1?3，则2?2?5。 t （6）若猪会飞，那么2?2?5。 t （8）若1?1?2，猪就会飞。 f

（1）若1?1?2，则2?2?4。 t （3）若1?1?3，则2?2?4。 t （5）若猪会飞，那么2?2?4。 t （7）若1?1?3，猪就会飞。 t