离散数学(虞慧群)1-2predicatelog.ppt

《离散数学(虞慧群)1-2predicatelog.ppt》由会员分享，可在线阅读，更多相关《离散数学(虞慧群)1-2predicatelog.ppt（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、1虞慧群虞慧群谓词逻辑谓词逻辑Predicative Logic21.1.谓词与量词谓词与量词2.2.项与公式项与公式3.3.公式语义公式语义4.4.前束范式前束范式5.5.推理理论推理理论内容提要内容提要1 1、谓词与量词、谓词与量词概念概念：谓词，个体词，论域，全称量词，存在量词谓词，个体词，论域，全称量词，存在量词考虑以下推理考虑以下推理（苏格拉底三段论苏格拉底三段论）：所有的人都会死的所有的人都会死的。苏格拉底是人。苏格拉底是人。苏格拉底会死的。苏格拉底会死的。直观上是有效的论证，但命题语言表示为：直观上是有效的论证，但命题语言表示为：pqr不是有效推论。命题的局限性命题的局限性原因：

2、原因：“苏格拉底三段论苏格拉底三段论”有效性不是取决于前提、结论之间的有效性不是取决于前提、结论之间的作为简单的命题的关系，而是依赖于命题的成分之间的联系。有作为简单的命题的关系，而是依赖于命题的成分之间的联系。有必要将命题分解得更细。必要将命题分解得更细。命题命题 =主语主语+谓语谓语+宾语宾语个体词个体词谓词谓词+量词量词命题命题的成分的成分：例例:(1):(1)苏格拉底是人苏格拉底是人 (2)(2)所有的人都会死的所有的人都会死的。注意：逻辑中主、谓注意：逻辑中主、谓成分成分划分与汉语有区别。划分与汉语有区别。谓词谓词表示命题的谓语部分的符号或符号串表示命题的谓语部分的符号或符号串常用表

3、示：大写字母，常用表示：大写字母，A,B,C,带有下标的大写字母，带有下标的大写字母，A1,A2,A3,以大写字母为首的字符串，以大写字母为首的字符串，Human,谓词的元数谓词的元数:谓词中包含个体的数目。谓词中包含个体的数目。1元谓词描述个体的性质，2元或多元谓词描述两个或多个个体间的关系。0元谓词中无个体，理解为就是命题6个体词个体词用于表示命题中主语部分的符号或符号串。用于表示命题中主语部分的符号或符号串。通常用小写字母，或带小标的小写字母表示。通常用小写字母，或带小标的小写字母表示。个体个体常常元元表示确指个体。表示确指个体。例：例：Human(s)中中s指苏格拉底，是个体常元。指苏

