第一部分 第四五章

1、第四章第四章 一阶逻辑一阶逻辑基本概念基本概念 命题逻辑存在局限命题逻辑存在局限 例子：著名的苏格拉底论断例子：著名的苏格拉底论断 人人都是都是要死的要死的； 苏格拉底苏格拉底是人是人； 所以所以苏格拉底苏格拉底是是要死的要死的。 命题公式：命题公式： （p p q q）rr 不能推出不能推出“该论断是正确的该论断是正确的”! !对原子命题进行分解：对原子命题进行分解： 个体词个体词 “人人”，“苏格拉底苏格拉底” 谓词谓词 “要死的要死的”, “, “是人是人” 量词量词 “所有所有”, “, “存在存在”4.1 4.1 一阶逻辑命题符号化一阶逻辑命题符号化个体词及符号化个体词及符号化定义：

2、个体词定义：个体词是指所研究对象中可以独立存是指所研究对象中可以独立存在的具体的或抽象的在的具体的或抽象的客体客体。 个体常项个体常项：用：用a a、b b、c c表示，具体或特定的表示，具体或特定的客体。客体。 个体变项个体变项：用：用x x、y y、z z表示，抽象或泛指的表示，抽象或泛指的客体。客体。 论域（个体域）论域（个体域）：个体变项的取值范围。：个体变项的取值范围。 全总个体域全总个体域：包含一切事物，是常用的个：包含一切事物，是常用的个体域。体域。例如：例如：1. 1. 3 3是素数。是素数。 （3 3是个体常项）是个体常项）2. 1002. 100是合数。是合数。 （1001

3、00是个体常项）是个体常项）3. x3. x是素数。是素数。 （x x是个体变项）是个体变项）4. x4. x是有理数。是有理数。 （x x是个体变项）是个体变项） 分别考虑论域为：实数集，整数集，分别考虑论域为：实数集，整数集，有理数集。有理数集。谓词及符号化谓词及符号化 谓词谓词：刻划：刻划个体词性质个体词性质或或几个个体词关系几个个体词关系的词。的词。 谓词常用大写英文字母表示。谓词常用大写英文字母表示。例如：例如： 李玲李玲是优秀学生是优秀学生。 张华张华比比李红李红高高。 小赵小赵坐在坐在小王小王和和小刘小刘的中间的中间。符号化：符号化： 用用F F，G G，H H表示上面三个命题中

4、的谓词：表示上面三个命题中的谓词： F F：是优秀学生。是优秀学生。 G G：比比高。高。 H H：坐在坐在和和的中间。的中间。 则则: : (1) F(a) (1) F(a) ：李玲是优秀学生。：李玲是优秀学生。 (2) G(b,c) (2) G(b,c) ：张华比李红高。：张华比李红高。 (3) H(e,f,g)(3) H(e,f,g)：小赵坐在小王和小刘的中间。：小赵坐在小王和小刘的中间。n n元谓词元谓词 n n元谓词：含元谓词：含n n个个体变元的谓词个个体变元的谓词 P P（x x1 1，x x2 2， ，x xn n） x x是个体变元，是个体变元，F(x)F(x)表示表示x x

5、具有性质具有性质F F。 x,yx,y是个体变元，是个体变元，G(x,y)G(x,y)表示表示x x和和y y具有关系具有关系G G。 定理：定理：n n元谓词元谓词n n元函数元函数 定理：定理：0 0元谓词（不含个体变元）命题元谓词（不含个体变元）命题例如：例如： F(x)F(x)：x x是优秀学生。是优秀学生。 （1 1元谓词）元谓词） G(x,y)G(x,y)：x x比比y y高。高。 （2 2元谓词）元谓词） H(x,y,z)H(x,y,z)：x x坐在坐在y y和和z z的中间。的中间。 （3 3元谓词）元谓词） F(a) F(a) ：李玲是优秀学生。：李玲是优秀学生。 （0 0元

