阶逻辑基本概念.ppt

《阶逻辑基本概念.ppt》由会员分享，可在线阅读，更多相关《阶逻辑基本概念.ppt（83页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第4 4章章 一阶逻辑基本概念一阶逻辑基本概念离离 散散 数数 学学本章说明本章说明本章说明本章说明q本章的主要内容本章的主要内容一阶逻辑基本概念、命题符号化一阶逻辑基本概念、命题符号化一阶逻辑公式、解释及分类一阶逻辑公式、解释及分类q本章与后续各章的关系本章与后续各章的关系克服命题逻辑的局限性克服命题逻辑的局限性是第五章的先行准备是第五章的先行准备 命题逻辑的缺陷命题逻辑的缺陷把命题看成是一个个孤立的命题，忽略了命题之间的联系，不能反映某些重要的常见的逻辑思维过程。1.繁琐例.表述集合个体性质及相互关系 S=1,2,50表述S中所有元素都大于3这样一个性质，需要13,23,503 等50个

2、命题。2.不能描述命题间的逻辑联系q例如，逻辑学中著名的苏格拉底三段论：P：所有人必死Q：苏格拉底是人R：苏格拉底必死q表示为命题逻辑：应该有(PQ)R，也就是公式(PQ)R应该是恒真的。q显然该公式不是恒真的，解释P，Q，R就能弄假该公式。q原因：命题R和命题P,Q是有内在关系的，只是这种关系在命题逻辑中无法表示。q因此，需要对命题的成分、结构和命题间的共同特性等作进一步的分析，分析出个体词、谓词和量词，以期达到表达出个体与总体的内在联系和数量关系，这正是谓词逻辑所要研究的问题。本章内容本章内容本章内容本章内容4.1 4.1 一阶逻辑命题符号化一阶逻辑命题符号化4.2 4.2 一阶逻辑公式及

3、解释一阶逻辑公式及解释 本章小结本章小结 习题习题 作业作业4.1 4.1 一阶逻辑命题符号化一阶逻辑命题符号化一阶逻辑命题符号化一阶逻辑命题符号化q一阶逻辑命题符号化的三个基本要素一阶逻辑命题符号化的三个基本要素个体词个体词谓词谓词量词量词个体词及相关概念个体词及相关概念q个体词一般是充当陈述句主语的名词或代词个体词一般是充当陈述句主语的名词或代词说说明明q个个体体词词：指指所所研研究究对对象象中中可可以以独独立立存存在在的的具具体体或或抽抽象的象的客体客体。q举例举例命题：电子计算机是科学技术的工具。命题：电子计算机是科学技术的工具。个体词：电子计算机。个体词：电子计算机。命题：他是三好学

4、生命题：他是三好学生。个体词：他。个体词：他。心物一元心物一元 or 心物二元？心物二元？量子力学中的测不准原理量子力学中的测不准原理q个个体体常常项项：表表示示具具体体或或特特定定的的客客体体的的个个体体词词，用用小小写写字字母母a a,b b,c c，表示。表示。q个个体体变变项项：表表示示抽抽象象或或泛泛指指的的客客体体的的个个体体词词，用用x x,y y,z z,表表示。示。q个体域（或称论域）个体域（或称论域）：指个体变项的取值范围。：指个体变项的取值范围。可以是有穷集合，如可以是有穷集合，如 a a,b b,c c,1,2,1,2。可以是无穷集合，如可以是无穷集合，如N N,Z Z

5、,R R,。q全总个体域（全总个体域（universeuniverse）由宇宙间一切事物组成由宇宙间一切事物组成 。个体词及相关概念个体词及相关概念个体词及相关概念个体词及相关概念q本教材在论述或推理中，如果没有指明所采本教材在论述或推理中，如果没有指明所采用的个体域，都是使用的全总个体域。用的个体域，都是使用的全总个体域。说说明明谓词及相关概念谓词及相关概念谓词及相关概念谓词及相关概念q谓词（谓词（predicatepredicate）是用来刻画个体词性质及个体词之间相是用来刻画个体词性质及个体词之间相互关系的词。互关系的词。(1)(1)是无理数。是无理数。是个体常项，是个体常项，“是无理数

