离散数学谓词公式与解释.ppt

西华大学 符号体系： 1. 个体常元符号：a,b,c,a1,a2,a3, 2. 个体变元:x,y,z,x1,x2,x3, 3. 函数符号:f,g,h,f1,f2,f3, 4. 谓词符号:F,G,H, 5. 量词符号: 6. 联结词: 项的定义 1.个体变元、个体常元是项； 2.若 是任意n元函数，t1,t2,tn 是项，则 是项； 3.有限次的应用1，2得到项。 2.2 一阶逻辑合式公式及解 释 西华大学 原子公式： 为n元谓词符号，t1,t2,tn 是项，则 是原子公式； 合式公式的归纳定义： 1、任意的原子公式是公式 2、若A是公式，则xA、xA是公式； 3、若A、B是公式，则 A、A B、AB、A B、A B 是公式； 有限次地应用前三条，得到公式。 判断下列符号串是否为合式公式： 1. x(P(x) Q(x) 2. xy(P(x) Q(y) 3. yx P(x) 4. x f(x) x(g(x,y) f(x) ) 一、合式公式的定义： 西华大学 在谓词公式中，形如xP(x)或xP(x)以及 xP(x，y)的部分中x称为指导变元，在 辖域中,x的所有出现称为约束变元（约 束出现）；y是自由变元（自由出现）。 量词的辖域 (x)P(x)或(x)P(x)中的公式P(x)，通 称为量词的辖域。换言之，量词的辖域 是邻接其后的公式，除非辖域是原子公 式，否则应在所辖公式的两侧插入圆括 号。 二、约束部分 西华大学 量词辖域举例 例如：x F(x)G(x,y) 解：x的辖域仅F(x),x是指导变元，变 元x第一次出现是约束出现，第二次 出现是自由出现，y的出现是自由出现 。所以第一个x是约束变元，第二个x 是自由变元，本质上这两个x的含义 是不同的；而y仅是自由变元。 西华大学 换名规则 可以看出,在谓词公式中一个变元可能既是约束出现,同 时又有自由出现,则该变元既是自由变元又是约束变 元,本质上这两种出现,用的是一个符号,实质上是不 同的含义。为避免混淆,需要改名。改名要采用以下 规则,使谓词公式的含义不改变。 1、 换名规则：对约束变元进行换名。 将量词辖域内出现的某个约束变元及其相应量词中的 指导变元，可以换成一个其他变元，改变元不能与 本辖域内的其他变元同名，公式中的其他部分不改 变。 2、 代替规则：对自由变元进行代入。 整个谓词公式中同一个字母的自由变元是指同一个个 体名词。因此可以用整个公式中没有的变元符号来 代替，且要求整个公式中该变元同时用同一个符号 代替。 西华大学 换名规则举例 x F(x,y)x G(x,y) 改为：x F(x,y)u G(u,y) 或者为： z F(z,y)x G(x,y) 对x (F(x,y)y G(x,y) F(x,y) 改为： x (F(x,t)y G(x,y) F(s,t) 或者为：t (F(t,y)y G(t,y) F(x,y) 西华大学 谓词公式的解释 谓词逻辑中的解释(赋值) 在命题逻辑对每个命题符号作个真值指定可以得一个 公式的一个指派,又称赋值,又称解释。如公式中共 出现n个不同的命题符号,则共有2n个解释,因而可 以列出公式的真值表。而谓词逻辑中公式的赋值解 释是怎样的呢？ 例如公式：x F(x,a)x G(f(x),a) 西华大学 三、谓词公式的赋值(解释) 一个解释由4部分组成： （1） 非空个体域D； （2）D中特定元素； （3）D上特定函数； （4）D上特定谓词。 公式x F(x,a)x G(f(x),a) 指定：D=实数集合；a=0； f(x):3x;F(x,y):xy；G(x,y):x=y。 则x (x 0) x (3x=0) 假命题。 西华大学 解释举例1 给定解释I如下： x(F(x) G(x,2) (F(2) G(2,2) (F(3) G(3,2) 0 1 1 y L(2,y) y L(3,y) (L(2,2)L(2,3) (L(3,2) L(3,3) ( 1 0 ) (0 1) 1 解释举例2 例2：已知指定一个解释N如下： (1)个体域为自然数集合DN (2)指定常项a=0 (3)DN上的指定函数f(x,y)=x+y,g(x,y)=x*y (4)指定谓词F(x,y)为x=y 在以上指定的解释N下,说明下列公式的真值 (1)xF(g(x,a),x) 即x(x*0=x)该命题假的 (2)xy(F(f(x,a),y)F(f(y,a),x) 在解释N下此公式：xy(x+0=yy+0=x)此命题为真 (3)F(f(x,y),f(y,z)在解释N下该公式x+y=y+z 此时,x,y,z均为自由变元,解释不对自由变元进行指定。因而 该公式是命题函数,不是命题,真值不能确定。 解释的说明 (1) 一个谓词公式如果不含自由变元,则在一个解释下, 可以得到确定的真值,不同的解释下可能得到不同的 真值。 (2) 公式的解释并不对变元进行指定,如果公式中含有 自由变元,即使对公式进行了一个指派,也得不到确定 的真值,其仅是个命题函数,但约束变元不受此限制。 3）有公式的解释定义可以看出,公式的解释有许多的 解释,当D为无限集时,公式有无限多个解释,根本不 可能将其一一列出,因而谓词逻辑的公式不可能有真 值表可列。 西华大学 四、谓词公式的类型 设A是公式。如果A在任何的解释下 都是真的，则A是永真式；如果A在任 何的解释下都是假的，则A是永假式； 如果A在一些解释下为假，一些解释下 为真，则A是非永真的可满足式。 例如： x A(x) x A(x)是永真式； x A(x)x A(x）是永假式。 西华大学 代换实例 设A0是含命题变元p1, p2, , pn的命题逻辑公式 ，A1, A2, , An是一阶逻辑公式，用Ai(1 i n)替换A0中的pi的处处出现所得到的一阶逻辑 公式A称为命题逻辑公式A0的替换实例。 定理：命题逻辑中的永真式的任意替换实例在一 阶逻辑中都是永真式；命题逻辑中的矛盾式的 任意替换实例在一阶逻辑中都是矛盾式 。 西华大学 1、永真式和永假式的代入实例是永真、永假式 ； 2. 对于某些简单的公式，特别对于简单的闭式 ，可在假定给定任意解释的前提下该公式的真 值都为真（或者为假）来证明该公式是永真式 （或矛盾式）。 3. 要证明一个公式是可满足式，只要找到一个 解释，使得该公式的真值为真即可。同时为了 证明它不是永真式，只要找一个解释，使得该 公式的真值为假即可。 西华大学 公式类型举例 判断下列公式的类型： 1) x F(x) (x yG(x,y) x F(x) ) 2) x F(x) x F(x) 3) x y F(x,y) y x F(x,y) 西华大学 1)x F(x) (x yG(x,y) x F(x) ) 解：显然该公式是：P (Q P ) 的替换实例。容易知道P (Q P ) 是永真式，从而x F(x) (x yG(x,y) x F(x) )是永 真式。 西华大学 2) x F(x) x F(x) 设在任意的解释I下， 1） x F(x) 为真，则 a，使得 F(a)为真， 使得 x F(x)为真， 在这种情况下，x F(x) x F(x)为真； 2） x F(x) 为假，x F(x) x F(x)为真 。 从而，在蕴涵式的前件x F(x) 为1或0的情 况，蕴涵式都为真。 又由解释I的任意性，知公式x F(x) x F(x)永真。 西华大学 3) x y F(x,y) y x F(x,y) 1）取解释I1为：D=R,F(x,y):xy 则公式为： x y (xy) y x(xy) =10=0，从而公式不是永真式； 2) 取解释I2为：D=R,F(x,y):x.y=0 则公式为：xy(xy=0)yx(xy=0)