第4章谓词逻辑

1、离散数学课程组离散数学课程组国家精品课程，国家双语教学示范课程国家精品课程，国家双语教学示范课程离离 散散 数数 学学电子科技大学电子科技大学计算机科学与工程计算机科学与工程学院学院 离散数学课程组离散数学课程组20222022年年4 4月月3030日星期六日星期六离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-2 22022-4-302022-4-30第第4 4章章 谓词逻辑谓词逻辑 例如例如: :对于含变量的语句，如对于含变量的语句，如 “x x3 3”，“x=y+3x=y+3”和和“x+y=zx+y=z”常见于数学断言和计算

2、机程序，在变量值未知的时常见于数学断言和计算机程序，在变量值未知的时候，这些语句既不成真也不成假。候，这些语句既不成真也不成假。对此，命题逻辑对此，命题逻辑将无能为力。将无能为力。 命题逻辑能够解决的问题是命题逻辑能够解决的问题是有有局限性局限性的。只能进行的。只能进行命题间关系命题间关系的的推理，无法解决与推理，无法解决与命题的结构和成分命题的结构和成分有关的推理问题。有关的推理问题。离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-3 32022-4-302022-4-30第第4 4章章 谓词逻辑谓词逻辑 例如例如，“著名的苏格

3、拉底三段论著名的苏格拉底三段论”所有的人都是要死的；所有的人都是要死的；苏格拉底是人。苏格拉底是人。所以，苏格拉底是要死的。所以，苏格拉底是要死的。设：设：P P：所有的人都是要死的；：所有的人都是要死的；Q Q：苏格拉底是人；：苏格拉底是人；R R：苏格拉底是要死的。：苏格拉底是要死的。则上述句子课表示成：则上述句子课表示成：P,QP,QR R根据逻辑蕴涵关系，命题公式根据逻辑蕴涵关系，命题公式P PQ QR R应为永真式，即在任何应为永真式，即在任何解释下公式取值为真，但此时当解释下公式取值为真，但此时当P P、Q Q取取1 1时，时，R R为为0 0时，时， P PQ QR R为假。为假

4、。离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-4 42022-4-302022-4-30本章内容本章内容 谓词逻辑中的基本概念谓词逻辑中的基本概念1谓词的翻译原理谓词的翻译原理2谓词的合式公式谓词的合式公式3谓词的标准型谓词的标准型-范式范式4谓词逻辑的推理理论谓词逻辑的推理理论5离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-5 52022-4-302022-4-304.1 4.1 本章学习要求本章学习要求 重点掌握重点掌握了解了解11 1 谓词逻辑符号谓词逻辑

5、符号化及真值化及真值2 2 谓词公式的有谓词公式的有效性和基本等价效性和基本等价公式公式3 3谓词逻辑推理谓词逻辑推理3前束范式与前束范式与SKOLEMSKOLEM范式范式 21 1 谓词公式的谓词公式的解释和真值解释和真值2 2 自由变元和自由变元和约束变元约束变元一般掌握一般掌握离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-6 62022-4-302022-4-304.2 4.2 谓词逻辑中的基本概念与表示谓词逻辑中的基本概念与表示 命题是具有真假意义的陈述句，从语法上分析，一命题是具有真假意义的陈述句，从语法上分析，一个陈

6、述句由个陈述句由主语和谓语主语和谓语两部分组成。两部分组成。 例如，例如，“计算机计算机是现代科学技术必不可少的工具是现代科学技术必不可少的工具” 例如例如 “陈华陈华是电子科技大学的学生是电子科技大学的学生”； “张强张强是电子科技大学的学生是电子科技大学的学生”。 若：是电子科技大学的学生若：是电子科技大学的学生-P(-P(陈华陈华) )-P(-P(张强张强) ) 离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-7 72022-4-302022-4-30谓词谓词更一般地，更一般地， P(x) P(x)：x x是电子科技大学的学

7、生。是电子科技大学的学生。x x：个体词：个体词P P：谓词：谓词P(x):P(x):命题函数命题函数P(x)P(x)离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-8 82022-4-302022-4-30个体词与谓词个体词与谓词定义定义4.2.14.2.1 在原子命题中，可以独立存在的客体在原子命题中，可以独立存在的客体（句子中的主语、宾语等），称为（句子中的主语、宾语等），称为个体词个体词(Individual)(Individual)。而用以刻划客体的性质或客体之间。而用以刻划客体的性质或客体之间的关系即是的关系即是谓词谓

