谓词公式与翻译

1、2022-2-2212.3 谓词公式与翻译1谓词公式（合式公式）谓词公式（合式公式）在给出一阶谓词逻辑中谓词公式的定义之前，我们首先对所使在给出一阶谓词逻辑中谓词公式的定义之前，我们首先对所使用的符号作如下约定。用的符号作如下约定。1）个体常量符号：）个体常量符号：a，b，c，ai，bi，ci，（，（i1）；）；2）个体变量符号：）个体变量符号：x，y，z，xi，yi，zi，（，（i1）；）；3）函数符号：）函数符号：f，g，h，fi，gi，hi，（，（i1）；）；4) 谓词符号：谓词符号：P，Q，R，Pi，Qi，Ri，（，（i1）；）；5）量词符号：）量词符号： x， x，x为任意的个体变量

2、符号；为任意的个体变量符号；6）联结词符号：）联结词符号：，；2022-2-2222.3 谓词公式与翻译1谓词公式（合式公式）谓词公式（合式公式）定义定义 项项可递归地定义如下可递归地定义如下1）个体常量是项；）个体常量是项；2）个体变量是项；）个体变量是项；3）若）若f（x1，x2，x3，xn）是任意的）是任意的n元函数，元函数，t1，t2，t3，tn是项，则是项，则f（t1，t2，t3，tn）是项；）是项；4）只有有限次地使用）只有有限次地使用1），），2），），3）所生成的符号串才是项。）所生成的符号串才是项。例如，例如，a，x，f（a），），g（x），），h（a，x），），h（f（a）

3、，），g（x），），f（h（a，x）等都是项。）等都是项。2022-2-2232.3 谓词公式与翻译定义定义 若若P（x1，x2，xn）是任意的）是任意的n元谓词，元谓词，t1，t2，tn是项，则称是项，则称P（t1，t2，t3，tn）为为原子公式。原子公式。例如：原子谓词公式包括下述形式的各种特例：例如：原子谓词公式包括下述形式的各种特例：Q,A(x)，A(x,y)，A(f(x)，y)，A(x,y,z)，A(a,y)等等2022-2-2242.3 谓词公式与翻译定义定义 一阶谓词逻辑中的一阶谓词逻辑中的谓词公式（合式公式）谓词公式（合式公式）的递的递归定义为归定义为1）原子公式是合式公式；）

4、原子公式是合式公式；2）若）若A是合式公式，则（是合式公式，则（A）是合式公式；）是合式公式；3）若）若A，B是合式公式，则（是合式公式，则（AB），（），（AB），），（AB），（），（A B）是合式公式；）是合式公式；4）若）若A是合式公式，则是合式公式，则 xA， xA是合式公式；是合式公式；只有有限次地使用只有有限次地使用1），），2），），3），），4）所生成的符）所生成的符号串才是合式公式。号串才是合式公式。通常，（通常，（A）的括号可以省略，写成）的括号可以省略，写成A，整个公式，整个公式最外层的括号可以省略。最外层的括号可以省略。但是量词后边如果有括号则不能省略。但是量词后边如

