离散03命题逻辑 推理理论

1、 3.1 推理的形式结构推理的形式结构3.1 推理的形式结构推理的形式结构3.2 自然推理系统自然推理系统 3.1 推理的形式结构推理的形式结构l数理逻辑数理逻辑用数学的方法来研究推理用数学的方法来研究推理.l推理推理是由前提是由前提(应用推理规则应用推理规则)得出结论的过程得出结论的过程 = A1, A2, , Ak B.其中其中前提前提是命题公式的集合是命题公式的集合, 结论结论是一个命题公式是一个命题公式.l若对于若对于命题变元的任意一组赋命题变元的任意一组赋值值, (1) A1 A2 Ak 为假为假; 或者或者 (2)当当 A1 A2 Ak为真时为真时, B 也为真也为真, 则称推理则

2、称推理 B 是是有效的有效的, 称称 B 是是 的的有效结论有效结论: B.否则是否则是无效无效的的: B./deduction /hypothesis /conclusion/valid /invalid 3.1 推理的形式结构推理的形式结构 对于任何一组赋值对于任何一组赋值, 前提和结论的取值情况有前提和结论的取值情况有:l只要不出现情况只要不出现情况, 推理就是有效的推理就是有效的. 3.1 推理的形式结构推理的形式结构例例1 判断下列推理是否有效判断下列推理是否有效:(1)p, pq q; (2)p, q p q.解解 是否出现前提合取式为真是否出现前提合取式为真, 而结论为假的情况而

3、结论为假的情况?(1) p, pq q.(2) p, q p q. 3.1 推理的形式结构推理的形式结构定理定理(有效推理的等价定理有效推理的等价定理)命题公式命题公式A1, A2, , Ak推推 B 是有效的是有效的 当且仅当当且仅当(A1 A2 Ak) B 为重言式为重言式.证明略证明略前提：前提：A1 ， A2 ， ， Ak结论：结论： B蕴涵关系式蕴涵关系式 H C 表示条件式表示条件式 H C 是重言式是重言式.形式结构形式结构 3.1 推理的形式结构推理的形式结构l推理有效性的判断即对其形式结构推理有效性的判断即对其形式结构(是一个命题公式是一个命题公式)永真性的判断永真性的判断.

4、 l方法有方法有 真值表法真值表法, 等值演算法等值演算法, 主析取范式法主析取范式法. 3.1 推理的形式结构推理的形式结构例例2 判断下面推理是否正确判断下面推理是否正确:(1)他要么打球要么游泳他要么打球要么游泳; 他没打球他没打球. 所以他去游泳了所以他去游泳了. (等值演算法等值演算法)(2)出了事他一定在场出了事他一定在场; 他在场就不会闲着他在场就不会闲着. 所以他没所以他没闲着就一定出事了闲着就一定出事了. (主析取范式法主析取范式法)解解 (1)设设 p: 他打球他打球; q: 他游泳他游泳.前提前提: p q, p, 结论结论: q.推理形式结构推理形式结构: (p q)

5、p) q (p q) p) q ( p q) p) q ( p p) ( q p) q q p q 1.可见推理有效可见推理有效. 3.1 推理的形式结构推理的形式结构(2)出了事他一定在场出了事他一定在场; 他在场就不会闲着他在场就不会闲着. 所以他所以他没闲着就一定出事了没闲着就一定出事了.设设 p: 出事了出事了; q: 他在场他在场; r: 他闲着他闲着.前提前提: p q, q r;结论结论: r p推理的形式结构推理的形式结构: (p q) (q r) ( r p) ( p q) ( q r) (r p) (p q) (q r) r p r p (用两次吸收律用两次吸收律) (pq

6、r) (pq r) (p qr) (p q r) ( pq r) ( p q r) (pq r) (p q r) m1 m3 m4 m5 m6 m7 (重排了序重排了序)这不是重言式这不是重言式, 所以推理无效所以推理无效. 3.1 推理的形式结构推理的形式结构推理定律（蕴涵关系式）推理定律（蕴涵关系式） 1. A (A B) 附加律附加律 2. (A B) A 化简律化简律 3. (AB) A B 假言推理假言推理 4. (AB) B A 拒取式拒取式 5. (A B)B A 析取三段论析取三段论 6. (AB) (BC) (AC) 假言三段论假言三段论 7. (AB) (BC) (AC)

