图论习题+谓词逻辑测验题2

1、Powerpoint TemplatesPage 1Powerpoint Templates图论习题图论习题Powerpoint TemplatesPage 2作业作业16 3. 求图求图4-1所示图中结点所示图中结点v1到其他所有结点的最短路径及最短距离，到其他所有结点的最短路径及最短距离，并填表。并填表。 步步骤骤永久结点集永久结点集P最近最近邻接点邻接点最短最短距离距离D(v2)D(v3)D(v4)D(v5)D(v6)D(v7)D(v8)D(v9)D(v10)D(v11)123Powerpoint TemplatesPage 3步步骤骤永久结点集永久结点集P最近最近邻接点邻接点最短最短距

2、离距离D(v2)D(v3)D(v4)D(v5)D(v6)D(v7)D(v8)D(v9)D(v10)D(v11)1234567891011 v128121*1*1*1*1*1*1*1*1*1*v41v1v4v2v1v4v2v5Vv2v5v8v6v3v7v10v9v112356791011132*v1v4v1v4v2v5v8v1v4v2v5v8v6v1v4v2v5v8v6v3v1v4v2v5v8v6v3v7v1v4v2v5v8v6v3v7v10v1v4v2v5v8v6v3v7v10v92*2*2*2*2*2*2*2*7*7*7*7*7*7888833*3*3*3*3*3*3*3*6*6*6*6*6

3、*6*669*5* 11* 10* 13*9*9*9*9101010101055*5*5*5*5*5*12121212121111* 10*10*1013141414141414Powerpoint TemplatesPage 4步步骤骤永久结点集永久结点集P最近最近邻接点邻接点最短最短距离距离D(v2)D(v3)D(v4)D(v5)D(v6)D(v7)D(v8)D(v9)D(v10)D(v11)1234567891011 v128121*1*1*1*1*1*1*1*1*1*v41v1v4v2v1v4v2v5Vv2v5v8v6v3v7v10v9v112356791011132*v1v4v1v4

4、v2v5v8v1v4v2v5v8v6v1v4v2v5v8v6v3v1v4v2v5v8v6v3v7v1v4v2v5v8v6v3v7v10v1v4v2v5v8v6v3v7v10v92*2*2*2*2*2*2*2*7*7*7*7*7*7888833*3*3*3*3*3*3*3*6*6*6*6*6*6*669*5* 11* 10* 13*9*9*9*9101010101055*5*5*5*5*5*12121212121111* 10*10*1013141414141414v1到到v11的最短距离为的最短距离为13,最短路径为最短路径为_25637109111vvvvvvvvvPowerpoint Te

5、mplatesPage 5作业作业16 1.某公司在六个城市某公司在六个城市C1, C2, , C6中有分公司，从中有分公司，从Ci到到Cj的直接航程票价在下述矩阵的的直接航程票价在下述矩阵的(i, j)位置上位置上. (表示无直接航线表示无直接航线). 该公司想要一张任意两城市之该公司想要一张任意两城市之间的票价最便宜的路线表，试做出这样的表格。间的票价最便宜的路线表，试做出这样的表格。 050402510500152025150102040201001025252010055102525550 Powerpoint TemplatesPage 6作业作业16 2. 在图在图4-2中中 求邻

6、接矩阵求邻接矩阵A； 求求v1到到v4长度为长度为4的路的数目；的路的数目； 求经过求经过v1长度为长度为3的回路数的数目；的回路数的数目； 求长度小于等于求长度小于等于3的路有多少？其中回路有多少条？的路有多少？其中回路有多少条？ 图图4-2v1v2v3v5v6v4v7Powerpoint TemplatesPage 7作业作业17特殊图特殊图4. 饱和烃的分子结构图是一棵树，其中每个碳原子结点的度为饱和烃的分子结构图是一棵树，其中每个碳原子结点的度为4，每个氢原子结点的度为每个氢原子结点的度为1。证明若该饱和烃含。证明若该饱和烃含n个碳原子，那么个碳原子，那么它就相应的含有它就相应的含有2

7、n+2个氢原子。个氢原子。 3. (1) 证明含有证明含有n个顶点的树中所有顶点度数之和为个顶点的树中所有顶点度数之和为2n-2. (2)设设d1, d2, , dn是是n个正整数；且个正整数；且 。证明存在一棵。证明存在一棵 结点度数为结点度数为d1, d2, dn的树。的树。12n2niid 作业作业15中中1. (1)证明非负整数的序列（证明非负整数的序列（d1,d2,dn） 为某个图的度序列的充要条件是为某个图的度序列的充要条件是1niid 为偶数。为偶数。Powerpoint TemplatesPage 8第四章第四章 图论复习图论复习Powerpoint TemplatesPage

