一阶逻辑公式及解释.ppt

第四章 一阶逻辑基本概念,第1节 一阶逻辑的符号化,第2节 一阶逻辑公式及解释,一、一阶语言,二、自由与约束,第2节 一阶逻辑公式及解释,三、闭公式,四、一阶公式的解释,五、一阶公式的分类,一阶语言 的字母表定义如下:,(1) 个体常项: a, b, c, , ai , bi , ci ，i1 (2) 个体变项: x, y, z, , xi, yi, zi， i1 (3) 函数符号: f, g, h, , fi, gi, hi， i1 (4) 谓词符号: F, G, H,Fi , Gi , Hi ，i1 (5) 量词符号: (6) 联结词符号: , , (7) 括号与逗号: ( , ), ,定义4.1,一、一阶语言,定义4.2 的项的定义如下:,(1) 个体常项和个体变项是项. (2) 若 f (x1, x2, , xn) 是任意的 n 元函数, t1,t2,tn是任意的 n 个项， 则 f (t1, t2, , tn) 是项. (3) 所有的项都是有限次使用(1)，(2)得到的.,例4.5中的1元谓词F(x)，G(x)，2元谓词 H(x,y)， L(x,y) 等都是原子公式,设 R(x1 , x2 , ,xn) 是的任意n元谓词, t1, t2, , tn 是 的任意的 n 个项，则称 R(t1, t2, , tn)是 的原子公式.,定义4.3,定义4.4 的合式公式定义如下:,(1) 原子公式是合式公式.,(2) 若A是合式公式，则(A)也是合式公式.,(3) 若A，B是合式公式，则(AB)，(AB)，(AB)，(AB) 也是合式公式.,(5) 只有有限次的应用(1)(4)构成的符号串才是 合式公式.,(4) 若A是合式公式，则 也是合式公式.,合式公式也称为谓词公式，简称公式 .,在定义4.4中出现的字母A, B是代表任意公式的 元语言符号. 为方便起见, 公式(A), (AB), 中 的最外层括号可以省去，使其变成A, AB，. (4.1)(4.21)都是 中的公式.,因为本书只引进一种一阶语言 ，下文的讨论 都是在 中，因而一般不再提及 .,下面讨论一阶公式的一些性质.,在公式 和 中，称x为指导变元， A为相应量词的辖域. 在 和 的辖域中, x 的 所有出现都称为约束出现. A中不是约束出现的 其他变项均称为是自由出现的.,定义4.5,二、自由与约束,例 4.6 指出下列各公式中的指导变元，各量词 的辖域，自由出现以及约束出现的个体变项:,(2)公式中含有两个量词，前件上的量词 的指导变元为x， 的辖域 A=(F(x)G(y)， 其中x是约束出现的，y是自由出现的.,(1) x是指导变元. 量词 的辖域 A=( F(x,y) G(x,z)， 在A中，x是约束出现的. 而且约束出现两次， y 和 z 均为自由出现的，而且各自由出现一次.,解：,后件中的量词 的指导变元为 y， 的辖域为 (H(x)L(x,y,z)， 其中y是约束出现的，x, z 均为自由出现的.,在整个公式中，x 约束出现一次，自由出现2次，y自由出现一次，约束出现一次，z 只自由出现一次.,则 x1 A( x1, x2, , xn ) 是含有 x2 , x3, xn 自由出现的 公式，可记为 A1( x2, , xn ).,类似的, x2x1A( x1, x2, , xn ) 可记为A2( x3, x4, , xn ) ， xn-1xn-2 x1A(x1, x2, , xn)中只含有xn是自由出现的 个体变项，可以记为 An-1( xn)，,而xn x1 A( x1, x2, , xn )已经没有自由出现的个体 变项了.,为方便起见，本书用 A( x1, x2, , xn )表示含 x1, x2, xn 自由出现的公式，并用表示任意的量词 ( 或 ).,可将例4.6(1)中的公式 简记为A( y, z )，这表明该公式含有自由出现的个 体变项 y，z. 而 y A( y, z )中只含有z为自由出现的公式， z yA( y, z )中已经没有自由出现的个体变项了， 此时的公式为 z y x(F( x, y )G( x, y, z ) (4.24),设A是任意的公式, 若A中不含有自由出现 的个体变项，则称A为封闭的公式，简称闭式.,定义4.6,三、闭公式,易知（4.1）（4.21）以及（4.24）都是闭式，而（4.22）和（4.23）则不是闭式。,要想使含有 r (r1)个自由出现个体变项的公式变成闭式，至少要加上 r 个量词.,四、一阶公式的解释,(1) x(F(x)G(x) (4.25) (2) x y(F(x)F(y)G(x,y) H( f (x,y),g(x,y) (4.26),例4.7 将下列两个公式中的变项指定成常项 使其成为命题:,(1) 指定个体变项的变化范围，并且指定谓词F，G 的含义，下面给出两种指定法:,解:,(a) 令个体域 D1为全总个体域，F(x)为x是人， G(x)为x是黄种人，则(4.25)表达的命题为 “所有人都是黄种人”， 这是假命题.,(b) 令个体域D2为实数集合R，F(x)为x是自然数， G(x)为x是整数，则(4.25)表达的命题为 “自然数都是整数” , 这是真命题.,(2) (4.26) 中含有两个2元函数变项，两个1元谓词 变项，两个2元谓词变项. 指定个体域为全总个体域, F(x)为x是实数, G(x,y) 为xy，H(x,y)为xy，f (x,y)=x2+y2, g(x,y)=2xy，,则(4.26)表达的命题为 “对于任意的x，y，若x与y都是实数，且xy， 则x2+y22xy”. 这是真命题. 若H(x,y)改为 xy，则所得命题就为 假命题了.,在例4.7中所谈的对各种变项的指定也可以称为 对它们的解释.,在本例中是给出公式后再对它们进行解释，也 可以先给出解释，再用这个解释去解释各种公式. 由以上的讨论不难看出，一个解释不外乎指定 个体域、个体域中一些特定的元素、特定的函数和 谓词等部分 .,定义4.7,(a) 非空个体域 DI (b) DI 中一些特定元素的集合 (c) DI 上特定函数集合 (d) DI 上特定谓词的集合,的解释I由下面4部分组成:,2. 被解释的公式 A中的个体变项均取值于D1 .,3. 若A中含有个体常项ai，就解释成,1. 在解释的定义中引进了几个元语言符号， 如,说 明,4. 为第 i 个n元函数.,例如，i=1，n=2时， 表示第一个二元函数， 它出现在解释中，可能是 等，,一旦公式中出现 f1(x, y) 就解释成 出现 g1(x, y)就解释成,5. 为第 i 个n元谓词.,例如，i=1，n=2时， 表示第二个三元谓词， 它可能以 的形式出现在解释中， 公式 A 若出现 F2( x, y, z) 就解释成,6. 被解释的公式不一定全部包含解释中的四部分.,(a) 个体域 D=N ( N为自然数集合),给定解释 I 如下:,例4.8,(b) =0,(c) ( x, y )=x+y , ( x, y )=x y,(d) ( x, y ) 为 x = y .,在 I 下，下列哪些公式为真? 哪些为假?,(1) F ( f ( x, y ), g ( x, y ) (2) F ( f ( x, a ), y )F ( g( x, y ), z) (3) F( g ( x, y ), g( y, z ) ),(4) x F ( g( x, y ), z (5) x F( g( x, a), x )F ( x, y ) (6) x F( g( x, a), x ) (7) x y (F ( f ( x, a), y )F( f ( y, a), x) ) (8) x y z F( f ( x, y ), z ) (9) x F( f ( x, x ), g ( x, x ),(1) 在I下，(1)中公式被解释成 “ x + y = x y ”， 这不是命题. (2) 公式被解释成 “( x + 0 = y )( x y = z )”， 这也不是命题. (3) 公式被解释成 “ x y y z ”. 不是命题. (4) 公式被解释成 “ x( x z y z )”. 不是命题. (5) 公式被解释成“ x ( x 0 = x)( x = y )”. 由于蕴涵式的前件为假，所以被解释的公式为真.,解 答,(6) 公式被解释成 “ x ( x 0 = x ) ”. 假命题. (7) 公式被解释成“ x y(x+0=y)(y+0=x)”. 真命题. (8) 公式被解释成“ x y z ( x + y =z )”. 真命题. (9) 公式被解释成“ x ( x + x = xx )”. 真命题.,解 答,从例4.8可以看出，闭式在给定的解释中都变成了命题(见公式(6)(8)，其实,定理4.1 封闭的公式在任何解释下都变成命题.,设A为一个公式，若A在任何解释下 均为真，则称 A为永真式(或称逻辑有效式).,定义4.8,五、一阶公式的分类,若A在任何解释下均为假，则称A为矛盾式(或 永假式).,若至少存在一个解释使A为真，则称A为可满足式.,从定义可知，永真式一定是可满足式，但可满足不一定是永真式。,设A0是含有命题变项 p1, p2, , pn 的命题 公式, A1, A2, An 是n个谓词公式, 用Ai(1in) 处处代替A0中的 pi，所得公式 A 称为A0的代换实例.,定义4.9,例如，F (x)G (x)， xF(x)yG(y)等都是 pq 的代换实例，而 x( F(x)G(x) 不是 pq 的代换实例.,重言式的代换实例都是永真式， 矛盾式的代换实例都是矛盾式.,定理4.2,例4.9 判断下列公式中，哪些是永真式，哪些是 矛盾式?,(1) x(F(x)G(x) (2) xF (x)( x yG (x，y) xF (x) (3) ( xF (x) yG (y) yG (y),解： 为方便起见，用A，B，C分别记(1)，(2)，(3) 中的公式.,(1) 取解释 I1: 个体域为实数集合R， F(x):x是整 数，G(x):x是有理数. 在I1下A为真，因而A不是矛盾式.,取解释I2: 个体域仍然为R, F(x): x是无理数, G(x): x能表示成分数.,在I2下A为假，所以A不是永真式. 故A是非永真式的可满足式.,(2) 易知B是命题公式p(q p)的代换实例， 而该命题公式是重言式，所以B是永真式.,(3) C是命题公式(p q) q的代换实例， 而该命题公式是矛盾式，所以C是矛盾式。,有些公式即使是重言式或矛盾式的代换实例，也不容易一眼就能看出来，特别是有些公式，它们不是重言式和矛盾式的代换实例，判断它们是否为永真式或矛盾式更不容易，但有些简单的公式还是可以根据定义判断的.,(1) xF(x) xF (x) (2) x yF (x，y) x yF (x, y) (3) x(F(x)G(x) yG (y),例4.10 判断下列公式的类型.,(1) 设 I 为任意一个解释，个体域为D. 若存在x0D，使得F(x0)为假，则 xF (x)为假， 所以A 的前件为假，故A为真. 若对于任意 xD ， F (x)均为真， 则 xF (x)， xF (x)都为真