离散数学复习题(期末测试卷)

第一篇：离散数学复习题(期末测试卷)

复习题

一、填空题（请将每空的正确答案写在答题纸相应位置处，答在试卷上不得分。每小题2分，共16分。）

1．谓词公式xy(P(x,y)Q(y,z))xR(x,y)中x的辖域是。

2．命题公式(pq)的成真赋值为。

3．在1和1000之间（包括1和1000在内）不能被4和5整除的数有个。

4．设R是定义在集合A{1,2,3,4}上的二元关系R{1,1,1,2,2,3,1,4}，则R的对称闭包s(R)。

5．A{1,2,3,4},xymin{x,y},则代数系统A,中的零元是。

6．具有10个结点的无向完全图的边数=。

7．一次同余方程3x1(mod5)的最小正整数解是。

8．84与198的最大公约数是。

二、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共16分。）

1.设F(x): x是有理数，G(x)：x能表示成分数。在一阶逻辑中，命题“没有不能表示成分数的有理数”可符号化为()。

A.x(F(x)G(x))B.x(F(x)G(x))

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

2.设个体域是整数集，则下列命题的真值为真的是()。

A．yx(xy1)B．xy(xy0)

C．xy(xyy2)D．yx(xyx2)

3.集合A{1,2,,10}上的关系R{x,y|xy10,x,yA}，则R的性质为()。

A、自反的B、传递的、对称的C、对称的D、反自反的、传递的4．对自然数集合N，下列定义的运算中()是不可结合的。

A.abab3B.aba2b

C.abab(mod 3)D.abmin{a,b}

5．下列各图中既是欧拉图，又是汉密尔顿图的是()。

A．B．C．D．

6．对于下列度数序列，可画成简单无向图的是()。

A．(1，1，1，2，3)B．(1，2，2，3，4，5)

C．(1，2，3，4，5，5)D．(2，3，3，4，5，6)

7.含有5个结点、3条边的不同构的简单图有()个。A.2B.3C.4D.5【】

8．5的模6逆等于()。

A．1B．

3C．4D．5

三、计算题（第1、2、3、4小题各7分，第5、6小题各8分共44分。）1．求命题公式(pq)(pr)的主析取范式和主合取范式。

2．设A,R为偏序集，其中A{1,2,3,4,6,9,24,54}，R是A上的整除关系。（1）画出A,R的哈斯图；（2）求A中的极大元；（3）令B{4,6,9}，求B的上确界和下确界。3．求下图1中带权无向图的最小生成树，并求出该最小生成树的权值。4．求解递推方程：an7an112an20,a04,a16。5．有向图D如图2所示，求：（1）D中v1到v3长度为3的通路有几条？（2）D中v1到v1长度为3的回路有几条？（3）D是哪类连通图？

v

4图1图

2v

36．在通讯中要传输字母a,b,c,d,e,f,g，它们出现的频率为：

a:30%,b:20%,c:15%,d:10%,e:10%,f:9%,g:6%，设计传输上述字母的最佳二元前缀码，画出最优树，并求传输100个按上述频率出现的字母所需二进制字个数。

四、证明题（每小题8分，共16分。）1．设R为自然数集N上的关系，定义N上的关系R如下：x,yRxy是偶数。（1）证明R为等价关系；（2）求商集N/R。2．设Z为整数集合，在Z上定义二元运算如下：证明：x,yZ,xyxy2，Z,是群。

五、符号化下列命题，并在自然推理系统P中论证结论的有效性（8分。）

若小张喜欢数学，则小李或小赵也喜欢数学。若小李喜欢数学，则他也喜欢物理。小张确实喜欢数学，可小李不喜欢物理。所以，小赵喜欢数学。

参考答案

一、填空题（请将每空的正确答案写在答题纸相应位置处，答在试卷上不得分。每小题2分，共16分。）

1．P(x,y)Q(y,z)2．10，11，003．600

4．{1,1,1,2,2,3,1,4,2,1,3,2,4,1}5．1 6．457．38．6

二、单项选择题（从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。答案错选或未选者，该题不得分。每小题2分，共16分。）

1．C2．C3．C4．B5．C6．A7．C8．D

三、计算题（第1、2、3、4小题各7分，第5、6小题各8分共44分。）

1．解：主合取范式为：（5分）

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

((pq)(rr))((pr)(qq))(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)M4M5M6

主析取范式为：（2分）

