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

《离散数学第三章一阶逻辑.ppt》由会员分享，可在线阅读，更多相关《离散数学第三章一阶逻辑.ppt（70页珍藏版）》请在三一办公上搜索。

1、1,第三章 一阶逻辑,2,一阶逻辑基本概念,一阶逻辑命题符号化一阶逻辑公式、解释,3,谓词逻辑（一阶逻辑）的引入,著名的三段论论证：所有的人都将死去。苏格拉底是人。所以：苏格拉底将死去。从人们的实践经验可知，这是一个有效的推论。但在命题逻辑中却无法判断它的正确性。因为在命题逻辑中只能将推理中的三个简单命题符号化为p,q,r，那么由p,q这两个命题无论如何不可能得出r为有效结论。,4,3.1 一阶逻辑基本概念,个体词 谓词 量词 一阶逻辑中命题符号化 一阶逻辑公式与分类,5,基本概念个体词、谓词、量词,个体词（个体）:所研究对象中可以独立存在的具体或抽象的客体 个体常项：具体的事务，用a,b,c

2、表示 个体变项：抽象的事物，用x,y,z表示 个体域（论域）:个体变项的取值范围 有限个体域，如a,b,c,1,2 无限个体域，如N,Z,R,全总个体域:宇宙间一切事物组成 如果事先没有给出个体域，都应以全总个体域为个体域。,6,基本概念(续),谓词:刻划个体词性质或相互之间关系的词 谓词常项：表示具体性质和关系的谓词，用F,G,H表示；谓词变项：表示抽象或泛指的谓词，也用F,G,H表示；一元谓词:表示事物的性质 多元谓词(n元谓词,n2):表示事物之间的关系 如 L(x,y)：x与y有关系L，L(x,y)：xy，0元谓词:不含个体变项的谓词,即命题常项或命题变项,7,实例,(1)4是偶数 4

3、是个体常项,“是偶数”是谓词常项,符号化为:F(4)(2)小王和小李同岁 小王,小李是个体常项,同岁是谓词常项.记a:小王,b:小李,G(x,y):x与y同岁,符号化为:G(a,b)(3)x y x,y是命题变项,是谓词常项,符号化为:L(x,y)(4)x具有某种性质P x是命题变项,P是谓词变项,符号化为:P(x),8,一阶逻辑中命题符号化,例1 用0元谓词将命题符号化,并讨论它们的真值.要求：先将它们在命题逻辑中符号化，再在一阶 逻辑中符号化(1)墨西哥位于南美洲 在命题逻辑中,设 p:墨西哥位于南美洲 符号化为 p,这是真命题 在一阶逻辑中,设a：墨西哥，F(x)：x位于南美洲 符号化为

4、F(a),9,例1(续),(2)是无理数仅当 是有理数 在一阶逻辑中,设F(x):x是无理数,G(x):x是有理数 符号化为(3)如果23，则3y，G(x,y)：xy,符号化为 F(2,3)G(3,4),10,将下列命题符号化,并讨论其真值:(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)真值为1,11,基本概念(续),量词:表示

