离散数学本科形考任务1答案

《离散数学》复习资料 2014年12月

一、单项选择题（每小题3分，本题共15分）

1．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( A )．

A． A?B，且A?B B．B?A，且A?B C．A?B，且A?B D．A?B，且A?B 2．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( D )．

图一 A．（a）是强连通的 B．（b）是强连通的

C．（c）是强连通的 D．（d）是强连通的 3．设图G的邻接矩阵为

?01100??10011???

?10000???01001????01010??则G的边数为( B )．

A．6 B．5 C．4 D．3

4．无向简单图G是棵树，当且仅当( A )．

A．G连通且边数比结点数少1 B．G连通且结点数比边数少1 C．G的边数比结点数少1 D．G中没有回路． 5．下列公式 ( C

《离散数学》复习资料 2014年12月

一、单项选择题（每小题3分，本题共15分）

1．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( A )．

A． A?B，且A?B B．B?A，且A?B C．A?B，且A?B D．A?B，且A?B 2．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( D )．

图一 A．（a）是强连通的 B．（b）是强连通的

C．（c）是强连通的 D．（d）是强连通的 3．设图G的邻接矩阵为

?01100??10011???

?10000???01001????01010??则G的边数为( B )．

A．6 B．5 C．4 D．3

4．无向简单图G是棵树，当且仅当( A )．

A．G连通且边数比结点数少1 B．G连通且结点数比边数少1 C．G的边数比结点数少1 D．G中没有回路． 5．下列公式 ( C

试卷代号：1009

中央广播电视大学2009—2010学年度第二学期“开放本科”期末考试(半开卷)

离散数学(本) 试题

2010年7月

一、单项选择题(每小题3分，本题共15分)

1．若集合A＝{1，{2}，{1，2}}，则下列表述正确的是( )．

A．2A

B．{l}A

C. 1A

D．2A

2．已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为( )．

A．6

B．4

C. 3

D．5

3．设无向图G的邻接矩阵为，则G的边数为( )．

A．1 B．7

C． 6 D． 14

4．设集合A＝{a}，则A的幂集为( )．

A． {{a}}

B． {a，{a}}

C. {，{a}}

D． {，a}

5．下列公式中( )为永真式．

二、填空题(每小题3分，本题共15分)

6．命题公式的真值是 ．

7．若无向树丁有5个结点，则T的边数为 ．

8．设正则m叉树的树叶数为t，分支数为i，则(m-1)i＝ ．

9．设集合A＝{1，2}上的关系只＝{<1，1>，<1，2>}，则在R中仅需加一个元素 ，就可使新得到的关系为对称的．

10．中的自由变元有——·

三、逻辑公式

★ 形成性考核作业 ★

离散数学作业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．

一、填空题

1、对于所有的真值指派，命题公式_______________，这种命题叫做重言式。

对于所有的真值指派，命题公式_______________，这种命题叫做矛盾式。 2、具有_______________________的______________________是命题。

3、一个命题标识符如表示确定的命题，就称为_____________，如果命题标识符只表示任意命题的位置标志，就称为______________。 4、设有命题“如果天不下雨，我就去游泳”。

则其逆换式为__________________________；

反换式为______________________________； 逆反式为______________________________。 5、已知原命题为：“如果天不下雨，我就去。”则该命题的

反换式是___________________________________________，

逆换式是___________________________________________， 逆反式是___________________________________________。 其中意义相同的

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、图的构成要素是（

离散数学作业1_集合与关系

1. 设A、B、C为任意三个集合，判断下列命题的真与假。如命题为真，则证明之；否则，举反例说明。 （1）若A?C=B?C，则A=B(假命题) （2）若A?C=B?C ，则A=B(假命题) （3）若A?C=B?C 且A?C=B?C ，则A=B (真命题,参考ppt 1.2节例8) 2.证明A-B=A∩~B.

证明思路：任取x∈A-B?……? x∈A∩~B

证明：任取x∈A-B?x∈A且x/∈B（根据相对补的定义）

? x∈A且x∈~B(根据绝对补的定义) ? x∈A∩~B

3. 设A={1，2，3，4，5，6},下面各式定义的R都是A上的二元关系。试分别以序偶、关系矩阵、关系图三种形式分别写出R。 (1) R={|x整除y}；(2) R={|x是y的倍数}； (3) R={|(x-y)2?A}；(4) R={|x/ y是素数}。 解： (1)

R={<1,1>,<1,2>,<1,3>,<1,4>,<1,5>,<1,6>,<2,2>,<2,4.>,<2,6>,<3,3>,<3,6>,<4,4>,<5,5>,<6,6>} (2)

R={<1,1>,<2,1>,<2,2>,<3,1>,<3,3>,<4,1>,<4,2>,<4,4>,<5,1>,

>,<6,1>,<6,2>,<6,3>,<6,6>} (3)

R={<1,2>,<1,3>,<2,1>,<2,3>,<2,4>,<3,2>,<3,4>,<3,1>,<3,5>,<4,3>,<4,5>,<4,2>,<4,6>,<5,4>,<5,6>,<5,3>,<6,5>,<6,4>}

(4) 质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。

100以内的质数有2，3，5，7，11，13

1 / 6

一、 命题逻辑部分

1．计算真值表、并由此写出主析取与主合取范式(一个命题公式的主范式具有唯一的表示形式，这样可以精减一个推理系统，去掉多余的等价的前提。其唯一性借助于小项或大项的设计，一个公式中所用到的小项或大项个数与其真值表中所对应的1或0的个数相对应，不能多也不能少)。注意：真值表与公式有什么区别？

2．设 A 、B 是两个命题公式，证明：

a) A B 当且仅当A B 是永真式。b) A B 的充要条件是A B 且B A 。

等价与蕴涵是对两个公式进行比较的概念，性质b)说明两者之间的关系，相对而言蕴涵比等价更重要。与上面两个性质相关联的一个等价公式是：A B A →B ∧B →A.3．证明 P →(Q →R )?Q →(P →R )? ┐R →(Q → ┐P ) 4．证明从前提P →Q ，┐(Q ∨R)可演绎出┐P .

5．证明R →S 可从前提P →(Q →S)，┐R ∨P 和Q 推出。 ├ 6、使用推理规则或归结推理，论证推理形式 1) P →Q, R →?Q ,R ∨S, S →?Q ├?P

2)?P ?Q, S →?Q, ?R, R ∨S ├ P

二、 谓词逻辑

1、 写出谓词的含义、一个谓词公式的解释应包含什么