离散数学练_离散数学练习

离散数学练由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“离散数学练习”。

《离散数学》练习

福建农林大学东方学院

2009 ——2010 学年第一学期

第一篇数理逻辑

一、填空题及单项选择题：

1、设解释I为：客体城D{2,3}，a

2b,3f(2)3f(3),2P(2,2)1P(2,3)1P(3,2)0P(3,3)0

则P(a,f(a))P(b,f(b))，xyP(x,y)。

2、公式G(P(QR))Q的主析取范式为。

3、下列命题等值式正确的是【】

（A）PQ(PQ)(QP)； PQ(PQ)(PQ)；（B）

（C）PQQP；（D）PQPQ.4、设命题公式G(QP)(PQ)，则G是【】

（A）可满足的；（B）永真的；（C）永假的；（D）析取范式

5、前提xP(x)与x(P(x)Q(x))的有效结论是【】

（A）xQ(x)；（B）xQ(x)；

（C）xP(x)；（D）x(P(x)Q(x))。.二、解答题：

1、将下列命题符号化：

（1）明天不下雨又有空的话，我就会去打球。

（2）只要她生病了，我都会去看她（只有她生病了，我才会去看她）。

（3）每个旅客或坐头等舱或坐二等舱。

（4）有些汽车比任何火车都慢，但并非所有的汽车都比火车慢。

2、求公式G(P(QR))Q的主合取范式和主析取范式，并求使G取值为 真的所有指派。

练习第1页（共6页）

三、逻辑推理题

1、用演绎法证明：P→（Q→R），SP，Q, R├S.（应注明每一步推理所采用的推理规则）。

2、找出下列推导过程中的错误，并问结论是否有效？如果是，写出正确的推导过程。（1）x(P(x)Q(x))（2）P(y)Q(y)（3）xP(x)（4）P(y)（5）Q(y)（6）xQ(x)

规则P（前提引入）(1)

规则P（前提引入）(3)

(2),(4)假言推理(5)

3、有红、黄、绿、白四队参加足球联赛，如果红队第三，则当黄队不是第二时，绿队第四。或者白队不是第一，或者红队第三。已知绿队不是第四。试证明：如果白队第一，那么黄队第二。

（要求：设P：白队第一；Q：黄队第二；R：红队第三；S：绿队第四。并写出前提和结论的符号化及推理过程。）

第二篇集合论

一、填空题及单项选择题：

1、设R是集合A{a,b,c}上的二元关系，且R{(a,b),(a,c)}，则

s(R)ts(R)。

2、设R是A{a,b,c,d}上的二元关系，且

R{(a,b),(a,d),(c,c),(d,a)}，则R的关系矩阵AR

3、偏序关系应具有的性质为

4．设N、Z、Q、R和C分别为自然数、整数、有理数、实数和复数集合，（0，1）为实数区间，则下列式子正确的是【】

（A）NR；（B）QC；（C）NQ；（D）(0,1)Z.5．设N、R分别为自然数和实数集合，则下列基数关系式正确的是【】（A）cardR；（B）0；（C）card2；（D）card2N0

练习第2页（共6页）

N

6．按照阶从低到高的次序排列，则下列排列次序正确的是【】（A

n,n2,2n；（B）lgnn,n2(2n)；（C）lognn,n2；（D）logn(lgnn,2n

二、解答题

1、设集合A{1,2,,12}，R为A上的整除关系，试求：（1）画出偏序集(A,R)的Hae图；

（2）写出A中的最大元、最小元、极大元、极小元；

（3）写出A的子集B{1,3,6,9}的上界、下界及上、下确界。

2、（自然映射问题）习题八（P162）第16题。（屈婉玲《离散数学》，下同）设A{a,b,c}，R为A上的等价关系，且

R{a,b,b,a}IA

求自然映射g:AA/R。

3、（计数问题）习题六（P99）第21，23题。

（1）某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人都会打蓝球或排球。求不会打球的人数。

（2）使用包含排斥原理求不超过120的素数个数。

三、证明题

也是A上的等价关系。

1、设R是非空集合A上的等价关系，试证R的逆关系R

也是A上的偏序关系。

2、设R是非空集合A上的偏序关系，试证R的逆关系R3、设（0，1）和[0，1]为实数区间，证明：(0,1)[0,1]

*第三篇代数系统一、填空题及单项选择题：

123456

1、设,,S6，且(1)，546213，



则=，的阶=。

123456

521436，,10,11}，运算是按位加，则群(G,)的子群有

