离散数学 第三章 一阶逻辑.ppt

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

1、第三章第三章 一阶逻辑一阶逻辑1一阶逻辑基本概念一阶逻辑基本概念一阶逻辑命题符号化一阶逻辑命题符号化一阶逻辑公式、解释一阶逻辑公式、解释2谓词逻辑（一阶逻辑）的引入谓词逻辑（一阶逻辑）的引入n著名的三段论论证：著名的三段论论证：所有的人都将死去。所有的人都将死去。苏格拉底是人。苏格拉底是人。所以：苏格拉底将死去。所以：苏格拉底将死去。n从人们的实践经验可知，这是一个有效的推论。从人们的实践经验可知，这是一个有效的推论。n但在命题逻辑中却无法判断它的正确性。但在命题逻辑中却无法判断它的正确性。n因为在命题逻辑中只能将推理中的三个简单命因为在命题逻辑中只能将推理中的三个简单命题符号化为题符号化为p

2、,q,r，那么由，那么由p,q这两个命题无论这两个命题无论如何不可能得出如何不可能得出r为有效结论。为有效结论。33.1一阶逻辑基本概念一阶逻辑基本概念 个体词个体词 谓词谓词 量词量词 一阶逻辑中命题符号化一阶逻辑中命题符号化 一阶逻辑公式与分类一阶逻辑公式与分类4基本概念基本概念个体词、谓词、量词个体词、谓词、量词个体词（个体）个体词（个体）:所研究对象中可以独立存在的具所研究对象中可以独立存在的具体或抽象的客体体或抽象的客体个体常项个体常项：具体的事务，用：具体的事务，用a,b,c表示表示个体变项个体变项：抽象的事物，用：抽象的事物，用x,y,z表示表示个体域（论域）个体域（论域）:个体

3、变项的取值范围个体变项的取值范围有限个体域有限个体域，如，如a,b,c,1,2无限个体域无限个体域，如，如N,Z,R,全总个体域全总个体域:宇宙间一切事物组成宇宙间一切事物组成 如果事先没有给出个体域，都应以全总个体域为如果事先没有给出个体域，都应以全总个体域为个体域。个体域。5基本概念基本概念(续续)谓词谓词:刻划个体词性质或相互之间关系的词刻划个体词性质或相互之间关系的词谓谓词词常常项项：表表示示具具体体性性质质和和关关系系的的谓谓词词，用用F,G,H表示；表示；谓谓词词变变项项：表表示示抽抽象象或或泛泛指指的的谓谓词词，也也用用F,G,H表示；表示；一元谓词一元谓词:表示事物的性质表示事

4、物的性质多元谓词多元谓词(n元谓词元谓词,n 2):表示事物之间的关系表示事物之间的关系如如L(x,y)：x与与y有关系有关系L，L(x,y)：x y，0元谓词元谓词:不含个体变项的谓词不含个体变项的谓词,即命题常项或命即命题常项或命题变项题变项6实例(1)4是偶数是偶数4是个体常项是个体常项,“是偶数是偶数”是谓词常项是谓词常项,符号化为符号化为:F(4)(2)小王和小李同岁小王和小李同岁小王小王,小李是个体常项小李是个体常项,同岁是谓词常项同岁是谓词常项.记记a:小王小王,b:小李小李,G(x,y):x与与y同岁同岁,符号化为符号化为:G(a,b)(3)x yx,y是命题变项是命题变项,3

5、，则，则3y，G(x,y)：xy,符号化为符号化为F(2,3)G(3,4)9将下列命题符号化将下列命题符号化,并讨论其真值并讨论其真值:(1)对任意的对任意的x,均有均有x2-3x+2=(x-1)(x-2)(2)存在存在x,使得使得x+5=3分别取分别取(a)个体域个体域D1=N,(b)个体域个体域D2=R解解记记F(x):x2-3x+2=(x-1)(x-2),G(x):x+5=3(a)(1)x F(x)真值为真值为1(2)x G(x)真值为真值为0(b)(1)x F(x)真值为真值为1(2)x G(x)真值为真值为110基本概念基本概念(续续)量词量词:表示数量的词表示数量的词全称量词全称量

