（本科）第4章 谓词逻辑ppt课件.ppt

《（本科）第4章 谓词逻辑ppt课件.ppt》由会员分享，可在线阅读，更多相关《（本科）第4章 谓词逻辑ppt课件.ppt（121页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、课程主讲人：（本科）第（本科）第4 4章章 谓词逻辑谓词逻辑pptppt课件课件电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程 双语示范课程双语示范课程离离 散散 数数 学学20222022年年5 5月月1616日星期一日星期一电子科技大学离散数学课程组电子科技大学离散数学课程组电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-32022-5-162022-5-16例如例如( (著名的苏格拉底三段论著名的苏格拉底三段论) ) （1 1）所有的人都是要死的；）所有的人都是要死的； （2 2）苏格拉底是人

2、。）苏格拉底是人。 （3 3）苏格拉底是要死的。）苏格拉底是要死的。 显然有：显然有：P,QP,QR R提出问题提出问题应该有应该有 PQPQR=T定理定理3.6.0 3.6.0 设设G,HG,H是公式，是公式， G G当且仅当当且仅当GG为永真公式。为永真公式。 P PQ QR R但是但是P=1P=1，Q=1Q=1，R=0R=0时，时，PQPQR=0 命题逻辑能够解决的问题是有命题逻辑能够解决的问题是有局限性局限性的。只的。只 能进行能进行命题间关系命题间关系的推理，无法解决与的推理，无法解决与命题的命题的结构和成分结构和成分有关的推理问题。有关的推理问题。电子科技大学离散数学课程组电子科技

3、大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-42022-5-162022-5-16第四章第四章 谓词逻辑谓词逻辑谓词逻辑中的基本概念谓词逻辑中的基本概念1谓词的翻译原理谓词的翻译原理2谓词的合式公式谓词的合式公式3谓词的标准型谓词的标准型-范式范式4谓词逻辑的推理谓词逻辑的推理理理论论5电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-52022-5-162022-5-164.1 4.1 本章学习要求本章学习要求 重点掌握重点掌握了解了解11 1 谓词逻辑符号化谓词逻辑符号化及真值及真值2 2

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

5、个陈述句由个陈述句由主语和谓语主语和谓语两部分组成。两部分组成。 例如，例如，“计算机计算机是现代科学技术必不可少的工具是现代科学技术必不可少的工具” 例如例如 “陈华陈华是电子科技大学的学生是电子科技大学的学生”； “张强张强是电子科技大学的学生是电子科技大学的学生”。 若：是电子科技大学的学生若：是电子科技大学的学生-P(-P(陈华陈华) ) -P(-P(张强张强) ) x若若( (x x) )：x x是电子科技大学的学生是电子科技大学的学生谓词谓词个体词个体词命题函数命题函数电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-

6、72022-5-162022-5-16个体词与谓词个体词与谓词定义定义 在原子命题中，可以独立存在的客体（句在原子命题中，可以独立存在的客体（句子中的主语、宾语等），称为子中的主语、宾语等），称为个体词个体词(Individual)(Individual)。而用以刻划客体的性质或客体之间的关系即是而用以刻划客体的性质或客体之间的关系即是谓词谓词(Predicate)(Predicate)。单纯的谓词或单纯的个体词都无法构成一个完整的单纯的谓词或单纯的个体词都无法构成一个完整的逻辑含义，只有将它们结合起来时才能构成一个独逻辑含义，只有将它们结合起来时才能构成一个独立的逻辑断言。立的逻辑断言。 例

7、例1 1 成都、北京、赵明、成都、北京、赵明、2006080620060806班、计算机科学班、计算机科学等等仅仅是简单的个体常量；等等仅仅是简单的个体常量；“是中国的首都是中国的首都”、“是计算机的基础课程是计算机的基础课程”等仅仅是简单的谓词，它等仅仅是简单的谓词，它们都不能构成完整的句子。们都不能构成完整的句子。电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-82022-5-162022-5-16个体词的分类个体词的分类 表示表示具体的或特定具体的或特定的个体词称为的个体词称为个体常量个体常量(Individual Con

8、stant)(Individual Constant)，一般个体词常量用，一般个体词常量用带或不带下标的小写英文字母带或不带下标的小写英文字母a, b, ca, b, c，a a1 1, , b b1 1, c, c1 1, ,等表示；等表示； 表示表示抽象的或泛指抽象的或泛指的个体词称为的个体词称为个体变量个体变量(Individual Variable)(Individual Variable)，一般用带或不带下，一般用带或不带下标的小写英文字母标的小写英文字母x, y, z, x, y, z, , x, x1 1, y, y1 1, , z z1 1, , 等表示。等表示。电子科技大学离

