命题逻辑与谓词逻辑PPT学习教案课件.pptx

《命题逻辑与谓词逻辑PPT学习教案课件.pptx》由会员分享，可在线阅读，更多相关《命题逻辑与谓词逻辑PPT学习教案课件.pptx（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1命题逻辑与谓词逻辑命题逻辑与谓词逻辑2.1 命命 题题 逻逻 辑辑 1命题 定义2-1 命题：具有真假意义的语句。定义2-2 原子命题：如果一个命题不能被进一步分解成更为简单的命题，则该命题就称为原子命题。第1页/共47页2连接词n n：称为“非”或“否定”。n n：称为“析取”，PQ读作“P或Q”。n n：称为“合取”，PQ读作“P与Q”。n n：称为“条件”。PQ。n n：称为“双条件”。PQ,“P当且仅当Q”。连接词优先级：，第2页/共47页 3合式公式 定义2-3 合式公式（Well-Formed Formula，WFF）孤立的命题变元或逻辑常量（T，F）是合式公式；如果A是一

2、个合式公式，则A也是一个合式公式；如果A、B是合式公式，则AB，AB，AB，AB也都是合式公式；当且仅当有限次使用规则后得到的公式才是合式公式。第3页/共47页 永真式（或重言式）：给定一个公式，如果对于所有的真值指派，它的值都为真（T），则称该公式为永真式（或重言式）；永假式（或称该公式为不可满足的）：如对于所有的真值指派，它的值都为假（F），则称该公式为永假式（或称该公式为不可满足的）。非永假的公式称为可满足的公式。第4页/共47页 4等价和永真蕴涵 定义2-4 等价：设A，B是两个命题公式，P1，P2，Pn是出现在A、B中的所有命题变元。如果对于这n个变元的任何一个真值指派的集合，A和B

3、的真值都相等，则称公式A等价于公式B，记作AB。“等价”又可定义为：AB当且仅当AB是一个永真式。第5页/共47页 定义2-5 永真蕴涵：命题公式A永真蕴涵命题公式B，当且仅当AB是一个永真式，记作AB，读作“A永真蕴涵B”，简称“A蕴涵B”。第6页/共47页2.2 谓谓 词词 逻逻 辑辑n n1谓词与个体 原子命题被分解为谓词和个体两部分。n n 个体是指可以单独存在的事物，它可以是一个抽象的概念，也可以是一个具体的东西。n n谓词是用来刻画个体性质或个体间关系的词。如：POET(libai)POET(dufu)GREAT(libai,dufu)一般用大写字母表示谓词，小写字母表示个体。第7

4、页/共47页 元数:谓词中包含的个体数目称为谓词的。一元谓词:与一个个体相连的谓词，如POET(x)；多元谓词:与多个个体相连的谓词叫，如GREAT(x,y)(二元谓词)。个体域:任何个体的变化都有范围。谓词变元命名式:一个n元谓词常被表示成P(x1 1,x2 2,xn n)。第8页/共47页 2量词n n全称量词:“(x)P(x)”表示命题“对个体域中所有的个体x，谓词P(x)均为T”。n n存在量词:“(x)Q(x)”表示命题“在个体域中存在某个个体使谓词Q(x)为T”。其中“”叫存在量词。设x的取值范围是甲，乙，丙三人，y的取值范围是bora,jetta,santana三种车型。(x)(

5、y)LIKE(x,y)表示甲、乙、丙三人都喜爱bora,jetta,santana中的某一种车型；(x)(y)LIKE(x,y)表示甲、乙、丙三人都喜爱bora,jetta,santana三种车型。第9页/共47页 3合式谓词公式原子公式:若P为不能再分解的n元谓词变元，x1 1,x2 2,xn n是个体变元，则称P(x1 1,x2 2,xn n)为原子公式或原子谓词公式。当n=0时，P表示命题变元或原子命题公式。所以命题逻辑是谓词逻辑的特例 第10页/共47页 定义定义定义定义2-62-6 谓词合式公式谓词合式公式（简称（简称公式公式）的定义如）的定义如下：下：原子公式是合式公式；原子公式是

