离散数学课件04一阶逻辑基本概念.ppt

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

1、第第第第4 4 4 4章章章章 一阶逻辑基本概念一阶逻辑基本概念一阶逻辑基本概念一阶逻辑基本概念离离 散散 数数 学学中国地质大学本科生课程中国地质大学本科生课程本章说明本章说明本章说明本章说明q本章的主要内容本章的主要内容一阶逻辑基本概念、命题符号化一阶逻辑基本概念、命题符号化一阶逻辑公式、解释及分类一阶逻辑公式、解释及分类q本章与后续各章的关系本章与后续各章的关系克服命题逻辑的局限性克服命题逻辑的局限性是第五章的先行准备是第五章的先行准备 引言引言 例如例如(著名的苏格拉底三段论著名的苏格拉底三段论)（1 1）所有的人都是要死的；）所有的人都是要死的；（2 2）苏格拉底是人。）苏格拉底是人

2、。（3 3）苏格拉底是要死的。）苏格拉底是要死的。命题逻辑能够解决的问题是有命题逻辑能够解决的问题是有局局限性限性的。只能进行的。只能进行命题间关系命题间关系的推的推理，无法解决与理，无法解决与命题的结构和成分命题的结构和成分有关的推理问题。有关的推理问题。苏格拉底三段论苏格拉底三段论 p p：所有的人都是要死的；：所有的人都是要死的；q q：苏格拉底是人。：苏格拉底是人。r r：苏格拉底是要死的。：苏格拉底是要死的。可见，可见，p p，q q，r r为不同的命题，无法体现三者相互之间的为不同的命题，无法体现三者相互之间的联系。联系。q问题在于这类推理中，各命题之间的逻辑关系不是体现问题在于这

3、类推理中，各命题之间的逻辑关系不是体现在原子命题之间，而是体现在在原子命题之间，而是体现在构成原子命题的内部成分构成原子命题的内部成分之间之间。对此，命题逻辑将无能为力。对此，命题逻辑将无能为力。本章内容本章内容 一阶逻辑命题符号化一阶逻辑命题符号化1一阶逻辑公式及其解释一阶逻辑公式及其解释2 本章学习要求本章学习要求 重点掌握重点掌握了解了解11 1 谓词逻辑符谓词逻辑符号化及真值号化及真值2 2 谓词公式的谓词公式的有效性和基本有效性和基本等价公式等价公式3谓词公式及其谓词公式及其解释解释 21 1 谓词公式的谓词公式的解释和真值解释和真值2 2 自由变元和自由变元和约束变元约束变元一般掌

4、握一般掌握4.1一阶逻辑命题符号化一阶逻辑命题符号化q一阶逻辑命题符号化的三个基本要素一阶逻辑命题符号化的三个基本要素个体词个体词谓词谓词量词量词q个体词及相关概念个体词及相关概念q个体词一般是充当主语的名词或代词。个体词一般是充当主语的名词或代词。说明说明q个个体体词词：指指所所研研究究对对象象中中可可以以独独立立存存在在的的具具体体或或抽抽象的客体。象的客体。q举例举例命题：电子计算机是科学技术的工具。命题：电子计算机是科学技术的工具。个体词：电子计算机。个体词：电子计算机。命题：他是三好学生命题：他是三好学生。个体词：他。个体词：他。q个个体体常常项项：表表示示具具体体或或特特定定的的客

5、客体体的的个个体体词词，用用小小写写字字母母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,R R,。q全总个体域（全总个体域（universeuniverse）宇宙间一切事物组成宇宙间一切事物组成 。个体词及相关概念个体词及相关概念个体词及相关概念个体词及相关概念q本教材在论

