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

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

1、1,第2章 一阶逻辑,一阶逻辑基本概念、命题符号化一阶逻辑公式、解释及分类一阶逻辑等值式、前束范式一阶逻辑推理理论,2,例“苏格拉底三段论”人都是要死的.(p)苏格拉底是人.(q)所以苏格拉底是要死的.(r)在命题逻辑中，推理的形式结构：（p q）r(不是重言式)原因：命题逻辑中，p、q、r之间的内在联系没有反映出来.方法：反映p、q、r内在联系，对简单命题进一步分析.,3,2.1 一阶逻辑基本概念,个体词 谓词 量词 一阶逻辑中命题符号化,4,基本概念个体词、谓词、量词,个体词（个体）:所研究对象中可以独立存在的具体或抽象的客体，它可以是一个具体的事物，也可以是一个抽象的概念.表示主语的词（

2、名词或代词）：苏格拉底，2，黑板，自然数，思想，定理.个体常项：具体的或特定的个体词，用a,b,c表示 个体变项：抽象的或泛指的个体词，用x,y,z表示 个体域:个体变项的取值范围 有限个体域，如a,b,c,1,2 无限个体域，如N,Z,R,全总个体域:宇宙间一切事物组成,5,基本概念(续),谓词:表示个体词的性质或相互之间关系的词 谓词常项：表示具体性质或关系的谓词 F:是人，F(a)：a是人 G：是自然数，F(2)：2是自然数 谓词变项：表示抽象的或泛指的谓词 F:具有性质F，F(x)：x具有性质F 元数：谓词中所包含的个体词数 一元谓词:表示事物的性质 多元谓词(n元谓词,n2):表示个

3、体词之间的关系 如 L(x,y)：x与y有关系L，L(x,y)：x比y高2厘米 注意：多元谓词中，个体变项的顺序不能随意改动,6,个体变项和谓词的联合体，F(x),L(x,y)，也称为谓词 n元谓词 L(x1,x2,xn)可看作一个函数，定义域为个体变项的个体域，值域为0,1n元谓词 L(x1,x2,xn)的真值不确定，不是命题,如：L(x,y)如果L(x,y)表示“x小于y”，谓词部分已经是常项，但 还不是命题.考虑L(2,3)和L(3,2)L(x1,x2,xn)是命题：只有当L是常项，x1,x2,xn是个体常项0元谓词:不含个体变项的谓词,如L(a,b)如L的意义明确，则0元谓词都是命题,

4、7,一阶逻辑中命题符号化,例1 用0元谓词将命题符号化 要求：先将它们在命题逻辑中符号化，再在一阶 逻辑中符号化(1)墨西哥位于南美洲 在命题逻辑中,设 p:墨西哥位于南美洲 符号化为 p,这是真命题 在一阶逻辑中,设a：墨西哥，F(x)：x位于南美洲 符号化为F(a),8,例1(续),(2)是无理数仅当 是有理数 在命题逻辑中,设 p：是无理数，q：是有理数.符号化为 p q,这是假命题 在一阶逻辑中,设F(x):x是无理数,G(x):x是有理 数符号化为(3)如果23，则33，q：3y，G(x,y)：xy,符号化为 F(2,3)G(3,4),9,例1(续)（4）如果张明比李民高，李民比赵亮

5、高，则张明比赵亮高.在命题逻辑中,设 p：张明比李民高，q：李民比赵亮高,r:张明比赵亮高.符号化为：p q r在一阶逻辑中,设 F(x,y)：x比y高 a:张明，b:李民，c:赵亮符号化为：F(a,b)F(b,c)F(a,c),10,基本概念(续)量词:表示数量的词例如（1）所有的人都要死的；（2）有的人活一百岁以上；全称量词:表示任意的,所有的,一切的等 x 表示对个体域中所有的个体，x F(x)表示个体域中所有的个体都有性质F.x F(x)，其中F(x)：x是要死的，个体域为人类集合 存在量词:表示存在着,有的,有一个，至少有一个等 x 表示存在个体域中的个体，x F(x)表示存在着个体

