离散数学之谓词逻辑

1、2.1谓词的概念与表示谓词的概念与表示命题逻辑的局限性：命题逻辑的局限性：下列推理：下列推理：凡是人都是要死的。凡是人都是要死的。 苏格拉底是人。苏格拉底是人。 苏格拉底是要死的。苏格拉底是要死的。众所周知，这是真命题。但在命题逻辑中众所周知，这是真命题。但在命题逻辑中( P Q ) R ，难证其为重言式。难证其为重言式。原因：命题逻辑不考虑命题之间的内在联系原因：命题逻辑不考虑命题之间的内在联系和数量关系。和数量关系。办法：将命题再次细分。办法：将命题再次细分。2.1谓词的概念与表示谓词的概念与表示 谓词谓词在反映判断的句子中，用以刻划客体在反映判断的句子中，用以刻划客体的性质或关系的即是谓

2、词。的性质或关系的即是谓词。 例：例：(1)3是有理数。是有理数。(2)x是无理数。是无理数。 (3)阿杜与阿寺同岁。阿杜与阿寺同岁。 (4)x与与y有关系有关系L。 其中，其中，“是有理数是有理数”、“是无理数是无理数”、“与与同岁同岁”、“与与有关系有关系L”均为谓词。均为谓词。前两个是指明客体性质的谓词，后两个是指前两个是指明客体性质的谓词，后两个是指明两个客体之间关系的谓词。明两个客体之间关系的谓词。2.1谓词的概念与表示谓词的概念与表示 将上述谓词分别记作大写字母将上述谓词分别记作大写字母F、G、H、L，用小写字母表示客体名称，则上述可表示为：用小写字母表示客体名称，则上述可表示为：

3、 (1)F(3)(2)G(x) (3)H(a,b)a:阿杜阿杜b:阿寺阿寺 (4)L(x,y) 谓词填式谓词填式单独一个谓词不是完整的命题，单独一个谓词不是完整的命题，把谓词字母后填以客体所得的式子称为谓词把谓词字母后填以客体所得的式子称为谓词填式。填式。2.1谓词的概念与表示谓词的概念与表示 n n元谓词元谓词由由n个客体插入到固定位置上的个客体插入到固定位置上的谓词填式。谓词填式。 例如：例如：A(b)称作一元谓词，称作一元谓词，B(a, b)称作二元称作二元谓词，谓词，L(a, b, c)称作三元谓词，称作三元谓词，P(x1 , x2 , , xn)称作称作n元谓词。元谓词。 注意：代表

4、客体名称的字母，它在多元谓词注意：代表客体名称的字母，它在多元谓词中出现的次序是固定的，与事先约定的次序中出现的次序是固定的，与事先约定的次序有关，如有关，如L(a, b, c)和和L(b, c, a)代表两个不同代表两个不同的命题。的命题。2.2命题函数与量词命题函数与量词 例：例：H是谓词是谓词“能够到达山顶能够到达山顶”，t表示老虎，表示老虎，c表示汽车，表示汽车，z表示张三，那么表示张三，那么H(t), H(c), H(z)表示三个不同的命题，但它们有一个共同的表示三个不同的命题，但它们有一个共同的形式形式H(x)，当当x分别取分别取t, c, z 时。时。 L(x, y)表示表示“x

5、小于小于y”，那么那么L(2, 3)表示了一表示了一个真命题个真命题“2小于小于3”，而，而L(5, 1)表示假命题表示假命题“5小于小于1”。可以看出，。可以看出，L(x, y)本身不是一本身不是一个命题，只有当变元个命题，只有当变元x, y取特定的客体时，取特定的客体时，才是一个命题。才是一个命题。2.2命题函数与量词命题函数与量词 简单命题函数简单命题函数由一个谓词，一些客体变由一个谓词，一些客体变元组成的表达式称为简单命题函数。元组成的表达式称为简单命题函数。 n元谓词就是有元谓词就是有n个客体变元的命题函数。个客体变元的命题函数。 不带任何客体变元的谓词称为不带任何客体变元的谓词称为

