离散数学每一章练习题

离散数学每一章练习题（共6篇）

离散数学每一章练习题 篇1

第1章

命题逻辑 1.1 命题符号化及联结词

命题: 判断结果惟一的陈述句

命题的真值: 判断的结果

真值的取值: 真与假 真命题: 真值为真的命题 假命题: 真值为假的命题

注意: 感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。

简单命题(原子命题)：简单陈述句构成的命题

复合命题：由简单命题与联结词按一定规则复合而成的命题

简单命题符号化

用小写英文字母 p, q, r, … ,pi,qi,ri(i≥1）表示 简单命题

用“1”表示真，用“0”表示假

例如，令 p：

是有理数，则 p 的真值为 0 q：2 + 5 = 7，则 q 的真值为 1

联结词与复合命题 1.否定式与否定联结词“”

定义 设p为命题，复合命题 “非p”（或 “p的否定”）称

为p的否定式，记作p.符号称作否定联结词，并规定p 为真当且仅当p为假.2.合取式与合取联结词“∧”

定义 设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作p∧q.∧称作合取联结词，并规定 p∧q为真当且仅当p与q同时为真

注意：描述合取式的灵活性与多样性

分清简单命题与复合命题

例 将下列命题符号化.(1)王晓既用功又聪明.(2)王晓不仅聪明，而且用功.(3)王晓虽然聪明，但不用功.(4)张辉与王丽都是三好生.(5)张辉与王丽是同学.解 令

p：王晓用功，q：王晓聪明，则

(1)p∧q

(2)p∧q

(3)p∧q.令 r : 张辉是三好学生，s :王丽是三好学生

(4)r∧s.(5)令 t : 张辉与王丽是同学，t 是简单命题.说明:

(1)~(4)说明描述合取式的灵活性与多样性.(5)中“与”联结的是两个名词，整个句子是一个简单命题.3.析取式与析取联结词“∨”

定义 设 p,q为二命题，复合命题“p或q”称作p与q的析取式，记作p∨q.∨称作析取联结词，并规定p∨q为假当且仅当p与q同时为假.例

将下列命题符号化

(1)2或4是素数.(2)2或3是素数.(3)4或6是素数.(4)小元元只能拿一个苹果或一个梨.(5)王晓红生于1975年或1976年.解 令 p:2是素数, q:3是素数, r:4是素数, s:6是素数，则(1),(2),(3)均为相容或.分别符号化为: p∨r , p∨q, r∨s，它们的真值分别为 1, 1, 0.而(4),(5)为排斥或.令 t :小元元拿一个苹果，u:小元元拿一个梨，则(4)符号化为

(t∧u)∨(t∧u).令v :王晓红生于1975年,w:王晓红生于1976年,则(5)既可符号化为(v∧w)∨(v∧w), 又可符号化为 v∨w , 为什么? 4.蕴涵式与蕴涵联结词“” 定义 设 p,q为二命题，复合命题 “如果p,则q” 称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件.称作蕴涵联结词，并规定，pq为假当且仅当 p 为真 q 为假.pq 的逻辑关系：q 为 p 的必要条件

“如果 p，则 q ” 的不同表述法很多：

若 p，就 q

只要 p，就 q

p 仅当 q

只有 q 才 p

除非 q, 才 p 或

除非 q, 否则非 p.当 p 为假时，pq 为真

常出现的错误：不分充分与必要条件

5.等价式与等价联结词“”

定义 设p，q为二命题，复合命题 “p当且仅当q”称作p与q的等价式，记作pq.称作等价联结词.并规定pq为真当且仅当p与q同时为真或同时为假.说明:

(1)pq 的逻辑关系:p与q互为充分必要条件

(2)pq为真当且仅当p与q同真或同假

联结词优先级:(),, , , , 

同级按从左到右的顺序进行

以上给出了5个联结词：, , , , ，组成 一个联结词集合{, , , , }，联结词的优先顺序为：, , , , ;如果出 现的联结词同级，又无括号时，则按从左到右 的顺序运算;若遇有括号时，应该先进行括号 中的运算.注意: 本书中使用的 括号全为园括号. 命题常项

 命题变项

1.2 命题公式及分类

 命题变项与合式公式  命题常项：简单命题

 命题变项：真值不确定的陈述句

 定义 合式公式(命题公式, 公式)递归定义如下： (1)单个命题常项或变项 p,q,r,…,pi ,qi ,ri ,…,0,1 

是合式公式

(2)若A是合式公式，则(A)也是合式公式

(3)若A, B是合式公式，则(AB),(AB),(AB),(AB)也是合式公式 (4)只有有限次地应用(1)~(3)形成的符号串才是合式公式  说明: 元语言与对象语言，外层括号可以省去

合式公式的层次 定义

(1)若公式A是单个的命题变项, 则称A为0层公式.(2)称A是n+1(n≥0)层公式是指下面情况之一：

(a)A=B, B是n层公式；

(b)A=BC, 其中B,C分别为i层和j层公式，且

n=max(i, j)；

(c)A=BC, 其中B,C的层次及n同(b)；

(d)A=BC, 其中B,C的层次及n同(b)；

(e)A=BC, 其中B,C的层次及n同(b).例如

公式

p p

pq

(pq)r

((pq)r)(rs)

公式的赋值

定义 给公式A中的命题变项 p1, p2, … , pn指定

一组真值称为对A的一个赋值或解释

成真赋值: 使公式为真的赋值

成假赋值: 使公式为假的赋值

说明：

0层

1层

2层

3层

4层



赋值=12…n之间不加标点符号，i=0或1.

A中仅出现 p1, p2, …, pn，给A赋值12…n是  指 p1=1, p2=2, …, pn=n



A中仅出现 p, q, r, …, 给A赋值123…是指  p=1,q=2 , r=3 …



含n个变项的公式有2n个赋值. 真值表

真值表: 公式A在所有赋值下的取值情况列成的表

例 给出公式的真值表

A=(qp)qp 的真值表

例

B = (pq)q 的真值表

例

C=(pq)r 的真值表

命题的分类

重言式

矛盾式

可满足式

定义 设A为一个命题公式

(1)若A无成假赋值，则称A为重言式(也称永真式)

(2)若A无成真赋值，则称A为矛盾式(也称永假式)

(3)若A不是矛盾式，则称A为可满足式

注意：重言式是可满足式，但反之不真.上例中A为重言式，B为矛盾式，C为可满足式

A=(qp)qp，B =(pq)q，C=(pq)r

1.3 等值演算

 等值式 定义 若等价式AB是重言式，则称A与B等值，记作AB，并称AB是等值式

说明：定义中，A,B,均为元语言符号, A或B中 可能有哑元出现.例如，在(pq)((pq)(rr))中，r为左边 公式的哑元.用真值表可验证两个公式是否等值 请验证：p(qr)(pq)r

p(qr)

(pq)r

 基本等值式

双重否定律 : AA

等幂律：

AAA, AAA

交换律:

ABBA, ABBA

结合律:

(AB)CA(BC)

(AB)CA(BC)分配律:

A(BC)(AB)(AC)

A(BC)(AB)(AC)德·摩根律:

(AB)AB

(AB)AB

吸收律:

A(AB)A，A(AB)A

零律:

A11，A00 同一律:

A0A，A1A

排中律:

AA1 矛盾律:

AA0

 等值演算:

由已知的等值式推演出新的等值式的过程

置换规则：若AB, 则(B)(A)等值演算的基础：

(1)等值关系的性质：自反、对称、传递

(2)基本的等值式

(3)置换规则

应用举例——证明两个公式等值 例1 证明 p(qr)(pq)r

证

p(qr)

p(qr)

（蕴涵等值式，置换规则）

(pq)r

（结合律，置换规则）

(pq)r

（德摩根律，置换规则）

(pq)r

（蕴涵等值式，置换规则）说明:也可以从右边开始演算（请做一遍）

因为每一步都用置换规则，故可不写出

熟练后，基本等值式也可以不写出

应用举例——证明两个公式不等值 例2 证明: p(qr)

(pq)r

用等值演算不能直接证明两个公式不等值,证明两 个公式不等值的基本思想是找到一个赋值使一个成 真,另一个成假.方法一

真值表法（自己证）

方法二

观察赋值法.容易看出000, 010等是左边的 的成真赋值，是右边的成假赋值.方法三

用等值演算先化简两个公式，再观察.应用举例——判断公式类型

例3 用等值演算法判断下列公式的类型

(1)q(pq)解

q(pq)

 q(pq)

（蕴涵等值式）

 q(pq)

（德摩根律）

 p(qq)

（交换律，结合律）

 p0

（矛盾律）

 0

（零律）

由最后一步可知，该式为矛盾式.(2)(pq)(qp)解

(pq)(qp)

(pq)(qp)

（蕴涵等值式）

(pq)(pq)

（交换律）

 1 由最后一步可知，该式为重言式.问：最后一步为什么等值于1？

(3)((pq)(pq))r)

