离散数学1-3章答案

离散数学试卷1（参考答案）

一、 选择题

1、设A?{{1,2,3},{4,5},{6,7,8}}，下列选项正确的是：（3）

（1）1?A （2）{1,2,3}?A （3）{{4,5}}?A （4）??A 2、对任意集合A,B,C，下述论断正确的是：（1）

（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 3、假设A?{a,b,c}上的关系如下，具有传递性的关系是：（4） （1）{?a,c??c,a??a,a??a,b??b,a?} （2）{?a,c??c,a??a,a?} （3）{?a,c??c,a?} （4）{?a,c?}

4、非空集合A上的空关系R不具备下列哪个性质：（1）

（1）自反性 （2）反自反性 （3） 对称性 （4）传递性 5、假设A?{a,b,c}，B?{1,2}，令：f:A?B，则不同的函数个数为：（2） （1）2+3个 （2）2个 （3）2?3个 （4）3个 6、假设A?{a,b,c}，B?{1,2}，下列哪个关系是A到B的函数：（3）

P20

1.用枚举法写出下列集合。 2大于5小于13的所有偶数。 ○A={6,8,10,12} 520的所有因数 ○

A={1,2,4,5,10,20} 6小于20的6的正倍数 ○

A={6,12,18}

2.用描述法写出下列集合 3能被5整除的整数集合 ○A{5x|x是整数}

4平面直角坐标系中单位圆内的点集 ○

A{|x2+y2≤1} 4.求下列集合的基数 1 9 ○3 1 ○7 3 ○8 2 ○10 1 ○

6.求下列集合的幂集 6{1，{2}} ○

解：{空集，{1}，{{2}}，{1，{2}}} 7 解：{空集，{空集}，{a}，{空集，a}} ○

9 解：{空集，{{1，2}}，{{2}}，{{1，2}，{2}}} ○

15.设全集U={1，2，3,4,5}，集合A={1，4}，B={1，2，5}， C={2，4}，确定下列集合。 2 {1，3,5} ○

3 {1，4,} ○

8 {5} ○

9 {空集，{1}，{2}，{4}，{1，4}，{2，4}} ○

18.对任意集合A，B和C，证明下列各式 2（A-(BUC)）=((A-B)-C) ○