9、散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-92022-5-162022-5-16例子例子例例2 2 考察下列句子：考察下列句子： （1 1）北京北京是中国的首都是中国的首都； （2 2）离散数学离散数学是计算机的基础课程是计算机的基础课程； （3 3）刘翔刘翔是一个跨栏世界冠军是一个跨栏世界冠军； （4 4）中国人中国人是很聪明的是很聪明的。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-102022-5-162022-5-16个体域个体域定义定义 个体词的取值范围个体

10、词的取值范围称为称为个体域个体域( (或或论域论域) ) (Individual Field)(Individual Field)，常用，常用D D表示；表示；1.1. 宇宙间的所有个体域聚集宇宙间的所有个体域聚集在一起所构成的个体在一起所构成的个体域称为域称为全总个体域全总个体域(Universal Individual (Universal Individual Field)Field)。电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-112022-5-162022-5-16n n元谓词元谓词定义定义 设设D D为为非空的非

11、空的个体域，定义在个体域，定义在D Dn n( (表示表示n n个个个个体都在个体域体都在个体域D D上取值上取值) )上取值于上取值于0,10,1上的上的n n元函数，元函数，称为称为n n元命题函数元命题函数或或n n元谓词元谓词(Propositional (Propositional 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) )

12、的的值域值域为为0, 10, 1。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-122022-5-162022-5-16例例设有如下命题，并用设有如下命题，并用n n元谓词进行表示。元谓词进行表示。 P P：王童王童是一个三好学生是一个三好学生； Q Q：李新华李新华是是李兰李兰的父亲的父亲； R R：张强张强与与谢莉谢莉是好朋友是好朋友； S S：武汉武汉位于位于北京北京和和广州广州之间之间。 S(x)S(x)：x x是一个三好学生是一个三好学生 a a：王童：王童 命题命题P P可表示为：可表示为：S(a)S(a) F(

13、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：张强：张强 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)电子科技大学离散数学课程组电子科技大学离散数学课程组国

14、家级精品课程国家级精品课程 双语示范课程双语示范课程120-132022-5-162022-5-16结论结论 谓词中谓词中个体词的顺序是十分重要个体词的顺序是十分重要的，不能随意的，不能随意变更。如命题变更。如命题F(b, c)F(b, c)为为“真真”，但命题，但命题F(c, b)F(c, b)为为“假假”； 一元谓词一元谓词用以描述用以描述某一个个体的某种特性某一个个体的某种特性，而，而n n元谓词元谓词则用以描述则用以描述n n个个体之间的关系个个体之间的关系。 0 0元谓词元谓词( (不含个体词的不含个体词的) )实际上就是一般的命题；实际上就是一般的命题；电子科技大学离散数学课程组电

15、子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-142022-5-162022-5-16结论（续）结论（续） 具体命题的谓词表示形式具体命题的谓词表示形式和和n n元命题函数元命题函数(n(n元谓元谓词词) )是不同的，前者是有真值的，而后者不是命是不同的，前者是有真值的，而后者不是命题，它的真值是不确定的。如上例中题，它的真值是不确定的。如上例中S(a)S(a)是有是有真值的，但真值的，但S(x)S(x)却没有真值；却没有真值； 一个一个n n元谓词不是一个命题元谓词不是一个命题，但，但将将n n元谓词中的元谓词中的个体变元都用个体域中具体的个体取代个体

16、变元都用个体域中具体的个体取代后，就后，就成为一个命题成为一个命题。而且，个体变元在不同的个体。而且，个体变元在不同的个体域中取不同的值对是否成为命题及命题的真值域中取不同的值对是否成为命题及命题的真值有很大的影响。有很大的影响。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-152022-5-162022-5-164.2.2 4.2.2 量词量词例例 符号化下述命题：符号化下述命题： （1 1）所有的所有的老虎都要吃人；老虎都要吃人； S(x)S(x)：x x登上过月球登上过月球 则有：则有：有一些有一些x x，S(x) x

17、S(x) x 人人 P(x)P(x)：x x会吃人会吃人 则有：则有：所有的所有的x x，P(x) xP(x) x 老虎老虎 （2 2）有一些有一些人登上过月球；人登上过月球；量词量词量词量词全称量词全称量词存在量词存在量词 ( (x x) ) ( (x x ) )作用变量作用变量变量的辖域变量的辖域电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-162022-5-162022-5-16不便之处不便之处 从从书写上书写上十分不便，总要特别注明个体域；十分不便，总要特别注明个体域； 在同一个比较复杂的句子中，对于不同命题函数在同一