解

((pq)(pq))r)

(p(qq))r

（分配律）

 p1r

（排中律）

 pr

（同一律）

这不是矛盾式，也不是重言式，而是非重言式的可 满足式.如101是它的成真赋值,000是它的成假赋值.总结：A为矛盾式当且仅当A0 A为重言式当且仅当A1 说明：演算步骤不惟一,应尽量使演算短些

1.5 对偶与范式 对偶式与对偶原理

定义 在仅含有联结词, ∧,∨的命题公式A中，将 ∨换成∧, ∧换成∨，若A中含有0或1，就将0换成 1，1换成0，所得命题公式称为A的对偶式，记为A*.从定义不难看出，(A*)* 还原成A

定理 设A和A*互为对偶式，p1,p2,…,pn是出现在A和

A*中的全部命题变项，将A和A*写成n元函数形式，则(1) A(p1,p2,…,pn) A*( p1,  p2,…,  pn)

(2)A( p1,  p2,…,  pn)  A*(p1,p2,…,pn)定理（对偶原理）设A，B为两个命题公式，若A  B，则A*  B*.析取范式与合取范式

文字:命题变项及其否定的总称

简单析取式:有限个文字构成的析取式

如 p, q, pq, pqr, …

简单合取式:有限个文字构成的合取式

如 p, q, pq, pqr, …

析取范式:由有限个简单合取式组成的析取式

A1A2Ar, 其中A1,A2,,Ar是简单合取式

合取范式:由有限个简单析取式组成的合取式

A1A2Ar , 其中A1,A2,,Ar是简单析取式 范式:析取范式与合取范式的总称

公式A的析取范式: 与A等值的析取范式

公式A的合取范式: 与A等值的合取范式 说明：

单个文字既是简单析取式，又是简单合取式

pqr, pqr既是析取范式，又是合取范式(为什么?)

命题公式的范式

定理

任何命题公式都存在着与之等值的析取范式 与合取范式.求公式A的范式的步骤：

(1)消去A中的, （若存在）

(2)否定联结词的内移或消去

(3)使用分配律

对分配（析取范式）

对分配（合取范式）

公式的范式存在，但不惟一

求公式的范式举例

例 求下列公式的析取范式与合取范式

(1)A=(pq)r

解

(pq)r

(pq)r

（消去）

 pqr

（结合律）

这既是A的析取范式（由3个简单合取式组成的析 取式），又是A的合取范式（由一个简单析取式 组成的合取式）

(2)B=(pq)r

解

(pq)r

(pq)r

（消去第一个）

 (pq)r

（消去第二个）

(pq)r

（否定号内移——德摩根律）

这一步已为析取范式（两个简单合取式构成）

继续：

(pq)r

(pr)(qr)

（对分配律）

这一步得到合取范式（由两个简单析取式构成）

极小项与极大项

定义 在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项均以文字的形式在其中出现且仅出现一 次，而且第i（1in）个文字出现在左起第i位上，称这样 的简单合取式（简单析取式）为极小项（极大项）.说明：n个命题变项产生2n个极小项和2n个极大项

2n个极小项（极大项）均互不等值

用mi表示第i个极小项，其中i是该极小项成真赋值的十进制表示.用Mi表示第i个极大项，其中i是该极大项成假赋值的十进制表示, mi(Mi)称为极小项(极大项)的名称.mi与Mi的关系:

mi  Mi ，Mi  mi

主析取范式与主合取范式

主析取范式: 由极小项构成的析取范式

主合取范式: 由极大项构成的合取范式