6、是无理数”是谓词，记为是谓词，记为F F，命题符号化命题符号化为为F(F()。(2)(2)x x是有理数。是有理数。x x是个体变项，是个体变项，“是有理数是有理数”是谓词，记为是谓词，记为G G，命题符号化命题符号化为为G(G(x x)。(3)(3)小王与小李同岁。小王与小李同岁。小王、小李都是个体常项，小王、小李都是个体常项，“与与同岁同岁”是谓词，记为是谓词，记为H H，命题符号化为命题符号化为H(H(a,ba,b)，其中，其中a a：小王，小王，b b：小李：小李。(4)(4)x x与与y y具有关系具有关系L L。x x，y y都是个体变项，谓词为都是个体变项，谓词为L L，命题符号

7、化为命题符号化为L(x,y)L(x,y)。q谓词常项谓词常项：表示具体性质或关系的谓词。用大写字母表示。：表示具体性质或关系的谓词。用大写字母表示。如如(1)(1)、(2)(2)、(3)(3)中谓词中谓词F F、G G、H H。q谓词变项谓词变项：表示抽象的、泛指的性质或关系的谓词。用大写：表示抽象的、泛指的性质或关系的谓词。用大写字母表示。如字母表示。如(4)(4)中谓词中谓词L L。qn n(n n 1)1)元谓词元谓词：P(xP(x1 1,x,x2 2,x,xn n)表示含表示含n n个个体变项的个个体变项的n n元谓元谓词。词。n=1n=1时，一元谓词时，一元谓词表示表示x x1 1具

8、有性质具有性质P P。n2n2时，多元谓词时，多元谓词表示表示x x1 1,x,x2 2,x,xn n具有关系具有关系P P。q0 0元谓词元谓词：不含个体变项的谓词。如：不含个体变项的谓词。如F(a)F(a)、G(a,b)G(a,b)、P(aP(a1 1,a,a2 2,a,an n)。若。若F F、G G、P P为谓词常项，则上述为谓词常项，则上述0 0元谓词为命元谓词为命题常项；若题常项；若F F、G G、P P为谓词变项，则为命题变项。为谓词变项，则为命题变项。qn n元谓词是命题吗？元谓词是命题吗？不是，只有用谓词常项取代不是，只有用谓词常项取代P P，用个体常项取代用个体常项取代x

9、x1 1,x,x2 2,x,xn n时，才能使时，才能使n n元谓词变为命题。元谓词变为命题。思思考考谓词及相关概念谓词及相关概念谓词及相关概念谓词及相关概念谓词的形式化定义谓词的形式化定义q设D是非空个体名称集合，定义在Dn上取值于0，1上的n元函数，称为n元命题函数或n元谓词。其中Dn表示集合D的n次笛卡尔乘积。例：令G(x，y)：“x高于y”，G(x，y)是一个二元谓词。将x代以个体“张三”，y代以个体“李四”，则G(张三，李四)就是命题：“张三高于李四”。qG(x，y)不是命题，而是一个命题函数即谓词。q将x，y代以任意确定的个体，由G(x，y)都能得到一个命题。D=2,3,4u设P(

10、x)：x大于3，则P(x)为一元谓词。指定元素-命题：P(2)=0,P(3)=0,P(4)=1u设P(x,y)：x大于y,则P(x,y)为二元谓词。指定元素-命题：P(2,3)=0,P(4,2)=1u设P(x,y,z)：若x+y-1=z，则P(x,y,z)为1，否则为0。则P(x,y,z)为三元谓词。指定元素-命题：P(2,3,4)=1,P(4,2,2)=0例题例题例题例题例题例题例题例题将命题将命题“这只大红书柜摆满了那些古书。这只大红书柜摆满了那些古书。”符号化符号化.(1)(1)设设 F(x,y)F(x,y)：x x摆满了摆满了y y，R(x)R(x)：x x是大红书柜是大红书柜Q(y)

11、Q(y)：y y是古书，是古书，a a：这个书柜这个书柜 b b：那些书那些书 符号化为：符号化为：R(a)Q(b)F(a,b)R(a)Q(b)F(a,b)(2)(2)设设 A(x)A(x)：x x是书柜，是书柜，B(x)B(x)：x x是大的是大的 C(x)C(x)：x x是红的，是红的，D(y)D(y)：y y是古老的是古老的E(y)E(y)：y y是图书，是图书，F(x,y)F(x,y)：x x摆满了摆满了y ya a：这个东西这个东西b b：那些东西那些东西 符号化为：符号化为：A(a)B(a)C(a)D(b)E(b)F(a,b)A(a)B(a)C(a)D(b)E(b)F(a,b)q用

12、谓词的概念可将苏格拉底三段论做如下的符号化：令H(x)表示“x是人”，M(x)表示“x必死”。则三段论的三个命题表示如下：P：H(x)M(x)Q：H(苏格拉底)R：M(苏格拉底)现在可以将苏格拉底三段论符号化为现在可以将苏格拉底三段论符号化为现在可以将苏格拉底三段论符号化为现在可以将苏格拉底三段论符号化为q 令命题P為：所有人都会死，其否定命題為P =(H(x)M(x)=(H(x)M(x)=H(x)M(x)亦即，命题 P“所有人都会死”的否定命题是“所有人都不會死”。这和人们对命题“所有人都必死”的否定的理解並不一致。但问题是但问题是但问题是但问题是q原因命题P的确切意思应该是：“对任意x，如

13、果x是人，则x必死”。但是H(x)M(x)中并没有确切的表示出“对任意x”这个意思，因此，在谓词逻辑中除引进谓词外，还需要引进“对任意x”这个语句，及其对偶的语句“存在一个x”。量词（量词（quantifierquantifier）是表示个体常项或个体变项数量屬性的词。是表示个体常项或个体变项数量屬性的词。1 1.全称量词全称量词：符号化为：符号化为“”（A Allll）q日日常常生生活活和和数数学学中中所所用用的的“一一切切的的”、“所所有有的的”、“每每一一个个”、“任意的任意的”、“凡凡”、“都都”等词可统称为全称量词。等词可统称为全称量词。qx x表表示示个个体体域域里里的的某某個個个

14、个体体，x x F(x)F(x)表表示示个个体体域域里里所所有有个个体体都有性质都有性质F F。2 2.存在量词存在量词：符号化为：符号化为“”（E Existxist）q日日常常生生活活和和数数学学中中所所用用的的“存存在在”、“有有一一个个”、“有有的的”、“至少有一个至少有一个”等词统称为存在量词。等词统称为存在量词。qy y表表示示个个体体域域里里某某個個个个体体，y y G(y)G(y)表表示示个个体体域域里里存存在在个个体体y y具有性质具有性质G G。量词及相关概念量词及相关概念量词及相关概念量词及相关概念q引入谓词后，命题P就可确切地符号化如下：x(H(x)M(x)命题P的否定

15、命题为：P=(x(H(x)M(x)=x(H(x)M(x)亦即“至少有一个人是不死的”。这个命题才是“所有人都要死”的否定。q三段论的三个命题，在谓词逻辑中可以如下表示：P：x(H(x)M(x)Q：H(苏格拉底)R：M(苏格拉底)q以后可以证明，在谓词逻辑中，R是P和Q的逻辑结果。q例例 符号化下述命题：符号化下述命题：（1 1）所有的所有的老虎都要吃人；老虎都要吃人；（2 2）每一个每一个大学生都会说英语；大学生都会说英语；（3 3）所有的所有的人都长着黑头发；人都长着黑头发；（4 4）有一些有一些人登上过月球；人登上过月球；（5 5）有一些有一些自然数是素数。自然数是素数。解解 设有如下谓词

16、：设有如下谓词：P(x)P(x)：x x会吃人；会吃人；Q(x)Q(x)：x x会说英语；会说英语；R(x)R(x)：x x长着黑头发；长着黑头发；S(x)S(x)：x x登上过月球；登上过月球；T(x)T(x)：x x是素数。是素数。（1 1）(x)P(x)x)P(x)x x 老虎老虎 ；（2 2）(x)Q(x)x)Q(x)x x 大学生大学生；（3 3）(x)R(x)x)R(x)x x 人人；（4 4）(x)S(x)x)S(x)x x 人人；（5 5）(x)T(x)x)T(x)x x 自然数自然数。不便之处不便之处不便之处不便之处（1 1）从从书写上书写上十分不便，总要特别注明个体域；十分

17、不便，总要特别注明个体域；（2 2）在同一个比较复杂的句子中，不同命题函数中在同一个比较复杂的句子中，不同命题函数中的个体可能属于不同的个体域，此时的个体可能属于不同的个体域，此时无法清晰无法清晰表达；表达；如例如例 (1)(1)和和(4)(4)的合取的合取 (x)P(x)(x)P(x)(x)R(x)x)R(x)x人人x老虎老虎不便之处不便之处不便之处不便之处(续续续续)（3 3）若个体域的注明不清楚，将造成若个体域的注明不清楚，将造成无法确定命题真值无法确定命题真值。即即对于同一个对于同一个n n元谓词，不同的个体域有可能带来不同的真元谓词，不同的个体域有可能带来不同的真值值。例如例如 对于

18、语句对于语句“(x)(x+6=5)x)(x+6=5)”可表示为：可表示为：“有一些有一些x x，使得，使得x+6=5x+6=5”。该语句在下面两种个体域下有不同的。该语句在下面两种个体域下有不同的真值：真值：（a a）在实数范围内时，确有在实数范围内时，确有x=-1x=-1使得使得x+6=5x+6=5，因此，因此，(x)(x+6=5)x)(x+6=5)为为“真真”；（b b）在正整数范围内时，则找不到任何在正整数范围内时，则找不到任何x x，使得，使得x+6=5x+6=5为为“真真”，所以，所以，(x)(x+6=5)x)(x+6=5)为为“假假”。不便之处的根源不便之处的根源不便之处的根源不便

19、之处的根源因为需要特别标注每个谓词的个体因为需要特别标注每个谓词的个体域！域！全总个体域全总个体域特性谓词特性谓词特性谓词特性谓词新的问题出现了，新的问题出现了，U(x)如何与如何与(x)P(x)，(x)S(x)结合才符合逻辑结合才符合逻辑呢？呢？U(x)：x是老虎是老虎x老虎老虎U(x)：x是人是人x人人例 将下面两个命题符号化:(1)所有的老虎都会吃人。(2)有些人登上过月球。特性谓词的使用特性谓词的使用特性谓词的使用特性谓词的使用（1）令）令 P(x)：x会吃人会吃人 U(x)：x是老虎是老虎 则符号化的正确形式应该是则符号化的正确形式应该是(x)(U(x)P(x)它的含义是：它的含义是

20、：“对于任意的对于任意的x,如果如果x是老虎，则是老虎，则x会吃人会吃人”，符合原命题的逻辑含义。，符合原命题的逻辑含义。若符号化为若符号化为(x)(U(x)P(x)它的含义是：它的含义是：“对于任意的对于任意的x,x是老虎，并且是老虎，并且x会吃人会吃人”，与原命题与原命题“所有的老虎都要吃人所有的老虎都要吃人”的逻的逻辑含义不符。辑含义不符。（2）令）令 S(x)：x登上过月球登上过月球 U(x)：x是人是人 则符号化的正确形式应该是则符号化的正确形式应该是(x)(U(x)S(x)它的含义是：它的含义是：“存在存在x,x是人并且是人并且x登上过月球登上过月球”，符合原命题的逻辑含义。，符合

21、原命题的逻辑含义。若符号化为若符号化为(x)(U(x)S(x)它的含义是：它的含义是：“存在存在x,如果如果x是人，则是人，则x登上过月登上过月球球”，与原命题与原命题“有人登上过月球有人登上过月球”的逻辑含义的逻辑含义似乎差不多似乎差不多U(x)S(x)Universe谓词逻辑符号化的规则谓词逻辑符号化的规则谓词逻辑符号化的规则谓词逻辑符号化的规则q若统一个体域为若统一个体域为全总个体域全总个体域，对每一个句子中个体变量的，对每一个句子中个体变量的变化范围用一元变化范围用一元特性谓词特性谓词刻划，这种特性谓词在加入到刻划，这种特性谓词在加入到命题函数中时命题函数中时必须必须遵循如下原则：遵循

22、如下原则：（1）对于全称量词）对于全称量词(x)，刻划其对应个体域的，刻划其对应个体域的特性谓词作为蕴涵式之前件加入。特性谓词作为蕴涵式之前件加入。（2）对于存在量词）对于存在量词(x)，刻划其对应个体域的，刻划其对应个体域的特性谓词作为合取式之合取项加入。特性谓词作为合取式之合取项加入。例题例题例题例题用谓词逻辑符号化下述语句：用谓词逻辑符号化下述语句：(1)(1)天下乌鸦一般黑；天下乌鸦一般黑；(2)(2)没有人登上过木星；没有人登上过木星；(3)(3)在美国留学的学生未必都是亚洲人；在美国留学的学生未必都是亚洲人；(4)(4)每个实数都存在比它大的另外的实数；每个实数都存在比它大的另外的

23、实数；(5)(5)尽管有人很聪明，但未必一切人都聪明；尽管有人很聪明，但未必一切人都聪明；(6)(6)对于任意给定的对于任意给定的 00，必存在着，必存在着 00，使得对任意的，使得对任意的x x，只要，只要|x-a|x-a|，就有，就有|f(x)-f(a)|f(x)-f(a)|0，必存在着，必存在着 0，使得对任意，使得对任意的的x，只要，只要|x-a|，就有，就有|f(x)-f(a)|0)()(0)(x)(|x-a|)(|f(x)-f(a)|3 则x P(x)等价于 P(2)P(3)P(4)所以其真值为 0 0 0 x P(x)等价于 P(2)P(3)P(4)所以其真值为 0 0 课堂练习

24、课堂练习课堂练习课堂练习设个体域D=1，2，3，P(x)：x2。试判断下列公式的真值：(1)xP(x)P(2)；(2)P(3)xP(x).(1)xP(x)P(2)等价于(P(1)P(2)P(3)P(2)所以其真值为(001)0=1 0=0(2)P(3)xP(x)等价于1(P(1)P(2)P(3)所以其真值为 1(0 0 1)=1 0 =0课堂练习（续）课堂练习（续）课堂练习（续）课堂练习（续）设设 P(x)P(x)：x x是素数；是素数；I(x)I(x)：x x是整数；是整数；Q(x,y)Q(x,y)：x+y=0 x+y=0。用语句描述下述句子，并判断其真假值。用语句描述下述句子，并判断其真假

25、值。（1 1）(x)(I(x)P(x)x)(I(x)P(x)；（2 2）(x)(I(x)P(x)x)(I(x)P(x)；（3 3）(x)(x)(y)(I(x)I(y)Q(x,y)y)(I(x)I(y)Q(x,y)；（4 4）(x)(I(x)(x)(I(x)(y)(I(y)Q(x,y)y)(I(y)Q(x,y)；（5 5）(x)(x)(y)(I(x)(I(y)Q(x,y)y)(I(x)(I(y)Q(x,y)。解解解解 句子句子(1)(1)可描述为：可描述为：“对任意的整数对任意的整数x x，x x一定是素数一定是素数”，真值为真值为“假假”；句子句子(2)(2)可描述为：可描述为：“存在一些整数

26、存在一些整数x x，x x是素数是素数”，真值，真值为为“真真”；句子句子(3)(3)可描述为：可描述为：“对任意的整数对任意的整数x x，y y，都有，都有x+y=0 x+y=0”，真值为，真值为“假假”；句子句子(4)(4)可描述为：可描述为：“对任意的整数对任意的整数x x，都存在着整数，都存在着整数y y，使得使得x+y=0 x+y=0”，真值为，真值为“真真”；句子句子(5)(5)可描述为：可描述为：“存在着整数存在着整数x x，使得对任意的整数，使得对任意的整数y y，都有，都有x+y=0 x+y=0”，真值为，真值为“假假”。例例例例符号化下述一组语句：符号化下述一组语句：只要是

27、需要室外活动的课，郝帥都喜欢；所有的公共体育只要是需要室外活动的课，郝帥都喜欢；所有的公共体育课都是需要室外活动的课；篮球是一门公共体育课；郝帥喜欢课都是需要室外活动的课；篮球是一门公共体育课；郝帥喜欢篮球这门课。篮球这门课。解解 设设 O(x)O(x)：表示：表示x x是需要室外活动的课；是需要室外活动的课；L(x,y)L(x,y)：表示：表示x x喜欢喜欢y y；S(x)S(x)：表示：表示x x是一门公共体育课；是一门公共体育课；Hao Hao：表示郝帥；：表示郝帥；BallBall：表示篮球。：表示篮球。上述句子可符号化为：上述句子可符号化为：(x)(O(x)L(Hao,x)x)(O(

28、x)L(Hao,x)；(x)(S(x)O(x)x)(S(x)O(x)；S(ball)S(ball)；L(Hao,Ball)L(Hao,Ball)。例例例例符号化下述一组语句：符号化下述一组语句：海关人员检查每一个进入本国的不重要人物；某海关人员检查每一个进入本国的不重要人物；某些走私者进入该国时仅仅被走私者所检查；没有一个些走私者进入该国时仅仅被走私者所检查；没有一个走私者是重要人物；海关人员中的某些人是走私者。走私者是重要人物；海关人员中的某些人是走私者。解解 设设 E(x)E(x)：表示：表示x x进入国境；进入国境；V(x)V(x)：表示：表示x x是重要人物；是重要人物；C(x)C(x

29、)：表示：表示x x是海关人员；是海关人员；P(x)P(x)：表示：表示x x是走私者；是走私者；B(x,y)B(x,y)：表示：表示y y检查检查x x。解解解解上述句子可符号化为：上述句子可符号化为：(x)(E(x)x)(E(x)V(x)(V(x)(y)(C(y)B(x,y)y)(C(y)B(x,y)；(x)(P(x)E(x)(x)(P(x)E(x)(y)(B(x,y)P(y)y)(B(x,y)P(y)；(x)(P(x)x)(P(x)V(x)V(x)；(x)(P(x)C(x)x)(P(x)C(x)。4.2 4.2 4.2 4.2 一阶逻辑公式及解释一阶逻辑公式及解释一阶逻辑公式及解释一阶逻

30、辑公式及解释q同在命题逻辑中一样，为在一阶逻辑中进行演算和推理，同在命题逻辑中一样，为在一阶逻辑中进行演算和推理，必须给出一阶逻辑中公式的抽象定义，以及它们的分类及必须给出一阶逻辑中公式的抽象定义，以及它们的分类及解释。解释。q一阶语言一阶语言是用于一阶逻辑的形式语言，而一阶逻辑就是建是用于一阶逻辑的形式语言，而一阶逻辑就是建立在一阶语言基础上的逻辑体系，一阶语言本身不具备任立在一阶语言基础上的逻辑体系，一阶语言本身不具备任何意义，但可以根据需要被解释成具有某种含义。何意义，但可以根据需要被解释成具有某种含义。q一阶语言的形式是多种多样的，一阶语言的形式是多种多样的，本书给出的一阶语言是便本书

31、给出的一阶语言是便于将自然语言中的命题符号化的一阶语言，记为于将自然语言中的命题符号化的一阶语言，记为F F。一阶语言中的字母表一阶语言中的字母表一阶语言中的字母表一阶语言中的字母表定义定义4.1 4.1 一阶语言一阶语言F F的的字母表字母表定义如下定义如下:(1)(1)个体常项：个体常项：a,b,c,ai ,bi ,ci ,i 1(2)(2)个体变项：个体变项：x,y,z,xi,yi ,zi ,i 1(3)(3)函数符号函数符号：f,g,h,fi,gi,hi,i 1；当个体名称集合D给出时，n元函数符号f(x1，xn)可以是Dn到D的任意一个映射。(4)(4)谓词符号：谓词符号：F,G,H

32、,Fi,Gi,Hi,i 1；当个体名称集合D给出时，n元谓词符号P(x1，xn)可以是Dn上的任意一个谓词，换言之，是Dn到0,1的任意一个映射。(5)(5)量词符号量词符号:，(6)(6)联结词符号联结词符号:,:,(7)(7)括号与逗号括号与逗号:(,),:(,),，为何需要函数符号？为何需要函数符号？为何需要函数符号？为何需要函数符号？例如例如 符号化符号化“周红的父亲是教授周红的父亲是教授”：设设f(x)f(x)：x x的父亲；的父亲；P(x)P(x)：x x是教授；是教授；c c：周红：周红此时此时P(f(c)P(f(c)表示表示“周红的父亲是教授周红的父亲是教授”这一命题。这一命题

33、。函数的使用给谓词逻辑中的个体词表示函数的使用给谓词逻辑中的个体词表示带来了很大的方便带来了很大的方便否则就需要引入二元谓词否则就需要引入二元谓词g(x,y):x 是是 y 的父亲，的父亲，符号化为：符号化为：P(x)g(x,c)，不如函数简单明了。不如函数简单明了。一阶语言中的项一阶语言中的项一阶语言中的项一阶语言中的项定义定义4.2 4.2 一阶语言一阶语言F F的的项项的定义如下的定义如下:(1)(1)个体常项和个体变项是个体常项和个体变项是项项。(2)(2)若若(x(x1 1,x,x2 2,x,xn n)是任意的是任意的n n元函数，元函数，t t1 1,t,t2 2,t,tn n是任

34、是任意的意的n n个项，则个项，则(t(t1 1,t,t2 2,t,tn n)是是项项。(3)(3)所有的项都是有限次使用所有的项都是有限次使用(1)(1)，(2)(2)得到的。得到的。一阶语言中的原子公式一阶语言中的原子公式一阶语言中的原子公式一阶语言中的原子公式定义定义4.34.3 设设R(xR(x1 1,x,x2,2,x,xn n)是一阶语言是一阶语言F F的的任意任意n n元谓词，元谓词，t t1 1,t,t2 2,t,tn n是一阶语言是一阶语言F F的任意的的任意的n n个项，则称个项，则称R(tR(t1 1,t,t2 2,t,tn n)是一阶语言是一阶语言F F的的原子公式原子公

35、式。例如例如：1 1元谓词元谓词F(x)F(x)，G(x)G(x)，2 2元谓词元谓词H(x,y)H(x,y)，L(x,y)L(x,y)等都是等都是原子公式。原子公式。一阶语言一阶语言一阶语言一阶语言 F F F F 的合式公式的合式公式的合式公式的合式公式定义定义4.4 4.4 一阶语言一阶语言F F的的合式公式合式公式(well-formed formula)(well-formed formula)定义如下定义如下:(1)(1)原子公式是合式公式。原子公式是合式公式。(2)(2)若若A A是合式公式，则是合式公式，则(A)A)也是合式公式。也是合式公式。(3)(3)若若A A，B B是合

36、式公式，则是合式公式，则(AB)AB)，(AB)(AB)，(AB)(AB)，(A(AB)B)也是合式公式。也是合式公式。(4)(4)若若A A是合式公式，则是合式公式，则 xAxA，xAxA也是合式公式。也是合式公式。(5)(5)只有有限次的应用只有有限次的应用(1)(1)(4)(4)构成的符号串才是合式公式。构成的符号串才是合式公式。一阶语言一阶语言F F的合式公式也称为的合式公式也称为谓词公式谓词公式，简称，简称公式公式。qA A，B B代表任意公式，是元语言符号。代表任意公式，是元语言符号。q下文的讨论都是在一阶语言下文的讨论都是在一阶语言F F中，因而不再提及。中，因而不再提及。说说明

37、明自由出现与约束出现自由出现与约束出现自由出现与约束出现自由出现与约束出现定义定义4.54.5 指导变元、辖域、约束出现、自由出现指导变元、辖域、约束出现、自由出现q在公式在公式 xAxA和和 xAxA中，称中，称x x为为指导变元指导变元。q在公式在公式 xAxA和和 xAxA中，中，A A为相应量词的为相应量词的辖域辖域。q在在 x x和和 x x的辖域中，的辖域中，x x的所有出现都称为的所有出现都称为约束出现约束出现。qA A中不是约束出现的其他个体变项均称为是中不是约束出现的其他个体变项均称为是自由出现自由出现的。的。量词辖域的确定方法：量词辖域的确定方法：（1）若量词后）若量词后有

38、括号有括号，则，则括号内的子公式括号内的子公式就是该量就是该量词的辖域；词的辖域；（2）若量词后）若量词后无括号无括号，则，则与量词邻接的子公式与量词邻接的子公式为该为该量词的辖域。量词的辖域。例例例例确定以下公式各量词的辖域以及各个体变量为自由变确定以下公式各量词的辖域以及各个体变量为自由变元还是约束变元。元还是约束变元。（1 1）(x)(P(x)(x)(P(x)(y)R(x,y)y)R(x,y)；（2 2）(x)P(x)Q(x,y)x)P(x)Q(x,y)；（3 3）(x)(x)(y)(P(y,z)Q(x,y)(y)(P(y,z)Q(x,y)(x)R(x,y)x)R(x,y)；（4 4）(

39、x)(P(x)R(x)(x)(P(x)R(x)(y)Q(x,y)y)Q(x,y)。解解解解 在在(1)(1)中，中，P(x)P(x)中的中的x x，R(x,y)R(x,y)的的x x，y y都为约束变元。都为约束变元。在在(2)(2)中，中，P(x)P(x)中的中的x x为约束变元，为约束变元，Q(x,y)Q(x,y)中的中的x x，y y是自由变元。是自由变元。在在(3)(3)中，中，P(y,z)P(y,z)、Q(x,y)Q(x,y)中的中的x,yx,y都为约束变元，都为约束变元，z z为自由变元；为自由变元；R(x,y)R(x,y)中的中的x x为约束变元，为约束变元，y y为自由变元。为

40、自由变元。在在(4)(4)中，中，P(x)P(x)，R(x)R(x)中的中的x x为约束变元，为约束变元，Q(x,y)Q(x,y)中的中的x x为自由变元、为自由变元、y y为约束变元。为约束变元。变元混淆变元混淆变元混淆变元混淆（4 4）(x)(P(x)(P(x x)R()R(x x)()(y)Q(y)Q(x x,y),y)约束变约束变元元自由变元自由变元 在一个公式中，某一个变元的出现既可以是自由的，在一个公式中，某一个变元的出现既可以是自由的，又可以是约束的，如又可以是约束的，如(4)中的中的x。为了使得我们的研究。为了使得我们的研究更方便，而不致引起混淆，同时为了使公式给人以一更方便，

41、而不致引起混淆，同时为了使公式给人以一目了然的结果，对于表示不同意思的个体变元，我们目了然的结果，对于表示不同意思的个体变元，我们总是以不同的变量符号来表示。总是以不同的变量符号来表示。改名规则改名规则改名规则改名规则约束变元的改名规则约束变元的改名规则（1 1）将量词中出现的变元以及该量词辖域中此）将量词中出现的变元以及该量词辖域中此 变量的所有约束出现都用新的个体变元替换；变量的所有约束出现都用新的个体变元替换；（2 2）新的变元应有别于公式中的所有其它变量。）新的变元应有别于公式中的所有其它变量。代入规则代入规则代入规则代入规则自由变元的代入规则自由变元的代入规则（1 1）将公式中出现该

42、自由变元的每一处都用新的）将公式中出现该自由变元的每一处都用新的个体变元替换；个体变元替换；（2 2）新变元不允许在原公式中以任何约束形式出）新变元不允许在原公式中以任何约束形式出现。现。例例例例（1 1）将公式）将公式(x)(P(x)Q(x,y)R(x,y)x)(P(x)Q(x,y)R(x,y)中的约中的约束变元束变元x x进行改名；进行改名；（2 2）将公式）将公式(x)(P(x)Q(x,y)R(x,y)x)(P(x)Q(x,y)R(x,y)中的约中的约束变元束变元y y进行代入。进行代入。解解 利用改名规则对利用改名规则对x x进行改名，则：进行改名，则：(z)(P(z)Q(z,y)R(

43、x,y)z)(P(z)Q(z,y)R(x,y)(z)(P(z)R(x,y)R(x,y)z)(P(z)R(x,y)R(x,y)(y)(P(y)R(y,y)R(x,y)y)(P(y)R(y,y)R(x,y)-对对-错错-错错 利用利用代入代入规则规则对对y进行代入，则：进行代入，则：(x)(P(x)Q(x,z)R(x,z)(x)(P(x)Q(x,z)R(x,y)(x)(P(x)Q(x,x)R(x,x)-对对-错错-错错改名规则和代入规则的关系改名规则和代入规则的关系改名规则和代入规则的关系改名规则和代入规则的关系改名规则和代入规则之间的共同点都是不能改变原有改名规则和代入规则之间的共同点都是不能改

44、变原有的约束关系，而不同点是：的约束关系，而不同点是：（1 1）施行的对象不同：改名规则是对约束变元施行，）施行的对象不同：改名规则是对约束变元施行，代入规则是对自由变元施行；代入规则是对自由变元施行；（2 2）施行的范围不同：改名规则可以只对公式中的一）施行的范围不同：改名规则可以只对公式中的一个量词及其辖域内施行，即只对公式的一个子公式施个量词及其辖域内施行，即只对公式的一个子公式施行；而代入规则必须对整个公式同一个自由变元的所行；而代入规则必须对整个公式同一个自由变元的所有自由出现同时施行，即必须对整个公式施行；有自由出现同时施行，即必须对整个公式施行；改名规则和代入规则的关系（续）改名

45、规则和代入规则的关系（续）改名规则和代入规则的关系（续）改名规则和代入规则的关系（续）（3 3）施行后的结果不同：改名后，公式含义不变，）施行后的结果不同：改名后，公式含义不变，因为约束变元只改名为另一个个体变元，约束关系不因为约束变元只改名为另一个个体变元，约束关系不改变，约束变元不能改名为个体常量；代入后，不仅改变，约束变元不能改名为个体常量；代入后，不仅可用另一个个体变元进行代入，并且也可用个体常量可用另一个个体变元进行代入，并且也可用个体常量去代入，从而使公式由具有普遍意义变为仅对该个体去代入，从而使公式由具有普遍意义变为仅对该个体常量有意义，即公式的含义改变了。常量有意义，即公式的含

46、义改变了。封闭的公式封闭的公式封闭的公式封闭的公式定义定义4.64.6 设设A A是任意的公式，若是任意的公式，若A A中不含有自由出现的个体变中不含有自由出现的个体变项，则称项，则称A A为为封闭的公式封闭的公式，简称，简称闭式闭式。例如：例如：x y(F(x)G(y)H(x,y)为闭式，为闭式，x(F(x)G(x,y)不是闭式不是闭式。一阶公式的解释一阶公式的解释一一阶阶公公式式没没有有确确定定的的意意义义，一一旦旦将将其其中中的的变变项项（项项的的变变项项 、谓谓词词变变项项）用用指指定定的的常常项项代代替后，所得公式就具备一定的意义，有时就变成命题了。替后，所得公式就具备一定的意义，有

47、时就变成命题了。一阶公式的解释一阶公式的解释一阶公式的解释一阶公式的解释定义定义4.74.7 一阶公式的一阶公式的解释解释I由下面由下面4 4部分组成部分组成:(a)a)非空个体域非空个体域D DI。(b)D(b)DI中一些特定元素的集合中一些特定元素的集合 。(c)Dc)DI上特定函数集合上特定函数集合|i,n11。(d)D(d)DI上特定谓词的集合上特定谓词的集合|i,n11。qA A中的第中的第i i个个n n元函数变项元函数变项 被解释为某个函数常项被解释为某个函数常项qA A中的第中的第i i个个n n元谓词变项元谓词变项 被解释成某个谓词常项被解释成某个谓词常项对解释对解释对解释对

48、解释I I I I的几点说明的几点说明的几点说明的几点说明q被解释的公式不一定全部包含解释中的四个部分。被解释的公式不一定全部包含解释中的四个部分。q被解释的公式被解释的公式A A中的个体变项均取值于中的个体变项均取值于D DI。qA A中的中的个体常项个体常项 ai 被解释成被解释成 。q在解释的定义中引进了几个元语言符号，如在解释的定义中引进了几个元语言符号，如给定解释给定解释I 如下：如下：(a)个体域个体域D=R(b)(c)(d)写出下列公式在写出下列公式在I下的解释下的解释,并指出它的真值并指出它的真值.(1)xF(f(x,a),g(x,a)例例例例 x(x+0=x 0)真真(2)x

49、 y(F(f(x,y),g(x,y)F(x,y)x y(x+y=x yx=y)假假(3)xF(g(x,y),a)x(x y=0)真值不定真值不定,不是命题不是命题定理定理4.14.1 封闭的公式在任何解释下都变成命题。封闭的公式在任何解释下都变成命题。一阶公式的分类一阶公式的分类一阶公式的分类一阶公式的分类定义定义4.8 4.8 永真式、永假式、可满足式永真式、永假式、可满足式q设设A A为一个公式，若为一个公式，若A A在任何解释下均为真，则称在任何解释下均为真，则称A A为为永真式永真式(或称或称逻辑有效式逻辑有效式)。q设设A A为一个公式，若为一个公式，若A A在任何解释下均为假，则称

50、在任何解释下均为假，则称A A为为矛盾式矛盾式(或或永假式永假式)。q设设A A为一个公式，若至少存在一个解释使为一个公式，若至少存在一个解释使A A为真，则称为真，则称A A为为可可满足式满足式。q永真式一定是可满足式，但可满足式不一定是永真式。永真式一定是可满足式，但可满足式不一定是永真式。q在一阶逻辑中，到目前为止，还没有找到一种可行的算在一阶逻辑中，到目前为止，还没有找到一种可行的算法，用来判断任意一个公式是否是可满足的，这与命题法，用来判断任意一个公式是否是可满足的，这与命题逻辑的情况完全不同。逻辑的情况完全不同。q但对某些特殊的公式还是可以判断的。但对某些特殊的公式还是可以判断的。