8、词(Predicate)(Predicate)。单纯的谓词或单纯的个体词都无法构成一个完整的单纯的谓词或单纯的个体词都无法构成一个完整的逻辑含义，只有将它们结合起来时才能构成一个独逻辑含义，只有将它们结合起来时才能构成一个独立的逻辑断言。立的逻辑断言。 例例1 1 成都、北京、赵明、成都、北京、赵明、2006080620060806班、计算机科学班、计算机科学等等仅仅是简单的个体常量；等等仅仅是简单的个体常量；“是中国的首都是中国的首都”、“是计算机的基础课程是计算机的基础课程”等仅仅是简单的谓词，它等仅仅是简单的谓词，它们都不能构成完整的句子。们都不能构成完整的句子。离散数学课程组离散数学课

9、程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-9 92022-4-302022-4-30个体词的分类个体词的分类1.1. 表示表示具体的或特定具体的或特定的个体词称为的个体词称为个体常量个体常量(Individual Constant)(Individual Constant)，一般个体词常量用，一般个体词常量用带或不带下标的小写英文字母带或不带下标的小写英文字母a, b, ca, b, c，a a1 1, , b b1 1, c, c1 1, ,等表示；等表示；2.2. 表示表示抽象的或泛指抽象的或泛指的个体词称为的个体词称为个体变量个体变量(Ind

10、ividual Variable)(Individual Variable)，一般用带或不带下，一般用带或不带下标的小写英文字母标的小写英文字母x, y, z, x, y, z, , x, x1 1, y, y1 1, , z z1 1, , 等表示。等表示。离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-10102022-4-302022-4-30例子例子例例2 2 考察下列句子：考察下列句子： （1 1）北京北京是中国的首都是中国的首都； （2 2）离散数学离散数学是计算机的基础课程是计算机的基础课程； （3 3）刘翔刘翔是一