例如，n=3, 命题变项为p, q, r时，(pqr)(pqr) m1m3 是主析取范式

(pqr)(pqr) M1M5 是主合取范式

A的主析取范式: 与A等值的主析取范式 A的主合取范式: 与A等值的主合取范式.定理

任何命题公式都存在着与之等值的主析取范 式和主合取范式, 并且是惟一的.用等值演算法求公式的主范式的步骤：

(1)先求析取范式（合取范式）

(2)将不是极小项（极大项）的简单合取式（简

单析取式）化成与之等值的若干个极小项的析

取（极大项的合取），需要利用同一律（零

律）、排中律（矛盾律）、分配律、幂等律等.(3)极小项（极大项）用名称mi（Mi）表示，并 按角标从小到大顺序排序.求公式的主范式

例 求公式 A=(pq)r的主析取范式与主合取范式.(1)求主析取范式

(pq)r

(pq)r ，（析取范式）

①

(pq)

(pq)(rr)

(pqr)(pqr)

 m6m7 ，r

(pp)(qq)r

(pqr)(pqr)(pqr)(pqr)

 m1m3m5m7

③

②, ③代入①并排序，得

(pq)r  m1m3m5 m6m7（主析取范式）

(2)求A的主合取范式

(pq)r

(pr)(qr)，（合取范式）

①

pr

 p(qq)r

(pqr)(pqr)

 M0M2, qr

(pp)qr

(pqr)(pqr)

 M0M4

②, ③代入①并排序，得

(pq)r  M0M2M4

（主合取范式）主范式的用途——与真值表相同(1)求公式的成真赋值和成假赋值

例如

(pq)r  m1m3m5 m6m7，其成真赋值为001, 011, 101, 110, 111，其余的赋值 000, 010, 100为成假赋值.类似地，由主合取范式也可立即求出成

②③

假赋值和成真赋值.(2)判断公式的类型

设A含n个命题变项，则

A为重言式A的主析取范式含2n个极小项

A的主合取范式为1.A为矛盾式 A的主析取范式为0

 A的主合取范式含2n个极大项

A为非重言式的可满足式

A的主析取范式中至少含一个且不含全部极小项

A的主合取范式中至少含一个且不含全部极大项

例 某公司要从赵、钱、孙、李、周五名新毕 业的大学生中选派一些人出国学习.选派必须 满足以下条件：

(1)若赵去，钱也去；

(2)李、周两人中至少有一人去；

(3)钱、孙两人中有一人去且仅去一人；

(4)孙、李两人同去或同不去；

(5)若周去，则赵、钱也去.试用主析取范式法分析该公司如何选派他们出 国？

解此类问题的步骤为：

① 将简单命题符号化

② 写出各复合命题

③ 写出由②中复合命题组成的合取式

④ 求③中所得公式的主析取范式

解 ① 设p：派赵去，q：派钱去，r：派孙去，s：派李去，u：派周去.②(1)(pq)

(2)(su)

(3)((qr)(qr))

(4)((rs)(rs))

(5)(u(pq))

③(1)~(5)构成的合取式为

A=(pq)(su)((qr)(qr))

((rs)(rs))(u(pq))④

A (pqrsu)(pqrsu)结论：由④可知，A的成真赋值为00110与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）.A的演算过程如下:

A (pq)((qr)(qr))(su)(u(pq))

((rs)(rs))

（交换律)B1=(pq)((qr)(qr))

((pqr)(pqr)(qr))（分配律）

B2=(su)(u(pq))

((su)(pqs)(pqu))

（分配律）

B1B2 (pqrsu)(pqrsu)

(qrsu)(pqrs)(pqru)再令 B3 =((rs)(rs))得 A  B1B2B3

(pqrsu)(pqrsu)注意：在以上演算中多次用矛盾律

要求：自己演算一遍

1.6 推理理论 推理的形式结构

推理的形式结构—问题的引入

推理举例:

(1)正项级数收敛当且仅当部分和有上界.(2)若

推理: 从前提出发推出结论的思维过程 上面(1)是正确的推理，而(2)是错误的推理.证明: 描述推理正确的过程.判断推理是否正确的方法 • 真值表法

• 等值演算法

判断推理是否正确 • 主析取范式法

• 构造证明法

证明推理正确

说明：当命题变项比较少时，用前3个方法比较方 便, 此时采用形式结构“造证明时，采用“前提:

”.而在构 , 结论: B”.推理定律与推理规则 推理定律——重言蕴涵式

构造证明——直接证明法 例 构造下面推理的证明：

若明天是星期一或星期三，我就有课.若有课，今天必备课.我今天下午没备课.所以，明天不是星期一和星期三.解 设 p：明天是星期一，q：明天是星期三，r：我有课，s：我备课 推理的形式结构为

例 构造下面推理的证明:

2是素数或合数.若2是素数，则

是无理数.若

是无理数，则4不是素数.所以，如果4是

素数，则2是合数.用附加前提证明法构造证明 解 设 p：2是素数，q：2是合数，r：

是无理数，s：4是素数 推理的形式结构

前提：p∨q, pr, rs

结论：sq 证明

① s

附加前提引入

②pr

前提引入

③rs

前提引入

④ps

②③假言三段论

⑤p

①④拒取式

⑥p∨q

前提引入

⑦q

离散数学复习题 篇2

一、填空

1、命题中的否定联接词；蕴含联接词

2、一个命题公式，若在所有赋值下取值为真，则称此公式为式；若……假，则……..为 永假 式；若至少存在一组赋值，其命题为真，则…….为可满足式。

3、有限布尔代数只能有n4、R是定义在集合上的二元关系，若R满足性、性，则称R是A上的等价关系。

5、全序集（A，≤）必是，且是

6、n阶m条边无向图G是树，当且仅当G是连通点，且m=

7、若有向树G中，有一个顶点的入度为，则称G为根树。

8、有序对具有以下性质

（1）当x不等于y时，≠

（2）=的充要条件是x=u且y=r。

9、关系的性质五。

10、图中顶点作为边的端点的称为此顶点的度数。

11、设X是格，并对交运算时可分配的，则且 格中的交运算对并运算是可分配的。

12、有向图按连通图分为三类连通图、连通图、连通图。