18、个比较复杂的句子中，对于不同命题函数中的个体可能属于不同的个体域，此时中的个体可能属于不同的个体域，此时无法清晰无法清晰表达；表达； 如例如例 (1)(1)和和(4)(4)的合取的合取 ( ( x)P(x)(x)P(x)( x)R(x)x)R(x)x x 人人 x x 老虎老虎 电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-172022-5-162022-5-16不便之处不便之处( (续续) ) 若个体域的注明不清楚，将造成若个体域的注明不清楚，将造成无法确定其真无法确定其真值值。 例如例如 对于语句对于语句“( ( x)(x

19、+6 = 5)x)(x+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)为为“假假”。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-182

20、022-5-162022-5-16不便之处的根源不便之处的根源对了，都是因为需要特别标注每个对了，都是因为需要特别标注每个谓词的个体域所致！谓词的个体域所致！全总个体域全总个体域电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-192022-5-162022-5-16特性谓词特性谓词U(x)U(x)：x x是老虎是老虎x x老虎老虎R(x)R(x)：x x是人是人x x人人 P(x)P(x)：x x会吃人会吃人, , U(x)U(x)：x x是老虎是老虎, ,则有：则有： ( ( x)x)P(x), P(x), U(x)U(x)

21、P(x)P(x)：x x会吃人会吃人, ,则有则有 ( ( x)x)P(x),P(x),x x 老虎老虎 S(x)S(x)：x x登上过月球登上过月球, , 则则有 ： 有 一 些有 ： 有 一 些 x x ， S ( x ) S ( x ) x x 人人 S(x)S(x)：x x登上过月球登上过月球, , R(x)R(x)：x x是人是人, , 则有：有一则有：有一( ( x)x)S(x), S(x), R(x)R(x)新的问题出现了，新的问题出现了，U(x)U(x)如何与如何与( ( x)P(x)x)P(x)结合才符合逻辑呢？结合才符合逻辑呢？电子科技大学离散数学课程组电子科技大学离散数学

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

23、在量词( ( x)x)，刻划其对应个体域的，刻划其对应个体域的特性谓词作为特性谓词作为合取式之合取项合取式之合取项加入。加入。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-212022-5-162022-5-16例例符号化下述命题：符号化下述命题： （1 1）所有的所有的老虎都要吃人；老虎都要吃人；解：设解：设S(x)S(x)：x x登上过月球，登上过月球，R(x)R(x)：x x是人是人, , 则有：则有：( ( x)x)S(x)S(x)R(x)R(x) 解：设解：设P(x)P(x)：x x会吃人，会吃人，U(x)U(x)

24、：x x是老虎是老虎, ,则有：则有：( ( x)(x)(U(x)U(x)P(x)P(x) （2 2）有一些有一些人登上过月球；人登上过月球；电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-222022-5-162022-5-16（2 2）每一个每一个大学生都会说英语；大学生都会说英语；（3 3）所有的所有的人都长着黑头发；人都长着黑头发；（5 5）有一些有一些自然数是素数。自然数是素数。 例例4.2.2(4.2.2(续续) )( ( x)Q(x) x)Q(x) x x 大学生大学生 ( ( x)R(x) x)R(x) x x

25、人人 ( ( x)T(x) x)T(x) x x 自然数自然数 。电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-232022-5-162022-5-16例例用谓词逻辑符号化下述语句：用谓词逻辑符号化下述语句：(1) (1) 天下天下乌鸦乌鸦一般一般黑；黑；(2) (2) 没没有人有人登上过木星；登上过木星；(3) (3) 在美国留学的学生在美国留学的学生未必未必都都是亚洲人；是亚洲人；(4) (4) 每个每个实数都实数都存在存在比它大的另外的实数；比它大的另外的实数；(5) (5) 尽管尽管有人有人很聪明，很聪明，但未必但未必

26、一切一切人都聪明；人都聪明；(6) (6) 对于对于任意任意给定的给定的 00，必必存在存在着着 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)正确的推导如下

27、：正确的推导如下：（1）( x)( y)G(x,y)P（2）( y)G(z,y)US,(1)错错要求：要求：使用使用US规则规则来来消去消去量词时，若选用量词时，若选用变元变元y取代取代x，则要求，则要求在在原公式中原公式中x x不能出现不能出现在量词在量词( ( y)y)或或( ( y)y)的辖域之内的辖域之内。电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-882022-5-162022-5-16推理规则的正确使用（推理规则的正确使用（2 2）推导推导2： （1）( x)( y)G(x, y) P （2）( y)G(z, y

28、) US,(1) （3）G(z, c) ES,(2) 正确的推导如下：正确的推导如下：（1）( x)( y)G(x,y)P（2）( y)G(z,y)US,(1)（3）G(z,f(z)ES,(2)( ( x)G(x) x)G(x) G(c) G(c)错错要求：要求：使用使用ESES规则规则来来消去消去量词时，量词时， 若还若还有其它有其它自由变自由变元元时，则必须用关于自由时，则必须用关于自由变元的变元的函数符号函数符号来取代常量符号来取代常量符号. .电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-892022-5-162022

29、-5-16推理规则的正确使用（推理规则的正确使用（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)的辖域之内的辖域之内。电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程1

30、20-902022-5-162022-5-16推理规则的正确使用（推理规则的正确使用（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不能出现不能出现在量词在量词( x)或或( x)的辖域之内的辖域之内且且原公式中原公式中中中无自由变量无自由变量x x。电子科技大学离散数学课程组电子科技大学离散数学课程组国

31、家级精品课程国家级精品课程 双语示范课程双语示范课程120-912022-5-162022-5-16判断判断（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(x, y) x)G(x, y) EG,(4)EG,(4)电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程