(pq)(pr)m0m1m2m3m7

(pqr)(pqr)(pqr)(pqr)(pqr)2．解：（1）A,R的哈斯图如下图所示。（3分）

429（2）A中的极大元是：24，54；(2分)

（3）B的上确界：无；B的下确界：1。(2分)3．解：所求该图的最小生成树如下图所示。（5分）

该最小生成树的权值之和

W（t）=2+1+1+2+3+4=13（2分）

4．解：其特征方程为：x27x120，其特征根是：x13,x24（2分）

通解为：anc13nc24n（2分）

代入初值得到：c1c24,3c14c26

解得：c110,c26（2分）

所以，原方程的解为：

an103n64n。（1分）

5．解：先求图D的邻接矩阵A及A2、A3。

11A

0

1110

220112，（1分）A1001



0001

122

541113,（2分）A1000

1102

233

232（2分）110



122

(1)D中v1到v3长度为3的通路有3条。（1分）(2)D中v1到v1长度为3的回路有5条。（1分）(3)D是强连通图。（1分）

6．解：按字母顺序，令pi为传输第i个字母的频率，i1,2,,7，则传输100个字母，各字母出现的频数为wi100pi，得

w130,w220,w315,w410,w510,w69,w76。将它们按照从小到大顺序排列，得691010152030。（2分）以wi为权求最优2叉树如下图所示。

6（4分）

传输的前缀码分别为：a01,b11,c001,d100,e101,f0001,g0000。传100个所需二进制数字个数为：

W(t)=15+30+60+100+40+20=265。（2分）

四、证明题（每小题8分，共16分。）1．（1）证明：

xN,因为xx2x，2xN且是偶数，于是x,xR,因此R在N上是自反的；（1分）

x,yN,若x,yR,则xy是偶数，即yx是偶数，于是y,xR, 因此R在N上是对称的；（1分）

x,y,zN,若x,yR且y,zR,则xy2k1yz2k2,k1,k2Z，于是xz(xy)(yz)2y2(k1k2y)，进而x,zR,因此R在N上是传递的；（2分）

综上所述，R是N上的等价关系。（1分）

（2）N关于等价关系R的所有等价类为[0]R{0,2,4,6,}和[1]R{1,3,5,7,}，则N/R{[0]R,[1]R}。（3分）

2．证明：显然，Z关于是封闭的。（1分）

对于任意x,y,zZ，由于

(xy)z(xy2)z(xy2)z2xyz4，而 x(yz)x(yz2)x(yz2)2xyz4，于是

(xy)zx(yz)，即满足结合律。（2分）

（2分）xZ，因为x2x22x2x，因此2是Z关于的单位元。

xZ，由于4xZ且x(4x)x(4x)22(4x)x，于是

x关于存在逆元4x。（2分）所以，Z,是群。（1分）

五、符号化下列命题，并在自然推理系统P中论证结论的有效性（8分。）解：设简单命题

p：小张喜欢数学。q：小李喜欢数学。

r：小赵喜欢数学。s：小李喜欢物理。（2分）前提：p(qr),qs,p,s 结论：r

（或写为：推理形式为p(qr),qs,p,sr）（1分）证明：

(1)qs前提引入(2)s前提引入

（2）拒取式（2分）(3)q（1）

(4)p(qr)前提引入(5)p前提引入

（5）假言推理（2分）(6)qr（4）

（6）析取三段论（1分）(7)r（3）

第二篇：离散数学复习题

离散数学复习题

• 设命题p，r的真值为1，命题q，s的真值为0，则（p→q）(﹁r→s)的真值

为。

• 只要4不是素数，3就是素数，用谓语表达式符号化为。

• D=｛｝，则幂集ρ(D)=

• A={a,{b}}，B=｛｝，则A×B=

• 若集合A，B的元素个数分别为|A|=m,|B|=n,则A到B有种不同二元关系。• 设A=｛1,2,3,4｝，B=｛4,5，6,7｝，R=｛<1,4>，<1,6><2,4>，<3,5>，<3,6>｝是由A

到B的二元关系，则domR=，ranR=

• I A是集合A上的恒等关系，A上的关系R具有性当且仅当IAR。• 二元关系R是等价关系，当且仅当的R是。

9.设K4是有4个点的无向完全图，则K4有条边。

10.无向图G是欧拉图当且仅当。

11.在任何无向图这，所有顶点的度数之和等于边数的倍。