证：（A-(BUC)）=A∩~(BUC)=A∩(~B∩~C) ((

离散数学练习题

第一章

一．填空

1.公式(p??q)?(?p?q)的成真赋值为 01；10

2.设p, r为真命题，q, s 为假命题，则复合命题(p?q)?(?r?s)的真值为 0 3.公式?(p?q)与(p??q)?(p?q)共同的成真赋值为 01；10

4.设A为任意的公式，B为重言式，则A?B的类型为 重言式

5．设p, q均为命题，在 不能同时为真 条件下，p与q的排斥也可以写成p与q的相容或。

二．将下列命题符合化 1.

7不是无理数是不对的。

7是无理数； 或p，其中p:

7是无理数。

解：?(?p)，其中p:

2.小刘既不怕吃苦，又很爱钻研。

解：?p?q,其中p: 小刘怕吃苦，q：小刘很爱钻研

3.只有不怕困难，才能战胜困难。

解：q??p，其中p: 怕困难，q: 战胜困难

或p??q，其中p: 怕困难， q: 战胜困难

4.只要别人有困难，老王就帮助别人，除非困难解决了。

解：?r?(p?q)，其中p: 别人有困难，q:老王帮助别人 ，r: 困难解决了 或：(?r?p)?q，其中p:别人有困难，q: 老王帮助别人，r: 困难解决了

5.整数n是整数当且仅当n能被2整除。

解：p?q，其中p:

★ 形成性考核作业 ★

离散数学作业5

姓 名： 学 号： 得 分： 教师签名： 离散数学图论部分形成性考核书面作业

本课程形成性考核书面作业共3次，内容主要分别是图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。

要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。

一、单项选择题

?0?0?1．设图G的邻接矩阵为?1??0??00001110000010010?1??0?，则G的边数为( D )． ?1?0??A．5 B．6 C．3 D．4 2．设图G＝，则下列结论成立的是 ( C )． A．deg(V)=2?E? B．

习题9

1. 设G是一个(n，m)简单图。证明：，等号成立当且仅当G是完全图。

证明：（1）先证结论：

因为G是简单图，所以G的结点度上限 max(d(v)) ≤ n-1, G图的总点度上限为 max(Σ(d(v)) ≤ n﹒max(d(v)) ≤ n(n-1) 。根据握手定理，G图边的上限为 max(m) ≤ n(n-1)/2,所以。 （2） =〉G是完全图 因为G具有上限边数，假设有结点的点度小于n-1,那么G的总度数就小于上限值，边数就小于上限值，与条件矛盾。所以，G的每个结点的点度都为n-1，G为完全图。 G是完全图 =〉 因为G是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G的边数 。■

2. 设G是一个（n，n+1）的无向图，证明G中存在顶点u，d（u）≥3。

证明：反证法，假设,则G的总点度上限为max(Σ(d(u)) ≤2 n，根据握手定理，图边的上限为max(m) ≤ 2n/2=n。与题设m = n+1，矛盾。因此，G中存在顶点u，d（u）≥3。■

3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）； （2）

第1章 习题解答

习题1.1

1. 下列句子中，哪些是命题？哪些不是命题？如果是命题，指出它的真值。 ⑴ 中国有四大发明。 ⑵ 计算机有空吗? ⑶ 不存在最大素数。 ⑷ 21+3＜5。

⑸ 老王是山东人或河北人。 ⑹ 2与3都是偶数。 ⑺ 小李在宿舍里。

⑻ 这朵玫瑰花多美丽呀! ⑼ 请勿随地吐痰!

⑽ 圆的面积等于半径的平方乘以?。 ⑾ 只有6是偶数，3才能是2的倍数。 ⑿ 雪是黑色的当且仅当太阳从东方升起。 ⒀如果天下大雨，他就乘班车上班。

解：⑴⑶⑷⑸⑹⑺⑽⑾⑿⒀是命题，其中⑴⑶⑽⑾是真命题，⑷⑹⑿是假命题，⑸⑺⒀的真值目前无法确定；⑵⑻⑼不是命题。

2. 将下列复合命题分成若干原子命题。 ⑴ 李辛与李末是兄弟。

⑵ 因为天气冷，所以我穿了羽绒服。 ⑶ 天正在下雨或湿度很高。 ⑷ 刘英与李进上山。

⑸ 王强与刘威都学过法语。

⑹ 如果你不看电影，那么我也不看电影。 ⑺我既不看电视也不外出，我在睡觉。 ⑻ 除非天下大雨，否则他不乘班车上班。 解：⑴本命题为原子命题；

⑵ p：天气冷；q：我穿羽绒服； ⑶ p：天在下雨；q：湿度很高； ⑷ p：刘英上山；q：李进上山；

⑸ p：王强学过法语；q：刘威学过法语； ⑹ p：你看电影；q：我看

第10章 图

第10章习题答案

1.解 (1)设G有m条边，由握手定理得2m＝?d(v)＝2＋2＋3＋3＋4＝14，所以G的边数7条。

v?V(2)由于这两个序列中有奇数个是奇数，由握手定理的推论知，它们都不能成为图的度数列。 (3) 由握手定理得?d(v)＝2m＝24，度数为3的结点有6个占去18度，还有6度由其它结点占有，

v?V其余结点的度数可为0、1、2，当均为2时所用结点数最少，所以应由3个结点占有这6度，即图G中至多有9个结点。

2.证明 设v1、v2、?、vn表示任给的n个人，以v1、v2、?、vn为结点，当且仅当两人为朋友时其对应的结点之间连一条边，这样得到一个简单图G。由握手定理知

?d(v)＝3n必为偶数，从而n必为偶数。

kk?1n3. 解 由于非负整数列d＝(d1，d2，…，dn)是可图化的当且仅当?di≡0(mod 2)，所以(1)、(2)、

i?1n(3)、(5)能构成无向图的度数列。

(1)、(2)、(3)是可简单图化的。其对应的无向简单图如图所示。

(5)是不可简单图化的。若不然，存在无向图G以为1，3，3，3度数列，不妨设G中结点为v1、v2、

v3、v4，且d(v1)＝1，d(v2)＝d(v3)＝d

2006年下半年《离散数学》（闭卷）70学时

离散数学（A卷）

闭卷、70学时

一、 填空选择题 (每空1分，共26分)

1、给定命题公式如下：p?(q??r)。该公式的成真赋值为A,成假赋值为B,公式的类型为C。

供选择的答案

A：①无；②全体赋值；

③010，100，101，111；④010，100，101，110，111。

B：①无；②全体赋值；③000，001，011；④000，010，110。 C：①重言式；②矛盾式；③可满足式。

（?x)(P(y)?Q(x,y))?(?y)R(x,y)中，?x的辖域是 P(z)→Q(x,z) ， 2、在公式

?y的辖域是 R(x,z) 。

3、设Z+={x∣x∈Z∧X>0},π1, π2,π3是Z+的3个划分。

π1={{x}∣x∈Z+},π2={S1,S2},S1为素数集,S2=Z+-S1.π3＝{Z+}, (1)3个划分块中最多的是A,最少的是B. +++

(2)划分π1对应的是Z上的C,π2对应的是Z上的D,π3对应的是Z上的E. 供选择的答案

A:( ①),B:( ③ ) ①π1, ②π2,③π3. C:( ⑧)

第一章

1. 假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A

和B表示ECNU不必学习离散数学的二年级的学生的集合。

试求： P(?) P(P(?)) P(P(P(?)))

2. (1) (2) (3)

3. 在1?200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？

能被5整除的有40个， 能被15整除的有13个，

∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。

第三章

1. (1) (2) (3) (4) (5)

下列语句是命题吗？ 2是正数吗？ x2+x+1=0。 我要上学。

明年2月1日下雨。

如果股票涨了，那么我就赚钱。

2. 请用自然语言表达命题(p??r)?(q??r)，其中p、q、r为如下命题： p：你得流感了

q：你错过了最后的考试 r：这门课你通过了

3. 通过真值表求p?(p?(q?p))的主析取范式和主合取范式。

4. 给出p?(q?s),q,p??r?r?s的形式证明。

第四章

1. 将?x(C(x)??y(C(y)?F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同

班同学，个体域是学校全体

离散数学期末试题(B卷)

一、单项选择题（每小题1分，共15分。四选一）

1、设Φ是一个空集，则下列之一哪一个不成立（）。 ①、Φ∈Φ

②、Φ?Φ

③、Φ∈{Φ}

④、Φ?{Φ}

2、如果命题公式G=P∧Q，则下列之一哪一个成立（）。 ①、G=?(P→Q)

②、G=?(P→?Q)

③、G=?(?P→Q)

④、G=?(?P→?Q)

3、设X、Y是两个集合|X|＝n，|Y|＝m，则从X到Y可产生（）个二元关系。 ①、n

m

②、m

n

③、m×n ④、2

m×n

4、在有补分配格中，?a,b∈L，a≤b当切仅当下列（）成立。 ①、a?b＝b

②、a?b＝a

③、a＇?b＝0

④、a＇?b＝1

5、若是一个群，则运算“*”一定满足（）。 ①、交换律

②、消去律

③、幂等律

④、分配律

6、量词的约束范围称为量词的（）。 ①、定义域

②、个体域

③、辖域

④、值域

7、下列公式中，（）是析取范式。 ①、?(P∧Q)

②、?(P∨Q)

③、(P∨Q)

④、(P∧Q)

8、设G是一个12阶循环群，则该群一定有（）个不变子群。 ①、2

②、4

③、6

④、8

9、图的构成要素是（