6、合式公式；若若AA是合式公式，则是合式公式，则AA也是合式公式；也是合式公式；若若AA和和B B都是合式公式，则都是合式公式，则(AAB B)，(AAB B)，(AAB B)，(AAB B)也都是合式公式；也都是合式公式；若若AA是合式公式，是合式公式，x x是任意变元，且是任意变元，且AA中无中无(x x)或或(x x)出现，则出现，则(x x)AA或或(x x)AA也都是合也都是合式公式；式公式；当且仅当有限次使用规则当且仅当有限次使用规则得到的公得到的公式是合式公式。式是合式公式。第11页/共47页 4 4量词的辖域与变元的约束量词的辖域与变元的约束 约束变元约束变元,自由变元自由变元

7、。公式公式 约束变元约束变元 自由变元自由变元 (x x)P P(x x,y y)x yx y (x x)Q Q(y y)无无 y y (x x)()(P P(x x)()(y y)Q Q(x x,y y)x x,y y (y y)P P(x x)Q Q(x x)y xy x第12页/共47页 5谓词公式的解释 谓词公式中的谓词变元、命题变元和自由个体变元，个体常量和函数的一种指派就是一个解释。在每一种解释下，谓词公式都具有一种真值（T或F）。第13页/共47页 定义定义定义定义2-72-7 设设D D为谓词公式为谓词公式P P的个体域，若对的个体域，若对P P中中的个体常量、函数和谓词按照如

8、下规定赋值：的个体常量、函数和谓词按照如下规定赋值：（a a）为每个个体常量指派）为每个个体常量指派D D中的一个元素；中的一个元素；（b b）为每个）为每个n n元函数指派一个从元函数指派一个从D Dn n到到D D的映射，的映射，其中其中 D Dn n=(x x1 1,x x2 2,x xn n)|x x1 1,x x2 2,x xn n D D （c c）为每个）为每个n n元谓词指派一个从元谓词指派一个从D Dn n到到FF，TT的的映射；映射；则称这些指派为公式则称这些指派为公式P P在在D D上的一个解释上的一个解释I I。第14页/共47页 例2-1 给定公式B=(x)(y)P(

9、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个不同的解释。第15页/共47页 P P(1,1)(1,1)P P(1,2)(1,2)P P(2,1)(2,1)P P(2,2)(2,2)I I1 1 T T T T T T T TI I2 2 T T T F T T T FI I3 3 T T F T T T F TI I4 4 T T F F T T F FI I5 5 T

10、 F T T T F T TI I6 6 T F T F T F T FI I7 7 T F F T T F F TI I8 8 T F F F 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为真。第16页/共47页如如 D D2 2=11，2 2，33 根据上面的分析，在根据上面的分析，在D D2 2上的解释应有上的解释应有2 29

11、9个。个。下面是其中的一个解释：下面是其中的一个解释：I I:P P(1,1)(1,1)P P(1,2)(1,2)P P(1,3)(1,3)P P(2,1)(2,1)P P(2,2)(2,2)P P(2,3)(2,3)P P(3,1)(3,1)P P(3,2)(3,2)P P(3,3)(3,3)T T T T T T F F F F T T F F F F F F 由于由于x x=3 3时，不存在一个时，不存在一个y y使使P P(x x,y y)=T T。所以在这个解释下公式。所以在这个解释下公式B B为假，即为假，即B B(I I)=F F。第17页/共47页 例例2-22-2 给定公式给

12、定公式 AA=(x x)()(P P(x x)Q Q(f f(x x),),a a)和个体域和个体域 D D=00，11。公式中有个体常量。公式中有个体常量a a和一元函数和一元函数f f(x x)，所以，所以按定义可以如下构造对它的解释按定义可以如下构造对它的解释I I1 1：（a a）给个体常量）给个体常量a a赋一个赋一个D D中的元素如：中的元素如：（b b）给一元函数）给一元函数f f(x x)指派一个由指派一个由D D1 1到到D D的映射，如：的映射，如：第18页/共47页（c c）对每个谓词符号指派一个由）对每个谓词符号指派一个由D D1 1到到FF，TT的映射（对的映射（对P

13、 P(x x)）或）或D D2 2到到FF，TT的映射（对的映射（对Q Q(f f(x x),),a a)），如：），如：P P(0)(0)P P(1)(1)Q Q(0,0)(0,0)Q Q(0,1)(0,1)Q Q(1,0)(1,0)Q Q(1,1)(1,1)F F T T T T (T)(T)F F (T)(T)其中（其中（T T）表示不可能出现的状态，因为）表示不可能出现的状态，因为a a已经取值已经取值0 0，不可能再取值，不可能再取值1 1，所以不，所以不可能出现可能出现Q Q(0,1)(0,1)或或Q Q(1,1)(1,1)这两种状态。这两种状态。要考察在这个解释下公式要考察在这个

14、解释下公式AA的真假，根据量词的真假，根据量词(x x)要对所有要对所有x x进行考察。由于：对进行考察。由于：对x x=0 0时，时，P P(x x)Q Q(f f(x x),),a a)=P P(0)(0)Q Q(f f(0),0)(0),0)=P P(0)(0)Q Q(1,0)(1,0)=FFFF=T T对对x x=1 1时时P P(x x)Q Q(f f(x x),),a a)=P P(1)(1)Q Q(f f(1),0)(1),0)=P P(1)(1)Q Q(0,0)(0,0)=TTTT=T T所以在此解释下，公式所以在此解释下，公式AA为真，即为真，即AA(I I1 1)=T T。