11、个跨栏世界冠军是一个跨栏世界冠军； （4 4）中国人中国人是很聪明的是很聪明的。 离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-11112022-4-302022-4-30个体域个体域定义定义4.2.24.2.2 1.1. 个体词的取值范围个体词的取值范围称为称为个体域个体域( (或或论域论域) ) (Individual Field)(Individual Field)，常用，常用D D表示；表示；2.2. 宇宙间的所有个体域聚集宇宙间的所有个体域聚集在一起所构成的个体在一起所构成的个体域称为域称为全总个体域全总个体域(Uni

12、versal Individual (Universal Individual Field)Field)。离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-12122022-4-302022-4-30n 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 (P

13、ropositional 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。 离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-13132022-4-302022-4-30例例4.2.14.2.1设有如下命题，并用设有如下命题，并用n n元谓词进行

14、表示。元谓词进行表示。 P P：王童王童是一个三好学生是一个三好学生； Q Q：李新华李新华是是李兰李兰的父亲的父亲； R R：张强张强与与谢莉谢莉是好朋友是好朋友； S S：武汉武汉位于位于北京北京和和广州广州之间之间。 S(x)S(x)：x x是一个三好学生是一个三好学生 a a：王童：王童 命题命题P P可表示为：可表示为：S(a)S(a) F(x, y) F(x, y)：x x是是y y的父亲的父亲 b b：李新华：李新华 c c：李兰：李兰 命题命题Q Q可表示为：可表示为：F(b, c)F(b, c) T(x, y) T(x, y)：x x与与y y是好朋友是好朋友 d d：张强：

15、张强 e e：谢莉：谢莉 命题命题R R可表示为：可表示为：T(d, e)T(d, e) B(x,y,z) B(x,y,z)：x x位于位于y y和和z z之间之间 f f：武汉：武汉 g g：北京：北京 h h：广州：广州 命题命题S S可表示为：可表示为：B(f, g, h)B(f, g, h)离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-14142022-4-302022-4-30结论结论 1.1. 谓词中谓词中个体词的顺序是十分重要个体词的顺序是十分重要的，不能随意的，不能随意变更。如命题变更。如命题F(b, c)F(b

16、, c)为为“真真”，但命题，但命题F(c, b)F(c, b)为为“假假”；2.2. 一元谓词一元谓词用以描述用以描述某一个个体的某种特性某一个个体的某种特性，而，而n n元谓词元谓词则用以描述则用以描述n n个个体之间的关系个个体之间的关系。3.3. 0 0元谓词元谓词( (不含个体词的不含个体词的) )实际上就是一般的命题；实际上就是一般的命题；离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-15152022-4-302022-4-30结论（续）结论（续）4.4. 具体命题的谓词表示形式具体命题的谓词表示形式和和n n元命题

17、函数元命题函数(n(n元谓元谓词词) )是不同的，前者是有真值的，而后者不是命是不同的，前者是有真值的，而后者不是命题，它的真值是不确定的。如上例中题，它的真值是不确定的。如上例中S(a)S(a)是有是有真值的，但真值的，但S(x)S(x)却没有真值；却没有真值；5.5. 一个一个n n元谓词不是一个命题元谓词不是一个命题，但，但将将n n元谓词中的元谓词中的个体变元都用个体域中具体的个体取代个体变元都用个体域中具体的个体取代后，就后，就成为一个命题成为一个命题。而且，个体变元在不同的个体。而且，个体变元在不同的个体域中取不同的值对是否成为命题及命题的真值域中取不同的值对是否成为命题及命题的真

18、值有很大的影响。有很大的影响。 离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-16162022-4-302022-4-304.2.2 4.2.2 量词量词例例4.2.24.2.2 符号化下述命题：符号化下述命题： （1 1）所有的所有的老虎都要吃人；老虎都要吃人； （2 2）每一个每一个大学生都会说英语；大学生都会说英语； （3 3）所有的所有的人都长着黑头发；人都长着黑头发； （4 4）有一些有一些人登上过月球；人登上过月球； （5 5）有一些有一些自然数是素数。自然数是素数。 T(x) T(x)：x x是素数是素数 则有：则

19、有：有一些有一些x x，T(x) xT(x) x 自然数自然数 S(x) S(x)：x x登上过月球登上过月球 则有：则有：有一些有一些x x，S(x) xS(x) x 人人 R(x) R(x)：x x长着黑头发长着黑头发 则有：则有：所有的所有的x x，R(x) xR(x) x 人人 Q(x) Q(x)：x x会说英语会说英语 则有：则有：每一个每一个x x，Q(x) Q(x) x x 大学生大学生 P(x) P(x)：x x会吃人会吃人 则有：则有：所有的所有的x x，P(x) xP(x) x 老虎老虎 离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双

20、语教学示范课程84-84-17172022-4-302022-4-30量词含义量词含义 ( ( x x) ) ( ( x x) )有些有些x x；至少有一个至少有一个x x；某一些某一些x x；存在存在x x；等等等等。所有的所有的x x；任意的任意的x x；一切的一切的x x；每一个每一个x x；等等。等等。离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-18182022-4-302022-4-30全称量词与存在量词全称量词与存在量词定义定义4.2.44.2.4 称称( ( x)x)为为全称量词全称量词（Universal Un

21、iversal 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)称为全称量词称为全称量词和存在量词的和存在量词的辖域辖域(Scope)(Scope)。离散数学课程组离散数学课程组国家级

22、精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-19192022-4-302022-4-30（1 1）所有的所有的老虎都要吃人；老虎都要吃人；（2 2）每一个每一个大学生都会说英语；大学生都会说英语；（3 3）所有的所有的人都长着黑头发；人都长着黑头发；（4 4）有一些有一些人登上过月球；人登上过月球；（5 5）有一些有一些自然数是素数。自然数是素数。 例例4.2.2(4.2.2(续续) )( ( x)P(x) x)P(x) x x 老虎老虎 ( ( x)Q(x) x)Q(x) x x 大学生大学生 ( ( x)R(x) x)R(x) x x 人人 ( ( x)S

23、(x) x)S(x) x x 人人 ( ( x)T(x) x)T(x) x x 自然数自然数 。离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-20202022-4-302022-4-30不便之处不便之处1.1. 从从书写上书写上十分不便，总要特别注明个体域；十分不便，总要特别注明个体域；2.2. 在同一个比较复杂的句子中，对于不同命题函数在同一个比较复杂的句子中，对于不同命题函数中的个体可能属于不同的个体域，此时中的个体可能属于不同的个体域，此时无法清晰无法清晰表达；表达； 如例如例 (1)(1)和和(4)(4)的合取的合取 (

24、 ( x)P(x)(x)P(x)( x)R(x)x)R(x)x x 人人 x x 老虎老虎 离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-21212022-4-302022-4-30不便之处不便之处( (续续) )3.3. 若个体域的注明不清楚，将造成若个体域的注明不清楚，将造成无法确定其真无法确定其真值值。即。即对于同一个对于同一个n n元谓词，不同的个体域有可元谓词，不同的个体域有可能带来不同的真值能带来不同的真值。 例如例如 对于语句对于语句“( ( x)(x+6 = 5)x)(x+6 = 5)”可表示可表示为：为：“有一

