第2篇数理逻辑ch4谓词逻辑

1、第第 4 4 章章 谓谓 词词 逻逻 辑辑4-1 谓词的概念与表示谓词的概念与表示4-2 命题函数与量词命题函数与量词4-3 谓词公式与翻译谓词公式与翻译 4-4 变元的约束变元的约束 第第4 4章章 谓词演算谓词演算4-5 谓词演算的等价式与蕴涵式谓词演算的等价式与蕴涵式 4-6 前束范式前束范式 4-7 谓词演算的演绎与推理理论谓词演算的演绎与推理理论 4-1 4-1 谓词的概念与表示谓词的概念与表示 命题逻辑是一完整的语句为单位的，谓词逻辑将语命题逻辑是一完整的语句为单位的，谓词逻辑将语句细分为句细分为“对象对象” 和和“谓词谓词”。对象一般是语句的主语，。对象一般是语句的主语，谓词一般

2、是语句的谓语。谓词一般是语句的谓语。 谓词演算中把一切讨论对象都称为谓词演算中把一切讨论对象都称为，它们它们可以是客观世界中的具体客体，也可以是抽象的客体，可以是客观世界中的具体客体，也可以是抽象的客体，诸如数字、符号等。诸如数字、符号等。 确定的个体常用确定的个体常用a，b，c等到小写字母或字母串表示。等到小写字母或字母串表示。a，b，c等称为等称为（constants）。）。 不确定的个体常用字母不确定的个体常用字母x，y，z，u，v，w等来表等来表示。它们被称为示。它们被称为（variables）。）。 谓词演算中把讨论对象谓词演算中把讨论对象个体的全体称为个体的全体称为（domain

3、of individuals），常用字常用字母母D表示，并约定任何表示，并约定任何D都至少含有一个成员都至少含有一个成员。 当讨论对象遍及一切客体时，个体域特称为当讨论对象遍及一切客体时，个体域特称为（universe），），用字母用字母U表示。表示。 用来指明对象的性质或对象间关系的语句成用来指明对象的性质或对象间关系的语句成分称为分称为（），），用大写字母表示谓词，用用大写字母表示谓词，用小写字母表示变元，变元之间用小写字母表示变元，变元之间用“，”分割。分割。 通常把谓词所携空位的数目称为谓词的通常把谓词所携空位的数目称为谓词的。表表示单个客体性质的谓词是一元谓词，例如示单个客体性质的谓

4、词是一元谓词，例如P（x）;表示两表示两个客体之间关系的谓词是二元谓词，例如个客体之间关系的谓词是二元谓词，例如Q（x,y）;依此依此类推。类推。 含空位的写法有一个明显的缺点，可读性差。因此含空位的写法有一个明显的缺点，可读性差。因此常用变元来代替空位，它们被称为常用变元来代替空位，它们被称为，简称简称。 当谓词的空位上填入个体后，便产生一个关于该个当谓词的空位上填入个体后，便产生一个关于该个体的语句，这时它被称为体的语句，这时它被称为 。 4-2 4-2 命题函数与量词命题函数与量词（quantifiers）指数量词指数量词“对所有的对所有的”、“每一每一个个”、“对任意一个对任意一个”等

5、。等。 例如：例如： xA(x), xA(x), yP(y)yP(y)指数量词指数量词“存在一些存在一些”、“至少至少有一个有一个”、“对于一些对于一些”等等 。 例如：例如： xA(x)xA(x)、 yP(y)yP(y) 由量词确定的表达式都与个体域有关，因此，在由量词确定的表达式都与个体域有关，因此，在讨论带有量词的命题函数时，必须确定其个体域。讨论带有量词的命题函数时，必须确定其个体域。 在全总个体域中，对全称量词在全总个体域中，对全称量词 xH(x)xH(x)可以写成可以写成 x x（M(x)M(x)H(x)H(x)）；对存在量词）；对存在量词 xH(x)xH(x)可以写成可以写成 x

6、 x（M(x)M(x)H(x)H(x)）, , M(x)M(x)为特性谓词。为特性谓词。 我们把我们把 A(x1,x2,xn) 称为谓词演算的原子公式，其称为谓词演算的原子公式，其中中x1,x2,xn是客体变元，原子公式包括下述形式：是客体变元，原子公式包括下述形式： Q，A(x), A(x,y), A(f(x),y), A(x,y,z), A(a,y)等。等。 定义定义4-3.1 以下条款规定的符号串称为以下条款规定的符号串称为 predicate forrmula)，又称，又称谓词填式是公式，命题常元是公式（看作零元谓谓词填式是公式，命题常元是公式（看作零元谓词）词）,原子谓词公式是合式公

