命题逻辑与谓词逻辑课件

a1第二章逻辑推理a1第二章逻辑推理a22.1命题逻辑1．命题定义2-1命题：具有真假意义的语句。定义2-2原子命题：如果一个命题不能被进一步分解成更为简单的命题，则该命题就称为原子命题。a22.1命题逻辑1．命题定义2-1命题：具有真假意义的a32．连接词?～：称为“非”或“否定”。?∨：称为“析取”，P∨Q读作“P或Q”。?∧：称为“合取”，P∧Q读作“P与Q”。?→：称为“条件”。P→Q。??：称为“双条件”。P?Q,“P当且仅当Q”。连接词优先级：～，∧，∨，→，?a32．连接词?～：称为“非”或“否定”。?∨：称为“析取”a43．合式公式定义2-3合式公式（Well-FormedFormula，WFF）①孤立的命题变元或逻辑常量（T，F）是合式公式；②如果A是一个合式公式，则～A也是一个合式公式；③如果A、B是合式公式，则A∨B，A∧B，A→B，A?B也都是合式公式；④当且仅当有限次使用规则①～③后得到的公式才是合式公式。a43．合式公式定义2-3合式公式（Well-Formeda5永真式（或重言式）：给定一个公式，如果对于所有的真值指派，它的值都为真（T），则称该公式为永真式（或重言式）；永假式（或称该公式为不可满足的）：如对于所有的真值指派，它的值都为假（F），则称该公式为永假式（或称该公式为不可满足的）。非永假的公式称为可满足的公式。a5永真式（或重言式）：给定一个公式，如果对于所有的真值指派a64．等价和永真蕴涵定义2-4等价：设A，B是两个命题公式，P1，P2，…，Pn是出现在A、B中的所有命题变元。如果对于这n个变元的任何一个真值指派的集合，A和B的真值都相等，则称公式A等价于公式B，记作A?B。“等价”又可定义为：A?B当且仅当A?B是一个永真式。a64．等价和永真蕴涵定义2-4等价：设A，B是两个命题公式a7定义2-5永真蕴涵：命题公式A永真蕴涵命题公式B，当且仅当A→B是一个永真式，记作A?B，读作“A永真蕴涵B”，简称“A蕴涵B”。a7定义2-5永真蕴涵：命题公式A永真蕴涵命题公式B，当且仅a82.2谓词逻辑?1．谓词与个体原子命题被分解为谓词和个体两部分。?个体是指可以单独存在的事物，它可以是一个抽象的概念，也可以是一个具体的东西。?谓词是用来刻画个体性质或个体间关系的词。如：POET(libai)POET(dufu)GREAT(libai,dufu)一般用大写字母表示谓词，小写字母表示个体。a82.2谓词逻辑?1．谓词与个体原子命题被分解为谓词和a9元数:谓词中包含的个体数目称为谓词的。一元谓词:与一个个体相连的谓词，如POET(x)；多元谓词:与多个个体相连的谓词叫，如GREAT(x,y)(二元谓词)。个体域:任何个体的变化都有范围。谓词变元命名式:一个n元谓词常被表示成P(x1,x2,…,xn)。a9元数:谓词中包含的个体数目称为谓词的。一元谓词: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}三种车型。a102．量词?全称量词:“(?x)P(x)”表示命题“a113．合式谓词公式原子公式:若P为不能再分解的n元谓词变元，x1,x2,…,xn是个体变元，则称P(x1,x2,…,xn)为原子公式或原子谓词公式。当n?=?0时，P表示命题变元或原子命题公式。所以命题逻辑是谓词逻辑的特例a113．合式谓词公式原子公式:若P为不能再分解的n元谓a12定义2-6谓词合式公式（简称公式）的定义如下：①原子公式是合式公式；②若A是合式公式，则～A也是合式公式；③若A和B都是合式公式，则(A∧B)，(A∨B)，(A→B)，(A?B)也都是合式公式；④若A是合式公式，x是任意变元，且A中无(?x)或(?x)出现，则(?x)A或(?x)A也都是合式公式；⑤当且仅当有限次使用规则①～④得到的公式是合式公式。a12定义2-6谓词合式公式（简称公式）的定义如下：①原子公a134．量词的辖域与变元的约束约束变元,自由变元。公式约束变元自由变元(?x)P(x,y)xy(?x)Q(y)无y(?x)(P(x)→(?y)Q(x,y))x,y(?y)P(x)∧Q(x)yxa134．量词的辖域与变元的约束约束变元,自由变元。公式约束a145．谓词公式的解释谓词公式中的谓词变元、命题变元和自由个体变元，个体常量和函数的一种指派就是一个解释。在每一种解释下，谓词公式都具有一种真值（T或F）。a145．谓词公式的解释谓词公式中的谓词变元、命题变元和自由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}的映射；则称这些指派为公式P在D上的一个解释I。a15定义2-7设D为谓词公式P的个体域，若对P中的个体常量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个不同的解释。a16例2-1给定公式B?=?(?x)(?y)P(x,y)a17P(1,1)P(1,2)P(2,1)P(2,2)I1TTTTI2TTTFI3TTFTI4TTFFI5TFTTI6TFTFI7TFFTI8TFFFI9FTTTI10FTTFI11FTFTI12FTFFI13FFTTI14FFTFI15FFFTI16FFFF如对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为真。a17P(1,1)P(1,2)P(2a18如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)TTTFFTFFF由于x?=?3时，不存在一个y使P(x,y)?=?T。所以在这个解释下公式B为假，即B(I)?=?F。a18如D2?=?{1，2，3}根据上面的分析，在D2上的解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

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