25、些有一些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)为为“假假”。 离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家

26、双语教学示范课程84-84-22222022-4-302022-4-30不便之处的根源不便之处的根源对了，都是因为需要特别标注每个对了，都是因为需要特别标注每个谓词的个体域所致！谓词的个体域所致！全总个体域全总个体域离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-23232022-4-302022-4-30特性谓词特性谓词新的问题出现了，新的问题出现了，U(x)U(x)如何与如何与( ( x)P(x)x)P(x)结合才符合逻辑呢？结合才符合逻辑呢？U(x)U(x)：x x是老虎是老虎x x老虎老虎离散数学课程组离散数学课程组国家级

27、精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-24242022-4-302022-4-30谓词逻辑符号化的两条规则谓词逻辑符号化的两条规则 统一个体域为统一个体域为全总个体域全总个体域，而对每一个句子，而对每一个句子中个体变量的变化范围用一元中个体变量的变化范围用一元特性谓词特性谓词刻划之。这刻划之。这种特性谓词在加入到命题函数中时必定遵循如下原种特性谓词在加入到命题函数中时必定遵循如下原则：则：（1 1）对于）对于全称量词全称量词( ( x)x)，刻划其对应个体域的，刻划其对应个体域的特性谓词作为特性谓词作为蕴涵式之前件蕴涵式之前件加入。加入。（2 2）对于）

28、对于存在量词存在量词( ( x)x)，刻划其对应个体域的，刻划其对应个体域的特性谓词作为特性谓词作为合取式之合取项合取式之合取项加入。加入。 离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-25252022-4-302022-4-30特性谓词的例子特性谓词的例子想想，为什么要这样规定特性谓词加入的想想，为什么要这样规定特性谓词加入的原则呢？若不遵循会出现什么样的问题？原则呢？若不遵循会出现什么样的问题？例如，符号化例如，符号化“所有的所有的老虎都要吃人老虎都要吃人”这个命题这个命题 若若P(x)P(x)：x x会吃人会吃人 U(x

29、)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) 它的含义是：它的含义是：“对于任意的对于任意的x,xx,x是老虎，并且是老虎，并且x x会吃人会吃人”，与原命题与原命题“所有的老虎都要吃人所有的老虎都要吃人”的的逻辑含义不符。逻辑含义不符。离散数学课程组离散数学课程组国家级精品课

30、程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-26262022-4-302022-4-30例例4.2.34.2.3用谓词逻辑符号化下述语句：用谓词逻辑符号化下述语句：(1) (1) 天下天下乌鸦乌鸦一般一般黑；黑；(2) (2) 没没有人有人登上过木星；登上过木星；(3) (3) 在美国留学的学生在美国留学的学生未必未必都都是亚洲人；是亚洲人；(4) (4) 每个每个实数都实数都存在存在比它大的另外的实数；比它大的另外的实数；(5) (5) 尽管尽管有人有人很聪明，很聪明，但未必但未必一切一切人都聪明；人都聪明；(6) (6) 对于对于任意任意给定的给定的 00，必必

31、存在存在着着 00，使得对，使得对任意任意的的x x，只要只要|x-a|x-a| ，就就有有|f(x)-f(a)|f(x)-f(a)|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)|xyx。 推导推导1： （1）( x)( y)G(x, y)P （2）( y)G(y, y) US,(1) 分析分析：推导：推导1是错误的。是错误的。正确的推导如下：正确的推导如下： （1）(

32、x)( y)G(x, y) P （2）( y)G(z, y)US,(1)注意：注意：使用使用US规则规则来来消去消去量词时，若选用量词时，若选用变元变元y取代取代x，则要求，则要求在在原公式中原公式中x x不能出现不能出现在量词在量词( ( y)y)或或( ( y)y)的辖域之内的辖域之内。离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-93932022-4-302022-4-30推理规则的正确使用（推理规则的正确使用（2 2）推导推导2 2： （1 1）( ( x)(x)( y)G(x, y) P y)G(x, y) P （2