6、述或推理中，如果没有指明所采本教材在论述或推理中，如果没有指明所采用的个体域，都是使用的全总个体域。用的个体域，都是使用的全总个体域。说明说明谓词及相关概念谓词及相关概念q谓词（谓词（predicatepredicate）是用来刻画个体词性质及个体词之间相是用来刻画个体词性质及个体词之间相互关系的词。互关系的词。(1)(1)是无理数。是无理数。是个体常项，是个体常项，“是无理数是无理数”是谓词，记为是谓词，记为F F，命题符号化命题符号化为为F(F()。(2)(2)x x是有理数。是有理数。x x是个体变项，是个体变项，“是有理数是有理数”是谓词，记为是谓词，记为G G，命题符号化命题符号化为

7、为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，命题符号化为命题符号化为L(x,y)L(x,y)。q谓词常项谓词常项：表示具体性质或关系的谓词。用大写字母表示。：表示具体性质或关系的谓词。用大写字母表示。如如(1)(1)、(2)(2)、(3)(3)中谓词中谓词F F、G G、

8、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具有性质具有性质P P。n2n2时，多元谓词时，多元谓词表示表示x x1 1,x,x2 2,x,xn n具有关系具有关系P P。q0 0元谓词元谓词：不含个体变项的谓词。如：不含个体变项的谓词。如F(a)F(a)、G(a,

9、b)G(a,b)、P(a P(a1 1,a,a2 2,a,an n)。qn n元谓词是命题吗？元谓词是命题吗？不是，只有用谓词常项取代不是，只有用谓词常项取代P P，用个体常项取代用个体常项取代x x1 1,x,x2 2,x xn n时，才能使时，才能使n n元谓词变为命题。元谓词变为命题。思考思考谓词及相关概念谓词及相关概念谓词及相关概念谓词及相关概念更一般地更一般地 P(x)P(x)：x x是电子科技大学的学生。是电子科技大学的学生。x x：个体词：个体词P P：谓词：谓词P(x):P(x):命题函数命题函数P(x)P(x)结论结论 1.1.谓词中谓词中个体词的顺序是十分重要个体词的顺序是

10、十分重要的，不能随意变更。的，不能随意变更。如命题如命题F(bF(b,c),c)为为“真真”，但命题，但命题F(cF(c,b),b)为为“假假”；2.2.一元谓词一元谓词用以描述用以描述某一个个体的某种特性某一个个体的某种特性，而，而n n元谓元谓词词则用以描述则用以描述n n个个体之间的关系个个体之间的关系。3.3.0 0元谓词元谓词(不含个体词的不含个体词的)实际上就是一般的命题；实际上就是一般的命题；结论（续）结论（续）4.4.具体命题的谓词表示形式具体命题的谓词表示形式和和n n元命题函数元命题函数(n(n元谓元谓词词)是不同的，前者是有真值的，而后者不是命是不同的，前者是有真值的，而

11、后者不是命题，它的真值是不确定的。如上例中题，它的真值是不确定的。如上例中S(aS(a)是有是有真值的，但真值的，但S(xS(x)却没有真值；却没有真值；5.5.一个一个n n元谓词不是一个命题元谓词不是一个命题，但，但将将n n元谓词中的元谓词中的个体变元都用个体域中具体的个体取代个体变元都用个体域中具体的个体取代后，就后，就成为一个命题成为一个命题。而且，个体变元在不同的个体。而且，个体变元在不同的个体域中取不同的值对是否成为命题及命题的真值域中取不同的值对是否成为命题及命题的真值有很大的影响。有很大的影响。例题例题例例4.14.1 将下列命题在一阶逻辑中用将下列命题在一阶逻辑中用0 0元

12、谓词符号化，并讨论真值。元谓词符号化，并讨论真值。(1)(1)只有只有2 2是素数，是素数，4 4才是素数。才是素数。(2)(2)如果如果5 5大于大于4 4，则，则4 4大于大于6.6.解：解：(1)(1)设一元谓词设一元谓词F(x):xF(x):x是素数，是素数，a:2a:2，b:4b:4。命题符号化为命题符号化为0 0元谓词的蕴涵式元谓词的蕴涵式 F(b)F(a)F(b)F(a)由于此蕴涵前件为假，所以命题为真。由于此蕴涵前件为假，所以命题为真。(2)(2)设二元谓词设二元谓词G(x,y):xG(x,y):x大于大于y y，a:4a:4，b:5b:5，c:6c:6。命题符号化为命题符号化

13、为0 0元谓词的蕴涵式元谓词的蕴涵式 G(b,a)G(a,c)G(b,a)G(a,c)由于由于G(b,a)G(b,a)为真，而为真，而G(a,c)G(a,c)为假，所以命题为假。为假，所以命题为假。例题例题将命题将命题“这只大红书柜摆满了那些古书。这只大红书柜摆满了那些古书。”符号化符号化.(1)(1)设设 F(x,y)F(x,y)：x x摆满了摆满了y y，R(x)R(x)：x x是大红书柜是大红书柜Q(y)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

14、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)量量词词（quantifiersquantifiers）是是表表示示个个体体常常项项或或个个体体变变项项之之间间数数量量关关系系的词。的词。1 1.全称量词全称量词：符号化为：符号化为“”q日日常常生生活活和和数数学

15、学中中所所用用的的“一一切切的的”、“所所有有的的”、“每每一一个个”、“任意的任意的”、“凡凡”、“都都”等词可统称为全称量词。等词可统称为全称量词。qx x表表示示个个体体域域里里的的所所有有个个体体，xF(xxF(x)表表示示个个体体域域里里所所有有个个体体都有性质都有性质F F。2 2.存在量词存在量词：符号化为：符号化为“”q日日常常生生活活和和数数学学中中所所用用的的“存存在在”、“有有一一个个”、“有有的的”、“至少有一个至少有一个”等词统称为存在量词。等词统称为存在量词。qy y表表示示个个体体域域里里有有的的个个体体，yG(yyG(y)表表示示个个体体域域里里存存在在个个体体

16、具具有性质有性质G G等。等。量词及相关概念量词及相关概念量词及相关概念量词及相关概念不便之处不便之处1.1.从从书写上书写上十分不便，总要特别注明个体域；十分不便，总要特别注明个体域；2.2.在同一个比较复杂的句子中，对于不同命题函数中的个在同一个比较复杂的句子中，对于不同命题函数中的个体可能属于不同的个体域，此时体可能属于不同的个体域，此时无法清晰无法清晰表达；表达；如例如例 (所有的所有的老虎都要吃人；老虎都要吃人；)和和(有一些有一些人登上过月球；人登上过月球；)的合取的合取 x x 人人 x x 老虎老虎(x)P(x)(x)R(x)不便之处不便之处(续续)3.3.若若个体域的注明不清

17、楚，个体域的注明不清楚，将将造成造成无法确定其真值无法确定其真值。即。即对于对于同一个同一个n n元谓词，不同的个体域有可能带来不同的真值元谓词，不同的个体域有可能带来不同的真值。例如例如 对于语句对于语句“(x)(x+6=5)”x)(x+6=5)”可表示为：可表示为：“有有一些一些x x，使得，使得x+6=5”x+6=5”。该语句在下面两种个体域下有不。该语句在下面两种个体域下有不同的真值：同的真值：（a a）在实数范围内时，确有在实数范围内时，确有x=-1x=-1使得使得x+6=5x+6=5，因此，因此，(x)(x+6=5)x)(x+6=5)为为“真真”；（b b）在正整数范围内时，则找不

18、到任何在正整数范围内时，则找不到任何x x，使得，使得x+6=5x+6=5为为“真真”，所以，所以，(x)(x+6=5)x)(x+6=5)为为“假假”。不便之处的根源不便之处的根源对了，都是因为需要特别标注每个谓词对了，都是因为需要特别标注每个谓词的个体域所致！的个体域所致！全总个体域全总个体域特性谓词特性谓词新的问题出现了，新的问题出现了，U(x)U(x)如何与如何与(x)P(x)x)P(x)结合才符合逻辑呢？结合才符合逻辑呢？U(x)U(x)：x x是老虎是老虎x x老虎老虎谓词逻辑符号化的两条规则谓词逻辑符号化的两条规则 统一个体域为统一个体域为全总个体域全总个体域，而对每一个句子中个体

19、变，而对每一个句子中个体变量的变化范围用一元量的变化范围用一元特性谓词特性谓词刻划之。这种特性谓词在刻划之。这种特性谓词在加入到命题函数中时必定遵循如下原则：加入到命题函数中时必定遵循如下原则：（1 1）对于）对于全称量词全称量词(x)x)，刻划其对应个体域的特性谓，刻划其对应个体域的特性谓词作为词作为蕴涵式之前件蕴涵式之前件加入。加入。（2 2）对于）对于存在量词存在量词(x)x)，刻划其对应个体域的特性谓，刻划其对应个体域的特性谓词作为词作为合取式之合取项合取式之合取项加入。加入。例例4.24.2 在个体域分别限制为在个体域分别限制为(a)a)和和(b)b)条件时，将下面两个条件时，将下面

