第二章谓词逻辑(1)

1、第二章第二章 一阶逻辑一阶逻辑(1/2) 在命题逻辑中，命题是最基本的单位，对简单在命题逻辑中，命题是最基本的单位，对简单命题不再进行分解，并且不考虑命题之间的内在联命题不再进行分解，并且不考虑命题之间的内在联系和数量关系系和数量关系.因而命题逻辑具有局限性，甚至无法因而命题逻辑具有局限性，甚至无法判断一些简单而常见的推理判断一些简单而常见的推理.考虑下面的推理考虑下面的推理: 凡偶数都能被凡偶数都能被2整除；整除；6是偶数是偶数.所以，所以，6能被能被2整除整除.这个推理是我们公认的数学推理中的真命题，但是在这个推理是我们公认的数学推理中的真命题，但是在命题逻辑中却无法判断它的正确性命题逻辑

2、中却无法判断它的正确性.因为在命题逻辑因为在命题逻辑中只能将推理中出现的三个简单命题依次符号化为中只能将推理中出现的三个简单命题依次符号化为p，q，r，将推理的形式结构符号化为，将推理的形式结构符号化为 (pq)r 由于上式不是由于上式不是重言式重言式，所以不能由它判断推理的正确，所以不能由它判断推理的正确性性.2.1 一阶逻辑的符号化一阶逻辑的符号化 个体词，谓词和量词是一阶逻辑命题符号个体词，谓词和量词是一阶逻辑命题符号化的三个基本要素化的三个基本要素.下面讨论这三个要素下面讨论这三个要素 一、个体词一、个体词 个体词个体词是指所研究对象中可以独立存在的具是指所研究对象中可以独立存在的具体

3、的体的 或抽象的客体或抽象的客体. 例如例如:小王，小李，中国，小王，小李，中国，3等都可以作为等都可以作为个体词个体词. 将表示具体或特定的客体的个体词称作个体将表示具体或特定的客体的个体词称作个体常项，一般用小写英文字母常项，一般用小写英文字母a，b，c表示；表示；而将表示抽象或泛指的个体词称为个体变项，而将表示抽象或泛指的个体词称为个体变项，常用常用x，y，z表示表示.称个体变项的取值范围为称个体变项的取值范围为个体域个体域(或称论域或称论域) 个体域可以是个体域可以是有穷集合有穷集合，例如，例如，1，2，3，a，b，c，d，a，b，c，x，y，z，；也可；也可以是以是无穷集合无穷集合，

4、例如，自然数集合，例如，自然数集合 N=0，1，2，实数集合，实数集合R=x|x是实数是实数. 有一个特殊的个体域，它是由宇宙间一切事物有一个特殊的个体域，它是由宇宙间一切事物组成的，称它为组成的，称它为全总个体域全总个体域.本课件在论述或推本课件在论述或推理中如没有指明所采用的个体域，都是使用全理中如没有指明所采用的个体域，都是使用全总个体域总个体域.二、谓词二、谓词 谓词谓词是用来刻画个体词性质及个体词之是用来刻画个体词性质及个体词之间相互关系的词间相互关系的词. .考虑下面四个命题考虑下面四个命题(或命题公式或命题公式): (1) 是无理数是无理数. (2)x是有理数是有理数. (3)小

5、王与小李同岁小王与小李同岁. (4)x与与y具有关系具有关系L. 2在在(2)中，中，x是个体变项，是个体变项，“是有理数是有理数”是谓词，记是谓词，记为为G，用，用G(x)表示表示(2)中命题中命题.在在(3)中，小王，小李都是个体常项，中，小王，小李都是个体常项，“与与同岁同岁”是谓词，记为是谓词，记为H，则，则(3)中命题符号化形式为中命题符号化形式为H(a,b)，其中，其中，a:小王，小王，b:小李小李. 在在(4)中，中，x，y为两个个体变项，谓词为为两个个体变项，谓词为L，(4)的符的符号化形式为号化形式为L(x, y). 在在(1)中，中， 是个体常项，是个体常项，“是无理数是无

