离散数学谓词公式与解释省公共课一等奖全国赛课获奖课件.pptx

西华大学 符号体系：符号体系：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 一阶逻辑合式公式及解释一阶逻辑合式公式及解释第1页西华大学 原子公式：原子公式：为为n元谓词符号，元谓词符号，t1,t2,tn 是是项，则项，则 是原子公式；是原子公式；合式公式归纳定义：合式公式归纳定义：1、任意原子公式是公式、任意原子公式是公式 2、若、若A是公式，则是公式，则 xA、xA是公式；是公式；3、若、若A、B是公式，则是公式，则 A、A B、A B、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)一、合式公式定义：一、合式公式定义：第2页西华大学 在谓词公式中，形如在谓词公式中，形如 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)，通称，通称为量词辖域。换言之，量词辖域是邻接其为量词辖域。换言之，量词辖域是邻接其后公式，除非辖域是原子公式，不然应在后公式，除非辖域是原子公式，不然应在所辖公式两侧插入圆括号。所辖公式两侧插入圆括号。二、约束部分二、约束部分第3页西华大学 量词辖域举例量词辖域举例比如：比如：x F(x)G(x,y)解解：x辖辖域域仅仅F(x),x是是指指导导变变元元，变变元元x第第一一次次出出现现是是约约束束出出现现，第第二二次次出出现现是是自自由由出出现现，y出出现现是是自自由由出出现现。所所以以第第一一个个x是是约约束束变变元元，第第二二个个x是是自自由由变变元元，本本质质上上这这两两个个x含含义义是是不不一一样样；而而y仅是自由变元。仅是自由变元。第4页西华大学 换名规则换名规则能够看出能够看出,在谓词公式中一个变元可能既是约束出现在谓词公式中一个变元可能既是约束出现,同同时又有自由出现时又有自由出现,则该变元既是自由变元又是约束变元则该变元既是自由变元又是约束变元,本质上这两种出现本质上这两种出现,用是一个符号用是一个符号,实质上是不一样含实质上是不一样含义。为防止混同义。为防止混同,需要更名。更名要采取以下规则需要更名。更名要采取以下规则,使使谓词公式含义不改变。谓词公式含义不改变。1、换名规则换名规则：对约束变元进行换名。：对约束变元进行换名。将量词辖域内出现某个约束变元及其对应量词中指导变将量词辖域内出现某个约束变元及其对应量词中指导变元元，能够换成一个其它变元能够换成一个其它变元，改变元不能与本辖域内改变元不能与本辖域内其它变元同名其它变元同名，公式中其它部分不改变。公式中其它部分不改变。2、代替规则代替规则：对自由变元进行代入。：对自由变元进行代入。整个谓词公式中同一个字母自由变元是指同一个个体名整个谓词公式中同一个字母自由变元是指同一个个体名词。所以能够用整个公式中没有变元符号来代替词。所以能够用整个公式中没有变元符号来代替，且且要求整个公式中该变元同时用同一个符号代替。要求整个公式中该变元同时用同一个符号代替。第5页西华大学 换名规则举例换名规则举例 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)第6页西华大学 谓词公式解释谓词公式解释谓词逻辑中解释谓词逻辑中解释(赋值赋值)在命题逻辑对每个命题符号作个真值指定能够得一个在命题逻辑对每个命题符号作个真值指定能够得一个公式一个指派公式一个指派,又称赋值又称赋值,又称解释。如公式中共出现又称解释。如公式中共出现n个不一样命题符号个不一样命题符号,则共有则共有2n个解释个解释,因而能够列出因而能够列出公式真值表。而谓词逻辑中公式赋值解释是怎样呢公式真值表。而谓词逻辑中公式赋值解释是怎样呢？比如公式：比如公式：x F(x,a)x G(f(x),a)第7页西华大学 三、谓词公式赋值三、谓词公式赋值(解释解释)一个解释由一个解释由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)假命题。假命题。第8页西华大学 解释举例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第9页解释举例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)在解释在解释N下此公式：下此公式：x y(x+0=yy+0=x)此命题为真此命题为真(3)F(f(x,y),f(y,z)在解释在解释N下该公式下该公式x+y=y+z此时此时,x,y,z均为自由变元均为自由变元,解释不对自由变元进行指定。因而该解释不对自由变元进行指定。因而该公式是命题函数公式是命题函数,不是命题不是命题,真值不能确定。真值不能确定。第10页解释说明(1)一个谓词公式假如不含自由变元一个谓词公式假如不含自由变元,则在一个解释下则在一个解释下,能够得到确定真值能够得到确定真值,不一样解释下可能得到不一样真值。不一样解释下可能得到不一样真值。(2)公式解释并不对变元进行指定公式解释并不对变元进行指定,假如公式中含有自由假如公式中含有自由变元变元,即使对公式进行了一个指派即使对公式进行了一个指派,也得不到确定真值也得不到确定真值,其仅是个命题函数其仅是个命题函数,但约束变元不受此限制。但约束变元不受此限制。3 3）有公式解释定义能够看出）有公式解释定义能够看出,公式解释有许多解释公式解释有许多解释,当当D为无限集时为无限集时,公式有没有限多个解释公式有没有限多个解释,根本不可能将其根本不可能将其一一列出一一列出,因而谓词逻辑公式不可能有真值表可列。因而谓词逻辑公式不可能有真值表可列。第11页西华大学 四、谓词公式类型四、谓词公式类型 设设A是公式。假如是公式。假如A在任何解释下都是在任何解释下都是真，则真，则A是永真式；假如是永真式；假如A在任何解释下在任何解释下都是假，则都是假，则A是永假式；假如是永假式；假如A在一些解在一些解释下为假，一些解释下为真，则释下为假，一些解释下为真，则A是非永是非永真可满足式。真可满足式。比如：比如：x A(x)x A(x)是永真式；是永真式；x A(x)x A(x）是永假式。）是永假式。第12页西华大学 代换实例代换实例设设A0是是含含命命题题变变元元p1,p2,pn命命题题逻逻辑辑公公式式，A1,A2,An是是一一阶阶逻逻辑辑公公式式，用用Ai(1 i n)替替换换A0中中pi处处处处出出现现所所得得到到一一阶阶逻逻辑辑公公式式A称称为为命题逻辑公式命题逻辑公式A0替换实例。替换实例。定定理理：命命题题逻逻辑辑中中永永真真式式任任意意替替换换实实例例在在一一阶阶逻逻辑辑中中都都是是永永真真式式；命命题题逻逻辑辑中中矛矛盾盾式式任任意意替替换换实实例例在一阶逻辑中都是矛盾式在一阶逻辑中都是矛盾式。第13页西华大学 1、永真式和永假式代入实例是永真、永假式；永真式和永假式代入实例是永真、永假式；2.对对于于一一些些简简单单公公式式，尤尤其其对对于于简简单单闭闭式式，可可在在假假定定给给定定任任意意解解释释前前提提下下该该公公式式真真值值都都为为真真（或或者者为为假假）来来证证实实该该公公式式是是永永真真式式（或或矛矛盾盾式）。式）。3.要证实一个公式是可满足式，只要找到一个要证实一个公式是可满足式，只要找到一个解释，使得该公式真值为真即可。同时为了证解释，使得该公式真值为真即可。同时为了证实它不是永真式，只要找一个解释，使得该公实它不是永真式，只要找一个解释，使得该公式真值为假即可。式真值为假即可。第14页西华大学 公式类型举例公式类型举例判断以下公式类型：判断以下公式类型：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)第15页西华大学 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)是永真式。是永真式。第16页西华大学 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)永真永真。第17页西华大学 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从而公式不是永假式；从而公式不是永假式；可知，公式是非永真可满足式。可知，公式是非永真可满足式。第18页西华大学 思索题：思索题：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)是永真式。是永真式。第19页