6、谓词）元谓词）例题例题【例【例4.14.1】 将下列命题符号化并讨论它们的真值。将下列命题符号化并讨论它们的真值。 2 2与与3 3都是偶数。都是偶数。 如果如果5 5大于大于3 3，则，则2 2大于大于6 6。解：解： 设设 F(x)F(x)：x x是偶数，是偶数， a a：2 2，b b：3 3。 该命题符号化为：该命题符号化为： F(a)F(b)F(a)F(b) 为假命题。为假命题。 设设 G(x,y)G(x,y)： x x大于大于y y a a：5 5，b b：3 3，c c：2 2，d d：6 6 该命题符号化为：该命题符号化为： G(a,b)G(c,d)G(a,b)G(c,d) 为

7、假命题。为假命题。（1 1） 全称量词全称量词日常生活和数学中常用的日常生活和数学中常用的“一切的一切的”，“所有的所有的”，“每一个每一个”，“任意的任意的”，“凡凡”，“都都”等词统称为全称量词等词统称为全称量词将它们符号化为将它们符号化为“ ”用用 x x， y y等表示个体域里的所有个体。等表示个体域里的所有个体。 xF(x) xF(x) 表示个体域中的所有个体都有性表示个体域中的所有个体都有性质质 F F量词及符号化量词及符号化（2 2） 存在量词存在量词“存在存在”，“有一个有一个”，“有些有些”，“至至少有一个少有一个”等词统称为存在量词等词统称为存在量词将它们符号化为将它们符号

8、化为“ ”用用 x x， y y 等表示个体域里的某个个体。等表示个体域里的某个个体。 xF(x) xF(x) 表示个体域中存在个体具有性表示个体域中存在个体具有性质质F F量词及符号化量词及符号化例题例题【例【例4.24.2】个体域分别是个体域分别是(a)(a)与与(b)(b)时，对下列命时，对下列命题符号化。题符号化。 凡人都呼吸。凡人都呼吸。 有的人用左手写字。有的人用左手写字。其中其中（a a）个体域为人类集合；）个体域为人类集合； （b b）个体域为全总个体域。）个体域为全总个体域。 解解 （a a）个体域为人类集合）个体域为人类集合 令令F(x)F(x)：x x呼吸。呼吸。 符号化

