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

《离散数学谓词公式与解释.ppt》由会员分享，可在线阅读，更多相关《离散数学谓词公式与解释.ppt（19页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、西华大学 符号体系：符号体系：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.联结词联结词:7.项的定义项的定义8.个体变元、个体常元是项；个体变元、个体常元是项；9.若若 是任意是任意n元函数，元函数，t1,t2,tn 是项，是项，则则 是项；是项；10.有限次的应用有限次的应用1，2得到项。得到项。2.2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释西华大学 原子公式：原子公式：为为n元谓词符号，元谓词符号，t1,

2、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.x y(P(x)Q(y)3.y x P(x)4.x f(x)x(g(x,y)f(x)一、合式公式的定义：一、合式公式的定义：西华大学 在谓词公式中，形如在谓词公式中

3、，形如 x xP(P(x x)或或 x xP(x)P(x)以及以及 x xP P(x x，y)y)的部分中的部分中x x称为指导变元，在辖域中称为指导变元，在辖域中,x x的所有出现的所有出现称为约束变元（约束出现）；称为约束变元（约束出现）；y y是自由变元（自由出现）。是自由变元（自由出现）。量词的辖域量词的辖域 (x)P(x)(x)P(x)或或(x)P(x)(x)P(x)中的公式中的公式P(x)P(x)，通，通称为量词的辖域。换言之，量词的辖域是称为量词的辖域。换言之，量词的辖域是邻接其后的公式，除非辖域是原子公式，邻接其后的公式，除非辖域是原子公式，否则应在所辖公式的两侧插入圆括号。否

4、则应在所辖公式的两侧插入圆括号。二、约束部分二、约束部分西华大学 量词辖域举例量词辖域举例例如：例如：x F(x)G(x,y)解解：x的的辖辖域域仅仅F(x),x是是指指导导变变元元，变变元元x第第一一次次出出现现是是约约束束出出现现，第第二二次次出出现现是是自自由由出出现现，y的的出出现现是是自自由由出出现现。所所以以第第一一个个x是是约约束束变变元元，第第二二个个x是是自自由由变变元元，本本质质上上这这两两个个x的的含含义义是是不不同的；而同的；而y仅是自由变元。仅是自由变元。西华大学 换名规则换名规则可以看出可以看出,在谓词公式中一个变元可能既是约束出现在谓词公式中一个变元可能既是约束出

5、现,同同时又有自由出现时又有自由出现,则该变元既是自由变元又是约束变元则该变元既是自由变元又是约束变元,本质上这两种出现本质上这两种出现,用的是一个符号用的是一个符号,实质上是不同的实质上是不同的含义。为避免混淆含义。为避免混淆,需要改名。改名要采用以下规则需要改名。改名要采用以下规则,使谓词公式的含义不改变。使谓词公式的含义不改变。1、换名规则换名规则：对约束变元进行换名。：对约束变元进行换名。将量词辖域内出现的某个约束变元及其相应量词中的指将量词辖域内出现的某个约束变元及其相应量词中的指导变元导变元，可以换成一个其他变元可以换成一个其他变元，改变元不能与本辖改变元不能与本辖域内的其他变元同

6、名域内的其他变元同名，公式中的其他部分不改变。公式中的其他部分不改变。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

7、(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个解释个解释,因而可以因而可以列出公式的真值表。而谓词逻辑中公式的赋值解释列出公式的真值表。而谓词逻辑中公式的赋值解释是怎样的呢？是怎样的呢

8、？例如公式：例如公式：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

9、)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)x y(F(f(x,a),y)F(f(y,a),x)在解释在解

10、释N下此公式：下此公式：x y(x+0=yy+0=x)此命题为真此命题为真(3)F(f(x,y),f(y,z)在解释在解释N下该公式下该公式x+y=y+z此时此时,x,y,z均为自由变元均为自由变元,解释不对自由变元进行指定。因而解释不对自由变元进行指定。因而该公式是命题函数该公式是命题函数,不是命题不是命题,真值不能确定。真值不能确定。解释的说明(1)一个谓词公式如果不含自由变元一个谓词公式如果不含自由变元,则在一个解释下则在一个解释下,可以得到确定的真值可以得到确定的真值,不同的解释下可能得到不同的不同的解释下可能得到不同的真值。真值。(2)公式的解释并不对变元进行指定公式的解释并不对变元

11、进行指定,如果公式中含有自如果公式中含有自由变元由变元,即使对公式进行了一个指派即使对公式进行了一个指派,也得不到确定的也得不到确定的真值真值,其仅是个命题函数其仅是个命题函数,但约束变元不受此限制。但约束变元不受此限制。3 3）有公式的解释定义可以看出）有公式的解释定义可以看出,公式的解释有许多的解公式的解释有许多的解释释,当当D为无限集时为无限集时,公式有无限多个解释公式有无限多个解释,根本不可能根本不可能将其一一列出将其一一列出,因而谓词逻辑的公式不可能有真值表因而谓词逻辑的公式不可能有真值表可列。可列。西华大学 四、谓词公式的类型四、谓词公式的类型 设设A是公式。如果是公式。如果A在任

12、何的解释下都在任何的解释下都是真的，则是真的，则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的的处处处处出出现现所所

13、得得到到的的一一阶阶逻逻辑辑公公式式A称为命题逻辑公式称为命题逻辑公式A0的的替换实例替换实例。定定理理：命命题题逻逻辑辑中中的的永永真真式式的的任任意意替替换换实实例例在在一一阶阶逻逻辑辑中中都都是是永永真真式式；命命题题逻逻辑辑中中的的矛矛盾盾式式的的任任意意替换实例替换实例在一阶逻辑中都是矛盾式在一阶逻辑中都是矛盾式。西华大学 1、永真式和永假式的代入实例是永真、永假式；永真式和永假式的代入实例是永真、永假式；2.对对于于某某些些简简单单的的公公式式，特特别别对对于于简简单单的的闭闭式式，可可在在假假定定给给定定任任意意解解释释的的前前提提下下该该公公式式的的真真值值都都为为真真（或或者

14、者为为假假）来来证证明明该该公公式式是是永永真真式式（或矛盾式）。（或矛盾式）。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)

15、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的情况，的情况，

16、蕴涵式都为真。蕴涵式都为真。又由解释又由解释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 则公式为：则公式为：x y(xy=0)y x(xy=0)=11=1从而公式不是永假式；从而公式不是永假式；可知，公式是非永真的可满足式。可知，公式是非永真的可满足式。西华大学 思考题：思考题：1、F(a)x F(x)2、F(a)x F(x)解：解：1、F(a)x F(x)是非永真的可满足式；是非永真的可满足式；设设D=2，a=2，F(x):x=2，显然此时为真；，显然此时为真；设设D=R，a=2，F(x):x=2，显然此时为假；，显然此时为假；2、F(a)x F(x)是永真式。是永真式。