5、果有括号则不能省略。合式公式或谓词公式可简称为公式。合式公式或谓词公式可简称为公式。2022-2-2252.3 谓词公式与翻译【例【例1】将下列命题形式化为谓词逻辑中的命题】将下列命题形式化为谓词逻辑中的命题: 没有不犯错误的人。没有不犯错误的人。 人总是要犯错误的。人总是要犯错误的。 解：设解：设F(x)：x犯错误，犯错误，M(x)：x是人。则上句符是人。则上句符号化为：号化为： (a) ( x)(M(x) F(x) (b) x(M(x)F(x) 【例【例2】尽管有人聪明但未必一切人都聪明。】尽管有人聪明但未必一切人都聪明。 解：设解：设P(x)：x聪明，聪明，M(x)：x是人。则上句符号是

6、人。则上句符号化为：化为： x(M(x) P(x) ( x(M(x)P(x) 翻译翻译：是将自然语言叙述的命题翻译成谓词：是将自然语言叙述的命题翻译成谓词公式的形式。公式的形式。2022-2-226l 由例可知，对于命题翻译成谓词公式时，机动性很大，由于对个体描述性质的刻划深度不同，就可翻译成不同形式的谓词公式。l l例如：这只大红书柜摆满了那些古书2.3 谓词公式与翻译l 解法1：l设：F(x,y): x摆满了yl R(x): x是大红书柜l Q(y): y是古书l a:这只 b:那些l结果：结果：R(a) Q(b) F(a,b)l 解法2：l设：F(x,y): x摆满了yl A(x): x

7、是书柜l B(x): x是大的l C(x): x是红的l D(y): y是古老的l E(y): y是图书l a:这只 b:那些l结果：结果：A(a) B(a) C(a) D(b) E(b) F(a,b)2022-2-2272.3 谓词公式与翻译2谓词公式的解释谓词公式的解释 对于命题公式，只要给出其所含命题变元的一组真对于命题公式，只要给出其所含命题变元的一组真值指派，即一种解释就可得到该公式的真值。值指派，即一种解释就可得到该公式的真值。 而谓词公式的真值，一般情况下，是由而谓词公式的真值，一般情况下，是由论域论域，个体个体常项常项，量词量词，个体变项个体变项，函数函数以及以及谓词谓词等确定

8、。对谓词等确定。对谓词公式中的各种变项予以特殊的指定，就得到该公式的一公式中的各种变项予以特殊的指定，就得到该公式的一个解释。下面给出谓词公式解释的一般定义。个解释。下面给出谓词公式解释的一般定义。2022-2-2282.3 谓词公式与翻译2谓词公式的解释谓词公式的解释定义定义 谓词公式的一个解释谓词公式的一个解释I，由下面，由下面4部分组成部分组成1）非空的论域）非空的论域U；2）U中的特定的个体常项；中的特定的个体常项；3）U上特定的函数；上特定的函数；4）U上特定的谓词。上特定的谓词。 若将谓词公式中的个体常项，函数和谓词分别指定若将谓词公式中的个体常项，函数和谓词分别指定为为U中的特定

9、个体常项，中的特定个体常项，U上特定的函数和上特定的函数和U上特定的谓上特定的谓词，即为该公式在解释词，即为该公式在解释I下的真值。下的真值。2022-2-229【例【例2.2.1】给定解释】给定解释I如下如下（1）U =a，b；（2）a = 2；（3）函数）函数f（x）为）为f（a）= b，f（b）= a；（4）谓词）谓词 P（x）为）为P（a）= 0，P（b）= 1；Q（x，y）为）为Q（a，a）= 0，Q（a，b）= Q（b，a）= Q（b，b）= 1；L（x，y）为）为L（a，b）=L（b，a）= 0，L（a，a）= L（b，b）= 1。求下列公式在解释求下列公式在解释I下的真值下的真

10、值1）P（a） x P(x)；在解释在解释I下下P（a） x P(x)= P（a）（P（a）P（b）= 0（01）= 00= 02022-2-2210【例【例2.2.1】给定解释】给定解释I如下如下（1）U =a，b；（2）a = 2；（3）函数）函数f（x）为）为f（a）= b，f（b）= a；（4）谓词）谓词 P（x）为）为P（a）= 0，P（b）= 1；Q（x，y）为）为Q（a，a）= 0，Q（a，b）= Q（b，a）= Q（b，b）= 1；L（x，y）为）为L（a，b）=L（b，a）= 0，L（a，a）= L（b，b）= 1。求下列公式在解释求下列公式在解释I下的真值下的真值2） x（

11、 P（f（x）Q（x，f（x）；）；在解释在解释I下下 x（ P（f（x）Q（x，f（x）=（ P（f（a）Q（a，f（a）（ P（f（b）Q（b，f（b）=（ P（b）Q（a，b）（ P（a）Q（b，a）=（ 11）（ 01）= 10= 12022-2-2211【例【例2.2.1】给定解释】给定解释I如下如下（1）U =a，b；（2）a = 2；（3）函数）函数f（x）为）为f（a）= b，f（b）= a；（4）谓词）谓词 P（x）为）为P（a）= 0，P（b）= 1；Q（x，y）为）为Q（a，a）= 0，Q（a，b）= Q（b，a）= Q（b，b）= 1；L（x，y）为）为L（a，b）=L

12、（b，a）= 0，L（a，a）= L（b，b）= 1。求下列公式在解释求下列公式在解释I下的真值下的真值3） x y L（x，y）。）。在解释在解释I下下 x y L（x，y）=（ L（a，a）L（a，b）（L（b，a）L（b，b）=（10）（01）=11=12022-2-22122.4 变元的约束1 作用域或辖域作用域或辖域 设设为一个谓词公式，其中有一部份公式形式为为一个谓词公式，其中有一部份公式形式为 xP(x)或彐或彐xP(x)。这里、彐后面所跟的。这里、彐后面所跟的x叫做叫做量词的指量词的指导变元导变元或或作用变元作用变元，P(x)叫做相应量词的叫做相应量词的作用域或辖域。作用域或辖

13、域。2 约束变元和自由变元约束变元和自由变元 约束变元约束变元在谓词公式在谓词公式中，中， x或彐或彐x作用域中出现作用域中出现的的x称为称为中的中的约束变元约束变元，x亦称为被相应量词中的亦称为被相应量词中的指导指导变元所约束变元所约束。 自由变元自由变元在在中除去约束变元以外所出现的变元称作中除去约束变元以外所出现的变元称作自由变元自由变元。自由变元是不受约束的变元，虽然它有时也。自由变元是不受约束的变元，虽然它有时也在量词的作用域中出现，但它不受相应量词中指导变元在量词的作用域中出现，但它不受相应量词中指导变元的约束，故我们可把自由变元看作是公式中的参数。的约束，故我们可把自由变元看作是

14、公式中的参数。 2022-2-22132.4 变元的约束 例题例题1 说明以下各式的作用域与变元约束的情况。说明以下各式的作用域与变元约束的情况。 a) x(P(x)Q(x) b) x(P(x)彐彐yR(x,y) c) x y(P(x,y)Q(y,z)彐彐xP(x,y) d) x(P(x)彐彐xQ(x,z)彐彐yR(x,y)Q(x,y)解解 a) x的作用域是的作用域是P(x)Q(x)，x为约束变元。为约束变元。 b) x的作用域是的作用域是(P(x)彐彐yR(x,y), 彐彐y的作用域是的作用域是R(x,y)，x,y都是约束变元都是约束变元. c) x和和 y的作用域是的作用域是(P(x,y

15、)Q(y,z)，其中，其中x,y是约束是约束变元，变元，z是自由变元。彐是自由变元。彐x的作用域是的作用域是P(x,y)，其中，其中x是约束是约束变元，变元，y是自由变元。在整个公式中是自由变元。在整个公式中,x是约束出现，是约束出现，y既是既是约束出现又是自由出现，约束出现又是自由出现，z是自由出现。是自由出现。 d) x的作用域是的作用域是(P(x)彐彐xQ(x,z)(彐彐y)R(x,y)，x和和y都是约束变元，但都是约束变元，但Q(x,z)中的中的x是受彐是受彐x的约束，而不是受的约束，而不是受 x的约束。的约束。Q(x,y)中的中的x,y是自由变元。是自由变元。2022-2-22142

16、.4 变元的约束3 约束变元的换名约束变元的换名 为了避免由于变元的约束与自由同时出现，引起概念为了避免由于变元的约束与自由同时出现，引起概念上的混乱，故可对约束变元进行换名。使得一个变元在一上的混乱，故可对约束变元进行换名。使得一个变元在一个公式中只呈一种形式出现，即呈自由出现或呈约束出现个公式中只呈一种形式出现，即呈自由出现或呈约束出现约束变元的换约束变元的换名规则名规则 (1) 对于约束变元可以换名，其更改的变元名称范围是量词对于约束变元可以换名，其更改的变元名称范围是量词中的指导变元，以及该量词作用域中所出现的该变元，在中的指导变元，以及该量词作用域中所出现的该变元，在公式的其余部份不

17、变。公式的其余部份不变。 (2) 换名时一定要更改为作用域中没有出现的变元名称。换名时一定要更改为作用域中没有出现的变元名称。 例题例题 2 对对 x(P(x)R(x,y)Q(x,y)换名。换名。 解解 可换名为：可换名为： z(P(z)R(z,y)Q(x,y)， 但不能改名为：但不能改名为： y(P(y)R(y,y)Q(x,y) 以及以及 z(P(z)R(x,y)Q(x,y)。 因为后两种更改都将使公式中量词的约束范围有所变动。因为后两种更改都将使公式中量词的约束范围有所变动。2022-2-22152.4 变元的约束 4 自由变元的代入自由变元的代入 对于公式中的自由变元，也允许更改，这种更

18、改叫做代对于公式中的自由变元，也允许更改，这种更改叫做代入。自由变元的代入，亦需遵守一定的规则，这个规则叫入。自由变元的代入，亦需遵守一定的规则，这个规则叫做自由变元的代入规则，现说明如下：做自由变元的代入规则，现说明如下： (1) 对于谓词公式中的自由变元，可以作代入，代入时对于谓词公式中的自由变元，可以作代入，代入时需对公式中出现该需对公式中出现该自由变元的每一处自由变元的每一处进行。进行。 (2) 用以代入的变元与原公式中所有变元的名称不能相用以代入的变元与原公式中所有变元的名称不能相同。同。 例题 3 对彐x(P(y)R(x,y)代入。 解 对y施行代入，经代入后公式为 彐x(P(z)

19、R(x,z) 但是彐x(P(x)R(x,x)与彐x(P(z)R(x,y)这两种代入都是与规则不符的。2022-2-22162.5谓词公式的等价与蕴涵1、谓词逻辑中常见的等价与蕴含关系、谓词逻辑中常见的等价与蕴含关系 l谓词公式的赋值谓词公式的赋值:l在谓词公式中常包含命题变元和客体变元，当客体在谓词公式中常包含命题变元和客体变元，当客体变元由确定的客体所取代，命题变元用确定的命题变元由确定的客体所取代，命题变元用确定的命题所取代时，就称作对谓词公式的赋值。一个谓词公所取代时，就称作对谓词公式的赋值。一个谓词公式经过赋值以后，就成为具有确定真值式经过赋值以后，就成为具有确定真值T或或F的命的命题

20、。题。2022-2-22172.5谓词公式的等价与蕴涵(1)命题逻辑中等价和蕴含的推广命题逻辑中等价和蕴含的推广 l定义定义1: 给定任何两个谓词公式给定任何两个谓词公式 A 和和 B，设它们有共同的，设它们有共同的个体域个体域E，若对，若对A和和B的任一组变元进行赋值，所得命题的任一组变元进行赋值，所得命题的真值相同，则称谓词公式的真值相同，则称谓词公式 A 和和 B 在在E上是等价的，并上是等价的，并记作：记作： ABl例如：例如：( x)(P(x)Q(x) ( x)(P(x) Q(x) l xP(x) x Q(x) ( x)P(x) x Q(x)l定义定义2: l设设A为谓词公式，若在任

21、何解释下，为谓词公式，若在任何解释下，A的真值都为真，则的真值都为真，则称称A为为永真式永真式；l若至少存在一种解释，使若至少存在一种解释，使A的真值为真，则称的真值为真，则称A为为可满足可满足式式；l若在任何解释下，若在任何解释下，A的真值都为假，则称的真值都为假，则称A为为矛盾式矛盾式，矛，矛盾式也称不可满足式。盾式也称不可满足式。l显然，永真式是可满足式。显然，永真式是可满足式。2022-2-2218(1)命题逻辑中等价和蕴含的推广l在命题演算中，任一永真公式，其中同一命题变元，在命题演算中，任一永真公式，其中同一命题变元，用同一公式取代时，其结果也是永真公式。我们可以用同一公式取代时，

22、其结果也是永真公式。我们可以把这个情况推广到谓词公式之中，当谓词演算中的公把这个情况推广到谓词公式之中，当谓词演算中的公式代替命题演算中永真公式的变元时，所得的谓词公式代替命题演算中永真公式的变元时，所得的谓词公式即为有效公式，故命题演算中的式即为有效公式，故命题演算中的等价公式表等价公式表和和蕴含蕴含式表式表都可推广到谓词演算中使用。都可推广到谓词演算中使用。l例如例如 2022-2-22192.5谓词公式的等价与蕴涵(2)量词否定的等价关系量词否定的等价关系l例例1 设设P(x)表示表示x今天来校上课，则今天来校上课，则P(x)表示表示x今天今天没有来校上课。没有来校上课。l故不是所有人今

23、天来上课与存在一些人今天没有来上课在意故不是所有人今天来上课与存在一些人今天没有来上课在意义上相同，义上相同， 即即l xP(x) 彐彐xP(x)。l又，不是存在一些人今天来上课与所有的人今天都没有来上又，不是存在一些人今天来上课与所有的人今天都没有来上课在意义上相同，即课在意义上相同，即l( x)P(x) ( x)P(x)。2022-2-22202.5谓词公式的等价与蕴涵(2)量词否定的等价关系量词否定的等价关系(量词转换规律量词转换规律)l为此我们得到公式：为此我们得到公式：l( x)P(x) ( x)P(x) l( x)P(x) ( x)P(x) l证明证明:设设u=a1,a2,an l

24、 ( x)P(x) l (P(a1)P(a2)P(an) l P(a1)P(a2) P(an) l ( x)P(x)2022-2-22212.5谓词公式的等价与蕴涵(2)量词否定的等价关系量词否定的等价关系(量词转换规律量词转换规律)l为此我们得到公式：为此我们得到公式：l( x)P(x) ( x)P(x) l( x)P(x) ( x)P(x) l证明证明:设设u=a1,a2,an l ( x)P(x) l (P(a1)P(a2)P(an) )l P(a1)P(a2) P(an) l ( x)P(x)2022-2-22222.5谓词公式的等价与蕴涵(3)量词辖域的扩张与收缩量词辖域的扩张与收缩

25、 l量词的作用域中，常有合取或析取项，如果其中一个为量词的作用域中，常有合取或析取项，如果其中一个为命题命题，则，则可将可将该命题该命题移至量词作用域之外。如：移至量词作用域之外。如：l x(A(x) B) x A(x) B l x(A(x) B) x A(x) B l x(BA(x) B x A(x)l x(A(x) B) x A(x) B l x(A(x) B) x A(x) B l x(BA(x) B x A(x)l这是因为在这是因为在B中不出现约束变元中不出现约束变元x，故它属于或不属于量词的作用，故它属于或不属于量词的作用域均有同等意义。域均有同等意义。 l注意：注意：l上面几式中，

26、上面几式中，B中不能出现约束变元中不能出现约束变元x。l x(A(x)B) x A(x) B 不成立不成立()l x(A(x)B) x A(x) B 不成立不成立()2022-2-22232.5谓词公式的等价与蕴涵l x(A(x)B) x A(x) Bl x(A(x)B) x A(x) Bl x(A(x)B) l x(A(x) B) l x A(x) B l x A(x) B l x A(x) B l同理同理, x(A(x)B) x A(x) B l x(A(x)B) l x(A(x) B) l x A(x) B l x A(x) B l x A(x) B 2022-2-22242.5谓词公式

27、的等价与蕴涵l当谓词的变元与量词的指导变元不同时，亦能有类似于上述的公式。例如l x(P(x)Q(y) xP(x)Q(y)l x( yP(x,y)Q(z) x yP(x,y)Q(z)2022-2-22252.5谓词公式的等价与蕴涵(4)量词分配的量词分配的等价等价关系关系 (量词分配律量词分配律)l量词与命题联结词之间存在不同的结合情况，下面举例量词与命题联结词之间存在不同的结合情况，下面举例说明一些等价公式说明一些等价公式 l x(A(x) B(x) x A(x) x B(x) l x(A(x) B(x) x A(x) x B(x) l证明证明:设设u=a1,a2,an l x(A(x) B

28、(x) l (A(a1) B(a1) (A(a2) B(a2) (A(an) B(an) l (A(a1) (A(a2) A(an) (B(a1) (B(a2) B(an) l x A(x) x B(x) l同理可证同理可证, x(A(x) B(x) x A(x) x B(x)2022-2-22262.5谓词公式的等价与蕴涵(5)量词分配的量词分配的蕴含蕴含关系关系 l量词与命题联结词之间存在一些不同的结合情况，有量词与命题联结词之间存在一些不同的结合情况，有些是蕴含公式。些是蕴含公式。l x A(x) x B(x)x(A(x) B(x) l x(A(x) B(x)x A(x) x B(x) l“所有的人都喜欢下棋或者所有的人都喜欢打牌所有的人都喜欢下棋或者所有的人都喜欢打牌”可可推出推出 l“所有的人都喜欢下棋或打牌所有的人都喜欢下棋或打牌”，反之不然。，反之不然。 l“有的人喜欢下棋和打牌有的人喜欢下棋和打牌”可推出可推出 l“有的人喜欢下棋并且有的人喜欢打牌有的人喜欢下棋并且有的人喜欢打牌”，反之不然。，反之不然。2022-2-22272.5谓词公式的等价与蕴涵(6)多重量词的