6、理数”是谓词，记是谓词，记为为F，并用，并用F( )表示表示(1)中命题中命题. 22 同个体词一样，谓词也有常项和变项之分同个体词一样，谓词也有常项和变项之分.表表示具体性质或关系的谓词称为示具体性质或关系的谓词称为谓词常项谓词常项，表，表示抽象的、泛指的性质或关系的谓词称为示抽象的、泛指的性质或关系的谓词称为谓谓词变项词变项.无论是谓词常项或变项都用大写英无论是谓词常项或变项都用大写英文字母文字母F，G，H，表示，可根据上下文区表示，可根据上下文区分分. 在上面四个命题中，在上面四个命题中，(1)，(2)，(3)中谓词中谓词F，G，H是常项，而是常项，而(4)中谓词中谓词L是变项是变项.

7、一般的，用一般的，用F(a)表示个体常项表示个体常项a具有性质具有性质F (F是谓词常项或谓词变项是谓词常项或谓词变项)，用，用F(x)表示个体变表示个体变项项x具有性质具有性质F.而用而用F(a，b)表示个体常项表示个体常项a，b具有关系具有关系F，用，用F(x , y)表示个体变项表示个体变项x，y具有具有关系关系F. 更一般的，用更一般的，用P(x1,x2,xn)表示含表示含n(n1)个命个命题变项的题变项的n元谓词元谓词.n=1时，时，P(x1)表示表示x1具有性质具有性质P；n2时，时，P(x1,x2,xn)表示表示x1,x2,xn具有关系具有关系P.实质上，实质上，n元谓词元谓词P

8、(x1,x2,xn)可以看成以个可以看成以个体域为定义域，以体域为定义域，以0,1为值域的为值域的n元函数或关元函数或关系系.它不是命题它不是命题.要想使它成为命题，必须用谓词要想使它成为命题，必须用谓词常项取代常项取代P，用个体常项，用个体常项a1,a2,an取代取代x1,x2,xn，得，得P(a1,a2,an)是命题是命题. 有时候将不带个体变项的谓词称为有时候将不带个体变项的谓词称为0元元谓词，例如，谓词，例如，F(a)，G(a,b)，P(a1,a2,an)等等都是都是0元谓词元谓词.当当F，G，P为谓词常项时，为谓词常项时，0元谓词为命题元谓词为命题.这样一来，命题逻辑中的命这样一来，

9、命题逻辑中的命题均可以表示成题均可以表示成0元谓词，因而可以将命题元谓词，因而可以将命题看成特殊的谓词看成特殊的谓词. 例例2.1.1 将下列命题在一阶逻辑中用将下列命题在一阶逻辑中用0元谓词符号化，元谓词符号化，并讨论它们的真值并讨论它们的真值: (1)只有只有2是素数，是素数，4才是素数才是素数. (2)如果如果5大于大于4，则，则4大于大于6. 解解: (1)设一元谓词设一元谓词F(x):x是素数，是素数，a:2，b:4. (1)中命题符号化为中命题符号化为0元谓词的蕴涵式元谓词的蕴涵式: F(b)F(a) 由于此蕴涵前件为假，所以由于此蕴涵前件为假，所以(1)中命题为真中命题为真. (

10、2)如果如果5大于大于4，则，则4大于大于6. (2) 设二元谓词设二元谓词G(x，y):x大于大于y，a:4，b:5，c:6.G(b,a)，G(a,c)是两个是两个0元谓词，把元谓词，把(2)中中命题符号化为命题符号化为 G(b,a)G(a,c) 由于由于G(b,a)为真，而为真，而G(a,c)为假，所以为假，所以(2)中中命题为假命题为假. 三、量词三、量词 (1) 全称量词全称量词 (2) 存在量词存在量词 (1) 全称量词全称量词 日常生活和数学中所用的日常生活和数学中所用的“一切的一切的”，“所所有的有的”，“每一个每一个”，“任意的任意的”，“凡凡”，“都都”等词可统称为全称量词，