7、等价三段论等价三段论 8. (AB) (CD) (A C) (B D) 构造性二难构造性二难 (AB) ( AB) (AA) B 构造性二难构造性二难(特殊形式特殊形式) 9.(AB) (CD) ( BD) ( AC) 破坏性二难破坏性二难 3.1 推理的形式结构推理的形式结构 3.1 推理的形式结构推理的形式结构 3.2 自然推理系统自然推理系统3.1 推理的形式结构推理的形式结构3.2 自然推理系统自然推理系统 3.2 自然推理系统自然推理系统l推理有效性的判断可以转换为对其形式结构推理有效性的判断可以转换为对其形式结构(命题命题公式公式)永真性的判断永真性的判断, 运用真值表运用真值表,

8、 等值演算和主析取等值演算和主析取范式的方法范式的方法. 当命题变项较多时当命题变项较多时, 计算量较大计算量较大.l下面给出一种形式系统下面给出一种形式系统, 使得严谨的证明可以在其使得严谨的证明可以在其中进行中进行.l证明证明是一个描述推理过程的是一个描述推理过程的命题公式的序列命题公式的序列, 其中其中的每个公式都是按推理规则写出的的每个公式都是按推理规则写出的(最后一个是推理最后一个是推理的的结论结论, 其余叫其余叫中间结论中间结论). = A1, A2, , Ak B. 3.2 自然推理系统自然推理系统定义定义3.2 一个一个形式系统形式系统 I 由下面四个部分组成由下面四个部分组成

9、:(1) 非空的字符表非空的字符表, 记作记作 A(I).(2) A(I) 中符号构造的合式公式集中符号构造的合式公式集, 记作记作 E(I).(3) E(I) 中一些特殊的公式组成的公理集中一些特殊的公式组成的公理集, 记作记作 AX(I).(4) 推理规则集推理规则集, 记作记作 R(I).A = alphabet, E = equation, AX = axiom, R = rule.形式系统形式系统 I = A(I), E(I), AX(I), R(I) , 其中其中 A(I), E(I) 是是 I 的的语言系统语言系统, AX(I), R(I) 为为 I 的的演算系统演算系统. 3.

10、2 自然推理系统自然推理系统形式系统可分为两类形式系统可分为两类.l自然推理系统自然推理系统从任意给定的前提出发从任意给定的前提出发, 得到的结论可能是重言式得到的结论可能是重言式, 也可能不是也可能不是.l公理推理系统公理推理系统 从若干给定的公理出发从若干给定的公理出发, 得到的结论是系统中的重得到的结论是系统中的重言式言式(系统中的系统中的定理定理).本课程只介绍一个自然推理系统本课程只介绍一个自然推理系统, 它没有公理它没有公理./System of natural deduction /system of axiomatic deduction 3.2 自然推理系统自然推理系统定义定

11、义3.3 自然推理系统自然推理系统 P 定义如下定义如下:1. 字母表字母表(1) 命题变项符号命题变项符号: p, q, r, , pi, qi, ri, (2) 联结词符号联结词符号: , , , , (3) 括号和逗号括号和逗号: ( , ), ,2. 合式公式合式公式: (同前同前)3. 推理规则推理规则(1)前提引入前提引入/P规则规则: 在证明的任何步骤上都可以引入前提在证明的任何步骤上都可以引入前提.(2) 结论引用结论引用/T规则规则: 在证明的任何步骤上得到的结论都可以在证明的任何步骤上得到的结论都可以作为后继证明的前提作为后继证明的前提.(3) 置换规则置换规则: 在证明的

12、任何步骤上在证明的任何步骤上, 命题公式中的子公式都命题公式中的子公式都可以用与之等值的公式置换可以用与之等值的公式置换, 得到公式序列中的又一个公式得到公式序列中的又一个公式./alphabet /well formed formula /rule of deduction 3.2 自然推理系统自然推理系统3. 推理规则推理规则(续续)由九条推理定律和结论引入规则还可以导出以下各由九条推理定律和结论引入规则还可以导出以下各条推理定律条推理定律.(1) 假言推理规则假言推理规则(或称分离规则或称分离规则):若证明的公式序若证明的公式序列中已出现过列中已出现过 AB 和和 A, 则可将则可将 B