8、 9第第四四章章基本概念基本概念 图、点的度数，图的分类（简单图、完全图）等图、点的度数，图的分类（简单图、完全图）等基本理论基本理论 握手定理（无向图、有向图）握手定理（无向图、有向图）连通性连通性无向图无向图 连通关系：连通关系：(1)任意两点间有路任意两点间有路; (2)w(G)=1有向图有向图 可达关系（单向、强、弱连通）可达关系（单向、强、弱连通） 赋权图赋权图D氏算法氏算法 求给定顶点之间的最短路径与最短距离求给定顶点之间的最短路径与最短距离树（无向树）树（无向树）定义定义无回路无回路连通连通|E|=|V|-1知二推三，即树知二推三，即树求最小生成树算法求最小生成树算法 Prim算

9、法算法Kruskal算法算法其它特殊图其它特殊图 欧拉图、哈密尔顿图、二部图、平面图（不考）欧拉图、哈密尔顿图、二部图、平面图（不考）Powerpoint TemplatesPage 10Powerpoint Templates谓词逻辑测验题谓词逻辑测验题Powerpoint TemplatesPage 11谓词逻辑测验题（第一题）谓词逻辑测验题（第一题）(1) 如果两个实数的乘积是零，那么其中至少有如果两个实数的乘积是零，那么其中至少有一个实数等于零。一个实数等于零。(个体域：所有实数的集合个体域：所有实数的集合) 解：设函数解：设函数f(x, y)=xy, 即即x与与y的乘积；的乘积； 谓