5、数量的词 全称量词:表示任意的,所有的,一切的等 如 x 表示对个体域中所有的x 存在量词:表示存在,有的,至少有一个等 如 x 表示在个体域中存在x,12,一阶逻辑中命题符号化(续),例2 在一阶逻辑中将下面命题符号化(1)人都爱美;(2)有人用左手写字 分别取(a)D为人类集合,(b)D为全总个体域.解：(a)(1)设G(x)：x爱美,符号化为 x G(x)(2)设G(x)：x用左手写字,符号化为 x G(x)(b)设F(x)：x为人，G(x)：同(a)中(1)x(F(x)G(x)(2)x(F(x)G(x)这是两个基本公式,注意这两个基本公式的使用.在这里是F(x)特性谓词,13,几点注意

6、：1.谓词的记法,设论域A中元素a,b,c A,满足关系P,Q,R，记作P(a),Q(a,b),R(a,b,c).不满足关系记作 P(a),Q(a,b),R(a,b,c).,一阶逻辑命题符号化,例 将下列命题符号化:李明是位大学生.,解:S(x):x是位大学生；c:李明则该命题符号化为S(c),14,例:若x的论域为某大学的全体学生，则S(x)为真；若x的论域为某中学的全体学生，则S(x)为假；若x的论域为某剧场中的观众，则S(x)真值不确定；,2.个体变元在哪些论域取特定的值，对命题的真值有影响。,15,例 将下列命题符号化:(1)小李比小赵高.(2)武汉位于北京和广州之间,3.个体变项的顺

7、序影响命题真值，不能随意调换.,解(1)L(x,y):x比y高；a:小李；b:小赵 则该命题符号化为 L(a,b),(2)P(x,y,z):x位于y和z之间；a:武汉;b:北京;c:广州,则该命题符号化为P(a,b,c),16,例：将命题符号化:凡有理数均可表成分数,(1)个体域是有理数集合.(2)个体域是实数集合,4.在不同的个体域中,命题符号化的形式可能不一样,解(1)xA(x)其中A(x)：x可表成分数,(2)x(R(x)A(x)其中 R(x)：x是有理数，A(x)：x可表成分数,17,5.在引入特性谓词后，使用全称量词与存在量词符号化的形式是不同的。,例将命题符号化:(1)每个自然数都

8、是实数.(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是实数,18,例：对任意的x，存在着y,使得x+y=5,个体域为实数集，其中H(x,y)：x+y=5，xyH(x,y)真命题如果颠倒量词的顺序，yxH(x,y)假命题意为“存在着y，对任意的x，都有x+y=5”，意义不符、假命题。,6.多个量词同时出现时,不能随意颠倒它们的顺序，颠倒后会改变原命题的含义.,19,一阶逻辑中命题符号化(续),例3 在一阶逻辑中将下面命题符号化(1)兔子比乌龟跑得快(2)有的兔子

9、比所有的乌龟跑得快（3）并不是所有的兔子都比乌龟跑得快（4）不存在跑得同样快的两只兔子,20,一阶逻辑中命题符号化(续),解 用全总个体域,令F(x):x是兔子,G(y):y是乌龟,H(x,y):x比y跑得快,L(x,y):x和y跑得一样快(1)xy(F(x)G(y)H(x,y)(2)x(F(x)(y(G(y)H(x,y)(3)xy(F(x)G(y)H(x,y)(4)xy(F(x)G(y)L(x,y),21,3.1.4 一阶逻辑公式及分类,字母表合式公式(简称公式)个体变项的自由出现和约束出现解释永真式（逻辑有效式）矛盾式（永假式）可满足式,22,字母表,定义 字母表包含下述符号：(1)个体常

10、项：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)谓词符号：F,G,H,Fi,Gi,Hi,i 1(5)量词符号：,(6)联结词符号：,(7)括号与逗号：(,),，,23,字母表中的函数,是广义的函数，它是一个从个体到个体的映射。,例1.f(x,y)表示x-y,f(7,4)表示个体自然数3例2.函数f(x)：x 的母亲,c:张明 谓词P(x)：x是教师，则 P(f(c)：张明的母亲是教师。,24,项,定义 项的定义如下：(1)个体常项和个体变项是项.(2)若(x1,x2,xn)是任意的n元函数，t

11、1,t2,tn是任意的n个项，则(t1,t2,tn)是项.(3)所有的项都是有限次使用(1),(2)得到的.其实,个体常项、变项是项，由它们构成的n元函数和复合函数还是项,25,原子公式,定义 设R(x1,x2,xn)是任意的n元谓词，t1,t2,tn是任意的n个项，则称R(t1,t2,tn)是原子公式.其实，原子公式是由项组成的n元谓词.例如，F(x,y),F(f(x1,x2),g(x3,x4)等均为原子公式,26,合式公式,定义 合式公式（谓词公式，简称公式）定义如下：(1)原子公式是合式公式.(2)若A是合式公式，则(A)也是合式公式(3)若A,B是合式公式，则(AB),(AB),(AB

12、),(AB)也是合式公式(4)若A是合式公式，则xA,xA也是合式公式(5)只有有限次地应用(1)(4)形成的符号串 才是合式公式.请举出几个合式公式的例子.,27,个体变项的自由出现与约束出现,定义 在公式xA和xA中，称x为指导变元，A为相应量词的辖域.在x和x的辖域中，x的所有出现都称为约束出现，A中不是约束出现的其他变项均称为是自由出现的.例如,在公式 x(F(x,y)G(x,z)中,A=(F(x,y)G(x,z)为x的辖域，x为指导变元,A中x的两次出现均为约束出现，y与z均为自由出现.闭式(封闭的公式):不含自由出现的个体变项的公式.,28,例3,1.x(x+1=0)量词的辖域是全

13、公式。x是约束变元 2.x(x+y+10)量词的辖域是全公式。x是约束变元,y是自由变元 3.x(x+y+1=0 y(x+y+10)的辖域是(x+y+10);的辖域是全公式，x是约束变元，第二个y是约束变元，第一个y是自由变元.,29,公式的解释与分类,给定公式 A=x(F(x)G(x)没有确定意义成真解释:个体域N,F(x):x2,G(x):x1 代入得A=x(x2x1)真命题成假解释:个体域N,F(x):x1,G(x):x2 代入得A=x(x1x2)假命题问:xF(x)xF(x)有成真解释吗？xF(x)xF(x)有成假解释吗？,30,解释,定义 解释I由下面4部分组成：(a)非空个体域DI

14、(b)DI中一些特定元素的集合(c)DI上特定函数集合(d)DI上特定谓词的集合 说明：在解释的定义中引进了元语言符号,如 等 被解释的公式A中的个体变项均取值于DI 若A中含个体常项ai，就解释成,31,解释(续),为第 i 个n元谓词.例如，表示第 2 个 3元谓词，它可能以 形式出现在解释中，公式A中若出现F2(x,y,z)就解释成,为第 i 个n元函数.例如，表示第一个二元函数,它出现在解释中，可能是=2xy等，一旦公式中出现f1(x,y)就解释成,出现 g1(x,y)就解释成,32,解释(续),例4 给定解释I 如下:(a)个体域 D=N(b)(c)(d)谓词说明下列公式在 I 下的

15、涵义,并讨论真值(1)xF(g(x,a),x),x(2x=x)假命题,(2)xy(F(f(x,a),y)F(f(y,a),x),xy(x+2=yy+2=x)假命题,33,例1(续),(3)xyzF(f(x,y),z),两点说明:5个小题都是闭式,在I下全是命题(3)与(5)说明，量词顺序不能随意改变,(5)xyzF(f(y,z),x),xyz(y+z=x)假命题,(4)xF(f(x,x),g(x,x),x(2x=x2)真命题,xyz(x+y=z)真命题,34,解释(续),被解释的公式不一定全部包含解释中的4部分.闭式在任何解释下都是命题，注意不是闭式的公式在某些解释下也可能是命题.,35,公式

16、的分类,永真式（逻辑有效式）：无成假赋值矛盾式（永假式）：无成真赋值可满足式：至少有一个成真赋值几点说明：永真式为可满足式，但反之不真判断公式是否为可满足式不是易事(不同于命题逻辑)某些特殊公式可以判断类型,36,代换实例(续),例5 证明下面公式既不是永真式，也不是矛盾式(1)x(F(x)G(x)(2)x(F(x)G(x)(3)xy(F(x)G(y)H(x,y)不难对每一个公式给出一个成假解释和一个成真解释,从而证明它们既不是永真式，也不是矛盾式.,37,代换实例,定义 设A0是含命题变项p1,p2,pn的命题公式，A1,A2,An是n个谓词公式，用Ai处处代替A0中的pi(1in)，所得公

17、式A称为A0的代换实例.例如:F(x)G(x),xF(x)yG(y)等都是pq的换实例，x(F(x)G(x)等不是 pq 的代换实例.定理 重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式.,38,代换实例(续),例6 判断下面公式类型(1)xF(x)(x y G(x,y)xF(x)(2)(x y G(x,y)xF(x)xF(x),39,3.2一阶逻辑等值演算,等值式基本等值式量词否定等值式量词辖域收缩与扩张等值式量词分配等值式,40,等值式与基本等值式,在一阶逻辑中，有些命题可以有不同的符号化形式。例如：没有不呼吸的人。取全总个体域时有下面两种不同的符号化形式：(1)x(F(x)G(x

18、)(2)x(F(x)G(x)F(x)：x是人，G(x)：x要呼吸,41,等值式与基本等值式,基本等值式:命题逻辑中16组基本等值式的代换实例如，xF(x)yG(y)xF(x)yG(y)(xF(x)yG(y)xF(x)yG(y)等 消去量词等值式 设D=a1,a2,an xA(x)A(a1)A(a2)A(an)xA(x)A(a1)A(a2)A(an),定义 若AB为逻辑有效式，则称A与B是等值的，记作 AB，并称AB为等值式.,42,实例,例 设个体域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(

19、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)xyF(x,y),(F(a,a)F(a,b)F(a,c)(F(b,a)F(b,b)F(b,c)(F(c,a)F(c,b)F(c,c),43,实例,解(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)xyL(x,y),(11)(01)1,解 yL(2,y)yL(3,y),(L(2,2)L(2,3

20、)(L(3,2)L(3,3),(10)(01)0,44,基本的等值式(续),量词否定等值式 设A(x)是含x自由出现的公式 xA(x)x A(x)xA(x)x A(x),45,基本等值式(续),量词辖域收缩与扩张等值式 设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),46,基本的等值式(续),量词分配等值式 x(A(x)B(x)x

21、A(x)xB(x)x(A(x)B(x)xA(x)xB(x)注意：对无分配律，对无分配律,47,基本的等值式(续),例 将下面命题用两种形式符号化(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)给出演算过程，并说明理由.,48,等值演算的三条原则,置换规则：若AB,则(B)(A)换名规则:将量词辖域中出现的某个约束变项的所有出现及对应的指导变项，改成该量词辖域中未曾出现过的个体变项符号，公式中其

22、余部分不变，则所得公式与原来的公式等值.代替规则:对某自由出现的个体变项用与原公式中所有个体变项符号不同的符号去代替，则所得公式与原来的公式等值.,49,换名规则与代替规则,例(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)(代替规则),50,例 给定解释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

23、.L(2,2)=L(3,3)=1,L(2,3)=L(3,2)=0.F(x)为：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)yxL(x,y),51,前束范式,例如，xy(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(1ik)为或，B为不含量词的公式.,52,公式的前束范式,定理（前束范式存在定理）一阶逻辑

24、中的任何公式都存在与之等值的前束范式 注意:公式的前束范式不惟一 求公式的前束范式的方法:利用重要等值式、置换规则、换名规则、代替规则进行等值演算.,53,公式的前束范式(续),例 求下列公式的前束范式(1)x(M(x)F(x)解 x(M(x)F(x)x(M(x)F(x)（量词否定等值式）x(M(x)F(x)两步结果都是前束范式，说明前束范式不惟一.,54,例(续),(2)xF(x)xG(x)解 xF(x)xG(x)xF(x)xG(x)（量词否定等值式）x(F(x)G(x)（量词分配等值式）另有一种形式 xF(x)xG(x)xF(x)xG(x)（量词否定等值式）xF(x)yG(y)(换名规则)

25、xy(F(x)G(y)(量词辖域扩张)两种形式是等值的,55,例(续),(3)xF(x)xG(x)解 xF(x)xG(x)xF(x)xG(x)（量词否定等值式）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)（换名规则）zy(F(z)(G(x,y)H(y)（为什么？）,56,例(续),或 xF(x)y(G(z,y)H(y)（代替规则）xy(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

26、(x,z)x(F(x,u)y(G(x,y)H(x,z)xy(F(x,u)G(x,y)H(x,z)注意：x与y不能颠倒,57,一阶逻辑推理理论,推理的形式结构判断推理是否正确的方法重要的推理定律推理规则构造证明附加前提证明法,58,推理,推理的形式结构有两种：第一种 A1A2AkB(*)第二种 前提：A1，A2，Ak 结论：B其中 A1,A2,Ak,B为一阶逻辑公式.若(*)为永真式,则称推理正确,否则称推理不正确.,59,重要的推理定律,第一组 命题逻辑推理定律代换实例 如 xF(x)yG(y)xF(x)为化简律代换实例.第二组 由基本等值式生成 如 由 xA(x)xA(x)生成 xA(x)x

27、A(x),xA(x)xA(x),第三组 xA(x)xB(x)x(A(x)B(x)x(A(x)B(x)xA(x)xB(x),60,推理规则,(1)前提引入规则(2)结论引入规则(3)置换规则(4)假言推理规则(5)附加规则(6)化简规则(7)拒取式规则(8)假言三段论规则(9)析取三段论规则(10)构造性二难推理规则(11)合取引入规则,61,推理规则(续),(12)全称量词消去规则（简记为UI规则或UI）两式成立的条件是：在第一式中，取代x的y应为任意的不在A(x)中约束出现的个体变项.在第二式中，c为任意个体常项.用y或c去取代A(x)中的自由出现的x时，一定要在x自由出现的一切地方进行取代

28、.,62,推理规则(续),(13)全称量词引入规则（简记为UG规则或UG）该式成立的条件是：无论A(y)中自由出现的个体变项y取何值，A(y)应该均为真.取代自由出现的y的x，也不能在A(y)中约束出现.,63,推理规则(续),(14)存在量词引入规则（简记为EG规则或EG）该式成立的条件是：c是使A为真的特定个体常项.取代c的x不能在A(c)中出现过.,64,推理规则(续),(15)存在量词消去规则（简记为EI规则或EI）该式成立的条件是：c是使A为真的特定的个体常项.c不在A(x)中出现.若A(x)中除自由出现的x外，还有其他自由出现的个体变项，此规则不能使用.,65,构造推理证明,例1

29、证明苏格拉底三段论:“人都是要死的,苏格拉底是人，所以苏格拉底是要死的.”令 F(x):x是人,G(x):x是要死的,a:苏格拉底 前提：x(F(x)G(x)，F(a)结论：G(a)证明：F(a)前提引入 x(F(x)G(x)前提引入 F(a)G(a)UI G(a)假言推理注意：使用UI时，用a取代x.,66,构造推理证明(续),例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),67,例2(续),证明：x(F(x)H(x)前提引入 F(y)H

30、(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)UG,68,构造推理证明(续),例3 构造下述推理证明 前提：x(F(x)G(x)，xF(x)结论：xG(x)证明：xF(x)前提引入 x(F(x)G(x)前提引入 F(c)EI F(c)G(c)UI G(c)假言推理 xG(x)EG注意：必须先消存在量词,69,构造推理证明(续),例4 构造下述推理证明 前提：xF(x)xG(x)结论：x(F(x)G(x)证明：xF(x)xG(x)前提引入 xy(F(x)G(y)置换 x(F(x)G(z)UI F(z)G(z)UI x(F(x)G(x)UG说明:不能对xF(x)xG(x)消量词,因为它不是前束范式.对此题不能用附加前提证明法.,70,构造推理证明(续),例5 构造下述推理证明 前提：x(F(x)G(x)结论：xF(x)xG(x)证明：xF(x)附加前提引入 F(y)UI x(F(x)G(x)前提引入 F(y)G(y)UI G(y)假言推理 xG(x)UG本题可以使用附加前提证明法,