13、T 为一颗根树，若T的每个分支点则称T为r元正则树。

14、设A、B是集合，求A与B之间关系（属于、不属于、包含…）如果A={1}，B={1,{1,2}}，则A不属于B、A不包含B15、若R是定义在集合A上的一个二元关系，若R满足、性、可传递性则称R是偏序关系。

16、设集合A={1,2,3,4}，A上二元关系R={<1,1><1,3><2,1><3,3><3,4><4,3>}，则逆序关系R−1。

17、在有补分配格中，每个元素（的补元）都是的。

18、在无向图中，度数为奇数的顶点个数必为数。

19、若图中通路P中所有边互不相同，则称P为通路，若通路中所有顶点互不相同，则称P为 基本 通路。

二、简述题

1、偏序关系与格

2、设R是A爱上的二元关系，如果R是自反的，反对称的，传递的二元关系，则称R是A上的偏序关系或者半序关系；

2、等价关系与集合的划分

3、握手定理

4、对偶式与对偶原理

5、正规子群

6、什么是域，有限整环是不是域，为什么？

7、集合的基本运算公式（集代数公式）有哪些？

8、群论中的拉格朗日定理

9、主析取范式与主合取范式

10、鸽巢原理与计数原理

三、判断题

1、设A,B是集合，则A⨁=

2、偶数阶循环群有且只有一个2阶元素

3、设（G,∗）是n阶群，且有k阶子群，则k丨n4、有限格必是有界格

5、偶数阶群中比存在非幺元a，使得a∗a=e6、不存在含有奇数个面且每个面上有奇数条棱的多面体

7、设（A，∗）是独异点，B是A的子集，且（B，∗）是独异点，则（B，∗）一定是（A，∗）的子独异点8、3阶群同构意义下唯一

9、（N=（0），⊗）是一个群

10、素数阶群一定没有非平凡子群

四、计算题

1、求命题公式P∧（Q→R）主析取范式。

2、写出3次对称群（S3,∗）的运算表及所有正规子群。

3、在1,2,3…….100这100个自然数中，可以被2或3整除但不能被5整除的数有多少个？

4、设, A =3，P B=64，P A⋃B=256，求 B , A⋂B , A−B , A⊕B。

5、设A={a,b,c,d}，R={（a,c）,（c,b）,（b,a）,（a,d）}，求R，r R ,s R ,t(R)的关系矩阵或关系图

6、命题公式 P∧Q ∨ −P ∧(−Q)的真值表

7、写出群(N13− 0,⨂13)各元素之阶数

8、集合A={1,2,3,6,8,12}，求A 上的整除关系R并画出Hasse图

9、写出（（a−4b）c−（7b+d））+（c+8a）的前缀式和后缀式

10、求（N6,⨂6）群的自同态

五、证明题

1、证明（N13− 0，⨂13）是循环群

2、证明不存在含有奇数个面且每个面上有奇数个棱的多面体

3、设（A,∗）是代数系统，R是（A,∗）上的同余关系，(A R,∗)是其商代数，设f是A到A/R的函数，对于A中任意元素a，都有f a = a R

证明：f是（A,∗）到(A R,∗)的同态映射

4、设T是完全k元树，若分枝点为i，树叶数为t，证明：i=(t−1)/(k−1)

5、证明偶数阶群必有二阶子群，且必有奇数个二阶子群

6、R是集合A上的等价关系，证明：对任意x，y属于A在此处键入公式。

（1）若xRy，则 x R= y R

（2）若(x,y)∉R，则 x R∩ x R=∅

7、证明下列说法是等价的（1）A≤B（2）A−B=∅（3）A∩B=A（4）A∪B=B8、证明逻辑等价式P↔Q⟺ P⋀Q ⋁(−P⋀−Q)

《离散数学》图论部分习题 篇3

1.已知无向图G有12条边，6个3度顶点，其余顶点的度数均小于3，问G至少有几个顶点？并画出满足条件的一个图形.（24-3*6）/2 +6=9 2.是否存在7阶无向简单图G，其度序列为1、3、3、4、6、6、7.给出相应证明.不存在；7阶无向简单图G中最大度≤6 3.设d1、d2、…、dn为n个互不相同的正整数.证明：不存在以d1、d2、…、dn为度序列的无向简单图.Max{d1，d2，…，dn}≥n，n阶无向简单图G中最大度≤n-1 4.求下图的补图.5.1)试画一个具有5个顶点的自补图

2)是否存在具有6个顶点的自补图，试说明理由。

对于n阶图，原图与其补图同构，边数应相等，均为(n*(n-1)/2)/2，即n*(n-1)/4且为整 数，n=4k或n=4k+1，不存在6阶自补图。

6.设图G为n(n>2且为奇数)阶无向简单图，证明：G与G的补图中奇度顶点个数相等.n(n>2且为奇数)，奇度点成对出现

7.无向图G中只有2个奇度顶点u和v，u与v是否一定连通.给出说明或证明。

只有2个奇度顶点u和v，如果不连通，在u和v在2个连通分支上，每个分支上仅有一个奇度顶点，与握手引理相矛盾。

8.图G如下图所示：

1)写出上图的一个生成子图.2)δ(G)，κ(G)，λ(G).δ(G)=2，κ(G)=1，λ(G)=2.说明：δ(G)=min{ d(v)| vV } ；κ(G)=min{ |V’| |V’是图G的点割集} ； λ(G)=min{ |E’| |E’是图G的边割集} 9.在什么条件下无向完全图Kn为欧拉图？

n为奇数时

10.证明：有桥的图不是欧拉图.假设是欧拉图：桥的端点是u和v，并且图各顶点度均为偶数； 桥为割边，删除桥，图不再连通，u和v应该在2各不同的连通分支上；且u和v度数变为奇数；由于其他顶点度数均为偶数，则u和v所在的连通分支上只有一个奇度顶点，与握手引理矛盾。

11.证明：有桥的图不是哈密尔顿图.若G是K2，显然不是哈密尔顿图；

否则n≥3，则桥的两个端点u和v至少有一个不是悬挂顶点（容易证明悬挂顶点不是割点）；设u不是悬挂点，则u是割点，存在割点显然不是哈密尔顿图。

12.树T有2个4度顶点，3个3度顶点，其余顶点全为树叶，问T有几片树叶？