4、格拉底，是个体常元。个体变元个体变元表示不确指个体。表示不确指个体。例：例：Human(x)中的中的x。个体域个体域(domain):个体变元的取值范围，常用个体变元的取值范围，常用D表示。表示。7量词量词：限定个体数量特性的词限定个体数量特性的词。全称量词全称量词(Universalquantifier)对所有的，对所有的，for All例：例：所有的整数都有质因子。所有的整数都有质因子。理解成理解成“对所有对所有x，若，若x是整数，那么是整数，那么x有质因子有质因子”(x)(I(x)P(x)xA(x)表示个体域中的表示个体域中的任意任意个体个体x均具有性质均具有性质A。存在量词存在量词(E

5、xistential quantifer)，有些，有些，there Exist xA(x)表示表示存在存在着个体域中的个体着个体域中的个体x具有性质具有性质A。例：例：有些猪有翅膀。有些猪有翅膀。理解为理解为“至少有一个物体至少有一个物体x，x是猪并且是猪并且x有翅膀。有翅膀。”(x)(P(x)W(x)例：将下列语句符号化：例：将下列语句符号化：（1）不是所有的鸟都能飞。）不是所有的鸟都能飞。(x)(B(x)F(x)（2）所有的人都能做那件事。）所有的人都能做那件事。(x)(M(x)D(x)（3）有些人是笨的。）有些人是笨的。(x)(M(x)S(x)（4）有一个整数比其它任何整数都大。）有一个

6、整数比其它任何整数都大。(x)(I(x)(y)(E(y)D(x,y)G(x,y)10考虑例（考虑例（1）“不是所有的鸟都能飞不是所有的鸟都能飞”可理解为可理解为“至少有一只鸟不能飞至少有一只鸟不能飞”。(x)(B(x)F(x)(x)(B(x)F(x)(x)等价于等价于。即只要有一个量词就够了。即只要有一个量词就够了。112 2、项与合式公式、项与合式公式概念概念：项，原子公式，合式公式，自由变元，约束变元，辖域，项，原子公式，合式公式，自由变元，约束变元，辖域，换名，代入换名，代入谓词语言：用符号串表示个体、谓词、量词和命题谓词语言：用符号串表示个体、谓词、量词和命题一阶谓词逻辑一阶谓词逻辑的

7、基本符号的基本符号个体个体变变元符号：元符号：x，y，z，个体个体常常元符号：元符号：a，b，c，连接词符号：连接词符号：,辅助符号：辅助符号：）,（函数符号：函数符号：f，g，谓词符号：谓词符号：P，Q，R，命题常元符号：命题常元符号：，量词符号：量词符号：，逻辑符号：在任何情况下都作用相同的符号。逻辑符号：在任何情况下都作用相同的符号。非逻辑符号：其他符号，即个体常元符号、函数符号、非逻辑符号：其他符号，即个体常元符号、函数符号、谓词符号。谓词符号。(1)个体常元和变元是项；个体常元和变元是项；(2)若若f是是n元函数符号，元函数符号，t1,tn是项，则是项，则f(t1,tn)是项；是项；

8、(3)仅仅有限次使用仅仅有限次使用(1)，(2)产生的符号串是项。产生的符号串是项。项（项（Term）注：项将解释成个体对象。注：项将解释成个体对象。合式公式合式公式(Well-Formed Formulas)递归定义如下：递归定义如下：(1)原子公式是公式；原子公式是公式；(2)若若A是合式公式，则是合式公式，则(A)是合式公式是合式公式；(3)若若A，B是公式，则是公式，则(A B)，(A B)，AB)，(AB)是公式；是公式；(4)若若A是公式，是公式，x是变元，则是变元，则 xA，xA是公式；是公式；(5)仅仅有限次使用得到的符号串才是合式公式。仅仅有限次使用得到的符号串才是合式公式。

9、原子公式原子公式(Atomicformulas)若若P是一个元谓词符号，是一个元谓词符号，t1,tn是项是项,则则P(t1,tn)是原子公式。是原子公式。变元的约束变元的约束设公式设公式 的一个子公式为的一个子公式为 xA或或 xA。则称：。则称：指导变元指导变元：x是是 或或 的指导变元。的指导变元。辖域辖域(Scope)：A是相应量词的辖域。是相应量词的辖域。约束出现约束出现(bounded)：辖域中：辖域中x的一切出现，以及的一切出现，以及(x)中的中的x称为称为x在在 中的约束出现。中的约束出现。自由出现自由出现(free)：变元的非约束出现。：变元的非约束出现。约束变元约束变元：约束

10、出现的变元。：约束出现的变元。自由变元自由变元：自由出现的变元。：自由出现的变元。封闭的封闭的(Closed)一个公式一个公式A是封闭的，若其中不含自由变元。是封闭的，若其中不含自由变元。例：例：x y(P(x,y)Q(y,z)xP(x,y)17变元换名变元换名(Replacement)目的目的是避免变元的约束与自由同时出现，引起混淆是避免变元的约束与自由同时出现，引起混淆,可对约可对约束变元换名。束变元换名。规则：规则：（1）换名的范围是量词的指导变元换名的范围是量词的指导变元,及其相应辖域及其相应辖域中的变元，其余部分不变。中的变元，其余部分不变。（2）换名时最好选用辖域中未出现的变元名换

11、名时最好选用辖域中未出现的变元名。例：例：x(P(x)R(x,y)Q(x,y)可换为可换为：z(P(z)R(z,y)Q(x,y)不能不能：y(P(y)R(y,y)Q(x,y)变变元代入元代入(Substitution)代入代入对自由变元进行对自由变元进行。不能。不能改变约束关系。改变约束关系。183 3、谓词公式语义、谓词公式语义概念概念：解释，解释，赋值赋值，有效的，可满足的，不可满足的，有效的，可满足的，不可满足的解释解释(Interpretation)谓词语言的一个谓词语言的一个解释解释 I=(D,)包括包括：(1)非空集合非空集合D，称之为论域；，称之为论域；(2)对应于每一个个体常元

12、对应于每一个个体常元a，(a)D；(3)对应于每一个对应于每一个n元函数符号元函数符号f都有一个函数都有一个函数(f):DnD；(4)对应于每一个对应于每一个n元谓词符号元谓词符号A都有一个都有一个n元元关系关系(A)Dn。注：解释也称为注：解释也称为结构结构，通常简单地用，通常简单地用 表示。表示。20赋值赋值(Assignment)解释解释I中的中的赋值赋值v为每一个个体变元为每一个个体变元x指定一个值指定一个值v(x）D，即设，即设V为所个体变元的集合，则为所个体变元的集合，则赋值赋值v是函数是函数v:VD.若若v是赋值，则是赋值，则v的的a-equivalent 赋值记为赋值记为vxa

13、（其中（其中a D表示一个由表示一个由定义的赋值。定义的赋值。注：给定解释注：给定解释I和和I中的中的赋值赋值v后，任何项和公式的含义后，任何项和公式的含义就明确了。就明确了。vI:TERMD vI:WFF1,0项的语义项的语义项项t在结构在结构I=(D，)和赋值和赋值v下的值，记为下的值，记为vI(t)(1)若若t 是常元是常元a，则，则vI(t)=(a)(2)若若t 是变元是变元x，则，则vI(t)=(x)(3)若若t 是是f(t1,t2,tn)，则，则vI(t)=(f)(vI(t1),vI(t2),vI(tn)例、例、=a,f，f(x,a)是一个项是一个项解释解释、：1(a)=1，1(f

14、)=+；I1=(Z,)2(a)=0，(f)=-；I=(Z,)3(a)=-2，3(f)=；I=(Z,)x的赋值的赋值v1、v2、v3 v1(x)=7、v2(x)=0、v3(x)=-5公式的语义公式的语义公式公式A在结构在结构I=(D，)和赋值和赋值v下的值，记为下的值，记为vI(A)2、若、若A为原子公式为原子公式P(t1,tn)，则，则1、若、若A为命题常元符号为命题常元符号p，则，则4、若、若A为析取式为析取式(B C)，则，则5、若、若A为合取式为合取式(B C)，则，则3、若、若A为否定式为否定式(B)，则，则7、若、若A为等价式为等价式(B C)，则，则6、若、若A为蕴含式为蕴含式(B

15、C)，则，则9、若、若A为为(xB)，则，则8、若、若A为为(xB)，则，则给出如下两个公式：给出如下两个公式：1)G=x(P(f(x)Q(x，f(a)2)H=x(P(x)Q(x，a)给出如下的解释给出如下的解释I：D=2，3 a=2 f(2)f(3)3 2 P(2)P(3)Q(2,2)Q(2,3)Q(3,2)Q(3,3)0 1 1 1 0 1练习练习TI(G)=TI(P(f(2)Q(2，f(2)(P(f(3)Q(3，f(2)=TI(P(3)Q(2，3)(P(2)Q(3，3)=(1 1)(0 0)=1TI(H)=TI(P(2)Q(2，2)P(3)Q(3，2)=0 1 1 0=0有效公式有效公式

16、当当一个解释一个解释I的的所有所有赋值赋值v都都使公式使公式A的真值的真值为为1，则称则称A在在解释解释I下下有效有效的的(validintheinterpretationI);当当公式公式A在所有的解释在所有的解释下都有效时，称下都有效时，称A是是(逻辑逻辑)有效的有效的(Logicallyvalid)。可满足的可满足的给定公式给定公式A，若在某一解释中至少有一，若在某一解释中至少有一种种赋值赋值使使A取取值值为为1，则称则称A为可满足的。否则称为可满足的。否则称A是不可满足的。是不可满足的。等等值值式式AB：若：若AB是有效的是有效的。30A=x（P(x，y)P(x，y)）不可满足公式）不

17、可满足公式A=（P(x，y)P(x，y)）有效公式）有效公式例、例、A=xP(x，y)可满足公式可满足公式几类等几类等值值式式（1）命题公式的推广命题公式的推广e.g.P(x)Q(x)P(x)Q(x)（2）否定深入）否定深入 xP(x)x(P(x)xP(x)x(P(x)32（3）量词作用域的扩张与收缩）量词作用域的扩张与收缩设设B中不含中不含x的自由出现，则的自由出现，则 x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B33（4）x(A(x)B(x)xA(x)xB(x)x(A(x)B(x)xA(x)xB(x)（5）多个量词的

18、使用）多个量词的使用 x yA(x,y)y xA(x,y)x yA(x,y)y xA(x,y)34置换规则置换规则 设设(A)是含是含A的公式的公式,那么那么,若若AB,则则(A)(B).换名规则换名规则 设设A为一公式，将为一公式，将A中某量词辖域中个体变项的所有约束中某量词辖域中个体变项的所有约束 出现及相应的指导变元换成该量词辖域中未曾出现过的个出现及相应的指导变元换成该量词辖域中未曾出现过的个 体变项符号，其余部分不变，设所得公式为体变项符号，其余部分不变，设所得公式为A，则，则AA.354 4、前束范式、前束范式概念概念：前束范式前束范式前束范式前束范式：如果谓词公式如果谓词公式A有

19、如下形状：有如下形状：Q1x1QnxnM其中其中Qixi或者是或者是 xi，或者是，或者是 xi，i=1，n，M是不含是不含量词的公式，量词的公式，Q1x1Qnxn称为首标，称为首标，M称为母式。称为母式。对于任意谓词公式，都存在与它逻辑等价的前束范式。对于任意谓词公式，都存在与它逻辑等价的前束范式。例、例、x y z(P(x，y)Q(x，z)；x y zP(x，y，z)均为前束范式。均为前束范式。步步3.将量词符号移至公式最外层。将量词符号移至公式最外层。步步1.对约束出现的变元进行必要的换名，使得约束出现对约束出现的变元进行必要的换名，使得约束出现的变元互不相同且不与任何自由变元同名。的变

20、元互不相同且不与任何自由变元同名。步步2.将所有的否定号将所有的否定号 深入到量词后面。深入到量词后面。xA=x A xA=x A前束前束范式范式的算法：的算法：xA B=x(A B)xA B=x(A B)xA B=x(A B)xA B=x(A B)xAB=x(AB)xAB=x(AB)A xB=x(AB)A xB=x(AB)x不在不在B中自由出现中自由出现x不在不在A中自由出现中自由出现例、例、例、例、(xP(x)x yQ(x,y)x yR(x,y)=(xP(x)w yQ(w,y)u vR(u,v)=(x P(x)w yQ(w,y)u vR(u,v)=x(P(x)w yQ(w,y)u vR(u

21、,v)换名换名 深入深入量词符量词符号前移号前移=(x w y(P(x)Q(w,y)u vR(u,v)=u v(x w y(P(x)Q(w,y)R(u,v)=u v x w y(P(x)Q(w,y)R(u,v)例例例例、x y(z(P(x,z)P(y,z)uQ(x,y,u)=x y(z(P(x,z)P(y,z)uQ(x,y,u)=x y(z(P(x,z)P(y,z)uQ(x,y,u)=x y z(P(x,z)P(y,z)uQ(x,y,u)=x y z u(P(x,z)P(y,z)Q(x,y,u)5 5、谓词逻辑推理理论、谓词逻辑推理理论概念概念：逻辑蕴含式，逻辑蕴含式，有效结论，有效结论，-规

22、则规则（USUS），+规则规则（UGUG），-规则规则(ES)(ES)，+规则规则(EG),(EG),推理推理逻辑逻辑蕴含式蕴含式AC：当且仅当当且仅当AC是是有效的。有效的。有效结论有效结论设设A、C是两个是两个谓词谓词公式，若公式，若AC，称，称C是是A的有效结论。的有效结论。推广推广:若若H1 HnC,称称C是一组前题是一组前题H1,Hn的有效结论。的有效结论。4243几类逻辑蕴涵式几类逻辑蕴涵式第一组第一组 命题逻辑推理定理的代换实例命题逻辑推理定理的代换实例 如如,xF(x)yG(y)xF(x)第二组第二组 基本等值式生成的推理定理基本等值式生成的推理定理 如如,xF(x)xF(x)

23、,xF(x)xF(x)xF(x)x F(x),x F(x)xF(x)第三组第三组 其它常用推理定律其它常用推理定律 (1)xA(x)xB(x)x(A(x)B(x)(2)x(A(x)B(x)xA(x)xB(x)(3)x(A(x)B(x)xA(x)xB(x)(4)x(A(x)B(x)xA(x)xB(x)+规则规则(UG)：-规则规则(US)：-规则规则(ES)：+规则规则(EG)：推理规则推理规则A xA xAAt/xAt/x xA x A(x)A(c)45自然推理系统自然推理系统NL自然推理系统自然推理系统NL定义如下定义如下:1.字母表字母表.同一阶语言同一阶语言L的字母表的字母表2.合式公式

24、合式公式.同同L的合式公式的合式公式3.推理规则推理规则:(1)前提引入规则前提引入规则(2)结论引入规则结论引入规则(3)置换规则置换规则(4)假言推理规则假言推理规则(5)附加规则附加规则(6)化简规则化简规则(7)拒取式拒取式(8)假言三段论规则假言三段论规则(9)析取三段论规则析取三段论规则(10)构造性二难推理规则构造性二难推理规则(11)合取引入规则合取引入规则(12)-规则规则(13)+规则规则(14)-规则规则(15)+规则规则推理（证明）推理（证明）从前提从前提A1,A2,Ak到结论到结论B的推理是一个公式序列的推理是一个公式序列C1,C2,Cl.其中其中Ci(1 i l)是

25、某个是某个Aj,或者可由序列中前面的公式应用推理或者可由序列中前面的公式应用推理规则得到规则得到,并且并且Cl=B。46例：用推理理论证明例：用推理理论证明(1)x(H(x)M(x),H(s)|-M(s)(2)x(C(x)W(x)R(x),x(C(x)Q(x)|-x(Q(x)R(x)注：先用注：先用ES，再用，再用US。(3)x(P(x)Q(x)|-xP(x)xQ(x)注：注：a.用归谬法。用归谬法。b.用用CP规则规则:将将 xP(x)xQ(x)看成看成 xP(x)xQ(x)47谓词逻辑总结谓词逻辑总结1.1.谓词与量词谓词与量词:谓词，个体词，论域，全称量词，存在量词谓词，个体词，论域，全称量词，存在量词2.2.项与公式项与公式:项，原子公式，合式公式，自由变元，约束变项，原子公式，合式公式，自由变元，约束变元，辖域，换名，代入元，辖域，换名，代入3.3.公式语义公式语义:解释，解释，赋值赋值，有效的，可满足的，不可满足的，有效的，可满足的，不可满足的4.4.前束范式前束范式:前束范式前束范式5.5.推理理论推理理论:逻辑蕴含式，逻辑蕴含式，有效结论，有效结论，-规则规则（USUS），+规则规则（UGUG），-规则规则(ES)(ES)，+规则规则(EG),(EG),推理推理48