离散数学谓词公式与解释公开课一等奖优质课大赛微课获奖课件.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页第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页第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页第3页西华大学 量词辖域举例量词辖域举例比如：x F(x)G(x,y)解：x辖域仅F(x),x是指导变元，变元x第一次出现是约束出现，第二次出现是自由出现，y出现是自由出现。因此第一个x是约束变元，第二个x是自由变元，本质上这两个x含义是不同；而y仅是自由变元。第4页第4页西华大学 换名规则换名规则能够看出,在谓词公式中一个变元可能既是约束出现,同时又有自由出现,则该变元既是自由变元又是约束变元,本质上这两种出现,用是一个符号,实质上是不同含义。为避免混同,需要更名。更名要采取以下规则,使谓词公式含义不改变。1、换名规则：对约束变元进行换名。将量词辖域内出现某个约束变元及其对应量词中指导变元，能够换成一个其它变元，改变元不能与本辖域内其它变元同名，公式中其它部分不改变。2、代替规则：对自由变元进行代入。整个谓词公式中同一个字母自由变元是指同一个个体名词。因此能够用整个公式中没有变元符号来代替，且要求整个公式中该变元同时用同一个符号代替。第5页第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页第6页西华大学 谓词公式解释谓词公式解释谓词逻辑中解释(赋值)在命题逻辑对每个命题符号作个真值指定能够得一个公式一个指派,又称赋值,又称解释。如公式中共出现n个不同命题符号,则共有2n个解释,因而能够列出公式真值表。而谓词逻辑中公式赋值解释是怎样呢？比如公式：x F(x,a)x G(f(x),a)第7页第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页第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页第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页第10页解释阐明(1)一个谓词公式假如不含自由变元,则在一个解释下,能够得到确定真值,不同解释下可能得到不同真值。(2)公式解释并不对变元进行指定,假如公式中含有自由变元,即使对公式进行了一个指派,也得不到确定真值,其仅是个命题函数,但约束变元不受此限制。3）有公式解释定义能够看出,公式解释有许多解释,当D为无限集时,公式有没有限多个解释,根本不可能将其一一列出,因而谓词逻辑公式不可能有真值表可列。第11页第11页西华大学 四、谓词公式类型四、谓词公式类型 设设A是公式。假如是公式。假如A在任何解释下都是在任何解释下都是真，则真，则A是永真式；假如是永真式；假如A在任何解释下在任何解释下都是假，则都是假，则A是永假式；假如是永假式；假如A在一些解在一些解释下为假，一些解释下为真，则释下为假，一些解释下为真，则A是非永是非永真可满足式。真可满足式。比如：比如：x A(x)x A(x)是永真式；是永真式；x A(x)x A(x）是永假式。）是永假式。第12页第12页西华大学 代换实例代换实例设设A0是是含含命命题题变变元元p1,p2,pn命命题题逻逻辑辑公公式式，A1,A2,An是是一一阶阶逻逻辑辑公公式式，用用Ai(1 i n)替替换换A0中中pi处处处处出出现现所所得得到到一一阶阶逻逻辑辑公公式式A称称为为命题逻辑公式命题逻辑公式A0替换实例。替换实例。定定理理：命命题题逻逻辑辑中中永永真真式式任任意意替替换换实实例例在在一一阶阶逻逻辑辑中中都都是是永永真真式式；命命题题逻逻辑辑中中矛矛盾盾式式任任意意替替换换实实例例在一阶逻辑中都是矛盾式在一阶逻辑中都是矛盾式。第13页第13页西华大学 1、永真式和永假式代入实例是永真、永假式；永真式和永假式代入实例是永真、永假式；2.对对于于一一些些简简朴朴公公式式，尤尤其其对对于于简简朴朴闭闭式式，可可在在假假定定给给定定任任意意解解释释前前提提下下该该公公式式真真值值都都为为真真（或或者者为为假假）来来证证实实该该公公式式是是永永真真式式（或或矛矛盾盾式）。式）。3.要证实一个公式是可满足式，只要找到一个要证实一个公式是可满足式，只要找到一个解释，使得该公式真值为真即可。同时为了证解释，使得该公式真值为真即可。同时为了证实它不是永真式，只要找一个解释，使得该公实它不是永真式，只要找一个解释，使得该公式真值为假即可。式真值为假即可。第14页第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页第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页第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页第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页第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页第19页