X+2*4+3*3=2*（2+3+x-1）

x=9 13.证明：最大度Δ（T）≥k的树T至少有k片树叶。

设有n个顶点，其中x片树叶

2*（n-1）≥1*K+（n-x-1）*2+x*1

x≥k 14.已知具有3个连通分支的平面图G有4个面，9条边，求G的阶数.n-9+4=3+1

n=9

15.给出全部互不同构的4阶简单无向图的平面图形。

离散数学函数复习题答案 篇4

一、选择题（每题3分）

1、设A{a,b,c},B{1,2,3}，则下列关系中能构成A到B函数的是（C）

A、f1{a,1,a,2,a,3}B、f2{a,1,b,1,b,2}

C、f4{a,1,b,1,c,1}D、f1{a,1,a,2,b,2,c,3}

2、设R、Z、N分别为实数集、整数集，自然数集，则下列关系中能构成函数的是（B）

A、{x,y|(x,yN)(xy10)}B、{x,y|(x,yR)(yx2)}

C、{x,y|(x,yR)(y2x)}D、{x,y|(x,yZ)(xymod3)}

3、设Z为整数集，则二元关系f{a,baZbZb2a3}（B）

A、不能构成Z上的函数B、能构成Z上的函数

C、能构成Z上的单射D、能构成Z上的满射

4、设f为自然数集N上的函数，且f(x)

10若x为奇数若x为偶数，则f（D）

A、为单射而非满B、为满射而非单射C、为双射D、既非单射又非满射

5、设f为整数集Z上的函数，且f(x)为x除以5的余数，则f（D）

A、为单射而非满B、为满射而非单射C、为双射D、既非单射又非满射

6、设R、Z分别为实数集、整数集，则下列函数为满射而非单射的是（C）

A、f:RR,C、f:RZ,A、f:RR,C、f:RR,f(x)x6B、f:RR,f(x)[x]D、f:RR,2f(x)(x6)f(x)x6x 627、设R、R、Z分别为实数集、非负实数集、正整数集，下列函数为单射而非满射的是（B）f(x)x7x1 B、f:ZR,f(x)lnx； f(x)xD、f:RR,f(x)7x

18、设Z、N、E分别为整数集，自然数集，偶数集，则下列函数是双射的为（A）

A、f : ZE , f(x)2xB、f : ZE , f(x)8x

C、f: ZZ,f(x)8D、f : NNN,f(n)n,n1

9、设X3,Y4，则从X到Y可以生成不同的单射个数为（B）．

A、12B、24C、64D、8110、设X3,Y2，则从X到Y可以生成不同的满射个数为（B）．

A、6B、8C、9D、6411、设函数f:BC，g:AB都是单射，则fg:AC（A）

A、是单射B、是满射C、是双射D、既非单射又非满射

12、设函数f:BC，g:AB都是满射，则fg:AC（B）

A、是单射B、是满射C、是双射D、既非单射又非满射

13、设函数f:BC，g:AB都是双射，则fg:AC（C）

A、是单射B、是满射C、是双射D、既非单射又非满射

14、设函数f:BC，g:AB，若fg:AC是单射，则（B）

A、f是单射B、g是单射C、f是满射D、g是满射

15、设函数f:BC，g:AB，若fg:AC是满射，则（C）

A、f是单射B、g是单射C、f是满射D、g是满射

16、设函数f:BC，g:AB，若fg:AC是双射，则（D）

A、f,g都是单射 B、f,g都是满射 C、f是单射, g是满射 D、f是满射, g是单射

二、填充题（每题4分）

1、设Xm,Yn，则从X到Y有2mn 种不同的关系，有nm 种不同的函数．

2、设Xm,Yn，且mn，则从X到Y有Anm 种不同的单射．

3、在一个有n个元素的集合上，可以有2不同的双射．

1，若x为奇数



4、设f为自然数集N上的函数，且f(x)x

若x为偶数2，n

种不同的关系，有nn 种不同的函数，有n!种,则f(0)0，f[{0}]{0}，f[{1,2,3}]{1}，f[{0,2,4,6,}]N．

5、设f,g是自然数集N上的函数,xN,f(x)x1,则fg(x)2x1，gf(x)2(x1)．

g(x)2x，三、问答计算题（每题10分）

1、设A{2，3，4}，B{2，4，7，10,12}，从A到B的关系

R{a,baA,bB,且a整除b}，试给出R的关系图和关系矩阵，并说明此

关系R及其逆关系R1是否为函数？为什么？

解：R{2,2,2,4,2,10,2,12,3,12,4,4,4,12}，则R的关系图为：

R的关系矩阵为MR



100

000

1

1 1

关系R不是A到B的函数，因为元素2，4的象不唯一

逆关系R1也不是B到A的函数 因为元素7的象不存在．

2、设Z为整数集，函数f：ZZZ，且f(x,y)xy，问f是单射还是满射？ 为什么？并求f(x,x),f(x,x)．

解：xZ, 0,xZZ，总有f(0,x)x，则f是满射；

对于1,2,2,1ZZ,，有f(1,2)3f(2,1)，而1,22,1，则f非单射；

f(x,x)2x,f(x,x)0．

3、设A{1,2}，A上所有函数的集合记为AA, “”是函数的复合运算，试给出AA上运算“”的运算表，并指出AA中是否有幺元，哪些元素有逆元？ 解：因为A2，所以A上共有224个不同函数，令A

f

1(1)1,f(2)2;

A

{f1,f2,f3,f4}，其中：

f(1)1,f(2)1;f(1)2,f(2)2;f(1)2,f4(2)1

A

f1为A中的幺元，f1和f4有逆元．

4、设R为实数集，函数f：RRRR，且f(x,y)xy,xy，问f是双射吗？为什么？并求其逆函数f



1(x,y)及ff(x,y)．

解： x1,y1,x2,y2RR，若f(x1,y1)f(x2,y2)，有x1y1,x1y1x2y2,x2y2，则x1,y1x2,y2，故f是单射；

2且f(x,y)xy,xyu,v，则f是满射，故为双射； xyxy, ； 22

ff(x,y)f(xy,xy)f(2x,2y)． f

1

u,vRR，令x

uv，y