15、第19页/共47页 还可以在还可以在D D上定义如下的解释上定义如下的解释I I2 2：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。第20页/共47页 在上述个体域在上述个体域D D上，公式上，公式AA有多少种解释？有多少种解释？对对a a有两种解释，对有两种解释，对f f(x x)有有2

16、22 2种解释（种解释（n nn n ），对），对P P(x x)有有2 22 2种解释（种解释（2 2n n ），对），对Q Q(f f(x x),),a a)有有2 22 2种解释种解释（2 2n n ），则在），则在D D上，上，AA共有共有2 2 2 22 2 2 22 2 2 22 2=2 27 7种有种有意义的解释。意义的解释。如果如果D D中含有中含有n n个元素，则公式个元素，则公式AA的有意义解释的有意义解释的个数为：的个数为：n n n nn n 2 2n n 2 2n n=2 22 2n n n nn n+1+1 将解释中各个值一一代入将解释中各个值一一代入P P(x x

17、)Q Q(f f(x x),),a a)中就可得中就可得出其真值。出其真值。第21页/共47页 定义定义2-8 公式B是相容的（又叫可满足的或非永假的），当且仅当存在一个解释I，使得B在I 下为T，即 B相容（可满足）(I)B(I)这时就称I 满足B，又称I 是B的一个模型。定义定义2-9 公式B是不相容的（又叫不可满足的或永假的），当且仅当没有任何能满足B的解释存在，即 B不相容（不可满足）(I)B(I)第22页/共47页 定义定义定义定义2-102-10 公式公式B B是是永真永真的，当且仅当所有解释的，当且仅当所有解释I I 都满足都满足B B，即，即 B B永真永真 (I I)B B(

18、I I)定义定义定义定义2-112-11 公式公式B B是是非永真非永真的，当且仅当不是所的，当且仅当不是所有的解释有的解释I I 都满足都满足B B，即，即 B B非永真非永真 (I I)B B(I I)这就是说公式这就是说公式B B在有些解释下为真，有些解释下在有些解释下为真，有些解释下为假。为假。第23页/共47页 推论 B相容 (B)非永真 B不相容（永假）(B)永真 B永真 B相容 B不相容（永假）B非永真第24页/共47页 定义定义2-12 公式G是B1,B2,Bn的逻辑结论（推论），当且仅当对每一个解释I，如果B1,B2,Bn都为T，则G也为T。这时称B1,B2,Bn为G的前提。

