(完整版)8一阶逻辑-概念公式4-14-1

1、命题逻辑的局限性命题逻辑的局限性 例：例：第四章第四章 一阶逻辑基本概念一阶逻辑基本概念 4 4.1 .1 一阶逻辑的符号化一阶逻辑的符号化 一、命题的分解一、命题的分解 命题命题( (陈述句）陈述句） 主语主语 和和 谓语谓语 个体个体 和和 谓词谓词 分解为：分解为： 对象对象 及及 对象的性质、特征及关系对象的性质、特征及关系 来讨论命题逻辑所不能反映的命题的内在联系及其微观结构来讨论命题逻辑所不能反映的命题的内在联系及其微观结构二、谓词二、谓词 1. 1.个体个体 个体词是指所研究对象中可以独立存在的具体的或抽象的客体个体词是指所研究对象中可以独立存在的具体的或抽象的客体 1 1）一般

2、用小写字母表示：）一般用小写字母表示：x,y,z,s,t x,y,z,s,t . . 2 2）个体常元和个体变元）个体常元和个体变元 具体的个体或具体的个体或 a,b,c a,b,c。 个体变元个体变元x,y,z.x,y,z.变元变元 3 3）个体域（个体的取值范围）个体域（个体的取值范围） 全总个体域全总个体域2 2谓词谓词：谓词是用来刻划个体词性质及个体词之间相互关系的词：谓词是用来刻划个体词性质及个体词之间相互关系的词 1) 1) 谓词一般用大写字母表示谓词一般用大写字母表示：f f、h h、l l、g g 2) 2)谓词所关联个体的个数谓词所关联个体的个数 谓词所关联的个体个数是一个称

3、该谓词为谓词所关联的个体个数是一个称该谓词为一元谓词一元谓词f(x)f(x)、g(x)g(x) f(x) f(x)：x x是人是人 g(x) g(x)：x x是整数是整数 d(x):x d(x):x是要死的是要死的 谓词所关联的个体个数是两个称该谓词为谓词所关联的个体个数是两个称该谓词为二元谓词二元谓词l(x,y)l(x,y) l(x,y) l(x,y)：x y h(x,y):xx y h(x,y):x比比y y跑的快跑的快 谓词所关联的个体个数是三个称该谓词为谓词所关联的个体个数是三个称该谓词为三元谓词三元谓词h(x,y,z)h(x,y,z) h(x,y,z) h(x,y,z)：x x位于位

