离散数学离散第4章谓词逻辑8080

1、离离 散散 数数 学学蔡瑞初蔡瑞初20222022年年5 5月月6 6日星期五日星期五2022-5-62022-5-6第第4 4章章 谓词逻辑谓词逻辑 例如例如( (著名的苏格拉底三段论著名的苏格拉底三段论) ) （1 1）所有的人都是要死的；）所有的人都是要死的； （2 2）苏格拉底是人。）苏格拉底是人。 （3 3）苏格拉底是要死的。）苏格拉底是要死的。 命题逻辑能够解决的问题是命题逻辑能够解决的问题是有有局限性局限性的。只能进行的。只能进行命题间关系命题间关系的的推理，无法解决与推理，无法解决与命题的结构和成分命题的结构和成分有关的推理问题。有关的推理问题。2022-5-62022-5-6

2、苏格拉底三段论苏格拉底三段论 P P：所有的人都是要死的；：所有的人都是要死的； Q Q：苏格拉底是人。：苏格拉底是人。 R R：所以，苏格拉底是要死的。：所以，苏格拉底是要死的。 可见，可见，P P，Q Q，R R为不同的命题，无法体现三者相为不同的命题，无法体现三者相互之间的联系。互之间的联系。问题在于这类推理中，各命题之间的逻辑关系不是问题在于这类推理中，各命题之间的逻辑关系不是体现在原子命题之间，而是体现在体现在原子命题之间，而是体现在构成原子命题的构成原子命题的内部成分之间内部成分之间。对此，命题逻辑将无能为力。对此，命题逻辑将无能为力。2022-5-62022-5-6本章内容本章内

3、容 谓词逻辑中的基本概念谓词逻辑中的基本概念1谓词的翻译原理谓词的翻译原理2谓词的合式公式谓词的合式公式3谓词的标准型谓词的标准型-范式范式42022-5-62022-5-64.1 4.1 本章学习要求本章学习要求 重点掌握重点掌握了解了解11 1 谓词逻辑符谓词逻辑符号化及真值号化及真值2 2 谓词公式的谓词公式的有效性和基本有效性和基本等价公式等价公式3前束范式与前束范式与SKOLEMSKOLEM范式范式 21 1 谓词公式的谓词公式的解释和真值解释和真值2 2 自由变元和自由变元和约束变元约束变元一般掌握一般掌握2022-5-62022-5-64.2 4.2 谓词逻辑中的基本概念与表示谓

4、词逻辑中的基本概念与表示 命题是具有真假意义的陈述句，从语法上分析，一命题是具有真假意义的陈述句，从语法上分析，一个陈述句由个陈述句由主语和谓语主语和谓语两部分组成。两部分组成。 例如，例如，“计算机计算机是现代科学技术必不可少的工具是现代科学技术必不可少的工具” 例如例如 “陈华陈华是电子科技大学的学生是电子科技大学的学生”； “张强张强是电子科技大学的学生是电子科技大学的学生”。 若：是电子科技大学的学生若：是电子科技大学的学生-P(-P(陈华陈华) )-P(-P(张强张强) ) 2022-5-62022-5-6谓词谓词更一般地，更一般地， P(x) P(x)：x x是电子科技大学的学生。

5、是电子科技大学的学生。x x：个体词：个体词P P：谓词：谓词P(x):P(x):命题函数命题函数P(x)P(x)2022-5-62022-5-6个体词与谓词个体词与谓词定义定义4.2.14.2.1 在原子命题中，可以独立存在的客体在原子命题中，可以独立存在的客体（句子中的主语、宾语等），称为（句子中的主语、宾语等），称为个体词个体词(Individual)(Individual)。而用以刻划客体的性质或客体之间。而用以刻划客体的性质或客体之间的关系即是的关系即是谓词谓词(Predicate)(Predicate)。单纯的谓词或单纯的个体词都无法构成一个完整的单纯的谓词或单纯的个体词都无法构成

6、一个完整的逻辑含义，只有将它们结合起来时才能构成一个独逻辑含义，只有将它们结合起来时才能构成一个独立的逻辑断言。立的逻辑断言。 例例1 1 成都、北京、赵明、成都、北京、赵明、2006080620060806班、计算机科学班、计算机科学等等仅仅是简单的个体常量；等等仅仅是简单的个体常量；“是中国的首都是中国的首都”、“是计算机的基础课程是计算机的基础课程”等仅仅是简单的谓词，它等仅仅是简单的谓词，它们都不能构成完整的句子。们都不能构成完整的句子。2022-5-62022-5-6个体词的分类个体词的分类（1 1）表示）表示具体的或特定具体的或特定的个体词称为的个体词称为个体常量个体常量(Indi

7、vidual Constant)(Individual Constant)，一般个体词常量用带或，一般个体词常量用带或不带下标的小写英文字母不带下标的小写英文字母a, b, ca, b, c，a a1 1, b, b1 1, , c c1 1, ,等表示；等表示；（2 2）表示）表示抽象的或泛指抽象的或泛指的个体词称为的个体词称为个体变量个体变量(Individual Variable)(Individual Variable)，一般用带或不带下标的，一般用带或不带下标的小写英文字母小写英文字母x, y, z, x, y, z, , x, x1 1, y, y1 1, z, z1 1, , 等