12.设K5是有5个点的无向完全图，则K5有条边。

13.无向图G是欧拉图当且仅当。

计算题

• 求公式（PQ）→（QR）的主析取范式

• 集合A=｛a,b,c｝,R={,,,}是集合A上的二元关系，求R的自反

闭包r(R),对称闭包s(R)和传递闭包t(R)(用矩阵运算)，并画出各闭包的关系图。• 设图G

• 写出G的邻接矩阵

• 求各结点的初度，入度

• 求V3到V2长度是3的路的数目

• 设集合A=｛1,2，3,4,6,8，12｝，R是A上的整除关系，• 画出偏序图的哈斯图；

证明题

• 在自然推理系统p中构造下面推理的证明

前提：﹁r，﹁pr，（q）→p

结论：q→﹁

• 在自然系统p中构造下面推理的证明

前提：pq,p→r,q→s

结论：sr

第三篇：离散数学复习题

离散数学复习题

一、填空

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)

9、证明10阶群必有5阶子群

第四篇：离散数学复习题1

逻辑

1、给出的真值表

2、证明为永真式 谓词量词和推理

1、使用量词和谓词表达不存在这一事实

2、证明前提“在这个班上的某个学生没有读过书”和班上的每个学生都通过了第一门考试蕴含结论“通过考试的某个人没有读过书” 集合、函数、数列与求和

1、全集为，求集合A=的位串？它的补集的位串是什么？写出集合A=的所有子集，写出集合

2、从集合到集合能定义多少个函数？下面给出的函数其定义为：该函数是双射吗？是满射吗？该函数是否存在逆函数？如果存在请给出其逆函数。计数

1、计算机系统的美国用户有一个6～8个字符构成的密码，其中每个字符是一个大写字母或数字，且每个密码必须至少包含一个数字，问总共有多少个合适的密码？

2、在30天的一个月里，某棒球队一天至少打一场比赛，但最多打45场。证明一定有连续的若干天内这个球队恰好打了14场比赛

3、证明n个元素的集合中允许重复的r组合数等于

4、按照字典顺序生成整数1，2，3的所有排列（不允许重复），在362541后面按照字典顺序的下一个最大排列是什么？找出在1000100111后面的下一个最大的二进制串。关系

1、求下面给出关系R的自反闭包、对称闭包和传递闭包的0-1关系矩阵，其中

2、S是所有比特串的集合，关系定义为当s=t或者s和t的长度至少是3，且前3个比特相同时具有关系，例如0101，0011100101，但01010，0101101110。证明是S上的等价关系，由产生的S的等价类是那些集合？

3、偏序集（{2,4,5,10,12,20,25},|）的那些元素是极大的，那些元素是极小的？ 图与树

1、在下图所示的图中，从a 到d的长度为4的通路有几条？该图是否是Euler图，是否是Hamilton图，该图的度序列是什么？该图是否可平面，如果是请给出平面画图，该图的点色数和边色数等于多少？给出该图的一个生成树，2、求下面赋权图从a到z的最短距离是多少？最短路径是什么？（画图给出标号过程）

3、用哈夫曼编码方法来编码下列符号，这些符号具有下列频率：A:0.08，B:0.10，C:0.12，D:0.15，E:0.20，F:0.35,该编码方法编码一个字符的平均位数是多少？

4、下面树的高度是多少？那些节点是内部节点，那些节点是叶子节点，该树是否是3元正则树？分别给出该树节点的前序、中序、后序遍历的节点访问次序

第五篇：本科离散数学复习题

离散数学复习题

一、填空题

1.集合A={,1}，B={1,2}，则2A2B=_________，2A2B=_________.A与B的笛卡尔积AB=_________.2.1000以内的所有正整数中，能被4和5同时整除的共有_____个，不能被6整除的共有_____个

3.设集合A={1,2,3}，B={a,b,c}，则AB共有_____个元素。A到B 的关系

(包括空关系)共有_____个，其中又有_____个是AB的函数, 有_____ 个是A B的内射, 有_____ 个是A B的双射。