4、于y y与与z z之间之间 n n元谓词元谓词t t（x1,x2x1,x2.xn.xn） 前面的命题由于不包含个体变元前面的命题由于不包含个体变元0 0元谓词元谓词 3 3）命题函数）命题函数 谓词中的个体是具体的客体谓词为命题（具有真值）谓词中的个体是具体的客体谓词为命题（具有真值） 谓词中的个体是泛指的任何客体谓词为谓词中的个体是泛指的任何客体谓词为命题函数（不是命题）命题函数（不是命题） （不具有真值）（不具有真值） 其真值由给定的客体所确定其真值由给定的客体所确定 f(xf(x）：）：x x 是无理数是无理数 g g（x x）：）：x x是有理数是有理数 那么那么 f f（22）为真）

5、为真 , f , f（2 2）为假，）为假， g g（e e ）为假、）为假、g g（4 4） 为真为真 l l（x,yx,y）: x: x与与y y是同学是同学, , l l（小王，小李）具有真值（小王，小李）具有真值 l l（x x，y y）不具有真值）不具有真值, ,为命题函数为命题函数 h h（x,y,zx,y,z）: x: x位于位于y y、z z之间，之间， h h（北京，郑州，广州）为假（北京，郑州，广州）为假 h h（郑州，北京，广州）为真（郑州，北京，广州）为真 若若4 4大于大于3 3且且3 3大于大于2 2 ，则，则4 4大于大于2 2 设谓词：设谓词：l l（x,yx,

6、y）: x: x大于大于y, y, 可符号化为：可符号化为：l l（x,yx,y）ll（y,zy,z）ll（x,zx,z）为命题函数）为命题函数 而而 l l（4,34,3）ll（3,23,2）ll（4,24,2）是真命题）是真命题有的谓词虽然含有任意个体，但也具有一定的逻辑真值：有的谓词虽然含有任意个体，但也具有一定的逻辑真值： 任何数任何数如果是整数则一定都是偶数是假命题如果是整数则一定都是偶数是假命题符号化命题符号化命题只有只有2 2是素数，是素数，4 4才是素数才是素数f(x):xf(x):x是素数是素数 a:2 b:4 a:2 b:4 f(b) f(a) f(b) f(a) 真真如果

7、如果5 5大于大于4 4，则，则4 4大于大于6 6 l l（5,45,4） l l（4,64,6）假）假仅有个体与谓词还仅有个体与谓词还不能准确表示一些逻辑问题不能准确表示一些逻辑问题 如：如：n n（x x）：）：x x是整数，是整数， o o（x x）:x:x是偶数是偶数 所有的整数是偶数可符号化为所有的整数是偶数可符号化为 n n（x x） o o（x x） 肯定为假肯定为假 其否定应为真其否定应为真. . 但但 （n n（x x）oo（x x）等值于）等值于 n n（x x）oo（x x） 即：即： 所有的整数且不是偶数也为假所有的整数且不是偶数也为假 主要原因是：主要原因是：没有体

8、现整体和个别的关系没有体现整体和个别的关系 所以在描述时必须所以在描述时必须引入反映数量关系的词引入反映数量关系的词3. 3. 量词量词 1 1）全称量词）全称量词 表示日常生活和数学中常用的表示日常生活和数学中常用的“一切的一切的”，“所有的所有的”，“每一个每一个”、 “任意的任意的”，“凡凡”，“都都”等词可统称为全等词可统称为全称量词称量词 用用xf(x)xf(x)，yg(y)yg(y)等分别表示个体域里所有个体都有性等分别表示个体域里所有个体都有性质质f f和都有性质和都有性质g g 2) 2) 存在量词存在量词- - 表示日常生活和数学中常用的表示日常生活和数学中常用的“存在存在”

9、，“有一个有一个”，“有的有的”，“至少有一个至少有一个”等词统称为存在量词等词统称为存在量词. . 并用并用x x，y y等表示个体域里有的个体，而用等表示个体域里有的个体，而用xf(x)xf(x)，yg(y)yg(y)等分别表示在个体域里存在个体具有性质等分别表示在个体域里存在个体具有性质f f和存在个体和存在个体具有性质具有性质g g等等 4.4.一阶逻辑的符号化一阶逻辑的符号化 要理解自然语言的真实含义，体会出整体和存在的意思要理解自然语言的真实含义，体会出整体和存在的意思 1 1）谓词的设定）谓词的设定 2 2）量词的选定）量词的选定 例：例： 3 3）个体域的选取，在未特别说明情况

10、下一般是指全总个体域）个体域的选取，在未特别说明情况下一般是指全总个体域但对于描述的具体具体要选用适当的但对于描述的具体具体要选用适当的特性谓词特性谓词来进行限定：来进行限定：特性谓词：确定个体对象、性质的谓词（一般为一元谓词）特性谓词：确定个体对象、性质的谓词（一般为一元谓词） f(x) f(x)：x x是人是人 r(x) r(x)：x x是实数是实数 h(x) h(x)：x x是猫是猫 等等4) 4) 从逻辑上一般用全称量词及蕴涵连接词来表示从逻辑上一般用全称量词及蕴涵连接词来表示“所有所有x x具有性质具有性质b b”的情况的情况 5) 5) 从逻辑上一般用存在量词及合取连接词来表从逻辑