8、表示。等表示。2022-5-62022-5-6例子例子例例2 2 考察下列句子：考察下列句子： （1 1）北京北京是中国的首都是中国的首都； （2 2）离散数学离散数学是计算机的基础课程是计算机的基础课程； （3 3）刘翔刘翔是一个跨栏世界冠军是一个跨栏世界冠军； （4 4）中国人中国人是很聪明的是很聪明的。 2022-5-62022-5-6个体域个体域定义定义4.2.24.2.2 （1 1）个体词的取值范围个体词的取值范围称为称为个体域个体域( (或或论论域域)(Individual Field)(Individual Field)，常用，常用D D表示；表示；（2 2）而）而宇宙间的所有个

9、体域聚集宇宙间的所有个体域聚集在一起所构成的在一起所构成的个体域称为个体域称为全总个体域全总个体域(Universal Individual (Universal Individual Field)Field)。2022-5-62022-5-6n n元谓词元谓词定义定义4.2.34.2.3 设设D D为为非空的非空的个体域，定义在个体域，定义在D Dn n( (表示表示n n个个体都在个体域个个体都在个体域D D上取值上取值) )上取值于上取值于0,10,1上的上的n n元元函数，称为函数，称为n n元命题函数元命题函数或或n n元谓词元谓词(Propositional (Propositio

10、nal Function)Function)，记为，记为P(xP(x1 1, x, x2 2, , , x, xn n) )。此时，个体。此时，个体变量变量x x1 1, x, x2 2, , , x, xn n的的定义域定义域都为都为D D，P(xP(x1 1, x, x2 2, , , , x xn n) )的的值域值域为为0, 10, 1。 2022-5-62022-5-6例例4.2.14.2.1设有如下命题，并用设有如下命题，并用n n元谓词进行表示。元谓词进行表示。 P P：王童王童是一个三好学生是一个三好学生； Q Q：李新华李新华是是李兰李兰的父亲的父亲； R R：张强张强与与谢

11、莉谢莉是好朋友是好朋友； S S：武汉武汉位于位于北京北京和和广州广州之间之间。 2022-5-62022-5-6例例4.2.14.2.1（续）（续）解解 定义命题函数：定义命题函数： S(x) S(x)： x x是一个三好学生；是一个三好学生； F(x, y) F(x, y)： x x是是y y的父亲；的父亲； T(x, y) T(x, y)： x x与与y y是好朋友；是好朋友； B(x,y,z) B(x,y,z)：x x位于位于y y和和z z之间；之间；用符号表示个体词：用符号表示个体词：a a：王童；：王童；b b：李新华；：李新华；c c：李兰；：李兰；d d：张强；：张强；e e

12、：谢莉；：谢莉；f f：武汉；：武汉；g g：北京；：北京；h h：广州。：广州。则命题可表示为：则命题可表示为： P P：S(a)S(a)；Q Q：F(b, c)F(b, c)； R R：T(d, e)T(d, e)；S S：B(f, g, h)B(f, g, h)。 2022-5-62022-5-6结论结论 （1 1）谓词中）谓词中个体词的顺序是十分重要个体词的顺序是十分重要的，不能随意的，不能随意变更。如命题变更。如命题F(b, c)F(b, c)为为“真真”，但命题，但命题F(c, b)F(c, b)为为“假假”；（2 2）一元谓词一元谓词用以描述用以描述某一个个体的某种特性某一个个体

13、的某种特性，而，而n n元谓词元谓词则用以描述则用以描述n n个个体之间的关系个个体之间的关系。（3 3）0 0元谓词元谓词( (不含个体词的不含个体词的) )实际上就是一般的命实际上就是一般的命题；题；2022-5-62022-5-6结论（续）结论（续）（4 4）具体命题的谓词表示形式具体命题的谓词表示形式和和n n元命题函数元命题函数(n(n元元谓词谓词) )是不同的，前者是有真值的，而后者不是命是不同的，前者是有真值的，而后者不是命题，它的真值是不确定的。如上例中题，它的真值是不确定的。如上例中S(a)S(a)是有真值是有真值的，但的，但S(x)S(x)却没有真值；却没有真值；（5 5）

14、一个一个n n元谓词不是一个命题元谓词不是一个命题，但，但将将n n元谓词中元谓词中的个体变元都用个体域中具体的个体取代的个体变元都用个体域中具体的个体取代后，就后，就成成为一个命题为一个命题。而且，个体变元在不同的个体域中取。而且，个体变元在不同的个体域中取不同的值对是否成为命题及命题的真值有很大的影不同的值对是否成为命题及命题的真值有很大的影响。响。 2022-5-62022-5-64.2.2 4.2.2 量词量词例例4.2.24.2.2 符号化下述命题：符号化下述命题： （1 1）所有的所有的老虎都要吃人；老虎都要吃人； （2 2）每一个每一个大学生都会说英语；大学生都会说英语； （3

15、3）所有的所有的人都长着黑头发；人都长着黑头发； （4 4）有一些有一些人登上过月球；人登上过月球； （5 5）有一些有一些自然数是素数。自然数是素数。 2022-5-62022-5-6例例4.2.2(4.2.2(续续) )解解 设立如下谓词：设立如下谓词： 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 x，P(x) xP(x) x 老虎；老虎； （2 2）每一个每一个x

16、x，Q(x) xQ(x) x 大学生大学生 ； （3 3）所有的所有的x x，R(x) xR(x) x 人人 ； （4 4）有一些有一些x x，S(x) xS(x) x 人人 ； （5 5）有一些有一些x x，T(x) xT(x) x 自然数自然数 。 2022-5-62022-5-6量词含义量词含义)( x)( x有些有些x x；至少有一个至少有一个x x；某一些某一些x x；存在存在x x；等等；等等。所有的所有的x x；任意的任意的x x；一切的一切的x x；每一个每一个x x；等等。；等等。2022-5-62022-5-6全称量词与存在量词全称量词与存在量词定义定义4.2.44.2.4

17、 称称( ( x)x)为为全称量词全称量词（Universal Universal QuantifierQuantifier），），( ( x)x)为为存在量词存在量词（Existential Existential QuantifierQuantifier），其中的），其中的x x称为称为作用变量作用变量（Function Function VariableVariable）。一般将其量词加在其谓词之前，记为）。一般将其量词加在其谓词之前，记为( ( x)F(x)x)F(x)，( ( x)F(x)x)F(x)。此时，。此时，F(x)F(x)称为全称量词称为全称量词和存在量词的和存在量词的辖域

18、辖域(Scope)(Scope)。2022-5-62022-5-6例例4.2.2(4.2.2(续续) )（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 自然数自然数 。2022-5-62022-5-6不便之处不便之处（1 1）从从书写上书写上十分不便，总要特别注明个体域；十分不便，总要特别注明个体域；（2 2）在同一个比较复杂的句子

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

20、对于语句“( ( 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)为为“假假

21、”。 2022-5-62022-5-6不便之处的根源不便之处的根源对了，都是因为需要特别标注每个对了，都是因为需要特别标注每个谓词的个体域所致！谓词的个体域所致！全总个体域全总个体域2022-5-62022-5-6特性谓词特性谓词新的问题出现了，新的问题出现了，U(x)U(x)如何与如何与( ( x)P(x)x)P(x)结合才符合逻辑呢？结合才符合逻辑呢？U(x)U(x)：x x是老虎是老虎x x老虎老虎2022-5-62022-5-6谓词逻辑符号化的两条规则谓词逻辑符号化的两条规则 统一个体域为统一个体域为全总个体域全总个体域，而对每一个句子，而对每一个句子中个体变量的变化范围用一元中个体变

22、量的变化范围用一元特性谓词特性谓词刻划之。这刻划之。这种特性谓词在加入到命题函数中时必定遵循如下原种特性谓词在加入到命题函数中时必定遵循如下原则：则：（1 1）对于）对于全称量词全称量词( ( x)x)，刻划其对应个体域的，刻划其对应个体域的特性谓词作为特性谓词作为蕴涵式之前件蕴涵式之前件加入。加入。（2 2）对于）对于存在量词存在量词( ( x)x)，刻划其对应个体域的，刻划其对应个体域的特性谓词作为特性谓词作为合取式之合取项合取式之合取项加入。加入。 2022-5-62022-5-6特性谓词的例子特性谓词的例子想想，为什么要这样规定特性谓词加入的想想，为什么要这样规定特性谓词加入的原则呢？

23、若不遵循会出现什么样的问题？原则呢？若不遵循会出现什么样的问题？例如，符号化例如，符号化“所有的所有的老虎都要吃人老虎都要吃人”这个命题这个命题 若若P(x)P(x)：x x会吃人会吃人 U(x)U(x)：x x是老虎是老虎 则符号化的正确形式应该是则符号化的正确形式应该是( ( x)(U(x)P(x)x)(U(x)P(x) 它的含义是：它的含义是：“对于任意的对于任意的x,x,如果如果x x是老虎，则是老虎，则x x会会吃人吃人”，符合原命题的逻辑含义。，符合原命题的逻辑含义。 若符号化为若符号化为 ( ( x)(U(x)x)(U(x)P(x)P(x) 它的含义是：它的含义是：“对于任意的对

24、于任意的x,xx,x是老虎，并且是老虎，并且x x会吃人会吃人”，与原命题与原命题“所有的老虎都要吃人所有的老虎都要吃人”的的逻辑含义不符。逻辑含义不符。2022-5-62022-5-6例例4.2.34.2.3用谓词逻辑符号化下述语句用谓词逻辑符号化下述语句（1 1）天下天下乌鸦乌鸦一般一般黑黑设设 F(x)F(x)：x x是乌鸦；是乌鸦；G(x, y)G(x, y)：x x与与y y一般黑，则一般黑，则： ( ( x)(x)( y)(F(x)F(y)G(x, y) y)(F(x)F(y)G(x, y) 或者或者( ( x)(x)( y)(F(x)F(y)y)(F(x)F(y)G(x, y)G

25、(x, y)；（2 2）没）没有人有人登上过木星登上过木星设设H(x)H(x)：x x是人；是人；M(x)M(x)：x x登上过木星，则：登上过木星，则： ( ( x)(H(x)M(y) x)(H(x)M(y) 或者或者 ( ( x)(H(x)x)(H(x)M(y)M(y)；2022-5-62022-5-6例例4.2.3(4.2.3(续续) )（3 3）在美国留学的学生在美国留学的学生未必未必都都是亚洲人是亚洲人设设A(x)A(x)：x x是亚洲人；是亚洲人； H(x) H(x)：x x是在美国留学的学生，则：是在美国留学的学生，则： ( ( x)(H(x)A(x) x)(H(x)A(x) 或

26、者或者 ( ( x)(H(x)x)(H(x)A(x)A(x)；（4 4）每个每个实数都实数都存在存在比它大的另外的实数比它大的另外的实数设设R(x)R(x)：x x是实数；是实数；L(x, y)L(x, y)：x x小于小于y y，则：，则： ( ( x)(R(x)(x)(R(x)( y)(R(y)L(x, y)y)(R(y)L(x, y)；2022-5-62022-5-6例例4.2.3(4.2.3(续续) )（5 5）尽管尽管有人有人很聪明，很聪明，但未必但未必一切一切人都聪明人都聪明设设M(x)M(x)：x x是人；是人；C(x)C(x)：x x很聪明，则：很聪明，则： ( ( x)(M(

27、x)C(x) x)(M(x)C(x) ( ( x)(M(x)C(x)x)(M(x)C(x)；（6 6）对于对于任意任意给定的给定的 00，必必存在存在着着 00，使得对，使得对任意任意的的x x，只要只要|x-a|x-a| ，就就有有|f(x)-f(a)|f(x)-f(a)|0)(0)()()( 0)(0)( x) x) (|x-a| (|x-a| )(|f(x)-f(a)|)(|f(x)-f(a)| )。2022-5-62022-5-64.2.3 4.2.3 谓词的语言翻译谓词的语言翻译001100)(,)(,)()(xGDxxGDxxGx001100)(,)(,)()(xGDxxGDxxG

28、x特殊的，当个体域特殊的，当个体域D Dxx0 0, x, x1 1, , 是是可数集合可数集合时，时，上述上述( ( x)G(x)x)G(x)、( ( x)G(x)x)G(x)的真值可表示为：的真值可表示为： ( ( x)G(x)=G(xx)G(x)=G(x0 0)G(x)G(x1 1).). ( ( x)G(x)=G(xx)G(x)=G(x0 0)G(x)G(x1 1).).2022-5-62022-5-6个体域可数或有限个体域可数或有限更特别的，当个体域更特别的，当个体域D Dxx0 0, x, x1 1, , x xn n 是是有限集有限集合合时，上述时，上述( ( x)G(x)x)G

29、(x)、( ( x)G(x)x)G(x)的真值可以用与的真值可以用与之等价的命题公式来进行表示。之等价的命题公式来进行表示。 ( ( x)G(x)=G(xx)G(x)=G(x0 0)G(x)G(x1 1).G(x).G(xn n) ) ( ( x)G(x)=G(xx)G(x)=G(x0 0)G(x)G(x1 1).G(x).G(xn n) )2022-5-62022-5-6例例4.2.54.2.5设设P(x)P(x)：x x是素数；是素数；I(x)I(x)：x x是整数；是整数；Q(x, y)Q(x, y)：x+y=0 x+y=0。用语。用语句描述下述句子，并判断其真假值。句描述下述句子，并判

30、断其真假值。 （1 1）( ( x)(I(x)P(x)x)(I(x)P(x)； 可描述为：可描述为：“对任意的整数对任意的整数x x，x x一定是素数一定是素数”，真值为，真值为“假假”； （2 2）( ( x) (I(x)P(x)x) (I(x)P(x)； 可描述为：可描述为：“存在一些整数存在一些整数x x，x x是素数是素数”，真值为，真值为“真真”； （3 3）( ( x) (x) ( y)(I(x)I(y)Q(x, y)y)(I(x)I(y)Q(x, y)； 可描述为：可描述为：“对任意的整数对任意的整数x x，y y，都有，都有x+y=0 x+y=0”，真值为，真值为“假假”；20

31、22-5-62022-5-6例例4.2.5 4.2.5 （4 4）( ( x)(I(x)(x)(I(x)( y)(I(y)Q(x, y)y)(I(y)Q(x, y)； 可描述为：可描述为：“对任意的整数对任意的整数x x，都存在着整数，都存在着整数y y，使得，使得x+y=0 x+y=0”，真值为，真值为“真真”； （5 5）( ( x)(x)( y)(I(x)(I(y)Q(x, y)y)(I(x)(I(y)Q(x, y)。 可描述为：可描述为：“存在着整数存在着整数x x，使得对任意的整数，使得对任意的整数y y，都有，都有x+y=0 x+y=0”，真值为，真值为“假假”。 2022-5-6

32、2022-5-64.2.4 4.2.4 谓词翻译难点谓词翻译难点 1 1、一元谓词一元谓词用以描述用以描述某一个个体的某种特性某一个个体的某种特性，而，而n n元谓词元谓词则用以描述则用以描述n n个个体之间的关系个个体之间的关系；2 2、如有多个量词，则读的顺序按、如有多个量词，则读的顺序按从左到右从左到右的顺序；的顺序；另外，量词对变元的约束，往往与量词的次序有关，另外，量词对变元的约束，往往与量词的次序有关，不同的不同的量词次序量词次序，可以产生不同的真值，此时对多，可以产生不同的真值，此时对多个量词同时出现时，不能随意颠倒它们的顺序，颠个量词同时出现时，不能随意颠倒它们的顺序，颠倒后会

33、改变原有的含义。倒后会改变原有的含义。2022-5-62022-5-6谓词翻译难点（续）谓词翻译难点（续）3 3、根据命题的实际意义，选用全称量词或存在量、根据命题的实际意义，选用全称量词或存在量词。词。全称量词加入全称量词加入时，其刻划个体域的特性谓词将时，其刻划个体域的特性谓词将以以蕴涵的前件蕴涵的前件加入，加入，存在量词加入存在量词加入时，其刻划个体时，其刻划个体域的特性谓词将以域的特性谓词将以合取项合取项加入；加入；4 4、有些命题在进行符号化时，由于语言叙述不同，、有些命题在进行符号化时，由于语言叙述不同，可能翻译不同，但它们表示的意思是相同的，即可能翻译不同，但它们表示的意思是相同

34、的，即句句子符号化形式可不止一种子符号化形式可不止一种。2022-5-62022-5-64.2.5 4.2.5 谓词翻译的应用谓词翻译的应用例例4.2.44.2.4 将下列命题符号化将下列命题符号化（1 1）兔子比乌龟跑得快；）兔子比乌龟跑得快；（2 2）有的兔子比所有乌龟跑得快；）有的兔子比所有乌龟跑得快；（3 3）并不是所有的兔子都比乌龟跑得快；）并不是所有的兔子都比乌龟跑得快；（4 4）不存在跑得同样快的两只兔子。）不存在跑得同样快的两只兔子。 谓词设定：谓词设定： P(x) P(x)：x x是兔子；是兔子；Q(x)Q(x)：x x是乌龟；是乌龟； R(x, y) R(x, y)：x x

35、比比y y跑得快；跑得快； T(x, y) T(x, y)：x x与与y y跑得同样快。跑得同样快。 2022-5-62022-5-6例例4.2.4 4.2.4 解解 （1 1） ( ( x) (x) ( y)(P(x)Q(y)R(x, y)y)(P(x)Q(y)R(x, y) ； （2 2）( ( x)(P(x)(x)(P(x)( y)(Q(y)R(x, y)y)(Q(y)R(x, y) ； （3 3） ( ( x) (x) ( y)(P(x)Q(y)R(x, y)y)(P(x)Q(y)R(x, y) 或者或者( ( x)(x)( y)(P(x)Q(y)y)(P(x)Q(y)R(x, y)R

36、(x, y)； （4 4）( ( x)(x)( y)(P(x)P(y)T(x, y)y)(P(x)P(y)T(x, y) 或者或者( ( x)(x)( y)(P(x)P(y) y)(P(x)P(y) T(x, y)T(x, y)。 2022-5-62022-5-64.3 4.3 谓词合式公式与解释谓词合式公式与解释 谓词公式涉及如下四种符号：谓词公式涉及如下四种符号：（1 1）常量符号常量符号：用带或不带下标的：用带或不带下标的小写英文字母小写英文字母a, a, b, c, b, c, , a, a1 1, b, b1 1, c, c1 1, , 来表示。当个体域名称集来表示。当个体域名称集合

37、合D D给出时，它可以是给出时，它可以是D D中的某个元素中的某个元素；（2 2）变量符号变量符号：用带或不带下标的：用带或不带下标的小写英文字母小写英文字母x, x, y, z, ., xy, z, ., x1 1, y, y1 1, z, z1 1,.,.来表示。当个体域名称来表示。当个体域名称集合集合D D给出时，它可以是给出时，它可以是D D中的任意元素中的任意元素；2022-5-62022-5-6符号定义符号定义（3 3）函数符号函数符号：用带或不带下标的：用带或不带下标的小写英文字母小写英文字母f, f, g, h, ., fg, h, ., f1 1, g, g1 1, h, h

38、1 1, ., .来表示。当个体域名称来表示。当个体域名称集合集合D D给出时，给出时，n n元函数符号元函数符号f(xf(x1 1, x, x2 2, , , x, xn n) )可以可以是是D Dn nDD的任意一个函数；的任意一个函数；（4 4）谓词符号谓词符号：用带或不带下标的：用带或不带下标的大写英文字母大写英文字母P, P, Q, R,., PQ, R,., P1 1, Q, Q1 1, R, R1 1.来表示。当个体域名称集来表示。当个体域名称集合合D D给出时，给出时，n n元谓词符号元谓词符号P(xP(x1 1, x, x2 2, , , x, xn n) )可以是可以是D

39、Dn n00，11的任意一个谓词。的任意一个谓词。 2022-5-62022-5-6为何需要函数符号？为何需要函数符号？例如例如 符号化符号化“周红的父亲是教授周红的父亲是教授”： 设设f(x)f(x)：x x的父亲；的父亲；P(x)P(x)：x x是教授；是教授；c c：周：周红红此时此时P(f(c)P(f(c)表示表示“周红的父亲是教授周红的父亲是教授”这一命题。这一命题。 函数的使用给谓词逻辑中的个体词表示函数的使用给谓词逻辑中的个体词表示带来了很大的方便带来了很大的方便2022-5-62022-5-6项项定义定义4.3.14.3.1 谓词逻辑中的谓词逻辑中的项项（TermTerm），被

40、递归地定），被递归地定义为：义为：（1 1）任意的常量符号任意的常量符号或或任意的变量符号任意的变量符号是项；是项；（2 2）若）若f(xf(x1 1,x,x2 2, ,x,xn n) )是是n n 元函数符号元函数符号，t t1 1,t,t2 2, ,t,tn n 是项，则是项，则f(tf(t1 1, t, t2 2, , , t, tn n) )是项；是项；（3 3）仅由）仅由有限次使用有限次使用(1)(1)，(2)(2)产生的符号串才是项。产生的符号串才是项。 2022-5-62022-5-6原子公式原子公式定义定义4.3.24.3.2 若若P(xP(x1 1, x, x2 2, , ,

41、 x, xn n) )是是n n 元谓词元谓词，t t1 1，t t2 2，t tn n是项，则称是项，则称P(tP(t1 1, t, t2 2, , , t, tn n) )为为原子谓原子谓词公式词公式(Atomic Propositional Formulae)(Atomic Propositional Formulae)，简称，简称原子公式原子公式(Atomic Formulae)(Atomic Formulae)。 2022-5-62022-5-6定义定义4.3.34.3.3满足下列条件的表达式，称为满足下列条件的表达式，称为合式公式合式公式(Well-Formed Formulae/

42、Wff)，简称，简称公式公式(Formulae)。（1 1）原子公式原子公式是合式公式；是合式公式；（2 2）若）若G G，H H是合式公式，则是合式公式，则( (G)G)、( (H)H)、 (GH)(GH)，(GH)(GH)、(GH)(GH)、(G(GH)H)也是合式公式；也是合式公式；（3 3）若）若G G是合式公式，是合式公式，x x是个体变量，则是个体变量，则 ( ( x)x)G G、( ( x)Gx)G 也是合式公式；也是合式公式；（4 4）仅仅由）仅仅由(1)-(3)(1)-(3)产生的表达式才是合式公式。产生的表达式才是合式公式。 2022-5-62022-5-6例子例子 ( (

43、 x)(x)( y)(P(x, y)(Q(x,y)R(x,a,f(z)y)(P(x, y)(Q(x,y)R(x,a,f(z)是公式是公式 构造过程：构造过程：f(z)f(z)是项是项, R(x,a,f(z), R(x,a,f(z)是公式是公式, , (Q(x,y)R(x,a,f(z) (Q(x,y)R(x,a,f(z)是公式是公式, , (P(x, y)(Q(x,y)R(x,a,f(z)(P(x, y)(Q(x,y)R(x,a,f(z)是公式，是公式， ( ( y)(P(x, y)(Q(x,y)R(x,a,f(z)y)(P(x, y)(Q(x,y)R(x,a,f(z) ( ( x)(x)( y

44、)(P(x, y)(Q(x,y)R(x,a,f(z)y)(P(x, y)(Q(x,y)R(x,a,f(z)， 而而 ( ( x)(P(x)R(x)x)(P(x)R(x)，( ( y)(y)( x)(P(x, y)x)(P(x, y)。 等则不是公式等则不是公式。 2022-5-62022-5-64.3.2 4.3.2 自由变元和约束变元自由变元和约束变元定义定义4.3.44.3.4 给定一个合适公式给定一个合适公式G G，若变元，若变元x x出现在出现在使用变元的量词的辖域之内，则称变元使用变元的量词的辖域之内，则称变元x x的出现为的出现为约约束出现束出现( (Bound Occurrenc

45、eBound Occurrence) )，此时的变元，此时的变元x x称为称为约约束变元束变元( (Bound VariableBound Variable) )。若。若x x的出现不是约束出的出现不是约束出现，则称它为现，则称它为自由出现自由出现( (Free OccurrenceFree Occurrence) )，此时，此时的变元的变元x x 称为称为自由变元自由变元( (Free VariableFree Variable) )。 量词辖域的确定方法：量词辖域的确定方法： （1 1）若量词后）若量词后有括号有括号，则，则括号内的子公式括号内的子公式就是就是该量词的辖域；该量词的辖域；

46、（2 2）若量词后）若量词后无括号无括号，则，则与量词邻接的子公式与量词邻接的子公式为该量词的辖域。为该量词的辖域。 2022-5-62022-5-6例例4.3.14.3.1确定以下公式各量词的辖域以及各个体变量为自由变确定以下公式各量词的辖域以及各个体变量为自由变元还是约束变元。元还是约束变元。 （1 1）( ( x)(P(x)(x)(P(x)( y)R(x, y)y)R(x, y) P(x)P(x)中的中的x x，R(x,y)R(x,y)的的x x，y y都为约束变元。都为约束变元。 （2 2）( ( x)P(x)Q(x, y)x)P(x)Q(x, y)； P(x) P(x)中的中的x x

47、为约束变元，为约束变元，Q(x,y)Q(x,y)中的中的x x，y y是自由变是自由变元。元。2022-5-62022-5-6例例4.3.1 4.3.1 解解 （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)； 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为自由变元。为自由变元。 （4 4）( ( x)(P(x)R(x)(x)(P(x)R(x)( y)Q(x,y

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

49、时为了使其式子给研究更方便，而不致引起混淆，同时为了使其式子给大家以一目了然的结果，对于表示不同意思的个体变大家以一目了然的结果，对于表示不同意思的个体变元，我们总是以元，我们总是以不同的变量符号不同的变量符号来表示之。来表示之。 2022-5-62022-5-6两个规则两个规则规则规则1(1(约束变元的改名规则约束变元的改名规则) )：（1 1）将量词中出现的变元以及该量词辖域中此将量词中出现的变元以及该量词辖域中此 变量之所有约束出现都用新的个体变元替换变量之所有约束出现都用新的个体变元替换；（2 2）新的变元一定要有别于改名辖域中的所有新的变元一定要有别于改名辖域中的所有其它变量其它变量

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

51、变元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) 错2022-5-62022-5-6改名规则和代入规则的关系改名规则和代入规则的关系改名规则和代入规则之间的改名规则和代入规则之间的共同点共同点都是都是不能改变原有不能改变原有的约束关系的约束关系，而，而不同点不同点是：是：（1 1）施行的对象不同施行的对象不同：改名规则是对：改名规则是对约束变元约束变元施行，施行，代入规则是对代入规则是对自由变元自由变元施行；施行；（2 2）施行的范围不同施行的范围不同：改名规则可以只对公式中的：改名

52、规则可以只对公式中的一个量词及其辖域内施行，即只一个量词及其辖域内施行，即只对公式的一个子公式对公式的一个子公式施行施行；而代入规则必须对整个公式同一个自由变元的；而代入规则必须对整个公式同一个自由变元的所有自由出现同时施行，即必须所有自由出现同时施行，即必须对整个公式施行对整个公式施行；2022-5-62022-5-6改名规则和代入规则的关系（续）改名规则和代入规则的关系（续）（3 3）施行后的结果不同施行后的结果不同：改名后，公式含义不变，：改名后，公式含义不变，因为因为约束变元只改名为另一个个体变元约束变元只改名为另一个个体变元，约束关系，约束关系不改变，约束变元不能改名为个体常量；代入

53、后，不改变，约束变元不能改名为个体常量；代入后，不仅可用另一个个体变元进行代入，并且也可用不仅可用另一个个体变元进行代入，并且也可用个个体常量体常量去代入，从而使公式由具有普遍意义变为仅去代入，从而使公式由具有普遍意义变为仅对该个体常量有意义，即公式的含义改变了。对该个体常量有意义，即公式的含义改变了。 2022-5-62022-5-6闭式的定义闭式的定义定义定义4.3.54.3.5 设设G G是任意一个公式，若是任意一个公式，若G G中无自由出中无自由出现的个体变元，则称现的个体变元，则称G G为封闭的合适公式，简称闭为封闭的合适公式，简称闭式。式。例例 ( ( x)(P(x)(x)(P(x

54、)( y)R(x, y)y)R(x, y) 是一个闭式。是一个闭式。 2022-5-62022-5-64.3.3 4.3.3 谓词合式公式的解释谓词合式公式的解释定义定义4.3.64.3.6 谓词逻辑中公式谓词逻辑中公式G G 的每一个的每一个解释解释I(Expl-I(Expl-anation)anation)由如下四部分组成：由如下四部分组成：（1 1）非空的个体域非空的个体域集合集合D D ；（2 2）G G中的每个中的每个常量符号常量符号，指定，指定D D中的某个特定元素；中的某个特定元素；（3 3）G G中的每个中的每个n n元元函数符号函数符号，指定，指定D Dn n到到D D中的某

55、个特定中的某个特定的函数；的函数；（4 4）G G中的每个中的每个n n 元元谓词符号谓词符号，指定，指定D Dn n到到0,10,1中的某中的某个特定的谓词。个特定的谓词。 2022-5-62022-5-6例例4.3.44.3.4个体域为个体域为D D ，；a a指定为：指定为：；f(f()指定为指定为：,f(,f()指定为：指定为：；P(P()指定为：指定为：1,1,P(P()指定为：指定为：0 0，Q(Q(,),)指定为：指定为：0 0，Q(Q(,),)指定为：指定为：1 1，Q(Q(,),)指定为：指定为：1 1，Q(Q(,),)指定为：指定为：1 1设有公式设有公式( ( x)x)(

56、 (P(f(x)Q(xP(f(x)Q(x，f(a)f(a)。在如下在如下给定的解释下，判断该公式的真值。给定的解释下，判断该公式的真值。2022-5-62022-5-6例例4.3.4 4.3.4 解解 （续）（续）因当因当x x时，有：时，有：f(f()，P(f(x)P(f(x)P(f(P(f()P(P()1,1,f(a)f(a)f(f()，Q(xQ(x，f(a)f(a)Q(Q(，f(f()Q(Q(，)1 1。所以：所以：P(f(P(f()Q(Q(,f(a),f(a)11111 1，即存在即存在x x,使得使得P(f(P(f()Q(Q(，f(a)f(a)1 1，即：即：( ( x)x)( (P

57、(f(x)Q(xP(f(x)Q(x，f(a)f(a)1 1。2022-5-62022-5-64.3.4 4.3.4 谓词合式公式的分类谓词合式公式的分类判断下列公式的真假。判断下列公式的真假。（1 1）P(x, y)Q(x,y)P(x, y)P(x, y)Q(x,y)P(x, y)；（2 2）P(x, y)P(x, y) P(x, y)P(x, y)；（3 3）P(x, y)P(x, y) P(x, y)P(x, y)。 解解 无论在何种结构中，无论对变元作何种赋值，无论在何种结构中，无论对变元作何种赋值，公公式式(1)(1)，(2)(2)均取真值均取真值T T，而公式，而公式(3)(3)均取

58、真值均取真值F F。 从而从而(1)(1)，(2)(2)就是关于一切结构与一切赋值下就是关于一切结构与一切赋值下恒取恒取“T T”值的谓词公式，值的谓词公式，(3)(3)就是关于一切结构与就是关于一切结构与一切赋值下恒取一切赋值下恒取“F F”值的谓词公式。值的谓词公式。 2022-5-62022-5-6谓词合式公式的分类谓词合式公式的分类定义定义4.3.74.3.7 （1 1）公式）公式G G称为称为有效公式有效公式， 如果如果G G在它在它所有的解释所有的解释I I下都取值为下都取值为“真真”。（2 2）公式）公式G G称为称为矛盾公式矛盾公式， 如果如果G G在它在它所有的解释所有的解释

59、I I下都取值为下都取值为“假假”。（3 3）公式）公式G G称为称为可满足公式可满足公式， 如果如果至少有一种解释至少有一种解释I I使得使得G G取值为取值为“真真”。 2022-5-62022-5-6公式之间的关系公式之间的关系从上述定义可知三种特殊公式之间的关系：从上述定义可知三种特殊公式之间的关系： （1 1）有效公式的否定为矛盾公式有效公式的否定为矛盾公式； 矛盾公式的否定为有效公式矛盾公式的否定为有效公式； （2 2）有效公式一定为可满足公式有效公式一定为可满足公式。2022-5-62022-5-6谓词逻辑的判定问题谓词逻辑的判定问题 若说谓词逻辑是若说谓词逻辑是可判定可判定的，

60、就要求给出一个的，就要求给出一个能能行的方法行的方法，使得对，使得对任一公式都能判断是否是有效的任一公式都能判断是否是有效的。所谓所谓能行的方法能行的方法，乃是，乃是一个机械方法一个机械方法，可一步一步，可一步一步做下去，并在做下去，并在有穷步有穷步内实现判断。内实现判断。2022-5-62022-5-6谓词公式的可判定性谓词公式的可判定性（1 1）谓词逻辑是不可判定的谓词逻辑是不可判定的；（2 2）只）只含有一元谓词变项含有一元谓词变项的公式是可判定的；的公式是可判定的；（3 3）如下形式的公式：）如下形式的公式： ( ( x x1 1)()( x x2 2) )( ( x xn n)P(x