13、 引入到命题序引入到命题序列中来列中来, 图示为图示为ABAB 3.2 自然推理系统自然推理系统(3) 化简规则化简规则: AA B A BA(2) 附加规则附加规则:(4) 拒取式规则拒取式规则: AB BA AB BC AC(5) 假言三段论规则假言三段论规则: 3.2 自然推理系统自然推理系统 A B B A(6) 析取三段论规则析取三段论规则: AB CD A C B D(7) 构造性二难推理构造性二难推理: AB CD BD AC(8) 破坏性二难推理规则破坏性二难推理规则: A B A B(9) 合取引入规则合取引入规则:这就完成了这就完成了 P 的定义的定义. 3.2 自然推理系

14、统自然推理系统P 中的中的证明证明就是以就是以P 中的一组公式作为前提中的一组公式作为前提, 按照按照 P 中的规则中的规则, 依次写出一序列的公式依次写出一序列的公式, 直至写出结论直至写出结论.I = A(I), E(I), AX(I), R(I) ,P = A(P), E(P), R(P) 例例4 在自然推理系统在自然推理系统 P 中构造下面推理的证明中构造下面推理的证明:(1)前提前提: p q, qr, ps, s 结论结论: r (p q)(2)前提前提: p q, rq, rs 结论结论: ps 3.2 自然推理系统自然推理系统解解 (1)前提前提: p q, qr, ps, s

15、 结论结论: r (p q) ps证明证明:前提引入前提引入推理有效推理有效. s p p q q qr r r (p q)前提引入前提引入拒取式拒取式前提引入前提引入析取三段论析取三段论前提引入前提引入假言推理假言推理合取合取 3.2 自然推理系统自然推理系统(2)前提前提: p q, rq, rs 结论结论: ps证明证明: p q前提引入前提引入推理有效推理有效. pq rq qr pr rs ps置换置换前提引入前提引入置换置换假言三段论假言三段论前提引入前提引入假言三段论假言三段论 3.2 自然推理系统自然推理系统可以在自然推理系统可以在自然推理系统 P 中构造数学和日常生活中的中构

16、造数学和日常生活中的推理推理, 所得结论都是有效的所得结论都是有效的, 即当各前提的合取式为即当各前提的合取式为真时真时, 结论必为真结论必为真. 3.2 自然推理系统自然推理系统例例5 在自然推理系统在自然推理系统 P 中构造下面推理的证明中构造下面推理的证明:若数若数 a 是实数是实数, 则它不是有理数就是无理数则它不是有理数就是无理数; 若若 a 不不能表示成分数能表示成分数, 则它不是有理数则它不是有理数; a 是实数且它不能是实数且它不能表示成分数表示成分数. 所以所以 a 是无理数是无理数.解解 令令 p: a 是实数是实数. q: a 是有理数是有理数. r: a 是无理数是无理

17、数. s: a 能表示成分数能表示成分数.前提前提: p (q r), sq, ps, 结论结论: r ps p s q r sq q化简化简化简化简前提引入前提引入假言推理假言推理前提引入前提引入假言推理假言推理析取三段论析取三段论前提引入前提引入 p(q r) r 3.2 自然推理系统自然推理系统 ps p s p(q r) q r sq q r ps ps p s p(q r) q r sq q r证明序列证明序列证明树证明树前提前提: p (q r), sq, ps, 结论结论: r 3.2 自然推理系统自然推理系统P 中证明的两个间接证明法中证明的两个间接证明法:附加前提证明法附加前

18、提证明法, 归谬法归谬法.l附加前提法附加前提法当推理的结论是蕴含式当推理的结论是蕴含式 A B 时时, 可将结论中的前件可将结论中的前件 A 挪作推理的前提挪作推理的前提, 而结论简化为而结论简化为 B.结论结论(目标目标)越简单越简单, 证明过程中的方向感就越强证明过程中的方向感就越强.即将推理即将推理(*)A1, A2, , Ak (AB)改为推理改为推理(*)A1, A2, , Ak , A B 3.2 自然推理系统自然推理系统附加前提法附加前提法正确性的证明正确性的证明: (A1 A2 Ak) (AB)(*)(*)式与式与(*)式是等值的式是等值的, 因而有相同的永真性因而有相同的永