a19例2-2给定公式A?=?(?x)(P(x)→Q(?f?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已经取值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)?=?F→F?=?T对x?=?1时P(x)→Q(?f?(x),a)?=?P(1)→Q(?f?(1),0)?=?P(1)→Q(0,0)?=?T→T?=?T所以在此解释下，公式A为真，即A(I1)?=?T。a20（c）对每个谓词符号指派一个由D1到{F，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)F则当x?=?0时，P(x)→Q(?f?(x),a)?=?P(0)→Q(?f?(0),1)?=?P(0)→Q(0,1)?=?T→F?=?F当x?=?1时，P(x)→Q(?f?(x),a)?=?P(1)→Q(?f?(1),1)?=?P(1)→Q(1,1)?=?F→T?=?T所以在解释I2下公式A为假，即A(I2)?=?F。a21还可以在D上定义如下的解释I2：f?(0)f?(1)0a22在上述个体域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?nn?2n?2n?=?22n?nn+1将解释中各个值一一代入P(x)→Q(?f?(x),a)中就可得出其真值。a22在上述个体域D上，公式A有多少种解释？对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)a23定义2-8公式B是相容的（又叫可满足的或非永假的），当a24定义2-10公式B是永真的，当且仅当所有解释I都满足B，即B永真?(?I?)B(I)定义2-11公式B是非永真的，当且仅当不是所有的解释I都满足B，即B非永真?～(?I)B(I)这就是说公式B在有些解释下为真，有些解释下为假。a24定义2-10公式B是永真的，当且仅当所有解释I都满足a25推论①B相容?(～B)非永真②B不相容（永假）?(～B)永真③B永真?B相容④B不相容（永假）?B非永真a25推论①B相容?(～B)非永真②B不相容（永假）?(～Ba26定义2-12公式G是B1,B2,…,Bn的逻辑结论（推论），当且仅当对每一个解释I，如果B1,B2,…,Bn都为T，则G也为T。这时称B1,B2,…,Bn为G的前提。a26定义2-12公式G是B1,B2,…,Bn的逻辑结a27定理2-1G为B1,B2,…,Bn的逻辑结论，当且仅当(B1∧B2∧?…?∧Bn)?G证明：若(B1∧?B2∧?…?∧?Bn)?G成立，即（B1∧?B2∧?…?∧?Bn)→G是永真式，也就是说在任一个使B1,B2,…,Bn都为真的解释下，G也为真，可见G是B1,B2,…,Bn的逻辑结论。反之，若(B1∧?B2∧?…?∧?Bn)?G不成立，即(B1∧?B2∧?…?∧?Bn)→G为非永真式，也就是说存在使B1,B2,…,Bn都为真的解释，但却不满足G，所以G不是B1,B2,…,Bn的逻辑结论。（证毕）a27定理2-1G为B1,B2,…,Bn的逻辑结论，当a28定理2-2G为B1,B2,…,Bn的逻辑结论，当且仅当(B1∧B2∧?…?∧Bn)?∧～G是不相容的（永假）。证明：由定理1知，G是B1,B2,…,Bn的逻辑结论，当且仅当(B1∧B2∧?…?∧Bn)?G即(B1∧B2∧?…?∧Bn)→G为永真式，也就是说～((B1∧B2∧?…?∧Bn)?→?G?)是不相容（永假）的，因为永真式的否定是不相容的。而～((B1∧B2∧?…?∧Bn)?→?G?)?～(～(B1∧B2∧?…?∧Bn)?∨G?)?(B1∧B2∧?…?∧Bn)?∧～G故(B1∧B2∧?…?∧Bn)?∧～G是不相容的。（证毕）定理2-2是反证法的理论依据。a28定理2-2G为B1,B2,…,Bn的逻辑结论，当a296．谓词公式中的等价和蕴涵式定义2-13设P与Q是两个谓词公式，D是它们共同的个体域。若对D上的任何一个解释，P与Q的真值都相同，则称公式P和Q在域D上是等价的。如果在任何个体域上P和Q都等价，则称P和Q是等价的，记做：P?Q。a296．谓词公式中的等价和蕴涵式定义2-13设P与Q是两个a30下面是一些常用的等价式：?交换律P∨Q?Q∨PP∧Q?Q∧P?结合律(P∨Q)∨R?P∨(Q∨R)(P∧Q)∧R?P∧(Q∧R)?分配律P∨(Q∧R)?(P∨Q)∧(P∨R)P∧(Q∨R)?(P∧Q)∨(P∧R)?德·摩根定律～(P∨Q)?～P∧～Q～(P∧Q)?～P?∨～Q?双重否定律～(～P)?Pa30下面是一些常用的等价式：?交换律P∨Q?Q∨PP∧Q?a31?吸收律P∨(P∧Q)?PP∧(P∨Q)?P?补余律P∨～P?TP∧～P?F?逆否定律P→Q?～Q→～P?连结词化归律P→Q?～P∨QP?Q?(P→Q)∧(Q→P)P?Q?(P∧Q)∨(～P∧～Q)?量词转换律～(?x)P?(?x)(～P)～(?x)P?(?x)(～P)?量词分配律(?x)(P∧Q)?(?x)P∧(?x)Q(?x)(P∨Q)?(?x)P∨(?x)Q注意，量词分配律是全称量词对合取的分配、存在量词对析取的分配。a31?吸收律P∨(P∧Q)?PP∧(P∨Q)?P?补余a32定义2-14对于谓词公式P和Q，如果P→Q是永真式，则称P永真蕴涵Q，且称Q为P的逻辑结论，P为Q的前提，记作P?Q。a32定义2-14对于谓词公式P和Q，如果P→Q是永真式，则a33下面是一些常用的永真蕴涵式：?化简式P∧Q?PP∧Q?Q?附加式P?P∨QQ?P∨Q?析取假论～P并且P∨Q?Q?假言推理P并且P→Q?Q?拒取式～Q并且P→Q?～P?假言三段论P→Q且Q→R?P→R?两难推理P∨Q且P→R且Q→R?R（证明：如果～R，则～P，～Q，此时P∨Q为假，与前提相矛盾）?全称固化(?x)P(x)?P(y)，其中y是个体域上的任一个体，利用此蕴涵式可以消去公式中的全称量词。?存在固化(?x)P(x)?P(y)，其中y是个体域上某个使P(y)为真的个体，利用此式可以消去公式中的存在量词。a33下面是一些常用的永真蕴涵式：?化简式P∧Q?PP∧Q?a347．子句集合为了便于进行谓词演算，应先将公式在不失原意的情况下进行变形，使之成为某种标准形，这种标准形也称为范式。前束范式和斯克林（skolem）范式。a347．子句集合为了便于进行谓词演算，应先将公式在不失原意a35（1）前束范式所谓前束范式，就是指在一个谓词公式中，如果它的所有量词均非否定地出现在公式的最前面，且它的辖域一直延伸到公式之尾，同时公式中不出现连结符号→、?，则这种形式的公式就是前束范式，形如(Q1x1)(Q2x2)…(Qnxn)M其中Qi或为?或为?，M称为母式。例如，公式(?x)(?y)(?z)((～P(x,y)∧Q(x,z))∨R(x,y,z))a35（1）前束范式所谓前束范式，就是指在一个谓词公式中，如a36（2）斯克林范式?在离散数学中，斯克林范式的定义是存在量词全部位于全称量词的前面，形如：(?x)(?y)(?z)(P(x)∧Q(y)∧F(z))?而在人工智能中，斯克林范式指在前束范式中消去全部存在量词后得到的公式，形如(?x1)(?x2)…(?xn)M(x1,…,xn)即母式M全部受全称量词约束。a36（2）斯克林范式?在离散数学中，斯克林范式的定义是存在a37将合式公式WFF（wellformedformula）化成skolem标准形的步骤如下：（a）利用等价式P→Q?～P∨Q消去连结符号“→”。（b）在所有可能地方将否定符去掉或将否定符内移，直至使其辖域减小到一个原子公式。（c）将合式公式WFF中的变量标准化，使得每一量词的约束变量有唯一的名字。（d）用skolem函数将所有的存在量词消去。（e）将合式公式化为前束范式，即把所有的全称量词都移到合式公式的左边，使每个?的辖域均为整个WFF。（f）将母式化为合取范式。（g）去掉全称量词。因为此时公式中的所有变量都被全称量词约束，已无存在必要，故可以消去。至此已化为skolem标准形。a37将合式公式WFF（wellformedformula38定义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)都是子句。a38定义2-15不含有任何连结词的谓词公式称为原子公式，简a39定义2-17不含任何文字的子句称为空子句，记为NIL。由于空子句不含任何文字，它不能被任何解释所满足，所以空子句是永假的、不可满足的。定义2-18子句集即由子句构成的集合。注意，可通过重新命名的方法，使子句集里各个子句间无同名变量。a39定义2-17不含任何文字的子句称为空子句，记为NIL。a40将合式公式化成子句集的方法是：首先通过上面所列的步骤(a)～(g)把公式化成skolem标准形，接着进行如下处理:（h）消去skolem标准形中的∧符号，写成集合的形式，各子句间用逗号分隔。（i）重命名子句中的变量，使得一个变量名只出现在一个子句中。比如：P(x)∨Q(x)∨L(x,y)～P(x)∨Q(y