19、第25页/共47页 定理定理定理定理2-12-1 G G为为B B1 1,B B2 2,B Bn n的逻辑结论，当且仅当的逻辑结论，当且仅当 (B B1 1 B B2 2 B Bn n)G G 证明：证明：若若 (B(B1 1 B B2 2 B Bn n)G G 成立，即成立，即 （B B1 1 B B2 2 B Bn n)G)G 是永真式，也就是说在任一个使是永真式，也就是说在任一个使B B1 1,B,B2 2,B,Bn n都为真的解都为真的解释下，释下，GG也为真，可见也为真，可见GG是是B1,B2,BnB1,B2,Bn的逻辑结论。的逻辑结论。反之，若反之，若 (B(B1 1 B B2 2

20、 B Bn n)G G 不成立，即不成立，即 (B(B1 1 B B2 2 B Bn n)G)G 为非永真式，也就是说存在使为非永真式，也就是说存在使B B1 1,B,B2 2,B,Bn n都为真的解释，都为真的解释，但却不满足但却不满足GG，所以，所以GG不是不是B B1 1,B,B2 2,B,Bn n的逻辑结论。的逻辑结论。（证毕）（证毕）第26页/共47页 定理定理定理定理2-22-2 G G为为B B1 1,B B2 2,BnBn的逻辑结论，当且仅当的逻辑结论，当且仅当 (B B1 1 B B2 2 B Bn n)G G 是不相容的是不相容的（永假）（永假）。证明：由定理证明：由定理1

21、 1知，知，G G是是B B1 1,B B2 2,B Bn n的逻辑结论，当且仅当的逻辑结论，当且仅当 (B B1 1 B B2 2 B Bn n)G G 即即 (B B1 1 B B2 2 B Bn n)G G 为永真式，也就是说为永真式，也就是说 (B B1 1 B B2 2 B Bn n)G G)是不相容是不相容（永假）（永假）的，因为永真式的否定是不相容的。的，因为永真式的否定是不相容的。而而 (B B1 1 B B2 2 B Bn n)G G)(B B1 1 B B2 2 B Bn n)G G)(B B1 1 B B2 2 B Bn n)G G 故故(B B1 1 B B2 2 B

22、Bn n)G G是不相容的。是不相容的。（证毕）（证毕）定理定理2-22-2是反证法的理论依据。是反证法的理论依据。第27页/共47页 6 6谓词公式中的等价和蕴涵式谓词公式中的等价和蕴涵式 定义定义定义定义2-132-13 设设P P与与Q Q是两个谓词公式，是两个谓词公式，D D是它们是它们共同的个体域。若对共同的个体域。若对D D上的任何一个解释，上的任何一个解释，P P与与Q Q的真值都相同，则称公式的真值都相同，则称公式P P和和Q Q在域在域D D上是等价的。上是等价的。如果在任何个体域上如果在任何个体域上P P和和Q Q都等价，则称都等价，则称P P和和Q Q是是等价的，记做：等

23、价的，记做：P P Q Q。第28页/共47页 下面是一些常用的等价式：下面是一些常用的等价式：n n交换律交换律P PQ QQ QP P P PQ QQ QP Pn n结合律结合律(P PQ Q)R RP P(Q QR R)(P PQ Q)R RP P(Q QR R)n n分配律分配律P P(Q QR R)(P PQ Q)(P PR R)P P(Q QR R)(P PQ Q)(P PR R)n n德德 摩根定律摩根定律 (P PQ Q)P P Q Q (P PQ Q)P P Q Qn n双重否定律双重否定律 (P P)P P第29页/共47页n n吸收律吸收律P P(P PQ Q)P P P

24、 P(P PQ Q)P Pn n补余律补余律 P PP P T T P PP P F Fn n逆否定律逆否定律P PQ Q Q QP Pn n连结词化归律连结词化归律 P PQ Q P PQ Q P PQ Q (P PQ Q)(Q QP P)P PQ Q (P PQ Q)(P PQ Q)n n量词转换律量词转换律(x x)P P (x x)()(P P)(x x)P P (x x)()(P P)n n量词分配律量词分配律(x x)()(P PQ Q)(x x)P P(x x)Q Q (x x)()(P PQ Q)(x x)P P(x x)Q Q 注意，量词分配律是全称量词对合取的分配、存在量注