2、设G{00,0

1凡子群有个，2阶子群有个。

3、整数集Z对于普通减法来说作成一个代数系统(Z,)，则(Z,)【】

（A）是半群但没有单位元；（B）含有单位元；

（C）有右单位元，但没有左单位元；（D）有左单位元，但没有右单位元。

练习第3页（共6页）

4、设S{0,1,2}，为模3乘法，即x,yS,xy(x)ymo，d

3则代数系统S,【】

（A）是可换群；（B）是群但不是可换群；（C）是半群但不是独异点；（D）是独异点。

*

5、设(B,,，0,1)是布尔代数，若ab，则下面不成立的公式是【】 a,bB，（A）ab1；（B）ab1；（C）ab0；（D）aba。*6．设I是整数集，,分别是普通加法和减法；A是非空集合，则【】（A）(I,,)是格；（B）(2A,)不是格；

（C）(2A,,)不是格；（D）(2A,)和(2A,,)是同一个格。

二、解答题

1、设A{0,1}，SA，试列出S中的所有函数，并给出S上合成运算的运算表。

2、设在实数集R上有运算*如下：ababab,a,bR。（1）求代数系统(R,)的单位元e和零元；

（2）求出元a(a1)的逆元a。(R,)中每一个元都有逆元吗？为什么？（3）(R,)是群吗？若RR1，则(R,)是否为群？为什么？

*

*



1A



21(,{)3(,)2})

3、已知3次对称群 S3{(1),(12),(13),(23),(123),(132)}，若H

1（1）试验证H是S3的一个正规子群；

（2）求出子群K(12)的所有左陪集及K在S3的指数[S3:K]；（3）求出S3的子群格，并画出它的偏序图。

三、证明题

1、设（G，*）是群，a∈G，定义映射

f：G →G，使f(x)axa,x G

证明f是（G，*）的自同构。

2、设G是群，若xG有xe，证明G为阿贝尔群。

练习第4页（共6页）。



1第四篇图论

一、填空题及单项选择题：

1020011、邻接矩阵为的有向图中，长度为2的非回路的路有条，110

长度为2的回路有条。

2、树叶权为1，2，3，4，5的最优树为

3、具有5个结点的所有不同构的树为

4、在下列的各种顶点度序列中可图解但不可简单图解的是【】（A）(3,1,1,1);（B）d(5,3,2,1,1);（C）d(1,1,1,1);

（D）d(3,2,2,1,1)

5、二分图K3,3也是【】（A）欧拉图;（B）哈密尔顿图;（C）平面图;

（D）完全图。

6、下图是【】（A）Bipartite Graph;(B)Planar Graph;（C）Eller Graph;(D)Hamilton Graph

二、计算题

1、设图G为平面图，它的边数是区域数的2倍，并且有一个6次顶点，四个3次顶点，三个2次顶点，其余顶点都是1次的。试求图G的顶点数、边数和区域数。

2、一棵树有2个2次分枝点，1个3次分枝点，3个4次分枝点，其余顶点都是树叶，问这棵树有几片树叶？

3、设有无向图G(V,E)，其中V(G){a1,a2,,a5}，而G的邻接矩阵

练习第5页（共6页）

01A0

1

110110

011

110001，

001110

且当(ai,aj)E(G)时，边(ai,aj)的权数为ij(i,j1,2,,5)。试画出图G，并求图

G的一个最小生成树及最小生成树的权数。

三、应用及证明题：

1、（哈米尔顿回路问题）习题十五（P306）第15题。

某工厂生产由6种颜色的纱织成的双色布。已知在一批双色布中，每种颜色至少与其他3种颜色相搭配。证明可以从这批双色布中挑出3种，它们由不同颜色的纱织成。

2、（最短路问题）习题十五（P307）第22题。

某工厂使用一台设备，每年年初要决定是继续使用，还是购买新的。预计该设备第一年的价格为11万元，以后每年涨1万元。使用的第1年，第2年，…，第5年的维修费分别为5，6，8，11，18万元。使用1年后的残值为4万元，以后每使用1年残值减少1万元。试制定购买维修该设备的5年计划，使总支出最小。

3、试证，在完全二叉树中，边的总条数应该等于2(nt1),其中的nt是树叶的总片数。

练习第6页（共6页）

离散数学

离散数学课件作业第一部分 集合论第一章集合的基本概念和运算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 为任意集合，则他们的共同......

离散数学

离散数学试题（A卷答案）一、（10分）（1）证明(PQ)∧(QR)(PR) （2）求(P∨Q)R的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值。 解：（1）因为((PQ)∧(QR))(PR) ((P∨Q)∧(Q∨R))∨(P......

离散数学

第一章数学语言与证明方法例1 设E={ x | x是北京某大学学生}, A,B,C,D是E的子集, A= { x | x是北京人},B= { x | x是走读生}, C= { x | x是数学系学生},D= { x | x是喜欢听......

离散数学

离散数学离散数学(Discrete mathematics)是数学的几个分支的总称，以研究离散量的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数无穷个元素；因此它充分描述了计......

离散数学证明题

证明题1.用等值演算法证明下列等值式：（1）┐(PQ)(P∨Q)∧┐(P∧Q)（2）(P∧┐Q)∨(┐P∧Q)(P∨Q)∧┐(P∧Q)证明：（1）┐(PQ)┐((P→Q)∧(Q→P))┐((┐P∨Q)∧(┐Q∨P))(P∧┐Q)∨(Q∧┐P......