uv，则x,yRR，(x,y)

四、证明题（每题10分）

1、设函数f：AB，g：BC，g和f的复合函数gf：AC，试证明：如果gf是双射，那么f是单射，g是满射． 证明：x1,x2A且f(x1)f(x2)B，则gf(x1)g[f(x1)]g[f(x2)]gf(x2)，因gf是单射，有x1x2，故f是单射；

cC，因gf是满射，aA，使cgfa()g[fa()]，而f(a)B，故g是满射．

注：如果gf是单射，那么f是单射；如果gf是满射，那么g是满射．

2、设f是A上的满射，且fff，证明：fIA．

证明：因f是满射，则对aA，存在a1A，使得f(a1)a，则ff(a1)f[f(a1)]f(a)，由 fff，知a1a，于是f(a)a，由a的任意性知fIA．

3、设函数f：AB，g：BA，证明：若f证明： 因f



11

g,fg

1，则gfIA,fgIB．

g,则yB,g(y)f

1

(y)xA，有g(y)x,f(x)y，于是，对yB，有fg(y)f[g(y)]f(x)yIB(y)，知fgIB；

1

又fg1，则对xA,f(x)g(x)y，有f(x)y,g(y)x，于是，对xA，有gf(x)g[f(x)]g(y)xIA(x)，知gfIA．

4、设函数f：AB，g：BA，证明：若gfIA,fgIB，则f



1g,fg

1

．

证明：因恒等函数IA是双射，则gf是A上的双射，有f是单射，g是满射； 同样，恒等函数IB是双射，则gf是B上的双射，有f是满射，g是单射； 所以，f和g都是双射函数，其反函数都存在，故有f注：设函数f：AB，g：BA，证明： f

1

1

g,fg

1

1

．

g,fg

 gfIA,fgIB．

5、设函数f：AB，g：B(A)，对于bB，g(b){xxAf(x)b}，(A)为A的幂集，证明：如果f是A到B的满射，则g是B到(A)的单射．

离散数学每一章练习题 篇5

1、设下面所有谓词的论域D={a、b、c}。试将下面命题中的量词消除，写成与之等值的命题公式。分析：本题主要是考察对全称量词、存在量词的理解，然后通过合取词、析取词把全称量词和存在量词消去。（1）xRxSx

解：R(a)R(b)R(c)S(a)S(b)S(c)（2）xPxQ(x)

解：P(a)Q(a))P(b)Q(b)P(c)Q(c)（3）x7P(x)xP(x)

解：7P(a)7P(b)7P(c))P(a)P(b)P(c)

2、指出下列命题的真值：

分析：本题主要是考察合式公式的解释的定义，已经判定给定解释下合式公式的真值。（1）xPQ(x))R(e)

其中，P:“3＞2”,Q(x):“x3”,R(x):“x＞5”,e:5，论域D={-2，3，6} 解：假。

（x为-2时不成立）（2）xP(x)Q(x)

其中，P(x):“x＞3”,Q(x):“x4”，论域D={2}。解：真。

3、在一阶逻辑中，将下列命题符号化：

分析：本题主要是考察存在量词、全称量词已经基本的连接词的运用。（1）凡有理数均可表示为分数。

解：令：P(x)： x是有理数；Q（x）:x可表示为分数。

x(P(x)Q(x))

（2）有些实数是有理数。解：P（x）：:x是实数，Q(x)：x是有理数。

xPxQ(x)

（3）并非所有实数都是有理数。解：P（x）：:x是实数，Q(x)：x是有理数。

x(P(x)Q(x))

（4）如果明天天气好，有一些学生将去公园。

解：P（x）: x去公园

S（x）: x是学生

W：明天天气好

Wx(P(x)S(x))

（5）对任意的正实数，都存在大于该实数的实数。解：P（x）: x是实数；

G（x, y）：:x大于y。

x(P(x)y(P(y)G(y,x)))（6）对任意给＞0，x0a,b，都在存在N，使当n＞N时，有

fx0fnx解：G（x，y）: x＞y, Sx:xa,b

＜

x0G,0Sx0Nn(Gn,NG(,f(x0)fn(x))))

4、指出下列公式中的自由变元和约束变元，并指出各量词的作用域。

分析：本题主要是考察自由边缘、约束变元的定义，以及量词的作用域的概念。（1）xPxQxxRxQz

解；自由变元z, 约束变元x, 第一个x的作用域是PxQx，第二个是R(x)。