11、上一般用存在量词及合取连接词来表示示“某些某些x x具有性质具有性质b b”的情况的情况(6)(6)“对于对于d d中所有中所有x x，y y而言，若而言，若x x有性质有性质f f，y y有性有性质质g g，则，则x x与与y y就有关系就有关系h h”，则符号化为则符号化为 : : x xy(f(x) g(y) h(xy(f(x) g(y) h(x，y)y) 例：猫必捉鼠例：猫必捉鼠 再看再看(7)(7)“对于对于d d中所有中所有x x而言，若而言，若x x有性质有性质f f，就存在，就存在y y有有性质性质g g，使得，使得x x与与y y有关系有关系h h”，符号化为，符号化为: :

12、 x(f(x) x(f(x) y(g(y) h(xy(g(y) h(x，y)y) 例：例： 不存在最大的整数不存在最大的整数 (8)(8)“存在着存在着d d中中x x有性质有性质f f，并且对，并且对d d中所有的中所有的y y而言，如果而言，如果y y有性质有性质g g，则，则x x与与y y就有关系就有关系h h”， 符号化为符号化为: : x(f(x) x(f(x) y(g(y) h(xy(g(y) h(x，y)y) 例：存在最大的整数例：存在最大的整数在使用量词时要注意：在使用量词时要注意：1 1、在不同的个体域，谓词的符号化形式可能不同，而且其真值、在不同的个体域，谓词的符号化形式

13、可能不同，而且其真值也可能不同。也可能不同。2 2、对于未指出个体域时，均认为是全总个体域、对于未指出个体域时，均认为是全总个体域3 3、多个量词出现时不能随意交换它们的位置，否则会得到错误、多个量词出现时不能随意交换它们的位置，否则会得到错误的结论。的结论。作业：作业： 习题四习题四 1 1（奇数）、（奇数）、2 2、4 4（奇数）、（奇数）、5 5（奇数）（奇数）转一阶公式1 1、无法判断一些简单而常见的推理考虑下面的推理：无法判断一些简单而常见的推理考虑下面的推理： 著名的著名的“苏格拉底苏格拉底(socrates(socrates，古希腊哲学家，公元前，古希腊哲学家，公元前470470

14、399)399)论证论证”就是如此：就是如此：p: p: “所有的人总是要死的。所有的人总是要死的。 q: q: 因为苏格拉底是人。因为苏格拉底是人。 r: r: 所以苏格拉底总是要死的。所以苏格拉底总是要死的。”凭直觉就能知道这个结论是真的，但是借助于命题演算的推理理论，却凭直觉就能知道这个结论是真的，但是借助于命题演算的推理理论，却不能推导出这个结论来。不能推导出这个结论来。 即公式即公式 (pq) r (pq) r 并不是重言式并不是重言式2 2、无法了解、无法了解 命题命题 的结构的结构 和内在联系和内在联系(1)(1)张华是个劳动英雄。张华是个劳动英雄。(2)(2)李明是个劳动英雄。

15、李明是个劳动英雄。 两个命题具有共同的性质（内在联系）两个命题具有共同的性质（内在联系） （3 3）x x是个劳动英雄是个劳动英雄 (4) (4)小王与小刘同学小王与小刘同学 张华与李明是同学张华与李明是同学 两个命题具有共同的性质（内在联系：两个命题具有共同的性质（内在联系：x x与与y y是同学是同学 ）命题逻辑将命题看成一个整体，不能研究它的内部结构。命题逻辑将命题看成一个整体，不能研究它的内部结构。 命题命题( (陈述句）陈述句） 主语主语 和和 谓语谓语 将命题的分解开将命题的分解开 个体个体 和和 谓词谓词返回返回 返回返回凡人都呼吸（个体域为人的集合）凡人都呼吸（个体域为人的集合

16、）f(x): x呼吸呼吸 x f(x)x f(x) 没有不呼吸的人没有不呼吸的人没有不怕死的人没有不怕死的人m(x):x是人；是人； f(x): x x不怕死不怕死 x x（m(x) f(x)x(x(m(x) f(x) 凡人都怕死凡人都怕死例：例： 人总是要死的（隐含着所有人的意思）人总是要死的（隐含着所有人的意思）设谓词：设谓词：m(x)m(x)：x x是人是人 d d（x x）:x:x是要死的是要死的 个体域为全总个体域为全总 x ( m（x）d（x）) 例：在美国留学的人未必都是亚洲人例：在美国留学的人未必都是亚洲人 有的人登上过月球有的人登上过月球 在北京工作的并非都是北京人在北京工作

17、的并非都是北京人 没有人登上过木星没有人登上过木星 凡偶数都能被凡偶数都能被2整除整除 6是偶数，是偶数， 所以所以6能被能被2整除整除。对于出现多个变元的情况：对于出现多个变元的情况： 令令f(x)f(x)：x x是兔子，是兔子，g(y)g(y)：y y是乌龟是乌龟 h(x h(x，y)y)：x x比比y y跑得快，跑得快，l(xl(x，y)y)：x x与与y y跑得同样快跑得同样快(1)(1)兔子比乌龟跑得快兔子比乌龟跑得快(2)(2)有的兔子比所有的乌龟跑得快有的兔子比所有的乌龟跑得快(3)(3)并不是所有的兔子都比乌龟跑得快并不是所有的兔子都比乌龟跑得快(4)(4)不存在跑得同样快的两

18、只兔子不存在跑得同样快的两只兔子 这这4 4个命题分别符号化为个命题分别符号化为 x xy( f(x)g(y) h(x,y) ) y( f(x)g(y) h(x,y) ) x(f(x) x(f(x) y(g(y)h(xy(g(y)h(x，y) y) x xy(f(x)g(y)h(xy(f(x)g(y)h(x，y) y) x xy(f(x)f(y)l(xy(f(x)f(y)l(x，y)y) 任何两个兔子跑的不同样快任何两个兔子跑的不同样快 返回返回 4 4.2 一阶逻辑公式及解释一阶逻辑公式及解释一、一阶语言一、一阶语言f f定义（字母表）定义（字母表） (1) (1)个体常项：个体常项：a,b

19、,c,da,b,c,d，a1,a2a1,a2，ai i1ai i1 (2) (2)个体变项：个体变项：x x，y y，z z，xixi，yiyi，zizi， i1 i1 (3) (3)函数符号：函数符号：f f，g g，h h，fifi，gigi，hihi， i1 i1 (4) (4)谓词符号：谓词符号：f f，g g，h h，fifi，gigi，hihi， i1 i1 (5) (5)量词符号：量词符号：， (6) (6)联结词符号：联结词符号：，1. f 1. f 下的合式公式定义如下：下的合式公式定义如下： (1) (1)原子公式是合式公式原子公式是合式公式 (2) (2)若若a a是合式

20、公式，则是合式公式，则(a)(a)也是合式公式也是合式公式 (3) (3)若若a a，b b是合式公式，则是合式公式，则(ab)(ab)，(a b)(a b)，(ab)(ab)， (a (a b) b)也是合式公式也是合式公式 (4) (4)若若a a是合式公式，则是合式公式，则xaxa，xaxa也是合式公式也是合式公式 (5) (5)只有有限次地应用只有有限次地应用(1)(4)(1)(4)构成的符号串才是合式公式构成的符号串才是合式公式 合式公式也称为谓词公式，简称公式合式公式也称为谓词公式，简称公式2 2、量词的辖域、量词的辖域: :量词所界定的量词所界定的子公式子公式3 3、自由变项自由

21、变项和和约束变项约束变项： 在公式在公式xaxa和和xaxa中，称中，称x x为指导变元，为指导变元，a a为相应量词的辖域为相应量词的辖域 在在x x和和x x的的辖域中辖域中，x x的所有出现都称为的所有出现都称为约束出现约束出现， a a中不是约束出现的其他变项均称为是中不是约束出现的其他变项均称为是自由出现的自由出现的 例例 考察下面谓词公式考察下面谓词公式 (1)( (1)(x)p(xx)p(x，y y) p(x) p(x，y)y)中的中的y y为自由变项为自由变项，x x为约束为约束的的 (2)( (2)(x)(p(x)(x)(p(x)(y)r(xy)r(x，y)y) x,yx,y

22、均为约束变元均为约束变元 (3)( (3)(x)(p(x)r(x)(p(x)r(y y)()(y)(f(y)(f(x x)q(y) )q(y) p(x) p(x)中的中的x x为约束的，为约束的， r(y) r(y)中的中的y y为自由变元为自由变元 f(x)q(y) f(x)q(y) 中的中的x x为自由的，为自由的，y y为约束的为约束的 公式中的公式中的x x与与y y均为双重身份（均为双重身份（即自由又约束即自由又约束） (4)( (4)(x)p(x)q(x)p(x)q(x x) ) (5) (5) x x y( r(x,y)l(y,y( r(x,y)l(y,z z) ) )x h(x

23、,x h(x,y y) ) 二、公式的、公式的解释解释（相当于命题公式的（相当于命题公式的赋值赋值） 按合式公式的形成规则形成的符号串是按合式公式的形成规则形成的符号串是f f中的公式，这种公中的公式，这种公式没有确定意义一旦式没有确定意义一旦将其中的变项将其中的变项( (项的变项，谓词变项等项的变项，谓词变项等) )用指定的常项代替用指定的常项代替后，所得公式就具备一定意义，有时就后，所得公式就具备一定意义，有时就变成变成命题了命题了 一个一个解释解释不外乎不外乎指定个体域、个体域中一些特定的元素、特定指定个体域、个体域中一些特定的元素、特定的函数和谓词等部分的函数和谓词等部分1 1、公式的

24、解释、公式的解释 1 1）定义：）定义：f f的解释的解释i i的内容一般由下面的内容一般由下面4 4部分组成：部分组成： (a) (a)指定非空个体域指定非空个体域d di i （个体域的取值范围个体域的取值范围） (b) (b)指定指定d di i中一些特定元素中一些特定元素( (常量常量) )的集合的集合a1,a2a1,a2，aiai (c) (c)给定给定d di i上特定函数集合上特定函数集合ffi i | i 1 | i 1 具体的函数具体的函数 (d) (d)给定给定d di i上特定谓词的集合上特定谓词的集合 h hi i | i1 | i1 具体的谓词具体的谓词 在解释在解释

25、i i下的公式下的公式a a中的个体变项均取值于中的个体变项均取值于d di i 被解释被解释i i下的公式不一定全部包含解释中的四部分下的公式不一定全部包含解释中的四部分4 4、闭式定义、闭式定义 设设a a是公式，若是公式，若a a中中不含自由出现的个体变项则不含自由出现的个体变项则称称a a为为封闭封闭的的公式，简称公式，简称闭式闭式 闭式在给定的解释中都变成了命题闭式在给定的解释中都变成了命题( (具有真值）具有真值）结论：结论： 定理定理4 41 1 封闭的公式在任何解释下都变成命题封闭的公式在任何解释下都变成命题 如：谓词公式如：谓词公式) ) x)(f(x) g(x) x)(f(

26、x) g(x) 是闭式是闭式 f(x):x f(x):x是人是人 g (x):x g (x):x是黄种人是黄种人 上式为假上式为假 f(x):x f(x):x是人是人 g (x):x g (x):x是要死的是要死的 上式为真上式为真 f(x):x f(x):x是自然数是自然数 g (x):x g (x):x是整数是整数 上式为真上式为真 注：注： 对于不是闭式的谓词公式则不能成为任何命题是对于不是闭式的谓词公式则不能成为任何命题是命题函数命题函数确定谓词公式的真值：确定谓词公式的真值：1) f(f(x,y),g(x,y) 1) f(f(x,y),g(x,y) 2) f(f(x,a),y)f(g

27、(x,y),z)2) f(f(x,a),y)f(g(x,y),z)3)3)x f(g(x,y), z) x f(g(x,y), z) 4)4)x(f(g(x,a),x)f(x,y) )x(f(g(x,a),x)f(x,y) )5)5)x xy(f(f(x,a),y) y(f(f(x,a),y) f(f(y,a),x) ) f(f(y,a),x) ) 6)6)x xy yz f(f(x,y),z)z f(f(x,y),z) 例：给定解释例：给定解释i i 1 1）个体域）个体域didi为自然数集合为自然数集合 2 2） a=0 a=0 3) 3)函数函数 f(x,y)=x+y, f(x,y)=x

28、+y, g(x,y)=xy g(x,y)=xy 4) 4)谓词谓词 f(x,y): x=y f(x,y): x=y确定谓词公式的真值：确定谓词公式的真值：1) f(f(x,a1),g(x,a1) 2) xy f( f(x,y),g(x,y) )3) x y f(f(x,y),g(x,y) ) 4)y( f(y,a0)x(f( f(x,y),g(x,y) ) )5)yx( f(x,y) f(f(x,y),x) ) 6) f(f(x,y),g(x,y) 7) x ( f(x,a0) f( f(x,y),g(x,y) ) )例：给定解释例：给定解释i i 1 1）个体域为整数集合）个体域为整数集合z

29、 2z 2） z z上的特定元素上的特定元素 a0=0 a0=0，a1=1;a1=1; 3)z 3)z上的特定函数上的特定函数 f(x,y)=x-y, g(x,y)=x+y f(x,y)=x-y, g(x,y)=x+y； 4)z 4)z上的特定谓词上的特定谓词 f(x,y): x y; f(x,y): x y;1) (x - 1 ) (x+1 ) 不是闭式不是闭式 ，但在此解释下是命题，但在此解释下是命题 t 2) xy( (x-y) (x+y) ) f3) x y ( (x-y) (x+y) ) t4)y( (y0)x( (x-y) (x+y) ) ) ) t5)yx( (x y) ( (x

30、-y) x ) ) f6) ( (x-y) (x+y) ) 不是闭式不是闭式 7) x ( (x0) ( (x-y) (x+y) ) ) 不是闭式不是闭式 注：注：1 1有的公式在具体的解释中真值确定，即变成了命题有的公式在某些解释有的公式在具体的解释中真值确定，即变成了命题有的公式在某些解释中真值仍然不能确定，因而仍然不是命题。中真值仍然不能确定，因而仍然不是命题。2 2闭式在任何解释中都成为命题闭式在任何解释中都成为命题不太严谨地说，由于在闭式中，每个个体不太严谨地说，由于在闭式中，每个个体变项都受量词的约束，因而在具体解释中总表达一个意义确定的语句，即变项都受量词的约束，因而在具体解释中