33、2）( ( y)G(z, y) US,(1)y)G(z, y) US,(1) （3 3）G(z, c) ES,(2)G(z, c) ES,(2) 分析分析：推导：推导2是错误的。是错误的。正确的推导如下：正确的推导如下： （1）( x) ( y)G(x, y) P （2）( y)G(z, y) US,(1) （3）G(z, f(z) ES,(2) 注意：注意：使用使用ESES规则规则来来消去消去量词时，量词时， 若还若还有其它有其它自由变自由变元元时，时，则必须用关于自由则必须用关于自由变元的变元的函数符号函数符号来取代常量符号来取代常量符号. .离散数学课程组离散数学课程组国家级精品课程，国

34、家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-94942022-4-302022-4-30推理规则的正确使用（推理规则的正确使用（3 3）推导推导3： （1）( y)G(z, y) P （2）( y)( y)G(y, y) UG,(1)分析分析：推导：推导3是错误的。是错误的。正确的推导如下：正确的推导如下： （1）( y)G(z, y) P （2）( z)( y)G(z, y) UG,(1)注意：注意：使用使用UG规则规则来来添加添加量词时，若选量词时，若选用变元用变元x取代取代y，则要求，则要求在在原公式中原公式中y不不能出现在量词能出现在量词( x)或或( x)的辖域

35、之内的辖域之内。离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-95952022-4-302022-4-30推理规则的正确使用（推理规则的正确使用（4 4）推导推导4： （1）G(x, c) P （2）( x)G(x, x) EG,(2)分析分析：推导：推导4是错误的。是错误的。正确的推导如下：正确的推导如下： （1）G(x, c) P （2）( y)G(x, y) EG,(2)注意：注意：使用使用EG规则规则来来添加添加量词时，若选用量词时，若选用变元变元x取代取代c，则要求，则要求在在原公式中原公式中c不能出现不能出现在量词在

36、量词( x)或或( x)的辖域之内的辖域之内且且原公式中原公式中中中无自由变量无自由变量x x。离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-96962022-4-302022-4-30判断判断（1 1）( ( x)(x)( y)G(x, y)y)G(x, y)P P （2 2）( ( y)G(z, y)y)G(z, y)US,(1)US,(1)（3 3）G(z, c)G(z, c)ES,(2)ES,(2)（4 4）( ( x)G(x, c) x)G(x, c) UG,(3)UG,(3)（5 5）( ( y)y) ( ( x)G

37、(x, y) x)G(x, y) EG,(4)EG,(4)离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-97972022-4-302022-4-304.5.2 4.5.2 谓词演算的综合推理方法谓词演算的综合推理方法1.1. 推导过程中可以引用命题演算中的推导过程中可以引用命题演算中的规则规则P P 和规和规则则T T 。2.2. 如果如果结论结论是以蕴涵形式是以蕴涵形式( (或或析取形式析取形式) )给出，我给出，我们还可以们还可以使用规则使用规则CPCP。3.3. 若需若需消去量词消去量词，可以，可以引用规则引用规则USUS

38、和规则和规则ESES。4.4. 当所要求的结论可能被当所要求的结论可能被定量定量时，此时可时，此时可引用规引用规则则UGUG和规则和规则EGEG将其量词加入将其量词加入。离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-98982022-4-302022-4-30谓词演算的综合推理方法（续谓词演算的综合推理方法（续1 1）5.5. 证明时可采用如证明时可采用如命题演算命题演算中的中的直接证明方法和直接证明方法和间接证明方法间接证明方法。6.6. 在推导过程中，在推导过程中，对消去量词的公式或公式中不对消去量词的公式或公式中不含量词的

39、子公式含量词的子公式，完全可以，完全可以引用命题演算中的引用命题演算中的基本等价公式和基本蕴涵公式基本等价公式和基本蕴涵公式。7.7. 在推导过程中，对在推导过程中，对含有量词的公式含有量词的公式可以可以引用谓引用谓词中的基本等价公式和基本蕴涵公式词中的基本等价公式和基本蕴涵公式。离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-99992022-4-302022-4-30例例4.5.2 解：设解：设H(x)H(x)：x x是人；是人；M(x)M(x)：x x是要死的；是要死的； s s：苏格拉底。：苏格拉底。则符号化为：则符号化为

40、： ( ( x)(H(x)x)(H(x)M(x)M(x)，H(s) H(s) M(s) M(s)证明证明苏格拉底三段论苏格拉底三段论：“所有的人都是要死的；苏所有的人都是要死的；苏格拉底是人。所以苏格拉底是要死的。格拉底是人。所以苏格拉底是要死的。”证明：证明： (1) ( x)(H(x)M(x)P (2) H(x)M(x)US,(1) (3) H(s)P (4) M(s)T,(2),(3),I证明：证明：(1)( x)(H(x)M(x)P (2)H(s)M(s)US,(1) (3)H(s)P (4)M(s)T,(2),(3),I(4)错了！错了！离散数学课程组离散数学课程组国家级精品课程，国

41、家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-1001002022-4-302022-4-30例例4.5.3 4.5.3 证明：证明：( ( x)(P(x)x)(P(x)Q(x)Q(x)，( ( x)x)P(x)P(x)( ( x)x)Q(x)Q(x)有下面的推导有下面的推导： (1) (1) ( ( x)(P(x)x)(P(x)Q(x)Q(x) P P (2) P(x) (2) P(x)Q(x)Q(x) US,(1) US,(1) (3) (3) ( ( x)x)P(x)P(x) P P (4) (4) P(c)P(c)ES,(3)ES,(3) (5) Q(c) (5)

42、Q(c)T,(2),(4),IT,(2),(4),I (6) (6) ( ( x)x)Q(x)Q(x) EG,(5) EG,(5)离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-1011012022-4-302022-4-30例例4.5.34.5.3（) )推导可修改为推导可修改为：(1) (1) ( ( x)(P(x)x)(P(x)Q(x)Q(x)P P(2) P(c)(2) P(c)Q(c)Q(c)US,(1)US,(1)(3)(3) ( ( x)x)P(x)P(x)P P(4)(4) P(c)P(c)ES,(3)ES,(3)

43、(5) Q(c)(5) Q(c)T,(2),(4),IT,(2),(4),I(6) (6) ( ( x)x)Q(x)Q(x)EG,(5)EG,(5)离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-1021022022-4-302022-4-30例例4.5.34.5.3( () )请看推导请看推导：(1)(1) ( ( x)x)P(x)P(x)P P(2)(2) P(c)P(c)ES,(1)ES,(1)(3) (3) ( ( x)(P(x)x)(P(x)Q(x)Q(x)P P(4) P(c)(4) P(c)Q(c)Q(c)US,(3

44、)US,(3)(5) Q(c)(5) Q(c)T,(2),(4),IT,(2),(4),I(6) (6) ( ( x)x)Q(x)Q(x)EG,(5)EG,(5)正确！正确！离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-1031032022-4-302022-4-30例例4.5.4 4.5.4 证明证明：1) (1) ( x x) )(P(x)(P(x)Q(x)Q(x)P P 2) P(c) 2) P(c)Q(c)Q(c) ES,1) ES,1) 3) P(c) 3) P(c)T,2),IT,2),I 4) Q(c) 4) Q(

45、c)T,2),IT,2),I 5) 5) ( ( x x) )P(x)P(x)EG,3)EG,3) 6) 6) ( ( x x) )Q(x)Q(x)EG,4)EG,4) 7) 7) ( ( x x) )P(x)P(x)( ( x x) )Q(x)Q(x)T,5),6),I T,5),6),I 证明：证明：( ( x x) )(P(x)(P(x)Q(x)Q(x)( ( x)x)P(x)P(x)( ( x)x)Q(x)Q(x)离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-1041042022-4-302022-4-30例例4.5.4

46、(4.5.4(续续1)1)1) (1) ( x x) )P(x)P(x)( ( x x) )Q(x)Q(x)P P2) 2) ( ( x x) )P(x)P(x)T,1),IT,1),I3) P(c)3) P(c)ES,2)ES,2)4) 4) ( ( x x) )Q(x)Q(x)T,1),IT,1),I5) Q(c)5) Q(c)ES,4)ES,4)6) P(c)6) P(c)Q(c)Q(c)T,3),4),IT,3),4),I7) 7) ( ( x x) )(P(x)(P(x)Q(x)Q(x)EG,6) EG,6) 请看上述推论的逆推导请看上述推论的逆推导：离散数学课程组离散数学课程组国家