11、将它们符号等词可统称为全称量词，将它们符号化为化为“ ”.并用并用 x， y等表示个体域里的等表示个体域里的所有个体，而用所有个体，而用 xF(x)， yG(y)等分别表示个体域里所有个等分别表示个体域里所有个体都有性质体都有性质F和都有性质和都有性质G. (2) 存在量词存在量词 日常生活和数学中所用的日常生活和数学中所用的“存在存在”，“有一有一个个”，“有的有的”，“至少有一个至少有一个”等词统称为等词统称为存在量词，将它们都符号化为存在量词，将它们都符号化为“ ”.并用并用 x， y等表示个体域里有的个体，而用等表示个体域里有的个体，而用 xF(x)， yG(y)等分别表示个体域里存在

12、个体具有性质等分别表示个体域里存在个体具有性质F和存在个体具有性质和存在个体具有性质G等等. 四、一阶逻辑命题符号化四、一阶逻辑命题符号化 例例3.1.2 在个体域分别限制为在个体域分别限制为(a)和和(b)条件时，条件时，将下面两个命题符号化将下面两个命题符号化: (1) 凡人都呼吸凡人都呼吸. (2) 有的人用左手写字有的人用左手写字. 其中其中:(a)个体域个体域D1为人类集合；为人类集合； (b)个体域个体域D2为全总个体域为全总个体域. 解解: (a)令令F(x):x呼吸呼吸.G(x):x用左手写字用左手写字.(1) 在在D1中除了人外，再无别的东西，中除了人外，再无别的东西，因而因

13、而“凡人都呼吸凡人都呼吸”应符号化为应符号化为 xF(x) (2.1)(2) 在在D1中的有些个体中的有些个体(人人)用左手写字，用左手写字，因而因而“有的人用左手写字有的人用左手写字”符号化为符号化为 xG(x) (2.2) (b) D2中除了有人外，还有万物，因而在中除了有人外，还有万物，因而在 (1)，(2)符号化时，必须考虑将人分离出来符号化时，必须考虑将人分离出来令令M(x):x是人是人. 在在D2中，中，(1)，(2)可以分别重述如下可以分别重述如下: (1)对于宇宙间一切事物而言，如果事物是对于宇宙间一切事物而言，如果事物是人，则他要呼吸人，则他要呼吸. (2)在宇宙间存在着用左