7、式。原子谓词公式是合式公式。如果如果A合式公式，那么合式公式，那么 (A) 是合式公式。是合式公式。如果如果A，B是合式公式，是合式公式，x为任一变元，为任一变元， 那么那么 ( xA)，( x A)， (AB)，(AB)， (AB)， (AB)）都是合式公式。都是合式公式。只有有限步使用（只有有限步使用（1）、（）、（2）、）、 条款所形条款所形成的符号串是合式公式。成的符号串是合式公式。 4-3 4-3 谓词公式与翻译谓词公式与翻译 在谓词公式中，在谓词公式中， 、 后面所跟的后面所跟的x叫做量词的叫做量词的指导指导变元变元或或作用变元作用变元， xA(x), xA(x), xP(x)xP

8、(x)中的中的A(x)A(x)和和P(x)P(x)分别叫做量词分别叫做量词 和和 的的作用域作用域或或辖域辖域。即。即当量当量词用于一谓词或复合谓词表达式时，该谓词或复合谓词词用于一谓词或复合谓词表达式时，该谓词或复合谓词表达式称为表达式称为(domains of quantifiers)。 在作用域中在作用域中x x的一切出现称为约束出现，即不可以取的一切出现称为约束出现，即不可以取值代入的变元称为值代入的变元称为( binding variables)。除去约束变元以外所出现的变元称为自由变元，即可取除去约束变元以外所出现的变元称为自由变元，即可取值代入的变元称为值代入的变元称为(free

9、 variables)。 4-4 4-4 变元的约束变元的约束 由前所述，由前所述，P(x1,x2,xn) 称为称为n元谓词元谓词。他有。他有n个相互独立的客体变元个相互独立的客体变元x1,x2,xn，若对其中的个，若对其中的个 k个个变元进行约束，则变元进行约束，则P(x1,x2,xn) 称变成称变成n-k元谓词元谓词。因此，谓词公式中如果没有自由变元出现，则该式就成因此，谓词公式中如果没有自由变元出现，则该式就成为一个命题。为一个命题。 为了避免由于变元的约束与自由同时出现，引起概为了避免由于变元的约束与自由同时出现，引起概念上的混乱，故可以对约束变元进行更名。使得一个变念上的混乱，故可以

10、对约束变元进行更名。使得一个变元在一个公式中具有一种形式出现，即呈自由出现或约元在一个公式中具有一种形式出现，即呈自由出现或约束出现。束出现。 约束变元更名规则：约束变元更名规则： （1）对于约束变元可以更名，其更改的变元名称范）对于约束变元可以更名，其更改的变元名称范围是量词中的指导变元，以及该量词作用域中所出现的围是量词中的指导变元，以及该量词作用域中所出现的该变元，在公式的其余部分不变。该变元，在公式的其余部分不变。 （2）更名时一定要更改为作用域中没有出现过的变）更名时一定要更改为作用域中没有出现过的变元名称。元名称。 自由变元代入规则：自由变元代入规则： （1）对于谓词公式中的自由变

11、元可以代入，代入时）对于谓词公式中的自由变元可以代入，代入时需要对公式中出现该自由变元的每一处进行代入。需要对公式中出现该自由变元的每一处进行代入。 （2）用以代入的变元与原公式中所有变元的名称不）用以代入的变元与原公式中所有变元的名称不能相同。能相同。 量词作用域中的约束变元，当论域的元素是有限时，量词作用域中的约束变元，当论域的元素是有限时，客体变元的所有可能的取代是可枚举的。客体变元的所有可能的取代是可枚举的。 设论域元素为：设论域元素为：a1 , a2 , , an 。 则有如下等价式：则有如下等价式： xA(x) xA(x) A(A(a1) ) A(A(a2 ) ) , A(A(an

12、) ) xA(x) xA(x) A(A(a1) ) A(A(a2 ) ) , A(A(an) ) 量词对变元的约束，往往与量词的出现顺序有关，量词对变元的约束，往往与量词的出现顺序有关，约定约定“量词按从左到右的顺序读出量词按从左到右的顺序读出”。 定义定义4-5.14-5.1 给定任何两个谓词公式给定任何两个谓词公式Wff Wff A A和和Wff Wff B B，设，设他们有共同的个体域他们有共同的个体域E E，若对若对A A和和B B的任一组变元进行赋值，的任一组变元进行赋值，所得命题的真值都相同，则称谓词公式所得命题的真值都相同，则称谓词公式A A和和B B在在E E上是等价上是等价的