19、真性, 从而从而推理推理 (*)与推理与推理 (*)有相同的有效性有相同的有效性. (A1 A2 Ak) ( A B) (A1 A2 Ak)A B (A1 A2 Ak A) B (A1 A2 Ak A) B(*) 3.2 自然推理系统自然推理系统例例6 在自然推理系统在自然推理系统 P 中构造下面推理的证明中构造下面推理的证明. 小小张和小王去张和小王去(看电影看电影)的话小李就一定去的话小李就一定去; 小赵不去小赵不去或小张去或小张去; 小王去小王去. 所以所以, 小赵去小李就一定去小赵去小李就一定去.解解 设设 p: 小张去小张去; q: 小王去小王去; r: 小李去小李去; s: 小赵去

20、小赵去.前提前提: (p q) r, s p, q 结论结论: s r s s p p (p q) r q p q r附加前提引入附加前提引入前提引入前提引入析取三段论析取三段论前提引入前提引入前提引入前提引入合取合取假言推理假言推理证明证明: 用附加前提证明法用附加前提证明法. 3.2 自然推理系统自然推理系统l归谬法归谬法(反证法反证法) 在构造推理在构造推理A1, A2, , Ak B的证明中的证明中, 如果将如果将 B 作为前提能推出矛盾式来作为前提能推出矛盾式来, 比比如说得出如说得出 (AA), 则说明推理正确则说明推理正确. 因为因为 (A1 A2 Ak) B (A1 A2 Ak

21、) B (A1 A2 Ak B)若若 (A1 A2 Ak B) 为矛盾式为矛盾式, 则则 (A1 A2 Ak) B 为重言式为重言式, 即即 A1, A2, , Ak B. 3.2 自然推理系统自然推理系统例例7 归谬法证明下面推理归谬法证明下面推理:(1)前提前提: p q, r q, r s 结论结论: p(2)前提前提: p q, p r, q s 结论结论: r s 解解 3.2 自然推理系统自然推理系统例例7 (2)前提前提: p q, p r, q s 结论结论: r s 3.2 自然推理系统自然推理系统4.1 一阶逻辑命题的符号化一阶逻辑命题的符号化4.2 一阶逻辑公式及解释一阶

22、逻辑公式及解释个体词个体词是指独立存在的客体是指独立存在的客体, 例如小王例如小王, 中国中国, 2.个体常项个体常项:特定特定, 用用 a, b, c, 表示表示;个体变项个体变项:泛指泛指, 用用 x, y, z, 表示表示.个体域个体域 (论域论域): 个体变项的取值范围个体变项的取值范围.l有一个特殊的个体域有一个特殊的个体域, 它由宇宙间一切事物组成它由宇宙间一切事物组成, 称为称为全总个体域全总个体域.本课中默认本课中默认个体域为全总个体域个体域为全总个体域. 个体词个体词individual, individual constant, individual variable, d

23、omain of individuals, domain of discourse, universel谓词谓词刻画个体性质或个体之间相互关系刻画个体性质或个体之间相互关系.l谓词常项谓词常项表示特指点的性质或关系表示特指点的性质或关系.l谓词变项谓词变项表示泛指的性质或关系表示泛指的性质或关系.l谓词常项或变项都用大写拉丁字母谓词常项或变项都用大写拉丁字母 F, G, H, 表示表示, 由上下文区分由上下文区分.谓词谓词/predicate /predicate constant /predicate variable谓词谓词考虑下面四个句子考虑下面四个句子(命题命题?):(1) 2是无理数

24、是无理数. (2) x 是有理数是有理数.(3)小王与小李同岁小王与小李同岁. (4) x 与与 y 具有关系具有关系 L.(1) F( 2), 其中其中F: “是无理数是无理数”,(2) G(x), 其中其中G: “是有理数是有理数”, (3) H(a, b), 其中其中 H: “与与同岁同岁”, a: 小王小王, b: 小小李李. (4) L(x, y), 其中其中L: “与与具有关系具有关系L”.一元谓词一元谓词 F(x) 表示表示 x 具有具有性质性质 F.二元谓词二元谓词 F(x, y) 表示个体变项表示个体变项 x, y 具有具有关系关系 F.n 元谓词元谓词 F(x1, x2,

25、, xn) 表示表示 x1, x2, , xn 具有关系具有关系 F.n 元谓词元谓词 F(x1, x2, , xn) 可看成是以个体域为定义域可看成是以个体域为定义域, 以以 0, 1 为值域的为值域的 n 元函数元函数.l不带个体变项的谓词称为不带个体变项的谓词称为 0 元谓词元谓词, 例如例如, F(a), G(a, b), P(a1, a2, , an).l不含不含(个体或谓词个体或谓词)变项的变项的谓词谓词(即即0 元谓词元谓词)叫做叫做命题命题: P(a1, a2, , an) 是命题是命题, 其中其中 P 是谓词常项是谓词常项.例例1 将下列句子将下列句子(命题命题?)在一阶逻辑