31、总表达一个意义确定的语句，即一个真命题或一个假命题一个真命题或一个假命题3 3不是闭式的公式在某一解释中，可能成为命题，也可能不能成为命题。不是闭式的公式在某一解释中，可能成为命题，也可能不能成为命题。6.6.谓词公式的分类谓词公式的分类定义：定义： 设设a a为一公式，若为一公式，若a a在在任何解释下均为真任何解释下均为真，则称，则称a a为永为永真式真式( (或称逻辑有效式或称逻辑有效式) )若若a a在在任何解释下均为假任何解释下均为假，则称，则称a a为矛盾式为矛盾式( (或永假式或永假式) )若至少存在一个解释使若至少存在一个解释使a a为真，则称为真，则称a a是可满足式是可满足

32、式 注：在一阶逻辑中，由于公式的复杂性和注：在一阶逻辑中，由于公式的复杂性和解释的多样性解释的多样性，到目前为止，还没有找到一种可行的算法，对某些特殊的公到目前为止，还没有找到一种可行的算法，对某些特殊的公式还是可以判断的。式还是可以判断的。 可以利用一些特殊方法来进行判断：可以利用一些特殊方法来进行判断： 7. 7. 代入实例代入实例 定义定义 设设a a0 0是含命题变项是含命题变项p p1 1，p p2 2，p pn n的命题公式，的命题公式，a a1 1，a a2 2，a an n是是 n n个谓词公式，用个谓词公式，用a ai i(1in)(1in)处处代替处处代替a a0 0中的中