13、的，并记作，并记作A A B B。 定义定义4-5.04-5.0 给定个体域给定个体域E E及公式及公式A A中各谓词符号的解中各谓词符号的解释释I I，如果，如果A A中个体变元中个体变元x x1 1 ,x ,xn n分别取值分别取值u u1 1 ,u ,un n时时A A真真，则称，则称；当；当x x1 1 ,x ,xn n无论取无论取E E中中怎样的个体怎样的个体u u1 1 ,u ,un n, , A A在在u u1 1 ,u ,un n处均真处均真，则称，则称。4-5 4-5 谓词演算的等价式和蕴涵式谓词演算的等价式和蕴涵式 定义定义4-5.34-5.3 如果在某一如果在某一个体域个

14、体域E、某一解释、某一解释I下，对下，对于变元的于变元的所有取值状况所有取值状况，A的取值的取值都假都假，则称公式，则称公式A为为不不的的。公式。公式A不可满足时也称不可满足时也称A为为。 定义定义4-5.24-5.2 给定个体域给定个体域E，若公式，若公式A在每一解释在每一解释I下下均真，那么称均真，那么称valid。若公式。若公式A对任何个体域对任何个体域E，均有均有E上永真上永真，则，则称称A为为，或称，或称A。 定义定义4-5.44-5.4 如果对某一如果对某一个体域个体域E、某一解释、某一解释I和变元和变元的的某一取值状况某一取值状况，A在在此处此处取值取值真真，则称公式，则称公式A

15、为为的的。 定义定义4-5.54-5.5 设谓词公式设谓词公式A A中含自由变元中含自由变元x x，设，设t t为一个为一个体项，且体项，且t t中无自由变元为中无自由变元为A A中的约束变元，那么称中的约束变元，那么称t t是是的的。 若若A是永真式，那么是永真式，那么对对A中变元可代入中变元可代入的代入实例都是永真的代入实例都是永真式。式。 设设A A，D D为谓词公式，为谓词公式，C C为为A A的子公式，且的子公式，且C C D D。若。若B B为将为将A A中子公式中子公式C C的某些出现（未必全部）替的某些出现（未必全部）替换为换为D D后所得的公式，那么后所得的公式，那么A A

16、B B。若公式若公式A A中无自由变元中无自由变元y y，那么，那么， xA(x) xA(x) yA(y),yA(y), xA(x) xA(x) yA(y)yA(y) （1）命题公式的推广）命题公式的推广 根据代入原理，命题演算中的公式可以推广到谓词根据代入原理，命题演算中的公式可以推广到谓词公式中。即命题演算中的等价公式表和蕴涵公式表都可公式中。即命题演算中的等价公式表和蕴涵公式表都可以推广到谓词演算中使用。以推广到谓词演算中使用。 （2）量词转化）量词转化 设设P (x)(x)表示个体表示个体x x具有性质具有性质P P。于是下面的语句表示。于是下面的语句表示的意义是等价的：的意义是等价的

17、： “ “不是所有的不是所有的 x x 都具有性质都具有性质P P。” “ “存在不具有性质存在不具有性质P P的的 x x 。”于是得到：于是得到： （ x x）P(x) P(x) （ x x） P(x) P(x) 同样，同样， “ “不存在具有性质不存在具有性质P P的的 x x 。” “ “所有的所有的 x x 都都不具有性质不具有性质P P。”于是得到：于是得到： （ x x）P(x) P(x) （ x x） P(x) P(x) （3）量词作用域的收缩与扩张）量词作用域的收缩与扩张 如果量的词作用域内有命题（命题内已经无个体如果量的词作用域内有命题（命题内已经无个体变元，真假值已经确定

18、了），则该命题可以移到量词变元，真假值已经确定了），则该命题可以移到量词作用域的外边。称之为作用域的外边。称之为量词作用域的收缩。量词作用域的收缩。 ( x)x) ( A(x)B )( A(x)B ) ( x)A(x)x)A(x) B B ( x)x) ( A(x)B )( A(x)B ) ( x)A(x)x)A(x) B B ( ( x)x) ( A(x)B )( A(x)B ) ( ( x)A(x)x)A(x) B B ( ( x)x) ( A(x)B )( A(x)B ) ( ( x)A(x)x)A(x) B B 量词作用域的扩张量词作用域的扩张: ( ( x) A(x) x) A(x)