25、意，量词分配律是全称量词对合取的分配、存在量词对析取的分配。词对析取的分配。第30页/共47页 定义2-14 对于谓词公式P和Q，如果PQ是永真式，则称P永真蕴涵Q，且称Q为P的逻辑结论，P为Q的前提，记作PQ。第31页/共47页 下面是一些常用的永真蕴涵式：下面是一些常用的永真蕴涵式：n n化简式化简式P PQ QP P P PQ QQ Qn n附加式附加式P PP PQ Q Q QP PQ Qn n析取假论析取假论P P并且并且P PQ QQ Qn n假言推理假言推理P P并且并且P PQ QQ Qn n拒取式拒取式Q Q并且并且P PQ Q P Pn n假言三段论假言三段论P PQ Q且

26、且Q QR RP PR Rn n两难推理两难推理P PQ Q且且P PR R且且Q QR RR R（证明：如果（证明：如果R R，则，则P P，Q Q，此时，此时P PQ Q为假，与前提相矛盾）为假，与前提相矛盾）n n全称固化全称固化(x x)P P(x x)P P(y y)，其中，其中y y是个体域上的是个体域上的任一任一个个 体，体，利用此蕴涵式可以消去公式中的全称量词。利用此蕴涵式可以消去公式中的全称量词。n n存在固化存在固化(x x)P P(x x)P P(y y)，其中，其中y y是个体域上是个体域上某个某个使使P P(y y)为真为真的个体，的个体，利用此式可以消去公式中的存在

27、量词。利用此式可以消去公式中的存在量词。第32页/共47页7 7子句集合子句集合 为为了了便便于于进进行行谓谓词词演演算算，应应先先将将公公式式在在不不失失原原意意的的情情况况下下进进行行变变形形，使使之之成成为为某某种种标标准准形形，这种标准形也称为这种标准形也称为范式范式。前束范式和斯克林（前束范式和斯克林（skolemskolem）范式。）范式。第33页/共47页 （1 1）前束范式）前束范式 所谓前束范式，就是指在一个谓词公式中，如果它的所谓前束范式，就是指在一个谓词公式中，如果它的所有量词均所有量词均非否定非否定地出现在公式的最前面，且它的辖域地出现在公式的最前面，且它的辖域一直延伸

28、到公式之尾，同时公式中不出现连结符号一直延伸到公式之尾，同时公式中不出现连结符号、，则这种形式的公式就是前束范式，形如，则这种形式的公式就是前束范式，形如 (Q Q1 1x x1 1)()(Q Q2 2x x2 2)()(Q Qn nx xn n)MM 其中其中Q Qi i或为或为 或为或为，MM称为母式。称为母式。例如，公式例如，公式 (x x)()(y y)()(z z)()(P P(x x,y y)Q Q(x x,z z)R R(x x,y y,z z)第34页/共47页（2）斯克林范式n n在离散数学中，斯克林范式的定义是存在量词全部位于全称量词的前面，形如：(x)(y)(z)(P(x

29、)Q(y)F(z)n n而在人工智能中，斯克林范式指在前束范式中消去全部存在量词后得到的公式，形如 (x1 1)(x2 2)(xn n)M(x1 1,xn n)即母式M全部受全称量词约束。第35页/共47页 将合式公式将合式公式WFFWFF（well formed formulawell formed formula）化成）化成skolemskolem标准形的步骤如标准形的步骤如下：下：（a a）利用等价式）利用等价式P PQ Q P PQ Q消去连结符号消去连结符号“”“”。（b b）在所有可能地方将否定符去掉或将否定符内移，直至使其辖域减小）在所有可能地方将否定符去掉或将否定符内移，直至使

30、其辖域减小到一个原子公式。到一个原子公式。（c c）将合式公式）将合式公式WFFWFF中的变量标准化，使得每一量词的约束变量有唯一中的变量标准化，使得每一量词的约束变量有唯一的名字。的名字。（d d）用）用skolemskolem函数将所有的存在量词消去。函数将所有的存在量词消去。（e e）将合式公式化为前束范式，即把所有的全称量词都移到合式公式的）将合式公式化为前束范式，即把所有的全称量词都移到合式公式的左边，使每个左边，使每个 的辖域均为整个的辖域均为整个WFFWFF。（f f）将母式化为合取范式。）将母式化为合取范式。（g g）去掉全称量词。因为此时公式中的所有变量都被全称量词约束，已）

31、去掉全称量词。因为此时公式中的所有变量都被全称量词约束，已无存在必要，故可以消去。无存在必要，故可以消去。至此已化为至此已化为skolemskolem标准形。标准形。第36页/共47页 定定定定义义义义2-152-15 不不含含有有任任何何连连结结词词的的谓谓词词公公式式称称为为原原子子公公式式，简简称称原原子子。原原子子和和原原子子的的否否定定统统称称文字文字。例如，例如，P P(x x),),Q Q(y y,z z),),R R(u u,v v,w w)都是原子公式。都是原子公式。定义定义定义定义2-162-16 子句子句是由文字组成的析取式。是由文字组成的析取式。例如，例如，P P(x

32、x)Q Q(y y,z z),),P P(x x)R R(u u,v v,w w)Q Q(y y,z z)都是子句。都是子句。第37页/共47页 定义定义定义定义2-172-17 不含任何文字的子句称为不含任何文字的子句称为空子句空子句，记，记为为NILNIL。由于空子句不含任何文字，它不能被任何解由于空子句不含任何文字，它不能被任何解释所满足，所以空子句是永假的、不可满足的。释所满足，所以空子句是永假的、不可满足的。定义定义定义定义2-182-18 子句集即由子句构成的集合。子句集即由子句构成的集合。注意，可通过重新命名的方法，使子句集里各注意，可通过重新命名的方法，使子句集里各个子句间无同