33、的p pi i所所得公式得公式a a称为称为a a0 0的代换实例的代换实例 如：如：xf(x)xf(x) x x g(x)g(x) a(x)a(x) b(x)b(x) 都是都是p p q q的代入实例的代入实例 x( f(x) g(x)x( f(x) g(x) 是否是是否是p p q q的代入实例？的代入实例？定理定理4 42 2 重言式的代换实例都是永真式，矛盾式的代换实例都重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式是矛盾式 这样由这样由命题逻辑的许多重言式命题逻辑的许多重言式可得到谓词公式相应的重言式可得到谓词公式相应的重言式 （只要能确定是那个重言式的代换实例）（只要能确定

34、是那个重言式的代换实例）看谓词公式：看谓词公式：（(x)p(x) (y)q(y) ） (x)p(x) (y)q(y) 而而 ( p q ) p q 是永真式是永真式 注意它们之间的关系注意它们之间的关系从命题公式中的永真式（矛盾式）来得到判别从命题公式中的永真式（矛盾式）来得到判别判断下列公式中，哪些是永真式，哪些是矛盾式判断下列公式中，哪些是永真式，哪些是矛盾式? ? （通过找到代入实例）（通过找到代入实例） (1) (1) xf(x)xf(x)(x xyg(xyg(x，y)y)xf(x)xf(x)因为可设因为可设 p: p: x f(x) q : x f(x) q : x xy g(x,y) y