26、中用在一阶逻辑中用0元谓词符元谓词符号化号化, 并讨论它们的真值并讨论它们的真值:(1)只有只有2是素数是素数, 4才是素数才是素数.(2)如果如果5大于大于4, 则则4大于大于6.解解 (1) 设一元谓词设一元谓词 F(x): x 是素数是素数, a: 2, b: 4.句子符号化为句子符号化为F(b) F(a).此蕴涵式前件为假此蕴涵式前件为假, 所以该命题为真所以该命题为真.(2) 设二元谓词设二元谓词 G(x, y): x 大于大于 y, a: 4, b: 5, c: 6.句子符号化为句子符号化为G(b, a) G(a, c),G(b, a) 为真为真, 而而 G(a, c) 为假为假,

27、 所以该命题为假所以该命题为假.量词量词表示个体常项或变项之间数量关系表示个体常项或变项之间数量关系.本课程介绍两种量词本课程介绍两种量词:(1) 全称量词全称量词 x表示个体域里的所有个体表示个体域里的所有个体, 而而 xF(x) 表示个体域里所有个体都有性质表示个体域里所有个体都有性质 F.中文中文: “一切的一切的”, “所有的所有的”, “每一个每一个”, “任意任意的的”, “凡凡”, “都都”等等. (2) 存在量词存在量词 x 表示个体域里有的个体表示个体域里有的个体, 而而 xF(x) 表示个体域里存在个体具有性质表示个体域里存在个体具有性质 F.中文中文: “存在存在”, “

28、有一个有一个”, “有的有的”, “至少有一个至少有一个”等等.量词量词这里的这里的“存在存在”是是“至少存在一个至少存在一个”, 可可以是多个以是多个./quantifier /universal quantifier /existential quantifier例例2 在条件在条件(a)和和(b)下分别将下面两个命题符号化下分别将下面两个命题符号化: (1) 凡人都呼吸凡人都呼吸. (2) 有的人用左手写字有的人用左手写字.其中其中: (a)个体域为人类集合个体域为人类集合; (b)个体域为全总个体域个体域为全总个体域.解解 令令F(x): x 呼吸呼吸. G(x): x 用左手写字用左

