1、a1第二章逻辑推理a22.1 命题逻辑1命题定义2-1命题：具有真假意义的语句。定义2-2原子命题：如果一个命题不能被进一步分解成更为简单的命题，则该命题就称为原子命题。a32连接词?：称为“非”或“否定”。?：称为“析取”，PQ读作“P或Q”。?：称为“合取”，PQ读作“P与Q”。?：称为“条件”。PQ。?：称为“双条件”。P?Q,“P当且仅当Q”。连接词优先级：，?a43合式公式定义2-3合式公式（Well-Formed Formula，WFF）孤立的命题变元或逻辑常量（T，F）是合式公式；如果A是一个合式公式，则A也是一个合式公式；如果A、B是合式公式，则AB，AB，AB，A?B也都是合
2、式公式；当且仅当有限次使用规则后得到的公式才是合式公式。a5永真式（或重言式）：给定一个公式，如果对于所有的真值指派，它的值都为真（T），则称该公式为永真式（或重言式）；永假式（或称该公式为不可满足的）：如对于所有的真值指派，它的值都为假（F），则称该公式为永假式（或称该公式为不可满足的）。非永假的公式称为可满足的公式。a64等价和永真蕴涵定义2-4等价：设A，B是两个命题公式，P1，P2，Pn是出现在A、B中的所有命题变元。如果对于这n个变元的任何一个真值指派的集合，A和B的真值都相等，则称公式A等价于公式B，记作A?B。“等价”又可定义为：A?B当且仅当A?B是一个永真式。a7定义2-5永
3、真蕴涵：命题公式A永真蕴涵命题公式B，当且仅当AB是一个永真式，记作A?B，读作“A永真蕴涵B”，简称“A蕴涵B”。a82.2 谓词逻 辑?1谓词与个体原子命题被分解为谓词和个体两部分。?个体是指可以单独存在的事物，它可以是一个抽象的概念，也可以是一个具体的东西。?谓词是用来刻画个体性质或个体间关系的词。如：POET(libai)POET(dufu)GREAT(libai,dufu)一般用大写字母表示谓词，小写字母表示个体。a9元数:谓词中包含的个体数目称为谓词的。一元谓词:与一个个体相连的谓词，如POET(x)；多元谓词:与多个个体相连的谓词叫，如GREAT(x,y)(二元谓词)。个体域:任
4、何个体的变化都有范围。谓词变元命名式:一个n元谓词常被表示成P(x1,x2,xn)。a102量词?全称量词:“(?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三种车型。a
5、113合式谓词公式原子公式:若P为不能再分解的n元谓词变元，x1,x2,xn是个体变元，则称 P(x1,x2,xn)为原子公式 或原子谓词公式。当n?=?0时，P表示命题变元或原子命题公式。所以命题逻辑是谓词逻辑的特例a12定义定义2-6谓词合式公式（简称公式）的定义如下：原子公式是合式公式；若A是合式公式，则 A也是合式公式；若A和B都是合式公式，则(AB)，(AB)，(AB)，(A?B)也都是合式公式；若A是合式公式，x是任意变元，且A中无(?x)或(?x)出现，则(?x)A或(?x)A也都是合式公式；当且仅当有限次使用规则得到的公式是合式公式。a134量词的辖域与变元的约束约束变元,自由
6、变元。公式约束变元自由变元(?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 xa145谓词公式的解释谓词公式中的谓词变元、命题变元和自由个体变元，个体常量和函数的一种指派就是一个解释。在每一种解释下，谓词公式都具有一种真值（T或F）。a15定义定义2-7设D为谓词公式 P的个体域，若对 P中的个体常量、函数和谓词按照如下规定赋值：（a）为每个个体常量指派D中的一个元素；（b）为每个n元函数指派一个从Dn到D的映射，其中Dn?=?(x1,x2,xn)?|?x1,x2,xn?D（c）为每个n元谓词指派一个从Dn到F，T的映射；则称
7、这些指派为公式P在D上的一个解释I。a16例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个不同的解释。a17P(1,1)P(1,2)P(2,1)P(2,2)I1T T T TI2T T T FI3T T F TI4 T T F FI5 T F T TI6 T F T FI7T F F TI8T F F FI9FTTTI10F
8、TTFI11FTFTI12FTFFI13FFTTI14FFTFI15FFFTI16FFFF如对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为真。a18如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 TF FT F F F由于x?=?3 时，不存在一个y使P(x,y)
9、?=?T。所以在这个解释下公式 B为假，即B(I)?=?F。a19例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的映射，如：a 0 f(0)f(1)1 0 a20（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)FTT(T)F(T)其中（T）表示不可能出现的状态，因为a已
10、经取值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。a21还可以在 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
11、)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。a22在上述个体域D上，公式A有多少种解释？对a有两种解释，对f?(x)有22种解释（nn），对P(x)有22种解释（2n），对Q(?f?(x),a)有22种解释（2n），则在D上，A共有2?22?22?22?=?27种有意义的解释。如果D中含有 n个元素，则公式A的有意义解释的个数为：n?
12、nn?2n?2n?=?22n?nn+1将解释中各个值一一代入P(x)Q(?f?(x),a)中就可得出其真值。a23定义2-8公式B是相容的（又叫可满足的或非永假的），当且仅当存在一个解释I，使得B在I 下为T，即B相容（可满足）?(?I?)B(I)这时就称I 满足B，又称I 是B的一个模型。定义2-9公式B是不相容的（又叫不可满足的或永假的），当且仅当没有任何能满足B的解释存在，即B不相容（不可满足）?(?I?)B(I)a24定义2-10公式B是永真 的，当且仅当所有解释I 都满足B，即B永真?(?I?)B(I)定义定义2-11公式B是非永真的，当且仅当不是所有的解释I 都满足 B，即B非永真
13、?(?I)B(I)这就是说公式B在有些解释下为真，有些解释下为假。a25推论B相容?(B)非永真B不相容（永假）?(B)永真B永真?B相容B不相容（永假）?B非永真a26定义定义2-12公式G是B1,B2,Bn的逻辑结论（推论），当且仅当对每一个解释I，如果B1,B2,Bn都为T，则G也为T。这时称B1,B2,Bn为G的前提。a27定理定理2-1G为B1,B2,Bn的逻辑结论，当且仅当(B1B2?Bn)?G证明：若(B1?B2?Bn)?G成立，即（B1?B2?Bn)G是永真式，也就是说在任一个使B1,B2,Bn都为真的解释下，G也为真，可见G是B1,B2,Bn的逻辑结论。反之，若(B1?B2?
14、Bn)?G不成立，即(B1?B2?Bn)G为非永真式，也就是说存在使B1,B2,Bn都为真的解释，但却不满足G，所以G不是B1,B2,Bn的逻辑结论。（证毕）a28定理定理2-2G为B1,B2,Bn的逻辑结论，当且仅当(B1B2?Bn)?G是不相容的（永假）。证明：由定理1知，G是B1,B2,Bn的逻辑结论，当且仅当(B1B2?Bn)?G即(B1B2?Bn)G为永真式，也就是说(B1B2?Bn)?G?)是不相容（永假）的，因为永真式的否定是不相容的。而(B1B2?Bn)?G?)?(B1B2?Bn)?G?)?(B1B2?Bn)?G故(B1 B2?Bn)?G是不相容的。（证毕）定理2-2是反证法的
15、理论依据。a296谓词公式中的等价和蕴涵式定义定义 2-13设P与Q是两个谓词公式，D是它们共同的个体域。若对D上的任何一个解释，P与Q的真值都相同，则称公式P和Q在域D上是等价的。如果在任何个体域上P和Q都等价，则称P和Q是等价的，记做：P?Q。a30下面是一些常用的等价式：?交换律PQ?QPPQ?QP?结合律(PQ)R?P(QR)(PQ)R?P(QR)?分配律P(QR)?(PQ)(PR)P(QR)?(PQ)(PR)?德摩根定律(PQ)?PQ(PQ)?P?Q?双重否定律(P)?Pa31?吸收律P(PQ)?PP(PQ)?P?补余律PP?TPP?F?逆否定律PQ?QP?连结词化归律PQ?PQP?
16、Q?(PQ)(QP)P?Q?(PQ)(PQ)?量词转换律(?x)P?(?x)(P)(?x)P?(?x)(P)?量词分配律(?x)(PQ)?(?x)P(?x)Q(?x)(PQ)?(?x)P(?x)Q注意，量词分配律是全称量词对合取的分配、存在量词对析取的分配。a32定义2-14对于谓词公式P和Q，如果PQ是永真式，则称P永真蕴涵Q，且称Q为P的逻辑结论，P为Q的前提，记作P?Q。a33下面是一些常用的永真蕴涵式：?化简式PQ?PPQ?Q?附加式P?PQQ?PQ?析取假论P并且PQ?Q?假言推理P并且PQ?Q?拒取式Q并且PQ?P?假言三段论PQ且QR?PR?两难推理PQ且PR且QR?R（证明：如
17、果R，则P，Q，此时PQ为假，与前提相矛盾）?全称固化(?x)P(x)?P(y)，其中y是个体域上的任一个体，利用此蕴涵式可以消去公式中的全称量词。?存在固化(?x)P(x)?P(y)，其中y是个体域上某个使P(y)为真的个体，利用此式可以消去公式中的存在量词。a347子句集合为了便于进行谓词演算，应先将公式在不失原意的情况下进行变形，使之成为某种标准形，这种标准形也称为范式。前束范式和斯克林（skolem）范式。a35（1）前束范式所谓前束范式，就是指在一个谓词公式中，如果它的所有量词均非否定地出现在公式的最前面，且它的辖域一直延伸到公式之尾，同时公式中不出现连结符号、?，则这种形式的公式就
18、是前束范式，形如(Q1x1)(Q2x2)(Qnxn)M其中Qi或为?或为?，M称为母式。例如，公式(?x)(?y)(?z)(P(x,y)Q(x,z)R(x,y,z)a36（2）斯克林范式?在离散数学中，斯克林范式的定义是存在量词全部位于全称量词的前面，形如：(?x)(?y)(?z)(P(x)Q(y)F(z)?而在人工智能中，斯克林范式指在前束范式中消去全部存在量词后得到的公式，形如(?x1)(?x2)(?xn)M(x1,xn)即母式M全部受全称量词约束。a37将合式公式 WFF（well formed formula）化成 skolem标准形的步骤如下：（a）利用等价式PQ?PQ消去连结符号“
19、”。（b）在所有可能地方将否定符去掉或将否定符内移，直至使其辖域减小到一个原子公式。（c）将合式公式WFF中的变量标准化，使得每一量词的约束变量有唯一的名字。（d）用skolem函数将所有的存在量词消去。（e）将合式公式化为前束范式，即把所有的全称量词都移到合式公式的左边，使每个?的辖域均为整个WFF。（f）将母式化为合取范式。（g）去掉全称量词。因为此时公式中的所有变量都被全称量词约束，已无存在必要，故可以消去。至此已化为 skolem标准形。a38定义定义2-15不含有任何连结词的谓词公式称为原子公式，简称原子。原子和原子的否定统称文字。例如，P(x),Q(?y,z),R(u,v,w)都是
20、原子公式。定义定义2-16子句是由文字组成的析取式。例如，P(x)Q(?y,z),P(x)R(u,v,w)Q(?y,z)都是子句。a39定义2-17不含任何文字的子句称为空子句，记为NIL。由于空子句不含任何文字，它不能被任何解释所满足，所以空子句是永假的、不可满足的。定义2-18 子句集即由子句构成的集合。注意，可通过重新命名的方法，使子句集里各个子句间无同名变量。a40将合式公式化成子句集的方法是：首先通过上面所列的步骤(a)(g)把公式化成skolem标准形，接着进行如下处理:（h）消去skolem标准形中的符号，写成集合的形式，各子句间用逗号分隔。（i）重命名子句中的变量，使得一个变量
21、名只出现在一个子句中。比如：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)a41例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)都在(
22、?x)的辖域内，故y和z都是x的函数。即(?x)(P(x,f(x)(Q(x,g(x)R(x,g(x)a42把母式化成合取范式：(?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)这种形式才是定理证明需要的标准形式。
23、a43定理定理2-3 设有谓词公式B，其标准形的子句集为S，则B不可满足当且仅当S不可满足。根据这个定理，对于不可满足的公式 B，可以通过证明它的子句集S的不可满足性来证明B的不可满足性。a44说明：一般情况下谓词公式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是不等价的，这是因为公式在化为标准形的过程中失去了一
24、些信息。a45如果一个公式本身就是个合取式，形如B?=?B1B2Bn，这时在把B化子句集S时，可通过分别把组成 B的各个合取式B1,B2,Bn等先行转化成子句集S1,S2,Sn，然后通过或运算求得S：S?=?S1S2Sna46例如，求公式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)a47应该说明，这样求得的子句集S并不完全等同于B的子句集，设B的子句集为SB，即SB?S1S2Sn但在不可满足性的意义下，它们却是等价的，即SB不可满足?S1S2Sn不可满足而这里求子句集的目的就是要利用其不可满足性这一点，所以就可以把S1S2Sn作为B的子句集来使用，这样可以大大减少求公式B真正的子句集的工作量。