47、级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-1051052022-4-302022-4-30例例4.5.4(4.5.4(续续2)2)正确地推导正确地推导：1) (1) ( x x) )P(x)P(x)( ( x x) )Q(x)Q(x)P P2) 2) ( ( x x) )P(x)P(x)T,1),IT,1),I3) P(c)3) P(c)ES,2)ES,2)4) 4) ( ( x x) )Q(x)Q(x)T,1),IT,1),I5) Q(b)5) Q(b)ES,4)ES,4)6) P(c)6) P(c)Q(b)Q(b)T,3),4),IT,3),4),I7

48、) 7) ( ( y y) )(P(c)(P(c)Q(y)Q(y)EG,6)EG,6)8) 8) ( ( x x) )( ( y y) )(P(x)(P(x)Q(y)Q(y)EG,7) EG,7) 离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-1061062022-4-302022-4-30例例4.5.5 4.5.5 证明证明( (采用反证法，采用反证法，CPCP规则的方法由学生完成规则的方法由学生完成) )：1 1) ) ( ( ( x)P(x)x)P(x)( ( x)x)Q(x)Q(x)P(P(附加附加) )2 2) ) (

49、 ( x)P(x)x)P(x) ( ( x)x)Q(x)Q(x)T,1),ET,1),E3) 3) ( ( x)P(x)x)P(x)T,2),IT,2),I4) 4) ( ( x)x)Q(x)Q(x)T,2),IT,2),I5) 5) ( ( x)x) P(x)P(x)T,3),ET,3),E6) 6) P(c)P(c) ES,5) ES,5)证明证明( ( x)(P(x)x)(P(x)Q(xQ(x) ( ( x)P(x)x)P(x)( ( x)x)Q(x)Q(x)离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-107107202

50、2-4-302022-4-30例例4.5.5 4.5.5 7) (7) ( x)x) Q(x)Q(x) T,4),ET,4),E8) 8) Q(c)Q(c) US,7)US,7)9) 9) P(c)P(c) Q(c)Q(c) T,6),8),IT,6),8),I10) 10) (P(c)(P(c)Q(c)Q(c) T,9),ET,9),E11) (11) ( x)(P(x)x)(P(x)Q(x)Q(x) P P12) (P(c)12) (P(c)Q(c)Q(c) US,11)US,11)13) 13) (P(c)(P(c)Q(c)Q(c)(P(c)(P(c)Q(c) Q(c) T,10),T,

51、10),12)12)离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-1081082022-4-302022-4-304.5.3 4.5.3 谓词逻辑推理的难点谓词逻辑推理的难点1.1. 在推导过程中，如在推导过程中，如既要使用规则既要使用规则USUS又要使用规则又要使用规则ESES消去公式中的量词，而且选用的个体是同一个消去公式中的量词，而且选用的个体是同一个符号，则必须符号，则必须先先使用规则先先使用规则ESES，再使用规则，再使用规则USUS。然后再使用命题演算中的推理规则，最后使用规然后再使用命题演算中的推理规则，最后使用规