29、手写字. M(x): x 是人是人.(a)(1) xF(x).(2) xG(x).(b) (1)可另述为可另述为: 对于宇宙间每个事物对于宇宙间每个事物, 如果该事物如果该事物是人是人, 则他要呼吸则他要呼吸. 符号化为符号化为 x(M(x) F(x), 这里这里特性谓词特性谓词M(x) 将所述事物与其他事物区分开来将所述事物与其他事物区分开来.(2)可另述为可另述为: 在宇宙间存在着用左手写字的人在宇宙间存在着用左手写字的人. 符号符号化为化为 x(M(x) G(x).同个命题在不同个体域中符号化形式可能不同同个命题在不同个体域中符号化形式可能不同./attribute predicate在

30、全总域中符号化时往往需要使用特性谓词在全总域中符号化时往往需要使用特性谓词, 且且全称量词后跟着蕴涵式全称量词后跟着蕴涵式, 而存在量词后跟着合取式而存在量词后跟着合取式.例例2 (1) 凡人都呼吸凡人都呼吸. (2) 有的人用左手写字有的人用左手写字.在在(b)个体域个体域 D2 为全总个体域时为全总个体域时,(1)符号化为符号化为 x(M(x) F(x). (2)符号化为符号化为 x(M(x) G(x).(1)能否符号化为能否符号化为 x(M(x) F(x)? (*)(2)能否符号化为能否符号化为 x(M(x) G(x)? (*)(*)意为意为“凡是个体都是人凡是个体都是人, 并且是呼吸的

31、并且是呼吸的.”(*)意为意为“存在个体存在个体, 如果它是人如果它是人, 那么它用左手写字那么它用左手写字”.例例3 符号化命题并判断其真值符号化命题并判断其真值: 存在存在 x, 使得使得 x + 5 = 3.个体域为个体域为 (a) (自然数集合自然数集合), (b) (实数集合实数集合).解解 令令 F(x): x+5 = 3.(a) xF(x), 假命题假命题.(b) xF(x), 真命题真命题.同一个命题同一个命题, 在不同个体域中的真值可能不同在不同个体域中的真值可能不同.例例5 将下列命题符号化将下列命题符号化:(1) 兔子比乌龟跑得快兔子比乌龟跑得快.(2) 有的兔子比所有的

32、乌龟跑得快有的兔子比所有的乌龟跑得快.(3) 并不是所有的兔子都比乌龟跑得快并不是所有的兔子都比乌龟跑得快.(4) 不存在跑得同样快的两只兔子不存在跑得同样快的两只兔子.解解 令令F(x): x 是兔子是兔子, G(y): y 是乌龟是乌龟, H(x, y): x 比比 y 跑得快跑得快, L(x, y): x 与与 y 跑得一样快跑得一样快.(1) x y(F(x) G(y) H(x, y);(2) x(F(x) y(G(y) H(x, y);(3) x y(F(x) G(y) H(x, y);(4) x y(F(x) F(y) L(x, y).QEI量词顺序不能随意调换量词顺序不能随意调换

33、.设个体域为设个体域为, H(x, y): x + y = 0, 则则 x yH(x, y) 与与 y xH(x, y) 含义不同含义不同, 前者为真前者为真, 后者为假后者为假.有些命题的符号化形式不止一种有些命题的符号化形式不止一种.设设 H(x): x 是人是人, P(x): x 是完美的是完美的, 则则 “人无完人人无完人”可可以符号化为以符号化为x(H(x) P(x) 或或 x (H(x) P(x).(下一章将证明这两式是等值的下一章将证明这两式是等值的).苏格拉底三段论苏格拉底三段论: 人都是要死的人都是要死的; 苏格拉底是人苏格拉底是人;所以所以, 苏格拉底是要死的苏格拉底是要死

34、的.令令 M(x): x 是要死的是要死的; H(x): x 是人是人; s = 苏格拉底苏格拉底.该三段论符号化为该三段论符号化为 x(H(x) M(x) H(s) M(s).(下一章将证明该式是永真式下一章将证明该式是永真式.)4.1 一阶逻辑命题的符号化一阶逻辑命题的符号化4.2 一阶逻辑公式及解释一阶逻辑公式及解释 本节介绍本节介绍一阶谓词逻辑形式系统一阶谓词逻辑形式系统(其中一种的其中一种的)的的语言语言 , 它便于翻译自然语言它便于翻译自然语言. (下一章介绍推理规则下一章介绍推理规则)A = alphabet, E = equation, AX = axiom, R = rule

35、.回顾：回顾：形式系统形式系统 I = A(I), E(I), AX(I), R(I) , 其中其中 A(I), E(I) 是是 I 的的语言系统语言系统, AX(I), R(I) 为为 I 的的演算系统演算系统. 4.2 一阶逻辑公式及解释一阶逻辑公式及解释定义定义4.1 一阶语言一阶语言 的的字母表字母表定义如下定义如下:(1)个体常项个体常项: a, b, c, , ai, bi, ci, , i 1.(2)个体变项个体变项: x, y, z, , xi, yi, zi, , i 1.(3)函数符号函数符号: f, g, h, , fi, gi, hi, , i 1.(4)谓词符号谓词符

36、号: F, G, H, , Fi, Gi, Hi, , i 1.(5)量词符号量词符号: , .(6)联结词符号联结词符号: , , , , .(7)括号与逗号括号与逗号: ( ), , ./alphabet一、一阶语言的概念一、一阶语言的概念定义定义4.2 的的项项的定义如下的定义如下:(1)个体常项和个体变项是项个体常项和个体变项是项.(2)若若 f (x1, x2, , xn) 是任意的是任意的 n 元函数元函数, t1, t2, , tn 是任意的是任意的 n 个项个项, 则则 f (t1, t2, , tn) 是项是项.(3) 有限次使用有限次使用(1), (2)得到的字符串是项得到

37、的字符串是项.定义定义4.3 设设 R(x1, x2, , xn) 是是 的任意的任意 n 元谓词元谓词, t1, t2, , tn 是是 的任意的的任意的 n 个项个项, 则称则称 R(t1, t2, , tn) 是是 的的原子公式原子公式.F(x), G(x, y), H(x, f (y), L(f(x, y), g(z) 是原子公式是原子公式. F(x) G(x, y), xG(x, y)不是原子公式不是原子公式.项的函数是项项的函数是项.项的谓词是原子公式项的谓词是原子公式./term /atomic formula定义定义4.4 的的合式公式合式公式(谓词公式谓词公式, 公式公式)定

38、义如下定义如下:(1)原子公式是合式公式原子公式是合式公式.(2)若若 A 是合式公式是合式公式, 则则 ( A) 也是合式公式也是合式公式.(3)若若 A, B 是合式公式是合式公式, 则则 (A B), (A B), (AB), (AB) 也是合式公式也是合式公式.(4)若若 A 是合式公式是合式公式, 则则 xA, xA 也是合式公式也是合式公式.(5)有限次应用有限次应用(1)(4)构成的字符串是合式公式构成的字符串是合式公式.为图方便为图方便, 对谓词公式往往加以简写对谓词公式往往加以简写.well formed formula/wff, predicate formula, for

39、mula定义定义4.5 在公式在公式 xA 和和 xA 中中, 称称 x 为量词的为量词的指导变指导变元元, A 为量词的为量词的辖域辖域, 在辖域中个体变项在辖域中个体变项 x 的所有出的所有出现都称为现都称为约束出现约束出现, 而其他个体变项而其他个体变项(y, z 等等)都称为都称为是是自由出现自由出现的的.leading variable, scope, bounded occurrence, free occurrence例例6 指出下列各公式中的指导变元指出下列各公式中的指导变元, 各量词的辖域各量词的辖域,自自由出现以及约束出现的个体变项由出现以及约束出现的个体变项:(1) x(

40、F(x, y) G(x, z);(2) x(F(x) G(y) y(H(x) L(x, y, z).二、变元的约束二、变元的约束通常通常 A(x1, x2, , xn) 表示公式中表示公式中 x1, x2, , xn 是自由是自由出现的出现的. 下面的下面的 D D 表示量词表示量词( 或或 ). 公式公式 D Dx1A(x1, x2, , xn) 中中 x2, x3, , xn 是自由是自由出现的出现的, 可记为可记为 A1(x2, x3, , xn). D Dx2D Dx1A(x1, x2, , xn) 可记为可记为 A2(x3, x4, , xn), , D DxnD Dx1A(x1,

41、x2, , xn) 中没有自由出现的个中没有自由出现的个体变项体变项, 可记为可记为 A.u不含自由个体变项的公式称为不含自由个体变项的公式称为封闭的公式封闭的公式(闭式闭式).A(y, z) = x(F(x, y) G(x, z)B(z) = yA(y, z) = y x(F(x, y) G(x, z)C = z yA(y, z) = z y x(F(x, y) G(x, z)closed form闭式否闭式否? x(M(x) G(x),x(F(x) G(x), x y(F(x) G(y) H(x, y)A(y, z) = x(F(x, y) G(x, z),B(x, y, z) = x(F

42、(x) G(y) y(H(x) L(x, y, z) 非闭式加量词后可以变成闭式非闭式加量词后可以变成闭式: y zA(y, z)y z x(F(x, y) G(x, z), x y zB(x, y, z) x y z( x(F(x) G(y) y(H(x) L(x, y, z)./closed formula例例7 将下列公式中的变项指定成常项使其成为命题将下列公式中的变项指定成常项使其成为命题:(1) x(F(x) G(x) (*)(2) x y(F(x) F(y) G(x, y) H(f (x, y), g(x, y)解解 (1)答案不唯一答案不唯一.(a)取个体域取个体域 为全总个体域

43、为全总个体域, F(x): x 是人是人, G(x): x 是是要死的要死的, 则则(*)成为成为“人都是要死的人都是要死的”, 是真命题是真命题.(b)取个体域取个体域 为实数集合为实数集合 , F(x): x 是整数是整数, G(x): x 是自然数是自然数, 则则(*)成为成为“整数都是自然数整数都是自然数”, 是假命题是假命题.(2) x y(F(x) F(y) G(x, y) H(f (x, y), g(x, y). (*)这里这里 f, g 是函数变项是函数变项, F, G, H是谓词变项是谓词变项.取个体域为全总个体域取个体域为全总个体域, F(x): x 是实数是实数, G(x

44、, y): x y, H(x, y): x y, f (x, y) = x2 + y2, g(x, y) = 2xy, 则则(*)成为成为“对于任意的对于任意的 x, y, 若若 x与与 y 都是实数都是实数, 且且 x y, 则则 x2 + y2 2xy”,这是真命题这是真命题.如果如果 H(x, y) 改为改为 x = 3. 所以所以 G 不不v3v2v1v3v2v1 V2V1 解解 这是二部图这是二部图, |V1| |V2| = 9 7 = 2, 所以不存在哈所以不存在哈密尔顿通路密尔顿通路. QEI例例5 5 wv1vluu1 v1vnuv2 0 0 引言引言可行遍性问题可行遍性问题图

45、论的一个特点是它在一些难题和游戏中大量表现出来, 这个特点曾经促进一些论题的普及. F. 哈拉里(美. 1921-2005) 骑士问题骑士问题/knights tour: 在棋盘上连续在棋盘上连续跳动一只马跳动一只马, 使使每个方格恰好每个方格恰好经过一次经过一次, 可否可否?马的两条行走路线马的两条行走路线(阿拉伯文献阿拉伯文献)欧拉欧拉(1759)骑士问题的图骑士问题的图 欧拉图问题: 能否从图中某一顶点出发, 沿着图中的边, 经过所有的边恰好一次?哈密顿图问题: 能否从图中某一顶点出发, 沿着图中的边, 经过所有的顶点恰好一次? 欧拉图欧拉图 半欧拉图半欧拉图欧拉图欧拉图1. 欧拉图的概

46、念欧拉图的概念 上图中，上图中，(1) ,(4) (1) ,(4) 为欧拉图，为欧拉图，(2),(5)(2),(5)为半欧拉图，为半欧拉图，(3),(6)(3),(6)既不是欧拉图，也不是半欧拉图既不是欧拉图，也不是半欧拉图. . 在在(3),(6)(3),(6)中各至少加几条中各至少加几条边才能成为欧拉图？边才能成为欧拉图？ 二、欧拉图的判断二、欧拉图的判断 1 下面两个图都是欧拉图下面两个图都是欧拉图. 从从A点出发点出发, 如何一次成功地如何一次成功地走出一条欧拉回路来？走出一条欧拉回路来？ 图例图例 欧拉图是边不重的圈的并欧拉图是边不重的圈的并.证明证明 参考教材参考教材.PLAY从以

47、上证明不难看出：欧拉图是若干个边不重的圈之从以上证明不难看出：欧拉图是若干个边不重的圈之并，见示意图并，见示意图. 16.1 16.1 无向树及其性质无向树及其性质 16.1无向树及其性质无向树及其性质“有一种简单且重要的图有一种简单且重要的图, 所有作者都把它叫做树所有作者都把它叫做树. 树之所以树之所以重要重要, 不仅因为它在许多不同的领域中有应用不仅因为它在许多不同的领域中有应用, 而且也在于图而且也在于图论本身论本身. 它对图论的重要性的一个原因是它对图论的重要性的一个原因是: 树是一种非常简单树是一种非常简单的图的图, 所以所以在探讨关于图的一般性猜想时可以首先研究树这在探讨关于图的

48、一般性猜想时可以首先研究树这种情形种情形.” F. 哈拉里哈拉里(美美. 1921-2005) 无无简单简单回路的连通无向图叫回路的连通无向图叫树树. .自然界中的树 16.1无向树及其性质无向树及其性质 无回路的无向图叫无回路的无向图叫森林森林, 它的每个连通分支都是树它的每个连通分支都是树.l 树和森林树和森林(无回路无回路)一定是简单图一定是简单图.l 平凡图叫做平凡图叫做平凡树平凡树. .tree, forest, trivial tree 16.1无向树及其性质无向树及其性质本章所说的回路都是初级回路本章所说的回路都是初级回路(圈圈)或简单回路或简单回路. 16.1无向树及其性质无向树及其性质基尔霍夫基尔霍夫(德德.1847)在研究电网时提出在研究电网时提出“生成树生成树”的概念的概念.一个电网络一个电