命题逻辑与谓词逻辑.ppt

第二章逻 辑 推 理2.1 命 题 逻 辑 1命题 定义2-1 命题：具有真假意义的语句。定义2-2 原子命题：如果一个命题不能被进一步分解成更为简单的命题，则该命题就称为原子命题。2连接词：称为“非”或“否定”。：称为“析取”，PQ读作“P或Q”。：称为“合取”，PQ读作“P与Q”。：称为“条件”。PQ。：称为“双条件”。PQ,“P当且仅当Q”。连接词优先级：，3合式公式 定义2-3 合式公式（Well-Formed Formula，WFF）孤立的命题变元或逻辑常量（T，F）是合式公式；如果A是一个合式公式，则A也是一个合式公式；如果A、B是合式公式，则AB，AB，AB，AB也都是合式公式；当且仅当有限次使用规则后得到的公式才是合式公式。永真式（或重言式）：给定一个公式，如果对于所有的真值指派，它的值都为真（T），则称该公式为永真式（或重言式）；永假式（或称该公式为不可满足的）：如对于所有的真值指派，它的值都为假（F），则称该公式为永假式（或称该公式为不可满足的）。非永假的公式称为可满足的公式。4等价和永真蕴涵 定义2-4 等价：设A，B是两个命题公式，P1，P2，Pn是出现在A、B中的所有命题变元。如果对于这n个变元的任何一个真值指派的集合，A和B的真值都相等，则称公式A等价于公式B，记作AB。“等价”又可定义为：AB当且仅当AB是一个永真式。定义2-5 永真蕴涵：命题公式A永真蕴涵命题公式B，当且仅当AB是一个永真式，记作AB，读作“A永真蕴涵B”，简称“A蕴涵B”。2.2 谓 词 逻 辑1谓词与个体 原子命题被分解为谓词和个体两部分。个体是指可以单独存在的事物，它可以是一个抽象的概念，也可以是一个具体的东西。谓词是用来刻画个体性质或个体间关系的词。如：POET(libai)POET(dufu)GREAT(libai,dufu)一般用大写字母表示谓词，小写字母表示个体。元数:谓词中包含的个体数目称为谓词的。一元谓词:与一个个体相连的谓词，如POET(x)；多元谓词:与多个个体相连的谓词叫，如GREAT(x,y)(二元谓词)。个体域:任何个体的变化都有范围。谓词变元命名式:一个n元谓词常被表示成P(x1,x2,xn)。2量词全称量词:“(x)P(x)”表示命题“对个体域中所有的个体x，谓词P(x)均为T”。存在量词:“(x)Q(x)”表示命题“在个体域中存在某个个体使谓词Q(x)为T”。其中“”叫存在量词。设x的取值范围是甲，乙，丙三人，y的取值范围是bora,jetta,santana三种车型。(x)(y)LIKE(x,y)表示甲、乙、丙三人都喜爱bora,jetta,santana中的某一种车型；(x)(y)LIKE(x,y)表示甲、乙、丙三人都喜爱bora,jetta,santana三种车型。3合式谓词公式原子公式:若P为不能再分解的n元谓词变元，x1,x2,xn是个体变元，则称P(x1,x2,xn)为原子公式或原子谓词公式。当n=0时，P表示命题变元或原子命题公式。所以命题逻辑是谓词逻辑的特例 定义定义2-6 谓词合式公式（简称公式）的定义如下：原子公式是合式公式；若A是合式公式，则A也是合式公式；若A和B都是合式公式，则(AB)，(AB)，(AB)，(AB)也都是合式公式；若A是合式公式，x是任意变元，且A中无(x)或(x)出现，则(x)A或(x)A也都是合式公式；当且仅当有限次使用规则得到的公式是合式公式。4量词的辖域与变元的约束 约束变元,自由变元。公式 约束变元 自由变元 (x)P(x,y)x y (x)Q(y)无 y (x)(P(x)(y)Q(x,y)x,y (y)P(x)Q(x)y x 5谓词公式的解释 谓词公式中的谓词变元、命题变元和自由个体变元，个体常量和函数的一种指派就是一个解释。在每一种解释下，谓词公式都具有一种真值（T或F）。定义定义2-7 设D为谓词公式P的个体域，若对P中的个体常量、函数和谓词按照如下规定赋值：（a）为每个个体常量指派D中的一个元素；（b）为每个n元函数指派一个从Dn到D的映射，其中 Dn=(x1,x2,xn)|x1,x2,xn D （c）为每个n元谓词指派一个从Dn到F，T的映射；则称这些指派为公式P在D上的一个解释I。例2-1 给定公式B=(x)(y)P(x,y)和个体域D1=1，2。求：公式B的解释及在该解释下B的真值。解：x,y都可以取D1中的任何值，于是可有以下几种情况：P(1,1)，P(1,2)，P(2,1)，P(2,2)。对这4个公式，每一个都可以指派真假（T，F）两个值，则共有24=16个不同的组合，构成16个不同的解释。P(1,1)P(1,2)P(2,1)P(2,2)I1 T T T TI2 T T T FI3 T T F TI4 T T F FI5 T F T TI6 T F T FI7 T F F TI8 T F F FI9FTTTI10FTTFI11FTFTI12FTFFI13FFTTI14FFTFI15FFFTI16FFFF如对I6，则有B(I6)=T。因为：对x=1时，存在一个y=1，有P(x,y)=P(1,1)=T。对x=2时，存在一个y=1，有P(x,y)=P(2,1)=T。所以在I6解释下，公式B为真。如 D2=1，2，3 根据上面的分析，在D2上的解释应有29个。下面是其中的一个解释：I:P(1,1)P(1,2)P(1,3)P(2,1)P(2,2)P(2,3)P(3,1)P(3,2)P(3,3)T T T F F T F F F 由于x=3时，不存在一个y使P(x,y)=T。所以在这个解释下公式B为假，即B(I)=F。例2-2 给定公式 A=(x)(P(x)Q(f(x),a)和个体域 D=0，1。公式中有个体常量a和一元函数f(x)，所以按定义可以如下构造对它的解释I1：（a）给个体常量a赋一个D中的元素如：（b）给一元函数f(x)指派一个由D1到D的映射，如：（c）对每个谓词符号指派一个由D1到F，T的映射（对P(x)）或D2到F，T的映射（对Q(f(x),a)），如：P(0)P(1)Q(0,0)Q(0,1)Q(1,0)Q(1,1)F T T (T)F (T)其中（T）表示不可能出现的状态，因为a已经取值0，不可能再取值1，所以不可能出现Q(0,1)或Q(1,1)这两种状态。要考察在这个解释下公式A的真假，根据量词(x)要对所有x进行考察。由于：对x=0时，P(x)Q(f(x),a)=P(0)Q(f(0),0)=P(0)Q(1,0)=FF=T对x=1时P(x)Q(f(x),a)=P(1)Q(f(1),0)=P(1)Q(0,0)=TT=T所以在此解释下，公式A为真，即A(I1)=T。还可以在D上定义如下的解释I2：f(0)f(1)01a1P(0)P(1)Q(0,0)Q(0,1)Q(1,0)Q(1,1)TF(T)F(T)F则当x=0时，P(x)Q(f(x),a)=P(0)Q(f(0),1)=P(0)Q(0,1)=TF=F当x=1时，P(x)Q(f(x),a)=P(1)Q(f(1),1)=P(1)Q(1,1)=FT=T所以在解释I2下公式A为假，即A(I2)=F。在上述个体域D上，公式A有多少种解释？对a有两种解释，对f(x)有22种解释（nn），对P(x)有22种解释（2n），对Q(f(x),a)有22种解释（2n），则在D上，A共有2222222=27种有意义的解释。如果D中含有n个元素，则公式A的有意义解释的个数为：nnn2n2n=22nnn+1 将解释中各个值一一代入P(x)Q(f(x),a)中就可得出其真值。定义定义2-8 公式B是相容的（又叫可满足的或非永假的），当且仅当存在一个解释I，使得B在I 下为T，即 B相容（可满足）(I)B(I)这时就称I 满足B，又称I 是B的一个模型。定义定义2-9 公式B是不相容的（又叫不可满足的或永假的），当且仅当没有任何能满足B的解释存在，即 B不相容（不可满足）(I)B(I)定义定义2-10 公式B是永真的，当且仅当所有解释I 都满足B，即 B永真 (I)B(I)定义定义2-11 公式B是非永真的，当且仅当不是所有的解释I 都满足B，即 B非永真 (I)B(I)这就是说公式B在有些解释下为真，有些解释下为假。推论 B相容 (B)非永真 B不相容（永假）(B)永真 B永真 B相容 B不相容（永假）B非永真 定义定义2-12 公式G是B1,B2,Bn的逻辑结论（推论），当且仅当对每一个解释I，如果B1,B2,Bn都为T，则G也为T。这时称B1,B2,Bn为G的前提。定理定理2-1 G为B1,B2,Bn的逻辑结论，当且仅当 (B1B2Bn)G 证明：若(B1B2Bn)G 成立，即 （B1B2Bn)G 是永真式，也就是说在任一个使B1,B2,Bn都为真的解释下，G也为真，可见G是B1,B2,Bn的逻辑结论。反之，若 (B1B2Bn)G 不成立，即 (B1B2Bn)G 为非永真式，也就是说存在使B1,B2,Bn都为真的解释，但却不满足G，所以G不是B1,B2,Bn的逻辑结论。（证毕）定理定理2-2 G为B1,B2,Bn的逻辑结论，当且仅当 (B1B2Bn)G 是不相容的（永假）。证明：由定理1知，G是B1,B2,Bn的逻辑结论，当且仅当 (B1B2Bn)G 即 (B1B2Bn)G 为永真式，也就是说 (B1B2Bn)G)是不相容（永假）的，因为永真式的否定是不相容的。而(B1B2Bn)G)(B1B2Bn)G)(B1B2Bn)G 故(B1B2Bn)G是不相容的。（证毕）定理2-2是反证法的理论依据。6谓词公式中的等价和蕴涵式 定义定义2-13 设P与Q是两个谓词公式，D是它们共同的个体域。若对D上的任何一个解释，P与Q的真值都相同，则称公式P和Q在域D上是等价的。如果在任何个体域上P和Q都等价，则称P和Q是等价的，记做：P Q。下面是一些常用的等价式：交换律PQQP PQQP结合律(PQ)RP(QR)(PQ)RP(QR)分配律P(QR)(PQ)(PR)P(QR)(PQ)(PR)德摩根定律(PQ)P Q (PQ)P Q双重否定律(P)P吸收律P(PQ)P P(PQ)P补余律 PP T PP F逆否定律PQ QP连结词化归律PQ PQ PQ (PQ)(QP)PQ (PQ)(PQ)量词转换律(x)P (x)(P)(x)P (x)(P)量词分配律(x)(PQ)(x)P(x)Q (x)(PQ)(x)P(x)Q 注意，量词分配律是全称量词对合取的分配、存在量词对析取的分配。定义2-14 对于谓词公式P和Q，如果PQ是永真式，则称P永真蕴涵Q，且称Q为P的逻辑结论，P为Q的前提，记作PQ。下面是一些常用的永真蕴涵式：化简式PQP PQQ附加式PPQ QPQ析取假论P并且PQQ假言推理P并且PQQ拒取式Q并且PQ P假言三段论PQ且QRPR两难推理PQ且PR且QRR（证明：如果R，则P，Q，此时PQ为假，与前提相矛盾）全称固化(x)P(x)P(y)，其中y是个体域上的任一个 体，利用此蕴涵式可以消去公式中的全称量词。存在固化(x)P(x)P(y)，其中y是个体域上某个使P(y)为真的个体，利用此式可以消去公式中的存在量词。7子句集合 为了便于进行谓词演算，应先将公式在不失原意的情况下进行变形，使之成为某种标准形，这种标准形也称为范式。前束范式和斯克林（skolem）范式。（1）前束范式 所谓前束范式，就是指在一个谓词公式中，如果它的所有量词均非否定地出现在公式的最前面，且它的辖域一直延伸到公式之尾，同时公式中不出现连结符号、，则这种形式的公式就是前束范式，形如 (Q1x1)(Q2x2)(Qnxn)M 其中Qi或为或为，M称为母式。例如，公式 (x)(y)(z)(P(x,y)Q(x,z)R(x,y,z)（2）斯克林范式在离散数学中，斯克林范式的定义是存在量词全部位于全称量词的前面，形如：(x)(y)(z)(P(x)Q(y)F(z)而在人工智能中，斯克林范式指在前束范式中消去全部存在量词后得到的公式，形如 (x1)(x2)(xn)M(x1,xn)即母式M全部受全称量词约束。将合式公式WFF（well formed formula）化成skolem标准形的步骤如下：（a）利用等价式PQ PQ消去连结符号“”。（b）在所有可能地方将否定符去掉或将否定符内移，直至使其辖域减小到一个原子公式。（c）将合式公式WFF中的变量标准化，使得每一量词的约束变量有唯一的名字。（d）用skolem函数将所有的存在量词消去。（e）将合式公式化为前束范式，即把所有的全称量词都移到合式公式的左边，使每个的辖域均为整个WFF。（f）将母式化为合取范式。（g）去掉全称量词。因为此时公式中的所有变量都被全称量词约束，已无存在必要，故可以消去。至此已化为skolem标准形。定定义义2-15 不含有任何连结词的谓词公式称为原子公式，简称原子。原子和原子的否定统称文字。例如，P(x),Q(y,z),R(u,v,w)都是原子公式。定义定义2-16 子句是由文字组成的析取式。例如，P(x)Q(y,z),P(x)R(u,v,w)Q(y,z)都是子句。定义定义2-17 不含任何文字的子句称为空子句，记为NIL。由于空子句不含任何文字，它不能被任何解释所满足，所以空子句是永假的、不可满足的。定义定义2-18 子句集即由子句构成的集合。注意，可通过重新命名的方法，使子句集里各个子句间无同名变量。将合式公式化成子句集的方法是：首先通过上面所列的步骤(a)(g)把公式化成skolem标准形，接着进行如下处理:（h）消去skolem标准形中的符号，写成集合的形式，各子句间用逗号分隔。（i）重命名子句中的变量，使得一个变量名只出现在一个子句中。比如：P(x)Q(x)L(x,y)P(x)Q(y)Q(z)L(z,y)可被重命名为 P(x1)Q(x1)L(x1,y1)P(x2)Q(y2)Q(z)L(z,y3)例2-3 把公式 G=(x)(y)P(x,y)(y)(Q(x,y)R(x,y)化成子句集的形式。解：消去条件符号：(x)(y)P(x,y)(y)(Q(x,y)R(x,y)否定符内移：(x)(y)P(x,y)(y)(Q(x,y)R(x,y)约束变量标准化，使每个量词的约束变量唯一：(x)(y)P(x,y)(z)(Q(x,z)R(x,z)把存在量词skolem化：因(y)、(z)都在(x)的辖域内，故y和z都是x的函数。即(x)(P(x,f(x)(Q(x,g(x)R(x,g(x)把母式化成合取范式：(x)(P(x,f(x)Q(x,g(x)(P(x,f(x)R(x,g(x)去掉全称量词：(P(x,f(x)Q(x,g(x)(P(x,f(x)R(x,g(x)去掉符号，写成子句集合形式：S=P(x,f(x)Q(x,g(x),P(x,f(x)R(x,g(x)或写成无括号的子句形式：P(x,f(x)Q(x,g(x)P(x,f(x)R(x,g(x)重命名，使各子句中变量不同名：P(x,f(x)Q(x,g(x)P(y,f(y)R(y,g(y)这种形式才是定理证明需要的标准形式。定理定理2-3 设有谓词公式B，其标准形的子句集为S，则B不可满足当且仅当S不可 满足。根据这个定理，对于不可满足的公式B，可以通过证明它的子句集S的不可满足性来证明B的不可满足性。说明：一般情况下谓词公式 B和其标准形的子句集 S并不完全等价，只是在不可满足性方面才等价。例如，设有公式 B=(x)P(x)其标准形为S=P(a)。可给如下一个解释I：个体域D=0，1，取a=0，并指派P(0)=F，P(1)=T。则在I下B为真：B(I)=T。因为存在一个x(=1)，使P(x)=P(1)=T。而在I下S为假，S(I)=F。由此可见，S和B是不等价的，这是因为公式在化为标准形的过程中失去了一些信息。如果一个公式本身就是个合取式，形如B=B1B2Bn，这时在把B化子句集S时，可通过分别把组成B的各个合取式B1,B2,Bn等先行转化成子句集S1,S2,Sn，然后通过或运算求得S：S=S1S2Sn 例如，求公式B的子句集：B=(x)(y)(z)(P(x,y)P(y,z)Q(x,z)(y)(xP(x,y)这个公式可以当作是下面两个公式的合取：B1=(x)(y)(z)(P(x,y)P(y,z)Q(x,z)B2=(y)(x)P(x,y)先分别求出B1、B2的子句集S1、S2：S1=P(x,y)P(y,z)Q(x,z)S2=P(f(y),y)则B的子句集为：S=S1S2 =P(x,y)P(y,z)Q(x,z),P(f(y),y)应该说明，这样求得的子句集S并不完全等同于B的子句集，设B的子句集为SB，即 SBS1S2Sn 但在不可满足性的意义下，它们却是等价的，即 SB不可满足S1S2Sn不可满足 而这里求子句集的目的就是要利用其不可满足性这一点，所以就可以把S1S2Sn作为B的子句集来使用，这样可以大大减少求公式B真正的子句集的工作量。