52、则则UGUG或规则或规则EGEG引入量词，得到所要的结论。引入量词，得到所要的结论。2.2. 如一个变量是用如一个变量是用规则规则ESES消去量词消去量词，对该变量在添，对该变量在添加量词时，则加量词时，则只能使用规则只能使用规则EGEG，而不能使用规则，而不能使用规则UGUG；如使用；如使用规则规则USUS消去量词消去量词，对该变量在添加量，对该变量在添加量词时，则词时，则可使用规则可使用规则EGEG和规则和规则UGUG。离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-1091092022-4-302022-4-30谓词逻辑推理

53、的难点（续）谓词逻辑推理的难点（续）3.3. 如有如有两个含有存在量词的公式两个含有存在量词的公式，当用，当用规则规则ESES消去消去量词量词时，时，不能选用同样的一个常量符号不能选用同样的一个常量符号来取代两来取代两个公式中的变元，而应用不同的常量符号来取代个公式中的变元，而应用不同的常量符号来取代它们。它们。4.4. 在用在用规则规则USUS和和规则规则ESES消去量词消去量词、用、用规则规则UGUG和和规则规则EGEG添加量词添加量词时，此量词必须位于时，此量词必须位于整个公式的最前整个公式的最前端，并且它的辖域为其后的整个公式端，并且它的辖域为其后的整个公式。离散数学课程组离散数学课程

