离散数学实验报告

离散数学实验报告（共10篇）

离散数学实验报告 篇1

离散数学的实验教学探讨

离散数学是计算机专业的一门很重要的`专业基础课,该课程概念多,理论性强,高度抽象.传统教学中过于注重理论而忽略实验,学生在学习过程中往往态度消极.从教材中选取适合实验教学的重要理论的算法描述、课程实验体系建设、实际应用等方面入手,强化实验教学,培养学生学习兴趣,提高学生的应用能力.

作 者：沈来信 杨帆 Shen Laixin Yang Fan 作者单位：黄山学院信息工程学院,安徽,黄山,245021刊 名：黄山学院学报英文刊名：JOURNAL OF HUANGSHAN UNIVERSITY年，卷(期)：11(3)分类号：G642.423关键词：离散数学 实验教学 课程实验 应用能力

离散数学考试范围 篇2

带全称量词和存在量词的命题逻辑推理的构造和证明 第二部分

集合基本运算，文氏图 有序对的基本知识，笛卡儿积，特征函数

函数的性质（单射，满射，双射）

集合的基本概念（交集，并集，幂集，定义域，值域）

给出关系图，画出r(R)，s(R)，t(R)等价关系及等价划分 集合相等证明

从A到B的函数的性质

关系的性质（自反，对称，传递）偏序关系和哈斯图

A卷

1、选择10题（2*10=20分）

2、填空8题（1*15=15分）

3、综合题（6题，39分）（1）前束范式

（2）偏序关系和哈斯图（3）文氏图（4）关系的闭包

（5）用真值表判断公式的成真赋值（6）量词消去

4、证明题（3题，共26分）自然推理系统证明（第三章）集合相等证明

命题逻辑推理证明（第五章）B卷

1、填空10题（2*10=20分）

2、选择10题（1*10=10分）

3、综合题（6题，44分）（1）主析取范式判断公式类型（2）量词消去，求公式真值（3）集合计算（4）量词消去（5）前束范式

（6）偏序关系和哈斯图

4、推理填空题（8分）

离散数学 篇3

第一部分 集合论

第一章集合的基本概念和运算

1-1 设集合 A ={1，{2}，a，4，3}，下面命题为真是[ B ]

A．2 ∈A；B．1 ∈ A；C．5 ∈A；D．{2}  A。

1-2 A,B,C 为任意集合，则他们的共同子集是[ D ]

A．C；B．A；C．B；D．Ø。

1-3 设 S = {N，Z，Q，R}，判断下列命题是否成立 ？

（1）N  Q，Q ∈S，则 N  S［不成立］

（2）-1 ∈Z，Z ∈S，则-1 ∈S［不成立］

1-4 设集合 A ={3，4}，B = {4，3} ∩ Ø，C = {4，3} ∩{ Ø }，D ={ 3，4，Ø }，2E = {x│x ∈R 并且 x-7x + 12 = 0}，F = { 4，Ø，3，3}，试问哪两个集合之间可用等号表示 ？

答：A = E；B = C；D = F

1-5 用列元法表示下列集合（1）A = { x│x ∈N 且 x2 ≤ 9 }

（2）A = { x│x ∈N 且 3－x 〈 3 }

答：（1）A = { 0，1，2，3 }；

（2）A = { 1，2，3，4，……} = Z+；

第二章二元关系

2-1 给定 X =（3, 2，1），R 是 X 上的二元关系，其表达式如下：

R = {〈x，y〉x，y ∈X 且 x≤ y }

求：(1)domR =?;(2)ranR =?;(3)R 的性质。

答：R = {<2，3>，<1,2>，<1,3>}；

DomR={R中所有有序对的x}={2,1,1}={2,1};

RanR={R中所有有序对的y}={3,2,3}={3,2}；

R 的性质:反自反,反对称,传递性质.2-2 设 R 是正整数集合上的关系，由方程 x + 3y = 12 决定，即

R = {〈x，y〉│x，y∈Z+ 且 x + 3y= 12}，试求：

（1）R 的列元表达式；（2）给出 dom（R。R）。

答：根据方程式有：y=4-x/3，x 只能取 3，6,9。

（1）R = {〈3，3〉,〈6，2〉,〈9，1〉}；

至于(2),望大家认真完成合成运算 R。R={<3,3>}.然后,给出 R。R 的定义域,即

（2）dom（R。R）= {3}。

2-3 判断下列映射 f 是否是 A 到 B 的函数；并对其中的 f：A→B 指出他的性质，即

是否单射、满射和双射，并说明为什么。

（1）A = {1，2，3}，B = {4，5}，f = {〈1，4〉〈2，4〉〈3，5〉}。

（2）A = {1，2，3} = B，f = {〈1，1〉〈2，2〉〈3，3〉}。

（3）A = B = R，f=x。

（4）A = B = N，f=x2。

（5）A = B = N，f = x + 1。

答：（1）是 A 到 B 的函数，是满射而不是单射；

（2）是双射；

（3）是双射；

（4）是单射，而不是满射；

（5）是单射而不是满射。

2-4 设 A ={1，2，3，4}，A 上的二元关系

R ={〈x，y〉︱（x-y）能被3整除}，则自然映射 g：A→A/R使 g(1)=[C]

A．｛1,2｝；B．｛1,3｝；C．｛1,4｝；D．｛1｝。

2-5 设 A ={1，2，3}，则商集A/IA =[D]

A．｛3｝；B．｛2｝；C．｛1｝；D．｛｛1｝，｛2｝，｛3｝｝。

2-6．设ｆ(x)＝x+1，ｇ(x)＝x-1 都是从实数集合Ｒ到Ｒ的函数，则ｆ。ｇ＝[C]

A．x+1；B．x-1；C．x；D．x2。

第三章 结构代数(群论初步)

3-1 给出集合及二元运算，阐述是否代数系统，何种代数系统 ？

（1）S1 = {1，1/4,1/3,1/2,2，3，4}，二元运算 *是普通乘法。

（2）S2 = {a1，a2，……，an}，ai ∈R，i = 1，2，……，n ；

二元运算。定义如下：对于所有 ai，aj ∈S2，都有 ai。aj = ai。

（3）S3 = {0，1}，二元运算 * 是普通乘法。

答：（1）二元运算*在S1上不封闭．所以，＂S1，*＂不能构成代数系统。

（2）由二元运算的定义不难知道。在 S2 内是封闭的，所以，〈S2。〉构成代数

系统；然后看该代数系统的类型：该代数系统只是半群。

（3）很明显，〈{0，1}，*〉构成代数系统；满足结合律，为半群；1是幺元，为独异

点；而 0 为零元；结论：仅为独异点，而不是群。

3-2 在自然数集合上，下列那种运算是可结合的［A］

A．x*y = max(x,y)；B．x*y = 2x+y ；

C．x*y = x2+y2 ；D．x*y =︱x-y︱..3-3 设 Z 为整数集合，在 Z 上定义二元运算。，对于所有 x，y ∈Z都有

x。y=x + y，试问〈Z。〉能否构成群，为什麽 ？

答：由题已知，集合Z满足封闭性；二元运算满足结合律，依此集合Z为半群；有幺元为 －5，为独异点.假设代数系统的幺元是集合中的元素 e,则一个方程来自于二元运算定义, 即e。x= e + x，一个方程来自该特殊元素的定义的性质,即e。x = x.由此而来的两个方程联立结果就有: e+x=x 成立.削去 x,e=0 的结果不是就有了吗!；每个元素都有逆.求每个元素的逆元素,也要解联方程,如同求幺元一样的道理；结论是：代数系统〈 Z。〉构成群。

第二部分图论方法

第四章 图

4-1 10 个顶点的简单图 G 中有 4 个奇度顶点，问 G 的补图中有几个偶数度顶点 ？ 答：因为10阶完全图的每个顶点的度数都是n-1=9――为奇数。这样一来，一个无向简单图 G 的某顶点的度数是奇数，其补图的相应顶点必偶数，因为一个偶数与一个奇数之和才是奇数．所以，Ｇ的补图中应有 10-4＝6 个奇数度顶点。

4-2 是非判断：无向图G中有10条边,4个3度顶点,其余顶点度数全是2,共有 8 个顶点.[是]

4-3 填空补缺：1条边的图 G 中，所有顶点的度数之和为[2]

第五章树

5-1握手定理的应用（指无向树）

（1）在一棵树中有 7 片树叶，3 个 3 度顶点，其余都是 4 度顶点，问有(有1个4度顶点)个？

（2）一棵树有两个 4 度顶点，3 个 3 度顶点，其余都是树叶，问有(9个1度顶点)片？

5-2 一棵树中有 i 个顶点的度数为 i（i=2，…k），其余顶点都是树叶(即一度顶点)，问树叶多少片？设有x片,则 x=

答：假设有 x 片树叶，根据握手定理和树的顶点与边数的关系，有关于树叶的方程，解方程得到树叶数 x = Σi（i—2）i + 2，（i = 2，3，……k）。

5-3 求最优 2 元树：用 Huffman 算法求带权为 1，2，3，5，7，8 的最优 2 元树 T。试问：（1）T 的权 W（T）？（2）树高几层 ？

答：用 Huffman 算法，以 1，2，3，5，7，8 为权，最优 2 元树 T ；然后，计算并回答所求问题：（1）T 的权 W（T）= 61；（2）树高几层：4 层树高。

5-4以下给出的符号串集合中，那些是前缀码？将结果填入[]内.B1 = {0，10，110，1111}[是]B2 = {1，01，001，000}[是]B3 = {a，b，c，aa，ac，aba，abb，abc}[非]B4 = {1，11，101，001，0011}[非]

5-5(是非判断题)11阶无向连通图G中17条边，其任一棵生成树 T 中必有6条树枝 [非]

5-6(是非判断题)二元正则树有奇数个顶点。[是]

5-7 在某次通信中 a，b，c，d，e 出现的频率分别为 5%;10%;20%;30%;35%.求传输他们的最佳前缀码。

1、最优二元树 T；2.每个字母的码字；

答：每个字母出现频率分别为：G、D、B、E、Y：14%，O：28%；(也可以不归一,某符号

出现次数即为权，如右下图).。100（近似）7.。563..4。282..2..2。..1..14141414111

1所以，得到编码如下：G（000），D（001），B（100），E（101），Y（01），O（11）。

第三部分逻辑推理理论

第六章 命题逻辑

6-1 判断下列语句是否命题，简单命题或复合命题。

（1）2月 17 号新学期开始。[真命题]

（2）离散数学很重要。[真命题]

（3）离散数学难学吗 ？[真命题]

（4）C 语言具有高级语言的简洁性和汇编语言的灵活性。[复合命题]

（5）x + 5 大于 2。[真命题]

（6）今天没有下雨，也没有太阳，是阴天。[复合命题]

6-2 将下列命题符号化.（1）2 是偶素数。

（2）小李不是不聪明，而是不好学。

（3）明天考试英语或考数学。（兼容或）

（4）你明天不去上海，就去北京。（排斥或）

答：（1）符号化为： p ∧ q。

（2）符号化为：p ∧ ﹃q。

（3）符号化为：p ∨ q。

（4）符号化为：（﹃p ∧ q）∨（p ∧ ﹃q）。

6-3分别用等值演算法,真值表法,主析取范式法,判断下列命题公式的类型.（1）﹃（p→q）∧ q；（2）（（p→q）∧ p）→q；（3）（p→q）∧ q。答：（1）0；

（2）Σ（0，1，2，3）；

（3）Σ（1，3）。

以下两题(6-4;6-5)为选择题,将正确者填入[]内.6-4 令 p：经一堑；q：长一智。命题’’只有经一堑，才能长一智’’符号化为[B]

A． p→q；B．q→p；C．p∧q；D．﹁q→﹁p

6-5 p：天气好；q：我去游玩．命题 ”如果天气好，则我去游玩” 符号化为［B］

A． p→q；B．q→p；C．p∧q；D．﹁q→p

6-6证明题:用不同方法(必须有构造证明法)判断推理结果是否正确。

如果今天下雨，则明天不上体育课。今天下雨了。所以，明天没有上体育课。答：将公式分成前提及结论。

前提：（p→﹃q），p；

结论：﹃q；

证明：（1）（p→﹃q）前提引入

（2）p前提引入

（3）（p→﹃q）∧p（1）（2）假言推理

（4）﹃q

要证明的结论与证明结果一致，所以推理正确。

第七章谓词逻辑

7-1 在谓词逻辑中用 0 元谓词将下列命题符号化

（1）这台机器不能用。

（2）如果 2 ＞ 3，则 2 ＞ 5。

答：（1）﹃F（a）。

（2）L（a，b）→ H（a，z）。

7-2 填空补缺题：设域为整数集合Ｚ，命题xy彐z（x-y=z）的真值为（0）

7-3在谓词逻辑中将下列命题符号化

（1）有的马比所有的牛跑得慢。

（2）人固有一死。

答：（1）符号化为：彐x（F（x）∧ 彐y（G（y）∧ H（x，y）））。

（2）与（1）相仿，要注意量词、联结词间的搭配：

x（F（x）→y（G（y）→ H（x，y）））。

《附录》习题符号集

Ø 空集, ∪ 并, ∩ 交,⊕ 对称差,～ 绝对补,∑ 累加或主析取范式表达式缩写 , － 普通减法, ÷ 普通除法, ㏑ 自然对数, ㏒ 对数，﹃ 非，量词 ”所有”，”每个”，∨ 析取联结词，∧ 合取联结词，彐 量词”存在”，”有的”。

离散数学复习重点 篇4

1、集合的运算以及运算律；

2、关系的三种表示方法，以及他们之间的转化；

3、常见关系的定义；

4、哈斯图的画法，以及最大最小元、极大极小元、上下界，上下确界的求法；

5、单射、满射以及双射的证明（尤其是在代数系统中）；

6、代数系统的概念以及代数系统的常用性质，能够证明具体的代数系统的运算律，找出单

位元，零元、以及逆元等；

7、环和格只要记住不同的环和格满足的运算律就好；

8、各种图和树的概念及相关的结论，比如：欧拉图的充要条件，哈密顿图的充分条件、必

要条件、充要条件等；

9、图的矩阵计算；

10、会画一些简单的树；

11、五种联结词的真值表；

12、一些要求记住的命题公式；

13、命题公式的证明；

14、命题公式的析取范式，合取范式，主析取范式和主合取范式的求法。

题型：填空题、证明题和解答题。

友情提醒：

1、周三下午一点半到三点半在逸夫楼519答疑。

2、概念、定理和公式请务必记住，可能会出填空题；

3、考试内容不会超出我们的重点；

离散数学试题+答案 篇5

一、单项选择题(本大题共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∪IA

B.R

C.R∪{〈c,a〉}

D.R∩IA 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

专注于收集各类历年试卷和答案

D.(x)(y)(A(x,y)→A(f(x,a),a))12.设B是不含变元x的公式，谓词公式(x)(A(x)→B)等价于（）A.(x)A(x)→B

B.(x)A(x)→B C.A(x)→B

D.(x)A(x)→(x)B 13.谓词公式(x)(P(x,y))→(z)Q(x,z)∧(y)R(x,y)中变元x（）A.是自由变元但不是约束变元 B.既不是自由变元又不是约束变元 C.既是自由变元又是约束变元 D.是约束变元但不是自由变元

14.若P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为（）A.P∨Q

B.P∧┐Q

C.P→┐Q

D.P∨┐Q 15.以下命题公式中，为永假式的是（）A.p→(p∨q∨r)

B.(p→┐p)→┐p C.┐(q→q)∧p

D.┐(q∨┐p)→(p∧┐p)

二、填空题(每空1分，共20分)16.在一棵根树中，仅有一个结点的入度为______，称为树根，其余结点的入度均为______。17.A={1,2,3,4}上二元关系R={〈2，4〉，〈3，3〉，〈4，2〉}，R的关系矩阵MR中m24=______,m34=______。18.设〈s,*〉是群，则那么s中除______外，不可能有别的幂等元；若〈s,*〉有零元，则|s|=______。19.设A为集合，P(A)为A的幂集，则〈P(A)，是格，若x,y∈P(A),则x,y最大下界是______，〉最小上界是______。

20.设函数f:X→Y,如果对X中的任意两个不同的x1和x2，它们的象y1和y2也不同，我们说f是______函数，如果ranf=Y，则称f是______函数。

21.设R为非空集合A上的等价关系，其等价类记为〔x〕R。x,y∈A，若〈x,y〉∈R，则 〔x〕R与〔y〕R的关系是______，而若〈x,y〉R，则〔x〕R∩〔y〕R=______。

22.使公式(x)(y)(A(x)∧B(y))(x)A(x)∧(y)B(y)成立的条件是______不含有y，______不含有x。23.设M(x):x是人，D(s):x是要死的，则命题“所有的人都是要死的”可符号化为(x)______,其中量词(x)的辖域是______。24.若H1∧H2∧„∧Hn是______，则称H1,H2,„Hn是相容的，若H1∧H2∧„∧Hn是______，则称H1,H2,„Hn是不相容的。

25.判断一个语句是否为命题，首先要看它是否为，然后再看它是否具有唯一的。

三、计算题(共30分)26.(4分)设有向图G=(V,E)如下图所示，试用邻接矩阵方法求长度为2的路的总数和回路总数。

27.(5)设A={a,b},P(A)是A的幂集，是对称差运算，可以验证

是群。设n是正整数，求({a}-1{b}{a})n{a}-n{b}n{a}n 28.(6分)设A={1,2,3,4,5},A上偏序关系

R={〈1，2〉，〈3，2〉，〈4，1〉，〈4，2〉，〈4，3〉，〈3，5〉，〈4，5〉}∪IA;

专注于收集各类历年试卷和答案

(1)作出偏序关系R的哈斯图

(2)令B={1,2,3,5}，求B的最大，最小元，极大、极小元，上界，下确界，下界，下确界。29.(6分)求┐(P→Q)(P→┐Q)的主合取范式并给出所有使命题为真的赋值。

30.(5分)设带权无向图G如下，求G的最小生成树T及T的权总和，要求写出解的过程。

31.(4分)求公式┐((x)F(x,y)→(y)G(x,y))∨(x)H(x)的前束范式。

四、证明题(共20分)32.(6分)设T是非平凡的无向树，T中度数最大的顶点有2个，它们的度数为k(k≥2),证明T中至少有2k-2片树叶。

33.(8分)设A是非空集合，F是所有从A到A的双射函数的集合，是函数复合运算。

证明：〈F, 〉是群。

34.(6分)在个体域D={a1,a2,„，an}中证明等价式：

(x)(A(x)→B(x))(x)A(x)→(x)B(x)

五、应用题(共15分)35.(9分)如果他是计算机系本科生或者是计算机系研究生，那么他一定学过DELPHI语言而且学过C++语言。只要他学过DELPHI语言或者C++语言，那么他就会编程序。因此如果他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结论。

36.(6分)一次学术会议的理事会共有20个人参加，他们之间有的相互认识但有的相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于20。问能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人?根据是什么?

参考答案

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

1.B

2.D

3.A

4.A

5.D

6.D

7.D

8.C

9.D

10.B

11.A

12.A

13.C

14.B

15.C

二、填空题 16.0 17.1

0 18.单位元

19.x∩y

x∪y 20.入射

满射

21.［x］R=［y］R

 22.A(x)

B(y)23.(M(x)→D(x))

M(x)→D(x)

专注于收集各类历年试卷和答案

24.可满足式

永假式(或矛盾式)25.陈述句

真值

三、计算题

1100101026.M=

1011001122M=21110111

121011M2ij18,ij6 M2i1i1j144

G中长度为2的路总数为18，长度为2的回路总数为6。

27.当n是偶数时，x∈P(A),xn=

当n是奇数时，x∈P(A),xn=x

于是：当n是偶数，(｛a｝-1｛b｝｛a｝)n｛a｝-n｛b｝n｛a｝n

=(｛a｝-1)n｛b｝n｛a｝n=

当n是奇数时，(｛a｝-1｛b｝｛a｝)n｛a｝-n｛b｝n｛a｝n

=｛a｝-1｛b｝｛a｝(｛a｝-1)n｛b｝n｛a｝n

=｛a｝-1｛b｝｛a｝｛a｝-1｛b｝｛a｝= 28.(1)偏序关系R的哈斯图为

(2)B的最大元：无，最小元：无；

极大元：2，5，极小元：1，3

下界：4，下确界4；

上界：无，上确界：无

29.原式(┐(P→Q)→(P→┐Q))∧((P→┐Q)→┐(P→Q))

((P→Q)∨(P→┐Q))∧(┐(P→┐Q)∨┐(P→Q))

(┐P∨Q∨┐P∨┐Q)∧(┐(┐P∨┐Q)∨(P∧┐Q))

(┐(P∧┐Q)∨(P∧┐Q))

(P∧Q)∨(P∧┐Q)

P∧(Q∨┐Q)

P∨(Q∧┐Q)

(P∨Q)∧(P∨┐Q)

命题为真的赋值是P=1,Q=0和P=1,Q=1

专注于收集各类历年试卷和答案

30.令e1=(v1,v3)，e2=(v4,v6)

e3=(v2,v5)，e4=(v3,v6)

e5=(v2,v3)，e6=(v1,v2)

e7=(v1,v4)，e8=(v4,v3)

e9=(v3,v5)，e10=(v5,v6)

令ai为ei上的权，则

a1

取a1的e1∈T,a2的e2∈T,a3的e3∈T,a4的e4∈T,a5的e5∈T,即，T的总权和=1+2+3+4+5=15 31.原式┐(x1F(x1,y)→y1G(x,y1))∨x2H(x2)

(换名)

┐x1y1(F(x1,y)→G(x,y1))∨x2H(x2)

x1y1┐(F(x1,y1)→G(x,y1))∨x2H(x2)

x1y1x2(┐(F(x1,y1)→G(x,y1))∨H(x2)

四、证明题

32.设T中有x片树叶，y个分支点。于是T中有x+y个顶点，有x+y-1 条边，由握手定理知T中所有顶点的度数之的

xy

d(vi)=2(x+y-1)。

i又树叶的度为1，任一分支点的度大于等于2

且度最大的顶点必是分支点，于是

xy

d(vi)≥x·1+2(y-2)+k+k=x+2y+2K-4 i1

从而2(x+y-1)≥x+2y+2k-4

x≥2k-2 33.从定义出发证明：由于集合A是非空的，故显然从A到A的双射函数总是存在的，如A上恒等函数，因此F非空

(1)f,g∈F,因为f和g都是A到A的双射函数，故fg也是A到A的双射函数，从而集合F关于运算是封闭的。

(2)f,g,h∈F,由函数复合运算的结合律有f(gh)=(fg)h故运算是可结合的。

(3)A上的恒等函数IA也是A到A的双射函数即IA∈F,且f∈F有IAf=fIA=f,故IA是〈F，〉中的幺元

(4)f∈F,因为f是双射函数，故其逆函数是存在的，也是A到A的双射函数，且有ff-1=f-1f=IA,因此f-1是f的逆元

由此上知〈F，〉是群

34.证明(x)(A(x)→B(x)) x(┐A(x)∨B(x))

专注于收集各类历年试卷和答案

(┐A(a1)∨B(a1))∨(┐A(a2)∨B(a2))∨„∨(┐A(an)∨B(an)))

(┐A(a1)∨A(a2)∨„∨┐A(an)∨(B(a1)∨B(a2)∨„∨(B(an))

┐(A(a1)∧A(a2)∧„∧A(an))∨(┐B(a1)∨B(a2)∨„∨(B(an))

┐(x)A(x)∨(x)B(x)(x)A(x)→(x)B(x)

五、应用题

35.令p：他是计算机系本科生

q：他是计算机系研究生

r：他学过DELPHI语言

s:他学过C++语言

t:他会编程序

前提：(p∨q)→(r∧s),(r∨s)→t

结论：p→t

证①p

P(附加前提)

②p∨q

T①I

③(p∨q)→(r∧s)

P(前提引入)

④r∧s

T②③I

⑤r

T④I

⑥r∨s

T⑤I

⑦(r∨s)→t

P(前提引入)

⑧t

T⑤⑥I 36.可以把这20个人排在圆桌旁，使得任一人认识其旁边的两个人。

根据：构造无向简单图G=,其中V={v1,v2,„，V20}是以20个人为顶点的集合，E中的边是若任两个人vi和vj相互认识则在vi与vj之间连一条边。

Vi∈V,d(vi)是与vi相互认识的人的数目，由题意知vi,vj∈V有d(vi)+d(vj)20,于是G中存在汉密尔顿回路。

离散数学习题集 篇6

数理逻辑(离散数学一分册)王捍贫 北京大学出版社 定价：15元

集合论与图论(离散数学二分册)耿素云 北京大学出版社 定价：19元

代数结构与组合数学(离散数学三分册)屈婉玲 北京大学出版社 定价：21元

离散数学习题集——数理逻辑与集合论分册 耿素云 北京大学出版社 定价：11.5元

离散数学习题集——图论分册 耿素云 北京大学出版社 定价：8元

离散数学习题集——抽象代数分册 张立昂 北京大学出版社 定价：8.8元

离散数学 左孝凌 刘永才 上海科学技术文献出版社 定价：16元

学习《离散数学》心得体会 篇7

计算机3班

120210324 罗 鸿

起先以为《离散数学》讲的是比高数更加深奥的数学问题，其实不为然。《离散数学》是计算机科学与技术专业的一门重要的专业基础课程,它在计算机科学中有着广泛的应用。离散数学，对绝大多数学生来说是一门十分困难的课程，当然也包括我在内。开始学的时候有点蒙，加上老师讲课有点口音，速度很快，课下也没及时地去复习，所以学得不是很好。

第一章学了数理逻辑，前面的几节学得还可以，可是后面几节就不行了。学习谓词时中，起初我并不知道它到底要讲些什么东西，将命题拆了几大块，又莫名奇妙将这些小块用联结词组合在一起，还对它们进行一系列的判断，越学越没想法。也许是自己的逻辑能力不是很好。

接下来学习了图论，这里所说的图并不是几何学中的图形，而是客观世界中某些具体事物间联系的一个数学抽象，用顶点代表事物，用边表示各式物间的二元关系，如果所讨论的事物之间有某种二元关系，我们就把相应的顶点练成一条边。这种由顶点及连接这些顶点的边所组成的图就是图论中所研究的图。由于它关系着客观世界的事物，所以对于解决实际问题是相当有效的。这一章概念很多，也让我也感觉很乱，这一章基本都是自学的，因为老师很快就过了，自己也是迷糊迷糊的。所以只能在课后多下功夫了。

离散数学试题答案[范文] 篇8

一、单项选择题(每小题2分，共10分)1.命题公式(PQ)Q为()

(A)矛盾式(B)可满足式(C)重言式(D)合取范式

2.设C(x): x是国家级运动员，G(x): x是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为()

(A)x(C(x)G(x))(B)x(C(x)G(x))

(C)x(C(x)G(x))(D)x(C(x)G(x))

3.设集合A={{1,2,3}, {4,5}, {6,7,8}}，则下式为真的是()

(A)1A(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){,<2,c>}(C){,}(D){<1,c>,}

5.如第5题图所示各图，其中存在哈密顿回路的图是()

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

6.设集合A={,{a}}，则A的幂集P(A7.设集合A={1,2,3,4 }, B={6,8,12}, A到B的关系R＝{x,yy2x,xA,yB},那么R1＝

8.图G如第8题图所示，那么图G的割点是－abfced第8题图

9.连通有向图D含有欧拉回路的充分必要条件是.10.设X＝{a,b,c}，R是X上的二元关系，其关系矩阵为

101，那么R的关系图为MR＝100100

三、化简解答题(每小题8分，共24分)11.简化表达式(((A(BC))A)(B(BA)))(CA).12.设代数系统(R*, )，其中R*是非0实数集，二元运算为：a,bR, ab=ab.试问是否满足交换律、结合律，并求单位元以及可逆元素的逆元.13.化简布尔表达式aab(cab).四．计算题(每小题8分，共32分)

14.求命题公式(PQ)(PQ)的真值表.15.试求谓词公式x(P(x)xQ(x,y)yR(x,y))A(x,y)中，x,x,y的辖域，试

问R(x,y)和A(x,y)中x,y是自由变元，还是约束变元？16.设R1是A1＝{1,2}到A2＝(a,b,c)的二元关系，R2是A2到A3＝{,}的二元关系，R1= {<1,a>,<1,b>,<2,c>}, R2={,}试用关系矩阵求R1R2的集合表达式.v

217图G如第17题图

求图G的最小生成树.v4v

3第17题图

五、证明题(第18题10分，第19题9分)18.证明(PQ)((QR)R)(PS))S19.设G为9个结点的无向图，每个结点的度数不是5就是6，试证明G中至少有5个度数为6的结点，或者至少有6个度数为5的结点.《计算机数学基础》离散数学试题

之五解答

一、单项选择题(每小题2分，共15分)1.B2.D3.C4.A5.C

二、填空题(每小题3分，共15分)6.{,{},{{a}},{,{a}}}

7.{<6,3>,<8,4> }8.a, f9.D中每个结点的入度＝出度.10.见第10题答案图.三、化简解答题(每小题8分，共24分)(((A(BC))A)(B(BA)))(CA)

c第10题答案图

(A(B(~BA)))(CA)（2分）

(A(AB))(CA)AC~A)

（4分）

（6分）（8分）

12.a,b,cR*, ab=ab=ba=ba，可交换；(2分)(ab)c=abc=abc=a(bc)=a(bc)=a(bc)，可结合.(4分)易见，单位元为1.(6分)

对aR*, aa1=aa1=1=a1a＝a1a，故a的逆元：a1

－

－

－

－

(8分)a

13.aab(cab)

＝aabcaab(2分)

＝aab(5分)＝(aa)(ab)ab(8分)

四、计算题(每小题8分，共32分)

表中最后一列的数中，每对1个数得2分.15.x的辖域：(P(x)xQ(x,y)yR(x,y))(2分)x的辖域：Q(x,y)(4分)y的辖域：R(x,y)(6分)R(x,y)中的x,y是约束变量，A(x,y)中的x,y是自由变量.(8分)

110

16.MR1,(2分)

001

01

(4分)MR20100

01

11001(6分)MR1R201

0010000



R1R2{1,}(8分)

v217图G的最小生成树，如第17题答案图.首先选对边(v 1, v 2)得2分，再每选对一条边得分.v4v

3第17题答案图

五、证明题(第18题10分，第19题9分，共19分)18.①QRP（2分）②RP(4分)

③Q①，②析取三段论

④PQP(7分)

⑤P③，④拒取式⑥PSP

⑦S⑤，⑥析取三段论(10分)

19.由第5章定理1(握手定理)的推论，G中度数为5的结点个数只能是0,2,4,6,8五种情况；(3分)此时，相应的结点度数为6的结点个数分别为9，7，5，3，1个，(6分)

离散数学证明方法有哪些 篇9

反证法反证法是证明那些“存在某一个例子或性质”，“不具有某一种的性质”，“仅存在”等的题目。它的方法是首先假设出所求命题的否命题，接着根据这个否命题和已知条件进行推演，直至推出与已知条件或定理相矛盾，则认为假设是不成立的，因此，命题得证。

构造法证明“存在某一个例子或性质”的题目，我们可以用反证法，假设不存在这样的例子和性质，然后推出矛盾，也可以直接构造出这么一个例子就可以了。这就是构造法，通常这样的题目在图论中多见。值得注意的是，有一些题目其实也是本类型的题目，只不过比较隐蔽罢了，像证明两个集合等势，实际上就是证明“两个集合中存在一个双射”，我们即可以假设不存在，用反证法，也可以直接构造出这个双射。

电大离散数学证明题参考题 篇10

1．设G是一个n阶无向简单图，n是大于等于3的奇数．证明图G与它的补图G中的奇数度顶点个数相等． 证明：设GV,E，V,E．则E是由n阶无向完全图Kn的边删去E所得到的．所以对于任意结

点uV，u在G和G中的度数之和等于u在Kn中的度数．由于n是大于等于3的奇数，从而Kn的每个结点都是偶数度的（n1(2)度），于是若uV在G中是奇数度结点，则它在G中也是奇数度结点．故图G与它的补图G中的奇数度结点个数相等．

k条边才能使其成为欧拉图．

2证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k是偶数．

又根据定理4.1.1的推论，图G是欧拉图的充分必要条件是图G不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图． k故最少要加条边到图G才能使其成为欧拉图． 2

五、证明题

1．试证明集合等式：A(BC)=(AB)(AC)．

证：若x∈A(BC)，则x∈A或x∈BC，即x∈A或x∈B且x∈A或x∈C．

即x∈AB且x∈AC，即x∈T=(AB)(AC)，所以A(BC)(AB)(AC)．

反之，若x∈(AB)(AC)，则x∈AB且x∈AC，即x∈A或x∈B且x∈A或x∈C，即x∈A或x∈BC，即x∈A(BC)，所以(AB)(AC) A(BC)．

因此．A(BC)=(AB)(AC)．

2．对任意三个集合A, B和C，试证明：若AB = AC，且A，则B = C．

证明：设xA，yB，则AB，因为AB = AC，故 AC，则有yC，所以B C．

设xA，zC，则 AC，因为AB = AC，故AB，则有zB，所以CB．

故得B = C．

3、设A，B是任意集合，试证明：若AA=BB，则A=B．

许多同学不会做，是不应该的．我们看一看

证明：设xA，则AA，因为AA=BB，故BB，则有xB，所以AB．

设xB，则BB，因为AA=BB，故AA，则有xA，所以BA．

故得A=B．

2．设连通图G有k个奇数度的结点，证明在图G中至少要添加

1．试证明命题公式(P(QR))PQ与（PQ）等价．

证：(P(QR))PQ(P(QR))PQ

((PQR)P)Q

PQ（吸收律）

(PQ)（摩根律）

2．试证明(x)(P(x)R(x))(x)P(x)(x)R(x)．

分析：前提：(x)(P(x)R(x))，结论：(x)P(x)(x)R(x)．

证明(1)(x)(P(x)R(x))P

(2)P(a)R(a)ES(1)(存在指定规则)

(3)P(a)T(2)（化简）

(4)(x)P(x)EG(3)(存在推广规则)

(5)R(a)T(2)（化简）

(6)(x)R(x)EG(5)(存在推广规则)

(7)(x)P(x)(x)R(x)T(4)(6)（合取引入）

2．设集合A={1,2,3,4}，B={2, 4, 6, 8}，判断下列关系f：A→B是否构成函数，并说明理由．

(1)f={<1, 4>,<2, 2,>,<4, 6>,<1, 8>}；(2)f={<1, 6>,<3, 4>,<2, 2>}；

(3)f={<1, 8>,<2, 6>,<3, 4>,<4, 2,>}．

解：(1)f不能构成函数．

因为A中的元素3在f中没有出现．

(2)f不能构成函数．

因为A中的元素4在f中没有出现．

(3)f可以构成函数．

因为f的定义域就是A，且A中的每一个元素都有B中的唯一一个元素与其对应，满足函数定义的条件．

三、公式翻译题

1．请将语句“今天是天晴”翻译成命题公式．

解：设P：今天是天晴；

则命题公式为： P．

问：“今天不是天晴”的命题公式是什么？

2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式．

解：设P：小王去旅游，Q：小李去旅游，则命题公式为：PQ．

注：语句中包含“也”、“且”、“但”等连接词，命题公式要用合取“”．

3．请将语句“他去旅游，仅当他有时间．”翻译成命题公式．

解：设P：他去旅游，Q：他有时间，则命题公式为：PQ．

注意：命题公式的翻译还要注意“不可兼或”的表示．

例如，教材第164页的例6 “T2次列车5点或6点钟开．”怎么翻译成命题公式？这里的“或”为不可兼或．

4．请将语句“所有人都努力工作．”翻译成谓词公式．

解：设P(x)：x是人，Q(x)：x努力工作．