6、0元谓词。元谓词。 复合命题函数复合命题函数由一个或由一个或n个简单命题函数个简单命题函数以及逻辑联结词组合而成的表达式称复合命以及逻辑联结词组合而成的表达式称复合命题函数。题函数。 2.2命题函数与量词命题函数与量词命题函数不是一个命题，只有客体变元取特命题函数不是一个命题，只有客体变元取特定名称时，才能成为一个命题。定名称时，才能成为一个命题。但客体变元在哪些范围内取特定的值，对是但客体变元在哪些范围内取特定的值，对是否成为命题及命题的真值极有影响。否成为命题及命题的真值极有影响。 例：例：R(x)表示表示“x是大学生是大学生”，如果，如果x的讨论范的讨论范围是某大学里班级中的学生，则围是

7、某大学里班级中的学生，则R(x)是永真式。是永真式。如果如果x的讨论范围是某中学里班级中的学生，的讨论范围是某中学里班级中的学生，则则R(x)是永假式。如果是永假式。如果x的讨论范围为一剧场的讨论范围为一剧场中的观众，那么对某些观众，中的观众，那么对某些观众，R(x)为真，对另为真，对另一些观众，一些观众，R(x)为假。为假。2.2命题函数与量词命题函数与量词 个体个体可以独立存在的具体的或抽象的客体。可以独立存在的具体的或抽象的客体。个体常量：具体的或特定的，一般用个体常量：具体的或特定的，一般用a,b,c,表示。表示。个体变元个体变元：抽象的或泛指的，一般用抽象的或泛指的，一般用x,y,z

8、,表示。表示。 个体域个体域个体变元的论述范围。个体变元的论述范围。 全总个体域全总个体域把各种个体域综合在一起作把各种个体域综合在一起作为论述范围的域。为论述范围的域。2.2命题函数与量词命题函数与量词 量词量词用来表示个体常量或变元之间数量用来表示个体常量或变元之间数量关系的词。量词分为两种：关系的词。量词分为两种：全 称 量 词 表 示全 称 量 词 表 示 “ 一 切一 切 ” , “ 所所有有”,“凡凡”,“每一个每一个”,“任意任意”等意的等意的词称为全称量词，记作词称为全称量词，记作 。 如：如： x 表示个体域内所有的表示个体域内所有的x。存 在 量 词 表 示存 在 量 词

9、表 示 “ 某 个某 个 ” , “ 对 于 一对 于 一些些”,“存在一些存在一些”,“至少有一个至少有一个”等意的等意的词称为存在量词，记作词称为存在量词，记作 。 如：如： y 表示个体域内存在一些表示个体域内存在一些y。2.2命题函数与量词命题函数与量词例：用谓词表达式写出下列命题。例：用谓词表达式写出下列命题。(1)凡是人都呼吸。凡是人都呼吸。(2)有的人是左撇子。有的人是左撇子。解：令解：令F(x)：x 呼吸。呼吸。G(x)：x 是左撇子。是左撇子。当个体域为当个体域为人类集合人类集合时：时：(1) xF(x) (2) xG(x)当个体域为当个体域为全总个体域全总个体域时：时：令令