54、组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-1101102022-4-302022-4-30谓词逻辑推理的难点（续）谓词逻辑推理的难点（续）5.5. 在在添加量词添加量词( ( x)x)、( ( x)x)时，所选用的时，所选用的x x不能在不能在公式公式G(y)G(y)或或G(c)G(c)中中自由出现自由出现且且G(y)G(y)或或G(c)G(c)对对x x是是自由自由的。的。6.6. 在使用在使用规则规则EGEG引入存在量词引入存在量词( ( x)x)时，时，此此x x不得不得仅为仅为G(c)G(c)或或G(y)G(y)中的函数变元中的函数变元。在使

55、用。在使用规则规则UGUG引入全称量词引入全称量词( ( x)x)时，时，此此x x不得为不得为G(y)G(y)中的函中的函数变元数变元( (因该函数变元不得作为自由变元因该函数变元不得作为自由变元) )。7.7. 在使用在使用规则规则UGUG引入全称量词引入全称量词( ( x)x)时，时，G(y)G(y)中不中不得出现在使用得出现在使用规则规则USUS引入引入y y之后由之后由规则规则ESES引入的引入的常量或函数。常量或函数。离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-1111112022-4-302022-4-304.5

56、.4 4.5.4 谓词逻辑推理的应用谓词逻辑推理的应用例例4.5.64.5.6 每个喜欢步行的人都不喜欢坐汽车；每每个喜欢步行的人都不喜欢坐汽车；每个人或者喜欢坐汽车或者喜欢骑自行车；有的人不个人或者喜欢坐汽车或者喜欢骑自行车；有的人不喜欢骑自行车。因而有的人不喜欢步行。喜欢骑自行车。因而有的人不喜欢步行。 设：设：H(x)：x是人；是人； P(x)：x喜欢坐汽车；喜欢坐汽车； Q(x)：x喜欢骑自行车；喜欢骑自行车； R(x)：x喜欢步行喜欢步行。则上述语句可符号化为：则上述语句可符号化为： ( x)(H(x)R(x) P(x)， ( x)(H(x)P(x)Q(x)， ( x)(H(x) Q

57、(x) ( x)(H(x) R(x) 离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-1121122022-4-302022-4-30例例4.5.6 4.5.6 证明证明(1)(1) ( ( x)(H(x)x)(H(x) Q(x)Q(x)P P(2)(2) H(c)H(c) Q(c)Q(c)ES,(1)ES,(1)(3)(3) H(c)H(c)T,(2 ),IT,(2 ),I(4)(4) Q(c)Q(c)T,(2 ),IT,(2 ),I(5)(5) ( ( x)( H(x)P(x)Q(x)x)( H(x)P(x)Q(x)P P(6

58、)(6) H(c)P(c)Q(c)H(c)P(c)Q(c)US,(5)US,(5)(7)(7) P(c)Q(c)P(c)Q(c)T,(3),(6),IT,(3),(6),I(8)(8) P(c)P(c)T,(4),(7),IT,(4),(7),I离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-84-1131132022-4-302022-4-30例例4.5.64.5.6（续）续）(9)(9) ( ( x)(H(x)R(x)x)(H(x)R(x) P(x)P(x)P P(10)(10)H(c)R(c)H(c)R(c) P(c)P(c)US

59、,(9)US,(9)(11)(11) (H(c)R(c)(H(c)R(c)T,(8),(10),IT,(8),(10),I(12)(12) H(c)H(c) R(c)R(c)T,(11),ET,(11),E(13)(13) R(c)R(c)T T,(3),(12),I,(3),(12),I(14)(14)H(c)H(c) R(c)R(c)T T,(3),(13),I,(3),(13),I(15)(15)( ( x)(H(x)x)(H(x) R(x)R(x)EGEG,(14) ,(14) 离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程84-8

60、4-1141142022-4-302022-4-30例例4.5.7 4.5.7 ：证明下述论断的正确性：证明下述论断的正确性：所有的哺乳动物都是脊椎动物；并非所有的哺乳动所有的哺乳动物都是脊椎动物；并非所有的哺乳动物都是胎生动物；故有些脊椎动物不是胎生的。物都是胎生动物；故有些脊椎动物不是胎生的。解解：设谓词如下：设谓词如下：P(x)P(x)：x x是哺乳动物；是哺乳动物；Q(x)Q(x)：x x是脊椎动物；是脊椎动物；R(x)R(x)：x x是胎生动物。是胎生动物。则有则有： ( ( x)(P(x)x)(P(x)Q(x)Q(x)， ( ( x)(P(x)x)(P(x)R(x)R(x) ( (