14、手写字的人在宇宙间存在着用左手写字的人. 特性谓词特性谓词(1)，(2)的符号化形式分别为的符号化形式分别为 x(M(x)F(x) (2.3) 和和 x(M(x)G(x) (2.4) 其中其中F(x)与与G(x)的含义同的含义同(a)中中. 问问: (a)能否将能否将(1)符号化为符号化为 x(M(x)F(x)？ (b)能否将能否将(2)符号化为符号化为 x(M(x)G(x)？ 否否例例2.1.3 在个体域限制为在个体域限制为(a)和和(b)条件时，将下条件时，将下列命题符号化列命题符号化: (1) 对于任意的对于任意的x，均有，均有x2-3x+2=(x-1)(x-2). (2) 存在存在x，

15、使得，使得x+5=3. 其中其中: (a)个体域个体域D1=N(N为自然数集合为自然数集合) (b)个体域个体域D2=R(R为实数集合为实数集合) (b) 在在D2内，内，(1)和和(2)的符号化形式还是的符号化形式还是(4.7)式和式和(4.8)式，式，(1)依然是真命题，而此时依然是真命题，而此时(2)也是真命题也是真命题.解解: (a)令令F(x): -3x+2=(x-1)(x-2)， G(x): x+5=3.命题命题(1)的符号化形式为的符号化形式为 xF(x) (2.5) 命题命题(2)的符号化形式为的符号化形式为 xG(x) (2.6) 显然显然(1)为真命题；而为真命题；而(2)

16、为假命题，因为为假命题，因为N不不含负数含负数.2x 1. 在不同个体域内，同一个命题的符号在不同个体域内，同一个命题的符号化形式可能不同，也可能相同化形式可能不同，也可能相同. 2. 同一个命题，在不同个体域中的真值同一个命题，在不同个体域中的真值也可能不同也可能不同. 从例从例2.1.2和例和例2.1.3可以看出以下两点可以看出以下两点: 例例2.1.4 将下列命题符号化，并讨论真值将下列命题符号化，并讨论真值. (1)所有的人都长着黑头发所有的人都长着黑头发. (2)有的人登上过月球有的人登上过月球. (3)没有人登上过木星没有人登上过木星. (4)在美国留学的学生未必都是亚洲人在美国留

17、学的学生未必都是亚洲人. 解解 :令令M(x):x为人为人. (1)令令F(x):x长着黑头发长着黑头发.命题命题(1)符号化为符号化为 设设a是是1969年登上月球完成阿波罗计划的一年登上月球完成阿波罗计划的一个美国人，则个美国人，则M(a)G(a)为真，所以为真，所以(2.8)表表示的命题为真示的命题为真. 设设a为某个金发姑娘，则为某个金发姑娘，则M(a)为真，而为真，而F(a)为假，所以为假，所以M(a)F(a)为假，故为假，故(2.7)所表所表示的命题为假示的命题为假. (2)令令G(x):x登上过月球登上过月球. 命题命题(2)的符号化形式的符号化形式 为为 x(M(x)F(x)

18、(2.7) x(M(x)G(x) (2.8) (4)令令F(x):x是在美国留学的学生，是在美国留学的学生，G(x):x是亚洲是亚洲人人.命题命题(4)符号化形式为符号化形式为 x(F(x)G(x) (2.10) 这个命题也为真这个命题也为真. (3)令令H(x):x登上过木星登上过木星.命题命题(3)符号化形式为符号化形式为 x(M(x)H(x) (2.9) 到目前为止，对于任何一个人到目前为止，对于任何一个人(含已经去世的人含已经去世的人)都还没有登上过木星，所以对任何人都还没有登上过木星，所以对任何人a，M(a)H(a)均为假，因而均为假，因而 x(M(x)H(x)为假，为假，所以所以(

19、2.9)表示的命题为真表示的命题为真.例例2.1.5 将下列命题符号化将下列命题符号化: (1) 兔子比乌龟跑得快兔子比乌龟跑得快. (2) 有的兔子比所有的乌龟跑得快有的兔子比所有的乌龟跑得快. (3) 并不是所有的兔子都比乌龟跑得快并不是所有的兔子都比乌龟跑得快. (4) 不存在跑得同样快的两只兔子不存在跑得同样快的两只兔子. 解解: 令令F(x):x是兔子，是兔子，G(y):y是乌龟，是乌龟，H(x,y):x比比y跑得快，跑得快，L(x,y):x与与y跑得一样快跑得一样快.这这4个命题个命题分别符号化为分别符号化为 x y(F(x)G(y)H(x,y) (2.11) x(F(x) y(G

20、(y)H(x,y) (2.12) x y(F(x)G(y)H(x,y) (2.13) x y(F(x)F(y)L(x,y) (2.14) 注意注意 1. 一般说来，多个量词出现时，它们的顺序不一般说来，多个量词出现时，它们的顺序不能随意调换能随意调换. 例如，考虑个体域为实数集，例如，考虑个体域为实数集，H(x，y)表示表示x+y=10，则命题，则命题“对于任意的对于任意的x，都存在，都存在y，使得使得x+y=10”的符号化形式为的符号化形式为 x y H(x, y) (2.15) 给命题显然为真命题给命题显然为真命题.但是如果改变两个量但是如果改变两个量词的顺序，得词的顺序，得 y x H(

21、x, y) (2.16) (4.18)已经不表示原命题，而且它所表示的已经不表示原命题，而且它所表示的命题是假命题命题是假命题.2. 有些命题的符号化形式可不止一种有些命题的符号化形式可不止一种.例如，在例如，在例例2.1.5中，中，(3)还可以符号化为还可以符号化为 x y(F(x)G(y)H(x,y) (2.17) (4)还可以符号化为还可以符号化为 x y(F(x)F(y)L(x,y) (2.18) 这样，（这样，（2.1.3）和）和(2.17)都是都是(3)的符号化形式，的符号化形式，（2.1.4）与）与(2.18)都是都是(4)的符号化形式，它们的符号化形式，它们都是正确的都是正确的

22、(下一节可以证明下一节可以证明(2.13)和和(2.17)是是等值的，等值的，(2.14)和和(2.18)是等值的是等值的). 2.2 一阶逻辑公式及解释一阶逻辑公式及解释 一、一阶语言一、一阶语言 定义定义2.2.1 一阶语言一阶语言 的字母表定义如下的字母表定义如下: (1)个体常项个体常项:a, b, c,ai, bi, ci，i1 (2)个体变项个体变项:x, y, z,，xi, yi, zi，i1 (3)函数符号函数符号:f, g, h,fi, gi, hi，i1 (4)谓词符号谓词符号:F, G, H,Fi, Gi, Hi，i1 (5)量词符号量词符号: (6)联结词符号联结词符号

23、:, (7)括号与逗号括号与逗号:(,),，,定义定义2.2.2 项的定义如下项的定义如下: (1)个体常项和个体变项是项个体常项和个体变项是项. (2)若若f(x1 , x2 , xn)是任意的是任意的n元函数，元函数，t1 , t2 , tn是任意的是任意的n个项个项,则则f( t1, t2 , tn)是项是项. (3)所有的项都是有限次使用所有的项都是有限次使用(1)，(2)得到得到的的. 定义定义2.2.3 设设R ( x1 , x2 , , xn )是任意是任意n元谓词，元谓词， t1,t2,tn是任意的是任意的n个项，则称个项，则称R(t1 , t2 , tn)是是原子公式原子公式

24、. 例例2.1.5中的中的1元谓词元谓词F(x)，G(x)，2元谓词元谓词H(x,y)，L(x,y)等都是原子公式等都是原子公式.(1)原子公式是合式公式原子公式是合式公式. 定义定义2.2.4 的合式公式定义如下的合式公式定义如下:(2)若若A是合式公式，则是合式公式，则(A)也是合式公式也是合式公式. (5)只有有限次的应用只有有限次的应用(1)(4)构成的符号串构成的符号串才是合式公式才是合式公式. 合式公式也称为谓词公式，简称公式合式公式也称为谓词公式，简称公式. (3)若若A，B是合式公式，则是合式公式，则(AB)，(AB)，(AB)，(A B)也是合式公式也是合式公式. (4)若若

25、A是合式公式，则是合式公式，则 xA，xA也是合式公式也是合式公式. 二、自由与约束 定义2.2.5 在公式 xA和 xA中，称x为指导变元，A为相应量词的辖域.在 x和 x的辖域中，x的所有出现都称为约束出现.A中不是约束出现的其他变项均称为是自由出现的. 例例2.2.6 指出下列各公式中的指导变元，各量词指出下列各公式中的指导变元，各量词的辖域，自由出现以及约束出现的个体变项的辖域，自由出现以及约束出现的个体变项: (1) x(F(x,y)G(x,z) (2.19) (2) x(F(x)G(y) y（H(x)L(x,y,z)(2.20)解解: (1)x是指导变元是指导变元.量词量词 的辖域

26、的辖域A=(F(x,y)G(x,z)，在，在A中，中，x是约束出现的是约束出现的.而且约束出现两次，而且约束出现两次，y和和z均为自由出现的，均为自由出现的，而且各自由出现一次而且各自由出现一次. (2)公式中含有两个量词，前件上的量词公式中含有两个量词，前件上的量词 的的指导变元为指导变元为x， 的辖域的辖域A=(F(x)G(y)，其中，其中x是约束出现的，是约束出现的，y是自由出现的是自由出现的.后件中的量词后件中的量词 的指导变元为的指导变元为y， 的辖域的辖域(H(x)L(x,y,z)，其中其中y是约束出现的，是约束出现的，x，z均为自由出现的均为自由出现的.在在整个公式中，整个公式中

27、，x约束出现一次，自由出现约束出现一次，自由出现2次，次，y自由出现一次，约束出现一次，自由出现一次，约束出现一次，z只自由出现只自由出现一次一次.三、闭公式三、闭公式 定义定义2.2.6 设设A是任意的公式，若是任意的公式，若A中不含有自中不含有自由出现的个体变项，则称由出现的个体变项，则称A为封闭的公式，为封闭的公式，简称闭式简称闭式. 如如: x(F(x) G(x), x y(F(x) G(x,y) 为闭为闭 式式而而 x(F(x) G(x,y), z yL(x,y,z) 不是闭式不是闭式. 四、一阶公式的解释四、一阶公式的解释 定义定义2.2.7 I的解释由下面的解释由下面4部分组成部

28、分组成: (a)非空个体域非空个体域D; (b)D中一些特定元素的集合中一些特定元素的集合; (c)D上特定函数集合上特定函数集合; (d)D上特定谓词的集合上特定谓词的集合. 例例2.2.7给定解释给定解释I如下如下:1)D=2.3;2)D中特定元中特定元a=2;3)函数函数f(x)为为f(2)=3,f(3)=2;4)谓词谓词F(x)为为 F(2)=0,F(3)=1 G(x,y)为为 G(i,j)=1,i,j=2,3 L(x,y)为为L(2,2)=L(3,3)=0,L(2,3)=L(3,2)=0在解释在解释I下下,求下列各式的真值求下列各式的真值.(1) x(F(x) G(x,a)(2) x

29、(F(f(x) G(x,f(x)(3) x yL(x,y) (F(2) G(2,2) (F(3) G(3,2) (0 1) (1 1) 0 (F(f(2) G(2,f(2) (F(f(3) G(3,f(3) 1 (L(2,2) L(2,3) (L(3,2) L(3,3) 0 例例2.2.8给定解释给定解释N如下如下:1)个体域为自然数集个体域为自然数集DN2) DN中特定元中特定元a=03) DN上特定函数上特定函数f(x,y)=x+y,g(x,y)=xy4) DN上特定谓词上特定谓词F(x,y):x=y.在解释在解释N下下,下面哪些公式为真下面哪些公式为真,哪些为假哪些为假? (1) xF(

30、g(x,a),x)x(x0=x) 为假命题为假命题(2) x y (F(f(x,a),y) F(f(y,a),x) x y(x+0=y y+0=x) 为真为真命题命题 (3) x y z F(f(x,y),z) x y z (x+y=z) 为为真命题真命题 (4) x y F(f(x,y),g(x,y) x y (x+y=xy)为为假命题假命题(5) F(f(x,y),f(y,z)x+y=y+z ,真值真值不能确定不能确定定理定理2.2.1 封闭的公式在任封闭的公式在任何解释下都变成命题何解释下都变成命题. 五、一阶公式的分类五、一阶公式的分类定义定义2.2.8 设设A为一个公式，若为一个公式

31、，若A在任何解释下在任何解释下均为真，则称均为真，则称A为永真式为永真式(或称逻辑有效式或称逻辑有效式).若若A在任何解释下均为假，则称在任何解释下均为假，则称A为矛盾式为矛盾式(或永假式或永假式).若至少存在一个解释使若至少存在一个解释使A为真，为真，则称则称A为可满足式为可满足式.定义定义2.2.9 设设A0是含有命题变项是含有命题变项p1, p2 , pn的的命题公式，命题公式，A1, A2, , An是是n个谓词公式，用个谓词公式，用Ai(1in)处处代替处处代替A0中的中的pi，所得公式，所得公式A称称为为A0的代换实例的代换实例. 定理定理2.2.2 重言式的代换实例都是永真式，矛重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式盾式的代换实例