6、域中的个体具有有性质F x G(x)，其中G(x)：x活一百岁以上，个体域为人类集合,11,如果个体域D为全总个体域，则x F(x)，其中F(x)：x是要死的，表示宇宙间的一切事物都要死的.x G(x)，其中G(x)：x活一百岁以上，表示宇宙间的一切事物中存在活一百岁以上的.特性谓词：M(x):x是人符号化为：（1）x（M(x)F(x)）（2）x（M(x)G(x)）考虑：（1）x（M(x)F(x)）（2）x（M(x)G(x)）,12,一阶逻辑中命题符号化(续),例2 在一阶逻辑中将下面命题符号化(1)人都爱美;(2)有人用左手写字 分别取(a)D为人类集合,(b)D为全总个体域.解：(a)(1

7、)设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)这是两个基本公式,注意这两个基本公式的使用.,13,一阶逻辑中命题符号化(续),例3 在一阶逻辑中将下面命题符号化(1)正数都大于负数(2)有的无理数大于有的有理数解 注意:题目中没给个体域,一律用全总个体域(1)令F(x):x为正数,G(y):y为负数,L(x,y):xy x(F(x)y(G(y)L(x,y)或 xy(F(x)G(y)L(x,y)两者等值(2)令F(x):x是无理数,G(y):y是有

8、理数,L(x,y)：xy x(F(x)y(G(y)L(x,y)或 xy(F(x)G(y)L(x,y)两者等值,14,一阶逻辑中命题符号化(续),几点注意：1元谓词与多元谓词的区分 无特别要求，用全总个体域 量词顺序一般不要随便颠倒 例：对任意x，存在着y，使得x+y=5.个体域为实数集.符号化为：x y H（x,y),其中H（x,y):x+y=5 考虑 y x H（x,y)否定式的使用,15,例：在一界逻辑中命题符号化 没有不呼吸的人 不是所有的人都喜欢吃糖 不是所有的火车都比所有的汽车快 x(F(x)G(x)其中F(x)：x是人，G(x)：x呼吸 或者：x(F(x)G(x)x(F(x)G(x

9、)其中F(x)：x是人，G(x)：x喜欢吃糖 或者：x(F(x)G(x)x(F(x)y(G(y)H(x,y)或者：x(F(x)y(G(y)H(x,y),16,例：在一界逻辑中命题符号化 一切人都不一样高 每个自然数都有后继数 有的自然数无先驱数 x y(F(x)F(y)G(x,y)H(x,y)其中F(x)：x是人，G(x,y):x和y不是同一个人，H(x,y)：x和y一样高 或者：x y(F(x)F(y)G(x,y)H(x,y)x(F(x)y(G(y)H(x,y)其中F(x)：x是自然数，H(x,y)：y是x的后继数 或者：x(F(x)L(x)，L(x)：x有后继数 x(F(x)y(G(y)H

10、(x,y)或者：x(F(x)L(x)，L(x)：x有先驱数,17,2.2 一阶逻辑公式及解释,字母表合式公式(简称公式)个体变项的自由出现和约束出现解释永真式（逻辑有效式）矛盾式（永假式）可满足式,18,字母表,定义 字母表包含下述符号：(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)谓词符号：F,G,H,Fi,Gi,Hi,i 1(5)量词符号：,(6)联结词符号：,(7)括号与逗号：(,),，,19,项,定义 项的定义如下：(1)个体常项和个体变项是项.(2)若(x1,x2,xn

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

12、：(1)原子公式是合式公式.(2)若A是合式公式，则(A)也是合式公式(3)若A,B是合式公式，则(AB),(AB),(AB),(AB)也是合式公式(4)若A是合式公式，则xA,xA也是合式公式(5)只有有限次地应用(1)(4)形成的符号串 才是合式公式(谓词公式).,22,个体变项的自由出现与约束出现,定义 在公式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均

13、为自由出现.闭式:不含自由出现的个体变项的公式.,23,例1：x(F(x)y H(x,y)y H(x,y)中，y 为指导变项，的辖域为H(x,y)，其中y 为约束出现的，x为自由出现的.在整个合式公式中，x为指导变项，的辖域为(F(x)y H(x,y)，其中x与y 都是约束出现的，x约束出现2次，y约束出现1次.例2：x y(R(x,y)L(y,z)x H(x,y)x y(R(x,y)L(y,z)中，x,y都是指导变项，辖域为(R(x,y)L(y,z)，x与y 都是约束出现的，z为自由出现的.x H(x,y)中，x 为指导变项，的辖域为H(x,y)，其中x 为约束出现的，y为自由出现的在此公式

14、中，x 为约束出现的，y为约束出现的，又为自由出现的.z为自由出现的.,24,换名规则 将量词辖域中出现的某个约束出现的个体变项及对应的指导变项，改成另一个辖域中未出现过的个体变项符号，公式中的其余部分不变。例：xF(x)G(x,y)换名规则：zF(z)G(x,y)代替规则 将某个自由出现的个体变项及对应的指导变项，改成公式中未出现过的个体变项符号，处处代替。代替规则：xF(x)G(z,y)用处：不存在既是约束出现，又是自由出现的个体变项,25,公式的解释与分类,给定公式 A=x(F(x)G(x)成真解释:个体域N,F(x):x2,G(x):x1 代入得A=x(x2x1)真命题成假解释:个体域

15、N,F(x):x1,G(x):x2 代入得A=x(x1x2)假命题问:xF(x)xF(x)有成真解释吗？xF(x)xF(x)有成假解释吗？,26,解释,定义 解释I由下面4部分组成：(a)非空个体域DI(b)DI中一些特定元素(c)DI上特定函数集合(d)DI上特定谓词的集合 说明：1 将公式的个体常项用I的特定常项代替，函数和谓词用I的特定函数和 谓词代替2 被解释的公式不一定全部包含解释中的4部分.3 闭式在任何解释下都是命题，4 不是闭式的公式在某些解释下也可能是命题.,27,例 给定解释I：(a)DI2,3(b)DI中特定元素a=2(c)DI上特定函数f(x):f(2)=3,f(3)=

16、2(d)DI上特定谓词F(x):F(2)=0,F(3)=1，G(x,y)为G(i,j)=1,其中i,j=2,3 1）x（F(x)G(x,a)（F(2)G(2,2)（F(3)G(3,2)(01)(1 1)0 假命题2)x(F(f(x)G(x,f(x)(F(f(2)G(2,f(2)(F(f(3)G(3,f(3)(F(3)G(2,3)(F(2)G(3,2)(1 1)(0 1)1 真命题,28,例 给定解释：(a)个体域为自然数集合DN(b)DN中特定元素a=0(c)DN上特定函数f(x,y)=x+y,g(x,y)=x.y(d)DN上特定谓词F(x,y)为xy 1）xF(g(x,a),x)xF(x.0

17、,x)x(x.0=x)假命题2)x y(F(f(x,a),y)F(f(y,a),x)x y(F(0+x,y)F(y+0,x)x y(0+x=y)(y+0=x)真命题 3)x y F(f(x,y),g(x,y)x y F(x+y,x.y)x y(x+y=x.y)假命题 4)F(f(x,y),f(y,z)F(x+y,y+z)x+y=y+z 不是命题,29,例1 给定解释I 如下:(a)个体域 D=N(b)(c)(d)谓词说明下列公式在 I 下的涵义,并讨论真值(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)

18、假命题,30,例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)真命题,31,公式的分类,永真式（逻辑有效式）：公式在任何解释下都是真的，即无成假赋值矛盾式（永假式）：公式在任何解释下都是假的，即无成真赋值可满足式：至少存在一个解释使公式成真说明：永真式为可满足式，但反之不真某些代换实例可判公式类型,32,代换实例,定义 设A0是含命题变项p1,p2,pn的命题公式，

19、A1,A2,An是n个谓词公式，用Ai处处代替A0中的pi(1in)，所得公式A称为A0的代换实例.例如:F(x)G(x),xF(x)yG(y)等都是pq的换实例，x(F(x)G(x)等不是 pq 的代换实例.定理 命题公式中的重言式的代换实例，在谓词公 式中都是永真式，命题公式中的矛盾式的代换实例，在谓词公 式中都是矛盾式.,33,代换实例(续),例2 判断下面公式的类型(1)xF(x)x F(x)解：设任意解释Ia)如果存在a 使得F(a)为假，则xF(x)为假，所以xF(x)x F(x)为真b)如果对任意 x使得F(x)为真，则xF(x)为真，而且x F(x)也为真，所以xF(x)x F(x)为真因此，公式为永真式.,34,(2)xF(x)(x y G(x,y)xF(x)(3)xF(x)(xF(x)y G(y)(4)(F(x,y)R(x,y)R(x,y)(5)xy F(x,y)x y F(x,y)解：解释I1,个体域为自然数集合N，F(x,y):x等于y 此时，前件为真，后件为假 解释I2,个体域为自然数集合N，F(x,y):x小于等于y 此时，前件为真，后件为真 因此，公式为非永真式的可满足式,