22 一阶逻辑公式及解释.docx

授课时间 第四周 第 1 次课授课章节2.2 —阶逻辑公式及解释任课教师及职称唐新华讲师教学方法与手段板书和电子课件结合课时安排2课时使用教材和主要参考书1、 教材：耿素云等，离散数学，清华大学出版社，20082. 参考书左孝琳、李为槛、刘永才，离散数学(上海科技文献版)2006教学与目的要求：深刻理解永真式、矛盾式、可满足式的概念及相互之间的关系；记住闭式的性质并 能应用它；对于给定的解释会判断公式的真值，或判定真值不确定(即仍不是命题)教学重点、难点：教学重点：合式公式、一阶逻辑公式的类型，闭式的主要特征 教学难点：一阶逻辑公式的类型，闭式的主要特征教学内容：2.2 一阶逻辑公式及解释一、 本节主要内容字母表合式公式(简称公式)个体变项的自由出现和约束出现解释永真式(逻辑有效式) 矛盾式(永假式)可满足式二、 教学内容字母表定义字母表包含下述符号：(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) 量词符号：V, 3(6) 联结词符号：「，A, V, T, J(7) 括号与逗号：(,), ，项定义项的定义如下：(1) 个体常项和个体变项是项.(2) 若9(x1, x2,…，xn)是任意的 n 元函数，tl,t2,...,tn 是任意的n个项，则9(t1, t2,…，tn)是项.(3) 所有的项都是有限次使用(1),⑵得到的.例：a，b，x, y，f(x,y)=x+y, g(x,y)=x-y 都是项f(a, g(x,y))=a+ (x-y)是项其实，个体常项、变项是项，由它们构成的n元函数 和复合函数还是项 原子公式定义 设R(xl, x2,…，xn)是任意的n元谓词，tl,t2,..., tn 是任意的n个项，则称R(t1, t2,…，tn)是原子公式.其实，原子公式是由项组成的n元谓词.例如，F(x,y), F(f(x1,x2),g(x3,x4))等均为原子公式 合式公式定义 合式公式(简称公式)定义如下：(1) 原子公式是合式公式.(2) 若A是合式公式，则(「A)也是合式公式(3) 若 A, B 是合式公式，则(AaB), (AvB), (AtB),(AoB)也是合式公式(4) 若A是合式公式，贝l」VxA, 3xA也是合式公式(5) 只有有限次地应用(1)〜⑷形成的符号串才是合式公式(谓词公式).个体变项的自由出现与约束出现 定义 在公式VxA和3xA中，称x为指导变元，A为相 应量词的辖域.在Vx和mx的辖域中，x的所有出现都 称为约束出现，A中不是约束出现的其他变项均称 为是自由出现的.例如，在公式 Vx(F(x,y)—G(x,z))中，A=(F(x,y)—G(x,z))%Vx 的辖域，x为指导变项,A中x的两次出现均为约束出现， y与z均为自由出现.闭式：不含自由出现的个体变项的公式.例 1: Vx(F(x)T m y H(x,y))m y H(x,y)中，y为指导变项，m的辖域为H(x,y)，其中y为约束出现的，x为自 由出现的.在整个合式公式中，x为指导变项，V的辖域为(F(x)—m yH(x,y))，其中x与y都是 约束出现的，x约束出现2次，y约束出现1次.例 2： Vx Vy(R(x,y) v L(y,z) ) a m x H(x,y)Vx Vy(R(x,y) v L(y,z))中，x,y都是指导变项，辖域为(R(x,y) v L(y,z) )， x与y都是约束 出现的，z为自由出现的.m xH(x,y)中，x为指导变项，m的辖域为H(x,y)，其中x为约束出现的，y为自由出现的在此公式中，x为约束出现的，y为约束出现的，又为自由出现的.z为自由出现的.换名规则 将量词辖域中出现的某个约束出现的个体变项及对应的指导变项，改成另一个辖域中未出现过的个体变项符号，公式中的其余部分不变。

例：VxF(x) a G(x,y)换名规则：VzF(z) a G(x,y)代替规则 将某个自由出现的个体变项及对应的指导变项，改成公式中未出现过的个体变项符号，处处代替代替规则：VxF(x) a G(z,y)用处：不存在既是约束出现，又是自由出现的个体变项公式的解释与分类给定公式 A=Vx(F(x)tG(x))成真解释：个体域N, F(x): x>2, G(x): x>1代入得A=Vx(x>2tx>1) 真命题成假解释：个体域N, F(x): x>1, G(x): x>2 代入得A=Vx(x>1tx>2) 假命题问：VxF(x)a3x^F(x)有成真解释吗？ 3xF(x)vVx^F(x)有成假解释吗？ 解释 定义 解释I由下面4部分组成：(a) 非空个体域DI(b) DI中一些特定元素(c) DI上特定函数集合(d) DI上特定谓词的集合说明：1将公式的个体常项用I的特定常项代替，函数和谓词用I的特定函数和 谓词代替 2被解释的公式不一定全部包含解释中的4部分.3闭式在任何解释下都是命题，4不是闭式的公式在某些解释下也可能是命题.例给定解释I：(a) D/= {2,3}(b) D］中特定元素a=2(c) DI 上特定函数f(x) :f(2)=3,f(3)=2(d) DI 上特定谓词 F(x) :F(2)=0, F(3)=1，G(x，y)为 G(IJ)=1,其中 i,j=2,31) Vx (F(x)a G(x,a))o (F(2)a G(2,2)) a (F(3)a G(3,2))o (0a 1) a(1 a1) o0 假命题2) 3x( F(f(x)) a G(x, Fx)))o ( F(f(2)) a G(2,f(2)) ) v (F(f(3)) a G(3, f(3)))o (F(3) a G(2, 3) ) v ( F(2) a G(3, 2))o ( 1 a 1 ) v ( 0 a 1 ) o1 真命题例给定解释：(a) 个体域为自然数集合Dn(b) Dn中特定元素a=0(c) Dn 上特定函数 fx，Y)= x+y , g(x，Y)= x.j(d) DN上特定谓词F(x，y)为x=y1) VxF(g(x,a), x))oVxF(x.O , x) o Vx(x.0= x) 假命题2) Vx Vy( F(f(x,a)，Y)T F(f(y,a),x))oVx Vy( F(0+x，y) t F(y+0,x))oVx Vy ( (0+x=y) t (y+0=x)) 真命题3) Vx Vy F(/(x，y), G(x，y))oVx Vy F(x+y，x.y) oVx Vy (x+y= x.y)假命题4) F(fx，Y), F(Y，z))oF(x+y，y+z) o x+y= Y+z 不是命题例1给定解释I如下：(a)个体域D=N(B) f (x, y)二 x + y，G(x, Y)二 xy戸(x,y)：x二 Y(c)⑷谓词说明下列公式在I下的涵义，并讨论真值公式的分类永真式(逻辑有效式)：公式在任何解释下都是真的，即无成假赋值 矛盾式(永假式)：公式在任何解释下都是假的，即无成真赋值 可满足式：至少存在一个解释使公式成真说明：永真式为可满足式，但反之不真 某些代换实例可判公式类型 代换实例定义设A0是含命题变项pl, p2,・…，的命题公式，A1,A2,…,An是n个谓词公式，用Ai处处代替A0中的pi(1