6、词:表示任意的表示任意的,所有的所有的,一切的等一切的等如如 x 表示对个体域中所有的表示对个体域中所有的x存在量词存在量词:表示存在表示存在,有的有的,至少有一个等至少有一个等如如 x表示在个体域中存在表示在个体域中存在x11一阶逻辑中命题符号化一阶逻辑中命题符号化(续续)例例2在一阶逻辑中将下面命题符号化在一阶逻辑中将下面命题符号化(1)人都爱美人都爱美;(2)有人用左手写字有人用左手写字分别取分别取(a)D为人类集合为人类集合,(b)D为全总个体域为全总个体域.解：解：(a)(1)设设G(x)：x爱美爱美,符号化为符号化为 x G(x)(2)设设G(x)：x用左手写字用左手写字,符号化为

7、符号化为 x G(x)(b)设设F(x)：x为人，为人，G(x)：同：同(a)中中(1)x(F(x)G(x)(2)x(F(x)G(x)这是两个基本公式这是两个基本公式,注意这两个基本公式的使用注意这两个基本公式的使用.在这里是在这里是F(x)特性谓词特性谓词12几点注意：几点注意：1.1.谓词的记法谓词的记法设论域设论域A A中元素中元素a,b,c A,a,b,c A,满足关系满足关系P,Q,RP,Q,R，记作，记作P(a),Q(a,b),R(a,b,cP(a),Q(a,b),R(a,b,c).).不满足关系记作不满足关系记作 P(aP(a),),Q(a,bQ(a,b),),R(a,b,cR(

8、a,b,c).).一阶逻辑命题符号化一阶逻辑命题符号化例例 将下列命题符号化将下列命题符号化 :李明是位大学生李明是位大学生.解解:S(x):xS(x):x是位大学生；是位大学生；c:c:李明李明则该命题符号化为则该命题符号化为S(cS(c)13例例:若若x x的论域为某大学的全体学生，则的论域为某大学的全体学生，则S(xS(x)为真；为真；若若x x的论域为某中学的全体学生，则的论域为某中学的全体学生，则S(xS(x)为假；为假；若若x x的论域为某剧场中的观众，则的论域为某剧场中的观众，则S(xS(x)真值不确定；真值不确定；2.2.个体变元在哪些论域取特定的值，个体变元在哪些论域取特定的

9、值，对命题的真值有影响。对命题的真值有影响。14例例 将下列命题符号化将下列命题符号化 :(1)(1)小李比小赵高小李比小赵高.(2)(2)武汉位于北京和广州之间武汉位于北京和广州之间3.个体变项的顺序影响命题真值，不能随意调换个体变项的顺序影响命题真值，不能随意调换.解解(1)(1)L(x,y):xL(x,y):x比比y y高；高；a:a:小李；小李；b:b:小赵小赵 则该命题符号化为则该命题符号化为 L(a,bL(a,b)(2)(2)P(x,y,z):xP(x,y,z):x位于位于y y和和z z之间；之间；a:a:武汉武汉;b:;b:北京北京;c:c:广州广州 ,则该命题符号化为则该命题

10、符号化为P(a,b,cP(a,b,c)15例：将命题符号化例：将命题符号化:凡有理数均可表成分数凡有理数均可表成分数,(1)(1)个体域是有理数集合个体域是有理数集合.(2)(2)个体域是实数集合个体域是实数集合4.4.在不同的个体域中在不同的个体域中,命题符号化的形式可能不一样命题符号化的形式可能不一样 解(1)xA(x)其中A(x)：x可表成分数 (2)x(R(x)A(x)其中 R(x)：x是有理数，A(x)：x可表成分数165.5.在引入特性谓词后，使用全称量词与存在引入特性谓词后，使用全称量词与存在量词符号化的形式是不同的。在量词符号化的形式是不同的。例将命题符号化:(1)每个自然数都

11、是实数.(2)有的自然数是实数.解(1)x(N(x)R(x)其中特性谓词N(x)：x是自然数;R(x)：x是实数(2)x(N(x)R(x)其中特性谓词N(x)：x是自然数;R(x)：x是实数17例：对任意的x，存在着y,使得x+y=5,个体域为实数集，其中H(x,y)：x+y=5，xyH(x,y)真命题如果颠倒量词的顺序，yxH(x,y)假命题意为“存在着y，对任意的x，都有x+y=5”，意义不符、假命题。6.6.多个量词同时出现时多个量词同时出现时,不能随意颠倒它们不能随意颠倒它们的顺序，颠倒后会改变原命题的含义的顺序，颠倒后会改变原命题的含义.18一阶逻辑中命题符号化一阶逻辑中命题符号化(

12、续续)例例3在一阶逻辑中将下面命题符号化在一阶逻辑中将下面命题符号化(1)兔子比乌龟跑得快兔子比乌龟跑得快(2)有的兔子比所有的乌龟跑得快有的兔子比所有的乌龟跑得快（3）并不是所有的兔子都比乌龟跑得快）并不是所有的兔子都比乌龟跑得快（4）不存在跑得同样快的两只兔子）不存在跑得同样快的两只兔子19一阶逻辑中命题符号化一阶逻辑中命题符号化(续续)解解用全总个体域用全总个体域,令令F(x):x是兔子是兔子,G(y):y是乌龟是乌龟,H(x,y):x比比y跑得快跑得快,L(x,y):x和和y跑得一样快跑得一样快(1)x y(F(x)G(y)H(x,y)(2)x(F(x)(y(G(y)H(x,y)(3)

13、x y(F(x)G(y)H(x,y)(4)x y(F(x)G(y)L(x,y)203.1.4一阶逻辑公式及分类一阶逻辑公式及分类字母表字母表合式公式合式公式(简称公式简称公式)个体变项的自由出现和约束出现个体变项的自由出现和约束出现解释解释永真式（逻辑有效式）永真式（逻辑有效式）矛盾式（永假式）矛盾式（永假式）可满足式可满足式 21字母表字母表 定义定义字母表字母表包含下述符号：包含下述符号：(1)个体常项：个体常项：a,b,c,ai,bi,ci,i 1(2)个体变项：个体变项：x,y,z,xi,yi,zi,i 1(3)函数符号：函数符号：f,g,h,fi,gi,hi,i 1(4)谓词符号：谓

14、词符号：F,G,H,Fi,Gi,Hi,i 1(5)量词符号：量词符号：,(6)联结词符号：联结词符号：,(7)括号与逗号：括号与逗号：(,),，22字母表中的函数字母表中的函数是广义的函数，它是一个从个体到个体的映射。是广义的函数，它是一个从个体到个体的映射。例例1.1.f(x,yf(x,y)表示表示x-y,f(7,4)x-y,f(7,4)表示个体自然数表示个体自然数3 3例例2.2.函数函数f(xf(x)：x x 的母亲的母亲,c:,c:张明张明 谓词谓词P(xP(x)：x x是教师，则是教师，则 P(P(f(cf(c)：张明的母亲是教师。：张明的母亲是教师。23项项 定义定义项项的定义如下

15、：的定义如下：(1)个体常项和个体变项是项个体常项和个体变项是项.(2)若若(x1,x2,xn)是是 任任 意意 的的 n元元 函函 数数，t1,t2,tn是是任意的任意的n个项，则个项，则(t1,t2,tn)是项是项.(3)所有的项都是有限次使用所有的项都是有限次使用(1),(2)得到的得到的.其实其实,个体常项、变项是项，由它们构成的个体常项、变项是项，由它们构成的n元函数元函数和复合函数还是项和复合函数还是项24原子公式原子公式 定定义义 设设R(x1,x2,xn)是是任任意意的的n元元谓谓词词，t1,t2,tn是是任意的任意的n个项，则称个项，则称R(t1,t2,tn)是是原子公式原子

16、公式.其实，原子公式是由项组成的其实，原子公式是由项组成的n元谓词元谓词.例如，例如，F(x,y),F(f(x1,x2),g(x3,x4)等均为原子公式等均为原子公式25合式公式合式公式 定义定义合式公式合式公式（谓词公式谓词公式，简称，简称公式公式）定义如下：）定义如下：(1)原子公式是合式公式原子公式是合式公式.(2)若若A是合式公式，则是合式公式，则(A)也是合式公式也是合式公式(3)若若 A,B是是 合合 式式 公公 式式，则则(A B),(A B),(AB),(AB)也是合式公式也是合式公式(4)若若A是合式公式，则是合式公式，则 xA,xA也是合式公式也是合式公式(5)只有有限次地

17、应用只有有限次地应用(1)(4)形成的符号串形成的符号串才是合式公式才是合式公式.请举出几个合式公式的例子请举出几个合式公式的例子.26个体变项的自由出现与约束出现个体变项的自由出现与约束出现 定义定义在公式在公式 xA和和 xA中，称中，称x为为指导变元指导变元，A为相为相应量词的应量词的辖域辖域.在在 x和和 x的的辖域辖域中，中，x的所有出现都的所有出现都称为称为约束出现约束出现，A中不是约束出现的其他变项均称中不是约束出现的其他变项均称为是为是自由出现的自由出现的.例如例如,在公式在公式 x(F(x,y)G(x,z)中中,A=(F(x,y)G(x,z)为为 x的辖域，的辖域，x为指导变

18、元为指导变元,A中中x的两次出现均为约束出现，的两次出现均为约束出现，y与与z均为自由出现均为自由出现.闭式闭式(封闭的公式封闭的公式):不含自由出现的个体变项的公式不含自由出现的个体变项的公式.27例例3 1.x(x+1=0)量词的辖域是全公式。x是约束变元 2.x(x+y+10)量词的辖域是全公式。x是约束变元,y是自由变元 3.x(x+y+1=0 y(x+y+10)的辖域是(x+y+12,G(x):x1代入得代入得A=x(x2x1)真命题真命题成假解释成假解释:个体域个体域N,F(x):x1,G(x):x2代入得代入得A=x(x1x2)假命题假命题问问:xF(x)x F(x)有成真解释吗

19、？有成真解释吗？xF(x)x F(x)有成假解释吗？有成假解释吗？29解释解释 定义定义解释解释I由下面由下面4部分组成：部分组成：(a)非空个体域非空个体域DI(b)DI中一些特定元素的集合中一些特定元素的集合(c)DI上特定函数集合上特定函数集合(d)DI上特定谓词的集合上特定谓词的集合说明：说明：在解释的定义中引进了元语言符号在解释的定义中引进了元语言符号,如如等等被解释的公式被解释的公式A中的个体变项均取值于中的个体变项均取值于DI若若A中含个体常项中含个体常项ai，就解释成就解释成30解释解释(续续)为为第第i 个个n元元谓谓词词.例例如如，表表示示第第2个个3元元谓谓词词，它它可可

20、能能以以形形式式出出现现在在解解释释中中，公式公式A中若出现中若出现F2(x,y,z)就解释成就解释成为为第第i 个个n元元函函数数.例例如如，表表示示第第一一个个二二元元函数函数,它出现在解释中，可能是它出现在解释中，可能是=2xy等等，一一旦旦公公式式中中出出现现f1(x,y)就就解解释释成成,出现出现g1(x,y)就解释成就解释成31解释解释(续续)例例4 4 给定解释给定解释I I 如下如下:(a)个体域个体域D=N(b)(c)(d)谓词谓词说明下列公式在说明下列公式在I 下的涵义下的涵义,并讨论真值并讨论真值(1)xF(g(x,a),x)x(2x=x)假命题假命题(2)x y(F(f

21、(x,a),y)F(f(y,a),x)x y(x+2=yy+2=x)假命题假命题32例例1(续续)(3)x y zF(f(x,y),z)两点说明两点说明:5个小题都是闭式个小题都是闭式,在在I下全是命题下全是命题(3)与与(5)说明，量词顺序不能随意改变说明，量词顺序不能随意改变(5)x y zF(f(y,z),x)x y z(y+z=x)假命题假命题(4)xF(f(x,x),g(x,x)x(2x=x2)真命题真命题 x y z(x+y=z)真命真命题题33解释解释(续续)n被解释的公式不一定全部包含解释中的被解释的公式不一定全部包含解释中的4部分部分.n 闭式在任何解释下都是命题，闭式在任何

22、解释下都是命题，n 注注意意不不是是闭闭式式的的公公式式在在某某些些解解释释下下也也可可能能是是命题命题.34公式的分类公式的分类 永真式（逻辑有效式）永真式（逻辑有效式）：无成假赋值：无成假赋值矛盾式（永假式）矛盾式（永假式）：无成真赋值：无成真赋值可满足式可满足式：至少有一个成真赋值：至少有一个成真赋值几点说明：几点说明：永真式为可满足式，但反之不真永真式为可满足式，但反之不真判断公式是否为可满足式不是易事判断公式是否为可满足式不是易事(不同于命题逻辑不同于命题逻辑)某些特殊公式可以判断类型某些特殊公式可以判断类型 35代换实例代换实例(续续)例例5证明下面公式既不是永真式，也不是矛盾式证

23、明下面公式既不是永真式，也不是矛盾式(1)x(F(x)G(x)(2)x(F(x)G(x)(3)x y(F(x)G(y)H(x,y)不难对每一个公式给出一个成假解释和一个成真不难对每一个公式给出一个成假解释和一个成真解释解释,从而证明它们既不是永真式，也不是矛盾从而证明它们既不是永真式，也不是矛盾式式.36代换实例代换实例 定义定义设设A0是含命题变项是含命题变项p1,p2,pn的命题公式，的命题公式，A1,A2,An是是n个个谓谓词词公公式式，用用Ai处处处处代代替替A0中中的的pi(1 i n)，所得公式所得公式A称为称为A0的的代换实例代换实例.例如例如:F(x)G(x),xF(x)yG(

24、y)等都是等都是pq的换实例，的换实例，x(F(x)G(x)等不是等不是pq 的代换实例的代换实例.定理定理重言式的代换实例都是永真式，矛盾式的代重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式换实例都是矛盾式.37代换实例代换实例(续续)例例6判断下面公式类型判断下面公式类型(1)xF(x)(x yG(x,y)xF(x)(2)(x y G(x,y)xF(x)xF(x)383.2一阶逻辑等值演算一阶逻辑等值演算等值式等值式基本等值式基本等值式量词否定等值式量词否定等值式量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式量词分配等值式量词分配等值式39等值式与基本等值式等值式与基本等值式 在

25、一阶逻辑中，有些命题可以有不同的符号化在一阶逻辑中，有些命题可以有不同的符号化形式。形式。例如例如：没有不呼吸的人。：没有不呼吸的人。取全总个体域时有下面两种不同的符号化形式：取全总个体域时有下面两种不同的符号化形式：(1)x(F(x)G(x)(2)x(F(x)G(x)F(x)：x是人，是人，G(x)：x要呼吸要呼吸40等值式与基本等值式等值式与基本等值式 基本等值式基本等值式:命题逻辑中命题逻辑中1616组基本等值式的代换实例组基本等值式的代换实例如，如，xF(x)yG(y)xF(x)yG(y)(xF(x)yG(y)xF(x)yG(y)等等消去量词等值式消去量词等值式设设D=a1,a2,an

26、 xA(x)A(a1)A(a2)A(an)xA(x)A(a1)A(a2)A(an)定义定义若若AB为逻辑有效式，则称为逻辑有效式，则称A与与B是是等值等值的，的，记作记作AB，并称并称AB为为等值式等值式.41实例例例设个体域设个体域D=a,b,c,消去下面公式中的量词消去下面公式中的量词:(1)x(F(x)G(x)(F(a)G(a)(F(b)G(b)(F(c)G(c)(2)x(F(x)yG(y)xF(x)yG(y)量词辖域收缩量词辖域收缩(F(a)F(b)F(c)(G(a)G(b)G(c)x(F(x,a)F(x,b)F(x,c)(3)x yF(x,y)(F(a,a)F(a,b)F(a,c)(

27、F(b,a)F(b,b)F(b,c)(F(c,a)F(c,b)F(c,c)42实例解解(F(f(2)G(2,f(2)(F(f(3)G(3,f(3)例例给定解释给定解释I:(a)D=2,3,(b)(c):x是奇数是奇数,:x=2 y=2,:x=y.在在I下求下列各式的真值下求下列各式的真值:(1)x(F(f(x)G(x,f(x)(2)x yL(x,y)(1 1)(0 1)1解解 yL(2,y)yL(3,y)(L(2,2)L(2,3)(L(3,2)L(3,3)(1 0)(0 1)043基本的等值式基本的等值式(续续)量词否定等值式量词否定等值式设设A(x)是含是含x自由出现的公式自由出现的公式 x

28、A(x)x A(x)xA(x)x A(x)44基本等值式基本等值式(续续)量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式设设A(x)是含是含x自由出现的公式，自由出现的公式，B中不含中不含x的出现的出现关于全称量词的：关于全称量词的：x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x)BxA(x)关于存在量词的关于存在量词的:x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x)BxA(x)45基本的等值式基本的等值式(续续)量词分配等值式量词分配等值式 x(A(x)B(x)xA(x)xB(

29、x)x(A(x)B(x)xA(x)xB(x)注意：注意：对对 无分配律，无分配律，对对 无分配律无分配律46基本的等值式基本的等值式(续续)例例将下面命题用两种形式符号化将下面命题用两种形式符号化(1)没有不犯错误的人没有不犯错误的人(2)不是所有的人都爱看电影不是所有的人都爱看电影解解(1)令令F(x)：x是人，是人，G(x)：x犯错误犯错误.x(F(x)G(x)x(F(x)G(x)请给出演算过程，并说明理由请给出演算过程，并说明理由.(2)令令F(x)：x是人，是人，G(x)：爱看电影爱看电影.x(F(x)G(x)x(F(x)G(x)给出演算过程，并说明理由给出演算过程，并说明理由.47等

30、值演算的三条原则等值演算的三条原则置换规则置换规则：若：若AB,则则(B)(A)换换名名规规则则:将将量量词词辖辖域域中中出出现现的的某某个个约约束束变变项项的的所所有有出出现现及及对对应应的的指指导导变变项项，改改成成该该量量词词辖辖域域中中未未曾曾出出现现过过的的个个体体变变项项符符号号，公公式式中中其其余余部部分分不不变变，则则所所得得公公式式与原来的公式等值与原来的公式等值.代替规则代替规则:对某对某自由出现的个体变项自由出现的个体变项用与用与原公式中所有原公式中所有个体变项符号不同的符号个体变项符号不同的符号去代替，则所得公式与原来去代替，则所得公式与原来的公式等值的公式等值.48换

31、名规则与代替规则换名规则与代替规则例例(1)xF(x)y(G(x,y)H(y)zF(z)y(G(x,y)H(y)（换名规则）（换名规则）(2)x(F(x,y)y(G(x,y)H(x,z)x(F(x,u)y(G(x,y)H(x,z)(代代替替规规则则)49例例给定解释给定解释I如下：如下：(a)个体域个体域D=2,3(b)D中特定元素中特定元素a=2(c)D中特定函数中特定函数f(x)为为：f(2)=3，f(3)=2(d)D中特定谓词中特定谓词G(x,y)为为：G(2,2)=G(2,3)=G(3,2)=1 G(3,3)=0.L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0.F(x)

32、为：为：F(2)=0，F(3)=1。在。在I下求下列各式的值下求下列各式的值(1)x(F(x)G(x,a)(2)x(F(f(x)G(x,f(x)(3)x yL(x,y)(4)y xL(x,y)50前束范式前束范式 例如，例如，x y(F(x)(G(y)H(x,y)x(F(x)G(x)是前束范式是前束范式,而而 x(F(x)y(G(y)H(x,y)x(F(x)G(x)不是前束范式，不是前束范式，定义定义设设A为一个一阶逻辑公式为一个一阶逻辑公式,若若A具有如下形式具有如下形式Q1x1Q2x2QkxkB,则称则称A为为前束范式前束范式,其中其中Qi(1 i k)为为 或或，B为不含量词的公式为不含

33、量词的公式.51公式的前束范式公式的前束范式 定理（前束范式存在定理）定理（前束范式存在定理）一阶逻辑中的任何公一阶逻辑中的任何公式都存在与之等值的前束范式式都存在与之等值的前束范式 注意注意:公式的前束范式不惟一公式的前束范式不惟一 求公式的前束范式的方法求公式的前束范式的方法:利用重要等值式、利用重要等值式、置换规则、换名规则、代替规则进行等值演算置换规则、换名规则、代替规则进行等值演算.52公式的前束范式公式的前束范式(续续)例例求下列公式的前束范式求下列公式的前束范式(1)x(M(x)F(x)解解x(M(x)F(x)x(M(x)F(x)（量词否定等值式）量词否定等值式）x(M(x)F(

34、x)两步结果都是前束范式，说明前束范式不惟一两步结果都是前束范式，说明前束范式不惟一.53例例(续续)(2)xF(x)xG(x)解解 xF(x)xG(x)xF(x)x G(x)（量词否定等值式）量词否定等值式）x(F(x)G(x)（量词分配等值式）量词分配等值式）另有一种形式另有一种形式 xF(x)xG(x)xF(x)x G(x)（量词否定等值式）（量词否定等值式）xF(x)y G(y)(换名规则换名规则)x y(F(x)G(y)(量词辖域扩张量词辖域扩张)两种形式是等值的两种形式是等值的54例例(续续)(3)xF(x)xG(x)解解 xF(x)xG(x)xF(x)x G(x)（量词否定等值式

35、）（量词否定等值式）x(F(x)G(x)（为什么？）为什么？）(4)xF(x)y(G(x,y)H(y)解解 xF(x)y(G(x,y)H(y)zF(z)y(G(x,y)H(y)（换名规则）换名规则）z y(F(z)(G(x,y)H(y)（为什么？）为什么？）55例例(续续)或或xF(x)y(G(z,y)H(y)（代替规则）代替规则）x y(F(x)(G(z,y)H(y)(5)x(F(x,y)y(G(x,y)H(x,z)解解用换名规则用换名规则,也可用代替规则也可用代替规则,这里用代替规则这里用代替规则 x(F(x,y)y(G(x,y)H(x,z)x(F(x,u)y(G(x,y)H(x,z)x

36、y(F(x,u)G(x,y)H(x,z)注意：注意：x与与 y不能颠倒不能颠倒56一阶逻辑推理理论一阶逻辑推理理论推理的形式结构推理的形式结构判断推理是否正确的方法判断推理是否正确的方法重要的推理定律重要的推理定律推理规则推理规则构造证明构造证明附加前提证明法附加前提证明法 57推理推理 推理的形式结构推理的形式结构有两种：有两种：第一种第一种 A1 A2 AkB(*)第二种第二种前提：前提：A1，A2，Ak结论：结论：B其中其中A1,A2,Ak,B为一阶逻辑公式为一阶逻辑公式.若若(*)为永真式为永真式,则称则称推理正确推理正确,否则称否则称推理推理不正确不正确.58重要的推理定律重要的推理

37、定律 第一组第一组 命题逻辑推理定律代换实例命题逻辑推理定律代换实例如如 xF(x)yG(y)xF(x)为化简律代换实例为化简律代换实例.第二组第二组 由基本等值式生成由基本等值式生成如如由由xA(x)x A(x)生成生成xA(x)x A(x),x A(x)xA(x),第三组第三组 xA(x)xB(x)x(A(x)B(x)x(A(x)B(x)xA(x)xB(x)59推理规则推理规则 (1)(1)前提引入规则前提引入规则 (2)(2)结论引入规则结论引入规则(3)(3)置换规则置换规则 (4)(4)假言推理规则假言推理规则(5)(5)附加规则附加规则 (6)(6)化简规则化简规则(7)(7)拒取

38、式规则拒取式规则 (8)(8)假言三段论规则假言三段论规则(9)(9)析取三段论规则析取三段论规则 (10)(10)构造性二难推理规则构造性二难推理规则(11)(11)合取引入规则合取引入规则 60推理规则推理规则(续续)(12)全称量词消去规则（简记为全称量词消去规则（简记为UI规则或规则或UI）两式成立的条件是：两式成立的条件是：在第一式中，取代在第一式中，取代x的的y应为任意的不在应为任意的不在A(x)中中约束出现的个体变项约束出现的个体变项.在第二式中，在第二式中，c为任意个体常项为任意个体常项.用用y或或c去取代去取代A(x)中的自由出现的中的自由出现的x时，一定要时，一定要在在x自

39、由出现的一切地方进行取代自由出现的一切地方进行取代.61推理规则推理规则(续续)(13)全称量词引入规则（简记为全称量词引入规则（简记为UG规则或规则或UG）该式成立的条件是：该式成立的条件是：无论无论A(y)中自由出现的个体变项中自由出现的个体变项y取何值，取何值，A(y)应该均为真应该均为真.取代自由出现的取代自由出现的y的的x，也不能也不能在在A(y)中约束出中约束出现现.62推理规则推理规则(续续)(14)存在量词引入规则（简记为存在量词引入规则（简记为EG规则或规则或EG）该式成立的条件是：该式成立的条件是：c是使是使A为真的特定个体常项为真的特定个体常项.取代取代c的的x不能在不能

40、在A(c)中出现过中出现过.63推理规则推理规则(续续)(15)存在量词消去规则存在量词消去规则（简记为简记为EI规则或规则或EI）该式成立的条件是：该式成立的条件是：c是使是使A为真的特定的个体常项为真的特定的个体常项.c不在不在A(x)中出现中出现.若若A(x)中除自由出现的中除自由出现的x外，还有其他自由出现外，还有其他自由出现的个体变项，此规则不能使用的个体变项，此规则不能使用.64构造推理证明构造推理证明 例例1证证明明苏苏格格拉拉底底三三段段论论:“人人都都是是要要死死的的,苏苏格格拉拉底是人，所以苏格拉底是要死的底是人，所以苏格拉底是要死的.”令令F(x):x是人是人,G(x):

41、x是要死的是要死的,a:苏格拉底苏格拉底前提：前提：x(F(x)G(x)，F(a)结论：结论：G(a)证明：证明：F(a)前提引入前提引入 x(F(x)G(x)前提引入前提引入F(a)G(a)UIG(a)假言推理假言推理注意：使用注意：使用UI时，用时，用a取代取代x.65构造推理证明构造推理证明(续续)例例2乌鸦都不是白色的乌鸦都不是白色的.北京鸭是白色的北京鸭是白色的.因此，因此，北京鸭不是乌鸦北京鸭不是乌鸦.令令F(x):x是乌鸦是乌鸦,G(x):x是北京鸭是北京鸭,H(x):x是白色的是白色的前提：前提：x(F(x)H(x)，x(G(x)H(x)结论：结论：x(G(x)F(x)66例例

42、2(续续)证明：证明：x(F(x)H(x)前提引入前提引入F(y)H(y)UI x(G(x)H(x)前提引入前提引入G(y)H(y)UI H(y)G(y)置换置换F(y)G(y)假言三段论假言三段论G(y)F(y)置换置换 x(G(x)F(x)UG67构造推理证明构造推理证明(续续)例例3构造下述推理证明构造下述推理证明前提：前提：x(F(x)G(x)，xF(x)结论：结论：xG(x)证明：证明：xF(x)前提引入前提引入 x(F(x)G(x)前提引入前提引入F(c)EIF(c)G(c)UIG(c)假言推理假言推理 xG(x)EG注意：必须先消存在量词注意：必须先消存在量词68构造推理证明构造

43、推理证明(续续)例例4构造下述推理证明构造下述推理证明前提：前提：xF(x)xG(x)结论：结论：x(F(x)G(x)证明：证明：xF(x)xG(x)前提引入前提引入 x y(F(x)G(y)置换置换 x(F(x)G(z)UIF(z)G(z)UI x(F(x)G(x)UG说明说明:不能对不能对 xF(x)xG(x)消量词消量词,因为它不是前束范式因为它不是前束范式.对此题不能用附加前提证明法对此题不能用附加前提证明法.69构造推理证明构造推理证明(续续)例例5构造下述推理证明构造下述推理证明前提：前提：x(F(x)G(x)结论：结论：xF(x)xG(x)证明：证明：xF(x)附加前提引入附加前提引入F(y)UI x(F(x)G(x)前提引入前提引入F(y)G(y)UIG(y)假言推理假言推理 xG(x)UG本题可以使用附加前提证明法本题可以使用附加前提证明法70