19、 B B ) ) ( ( x)x) ( (A(x) A(x) B B ) ) ( ( ( x) A(x) x) A(x) B B ) ) ( x)x) ( (A(x) A(x) B B ) ) ( (B B ( x)( A(x)x)( A(x) ) ( x)x) ( (B B A(x)A(x) ) ( (B B ( x)( A(x)x)( A(x) ) ( x)x) ( (B B A(x)A(x) ) 证明（略）证明（略） （4 4）量词与命题联结词之间的一些等价式）量词与命题联结词之间的一些等价式 ( x)x) ( ( A(x)B(x) A(x)B(x) ) ( x)A(x)x)A(x)(

20、x)B(x)x)B(x) ( x)x) ( ( A(x)B(x) A(x)B(x) ) ( x)A(x)x)A(x)( x)B(x)x)B(x) （5 5）量词与命题联结词之间的一些蕴涵式）量词与命题联结词之间的一些蕴涵式 ( x)A(x)x)A(x)( x)B(x)x)B(x) ( x)x) （A(x)B(x)A(x)B(x)） ( x)x) ( ( A(x)B(x) A(x)B(x) ) ( x)A(x)x)A(x)( x)B(x)x)B(x) ( x) x) ( ( A(x) A(x)B(x)B(x) ) ( ( x)A(x)x)A(x)( ( x)B(x)x)B(x) ) ( x) x

21、) ( ( A(x) A(x) B(x)B(x) ) ( ( x)A(x)x)A(x)( ( x)B(x)x)B(x) ) 定义定义4-7.1 设设A A为为联结词联结词 ，的谓词公的谓词公式，式，A A* *为将为将A A中符号中符号，t t，f f， , , 分别换为分别换为，f f，t, t, ， 后所得的公式，那么称后所得的公式，那么称A A* *为为A A的的。（6 6）多个量词的使用）多个量词的使用 全称量词与存在量词在公式中出现的次序不能随全称量词与存在量词在公式中出现的次序不能随意更换。具有两个量词的谓词公式有如下关系：意更换。具有两个量词的谓词公式有如下关系： ( x) x)

22、 ( y) A(x,y) A(x,y) ( y) ) ( x) A(x,y)x) A(x,y) ( x) x) ( y) A(x,y) A(x,y) ( y) ) ( x) A(x,y)x) A(x,y) ( x) x) ( y) A(x,y) A(x,y) ( y) ) ( x) A(x,y)x) A(x,y) ( y) ) ( x) A(x,y)x) A(x,y) ( x) x) ( y) A(x,y) A(x,y) ( y) ) ( x) A(x,y)x) A(x,y) ( x) x) ( y) A(x,y) A(x,y) ( x) x) ( y) A(x,y) A(x,y) ( y)

23、) ( x) A(x,y)x) A(x,y) ( x) x) ( y) A(x,y) A(x,y) ( y) ) ( x) A(x,y)x) A(x,y) ( y) ) ( x) A(x,y)x) A(x,y) ( x) x) ( y) A(x,y) A(x,y)等价式等价式蕴涵式蕴涵式 定义定义4-6.1 4-6.1 公式公式A A称为公式称为公式A A的的prenex normal forms)prenex normal forms)，如果，如果A A A A，且，且A A形形如如 Q Q1 1x x1 1QQn nx xn nB B其中其中Q Q1 1，Q Qn n为量词为量词 或或 ，

24、B B中无量中无量词，词，联结词联结词，B B称为称为。当。当B B为合取为合取( (析取析取) )范式时，范式时，A A称为称为A A的的。 注意：注意：“一般的范式不要求只含一般的范式不要求只含，”，此定，此定义含盖了义含盖了定义定义3-6.23-6.2和和定义定义3-6.33-6.3的内容的内容 。4-6 4-6 前束范式前束范式 定义定义4-7.14-7.1 设设A A为为联结词联结词 ，的谓词的谓词公式，公式，A A* *为将为将A A中符号中符号，t t，f f， , , 分别换为分别换为，f f，t, t, ， 后所得的公式，那么称后所得的公式，那么称A A* *为为A A的的。 定理定理4-6.14-6.1 （） 对对任意任意谓词公式均可作出其谓词公式均可作出其前束范式前束范式，进而作出其，进而作出其前束合取范式前束合取范式或或前束析取范式前束析取范式。 证明方法