4.设A={1,2,3,4,5,6,7,8}.则由B15 表示的A的子集是____________.A的一个子集{2,3,5,7}可表示为____________ 5.集合A={1,2,3,4}，上的两个关系 1={(1,2),(1,3),(2,1)(2,2),(4,1)}，2={(1,3),(3,1)}，则12=____________.12=____________.=_________.6=_________ 12=____________.21=____________.116.集合 A={1,2,3} 上的关系 ={(1,1),(1,2),(1,3),(3,3)} 具有的性质是 _____.7.集合 A={1,2,3,4} 上具有自反性的关系有_____个，具有对称性的关系有_____个，8.设集合A={a,b,c,d}，则A共有_____中不同的分划，A上共有_____个不同的等价关系。若其中的一个分划则与之对应的等价关系是________________.A={{a},{b,c},{d}}，若A上的等价关系：{(a,a),(b,b),(c,c),(d,d),(a,c),(c,a),(b,d),(d,b}.则由导出的A的分划是____________.9.设是集合A={1,2,3,4,5,6,7,8,9,10}上的关于模3同余关系，则[2]=______________________.10.A={1,2,3,4,5,6,7,8,9,10,11,12,24}, 是集合A上的整除关系, BA且 B={2,4,6},则B的最大元是______.最小元是______.上界是______.下界是 ______.最小上界是______.最大下界是______.A的最大元是______.最小元是 ______.A11.在格2,中，集合 A={1,2,3,4,5,6},2A的两元素{1,2}{2,3,5}______.{1,2}与{2,3,5}上界有 ______个.{1,2}{2,3,5}是______.{2,3,4}与{2,4,5}共有______个不同的下界.{1,2,4,6}的补元是________.13.设为任意的格,a,b,c,dL, 若ab且bc,则ac=______________.bc=______________.ac=______________.ab=______________.14.自然数集上的整除关系是一个格, 则在格 N,.中

812=______________812=______________.911=______________911=______________.15.Z是整数集,函数 ƒ定义为:ZZ,且 ƒ(X)=|X|-2X,则函数ƒ的类型是_____(内射,满射,双射).16.设A={1,2,3,4,5},函数ƒ: AA, ƒ(x)=6-x, 则函数ƒ是一个_________射, 17.设函数ƒ: RR，则

f(x)x22，函数g: RR, g(x)x4

fg____,gf____.f1(x)_________.18.设集合A={1,2,3,4,5,6,7,8,9,10},B={2,4,6,8,10,12,14,16,18,20}，函数f:AB,f(i)182i,iA，设H1,2,5,6,A,则f(H)______，设G4,8,10,16B,则f1(G)_____.19.含10条边的图的总度数是____________.20.含有8个顶点的完全图共有______条边.21.含6个结点,9条边的无向连通图,要得到此图的一棵生成树,必须删去__条边.22.不同构且有6个结点的树共有______个.23.简单图G=共有10个结点,其中6个结点的度数为3，其余4个结点的 度数都为2, 则该图共有____条边.该图的补图共有____条边.24.简单图G共有9个结点,且图G与它的补图同构，则该图共有____条边.25.一棵树有2个2度分支点, 1个3度分支点, 3个4度分支点, 则此树共有____片树叶.26.若完全图Kn既是欧拉图又是哈密尔顿，则n满足的条件是__________ 2 27.命题P:“小王学过高等数学”.Q:“小王学过离散数学”.则符合命题“小王学过 高等数学但没有学过离散数学”可表示为___________.命题(PQ)表示的 复合命题含义是:__________________________________________________.28.公式((PQ)(QP))P可化简为___________________________.29.将公式P(QP)化成与之等价的且只含和的公式，则此公式为: __________________.30.令P,Q的赋值分别为1,0.则公式

（(PQ)(QP)）（PQ的真值为__________________.31.公式A含两个命题变元P,Q，其主析取范式为：

(PQ)(QP)），则它的主合取范式是______________.二、选择题

1.设集合A={a，{a}}，则下列错误的是().A){a}2A;B){a}2A;C){{a}}2A； D){{a}}2A;

2.集合A={1,2,3,4,5,6,7,8,9,10}, A上的关系={(x,y)|x+y=10，x,yA},则关 系 具有的性质是().A)自反的;B)对称的;C)传递的,对称的;D)反自反的,对称的;

3.设集合X={-1,1,2,3}与Y={1,2,3,4,5,9}, ƒ(x)=x2,是XY的一个函数,则下列 正确的是().A)ƒ是内射但不是满射;

B)ƒ是满射但不是内射;C)ƒ是双射;

D)ƒ既不是入射也不是满射;

