12谓词逻辑.ppt

第二章 谓词逻辑第十二讲第十二讲 23 变元的约束变元的约束 一个谓词公式中的所有个体变元被量化以后便一个谓词公式中的所有个体变元被量化以后便成为命题。分析一个谓词公式，看它是否成为命题，成为命题。分析一个谓词公式，看它是否成为命题，必须看它被量化的情况。必须看它被量化的情况。231定义定义 定义定义2-9在谓词公式中，被量化的个体变元称为约在谓词公式中，被量化的个体变元称为约束变元。束变元。定义定义2-10在谓词公式中，量词的作用范围称为辖域。在谓词公式中，量词的作用范围称为辖域。在量词辖域中，约束变元的一切出现称为约束出现。在量词辖域中，约束变元的一切出现称为约束出现。定义定义2-11在谓词公式中，未被约束的变元称为自由在谓词公式中，未被约束的变元称为自由变元。自由变元的一切出现称为自由出现。变元。自由变元的一切出现称为自由出现。在谓词公式中存在自由变元有两种情况：在谓词公式中存在自由变元有两种情况：（1）该变元在量词的辖域中，但与量词的指导变）该变元在量词的辖域中，但与量词的指导变元不同名。元不同名。（2）该变元与量词指导变元同名，但不在量词的）该变元与量词指导变元同名，但不在量词的辖域中。辖域中。例例2-11指出下列各式中量词的辖域、约束变元和自指出下列各式中量词的辖域、约束变元和自由变元。由变元。（1）（2）（3）解：解：（1）全称量词全称量词 的辖域是的辖域是 ，个体变，个体变元元x为约束变元，为约束变元，x在辖域中的所有出现为约束出在辖域中的所有出现为约束出现。现。（2）全称量词全称量词 的辖域是的辖域是 ，个体变元，个体变元x是约束变元，是约束变元，x在辖域中的所有出现为约束出现在辖域中的所有出现为约束出现（包括出现在（包括出现在 的命题公式中的的命题公式中的x）。存）。存在量词在量词 的辖域是的辖域是 ,y为约束变元。为约束变元。（3）存在量词存在量词 的辖域是的辖域是 ，其中其中 的个体变元的个体变元x受到存在量词受到存在量词 的约束，个体变元的约束，个体变元y受到全称量词受到全称量词 的约束，个体的约束，个体变元变元z未受约束，是自由变元；未受约束，是自由变元；命题公式命题公式 中的中的x除受存在量词除受存在量词 的约束的约束外，又受全称量词外，又受全称量词 的约束，以最内层的全称量的约束，以最内层的全称量词词 的约束为准，其中的的约束为准，其中的y未受约束，是自由变元。未受约束，是自由变元。【说明 】（1）如果一个个体变元受到多重约束，则最内层辖域的约束变元以最后一次约束为准。（2）如果一个谓词公式中没有自由变元，则该公式为命题。（3）若至少有一个个体变元未被约束，则该谓词公式为命题函数。232约束变元的换名约束变元的换名 在谓词公式中，一个个体变元可能处在不同量词辖域在谓词公式中，一个个体变元可能处在不同量词辖域内，或者一个个体变元受到多重约束。例如内，或者一个个体变元受到多重约束。例如在公式的前件中，在公式的前件中，y分别受到分别受到y与与y的两重约束，的两重约束，x、z为自由变元；在公式的后件中为自由变元；在公式的后件中x、y均为自由变元。由于均为自由变元。由于同一个体变元在同一命题公式中受到不同量词的约束，容同一个体变元在同一命题公式中受到不同量词的约束，容易引起混乱。易引起混乱。我们知道，一个公式中的个体变元与所使用的个体变我们知道，一个公式中的个体变元与所使用的个体变元的符号无关。例如元的符号无关。例如xP(x)与与yP(y)的含义相同，都表的含义相同，都表示论域中个体具有示论域中个体具有P属性。属性。因此，我们可以更改公式中约束变元的名称符号，这个因此，我们可以更改公式中约束变元的名称符号，这个过程称为过程称为约束变元的换名约束变元的换名。约束变元的换名规则：约束变元的换名规则：只能对量词指导变元所指示的变元换名。只能对量词指导变元所指示的变元换名。若某一量词指导变元一旦被换名，则辖域中该变元都应若某一量词指导变元一旦被换名，则辖域中该变元都应换成相同名称。即换名一致性。换成相同名称。即换名一致性。换名时一定要换成公式中未出现的名称。换名时一定要换成公式中未出现的名称。例例2-12对下列谓词公式的约束变元进行换名对下列谓词公式的约束变元进行换名（1）（2）（3）（4）解（解（1）：公式中的变元：公式中的变元x分别受到量词分别受到量词约束，约束，z为为自由变元。可将受全称量词约束的变元自由变元。可将受全称量词约束的变元x换名为换名为y，得题公，得题公式：式：解解:公式中全称量词的辖域为公式中全称量词的辖域为(P(x)P(x)x x Q(xQ(x)，辖，辖域中的域中的x受到全称量词的约束，又受到存在量词的受到全称量词的约束，又受到存在量词的约束。可将受存在量词约束的变元换名为约束。可将受存在量词约束的变元换名为y，得公，得公式：式：解：公式前件的变元解：公式前件的变元y受到两重约束，受到两重约束，P(y)受到全受到全称量的约束，称量的约束，Q(x,y,z)中的中的y受到存在量词的约束，受到存在量词的约束，后件的变后件的变x,y都是自由变元。可将受全称量词约束都是自由变元。可将受全称量词约束的变元的变元y换为换为u，受存在量词约束的变元，受存在量词约束的变元y换为换为v。得公式：得公式：解：全称量词的辖域中的个体变元为解：全称量词的辖域中的个体变元为x，不变。，不变。存在量词辖域中的个体变元存在量词辖域中的个体变元 x 换为换为v，全称量，全称量词辖域中的个体变元词辖域中的个体变元y 换为换为m，得谓词公式：，得谓词公式：233 自由变元的代入自由变元的代入 由于谓词公式中的同一个个体变元可以是约由于谓词公式中的同一个个体变元可以是约束变元，也可以是自由变元，容易引起概念上的束变元，也可以是自由变元，容易引起概念上的混乱。混乱。为了使谓词公式结构清晰，除前面介绍的对为了使谓词公式结构清晰，除前面介绍的对约束变元约束变元换名换名外，还可以对外，还可以对自由变元自由变元进行代入。进行代入。改变谓词公式中自由变元的改变谓词公式中自由变元的符号名称符号名称，称为，称为自由变元的自由变元的代入代入。自由变元代入的规则与约束变元类同。自由变元代入的规则与约束变元类同。自由变元规则：自由变元规则：某一自由变元被代入，则公式中某一自由变元被代入，则公式中同名同名自由变元自由变元都应同时被代入，即代入都应同时被代入，即代入一致性一致性。代入的符号应与公式中的已有符号代入的符号应与公式中的已有符号不同名不同名。例如：例如：分析：存在量词分析：存在量词的辖域是整个公式，其中的个的辖域是整个公式，其中的个体变元体变元x都被约束；都被约束；全称量词全称量词的辖域是的辖域是，其中个，其中个体变元体变元y受到全称量词的约束，而受到全称量词的约束，而x受到存在量词受到存在量词的约束。的约束。谓词子公式谓词子公式中的中的y是自由变元，是自由变元，与约束变元同名。与约束变元同名。现用现用z代入自由变元代入自由变元y可得谓词公式如下：可得谓词公式如下：2.4 谓词演算的等价式和蕴含式谓词演算的等价式和蕴含式 由谓词公式的定义可知，谓词公式包含一般命由谓词公式的定义可知，谓词公式包含一般命题和谓词命题，也包含命题变元和命题函数题和谓词命题，也包含命题变元和命题函数;因此，一个谓词公式要成为因此，一个谓词公式要成为确定命题确定命题，必须用，必须用确定的命题确定的命题取代谓词公式中的命题变元，用一组取代谓词公式中的命题变元，用一组具具体的个体体的个体取代谓词公式中的自由变元。取代谓词公式中的自由变元。定义定义2-12 当谓词公式中的自由变元用其个体域中确当谓词公式中的自由变元用其个体域中确定的个体取代，命题变元用确定命题取代，这样一定的个体取代，命题变元用确定命题取代，这样一组确定的个体和命题称为该公式的组确定的个体和命题称为该公式的一组赋值一组赋值。定义定义解释解释I由下面由下面4部分组成：部分组成：(a)非空个体域非空个体域DI(b)DI中一些特定元素中一些特定元素等等(c)DI上一些特定函数上一些特定函数等等(d)DI上一些特定谓词上一些特定谓词等等说明：说明：被解释的公式被解释的公式A中的个体变项均取值于中的个体变项均取值于DI若若A中含个体常项中含个体常项a、函数函数f、谓词谓词F,就分别解释就分别解释成成、解释解释(续续)被解释的公式不一定全部包含解释中的被解释的公式不一定全部包含解释中的4部分部分.闭式闭式在任何解释下都是命题，在任何解释下都是命题，注注意意不不是是闭闭式式的的公公式式在在某某些些解解释释下下也也可可能能是是命命题题.定义定义2-13两个有相同个体域两个有相同个体域E的谓词公式的谓词公式A和和B，若对两，若对两个谓词公式所有变元的任一组赋值，所得命题真值相同，个谓词公式所有变元的任一组赋值，所得命题真值相同，则称这两个谓词公式在指定个体域则称这两个谓词公式在指定个体域E上等价。上等价。记为记为 定义定义2-14给定谓词公式给定谓词公式A，其个体域为，其个体域为E，若对，若对A的任一的任一组赋值，组赋值，A的值总为真，则称的值总为真，则称A在在E上是永真的（或有效的）上是永真的（或有效的）。记为记为 定义定义2-15给定谓词公式给定谓词公式A，其个体域为，其个体域为E，若对，若对A的任一的任一组赋值，组赋值，A的值恒为假，则称的值恒为假，则称A在在E上是永假的（或不可满上是永假的（或不可满足的）。记为足的）。记为 定义定义2-16给定谓词公式给定谓词公式A，其个体域为，其个体域为E，若对，若对A至少有一至少有一组赋值，组赋值，A的值为真，则称的值为真，则称A在在E上是可满足的。上是可满足的。在命题公式中，如果两个命题公式所含命题在命题公式中，如果两个命题公式所含命题变元的任一组指派，所得命题的真值总相等，则变元的任一组指派，所得命题的真值总相等，则两个命题公式等价。两个命题公式等价。在谓词公式中同样存在在谓词公式中同样存在等价问题等价问题，不过谓词，不过谓词公式不能直接公式不能直接指派真值指派真值，因为谓词公式包含个体，因为谓词公式包含个体变元，必须对个体变元进行变元，必须对个体变元进行代换代换或或约束约束才能确定才能确定其真值，这就涉及到个体变元的个体域问题。其真值，这就涉及到个体变元的个体域问题。所以两个谓词公式的个体变元必须所以两个谓词公式的个体变元必须有相同的有相同的个体域个体域才能讨论其是否等价。才能讨论其是否等价。（一）命题公式的推广（一）命题公式的推广命题公式是谓词公式的特例，命题逻辑中的所有等价命题公式是谓词公式的特例，命题逻辑中的所有等价式和蕴含式在谓词逻辑中都适用。式和蕴含式在谓词逻辑中都适用。可以将命题逻辑中的等价式和蕴含式可以将命题逻辑中的等价式和蕴含式推广推广到谓词逻辑到谓词逻辑中。中。用用原子谓词公式原子谓词公式取代取代命题演算命题演算中永真公式的中永真公式的命题变元命题变元，所得的谓词公式也是永真公式。所得的谓词公式也是永真公式。例如：例如：含有含有量词量词和约束变元的原子谓词公式取代命题演算和约束变元的原子谓词公式取代命题演算中永真公式的命题变元，同样可得到永真的谓词演算公中永真公式的命题变元，同样可得到永真的谓词演算公式。例如用式。例如用XP(x)取代取代A，用，用xQ(x)取代取代B，则：，则：使用这种方法，可以得到一组谓词演算的使用这种方法，可以得到一组谓词演算的等价公式等价公式和和蕴含公式蕴含公式。（二）量词（二）量词转换转换律律 全称量词和存在量词表示两种不同的全称量词和存在量词表示两种不同的量化关系量化关系，它们，它们之间究竟有什么联系呢？之间究竟有什么联系呢？例如：全称量化谓词公式若为真，表示论域中的所有例如：全称量化谓词公式若为真，表示论域中的所有个体个体x，都能使为真；，都能使为真；若为假，表示论域中的所有个体使为真是不可能的，若为假，表示论域中的所有个体使为真是不可能的，则至少论域中则至少论域中“存在存在”某些个体使为假。某些个体使为假。例如：论域为小汽车。例如：论域为小汽车。P(x)表示表示x是粉红色的。是粉红色的。xP(x)表示所有的小汽车是粉红色的。表示所有的小汽车是粉红色的。复合命题复合命题xP(x)表示所有小汽车都是粉红色是不对表示所有小汽车都是粉红色是不对的，说明必定存在某些小汽车不是粉红色的，的，说明必定存在某些小汽车不是粉红色的，即即xP(x)。所以所以：反之，复合命题反之，复合命题xP(x)表示有的小汽车不是粉红色，说表示有的小汽车不是粉红色，说明不是所有的小汽车都是粉红色，即明不是所有的小汽车都是粉红色，即xP(x)。所以所以因此因此（2-3）设论域设论域，使用，使用代换实例代换实例证明：证明：同样同样 表示存在有粉红色小汽车是不对的，说明所有小表示存在有粉红色小汽车是不对的，说明所有小汽车都不是粉红色，即汽车都不是粉红色，即 。所以。所以 。反之，反之，表示所有的小汽车都不是粉红色，说明不可能表示所有的小汽车都不是粉红色，说明不可能有粉红色的小汽车，即有粉红色的小汽车，即 。所以所以 。因此因此 （2-4）同样，我们用代换实例加以证明：同样，我们用代换实例加以证明：不难发现，我们将否定符移到量词后面时，全称量词变不难发现，我们将否定符移到量词后面时，全称量词变为存在量词，存在量词变为全称量词。为存在量词，存在量词变为全称量词。反之，量词后面的否定符移到量词的前面时，也要作相反之，量词后面的否定符移到量词的前面时，也要作相应的改变，这种量词与否定的关系是普遍成立的，人们习惯应的改变，这种量词与否定的关系是普遍成立的，人们习惯称之为称之为量词转换律量词转换律。（三）量词辖域的扩张和收缩（三）量词辖域的扩张和收缩量词辖域的扩张和收缩是指量词辖域的扩张和收缩是指不受量词约束不受量词约束的命题函数和的命题函数和命题进入和退出量词的辖域，但由于命题公式结构不同，不命题进入和退出量词的辖域，但由于命题公式结构不同，不受约束的命题函数和命题进出量词辖域时应区别对待。受约束的命题函数和命题进出量词辖域时应区别对待。（1）若量词辖域中是合取式或析取式，则）若量词辖域中是合取式或析取式，则不受约束不受约束的谓词公的谓词公式可以式可以直接直接退出该辖域。退出该辖域。例如：例如：（2）若量词辖域是条件命题的前件，则作为后件的不受约）若量词辖域是条件命题的前件，则作为后件的不受约束的谓词公式不能直接进出该辖域。束的谓词公式不能直接进出该辖域。证明：同理可得：（3）若量词辖域是条件命题）若量词辖域是条件命题后件后件，则作为前件不受约束的谓，则作为前件不受约束的谓词公式可以直接进出该辖域。词公式可以直接进出该辖域。（四）含量词的合取式、析取式的等价式（四）含量词的合取式、析取式的等价式（1）全称量词可以对合取式进行）全称量词可以对合取式进行分配分配。例如全班所有的同学既聪明又刻苦。例如全班所有的同学既聪明又刻苦。设论域设论域D为全班同学。为全班同学。A(x)：表示：表示x聪明。聪明。B(x)：表示：表示x刻苦。刻苦。因为全班所有的同学既聪明又刻苦，即每个同学都聪明，因为全班所有的同学既聪明又刻苦，即每个同学都聪明，并且同时每个同学都刻苦，所以并且同时每个同学都刻苦，所以为真。为真。如果每个同学都聪明，而且每个同学都刻苦，即全班所如果每个同学都聪明，而且每个同学都刻苦，即全班所有同学既聪明又刻苦，所以有同学既聪明又刻苦，所以为真。为真。因此因此证明：设论域为有限论域证明：设论域为有限论域 ，则，则（2）存在量词可对析取式进行分配。）存在量词可对析取式进行分配。证证明：明：设论设论域域为为有限有限论论域域，则则 该公式可对全称量词分配律等价公式两边加上否定该公式可对全称量词分配律等价公式两边加上否定后转换成该项公式。后转换成该项公式。（五）前束范式（五）前束范式 定义定义2-17在谓词公式中，如果所有量词都出现在公式在谓词公式中，如果所有量词都出现在公式的最前面，且其辖域为的最前面，且其辖域为整个公式整个公式，则称该谓词公式为，则称该谓词公式为前束前束范式范式。例如：例如：都为前束范式，而下列各式不是前束范式。都为前束范式，而下列各式不是前束范式。【说明说明】全称量词可以合取式进行分配，存在量词可以对析全称量词可以合取式进行分配，存在量词可以对析取式进行分配，但全称量词不能对取式进行分配，但全称量词不能对析取式析取式进行分配，存在量进行分配，存在量词不能对合取式进行分配。词不能对合取式进行分配。谓词公式转化为谓词公式转化为前束范式前束范式的步骤：的步骤：利用等价公式把公式的利用等价公式把公式的联结词联结词归化归化。利用量词转换律和德利用量词转换律和德摩根律，把公式中的否定摩根律，把公式中的否定联结词移到联结词移到原子命题函数原子命题函数前面。前面。利用约束变元的利用约束变元的换名规则换名规则和自由变元的和自由变元的代入规代入规则则，使所有约束变元和自由变元，使所有约束变元和自由变元不同名不同名。将所有量词按其出现的将所有量词按其出现的先后顺序先后顺序移到公式前面。移到公式前面。例例2-13将下列公式转换成前束范式。将下列公式转换成前束范式。(1)(2)(3)解解(1):解解(2):解解(3):定理（前束范式存在定理）定理（前束范式存在定理）一阶逻辑中的任何公式都存在与之等值的前束范式一阶逻辑中的任何公式都存在与之等值的前束范式(1)xF(x)y(G(x,y)H(y)或或 xF(x)y(G(z,y)H(y)代替规则代替规则 x y(F(x)(G(z,y)H(y)解解 xF(x)y(G(x,y)H(y)zF(z)y(G(x,y)H(y)换名规则换名规则 z y(F(z)(G(x,y)H(y)辖域收缩扩张规则辖域收缩扩张规则例例4求下列公式的前束范式求下列公式的前束范式