《第二章谓词逻辑PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第二章谓词逻辑PPT讲稿.ppt（37页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章谓词逻辑第二章谓词逻辑第二章谓词逻辑第二章谓词逻辑第1页，共37页，编辑于2022年，星期二命题逻辑的局限命题逻辑的局限 在命题演算中在命题演算中,原子命题是演算的基本单位原子命题是演算的基本单位,不再对原子命不再对原子命题进行分解。故无法研究命题内部的成分题进行分解。故无法研究命题内部的成分,结构及其逻辑特征。结构及其逻辑特征。1、对于某些问题，命题反映不出它们之间的关系。、对于某些问题，命题反映不出它们之间的关系。如：如：P：小王是大学生。：小王是大学生。Q：小李是大学生。：小李是大学生。是是大学生大学生。第2页，共37页，编辑于2022年，星期二命题逻辑的局限命题逻辑的局限2、对于
2、一些简单的推理，不能用命题逻辑的方法实现。、对于一些简单的推理，不能用命题逻辑的方法实现。如：如：P：凡是人都是要死的。：凡是人都是要死的。R：苏格拉底是人。：苏格拉底是人。Q：所以苏格拉底是要死的。：所以苏格拉底是要死的。凭直觉这个论证是正确的凭直觉这个论证是正确的,但无法用命题演算表达出来。但无法用命题演算表达出来。P RQ 不成立不成立，P RQ不是永真式。不是永真式。第3页，共37页，编辑于2022年，星期二2.1 谓词及相关的概念谓词及相关的概念 1、谓词、谓词谓词谓词带有客体变元的断语。（指明个体的性质或个体之间的关带有客体变元的断语。（指明个体的性质或个体之间的关系。）系。）例如
3、：小王是大学生。例如：小王是大学生。“小王小王”就是一个具体的客体；就是一个具体的客体；“是大学生是大学生”就是谓就是谓词。词。符号化为，符号化为，P(x)：x是大学生。是大学生。a：小王：小王 b：小李：小李 则则P(a)：小王是大学生：小王是大学生 P(b)：小李是大学生：小李是大学生 第4页，共37页，编辑于2022年，星期二 一个客体变元的谓词叫一个客体变元的谓词叫一元谓词一元谓词,两个客体变元的谓词两个客体变元的谓词叫叫二元谓词二元谓词,一般地一般地,n个个体变元的谓词叫个个体变元的谓词叫n元谓词元谓词,记为记为P(x1,x2,x n)。例如：例如：P(x，y)：x围绕围绕y转。转。
4、a：地球：地球 b：太阳：太阳 c：月亮：月亮 P(a，b)：地球围绕太阳转。：地球围绕太阳转。P(b，c)：太阳围绕月亮转。太阳围绕月亮转。2.1 谓词及相关的概念谓词及相关的概念 第5页，共37页，编辑于2022年，星期二2、命题函数、命题函数简单命题函数简单命题函数由一个谓词，一些客体变元组成的表达式称为由一个谓词，一些客体变元组成的表达式称为简单命题函数。如：简单命题函数。如：A(x),B(x,y),R(a,b,c)等等复合命题函数复合命题函数由一个或由一个或N个简单命题函数以及逻辑联结词个简单命题函数以及逻辑联结词组合而成的表达式。如组合而成的表达式。如:A(x)B(x)注意：命题函
5、数不是一个命题，只有客体变元取特定名称时，注意：命题函数不是一个命题，只有客体变元取特定名称时，才能成为一个命题。才能成为一个命题。2.1 谓词及相关的概念谓词及相关的概念谓词及相关的概念谓词及相关的概念 第6页，共37页，编辑于2022年，星期二3、论域、论域客体变元的取值范围，记为客体变元的取值范围，记为u。例如：例如：u=人类人类 P(x)：x是大学生。是大学生。全总个体域全总个体域 宇宙间万物的集合。宇宙间万物的集合。(各种个体域的综合各种个体域的综合)4、量词、量词表示数量的词。表示数量的词。全称量词全称量词 x 指对论域中所有元素。读做指对论域中所有元素。读做“对一切对一切x”，“
6、对任一对任一x”或或“对每一对每一x”，这里，这里 是全称量词，是全称量词，x标记标记 所作用的客体变元。所作用的客体变元。xP(x)表示表示“对一切对一切x，P(x)是真。是真。”存在量词存在量词 x 指对论域中某些元素。读做指对论域中某些元素。读做“存在一存在一x”，“对某对某些些x”或或“至少有一至少有一x”。这里这里 是存在量词，是存在量词，x标记标记所作用的客所作用的客体变元。体变元。xP(x)表示表示“存在存在x，P(x)是真。是真。”2.1 2.1 谓词及相关的概念谓词及相关的概念 第7页，共37页，编辑于2022年，星期二例如：例如：u=人类人类 P(x)：x是大学生。是大学生
7、。xP(x)：所有人都是大学生。：所有人都是大学生。xP(x)：有些人是大学生。：有些人是大学生。5、量词命题式、量词命题式(谓词公式谓词公式)由论域、谓词和量词组成的整体。由论域、谓词和量词组成的整体。6、量词和命题的关系、量词和命题的关系设设u=a1,a2,an xP(x)P(a1)P(a2)P(an)xP(x)P(a1)P(a2)P(an)2.1 谓词及相关的概念谓词及相关的概念谓词及相关的概念谓词及相关的概念 第8页，共37页，编辑于2022年，星期二7、多重量词、多重量词 对于多元谓词，需用多个量词对其中不同的变元加对于多元谓词，需用多个量词对其中不同的变元加以约束。以约束。如：如：
8、u=a1,a2,an x yP(x,y)x(yP(x,y)x(P(x,a1)P(x,a2)P(x,an)(P(a1,a1)P(a1,a2)P(a1,an)(P(a2,a1)P(a2,a2)P(a2,an)(P(an,a1)P(an,a2)P(an,an)2.1 谓词及相关的概念谓词及相关的概念 第9页，共37页，编辑于2022年，星期二8、特性谓词、特性谓词 在使用全总个体域的条件下，对每一个客体变元在使用全总个体域的条件下，对每一个客体变元的范围用一个谓词加以限制，这个谓词称为特性谓词。的范围用一个谓词加以限制，这个谓词称为特性谓词。(1)对全称量词对全称量词,特性谓词作为条件之前件。特性谓
9、词作为条件之前件。(2)对存在量词对存在量词,特性谓词作为合取项。特性谓词作为合取项。例如：符号化例如：符号化“每个人都有一些缺点每个人都有一些缺点”。解：设论域为全总个体域。解：设论域为全总个体域。M(x):x是人，是人，G(y):y是缺点，是缺点，F(x,y):x有有y。可符号化为：可符号化为：x y(M(x)(G(y)F(x,y)其中，其中，M(x)、G(y)都是特性谓词。都是特性谓词。2.1 谓词及相关的概念谓词及相关的概念 第10页，共37页，编辑于2022年，星期二【例例1】符号化符号化每个人都是要死的。每个人都是要死的。有的人活有的人活100岁以上。岁以上。(1)设设u=人类人类
10、则则为为 xD(x)，D(x)：x是要死的。是要死的。为为 xH(x)，H(x)：x活活100岁以上。岁以上。(2)设设u为全总个体域，为全总个体域，M(x)：x是人。是人。则则为为 x(M(x)D(x)为为 x(H(x)M(x)2.1 2.1 谓词及相关的概念谓词及相关的概念 第11页，共37页，编辑于2022年，星期二全总个体域全总个体域要死的要死的人人全总个体域全总个体域活一百岁以上活一百岁以上人人2.1 谓词及相关的概念谓词及相关的概念 第12页，共37页，编辑于2022年，星期二【例例2】将下列命题形式化为谓词逻辑中的命题将下列命题形式化为谓词逻辑中的命题(a)没有不犯错误的人。没有
11、不犯错误的人。(b)人总是要犯错误的。人总是要犯错误的。解：设解：设F(x)：x犯错误，犯错误，M(x)：x是人。则上句符号化为：是人。则上句符号化为：(a)(x)(M(x)F(x)(b)x(M(x)F(x)【例例3】尽管有人聪明但未必一切人都聪明。尽管有人聪明但未必一切人都聪明。解：设解：设P(x)：x聪明，聪明，M(x)：x是人。则上句符号化为：是人。则上句符号化为：x(M(x)P(x)(x(M(x)P(x)2.1 谓词及相关的概念谓词及相关的概念谓词及相关的概念谓词及相关的概念 第13页，共37页，编辑于2022年，星期二【例例4】将下列命题形式化为谓词逻辑中的命题：将下列命题形式化为谓
12、词逻辑中的命题：(1)所有的病人都相信医生。所有的病人都相信医生。(2)有的病人相信所有的医生。有的病人相信所有的医生。(3)有的病人相信某些医生。有的病人相信某些医生。(4)所有的病人都相信某些医生。所有的病人都相信某些医生。解解:设设F(x)：x是病人，是病人，G(y)：y是医生，是医生，H(x，y)：x相信相信y。(1)x(F(x)y(G(y)H(x，y)(2)x(F(x)y(G(y)H(x，y)(3)x y(F(x)G(y)H(x，y)(4)x(F(x)y(G(y)H(x，y)2.1 谓词及相关的概念谓词及相关的概念谓词及相关的概念谓词及相关的概念 第14页，共37页，编辑于2022年
13、，星期二【例例5】将将“有的火车比所有的汽车都快有的火车比所有的汽车都快”符号化符号化解：设解：设H(x)：x是火车，是火车，Q(y)：y是汽车。是汽车。F(x,y)：x比比y快。快。则上句符号化为：则上句符号化为：x(H(x)y(Q(y)F(x,y)2.1 谓词及相关的概念谓词及相关的概念谓词及相关的概念谓词及相关的概念 第15页，共37页，编辑于2022年，星期二【例例6】将将“不管黑猫白猫，抓住老鼠就是好猫。不管黑猫白猫，抓住老鼠就是好猫。”符号化符号化令令C(x)：x是猫是猫 B(x)：x是黑的是黑的 W(x)：x是白的是白的 G(x)：x是好的是好的 M(y)：y是老鼠是老鼠 K(x
14、,y)：x抓住抓住y则上句符号化为：则上句符号化为：x y(C(x)(B(x)W(x)M(y)K(x,y)G(x)2.1 谓词及相关的概念谓词及相关的概念 第16页，共37页，编辑于2022年，星期二2.2 2.2 谓词公式中的等价与蕴含谓词公式中的等价与蕴含 1、谓词逻辑中常见的等价与蕴含关系、谓词逻辑中常见的等价与蕴含关系(1)命题逻辑中等价和蕴含的推广命题逻辑中等价和蕴含的推广例如：例如：(x)(P(x)Q(x)(x)(P(x)Q(x)xP(x)x Q(x)(x)P(x)x Q(x)第17页，共37页，编辑于2022年，星期二(2)量词否定的等价关系量词否定的等价关系 (x)P(x)(x
15、)P(x)(x)P(x)(x)P(x)证明证明:设设u=a1,a2,an(x)P(x)(P(a1)P(a2)P(an)P(a1)P(a2)P(an)(x)P(x)2.2 谓词公式中的等价与蕴含谓词公式中的等价与蕴含 第18页，共37页，编辑于2022年，星期二(3)量词辖域的扩张与收缩量词辖域的扩张与收缩 x(A(x)B)x A(x)B x(A(x)B)x A(x)B x(A(x)B)x A(x)B x(A(x)B)x A(x)B注意：上面几式中，注意：上面几式中，B中不能出现约束变元中不能出现约束变元x。x(A(x)B)x A(x)B 不成立不成立()2.2 谓词公式中的等价与蕴含谓词公式中
16、的等价与蕴含 第19页，共37页，编辑于2022年，星期二 x(A(x)B)x A(x)B 不成立不成立()x(A(x)B)x(A(x)B)x A(x)B x A(x)B x A(x)B同理同理,x(A(x)B)x A(x)B 2.2 谓词公式中的等价与蕴含谓词公式中的等价与蕴含 第20页，共37页，编辑于2022年，星期二(4)量词分配的等价关系量词分配的等价关系 x(A(x)B(x)x A(x)x B(x)x(A(x)B(x)x A(x)x B(x)证明证明:设设u=a1,a2,an x(A(x)B(x)(A(a1)B(a1)(A(a2)B(a2)(A(an)B(an)(A(a1)(A(a
17、2)A(an)(B(a1)(B(a2)B(an)x A(x)x B(x)同理可证同理可证,x(A(x)B(x)x A(x)x B(x)2.2 谓词公式中的等价与蕴含谓词公式中的等价与蕴含 第21页，共37页，编辑于2022年，星期二(5)量词分配的蕴含关系量词分配的蕴含关系 x A(x)x B(x)x(A(x)B(x)x(A(x)B(x)x A(x)x B(x)“所有的人都喜欢下棋或者所有的人都喜欢打牌所有的人都喜欢下棋或者所有的人都喜欢打牌”可推出可推出“所有的人都喜欢下棋或打牌所有的人都喜欢下棋或打牌”，反之不然。，反之不然。“有的人喜欢下棋和打牌有的人喜欢下棋和打牌”可推出可推出“有的人
18、喜欢下棋并且有的人喜欢打牌有的人喜欢下棋并且有的人喜欢打牌”，反之不然。，反之不然。2.2 谓词公式中的等价与蕴含谓词公式中的等价与蕴含 第22页，共37页，编辑于2022年，星期二(6)多重量词的可交换性多重量词的可交换性 x y A(x,y)y x A(x,y)x y A(x,y)y x A(x,y)y x A(x,y)x y A(x,y)y x A(x,y)x y A(x,y)“有的人要补考所有的课程有的人要补考所有的课程”可推出可推出“所有的课程都有人要补考所有的课程都有人要补考”，反之不然。，反之不然。2.2 谓词公式中的等价与蕴含谓词公式中的等价与蕴含 第23页，共37页，编辑于2
19、022年，星期二2.3 前束范式前束范式 1、前束范式、前束范式前束范式前束范式一个公式，如果量词均在全式的开头，它们的作一个公式，如果量词均在全式的开头，它们的作用域，延伸到整个公式的未尾，则该公式叫做前束范式。用域，延伸到整个公式的未尾，则该公式叫做前束范式。前束范式可记为下述形式：前束范式可记为下述形式：Q1x1Q2x2QkxkB 其中其中Qi可能是量词可能是量词 或量词或量词 ，Qixi(i=1,2,n)为为 xi或者或者 xi，B是不带量词的谓词公式。是不带量词的谓词公式。第24页，共37页，编辑于2022年，星期二2.3 前束范式前束范式 【例例7】求下面公式的前束范式。求下面公式
20、的前束范式。(1)x A(x)x B(x)解：解：x A(x)x B(x)x A(x)x B(x)x(A(x)B(x)(2)x A(x)x B(x)解：解：x A(x)x B(x)x A(x)x B(x)x A(x)y B(y)x y(A(x)B(y)第25页，共37页，编辑于2022年，星期二(3)x A(x)x B(x)解：解：x A(x)x B(x)x A(x)x B(x)x A(x)x B(x)x A(x)y B(y)x y(A(x)B(y)(4)x A(x)x B(x)解：解：x A(x)x B(x)x A(x)x B(x)x A(x)x B(x)x(A(x)B(x)2.3 前束范式
21、前束范式 第26页，共37页，编辑于2022年，星期二2、谓词公式转换为前束范式的方法：、谓词公式转换为前束范式的方法：任意一个谓词公式均和一个前束范式等价。其转换步骤为：任意一个谓词公式均和一个前束范式等价。其转换步骤为：(1)消去联结词消去联结词 和和。(2)将联结词将联结词向内深入，使之只作用于原子谓词公式。向内深入，使之只作用于原子谓词公式。(3)利用换名或代入规则使所有约束变元的符号都不同，并利用换名或代入规则使所有约束变元的符号都不同，并且自由变元与约束变元的符号也不同。且自由变元与约束变元的符号也不同。(4)利用量词辖域的扩张和收缩，扩大量词至整个公式。利用量词辖域的扩张和收缩，
22、扩大量词至整个公式。(5)利用分配律将公式化为前束范式。利用分配律将公式化为前束范式。2.3 前束范式前束范式 第27页，共37页，编辑于2022年，星期二【例例8】化公式化公式 x y(z(P(x,z)P(y,z)u Q(x,y,u)为前束范式。为前束范式。解：解：x y(z(P(x,z)P(y,z)u Q(x,y,u)x y(z(P(x,z)P(y,z)u Q(x,y,u)x y(z(P(x,z)P(y,z)u Q(x,y,u)x y z u(P(x,z)P(y,z)Q(x,y,u)2.3 前束范式前束范式 第28页，共37页，编辑于2022年，星期二【例例9】把公式把公式 x y A(x
23、,y)x y B(x,y)y(A(y,x)B(x,y)化为前束范式。化为前束范式。解：解：第一步否定深入第一步否定深入原式原式 x yA(x,y)x yB(x,y)y(A(y,x)B(x,y)x yA(x,y)x y B(x,y)y (A(y,x)B(x,y)第二步改名，以便把量词提到前面。第二步改名，以便把量词提到前面。x yA(x,y)u R B(u,R)z(A(z,u)B(u,z)x y u R zA(x,y)B(u,R)(A(z,u)B(u,z)2.3 前束范式前束范式 第29页，共37页，编辑于2022年，星期二2.4 谓词逻辑推理谓词逻辑推理 1、推理形式、推理形式 H1 H2 H
24、m C 其中，其中，H1、H2、Hm 称为推理的前提，称为推理的前提，C为这一组前提的为这一组前提的有效结论。它们一般都是谓词公式。有效结论。它们一般都是谓词公式。第30页，共37页，编辑于2022年，星期二2、推理规则、推理规则(1)P规则规则（前提引入规则）：给定的前提在证明的过程中随（前提引入规则）：给定的前提在证明的过程中随时都可以加以引用。时都可以加以引用。(2)规则规则（结论引用规则）：在证明过程中产生的结论可以作（结论引用规则）：在证明过程中产生的结论可以作为后续证明的前提加以引用。为后续证明的前提加以引用。(3)CP规则规则（附加前提引入规则）：（附加前提引入规则）：如如果果证
25、证明明的的形形式式为为H1 H2 Hm AB，等等价价于于证证明明H1 H2 Hm A B。A称为附加前提。称为附加前提。2.4 谓词逻辑推理谓词逻辑推理谓词逻辑推理谓词逻辑推理 第31页，共37页，编辑于2022年，星期二(4)US规则规则（全称量词消去规则）：（全称量词消去规则）：x A(x)A(c)c是指是指u中任意一个元素中任意一个元素(5)UG规则规则（全称量词引入规则）：（全称量词引入规则）：A(c)x A(x)c是指是指u中任意一个元素中任意一个元素(6)ES规则规则（存在量词消去规则）：（存在量词消去规则）：x A(x)A(c)c是使是使A(x)为真的某个元素为真的某个元素(7
26、)EG规则规则（存在量词引入规则）：（存在量词引入规则）：A(c)x A(x)c是指是指u中某个元素中某个元素2.4 2.4 谓词逻辑推理谓词逻辑推理谓词逻辑推理谓词逻辑推理 第32页，共37页，编辑于2022年，星期二【例例10】证明三段论方法的正确性证明三段论方法的正确性:凡是人都要死。凡是人都要死。苏格拉底苏格拉底是人。是人。苏格拉底要死。苏格拉底要死。令令H(x):x是人。是人。M(x):x要死。要死。s:苏格拉底。苏格拉底。则本题要证明则本题要证明:x(H(x)M(x),H(s)M(s)证明证明:x(H(x)M(x)P H(s)M(s)US H(s)P M(s)T 2.4 2.4 谓
27、词逻辑推理谓词逻辑推理谓词逻辑推理谓词逻辑推理 第33页，共37页，编辑于2022年，星期二【例例11】证明证明 x(C(x)W(x)R(x)x(C(x)Q(x)x(Q(x)R(x)证明：证明：x(C(x)Q(x)P C(a)Q(a)ES C(a)T x(C(x)W(x)R(x)P C(a)W(a)R(a)US W(a)R(a)T R(a)T Q(a)T Q(a)R(a)T x(Q(x)R(x)EG2.4 2.4 谓词逻辑推理谓词逻辑推理 第34页，共37页，编辑于2022年，星期二【例例12】证明证明 x H(x)x(H(x)M(x)x M(x)证明：证明：x H(x)P H(a)ES x(
28、H(x)M(x)P H(a)M(a)US M(a)T x M(x)EG 不不能能互互换换2.4 谓词逻辑推理谓词逻辑推理 第35页，共37页，编辑于2022年，星期二【例例13】例例 2.14 2.14 判断下列的推理过程是否正确。判断下列的推理过程是否正确。证明：证明：x y G（x，y）P y G（z，y）US G（z，c）ES x G（x，c）UG y x G（x，y）EG 2.4 2.4 谓词逻辑推理谓词逻辑推理 第36页，共37页，编辑于2022年，星期二解：此推理过程是错误的。解：此推理过程是错误的。它它的的推推导导错错误误出出现现在在第第步步。x y G(x，y)的的含含义义是是
29、：对对于于任任意意的的一一个个x，存存在在着着与与它它对对应应的的y，使使得得G(x，y)成成立立。但但是是，对对 y G(z，y)利利用用ES规规则则消消去去存存在在变变量量后后得得到到G(z，c)的的含含义义却却是是：对对于于任任意意个个体体z，有有同同一一个个体体c，使使得得G(z，c)成成立立。显显然然，G(z，c)不是不是 y G(z，y)的有效结论。的有效结论。因因此此，使使用用ES规规则则 xP(x)P(c)消消去去存存在在量量词词的的条条件件是是：P(x)中除中除x外没有其他自由出现的个体变元。外没有其他自由出现的个体变元。2.4 2.4 谓词逻辑推理谓词逻辑推理谓词逻辑推理谓词逻辑推理 第37页，共37页，编辑于2022年，星期二