10、词谓词Q(x)表示表示x=0. 则原命题可以表示为则原命题可以表示为 ( ( , )( )( ).x y Q f x yQ xQ y 不要在添加不要在添加特性谓词特性谓词了！了！Powerpoint TemplatesPage 12谓词逻辑测验题（第一题）谓词逻辑测验题（第一题）(2)不存在既是偶数又是奇数的自然数。不存在既是偶数又是奇数的自然数。 解：个体域默认为解：个体域默认为“全总个体域全总个体域”，即需要特性，即需要特性谓词。谓词。 设谓词设谓词N(x)表示表示x是自然数是自然数, 谓词谓词O(x)表示表示x是奇数，是奇数，E(x)表示表示x是偶数是偶数. 则原命题可以表示为则原命题可

11、以表示为 ( )( )( )x N xO xE x.存存在在量量词词 在在特特性性谓谓词词之之后后用用；全全称称量量词词 在在特特性性谓谓词词之之后后用用Powerpoint TemplatesPage 13谓词逻辑测验题（第一题）谓词逻辑测验题（第一题）(2)不存在既是偶数又是奇数的自然数。不存在既是偶数又是奇数的自然数。 解：个体域默认为解：个体域默认为“全总个体域全总个体域”，即需要特性谓词。，即需要特性谓词。 设谓词设谓词N(x)表示表示x是自然数是自然数, 谓词谓词O(x)表示表示x是奇数，是奇数，E(x)表示表示x是偶数是偶数.原命题等价于原命题等价于“任何一个自然数或是奇数或是偶

12、数任何一个自然数或是奇数或是偶数” 则原命题可以表示为则原命题可以表示为 ( )( )( )x N xO xE x ( )( )( )( )( )x N xO xE xO xE x 或或严格按照原命题的含义来做符号化！严格按照原命题的含义来做符号化！Powerpoint TemplatesPage 14(3)尽管有些人聪明，但并不是所有人都聪明。尽管有些人聪明，但并不是所有人都聪明。解：个体域默认为解：个体域默认为“全总个体域全总个体域”，即需要特性，即需要特性谓词。谓词。 设谓词设谓词M(x)表示表示x是人，是人， “有些人聪明有些人聪明”表示为表示为 “不是所有人都聪明不是所有人都聪明”表

13、示为表示为谓词逻辑测验题（第一题）谓词逻辑测验题（第一题）C(x): x聪明。聪明。 ( )( )x M xC x ( )( )x M xC x Question：两句话之间什么关系？：两句话之间什么关系？ ( )( )x M xC x ( )( )x M xC x Powerpoint TemplatesPage 151. 鸟会飞，猴子不会飞；所以，猴子不是鸟。鸟会飞，猴子不会飞；所以，猴子不是鸟。解：设个体域为全总个体域。解：设个体域为全总个体域。 设设B(x): x是鸟，是鸟，M(x): x是猴子，是猴子，F(x): x会飞。会飞。 则此推理可以表示为：则此推理可以表示为： 谓词逻辑测验

14、题（第二题）谓词逻辑测验题（第二题）( )( ) ,x B xF x( )( )x M xF x ( )( ) .x M xB x Powerpoint TemplatesPage 16谓词逻辑测验题（第二题）谓词逻辑测验题（第二题）( )( ) ,x B xF x( )( )x M xF x ( )( ) .x M xB x 利用反证法利用反证法(1)(2)(1)(3)( )(2)(4)( ),(3)(5) ( ),(3)(6)(7)( )(6)(8( )( ) ,( )( ) ,( ),( )( )( ),( ),( )( ) ,()(4)(7)(9)(10) ( )(9),x M xB

15、xx M xB xB cxM cM cM xFB cPM cPB cxF cF cx B xF xF c附加前提等价置换存在量词消去规则合取化简规则合取化简规则规则全称量词消去规则假言推理规则规则，)(11) ( ),(5)(10)(8)F c全称量词消去规则假言推理规则与矛盾，故原推理有效。Powerpoint TemplatesPage 17谓词逻辑测验题（第二题）谓词逻辑测验题（第二题）2.会操作计算机的人都认识会操作计算机的人都认识26个英文字母。文盲都个英文字母。文盲都不认识不认识26个英文字母。有的文盲是很聪明的。所个英文字母。有的文盲是很聪明的。所以有的很聪明的人不会操作计算机。

16、以有的很聪明的人不会操作计算机。 (个体域：所有人的集合个体域：所有人的集合) 解：解：设设C(x): x会操作计算机，会操作计算机，I(x): x是文盲，是文盲， A(x): x认识认识26个字母，个字母，B(x): x聪明。聪明。则此推理可以表示为则此推理可以表示为 ( )( ) ,( )( ) ,( )( )( )( ) .x C xA xx I xA xx I xB xx B xC x 先消去存在量词，后消去全称量词先消去存在量词，后消去全称量词Powerpoint TemplatesPage 18 ()() ,()() ,()()()() .x C xA xx I xA xx I x

17、B xx B xC x (1)(2) ( )(1)(3) ( ),(2)(4) ( ),( )( ) ,( ),( )( )(2)(5),PI cI cx I xB xBB cx I xA xcP 规则存在量词消去规则合取化简规则合取化简规则规则( ),( )(6) ( )(5)(7)(3)(6,( )() ,)(8A cA cx C xAI cPx 全称量词消去规则假言推理规则规则(9) ( )(8)(10)(7)(9)(11) ( )(4)(10( ),( ),( ),)A cC cBC cC cc全称量词消去规则拒取式合取引入规则( )( ) ,(111)( 2) x B xC x存在量

18、词引入规则故推理有效故推理有效 Powerpoint TemplatesPage 19谓词逻辑测验题（第二题）谓词逻辑测验题（第二题）3.每个在学校读书的人都获得知识。所以如果没有每个在学校读书的人都获得知识。所以如果没有人获得知识就没有人在学校读书。（个体域：所人获得知识就没有人在学校读书。（个体域：所有人的集合）有人的集合）解：解：设设S(x): x在学校读书，在学校读书，K(x): x获得知识。获得知识。 则原命题可以表示为则原命题可以表示为 ( )( )( )( ).x S xK xxK xxS x( )( )( )( )xK xxS xx K xx S x 结结论论等等价价于于使用使

19、用CP规则，即将规则，即将 作为新的前提作为新的前提,则现在的目标是证明则现在的目标是证明 这是关于全称量词的一个结论，故用这是关于全称量词的一个结论，故用反证法反证法。( )x K x ( ).x S x Powerpoint TemplatesPage 20设命题函数：设命题函数：RA(x): x属于实数集合属于实数集合A； RB(x)：属于实数集合：属于实数集合B； D(x, y)：xy试将命题试将命题“并非并非A中的数都比中的数都比B中的数大中的数大”按下列要求分按下列要求分别别用谓词公式表示。用谓词公式表示。(1994年中国科学院研究生入学试题）年中国科学院研究生入学试题）(1)只出

20、现全称量词；只出现全称量词；(2)只出现存在量词；只出现存在量词；(3)量词全部放在左边：量词全部放在左边： 即求前束范式，即不能有量词的否定形式出现，即求前束范式，即不能有量词的否定形式出现， 故答案同故答案同2。谓词逻辑测验题（第三题）谓词逻辑测验题（第三题）( )( , )( ).ABx y RxRD x yy )( )( , )(ABx y RRyD x yx Powerpoint TemplatesPage 21第第三三章章谓谓词词逻逻辑辑符号化符号化 论域、量词论域、量词 的选取的选取运运 算算 推理有效性的证明推理有效性的证明()x如如等等价价式式： 与与 、 及及的的分分配配律律等等论论号号结结论论域域、符符化化、前前提提、证证间间证证证证用用直直接接明明法法、接接明明法法明明消去规则消去规则几个注意几个注意（见上课时的课件）（见上课时的课件）第三章第三章 谓词逻辑谓词逻辑复习复习Powerpoint TemplatesPage 22第二章第二章 命题逻辑命题逻辑复习复习命命题题逻逻辑辑正正确确的的符符号号化化, , 真真值值表表按按照照规规则则来来写写，不不遗遗漏漏情情况况00001111,001100