4.设I为整数集合.A={x | x2<30，xI}, B={x | x为质数，x<20}, C={1,3,5}, 则(C-A)(B-A)=().A){1,2,3,5};B);

C){1,3,5,7};

D){1,2,3,5,7};5.在下面的三个命题公式

1)(PQ)(PQ);2)(PQ)(PQ);3)(PQ)(QP);中是永真式的公式有()个.A)0;B)1;C)2;D)3;

6.下面论断正确的是().A)有补格一定是分配格;B)有补格一定是有界格;C)任何一个格必有最大元;D)偏序集就是格;

7.下列命题中错误的是().A)若L为有限集,则格必定是有限格;

B)在格中,a,bL,必有a(ab)=a;C)格是有补格当且仅当有元素存在补元;

D)在有补分配格中,a,bL, 必有ab=ab;

8.一个含n个结点,连通且有圈的简单图,至少有()条边.A)

n;B)n+1;C)n+2;D)2n-1;

三、判断题

1.设A={}, B=22, 则: {}B且{}B.A

()

()2.集合A={a,b,c}上的关系={(a,b),(a,c)}是不可传递的.3.平面上直线间的“平行关系”是等价关系.()4.人群中的“朋友关系”是偏序

()5.若ƒg是满射,则ƒ必是满射.()6.若ƒ, g都是入射,则gƒ也是入射.()7.在有限分配格中,一个元素若有补元,则补元一定是唯一的.()8.K4有10个生成子图.()9.三个(4,2)无向简单图中,至少有两个同构.()10.凡陈述句都是命题.()11.命题公式(P(PQ))Q是矛盾式.()12.命题“如果1+2=3，那么雪是黑的”是真命题.。

13.判定偏序集是否为格.（教材P150页图7-

3、P174页图7-12）

四、解答题

1.设集合A={1,2,4,5},B={1,2,3,5,16,25}，A到B的关系={(x,y)|xA,yB且y=x2}, 1)写出的所有元素;

2)求出关系的定义域及值域;3)写出关系的关系矩阵M;4)判断关系是否为AB的一个函数? 2.设集合A={1,2,3,4},是A上的一个关系,的关系矩阵如下:

求:的自反闭包r(),对称闭包s(),传

递闭包t().4.设集合A={1,2,3,6,12,24,36,72},A上的整除关系={(a,b)|a,bA且a|b}.1)画出偏序集的次序图;2)A的子集B={6,24,36},求集合{x|xA,且x能整除B中的每一个整数}，并求集合{x|xA,且x能被B中的每一个整数整除}.3)判定偏序集是否为格?说明理由.5.偏序集的次序图 如下:

1)求B1={b,c,e}的最小元,最大元.2)求B2={b,c,d,e}的上界,最小上界,下界,最大下界.3)求A的最小元,最大元.4)偏序集是否为格?为什么?

6.格的次序图如下:

1)求出A中所有元素的补元.2)判定格是否为有补格?为什么? 3)判定格是否为分配格?为什么?

7.无向简单图G的邻接矩阵如下：

011000 110000100010110010010100000100

求图G的所有割点、割边.8.有向图G=如下:

1)

2)3)4)5)

求G的邻接矩阵;求deg(V1);

从结点V2到V4长度为3的路有几条? 图中长度为2的回路有几条? 求d(V1 , V4)

9.求下面有权图的一棵最小生成树.并求出最小权数.10.求公式(P(QR))(R(QP))的主析取范式和主合取范式.11.掌握欧拉图、哈密顿图的判定.(教材P227页第16、17、18题)

五、证明题

1.证明： P(QR)Q(PR)2.证明：（Q(PP)(R(PP))R 3.用推理规则证明: 1)(PQ)R, SU, RS, UW, WPQ.2)证明:QS是前提,PQR, Q(RS), P的有效结论.4.试给出以下推理证明: 若这里举行足球赛，则交通就会很拥堵.若他们按时到了球场，则说明交通是畅通的.他们按时到达了.所以这里没有举行足球赛.5.设是一个格,a,b,c,dL, 若ab且cd.求证:acbd.6.设是一个格,a,b,c, L.证明：（ab）(bc)(ac)(ab)(bc)(ac).7.设N是自然数集,定义N上的二元关系={(x,y)|xN,yN,x+y是偶数} 证明是一个等价关系.8.证明：自然数集N上的“整除关系”是一个偏序

9.证明：在（n,m）的树中，m = n-1 6