10、M(x)：x 是人。是人。(1) x(M(x) F(x) (2) x(M(x)G(x)2.2命题函数与量词命题函数与量词约定：以后如不指定个体域，默认为全总个约定：以后如不指定个体域，默认为全总个体域。体域。 特性谓词在讨论带有量词的命题函数时，特性谓词在讨论带有量词的命题函数时，必须确定其个体域。当使用全总个体域时，必须确定其个体域。当使用全总个体域时，对客体变元的变化范围限制的词，称作特性对客体变元的变化范围限制的词，称作特性谓词。谓词。 如上例中，如上例中，M(x)为为F(x)和和G(x)的特性谓词，的特性谓词，它限定了变元它限定了变元x的范围。的范围。一般，对全称量词，特性谓词常作条件

11、的前一般，对全称量词，特性谓词常作条件的前件；对存在量词，特性谓词常作合取项。件；对存在量词，特性谓词常作合取项。2.2命题函数与量词命题函数与量词例：将下列命题符号化，并讨论其真值。例：将下列命题符号化，并讨论其真值。(1)所有的人都长头发。所有的人都长头发。解解: 令令M(x): x是人。是人。F(x): x 长头发。则长头发。则 x(M(x) F(x) 真值为真值为0(2)有的人吸烟。有的人吸烟。解解: 令令M(x): x是人。是人。S(x): x 吸烟。则吸烟。则 x(M(x)S(x) 真值为真值为12.2命题函数与量词命题函数与量词(3)没有人登上过木星。没有人登上过木星。解解: 令

12、令M(x): x是人。是人。D(x): x 登上过木星。则登上过木星。则 x(M(x)D(x) 真值为真值为1(4)清华大学的学生未必都是高素质的。清华大学的学生未必都是高素质的。解解: 令令Q(x): x 是清华大学的学生。是清华大学的学生。H(x): x 是是高素质的。则高素质的。则 x(Q(x) H(x) 真值为真值为1 或或 x(Q(x) H(x)可见，有些命题的符号化形式不止一种。可见，有些命题的符号化形式不止一种。2.2命题函数与量词命题函数与量词至此，至此，下列推理即可解决：下列推理即可解决： 凡是人都是要死的。凡是人都是要死的。 苏格拉底是人。苏格拉底是人。 苏格拉底是要死的。

13、苏格拉底是要死的。 令令M(x): x 是人。是人。D(x): x 是要死的。是要死的。s: 苏格苏格拉底。则谓词表达式为：拉底。则谓词表达式为：( x)(M(x) D(x) M(s) D(s)2.3 谓词公式与翻译谓词公式与翻译 一阶语言一阶语言一阶语言一阶语言F 的字母表定义如下的字母表定义如下: (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) 谓词符号：F,G,H,Fi,Gi,Hi,i1. (5) 量词符号： ， . (6) 联结词符号：，. (7) 括号与逗号

14、：( , ) , , .2.3 谓词公式与翻译谓词公式与翻译 F 的项：的项：(1)(1)个体常项和个体变项都是项个体常项和个体变项都是项。(2)(2)若若f(x1, x2, , xn)是任意的是任意的n元函数，元函数，t1, t2, , tn是任意的是任意的n个项，则个项，则f(t1, t2, , tn)是是项。项。(3)(3)所有的项都是有限次使用所有的项都是有限次使用(1),(2)(1),(2)得到的。得到的。 原子公式原子公式若若A(x1, x2, , xn)是是F 的任意的任意n元谓词，元谓词，t1, t2, , tn是是F 的任意的任意n个项，则称个项，则称A(t1, t2, ,

15、tn)为谓词演算的原子公式。为谓词演算的原子公式。2.3 谓词公式与翻译谓词公式与翻译 谓词演算的合式公式谓词演算的合式公式/ /谓词公式谓词公式(1)原子公式是合式公式。原子公式是合式公式。(2)若若A 是合式公式，则是合式公式，则 ( A) 也是合式公式。也是合式公式。(3)若若A和和B是合式公式，则是合式公式，则(AB)，(AB)，(AB)，(AB)也是合式公式。也是合式公式。(4)若若A是合式公式，是合式公式，x是是A中出现的任何变元，中出现的任何变元，则则 x xA和和 x xA，也是合式公式。，也是合式公式。(5)只有有限次应用规则只有有限次应用规则(1)(4)构成的符号串构成的符

16、号串才是合式公式。才是合式公式。2.3 谓词公式与翻译谓词公式与翻译约定：最外层的圆括号可以省略。但量词后约定：最外层的圆括号可以省略。但量词后面若有括号则不能省略。面若有括号则不能省略。例：将下列命题符号化例：将下列命题符号化 。(1)没有不能表示为分数的有理数。没有不能表示为分数的有理数。解解: 令令Q(x):x是有理数。是有理数。W(x):x能表示成分数。能表示成分数。 则则 x(Q(x)W(x) 或或 x(Q(x) W(x)2.3 谓词公式与翻译谓词公式与翻译(2)在北京买菜的人不全是外地人。在北京买菜的人不全是外地人。解解: 令令B(x):x在北京买菜的人。在北京买菜的人。F(x):

17、x是外地人。是外地人。则则 x(B(x)F(x)或或 x(B(x) F(x)例：将下列命题符号化例：将下列命题符号化 。(1)火车都比轮船快。火车都比轮船快。解解: 令令T(x):x是火车。是火车。S(x):x是轮船。是轮船。F(x,y):x 比比y 跑得快。则跑得快。则 x y(T(x)S(y) F(x,y)2.3 谓词公式与翻译谓词公式与翻译(2)有的火车比有的汽车快。有的火车比有的汽车快。解解: 令令T(x):x是火车。是火车。C(x):x是汽车。是汽车。F(x,y):x 比比y 跑得快。则跑得快。则 x y(T(x)C(y)F(x,y)(3)不存在比所有火车都快的汽车。不存在比所有火车

18、都快的汽车。解解: 令令T(x):x是火车。是火车。C(x):x是汽车。是汽车。F(x,y):x 比比y 跑得快。则跑得快。则 x(C(x) y(T(y)F(x,y)或或 x(C(x) y(T(y)F(y,x)2.4 变元的约束变元的约束 给定给定A为一谓词公式，其中有一部分公式形为一谓词公式，其中有一部分公式形为为 xP(x)或或 xP(x)。 和和 后面所跟的后面所跟的x，称称为相应量词的为相应量词的指导变元指导变元。P(x)称为相应量词称为相应量词的的作用域作用域/ /辖域辖域。在在 x x和和 x x的辖域中，的辖域中，x x的的所有出现都称为所有出现都称为x x在公式在公式A中的中的

19、约束出现约束出现，所有约束出现的变元，叫做所有约束出现的变元，叫做约束变元约束变元。A中中不是约束出现的变元均称作不是约束出现的变元均称作自由变元自由变元。2.4 变元的约束变元的约束(1) x(F(x) G(x,y) x是指导变元，量词是指导变元，量词 的辖域为的辖域为(F(x)G(x,y)，其中，其中，x是约束出现两次，是约束出现两次，y是自由出现一次。是自由出现一次。(2) x F(x,y) y G(x,y) x是指导变元，量词是指导变元，量词 的辖域是的辖域是F(x,y)，其中，其中，x是约束出现一次，是约束出现一次，y是自由出现一次；同时，是自由出现一次；同时，y也是指导变元，量词也

20、是指导变元，量词 的辖域是的辖域是G(x,y)，其其中，中，y是约束出现一次，是约束出现一次，x是自由出现一次。是自由出现一次。2.4 变元的约束变元的约束(3) x y (F(x,y)G(y,z) x H(x,y,z) x、y是指导变元，对应量词是指导变元，对应量词 、 的辖域为的辖域为 y(F(x,y)G(y,z)和和(F(x,y)G(y,z) ，其中，其中x是约束出现一次，是约束出现一次，y是约束出现两次，是约束出现两次，z是是自由出现一次；后一个自由出现一次；后一个x也是指导变元，量也是指导变元，量词词 的辖域为的辖域为H(x,y,z)，其中其中x是约束出现一是约束出现一次，次，y、z

21、是自由出现一次。是自由出现一次。2.4 变元的约束变元的约束例例: (1) x(H(x,y) y(W(y)L(x,y,z) (2) x(H(x)W(y) y(F(x)L(x,y,z) 为了避免由于变元的约束与自由同时出现，为了避免由于变元的约束与自由同时出现，引起概念上的混乱，故可对约束变元进行引起概念上的混乱，故可对约束变元进行换换名名。使得一个变元在一个公式中只呈一种形。使得一个变元在一个公式中只呈一种形式出现，即呈式出现，即呈自由出现自由出现或呈或呈约束出现约束出现。 一个公式的约束变元所使用的名称符号是无一个公式的约束变元所使用的名称符号是无关紧要的，即关紧要的，即 xP(x)与与 y

22、P(y)具有相同的意具有相同的意义，义， xP(x)与与 yP(y)意义也相同。意义也相同。2.4 变元的约束变元的约束约束变元的换名约束变元的换名规则：规则：对于约束变元可以换名，其更改的变元名对于约束变元可以换名，其更改的变元名称范围是量词中的指导变元，以及该量词称范围是量词中的指导变元，以及该量词作用域中所出现的该变元，公式的其余部作用域中所出现的该变元，公式的其余部分不变。分不变。换名时一定要更改为作用域中没有出现的换名时一定要更改为作用域中没有出现的变元名称。变元名称。例例: 对对 x(H(x,y) y(W(y)L(x,y,z)换名。换名。解解: 可换名为可换名为 x(H(x,y)

23、u(W(u)L(x,u,z)2.4 变元的约束变元的约束对于公式中的自由变元，也允许更改，这对于公式中的自由变元，也允许更改，这种更改叫做种更改叫做代入代入/代替代替。自由变元的代入自由变元的代入规则：规则：对于谓词公式中的自由变元，可以作代入，对于谓词公式中的自由变元，可以作代入，代入时需对公式中出现该自由变元的每一代入时需对公式中出现该自由变元的每一处进行。处进行。1) 用以代入的变元与原公式中所有变元的名用以代入的变元与原公式中所有变元的名称不能相同。称不能相同。2.4 变元的约束变元的约束例例:对对 x(H(x)W(y)y(F(x)L(x,y,z)代入。代入。解解:经代入后公式为经代入

24、后公式为 x(H(x)W(v) y(F(u)L(u,y,z)2.4 变元的约束变元的约束 A(x1, x2, , xn)是是n元谓词，它有元谓词，它有n个相互独个相互独立的自由变元。若对其中立的自由变元。若对其中k个变元进行约束个变元进行约束则成则成n - k元谓词。若谓词公式中没有自由变元谓词。若谓词公式中没有自由变元出现，则该式就成为一个命题。元出现，则该式就成为一个命题。 当论域的元素有限时，可以消去公式中的量当论域的元素有限时，可以消去公式中的量词。设论域元素为词。设论域元素为a1, a2, , an。则则 ( x)A(x)A(a1)A(a2)A(an) ( x)A(x)A(a1)A(

25、a2)A(an)2.4 变元的约束变元的约束 量词对变元的约束，往往与量词的次序有关。量词对变元的约束，往往与量词的次序有关。命题中的多个量词，我们约定从左到右的次命题中的多个量词，我们约定从左到右的次序读出。注意序读出。注意: 量词的次序不能颠倒，否则量词的次序不能颠倒，否则将与原命题不符。将与原命题不符。2.5 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式 赋值赋值/解释解释在谓词公式中常包含命题变元在谓词公式中常包含命题变元和客体变元，当客体变元由确定的客体所取和客体变元，当客体变元由确定的客体所取代，命题变元用确定的命题所取代时，就称代，命题变元用确定的命题所取代时，就称作对谓词公

26、式作对谓词公式赋值赋值。一个谓词公式经过赋值。一个谓词公式经过赋值以后，就成为命题。以后，就成为命题。 等价等价给定任何两个谓词公式给定任何两个谓词公式wff A和和wff B，设它们有共同的个体域设它们有共同的个体域E，若对若对A和和B的变元的变元的任一组真值指派，所得真值均相同，则称的任一组真值指派，所得真值均相同，则称谓词公式谓词公式A和和B在在E上是上是等价等价的，并记作的，并记作AB。 永真式永真式/逻辑有效式逻辑有效式给定任意谓词公式给定任意谓词公式wff A，其个体域为其个体域为E，对于对于A的任一组真值指派，的任一组真值指派，wff A皆为皆为1，则称公式则称公式A在在E上是上

27、是有效的有效的/永永真的真的。 不可满足式不可满足式/永假式永假式一个谓词公式一个谓词公式wff A，如果在所有赋值下都为如果在所有赋值下都为0，则称该则称该wff A是是不不可满足的可满足的/永假的永假的。 可满足式可满足式一个谓词公式一个谓词公式wff A，如果至少如果至少在一种赋值下为在一种赋值下为T，则称该则称该wff A是是可满足的可满足的。2.5 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式 谓词演算中的等价式和蕴涵式谓词演算中的等价式和蕴涵式命题演算中命题演算中的等价公式表和蕴含公式表都可的等价公式表和蕴含公式表都可推广推广到谓词到谓词演算中使用。演算中使用。 消去量词的等价

28、式消去量词的等价式 量词否定的等价式量词否定的等价式（量词的转化律）量词的转化律） ( x)P(x)( x) P(x) ， ( x)P(x)( x) P(x) 证明：证明：(可在有限个体域上证明可在有限个体域上证明) 2.5 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式设个体域中的客体变元为设个体域中的客体变元为a1, a2, , an，则则 ( x)A(x) (A(a1)A(a2)A(an) A(a1) A(a2) A(an) ( x) A(x) ( x)A(x) (A(a1)A(a2)A(an) A(a1) A(a2) A(an) ( x) A(x)2.5 谓词演算的等价式与蕴含式谓词

29、演算的等价式与蕴含式 量词作用域的扩张与收缩的等价式量词作用域的扩张与收缩的等价式 x(A(x)B) x A(x)B x(A(x)B) x A(x)B x(A(x)B) x A(x)B x(BA(x) Bx A(x) x(A(x)B) x A(x)B x(A(x)B) x A(x)B x(A(x)B) x A(x)B x(BA(x) Bx A(x)2.5 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式 以上各等价式中的以上各等价式中的B不含客体变元不含客体变元x ; 或含有或含有与量词指导变元与量词指导变元x 不同的变元不同的变元 , 如如y , z 等。等。 试证明试证明 x(A(x)B)

30、 x A(x)B 证：左证：左 x( A(x)B) x A(x)B x A(x)B x A(x)B（右）右）2.5 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式 量词分配的等价式量词分配的等价式 x(A(x)B(x) x A(x) x B(x) x(A(x)B(x) x A(x) x B(x) 量词与命题联结词间的一些蕴含式量词与命题联结词间的一些蕴含式 x A(x) x B(x) x(A(x)B(x) x(A(x)B(x) x A(x) x B(x) x(A(x) B(x) x A(x) x B(x) x(A(x) B(x) x A(x) x B(x) x A(x) x B(x) x(A

31、(x) B(x)2.5 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式 具有两个量词的二元谓词公式（共八种）具有两个量词的二元谓词公式（共八种） x y A(x,y) y x A(x,y) x y A(x,y) y x A(x,y) x y A(x,y) y x A(x,y) y x A(x,y) x y A(x,y) 其中：其中： x y A(x,y) y x A(x,y) x y A(x,y) y x A(x,y) 后四种均不等价，故全称量词和存在量词在后四种均不等价，故全称量词和存在量词在公式中出现的次序，不能随意更换。公式中出现的次序，不能随意更换。2.5 谓词演算的等价式与蕴含式谓

32、词演算的等价式与蕴含式2.6 前束范式前束范式 前束范式前束范式一个公式如果量词均包含在全一个公式如果量词均包含在全式的开头，它们的作用域延伸到整个公式的式的开头，它们的作用域延伸到整个公式的末尾，则该公式叫做末尾，则该公式叫做前束范式前束范式。其形式为。其形式为(v1)(v2)(vn)A ，其中其中是量词是量词 或或 ，vi (i=1,2,n)是客体变元，是客体变元，A 是没有量词的是没有量词的谓词公式。谓词公式。如：如： x y(F(x)G(y) H(x,y) x y(F(x,y)G(y,z) x H(x,y,z) 2.6 前束范式前束范式 Th1(前束范式存在定理前束范式存在定理)任意一

33、个谓词公任意一个谓词公式，均和一个前束范式等价。式，均和一个前束范式等价。 本定理说明任何公式的前束范式都是存在的，本定理说明任何公式的前束范式都是存在的，但一般不是唯一的。但一般不是唯一的。 求法：求法： 利用对合律、德利用对合律、德摩根律、量词转化律把否摩根律、量词转化律把否定深入到命题变元和谓词填式的前面；定深入到命题变元和谓词填式的前面；1) 利用换名和代入规则，量词作用域的扩张和利用换名和代入规则，量词作用域的扩张和收缩等价式，把量词提到前面。收缩等价式，把量词提到前面。 2.6 前束范式前束范式例例: 求下列公式的前束范式。求下列公式的前束范式。(1) x F(x) x G(x)解

34、：解： xF(x) xG(x) xF(x) x G(x) (量词否定等价式量词否定等价式) x(F(x) G(x) (量词分配等价式量词分配等价式)或或 xF(x) yG(y) (换名规则换名规则) xF(x) y G(y) (量词否定等价式量词否定等价式) x(F(x) y G(y) (量词辖域扩张等价式量词辖域扩张等价式) x y(F(x) G(y) (量词辖域扩张等价式量词辖域扩张等价式)2.6 前束范式前束范式(2) x F(x) x G(x)解：原式解：原式 xF(x) yG(y) (换名规则换名规则) xF(x) y G(y) (量词否定等价式量词否定等价式) x(F(x) y G

35、(y) (量词辖域扩张等价式量词辖域扩张等价式) x y(F(x) G(y) (量词辖域扩张等价式量词辖域扩张等价式)(3) x F(x) x G(x)解：原式解：原式 xF(x) yG(y) (换名规则换名规则) x y(F(x)G(y) (量词辖域扩张等价式量词辖域扩张等价式)2.6 前束范式前束范式(4) x F(x,y) y G(x,y)解：解： xF(x,y)yG(x,y) t F(t,y)w G(x,w) (换名规则换名规则) t w(F(t,y)G(x,w) (量词辖域扩张等价式量词辖域扩张等价式)或或 x F(x,t)y G(w,y) (代入规则代入规则) x y(F(x,t)

36、G(w,y) (量词辖域扩张等价式量词辖域扩张等价式)(5) x F(x) x G(x) 解：原式解：原式 xF(x)yG(y) ( (换名规则换名规则) ) x y(F(x)G G(y) ( (量词辖域扩张等价式量词辖域扩张等价式) )2.6 前束范式前束范式(6)( x F(x,y)y G(y)x H(x,y,z) 解：原式解：原式( x F(x,y)b G(b)c H(c,y,z) x b(F(x,y)G(b)c H(c,y,z) x b c (F(x,y)G(b)H(c,y,z) 2.6 前束范式前束范式 前束合取范式前束合取范式一个一个wff A如果具有如下形如果具有如下形式，则称为

37、式，则称为前束合取范式前束合取范式。 (v1)(v2)(vn)(A11A12A1k1) (A21A22A2k2)(Am1Am2Amkm) ， 其中其中是量词是量词 或或 ，vi (i=1,2,n)是客体变是客体变元，元，Ai j是原子公式或其否定。是原子公式或其否定。 Th2(前束合取范式存在定理前束合取范式存在定理)每一个每一个wff A都可转化为与其等价的前束合取范式。都可转化为与其等价的前束合取范式。2.6 前束范式前束范式 前束析取范式前束析取范式一个一个wff A如果具有如下形如果具有如下形式，则称为式，则称为前束析取范式前束析取范式。 (v1)(v2)(vn)(A11A12A1k1

38、) (A21A22A2k2)(Am1Am2Amkm) ， 其中其中是量词是量词 或或 ，vi (i=1,2,n)是客体变是客体变元，元，Ai j是原子公式或其否定。是原子公式或其否定。 Th3(前束析取范式存在定理前束析取范式存在定理)每一个每一个wff A都可转化为与其等价的前束析取范式。都可转化为与其等价的前束析取范式。2.6 前束范式前束范式 任一个任一个wff A转换为等价的前束合转换为等价的前束合(析析)取范取范式的步骤：式的步骤： 消去公式中出现的多余量词；消去公式中出现的多余量词； 利用换名、代入规则使所有约束变元均不利用换名、代入规则使所有约束变元均不相同，并且使约束变元和自由

39、变元不同；相同，并且使约束变元和自由变元不同；1) 将谓词公式中出现的联结词均转化成将谓词公式中出现的联结词均转化成 , , ；2.6 前束范式前束范式 利用对合律，德利用对合律，德摩根律及量词转化律，将摩根律及量词转化律，将谓词公式中的谓词公式中的 深入到命题变元和谓词填式深入到命题变元和谓词填式的前面；的前面； 利用量词作用域的扩张和收缩等价式，将利用量词作用域的扩张和收缩等价式，将量词推到左边，扩大量词作用域至整个公量词推到左边，扩大量词作用域至整个公式。式。2.7 谓词演算的推理理论谓词演算的推理理论 命题演算中的推理规则，如命题演算中的推理规则，如P、T和和CP规则规则等也可在谓词演

40、算的推理理论中应用。等也可在谓词演算的推理理论中应用。 但在谓词推理中，某些前提与结论可能受量但在谓词推理中，某些前提与结论可能受量词限制，为了能使用命题演算中的等价式和词限制，为了能使用命题演算中的等价式和蕴含式，必须在推理过程中有消去和添加量蕴含式，必须在推理过程中有消去和添加量词的规则。词的规则。2.7 谓词演算的推理理论谓词演算的推理理论(1)全称指定规则（简记为全称指定规则（简记为US） ( ( x)P(x) x)P(x) P(c) P(c) 如果对论域中所有客体如果对论域中所有客体x ，P(x)成立，则成立，则对论域中某个任意客体对论域中某个任意客体c ，P(c)成立。成立。2.7

41、 谓词演算的推理理论谓词演算的推理理论(2)全称推广规则（简记为全称推广规则（简记为UG） P(x) P(x) ( ( x)P(x)x)P(x) 如果能够证明对论域中每一个客体如果能够证明对论域中每一个客体c c断言断言P(c)P(c)都成立，则可得到结论都成立，则可得到结论( ( x)P(x)x)P(x)成成立。立。2.7 谓词演算的推理理论谓词演算的推理理论(3)存在指定规则（简记为存在指定规则（简记为ES） ( ( x) P(x)x) P(x) P(c) P(c) 如果对于论域中某些客体如果对于论域中某些客体P(x)P(x)成立，则必成立，则必有某个特定客体有某个特定客体c c，使使P(

42、c)P(c)成立。应注意，成立。应注意，指定的客体指定的客体c c不是任意的。不是任意的。2.7 谓词演算的推理理论谓词演算的推理理论(4)存在推广规则（简记为存在推广规则（简记为EG） P(c) P(c) x P(x)x P(x) 如果对论域中某个特定客体如果对论域中某个特定客体c ，有有P(c)成成立，则在论域中，必存在立，则在论域中，必存在x 使得使得P(x)成立。成立。2.7 谓词演算的推理理论谓词演算的推理理论例：构造下列推理的证明。例：构造下列推理的证明。前提：前提： x (A(x)B(x)， x A(x)结论：结论： x B(x)证明：证明：(1) x A(x) P (2) A(c) (1)ES (3) x (A(x)B(x