（2）x(P(x)y(Q(y))(xP(x)Q(z))

中的Px 解：自由变元z，约束为元：x，y。第一个x的作用域为PxyQy



第二个x的作用域为第二个P(x)； y的作用域为Q(y)。（3）x(P(x)Q(x))yR(y)s(z)

解：自由变元：z，约束变元：x和y；

x的作用域为(P(x)Q(x))，y的作用域为R(y)

（4）x(F(x)yH(x,y))

解：无自由变元

约束变元x，y；

x的作用域：(F(x)yH(x，y))，y的作用域：H(x,y)

（5）xF(x)G(x,y)

解：自由变元：y与G(x，y)中的x，约束变元：F(x)中的x；

x的作用域：F(x)（6）xy(R(x,y)Q(x,z))xH(x,y)

解：自由变元：Z与H(x，y)中的y；

约束变元：x,y, x和y的作用范围：(R(x,y)Q(x,z)，x的作用范围：H(x,y)

5．设谓词公式x(P(x,y)Q(x,z))。判定以下改名是否正确 ：

分析：本题主要是考察改名规则的定义，以及它的适用范围。有兴趣的同学可以顺便了解一下代替规则情形。

（1）u(P(u,y)Q(x,z))

解：错误（2）u(P(u,y)Q(u,z))

解：正确（3）x(P(u,y)Q(u,z))

解：错误（4）u(P(x,y)Q(x,z))

解：错误（5）y(P(y,y)Q(y,z))

解：错误 6．设I是如下一个解释 ：

D:a，b，P(a，a):1，P(a,b):0，P(b,a):0，P(b,b):1。

试确定下列公式在I下的真值：

分析：本题主要考察合式公式在特定解释下的真值。（1）xyP(x,y)

解：真

（2）xyP(x,y)

解：假

（3）xy(P(x,y)P(y,x))解：真（4）xP(x,x)

解：真

7．判断下列公式的恒真性和恒假性

分析：本题主要是根据已知的命题公式、合式公式的基本等值式来进行推导，看该合式公式是与1等值还是与0等值。

（1）xF(x)xF(x)

解：恒真（2）xF(x)(xyG(x,y)xF(x))

解：恒真（3）xF(x)(x(F(x)yG(y))

解：恒真（4）(F(x,y)F(x,y))

解：恒假

8．设G（x）是恰含自由变元x的谓词公式，H是不含变元x的谓词公式，证明：（1）x(G(x)H)xG(x)H（2）x(G(x)H)xG(x)H 分析：本题根据量词作用域的扩张进行证明。证明（1）

x(G(x)H)x(7G(x)H)x7G(x)H7(xG(x))HxG(x)H

证明（2）

x(G(x)H)x(7G(x)H)x7G(x)H7(xG(x))HxG(x)H

9．设G（x，y）是任意一个含x，y自由出现的谓词公式，证明：（1）xyG(x，y)yxG(x，y)

分析：本题主要是根据两个合式公式等值的定义进行证明。证：设D是论域，I是G（x，y）的一个解释。

（a）若xyG(x，y)在I下的为真，则在I下，对任意的x,yD,G(x,y)即yxG(x,y)是真命题，反之亦然。

（b）若xyG(x,y)在I下为假，则在I下必存在x0D或y0D，使得G（x0, y）或G（x, y0）为假，于是，此xo或yo亦弄假yxG(x,y)，反之亦然。

（2）xyG(x，y)yxG(x，y)

分析：本题主要是根据两个合式公式等值的定义进行证明。

证：设D是论域，I是G（x, y）的一个解释。

（a）若xyG(x，y)在I下为真，则在I下存在x0D与y0D,使G（x0,y0）为真命题，于是，yxG(x,y)也是真命题，反之亦然。

（b）若xyG(x，y)在I下为假，则对任意x，yD，G（x, y）均为假，故yxG(x,y)亦为假，反之亦然。

10．将下列公式化成等价的前束范式：

分析：本题主要是根据已知的基本等值式通过消去蕴含连接词、等价连接词，依据改名规则、代替规则进行等值演算化成前束范式。

（1）xF(x)xG(x)

解：xF(x)xG(x)xF(x)xG(x)x(F(x)G(x))（2）xF(x)xG(x)解：

xF(x)xG(x)xF(x)xG(x)x(7F(x))xG(x)x(7F(x)G(x))

（3）(xF(x,y)yG(y))xH(x,y)

解：

(xF(x,y)yG(y))xH(x,y)(7(xF(x,y))yG(y))xH(x,y)(x(7F(x,y))zG(z))xH(x,y)xz(7F(x,y)G(z))xH(x,y)xz(F(x,y)7G(z))uH(u,y)xzu((F(x,y)G(z))H(u,y))

（4）x(P(x)yQ(x,y))

解：x(P(x)yQ(x,y))x(7P(x)yQ(x,y))xy(7P(x)Q(x,y))

11．给出下面公式的skolem范式：

分析：本题主要是根据已知的基本等值式通过消去蕴含连接词、等价连接词，依据改名规则、代替规则进行等值演算化成前束范式，然后根据前束范式写出对应的skolem范式。

（1）7(xP(x)yzQ(y,z))解：

7(xP(x)yzQ(y,z))(xP(x)yzQ(y,z)xyz(P(x)Q(y,z))

∴所求为:xz(P(x)Q(f(x),z))

（2）x(7E(x,o)(y(E(y,g(x))zE(z,g(x))E(y,z)))))解: 原式x(7E(x,o)(yz(E(y),g(x)E(z),g(x)E(y,z))))

x(7E(x,o)7(yz(E(y)g(x))E(y,g(x)E(y,z))))x(7E(x,o)(u7(E(y),g(x))E(,g(x)E(y,z))))

x(7E(x,o)u((7(E(u),g(x)))(7E(1g(x)))E(y,z))

xu(E(x,o)((7E(u,g(x)))(7E(,g(x)))E(y,z))

即为所求

（3）7(xP(x)yP(y))

解：7(xP(x)yP(y))7(7xP(x)yP(y)7(x7P(x)yP(y)

7(xy(7P(x)P(y)))xy(P(x)7P(y))即为所求。

12．假设xyM(x，y)是公式G的前束范式，其中M（x, y）是仅仅包含变量x，y的母式，设f是不出现在M（x, y）中的函数符号。证明：G恒真当且仅当xyM(x,f(x))恒真。

分析：本题主要是用反证法，根据解释的定义来证明结论成立。

证：设GxyM(x，y)恒真。若xM(x,f(x))不真，则存在一个解释I, 使得对任意的x0D（论域），M(x0,f(x0))为假。于是，G在I下也为假。此为矛盾。

反之，设xM(x,f(x))恒真。若xyM(x，y)不是恒真，则存在一个解释I’，使得对任意xiD，存在yiD，使M(xi，yi)为假。由于f是不出现在M(x，y)中的函数符号，故可定义函数f:使得f(xi)yi。于是，xM(x,f(x))在I’下为假。矛盾。

故结论成立。13．证明

DD，(x)(P(x)Q(x))(x)(Q(x)R(x))(x)(P(x)R(x))

分析：本题是根据基本的等值式、蕴含式、以及US、UG、ES、EG规则证明结论成立。证：（1）(x)(P(x)Q(x))(x)(Q(x)R(x))前提引入

(2)(x)(P(x)Q(x))

化简（1）

（3）P(y)Q(y)

US规则，根据（2）（4）(x)(Q(x)R(x))

化简（1）

（5）Q(y)R(y)

US规则，根据（4）

（6）P(y)R(y)

假言三段论，根据（3），（5）（7）(x)(P(x)R(x))

ES规则，根据（6）

14．构造下面推理的证明：

分析：本题是根据基本的等值式、蕴含式、以及US、UG、ES、EG规则证明结论成立。前提：x(F(x)H(x)),x(G(x)H(x))结论：xG(x)7F(x)

证：（1）x(F(x)H(x))

前提引入

（2）x(7F(x)7H(x))

等价式（1）（3）x(H(x)7F(x))

等值式（2）（4）H(y)7F(y)

US规则（3）（5）x(G(x))H(x)

前提引入（6）G(y)H(y)

US规则（5）（7）G(y)F(y)

假言三段论（4），（6）

（8）x(G(x)7F(x))

UG规则（7）

15．指出下面两个推理的错误。

分析：本题主要是考察US、UG、ES、EG规则的适用范围，也就是前提条件。（1）x(F(x)G(x))

前提引入

（2）F(y)G(y)

US规则，根据（1）（3）xF(x)

前提引入

（4）F（y）

ES,(3)（5）G（y）

假言推理，（2），（4）（6）xGx

UG,(5）

解：（4）错误。Fy中的变元y与（2）中的变元重名。

（1）xyx，y

前提引入（2）yF(z,y)

US规则，（1）（3）F(z,c)

ES规则，（2）（4）xFx,c

UG，（3）（5）yxF(x,y)

EG，（4）解：（3）错误。在yF(z,y)中变元并非只有y。

16.每个学术会的成员都是知识分子并且是专家，有些成员是青年人。证明：有的成员是青年专家。分析：本题主要是首先把明天符号化，符号化前提，结论。然后根据US、UG、ES、EG规则证明结论成立。

解：P（x）：x是学术会的成员；

E（x）：x是专家；

G（x）：x是知识分子；

Y（x）：x是青年人。

前提：x(P(x)G(x)E(x)),(x)(P(x)Y(x))结论：x(P(x)Y(x)E(x))

证明：（1）x(P(x)G(x)E(x)))

前提引入

（2）P(c)(G(x)E(c))

US,(1)

（3）x(P(x)Y(x))

前提引入（4）P(c)Y(c)

ES,（3）（5）P（c）

化简（4）

（6）G(c)E(c)

假言推理,（2），（5）（7）E（c）

化简,（6）

（8）Y(c)

化简,（4）

（9）P(c)Y(c)E(c)

合取（5）（7）（8）（10）x(P(x)Y(x)E(x))

离散数学每一章练习题 篇6

1.设xn

nn2

(n1,2,),证明limxn1,即对于任意0,求出正整数N,使得

n

当nN时有 |xn-1|,并填下表:

n

1|

2n2

,只需n

22,取

证0,不妨设1,要使|xn-1||N

n2

2

2,则当nN时,就有|xn-1|.

n

n

2.设limanl,证明lim|an||l|.证0,N,使得当nN时,|anl|,此时||an||l|||anl|,故lim|an||l|.n

3.设{an}有极限l,证明

(1)存在一个自然数N,nN|an||l|1;

(2){an}是一个有界数列,即存在一个常数M,使得|an|M(n12,).证(1)对于1,N,使得当nN时,|anl|1,此时|an||anll||anl||l||l|1.(2)令Mmax{|l|1,|a1|,,|aN|},则|an|M(n12,).4.用-N说法证明下列各极限式:

(1)lim

n

3n12n3



;(2)lim

n

n1

0;

(3)limnq0(|q|1);(4)lim

n

n

2n

n!n

n

0;

111(5)lim1;n1223(n1)n11(6)lim0.3/23/2n(n1)(2n)证(1)>0,不妨设<1,要使

3n12n3

32

112(2n3)

,只需n

112

3,取N

3n133n1311

3,当nN时,,故lim.2n2n32n322

(2)>0,要使

,由于



只需

,n



3,1

取N

3(3)|q||nq|

n

,当

nN时1

.1n

(0).n4



1n124n

n

n(n1)

(1)6n

n



n(n1)(n2)



}.

3n



(n1)(n2)n!n

n

,n1.

,Nmax{4,243

(4)

1n

,n

,N

111(5)1

(n1)n1223

111111111

1,n,N

n(n1)n1223



.

(6)

1(n1)

n

3/2



1(2n)

3/2



n(n1)

3/2



,n

,N

12.

5.设liman0,{bn}是有界数列,即存在常数M,使得|bn|M(n1,2,),证

明limanbn0.n

证0,正整数 N,使得

|an|故limanbn0.n



M,|anbn||an||bn|



M

M,6.证明lim

n

1.证0,要使1|n(1)

n

1,只需

n(1)

n

1.4n

而

1n

nn(n1)





(n1)



4n,只需1,n

,N

4

2.

7.求下列各极限的值:(1)limn

lim

n

0.22

(2)lim

n

n3n1004nn2(2n10)nn

lim

n

13/n100/n41/n2/n



.(3)lim

n

lim

n

(210/n)11/n

n

16.2

1

(4)lim1

nn

2n

1

lim1

nn

e.2

11

(5)lim1limn1

nnn11

11

n1n1

1

lim1nn11

(6)lim1

nn

n

n

n

n1



1

lim1nn1

n

n

1e

.111

lim1,取q(,1),N,当nN时,1qnnen

11

10,即lim1nnn

n

n

n

n

n

1nn

01q,limq0,lim

nnn

n

n

n

0.1111

(7)lim12lim1lim1e1.nnnnnne

8.利用单调有界序列有极限证明下列序列极限的存在性:(1)xnxn1(2)xn

11112121



1n,xn1xn2

121

n

1(n1)

xn,

1(n1)n1

1n

2.xn单调增加有上界，故有极限.,xn1xn

n1



21



1

xn,1n

111111111.xn2n12n12222222211

2xn单调增加有上界，故有极限.(3)xn

1n1



1n2



1nn

.xn1xn

12n2



1n1



12n2

0,xn1xn,xn0,xn单调减少有下界，故有极限.(4)xn11

12!

1n!

.xn1xn

1(n1)!

0,111111

xn2133.223nn1nxn单调增加有上界，故有极限.11

9.证明e=lim11.n2!n!

11n(n1)1n(n1)(nk1)1

证11n2k

nn2!nk!n

n(n1)(nn1)1

n!

n

n

n

2

1111k111n1111112!nk!nnn!nn1

n

11111.elim1lim11.nn2!n!n2!n!对于固定的正整数k,由上式,当nk时,11111k112111,n2!nk!nn

11

令n得e11,2!k!

1111

elim11lim11n.k2!k!2!n!

10.设满足下列条件:|xn1|k|xn|,n1,2,,其中是小于1的正数.证明limxn0.n

n

n1