9、为：符号化为： xF(x)xF(x) 令令G(x)G(x)：x x用左手写字。用左手写字。 符号化为：符号化为： xG(x)xG(x) 全总个体域需要引入特性谓词全总个体域需要引入特性谓词 （b b）全总个体域全总个体域。 令令M(x)M(x)：x x是人是人。（。（特性谓词特性谓词） （1 1）对于一切事物而言，如果事物是对于一切事物而言，如果事物是人，则他要呼吸人，则他要呼吸。 符号化：符号化： x(M(x)x(M(x)F(x)F(x) （2 2）在宇宙间存在着用左手写字的人在宇宙间存在着用左手写字的人。 符号化：符号化： x(M(x)x(M(x)G(x)G(x)例题例题【例【例4.44.

10、4】将下列命题符号化，并讨论其真值。】将下列命题符号化，并讨论其真值。 (1)(1)所有的人都长着黑头发。所有的人都长着黑头发。 (2)(2)有的人登上过月球。有的人登上过月球。 (3)(3)没有人登上过木星。没有人登上过木星。 (4)(4)在美国留学的学生未必都是亚洲人。在美国留学的学生未必都是亚洲人。提示：全总个体域中特性谓词加入的方法提示：全总个体域中特性谓词加入的方法 对全称量词，特性谓词作为对全称量词，特性谓词作为蕴涵式蕴涵式的前件加入。的前件加入。 对存在量词，特性谓词作为对存在量词，特性谓词作为合取项合取项加入。加入。例题例题 (1)(1)所有的人都长着黑头发。所有的人都长着黑头

11、发。 x(M(x)x(M(x)F(x) F(x) （真值为（真值为0 0） (2)(2)有的人登上过月球。有的人登上过月球。 x(M(x)x(M(x)G(x) G(x) （真值为（真值为1 1） (3)(3)没有人登上过木星。没有人登上过木星。 x(M(x)x(M(x)H(x) H(x) x(M(x)x(M(x) H(x) H(x) （真值为（真值为1 1） (4)(4)在美国留学的学生未必都是亚洲人。在美国留学的学生未必都是亚洲人。 x(F(x)x(F(x)G(x) G(x) （真值为（真值为1 1） x(F(x)x(F(x)G(x) G(x) 例题例题【例【例4.54.5】将下列命题符号化

12、。】将下列命题符号化。 (1)(1)兔子比乌龟跑得快兔子比乌龟跑得快。 (2)(2)有的兔子比所有的乌龟跑得快。有的兔子比所有的乌龟跑得快。 (3)(3)并不是所有的兔子都比乌龟跑得快。并不是所有的兔子都比乌龟跑得快。 (4)(4)不存在跑得同样快的两只兔子。不存在跑得同样快的两只兔子。 （1 1） x x y y(F(x)G(y)H(x,y)(F(x)G(y)H(x,y) （2 2） x(F(x)x(F(x) y(y(G(y)H(x,y)G(y)H(x,y) （3 3） x x y y(F(x)G(y)H(x,y)(F(x)G(y)H(x,y) x x y y(F(x)G(y)(F(x)G(

13、y) H(x,y) H(x,y) （4 4） x x y y(F(x)F(y)L(x,y)(F(x)F(y)L(x,y) x x y y(F(x)F(y)(F(x)F(y) L(x,y) L(x,y)练习练习将下列命题符号化将下列命题符号化。 (1)(1)火车都比轮船快。火车都比轮船快。 (2)(2)有火车比有的汽车快。有火车比有的汽车快。 (3)(3)不存在比所有火车都快的汽车。不存在比所有火车都快的汽车。 (4)(4)说凡是汽车就比火车慢是不对的。说凡是汽车就比火车慢是不对的。 (5)(5)苏格拉底论断：苏格拉底论断： 人都是要死的；人都是要死的； 苏格拉底是人；苏格拉底是人； 所以苏格拉

14、底是要死的。所以苏格拉底是要死的。4.2 4.2 一阶逻辑公式及其解释一阶逻辑公式及其解释定义定义4.1 4.1 设设 L L 是一个非逻辑符号集合，由是一个非逻辑符号集合，由 L L 生生成的一阶语言的成的一阶语言的字母表字母表包括如下符号：包括如下符号：非逻辑符号非逻辑符号 (1) L (1) L 中的中的个体常元个体常元符号，常用符号，常用a a，b b，c c表示表示 (2) L (2) L 中的中的函数符号函数符号，常用，常用f f，g g，h h表示表示 (3) L (3) L 中的中的谓词符号谓词符号，常用，常用F F，G G，H H表示表示 谓词公式：谓词公式： x x y y

15、( F(x)G(y)H(x,y) )( F(x)G(y)H(x,y) ) x F( x F( g(x,a),g(x,a),z )z ) F( F( f(x,a),f(x,a),y ) H( y ) H( g(x,y),g(x,y),z )z ) 字母表字母表定义定义4.1 4.1 设设L L是一个非逻辑符号集合，由是一个非逻辑符号集合，由L L生成生成的一阶语言的字母表的一阶语言的字母表包括如下符号：包括如下符号：逻辑符号逻辑符号 (4)(4)个体变元个体变元符号：符号：x x，y y，z z (5) (5)量词量词符号：符号： ， (6) (6)联结词联结词符号：符号： ， (7) (7)逗

16、号和圆括号逗号和圆括号原子公式原子公式定义定义4.2 4.2 项的定义项的定义： 个体变元或个体常元是项。个体变元或个体常元是项。 如果如果f f是是n n元函数，元函数，t t1 1，t t2 2，t tn n是项，是项， 则则f f（t t1 1，t t2 2，t tn n）是项。）是项。 所有的项由且仅由有限次使用（所有的项由且仅由有限次使用（1 1）、（）、（2 2）所）所生成。生成。定义定义4.3 4.3 若若F F是是n n元谓词，元谓词，t t1 1，t t2 2，t tn n是项，是项，则则F(tF(t1 1，t t2 2，t tn n）是）是原子公式原子公式。 F( F( f

17、(x,a),f(x,a),y ) H( y ) H( g(x,y),g(x,y),z )z ) 项项项项原子公式原子公式原子公式原子公式谓词公式谓词公式定义定义4.4 4.4 合式公式合式公式的定义：的定义： 原子公式是合式公式。原子公式是合式公式。 若若A A是合式公式，则（是合式公式，则（A A）是合式公式。）是合式公式。 若若A A和和B B是合式公式，则是合式公式，则(AB)(AB)， (AB)(AB)，(AB)(AB)和和(A(AB)B)是合式公式。是合式公式。 如果如果A A是合式公式，是合式公式， 则则 xAxA， xAxA是合式公式。是合式公式。 有限次地应用有限次地应用、所得

18、的公所得的公式是合式公式。式是合式公式。约束出现与自由出现约束出现与自由出现定义定义4.5 4.5 在公式在公式 xAxA， xAxA中，中，A A称为相应量词的称为相应量词的辖辖域域，x x为为指导变元指导变元。 量词量词 x x和和 x x的辖域内的辖域内x x的一切出现叫的一切出现叫约束约束出现出现，x x叫做约束变元；叫做约束变元； 约束变元以外的其它变元的出现叫约束变元以外的其它变元的出现叫自由自由出现出现，自由出现的变元叫自由变元。，自由出现的变元叫自由变元。例题例题【例】【例】说明下列各式量词的辖域，找出约束变说明下列各式量词的辖域，找出约束变元和自由变元。元和自由变元。 xP(

19、x) Q(y) xP(x) Q(y) x( P(x) x( P(x) yQ(x,y) )yQ(x,y) ) xP(x) xP(x) yQ(x,y) yQ(x,y) x x y( P(x,y)Q(y,z) ) y( P(x,y)Q(y,z) ) x R(x,y)x R(x,y) xP(x) R(x,y)xP(x) R(x,y)封闭的公式封闭的公式定义定义4.6 4.6 设设A A是任意的公式，若是任意的公式，若A A中不含自由出现中不含自由出现的个体变项，则称的个体变项，则称A A为为封闭的公式封闭的公式，简称，简称闭式。闭式。定理定理4.1 4.1 闭式在任何解释下都变成命题。闭式在任何解释下

20、都变成命题。定义定义4.7 4.7 一个公式的解释就是指定个体域、个体常一个公式的解释就是指定个体域、个体常元、特定的函数与谓词。元、特定的函数与谓词。谓词公式的分类谓词公式的分类定义定义4.84.8 设设A A是任意的公式，若是任意的公式，若A A在任何解释下均为在任何解释下均为真，则称真，则称A A为为永真式永真式（逻辑有效式）。（逻辑有效式）。 若在任何解释下均为假，则称为若在任何解释下均为假，则称为矛盾式矛盾式（永假式）。（永假式）。 若至少存在一个解释使得若至少存在一个解释使得A A为真，则称为真，则称A A是是可满足式可满足式。定理定理4.2 4.2 重言式的代换实例都是永真式，矛

21、盾式的重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。代换实例都是矛盾式。第五章第五章 一阶逻辑一阶逻辑等值演算与推理等值演算与推理 5.1 5.1 一阶逻辑一阶逻辑等值式等值式与置换规则与置换规则 5.2 5.2 一阶逻辑一阶逻辑前束范式前束范式 5.3 5.3 一阶逻辑的一阶逻辑的推理理论推理理论 5.1 5.1 一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则定义定义5.1 5.1 设设 A A、B B 是任意两个谓词公式，对是任意两个谓词公式，对 A A、B B 的任的任何解释，若其真值相同，即何解释，若其真值相同，即 A AB B 是永真式，是永真式，则称则称 A A 与与

22、B B 是等值的，记作是等值的，记作 A AB B 命题逻辑中的重言式的代换实例命题逻辑中的重言式的代换实例 例如：例如：(pq) (pq) ppq q 用用 xP(x)xP(x)代替代替p p， yR(y)yR(y)代替代替q q，( ( xP(x)xP(x) yR(y)yR(y) xP(x)xP(x) yR(y)yR(y)重要的等值式重要的等值式1 1消去量词等值式消去量词等值式 设个体域为有限集设个体域为有限集 a a1 1，a a2 2，a an n ，A(x) A(x) 是含自是含自由变元由变元 x x 的任意谓词公式，有下列等值式成立：的任意谓词公式，有下列等值式成立： xA(x)

23、xA(x)A(aA(a1 1) )A(aA(a2 2) )A(aA(an n) ) xA(x)xA(x)A(aA(a1 1) )A(aA(a2 2) )A(aA(an n) ) 有的兔子有的兔子 xF(x) F(c) c 比所有的乌龟跑得快比所有的乌龟跑得快 y( G(y) H(c,y) ) F(c) y ( G(y) H(c,y) ) x(F(x) y(G(y)H(x,y) 有的兔子比所有的乌龟跑得快。有的兔子比所有的乌龟跑得快。 x(F(x)x(F(x) y(y(G(y)H(x,y)G(y)H(x,y) 重要的等值式重要的等值式2 2量词否定等值式量词否定等值式 A(x) A(x) 是含自

24、由变元是含自由变元 x x 的任意谓词公式，有下列等的任意谓词公式，有下列等值式成立：值式成立： xA(x) xA(x) xA(x)xA(x) xA(x) xA(x) xxA A(x)(x)重要的等值式重要的等值式3.3.量词辖域的收缩与扩张等值式（之一）量词辖域的收缩与扩张等值式（之一） 设设 A(x) A(x) 是含自由变元是含自由变元 x x 的任意谓词公式。的任意谓词公式。B B 是不含变元是不含变元 x x 的谓词公式，则的谓词公式，则 x(A(x)B)x(A(x)B)xA(x)BxA(x)B x(A(x)B)x(A(x)B)xA(x)BxA(x)B x(A(x)B)x(A(x)B)

25、 xA(x)BxA(x)B x(BA(x)x(BA(x)BB xA(x)xA(x) 重要的等值式重要的等值式3.3.量词辖域的收缩与扩张等值式（之二）量词辖域的收缩与扩张等值式（之二） 设设 A(x )A(x )是含自由变元是含自由变元 x x 的任意谓词公式。的任意谓词公式。B B 是不含变元是不含变元 x x 的谓词公式，则的谓词公式，则 x(A(x)B)x(A(x)B)xA(x)BxA(x)B x(A(x)B)x(A(x)B)xA(x)B xA(x)B x(A(x)B)x(A(x)B) xA(x)B xA(x)B x(BA(x)x(BA(x)BB xA(x)xA(x) 重要的等值式重要的

26、等值式4.4.量词分配等值式量词分配等值式 设设 A(x) A(x) 和和 B(x) B(x) 是含自由变元是含自由变元 x x 的的任意谓词公式，则任意谓词公式，则 x(A(x)x(A(x)B(x)B(x)xA(x)xA(x) xB(x)xB(x) x(A(x)x(A(x)B(x)B(x)xA(x)xA(x) xB(x)xB(x) 三条规则三条规则1.1.置换规则置换规则 设设 （A A）是一个含有公式）是一个含有公式A A的公式的公式 （B B）是用公式）是用公式B B置换了置换了 （A A）中的）中的公式公式A A后得到的公式后得到的公式如果如果A A B B，那么，那么 （A A） （

27、B B） 三条规则三条规则2.2.换名规则换名规则 为了使换名后的公式中出现的变元为了使换名后的公式中出现的变元要么要么是约束的，要么是自由的是约束的，要么是自由的，可以换名：，可以换名： 对约束变元可以换名，其更改的范围对约束变元可以换名，其更改的范围是量词的辖域，公式的其余部分不变是量词的辖域，公式的其余部分不变。 换名时一定要更改成辖域中没有出现换名时一定要更改成辖域中没有出现的变元名，最好是公式中没有的变量名。的变元名，最好是公式中没有的变量名。 三条规则三条规则3.3.代替规则代替规则 对公式中的自由变元也可以进行更改，对公式中的自由变元也可以进行更改，用来解决公式中用来解决公式中约

28、束变元与自由变元的约束变元与自由变元的同名同名问题。问题。 对于谓词公式中的对于谓词公式中的自由变元自由变元可以代入，可以代入，代入时需对公式中该变元自由出现的每代入时需对公式中该变元自由出现的每处进行。处进行。 代入的变元与原公式中其他变元的名代入的变元与原公式中其他变元的名称不能相同。称不能相同。 例题例题【例【例5.15.1】 将公式化成等值的公式，使其没有既是约束将公式化成等值的公式，使其没有既是约束出现又是自由出现的个体变元。出现又是自由出现的个体变元。 （1 1） xF(x,y,z)xF(x,y,z) yG(x,y,z)yG(x,y,z) （2 2） x(F(x,y)x(F(x,y

29、) yG(x,y,z)yG(x,y,z)例题例题【例【例5.25.2】证明：】证明： x(A(x)B(x)x(A(x)B(x)xA(x)xA(x) xB(x) xB(x) x(A(x)B(x)x(A(x)B(x)xA(x)xA(x) xB(x)xB(x) 反例反例：论域为自然数集合：论域为自然数集合 A(x):xA(x):x是奇数是奇数 B(x):xB(x):x是偶数是偶数蕴含关系（推理定律）：蕴含关系（推理定律）： xA(x) xB(x) x(A(x) B(x) ) x(A(x)B(x) xA(x) xB(x) 例题例题【例【例5.35.3】 设个体域为设个体域为D=a,b,c,D=a,b,

30、c,将下面公式将下面公式的量词消去：的量词消去： （1 1） x(F(x)x(F(x)G(x) G(x) （2 2） x(F(x)x(F(x) y yG(y)G(y) （3 3） x x yF(x,y)yF(x,y)例题例题【例【例5.55.5】证明各等值式：证明各等值式： （1 1） x(M(x)F(x)x(M(x)F(x) x(M(x) F(x)x(M(x) F(x) （2 2） x(F(x)G(x)x(F(x)G(x) x(F(x)G(x)x(F(x)G(x) （3 3） x x y y(F(x)G(y)H(x,y) (F(x)G(y)H(x,y) x x y y(F(x)G(y) H(

31、x,y)(F(x)G(y) H(x,y) （4 4） x x y y(F(x)F(y)L(x,y) (F(x)F(y)L(x,y) x x y y(F(x)F(y) L(x,y)(F(x)F(y) L(x,y)练习练习设个体域为设个体域为D=a,b,c,D=a,b,c,将下面公式的将下面公式的量词消去量词消去： （1 1） x x y(F(x)y(F(x)G(y) G(y) （2 2） x x y y(F(x)(F(x)G(y)G(y) （3 3） xF(x)xF(x) yG(y)yG(y) （4 4） x(F(x,y)x(F(x,y) yG(y)yG(y)思考题思考题 函数极限的定义：函数极

32、限的定义：a a 是是 f(x) f(x) 在在 x x0 0 的极限。的极限。2. b 2. b 不是不是 f(x) f(x) 在在 x x0 0 的极限。的极限。3. b 3. b 不是数列的极限。不是数列的极限。5.2 5.2 一阶逻辑前束范式一阶逻辑前束范式定义定义5.2 5.2 一个公式，如果量词均在全式的开头，一个公式，如果量词均在全式的开头，它们的作用域延伸到整个公式的末尾，它们的作用域延伸到整个公式的末尾，则称为则称为前束范式前束范式。 前束范式可表示成如下形式：前束范式可表示成如下形式： Q Q1 1x x1 1Q Q2 2x x2 2QQk kx xk kB B 其中其中Q

33、 Qi i（1ik1ik）是量词，）是量词，B B是不含量词是不含量词的公式。的公式。前束范式存在定理前束范式存在定理 定理定理5.1 5.1 任何谓词公式任何谓词公式, ,都可以化成与其等值的前都可以化成与其等值的前束范式束范式。 【例【例5.65.6】求下面公式的前束范式：】求下面公式的前束范式： （1 1） xF(x)xF(x) xG(x) xG(x) （2 2） xF(x)xF(x) xG(x)xG(x)例题例题【例【例5.75.7】求下面公式的前束范式：】求下面公式的前束范式： （1 1） xF(x)xF(x) xG(x) xG(x) （2 2） xF(x)xF(x) xG(x)xG

34、(x) （3 3） xF(x)xF(x) xG(x)xG(x) （4 4） xF(x)xF(x) yG(y)yG(y)练习练习求下面公式的前束范式：求下面公式的前束范式： （1 1） xF(x,y)xF(x,y) yG(x,y)yG(x,y) （2 2） xF(x)xF(x) yG(x,y)yG(x,y) 5.3 5.3 一阶逻辑的推理理论一阶逻辑的推理理论推理的形式结构与正确的推理推理的形式结构与正确的推理 在一阶逻辑中，由前提在一阶逻辑中，由前提A A1 1，A A2 2，A An n推出推出结论结论B B的的形式结构形式结构仍然是仍然是 A A1 1AA2 2AAn n B B 如果此式

35、是如果此式是永真式永真式，则称，则称 由由A A1 1，A A2 2，A An n推出推出B B的推理正确的推理正确 正确的推理记作正确的推理记作 A A1 1AA2 2AAn n B B自然推理系统自然推理系统 N N定义定义5.3 5.3 一个自然推理系统一个自然推理系统 N N 由三部分组成：由三部分组成： 1.1.字母表；字母表； 2.2.合式公式；合式公式； 3.3.推理规则：推理规则： 前提引入前提引入 结论引入结论引入 置换规则置换规则 假言推理假言推理 附加附加 化简化简 拒取式拒取式 假言三段论假言三段论 析取三段论析取三段论 二难推理二难推理 合取引入合取引入 （关于量词的

36、规则）（关于量词的规则） - - 规则；规则； + + 规则规则 - - 规则；规则； + + 规则规则推理规则推理规则 全称量词消去规则（全称量词消去规则（ - -）之一）之一 xA(x)xA(x) - - A(c) A(c)成立的条件：成立的条件： c c 是个体域中是个体域中任一任一个体。个体。 用用 c c 取代取代 A(x) A(x) 中中 x x 时，一定时，一定在在 x x 出现的所有地方进行取代。出现的所有地方进行取代。推理规则推理规则 全称量词消去规则（全称量词消去规则（ - -）之二）之二 xA(x)xA(x) - - A(y) A(y) y y 为任意的不在为任意的不在

37、A(x) A(x) 中约束出现中约束出现的个体变项。的个体变项。推理规则推理规则 全称量词引入规则（全称量词引入规则（ + +） A(x)A(x) - - xA(x)xA(x) 若对个体域中每一个个体若对个体域中每一个个体 c c，A(c) A(c) 为真，为真，则则 xA(x) xA(x) 为真。为真。 应用本规则时，必须能保证前提应用本规则时，必须能保证前提 A(x) A(x) 对论域中的每个可能的对论域中的每个可能的 x x 都是真的。都是真的。推理规则推理规则 存在量词消去规则（存在量词消去规则（ - -） xA(x)xA(x) - - A(c) A(c) c c 是使是使 A A 为

38、真的为真的特定特定的个体常项。的个体常项。推理规则推理规则 存在量词引入规则（存在量词引入规则（ + +）之一）之一 A(c)A(c) - - xA(x)xA(x) c c 是某个确定的个体是某个确定的个体, ,若若 A(c) A(c) 为真为真, ,则则 xA(x) xA(x) 为真。为真。推理规则推理规则 存在量词引入规则（存在量词引入规则（ + +）之二）之二 A(y)A(y) - - xA(x)xA(x) 证明证明: (1) A: (1) A(y) (y) 前提引入前提引入 (2) (2) xA(x) xA(x) （1 1） + + (3) (3) A(c)A(c) （2 2） - -

39、 (4) (4) xA(x) xA(x) （3 3） + +可由其它可由其它规则推出规则推出推理规则推理规则 存在量词引入规则（存在量词引入规则（ + +）之三、之四）之三、之四 B B A(y)A(y) - - B B xA(x)xA(x) B B A(c)A(c) - - B B xA(x)xA(x) 通过附加前提，可通过附加前提，可由其它规则推出由其它规则推出例题例题【5.95.9】构造下面推理的证明：】构造下面推理的证明： 任何自然数都是整数，任何自然数都是整数， 存在着自然数，存在着自然数， 所以存在着整数。所以存在着整数。 （个体域为实数集合（个体域为实数集合R.R.） 设设F(x

40、):xF(x):x为自然数；为自然数； G(x)G(x)：x x为整数为整数 前提：前提： x(F(x)x(F(x)G(x),G(x), xF(x)xF(x) 结论：结论： xG(x)xG(x) 证明证明: (1) : (1) xF(x) xF(x) 前提引入前提引入 (2) F(c)(2) F(c) （1 1） - - (3) (3) x(F(x)x(F(x)G(x) G(x) 前提引入前提引入 (4) F(c)G(c)(4) F(c)G(c) （3 3） - - (5) G(c) (5) G(c) （2 2）（）（4 4）假言推理）假言推理 (6) (6) xG(x) xG(x) （5 5

41、） + +练习练习 在自然推理系统中，构造下面推理的证明：在自然推理系统中，构造下面推理的证明： 1.1.前提前提: : x(F(x)x(F(x)G(x),G(x), x(F(x)x(F(x)H(x) H(x) 结论结论: : x(G(x)x(G(x)H(x) H(x) 2. 2.前提前提: : x(M(x)x(M(x)F(x),F(x), M(a)M(a) 结论结论: : F(a)F(a) 3. 3.前提前提: : x(F(x)x(F(x)G(x),G(x), xF(x)xF(x) 结论结论: : xG(xxG(x) ) 注意：存在量词与全称量词的消去次序注意：存在量词与全称量词的消去次序

42、例题例题【例【例5.115.11】构造下面推理的证明：构造下面推理的证明： 不存在能表示成分数的无理数，不存在能表示成分数的无理数， 有理数都能表示成分数，有理数都能表示成分数， 因此有理数都不是无理数。因此有理数都不是无理数。 （论域为实数域）（论域为实数域） 设设 F(x):xF(x):x是无理数，是无理数， G(x):xG(x):x是有理数是有理数 H(x):xH(x):x能表示成分数能表示成分数 前提前提: : x(F(x)x(F(x)H(x)H(x)， x(G(x)x(G(x)HH(x),(x), 结论结论: : x(G(x)x(G(x) F F(x)(x) 注意：规则适用于前束范式

43、注意：规则适用于前束范式附加前提证明法附加前提证明法适用范围：结论为蕴涵式适用范围：结论为蕴涵式 A A1 1AA2 2AAn n (AB)(AB) 将推理形式转化为等值形式：将推理形式转化为等值形式： A A1 1AA2 2AAn n A A B B例题例题在自然推理系统中，构造下面推理的证明：在自然推理系统中，构造下面推理的证明：(1)(1)前提前提: : x(F(x)x(F(x)GG(x),(x), x(G(x)x(G(x)HH(x),(x), 结论结论: : xF(x)xF(x) x xH H(x)(x)(2)(2)前提前提: : x(F(x)x(F(x)GG(x),(x), x(G(

44、x)x(G(x)HH(x),(x), 结论结论: : x(F(x)x(F(x)HH(x)(x) 归谬法归谬法将推理将推理 A A1 1AA2 2AAn nB B 转化为等值形式：转化为等值形式： A A1 1AA2 2AAn nB B0 0例题例题在自然推理系统中，用归谬法构造下面在自然推理系统中，用归谬法构造下面推理的证明：推理的证明：前提前提: : x(F(x)x(F(x)G(x), (x), xG(x) xG(x) 结论结论: : xF(x)xF(x) 练习练习构造下面推理的证明：构造下面推理的证明： 鸟会飞，猴子不会飞；鸟会飞，猴子不会飞； 所以猴子不是鸟所以猴子不是鸟。 提示：提示：首先符号化首先符号化 写出前提与结论写出前提与结论 采用适当的方法证明采用适当的方法证明练习练习鸟会飞，猴子不会飞；鸟会飞，猴子不会飞； 所