32、双语示范课程120-922022-5-162022-5-164.5.2 4.5.2 谓词演算的综合推理方法谓词演算的综合推理方法 推导过程中可以引用命题演算中的推导过程中可以引用命题演算中的规则规则P P 和规和规则则T T 。 如果如果结论结论是以蕴涵形式是以蕴涵形式( (或或析取形式析取形式) )给出，我给出，我们还可以们还可以使用规则使用规则CPCP。 若需若需消去量词消去量词，可以，可以引用规则引用规则USUS和规则和规则ESES。 当所要求的结论可能被当所要求的结论可能被定量定量时，此时可时，此时可引用规引用规则则UGUG和规则和规则EGEG将其量词加入将其量词加入。电子科技大学离散

33、数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-932022-5-162022-5-16谓词演算的综合推理方法（续谓词演算的综合推理方法（续1 1） 证明时可采用如证明时可采用如命题演算命题演算中的中的直接证明方法和直接证明方法和间接证明方法间接证明方法。 在推导过程中，在推导过程中，对消去量词的公式或公式中不对消去量词的公式或公式中不含量词的子公式含量词的子公式，完全可以，完全可以引用命题演算中的引用命题演算中的基本等价公式和基本蕴涵公式基本等价公式和基本蕴涵公式。 在推导过程中，对在推导过程中，对含有量词的公式含有量词的公式可以可以引用谓引

34、用谓词中的基本等价公式和基本蕴涵公式词中的基本等价公式和基本蕴涵公式。电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-942022-5-162022-5-16例例4.5.1解：设解：设H(x)H(x)：x x是人；是人；M(x)M(x)：x x是要死的；是要死的； s s：苏格拉底。：苏格拉底。则符号化为：则符号化为： ( ( x)(H(x)x)(H(x)M(x)M(x)，H(s) H(s) M(s) M(s)证明证明苏格拉底三段论苏格拉底三段论：“所有的人都是要死的；苏所有的人都是要死的；苏格拉底是人。所以苏格拉底是要死的。格

35、拉底是人。所以苏格拉底是要死的。”证明：证明：(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)错了！错了！电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-952022-5-162022-5-16例例4.5.2 4.5.2 证明：证明： ( ( x)(P(x)x)(P(x)Q(x)Q(x), ,( ( x)x)P(x)P(x

36、)( ( 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) Q(c)T,(2),(4),IT,(2),(4),I (6) (6) ( ( x)x)Q(x)Q(x) EG,(5) EG,(5)电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程1

37、20-962022-5-162022-5-16例（例（) )推导可修改为推导可修改为：(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)(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)电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-

38、972022-5-162022-5-16例例( () )请看推导请看推导：(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)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)正确！正确！电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-

39、982022-5-162022-5-16例例4.5.3 4.5.3 证明证明：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(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 证明：证明：( (

40、x)x)(P(x)(P(x)Q(x)Q(x)( ( x)x)P(x)P(x)( x)x)Q(x)Q(x)电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-992022-5-162022-5-16例例4.5.3(4.5.3(续续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)

41、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) 请看上述推论的逆推导请看上述推论的逆推导：电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-1002022-5-162022-5-16例例4.5.3(4.5.3(续续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)

42、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) 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) 电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-1012022-5-162022-5-16例例4.5.4 4.5.4

43、 证明证明( (采用反证法，采用反证法，CPCP规则的方法由学生完成规则的方法由学生完成) )：1 1) ) ( ( ( x)P(x)x)P(x)( x)x)Q(x)Q(x)P(P(附加附加) )2 2) ) ( ( 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

44、)Q(x) Q(x) ( ( x)P(x)x)P(x)( x)x)Q(x)Q(x)电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-1022022-5-162022-5-16例例4.5.4 4.5.4 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