33、名变量。个子句间无同名变量。第38页/共47页 将合式公式化成子句集的方法是：首先通过上面所列的将合式公式化成子句集的方法是：首先通过上面所列的步骤步骤(a)(a)(g)(g)把公式化成把公式化成skolemskolem标准形，接着进行如下处标准形，接着进行如下处理理:（h h）消去）消去skolemskolem标准形中的标准形中的符号，写成集合的形式，各符号，写成集合的形式，各子句间用逗号分隔。子句间用逗号分隔。（i i）重命名子句中的变量，使得一个变量名只出现在一个）重命名子句中的变量，使得一个变量名只出现在一个子句中。比如：子句中。比如：P P(x x)Q Q(x x)L L(x x,y

34、 y)P P(x x)Q Q(y y)Q Q(z z)L L(z z,y y)可被重命名为可被重命名为 P P(x x1 1)Q Q(x x1 1)L L(x x1 1,y y1 1)P P(x x2 2)Q Q(y y2 2)Q Q(z z)L L(z z,y y3 3)第39页/共47页 例例2-32-3 把公式把公式 G G=(=(x x)()(y y)P P(x x,y y)(y y)()(Q Q(x x,y y)R R(x x,y y)化成子句集的形式。化成子句集的形式。解：解：消去条件符号消去条件符号：(x x)()(y y)P P(x x,y y)(y y)()(Q Q(x x,

35、y y)R R(x x,y y)否定符内移：否定符内移：(x x)()(y y)P P(x x,y y)(y y)()(Q Q(x x,y y)R R(x x,y y)约束变量标准化，使每个量词的约束变量唯一：约束变量标准化，使每个量词的约束变量唯一：(x x)()(y y)P P(x x,y y)(z z)()(Q Q(x x,z z)R R(x x,z z)把存在量词把存在量词skolemskolem化：化：因因(y y)、(z z)都在都在(x x)的辖域内，故的辖域内，故y y和和z z都是都是x x的函数。的函数。即即 (x x)(P P(x x,f f(x x)(Q Q(x x,g

36、 g(x x)R R(x x,g g(x x)第40页/共47页 把母式化成合取范式：把母式化成合取范式：(x x)()(P P(x x,f f(x x)Q Q(x x,g g(x x)(P P(x x,f f(x x)R R(x x,g g(x x)去掉全称量词：去掉全称量词：(P P(x x,f f(x x)Q Q(x x,g g(x x)(P P(x x,f f(x x)R R(x x,g g(x x)去掉去掉符号，写成子句集合形式：符号，写成子句集合形式：S S=P P(x x,f f(x x)Q Q(x x,g g(x x),),P P(x x,f f(x x)R R(x x,g g

37、(x x)或写成无括号的子句形式：或写成无括号的子句形式：P P(x x,f f(x x)Q Q(x x,g g(x x)P P(x x,f f(x x)R R(x x,g g(x x)重命名，使各子句中变量不同名：重命名，使各子句中变量不同名：P P(x x,f f(x x)Q Q(x x,g g(x x)P P(y y,f f(y y)R R(y y,g g(y y)这种形式才是定理证明需要的标准形式。这种形式才是定理证明需要的标准形式。第41页/共47页 定理定理2-3 设有谓词公式B，其标准形的子句集为S，则B不可满足当且仅当S不可 满足。根据这个定理，对于不可满足的公式B，可以通过证

38、明它的子句集S的不可满足性来证明B的不可满足性。第42页/共47页 说明：说明：一般情况下谓词公式一般情况下谓词公式 B B和其标准形的子句集和其标准形的子句集 S S并不并不完全等价，只是在不可满足性方面才等价。例如，设有完全等价，只是在不可满足性方面才等价。例如，设有公式公式 B B=(=(x x)P P(x x)其标准形为其标准形为S S=P P(a a)。可给如下一个解释可给如下一个解释I I：个体域：个体域D D=0=0，11，取，取a a=0=0，并指，并指派派P P(0)=F(0)=F，P P(1)=T(1)=T。则在。则在I I下下B B为真：为真：B B(I I)=T)=T。

39、因为存在。因为存在一个一个x x(=1)(=1)，使，使P P(x x)=)=P P(1)=T(1)=T。而在。而在I I下下S S为假，为假，S S(I I)=F)=F。由此可见，由此可见，S S和和B B是不等价的，这是因为公式在化为标是不等价的，这是因为公式在化为标准形的过程中失去了一些信息。准形的过程中失去了一些信息。第43页/共47页 如果一个公式本身就是个合取式，形如B=B1B2Bn，这时在把B化子句集S时，可通过分别把组成B的各个合取式B1,B2,Bn等先行转化成子句集S1,S2,Sn，然后通过或运算求得S：S=S1S2Sn第44页/共47页 例如，求公式例如，求公式B B的子句

40、集：的子句集：B B=(x x)()(y y)()(z z)()(P P(x x,y y)P P(y y,z z)Q Q(x x,z z)(y y)()(x xP P(x x,y y)这个公式可以当作是下面两个公式的合取：这个公式可以当作是下面两个公式的合取：B B1 1=(=(x x)()(y y)()(z z)()(P P(x x,y y)P P(y y,z z)Q Q(x x,z z)B B2 2=(=(y y)()(x x)P P(x x,y y)先分别求出先分别求出B B1 1、B B2 2的子句集的子句集S S1 1、S S2 2：S S1 1=P P(x x,y y)P P(y

41、y,z z)Q Q(x x,z z)S S2 2=P P(f f(y y),),y y)则则B B的子句集为：的子句集为：S S=S S1 1S S2 2 =P P(x x,y y)P P(y y,z z)Q Q(x x,z z),),P P(f f(y y),),y y)第45页/共47页 应该说明，这样求得的子句集应该说明，这样求得的子句集S S并不完全等同并不完全等同于于B B的子句集，设的子句集，设B B的子句集为的子句集为S SB B，即，即 S SB B S S1 1S S2 2S Sn n 但在不可满足性的意义下，它们却是等价的，即但在不可满足性的意义下，它们却是等价的，即 S SB B不可满足不可满足 S S1 1S S2 2S Sn n不可满足不可满足 而这里求子句集的目的就是要利用其不可满足性而这里求子句集的目的就是要利用其不可满足性这一点，所以就可以把这一点，所以就可以把S S1 1S S2 2S Sn n作为作为B B的的子句集来使用，这样可以大大减少求公式子句集来使用，这样可以大大减少求公式B B真正真正的子句集的工作量。的子句集的工作量。第46页/共47页