离散数学 第2章 一阶逻辑

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

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

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

3、谓词, n2): 表示个体词之间的关系如 L(x,y)： x与y有关系L， L(x,y)： x比y高2厘米注意：多元谓词中，个体变项的顺序不能随意改动 5个体变项和谓词的联合体，F(x),L(x,y)，也称为谓词n元谓词 L(x1, x2, xn)可看作一个函数，定义域为个体变项的 个体域，值域为0,1 n元谓词 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元谓词: 不含个体变项的谓词,

4、 如L(a, b)如L的意义明确，则0元谓词都是命题6一阶逻辑中命题符号化 例1 用0元谓词将命题符号化要求：先将它们在命题逻辑中符号化，再在一阶逻辑中符号化(1) 墨西哥位于南美洲在命题逻辑中, 设 p: 墨西哥位于南美洲符号化为 p, 这是真命题 在一阶逻辑中, 设a：墨西哥，F(x)：x位于南美洲符号化为F(a)7例1(续)(2) 是无理数仅当 是有理数在命题逻辑中, 设 p： 是无理数，q： 是有理数. 符号化为 p q, 这是假命题 在一阶逻辑中, 设F(x): x是无理数, G(x): x是有理数符号化为(3) 如果23，则33，q：3y，G(x,y)：xyx(F(x)y(G(y)

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

6、汽车快 x( F(x) G(x)其中F(x)：x是人， G(x)：x呼吸或者： x( F(x) G(x) x( F(x) G(x)其中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) )15例：在一界逻辑中命题符号化 一切人都不一样高 每个自然数都有后继数 有的自然数无先驱数 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

7、) 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(x,y)或者： x( F(x) L(x) ) ，L(x) ：x有先驱数162.2 一阶逻辑公式及解释 字母表 合式公式(简称公式) 个体变项的自由出现和约束出现 解释 永真式（逻辑有效式） 矛盾式（永假式） 可满足式 17字母表 定义 字母表包含下述符号：(1) 个体常项：a, b, c, , ai, bi, ci, , i 1(2) 个体变项：x, y, z, , xi, yi,

8、zi, , i 1 (3) 函数符号：f, g, h, , fi, gi, hi, , i 1(4) 谓词符号：F, G, H, , Fi, Gi, Hi, , i 1(5) 量词符号：, (6) 联结词符号：, , , , (7) 括号与逗号：( , ), ， 18项 定义 项的定义如下：(1) 个体常项和个体变项是项.(2) 若(x1, x2, , xn)是任意的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,

9、y)=a+ (x-y)是项其实, 个体常项、变项是项，由它们构成的n元函数 和复合函数还是项19原子公式 定义 设R(x1, x2, , xn)是任意的n元谓词，t1,t2, tn 是任意的n个项，则称R(t1, t2, , tn)是原子公式. 其实，原子公式是由项组成的n元谓词. 例如，F(x,y), F(f(x1,x2),g(x3,x4)等均为原子公式 20合式公式 定义 合式公式（简称公式）定义如下：(1) 原子公式是合式公式. (2) 若A是合式公式，则 (A)也是合式公式(3) 若A, B是合式公式，则(AB), (AB), (AB), (AB)也是合式公式(4) 若A是合式公式，则

10、xA, xA也是合式公式(5) 只有有限次地应用(1)(4)形成的符号串才是合式公式(谓词公式).21个体变项的自由出现与约束出现 定义 在公式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均为自由出现. 闭式: 不含自由出现的个体变项的公式.22例1：x(F(x) y H(x,y) )$y H(x,y)中， y 为指导变项， 的辖域为H(x,y)

11、，其中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为自由出现的在此公式中， x 为约束出现的，y为约束出现的，又为自由出 现的. z为自由出现的.23换名规则

12、 将量词辖域中出现的某个约束出现的个体变项及对应的指 导变项，改成另一个辖域中未出现过的个体变项符号，公式中的其余部 分不变。例：xF(x) G(x,y)换名规则：zF(z) G(x,y)代替规则 将某个自由出现的个体变项及对应的指导变项，改成公式 中未出现过的个体变项符号，处处代替。代替规则：xF(x) G(z,y)用处：不存在既是约束出现，又是自由出现的个体变项24公式的解释与分类 给定公式 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(x1x

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

14、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 真命题27例 给定解释：(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 , 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 不是命题28例1 给定解释I