45、(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,10),12)12)电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-1032022-5-162022-5-164.5.3 4.5.3 谓词逻辑推理的难点谓词逻辑推理的难点 在推导过程中，如在推导过程中，如既要使用规则既要使用规则USUS又要使用规则又要使用规则ESES消去公式中的量词，而且选用的个体是同一个消去公式中的量词，

46、而且选用的个体是同一个符号，则必须符号，则必须先先使用规则先先使用规则ESES，再使用规则，再使用规则USUS。然后再使用命题演算中的推理规则，最后使用规然后再使用命题演算中的推理规则，最后使用规则则UGUG或规则或规则EGEG引入量词，得到所要的结论。引入量词，得到所要的结论。 如一个变量是用如一个变量是用规则规则ESES消去量词消去量词，对该变量在添，对该变量在添加量词时，则加量词时，则只能使用规则只能使用规则EGEG，而不能使用规则，而不能使用规则UGUG；如使用；如使用规则规则USUS消去量词消去量词，对该变量在添加量，对该变量在添加量词时，则词时，则可使用规则可使用规则EGEG和规则

47、和规则UGUG。电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-1042022-5-162022-5-16谓词逻辑推理的难点（续）谓词逻辑推理的难点（续） 如有如有两个含有存在量词的公式两个含有存在量词的公式，当用，当用规则规则ESES消去消去量词量词时，时，不能选用同样的一个常量符号不能选用同样的一个常量符号来取代两来取代两个公式中的变元，而应用不同的常量符号来取代个公式中的变元，而应用不同的常量符号来取代它们。它们。 在用在用规则规则USUS和和规则规则ESES消去量词消去量词、用、用规则规则UGUG和和规则规则EGEG添加

48、量词添加量词时，此量词必须位于时，此量词必须位于整个公式的最前整个公式的最前端，并且它的辖域为其后的整个公式端，并且它的辖域为其后的整个公式。电子科技大学离散数学课程组电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-1052022-5-162022-5-16谓词逻辑推理的难点（续）谓词逻辑推理的难点（续） 在在添加量词添加量词( ( x)x)、( ( x)x)时，所选用的时，所选用的x x不能在不能在公式公式G(y)G(y)或或G(c)G(c)中中自由出现自由出现且且G(y)G(y)或或G(c)G(c)对对x x是是自由自由的。的。 在使用在使用规则规则

49、EGEG引入存在量词引入存在量词( ( x)x)时，时，此此x x不得不得仅为仅为G(c)G(c)或或G(y)G(y)中的函数变元中的函数变元。在使用。在使用规则规则UGUG引入全称量词引入全称量词( ( x)x)时，时，此此x x不得为不得为G(y)G(y)中的函中的函数变元数变元( (因该函数变元不得作为自由变元因该函数变元不得作为自由变元) )。 在使用在使用规则规则UGUG引入全称量词引入全称量词( ( x)x)时，时，G(y)G(y)中不中不得出现在使用得出现在使用规则规则USUS引入引入y y之后由之后由规则规则ESES引入的引入的常量或函数。常量或函数。电子科技大学离散数学课程组

50、电子科技大学离散数学课程组国家级精品课程国家级精品课程 双语示范课程双语示范课程120-1062022-5-162022-5-164.5.4 4.5.4 谓词逻辑推理的应用谓词逻辑推理的应用例例 每个喜欢步行的人都不喜欢坐汽车；每个人或每个喜欢步行的人都不喜欢坐汽车；每个人或者喜欢坐汽车或者喜欢骑自行车；有的人不喜欢骑者喜欢坐汽车或者喜欢骑自行车；有的人不喜欢骑自行车。因而有的人不喜欢步行。自行车。因而有的人不喜欢步行。 设：设：H(x)：x是人；是人；P(x)：x喜欢坐汽车；喜欢坐汽车；Q(x)：x喜欢骑自行车；喜欢骑自行车；R(x)：x喜欢步行喜欢步行。则上述语句可符号化为：则上述语句可符