20、两个命题符号化命题符号化:(1)(1)凡人都呼吸。凡人都呼吸。(2)(2)有的人用左手写字。有的人用左手写字。其中其中:(:(a)a)个体域个体域D D1 1为人类集合；为人类集合；(b)b)个体域个体域D D2 2为全总个体域。为全总个体域。一阶逻辑命题符号化一阶逻辑命题符号化一阶逻辑命题符号化一阶逻辑命题符号化解解:(:(a)a)个体域为人类集合。个体域为人类集合。令令F(x):xF(x):x呼吸。呼吸。G(x):xG(x):x用左手写字。用左手写字。(1)(1)在个体域中除了人外，再无别的东西，因而在个体域中除了人外，再无别的东西，因而“凡人都呼吸凡人都呼吸”应符号化为应符号化为 xF(

21、x)xF(x)(2)(2)在个体域中除了人外，再无别的东西，因而在个体域中除了人外，再无别的东西，因而“有的人用左有的人用左手写字手写字”符号化为符号化为 xG(x)xG(x)(b)b)个体域为全总个体域个体域为全总个体域。即除人外，还有万物，所以必须考虑将人先分离出来。即除人外，还有万物，所以必须考虑将人先分离出来。令令F(x):xF(x):x呼吸。呼吸。G(x):xG(x):x用左手写字。用左手写字。M(x):xM(x):x是人。是人。(1)“(1)“凡人都呼吸凡人都呼吸”应符号化为应符号化为 x(M(x)F(x)x(M(x)F(x)(2)(2)“有的人用左手写字有的人用左手写字”符号化为

22、符号化为 x(M(x)G(x)x(M(x)G(x)q在使用全总个体域时，要将人从其他事物中区别出来，为此在使用全总个体域时，要将人从其他事物中区别出来，为此引进了谓词引进了谓词M(x)M(x)，称为称为特性谓词特性谓词。q同一命题在不同的个体域中符号化的形式可能不同。同一命题在不同的个体域中符号化的形式可能不同。q思考：思考：在全总个体域中，能否将在全总个体域中，能否将(1)(1)符号化为符号化为 x(M(x)F(x)x(M(x)F(x)？能否将能否将(2)(2)符号化为符号化为 x(M(x)G(x)x(M(x)G(x)？结结论论例题例题例例4.3 在个体域限制为在个体域限制为(a)a)和和(

23、b)b)条件时，将下列命题符号化条件时，将下列命题符号化:(1)(1)对于任意的对于任意的x x，均有均有x x2 2-3x+2=(x-1)(x-2)-3x+2=(x-1)(x-2)。(2)(2)存在存在x x，使得使得x+5=3x+5=3。其中其中:(:(a)a)个体域个体域D D1 1=N(N=N(N为自然数集合为自然数集合)(b)b)个体域个体域D D2 2=R(R=R(R为实数集合为实数集合)(a)a)令令F(x):xF(x):x2 2-3x+2=(x-1)(x-2)-3x+2=(x-1)(x-2)，G(x):x+5=3G(x):x+5=3。命题命题(1)(1)的符号化形式为的符号化形

24、式为 xF(x)xF(x)（真命题）真命题）命题命题(2)(2)的符号化形式为的符号化形式为 xG(x)xG(x)（假命题）假命题）(b)b)在在D D2 2内，内，(1)(1)和和(2)(2)的符号化形式同的符号化形式同(a)a)，皆为真命题。皆为真命题。q在不同个体域内，同一个命题的符号化形式可能不在不同个体域内，同一个命题的符号化形式可能不同，也可能相同。同，也可能相同。q同一个命题，在不同个体域中的真值也可能不同。同一个命题，在不同个体域中的真值也可能不同。说明说明例例4.44.4 将下列命题符号化，并讨论真值。将下列命题符号化，并讨论真值。（1 1）所有的人长着黑头发。）所有的人长着

25、黑头发。（2 2）有的人登上过月球。）有的人登上过月球。（3 3）没有人登上过木星。）没有人登上过木星。（4 4）在美国留学的学生未必都是亚洲人。）在美国留学的学生未必都是亚洲人。分析：谓词逻辑中命题的符号化，主要考虑：分析：谓词逻辑中命题的符号化，主要考虑：(1)(1)非空个体域的选取。若是为了确定命题的真值，一般约非空个体域的选取。若是为了确定命题的真值，一般约定在某个个体域上进行，否则，在由一切事物构成的全总定在某个个体域上进行，否则，在由一切事物构成的全总个体域上考虑问题时，需要增加一个指出个体变量变化范个体域上考虑问题时，需要增加一个指出个体变量变化范围的特性谓词。围的特性谓词。(2

26、)(2)量词的使用及作用范围。量词的使用及作用范围。(3)(3)正确地语义。正确地语义。例题例题例题例题例题例题解：没有提出个体域，所以认为是全总个体域。解：没有提出个体域，所以认为是全总个体域。（1 1）所有的人长着黑头发。）所有的人长着黑头发。令令F(x):xF(x):x长着黑头发，长着黑头发，M(x):xM(x):x是人。命题符号化为是人。命题符号化为 x(M(x)F(x)x(M(x)F(x)。命题真值为假。命题真值为假。（2 2）有的人登上过月球。）有的人登上过月球。令令G(x):xG(x):x登上过月球登上过月球，M(x):xM(x):x是人。命题符号化为是人。命题符号化为 x(M(

27、x)G(x)x(M(x)G(x)。命题真值为真。命题真值为真。例题例题（3 3）没有人登上过木星。）没有人登上过木星。令令H(x):xH(x):x登上过木星登上过木星，M(x):xM(x):x是人。命题符号化为是人。命题符号化为 x(M(x)H(x)x(M(x)H(x)。命题真值为真。命题真值为真。（4 4）在美国留学的学生未必都是亚洲人。在美国留学的学生未必都是亚洲人。令令F(x):xF(x):x是在美国留学的学生，是在美国留学的学生，G(x):xG(x):x是亚洲人。符号化是亚洲人。符号化 x(F(x)G(x)x(F(x)G(x)命题真值为真。命题真值为真。谓词翻译难点谓词翻译难点 1.1

28、.一一元元谓谓词词用用以以描描述述某某一一个个个个体体的的某某种种特特性性，而而n n元谓词元谓词则用以描述则用以描述的的n n个个体之间关系个个体之间关系；2.2.如如有有多多个个量量词词，则则读读的的顺顺序序按按从从左左到到右右的的顺顺序序；另另外外，量量词词对对变变元元的的约约束束，往往往往与与量量词词的的次次序序有有关关，不不同同的的量量词词次次序序，可可以以产产生生不不同同的的真真值值，此此时时对对多多个个量量词词同同时时出出现现时时，不不能能随随意意颠颠倒倒它它们们的的顺序，颠倒后会改变原有的含义。顺序，颠倒后会改变原有的含义。谓词翻译难点（续）谓词翻译难点（续）3.3.根根据据命

29、命题题的的实实际际意意义义，选选用用全全称称量量词词或或存存在在量量词词。全全称称量量词词加加入入时时，其其刻刻划划个个体体域域的的特特性性谓谓词词将将以以蕴蕴涵涵的的前前件件加加入入，存存在在量量词词加加入入时时，其其刻刻划划个个体体域域的的特特性性谓谓词将以词将以合取项合取项加入；加入；4.4.有有些些命命题题在在进进行行符符号号化化时时，由由于于语语言言叙叙述述不不同同，可可能能翻翻译译不不同同，但但它它们们表表示示的的意意思思是是相相同同的的，即即句句子子符符号号化形式可不止一种化形式可不止一种。例题例题 n n元谓词的符号化元谓词的符号化例例4.54.5 将下列命题符号化将下列命题符

30、号化（1 1）兔子比乌龟跑得快。）兔子比乌龟跑得快。（2 2）有的兔子比所有的乌龟跑得快。）有的兔子比所有的乌龟跑得快。（3 3）并不是所有的兔子都比乌龟跑得快。）并不是所有的兔子都比乌龟跑得快。（4 4）不存在跑得同样快的两只兔子。）不存在跑得同样快的两只兔子。解解：令：令 F(x):xF(x):x是兔子，是兔子，G(y):yG(y):y是乌龟，是乌龟，H(x,y):xH(x,y):x比比y y跑得快，跑得快，L(x,y):xL(x,y):x与与y y跑得同样快。跑得同样快。（1 1）x x y(F(x)y(F(x)G(y)G(y)H(x,y)H(x,y)（2 2）x(F(x)x(F(x)y

31、 y(G(y)(G(y)H(x,y)H(x,y)（3 3）x x y(F(x)y(F(x)G(y)G(y)H(x,y)H(x,y)（4 4）x x y(F(x)y(F(x)F(y)L(x,y)F(y)L(x,y)一阶逻辑命题符号化时需要注意的事项一阶逻辑命题符号化时需要注意的事项q分析命题中表示性质和关系的谓词，分别符号为一元和分析命题中表示性质和关系的谓词，分别符号为一元和n n（n n 2 2）元谓词。元谓词。q根据命题的实际意义选用全称量词或存在量词。根据命题的实际意义选用全称量词或存在量词。q一般说来，多个量词出现时，它们的顺序不能随意调换。一般说来，多个量词出现时，它们的顺序不能随意

32、调换。例如，考虑个体域为实数集，例如，考虑个体域为实数集，H(xH(x，y)y)表示表示x+y=10 x+y=10，则则命命题题“对对于于任任意意的的x x，都都存存在在y y，使使得得x+y=10”x+y=10”的的符符号号化化形形式为式为 x x y yH(x,y)H(x,y)，为真命题。为真命题。如果改变两个量词的顺序，得如果改变两个量词的顺序，得 y y x xH(x,y)H(x,y)，为假命题。为假命题。q有些命题的符号化形式可不止一种。（例有些命题的符号化形式可不止一种。（例4.54.5之之(3)(3)）x x y(F(x)y(F(x)G(y)G(y)H(x,y)H(x,y)x x

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

34、成具有某种含义。q一阶语言的形式是多种多样的，一阶语言的形式是多种多样的，本书给出的一阶语言是便本书给出的一阶语言是便于将自然语言中的命题符号化的一阶语言，记为于将自然语言中的命题符号化的一阶语言，记为F F。一阶语言中的字母表一阶语言中的字母表定义定义4.14.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(4)(4)谓词符号：谓词符号：F,G,H,Fi,Gi,Hi,

35、i 1(5)(5)量词符号量词符号:，(6)(6)联结词符号联结词符号:,:,(7)(7)括号与逗号括号与逗号:(,),:(,),，一阶语言一阶语言L L (续续)定义定义4.24.2 L L 的项的项的定义如下：的定义如下：(1)(1)个体常项和个体变项是项个体常项和个体变项是项.(2)(2)若若(x x1 1,x x2 2,x xn n)是任意的是任意的n n元函数，元函数，t t1 1,t t2 2,t tn n是任意是任意 的的n n个项，则个项，则(t t1 1,t t2 2,t tn n)是项是项.(3)(3)所有的项都是有限次使用所有的项都是有限次使用(1),(2)(1),(2)

36、得到的得到的.定义定义4.34.3 设设R R(x x1 1,x x2 2,x xn n)是是L L 的任意的任意n n元谓词，元谓词，t t1 1,t t2 2,t tn n是是L L 的任意的任意n n个项，则称个项，则称R R(t t1 1,t t2 2,t tn n)是是原子公式原子公式一阶语言一阶语言L L(续续)定义定义4.44.4 L L 的合式公式的合式公式定义如下：定义如下：(1)(1)原子公式是合式公式原子公式是合式公式 (2)(2)若若A A是合式公式是合式公式,则则(A A)也是合式公式也是合式公式(3)(3)若若A A,B B是是合合式式公公式式,则则(A A B B

37、),),(A A B B),),(A AB B),),(A AB B)也也 是合式公式是合式公式(4)(4)若若A A是合式公式是合式公式,则则 xAxA,xAxA也是合式公式也是合式公式(5)(5)只有有限次地应用只有有限次地应用(1)(4)(1)(4)形成的符号串才是合式公式形成的符号串才是合式公式.合式公式又称合式公式又称谓词公式谓词公式,简称简称公式公式量词的辖域量词的辖域定义定义4.54.5 在公式在公式 xAxA和和 xAxA中中,称称x x为为指导变元指导变元,A A为相应量为相应量词的词的辖域辖域.在在 x x和和 x x的的辖域辖域中中,x x的所有出现称为的所有出现称为约束

38、出现约束出现，A A中不是约束出现的其他变项称为中不是约束出现的其他变项称为自由出现自由出现例例6 6 公式公式 x x(F F(x x,y y)yGyG(x x,y y,z z)x x的辖域的辖域:(F F(x x,y y)yGyG(x x,y y,z z)，指导变元为指导变元为x x y y的辖域的辖域:G G(x x,y y,z z)，指导变元为指导变元为y y x x的两次出现均为约束出现的两次出现均为约束出现 y y的第一次出现为自由出现的第一次出现为自由出现,第二次出现为约束出现第二次出现为约束出现z z为自由出现为自由出现.谓词合式公式难点谓词合式公式难点3命题逻辑与谓命题逻辑与

39、谓词逻辑中的公词逻辑中的公式及其解释的式及其解释的不同不同1掌握并能够灵掌握并能够灵活运用谓词，活运用谓词，个体词和量词；个体词和量词；2注意量词的作注意量词的作用域。通过紧用域。通过紧跟量词后面的跟量词后面的是否为括号进是否为括号进行判定；行判定；例例4.64.6 指出下列各公式中的指导变元，各量词的辖域，自由出指出下列各公式中的指导变元，各量词的辖域，自由出现以及约束出现的个体变项。现以及约束出现的个体变项。(1)(1)x x(F(F(x x,y)G(,y)G(x x,z),z)(2)(2)x x(F(F(x x)G(y)G(y)y y(H(x)L(x,(H(x)L(x,y y,z),z)

40、例题例题例题例题解答解答(1)(1)x x是指导变元。量词是指导变元。量词 的辖域的辖域A=(F(x,y)G(x,z)A=(F(x,y)G(x,z)。在在A A中，中，x x的两次出现均是约束出现。的两次出现均是约束出现。y y和和z z均为自由出现。均为自由出现。(2)(2)前件上量词前件上量词 的指导变元为的指导变元为x x，量词量词 的辖域的辖域A=(F(x)G(y)A=(F(x)G(y)，x x在在A A中是约束出现的，中是约束出现的，y y在在A A中是自由出中是自由出现的。后件中量词现的。后件中量词 的指导变元为的指导变元为y y，量词量词 的辖域为的辖域为B=(H(x)L(x,y

41、,z)B=(H(x)L(x,y,z)，y y在在B B中是约束出现的，中是约束出现的，x x、z z在在B B中中均为自由出现的。均为自由出现的。例例确定以下公式各量词的辖域以及各个体变量为自由变确定以下公式各量词的辖域以及各个体变量为自由变元还是约束变元。元还是约束变元。（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(x,y)Q(y,z)y)(P(x,y)Q(y,z)(x)R(x,y)x)R(x,y)；（4 4）(x)(P(x)R(x)(x)(P(x)R(x)(y)Q

42、(x,y)y)Q(x,y)。变元混淆变元混淆（4 4）(x)(P(x)(P(x x)R()R(x x)()(y)Q(y)Q(x x,y),y)约束变约束变元元自由变自由变元元 在一个公式中，某一个变元的出现在一个公式中，某一个变元的出现即可以是自由的，又即可以是自由的，又可以是约束的可以是约束的，如，如(4)(4)中的中的x x。为了使得我们的研究更方便，。为了使得我们的研究更方便，而不致引起混淆，同时为了使其式子给大家以一目了然的而不致引起混淆，同时为了使其式子给大家以一目了然的结果，对于表示不同意思的个体变元，我们总是以结果，对于表示不同意思的个体变元，我们总是以不同的不同的变量符号变量符

43、号来表示之。来表示之。本书中的记法本书中的记法q用用A(xA(x1 1,x,x2 2,x,xn n)表示含表示含x x1 1,x,x2 2,x,xn n自由出现的公式。自由出现的公式。q用用表示任意的量词表示任意的量词 或或，则则xx1 1A(xA(x1 1,x,x2 2,x,xn n)是含有是含有x x2 2,x,x3 3,x,xn n自由出现的公式，可记为自由出现的公式，可记为A A1 1(x(x2 2,x,x3 3,x,xn n)。q类似的，类似的，xx2 2xx1 1A(xA(x1 1,x,x2 2,x,xn n)可记为可记为A A2 2(x(x3 3,x,x4 4,x,xn n)qx

44、xn-1n-1xxn-2n-2xx1 1A(xA(x1 1,x,x2 2,x,xn n)中只含有中只含有x xn n是自由出现是自由出现的个体变项，可以记为的个体变项，可以记为A An-1n-1(x(xn n)。qxxn nxx1 1A(xA(x1 1,x,x2 2,x,xn n)没有自由出现的个体变项。没有自由出现的个体变项。闭式闭式:不含自由出现的个体变项的公式不含自由出现的个体变项的公式.例题例题4.74.7例例4.74.7 将下列两个公式中的变项指定成常项使其成为命题将下列两个公式中的变项指定成常项使其成为命题:(1)(1)x(F(x)G(x)x(F(x)G(x)(2)(2)x x y

45、(F(x)F(y)G(x,y)H(f(x,y),g(x,y)y(F(x)F(y)G(x,y)H(f(x,y),g(x,y)(1)(1)指定个体变项的变化范围，并且指定谓词指定个体变项的变化范围，并且指定谓词F F，G G的含义，下的含义，下面给出两种指定法面给出两种指定法:(a)a)令个体域令个体域D D1 1为全总个体域，为全总个体域，F(x)F(x)为为x x是人，是人，G(x)G(x)为为x x是黄种人，是黄种人，则命题为则命题为“所有人都是黄种人所有人都是黄种人”，这是假命题。，这是假命题。(b)b)令个体域令个体域D D2 2为实数集合为实数集合R R，F(x)F(x)为为x x是自

46、然数，是自然数，G(x)G(x)为为x x是整数，是整数，则命题为则命题为“自然数都是整数自然数都是整数”，这是真命题。，这是真命题。例题例题例题例题4.74.74.74.7(2)(2)x x y(F(x)F(y)G(x,y)H(f(x,y),g(x,y)y(F(x)F(y)G(x,y)H(f(x,y),g(x,y)含有两个含有两个2 2元函数变项，两个元函数变项，两个1 1元谓词变项，两个元谓词变项，两个2 2元谓词变元谓词变项。项。指定个体域为全总个体域，指定个体域为全总个体域，F(x)F(x)为为x x是实数，是实数，G(x,y)G(x,y)为为xyxy，H(x,y)H(x,y)为为xy

47、xy，f(x,y)=xf(x,y)=x2 2+y+y2 2，g(x,y)=2xyg(x,y)=2xy，则表达的命题为则表达的命题为“对于任意的对于任意的x x，y y，若若x x与与y y都是实数，且都是实数，且xyxy，则则x x2 2+y+y2 22xy”2xy”，这是真命题。这是真命题。如果如果H(x,y)H(x,y)改为改为xyxy，则所得命题为假命题。则所得命题为假命题。解释解释定义定义4.7设一阶语言设一阶语言L L 的个体常项集的个体常项集ai|i 1,函数符号集函数符号集fi|i 1,谓词符号集谓词符号集Fi|i 1,L L的的解释解释I由下面由下面4部分组部分组成成:(1)非

48、空个体域非空个体域DI(2)对每一个个体常项对每一个个体常项ai,DI,称作称作ai在在I中的解释中的解释(3)对每一个函数符号对每一个函数符号fi,设其为设其为m元的元的,是是DI上的上的m元元函函数数,称作称作fi在在I中的解释中的解释(4)对每一个谓词符号对每一个谓词符号Fi,设其为设其为n元的元的,是一个是一个n元谓元谓词词,称作称作Fi在在I中的解释中的解释q 为第为第i个个n元谓词，如元谓词，如i=2，n=3时，时，表示第表示第2个个3元谓元谓词，它可能以词，它可能以 (x,y,z)的形式出现在解释中，公式的形式出现在解释中，公式A若出现若出现F2(x,y,z)就解释成就解释成 (

49、x,y,z)。q 为第为第i个个n元函数。例如，元函数。例如，i=1，n=2时，时，表示第一个二表示第一个二元函数，它出现在解释中，可能是元函数，它出现在解释中，可能是 (x,y)=x2+y2，(x,y)=2xy等，一旦公式中出现等，一旦公式中出现f1(x,y)就解释成就解释成 (x,y)，出现出现g1(x,y)就解释成就解释成 (x,y)=2xy。对解释对解释I I的几点说明的几点说明q被解释的公式不一定全部包含解释中的四部分。被解释的公式不一定全部包含解释中的四部分。q在解释的公式在解释的公式A A中的个体变项均取值于中的个体变项均取值于D DI I。q若若A A中含有个体常项中含有个体常

50、项，就解释成就解释成 。q在解释的定义中引进了几个元语言符号，如在解释的定义中引进了几个元语言符号，如例例4.84.8 给定解释给定解释I I如下如下:(a)a)个体域个体域D=N(ND=N(N为自然数集合，即为自然数集合，即 N=0,1,2,)N=0,1,2,)(b)=0(c)(x,y)=x+y,(x,y)=xy。(d)(x,y)为为x=y。在在I下，下列哪些公式为真下，下列哪些公式为真?哪些为假哪些为假?哪些的真值还不能确定哪些的真值还不能确定?例题例题例题例题4.84.8例题例题4.84.8(1)F(f(x,y),g(x,y)(2)F(f(x,a),y)F(g(x,y),z)(3)F(g