《离散数学之谓词逻辑讲义》由会员分享，可在线阅读，更多相关《离散数学之谓词逻辑讲义（57页珍藏版）》请在金锄头文库上搜索。
1、离散数学之谓词逻辑讲义2.1谓词的概念与表示谓词的概念与表示谓词谓词在反映判断的句子中，用以刻划客体在反映判断的句子中，用以刻划客体的性质或关系的即是谓词。的性质或关系的即是谓词。 例：例：(1)3是有理数。是有理数。(2)x是无理数。是无理数。 (3)阿杜与阿寺同岁。阿杜与阿寺同岁。 (4)x与与yL。 其其中中，“是是有有理理数数”、“是是无无理理数数”、“与与同同岁岁”、“与与有有关关系系L”均均为为谓谓词词。前前两两个个是是指指明明客客体体性性质质的的谓谓词词，后后两两个个是是指指明明两个客体之间关系的谓词。两个客体之间关系的谓词。2.1谓词的概念与表示谓词的概念与表示 将将上上述述谓
2、谓词词分分别别记记作作大大写写字字母母F、G、H、L，用用小小写写字字母母表表示示客客体体名名称称，则则上上述述可可表表示示为：为： (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)称作二元称作二元谓词，
3、谓词，L(a, b, c)称作三元谓词，称作三元谓词，P(x1 , x2 , , xn)称作称作n元谓词。元谓词。 注注意意：代代表表客客体体名名称称的的字字母母，它它在在多多元元谓谓词词中中出出现现的的次次序序是是固固定定的的，与与事事先先约约定定的的次次序序有有关关，如如L(a, b, c)和和L(b, c, a)代代表表两两个个不不同同的命题。的命题。2.2命题函数与量词命题函数与量词 例例：H是是谓谓词词“能能够够到到达达山山顶顶”，t表表示示老老虎虎，c表表示示汽汽车车，z表表示示张张三三，那那么么H(t), H(c), H(z)表表示示三三个个不不同同的的命命题题，但但它它们们有有
4、一一个个共共同的形式同的形式H(x)，当当x分别取分别取t, c, z 时。时。 L(x, y)表表示示“x小小于于y”，那那么么L(2, 3)表表示示了了一一个个真真命命题题“2小小于于3”，而而L(5, 1)表表示示假假命命题题“5小小于于1”。可可以以看看出出，L(x, y)本本身身不不是是一一个个命命题题，只只有有当当变变元元x, y取取特特定定的的客客体体时时，才是一个命题。才是一个命题。2.2命题函数与量词命题函数与量词简单命题函数简单命题函数由一个谓词，一些客体变由一个谓词，一些客体变元组成的表达式称为简单命题函数。元组成的表达式称为简单命题函数。 n元谓词就是有元谓词就是有n个
5、客体变元的命题函数。个客体变元的命题函数。 不带任何客体变元的谓词称为不带任何客体变元的谓词称为0元谓词。元谓词。复合命题函数复合命题函数由一个或由一个或n个简单命题函数个简单命题函数以及逻辑联结词组合而成的表达式称复合命以及逻辑联结词组合而成的表达式称复合命题函数。题函数。 2.2命题函数与量词命题函数与量词命题函数不是一个命题，只有客体变元取特命题函数不是一个命题，只有客体变元取特定名称时，才能成为一个命题。定名称时，才能成为一个命题。但客体变元在哪些范围内取特定的值，对是但客体变元在哪些范围内取特定的值，对是否成为命题及命题的真值极有影响。否成为命题及命题的真值极有影响。 例：例：R(x
6、)表示表示“x是大学生是大学生”，如果，如果x的讨论范的讨论范围是某大学里班级中的学生，则围是某大学里班级中的学生，则R(x)是永真式。是永真式。如果如果x的讨论范围是某中学里班级中的学生，的讨论范围是某中学里班级中的学生，则则R(x)是永假式。如果是永假式。如果x的讨论范围为一剧场中的讨论范围为一剧场中的观众，那么对某些观众，的观众，那么对某些观众，R(x)为真，对另一为真，对另一些观众，些观众，R(x)为假。为假。2.2命题函数与量词命题函数与量词个体个体可以独立存在的具体的或抽象的客体。可以独立存在的具体的或抽象的客体。个体常量：具体的或特定的，一般用个体常量：具体的或特定的，一般用a,
7、b,c,表示。表示。个体变元个体变元：抽象的或泛指的，一般用抽象的或泛指的，一般用x,y,z,表示。表示。个体域个体域个体变元的论述范围。个体变元的论述范围。全全总总个个体体域域把把各各种种个个体体域域综综合合在在一一起起作作为论述范围的域。为论述范围的域。2.2命题函数与量词命题函数与量词量量词词用用来来表表示示个个体体常常量量或或变变元元之之间间数数量量关系的词。量词分为两种：关系的词。量词分为两种：全全称称量量词词表表示示“一一切切”,“所所有有”,“凡凡”,“每每一一个个”,“任任意意”等等意意的的词词称称为为全全称量词，记作称量词，记作 。 如：如： x 表示个体域内所有的表示个体域
8、内所有的x。存存在在量量词词 表表示示“某某个个”,“对对于于一一些些”,“存存在在一一些些”,“至至少少有有一一个个”等等意意的的词称为存在量词，记作词称为存在量词，记作 。 如：如： y 表示个体域内存在一些表示个体域内存在一些y。2.2命题函数与量词命题函数与量词例：用谓词表达式写出下列命题。例：用谓词表达式写出下列命题。(1)凡是人都呼吸。凡是人都呼吸。(2)有的人是左撇子。有的人是左撇子。解：令解：令F(x)：x 呼吸。呼吸。G(x)：x 是左撇子。是左撇子。当个体域为人类集合时：当个体域为人类集合时：(1) xF(x) (2) xG(x)当个体域为全总个体域时：当个体域为全总个体域
9、时：令令M(x)：x 是人。是人。(1) x(M(x) F(x) (2) x(M(x)G(x)2.2命题函数与量词命题函数与量词约约定定：以以后后如如不不指指定定个个体体域域，默默认认为为全全总总个个体域。体域。特性谓词在讨论带有量词的命题函数时，特性谓词在讨论带有量词的命题函数时，必须确定其个体域。当使用全总个体域时，必须确定其个体域。当使用全总个体域时，对客体变元的变化范围限制的词，称作特性对客体变元的变化范围限制的词，称作特性谓词。谓词。 如上例中，如上例中，M(x)为为F(x)和和G(x)的特性谓词，的特性谓词，它限定了变元它限定了变元x的范围。的范围。一般，对全称量词，特性谓词常作条
10、件的前一般，对全称量词，特性谓词常作条件的前件；对存在量词，特性谓词常作合取项。件；对存在量词，特性谓词常作合取项。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)没有人登上过木星。没有人登上过木星。解解:
11、令令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命题函数与量词命题函数与量词至此，至此，下列推理即可解决：下列推理即可解决： 凡是人都是要死的。凡是人都是要死的。 苏格拉底是人。苏格拉底是人。 苏格拉底是要死的。
12、苏格拉底是要死的。 令令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) 括号与逗号：(
13、, ) , , .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, , tn)
14、为谓词演算的原子公式。为谓词演算的原子公式。2.3 谓词公式与翻译谓词公式与翻译谓词演算的合式公式谓词演算的合式公式/ /谓词公式谓词公式(1)原子公式是合式公式。原子公式是合式公式。(2)若若A 是合式公式，则是合式公式，则 ( A) 也是合式公式。也是合式公式。(3)若若A和和B是是合合式式公公式式，则则(AB)，(AB)，(AB)，(AB)也是合式公式。也是合式公式。(4)若若A是是合合式式公公式式，x是是A中中出出现现的的任任何何变变元元，则则 x xA和和 x xA，也是合式公式。，也是合式公式。(5)只只有有有有限限次次应应用用规规则则(1)(4)构构成成的的符符号号串串才是合式公
15、式。才是合式公式。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):x是是外外地地人
16、。则人。则 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)不存在比所有火车都快的汽车。不存在比所有火车都快的汽车。解解: 令令
17、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中中的的约约束束出出现现，所所有有约约束束
18、出出现现的的变变元元，叫叫做做约约束束变变元元。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也是指导变元，量词也是指导变元，量词 的辖域是的辖域是G
19、(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是自由出现一次。是自由出现一次。2.4 变元的约
20、束变元的约束例例: (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)与与 yP(y)具有相同的意具有相同的意义，义， xP(x)与与
21、 yP(y)意义也相同。意义也相同。2.4 变元的约束变元的约束约束变元的换名规则：约束变元的换名规则：1)对于约束变元可以换名，其更改的变元名对于约束变元可以换名，其更改的变元名称范围是量词中的指导变元，以及该量词称范围是量词中的指导变元，以及该量词作用域中所出现的该变元，公式的其余部作用域中所出现的该变元，公式的其余部分不变。分不变。2)换名时一定要更改为作用域中没有出现的换名时一定要更改为作用域中没有出现的变元名称。变元名称。例例: 对对 x(H(x,y) y(W(y)L(x,y,z)换名。换名。解解: 可换名为可换名为 x(H(x,y) u(W(u)L(x,u,z)2.4 变元的约束变
22、元的约束对于公式中的自由变元，也允许更改，这对于公式中的自由变元，也允许更改，这种更改叫做种更改叫做代入代入/代替代替。自由变元的代入规则：自由变元的代入规则：1)对于谓词公式中的自由变元，可以作代入，对于谓词公式中的自由变元，可以作代入，代入时需对公式中出现该自由变元的每一代入时需对公式中出现该自由变元的每一处进行。处进行。2)用以代入的变元与原公式中所有变元的名用以代入的变元与原公式中所有变元的名称不能相同。称不能相同。2.4 变元的约束变元的约束例例:对对 x(H(x)W(y)y(F(x)L(x,y,z)代入。代入。解解:经代入后公式为经代入后公式为 x(H(x)W(v) y(F(u)L
23、(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(a2)A(an)2.4 变元的约束变元的约束量词对
24、变元的约束，往往与量词的次序有关。量词对变元的约束，往往与量词的次序有关。命题中的多个量词，我们约定从左到右的次命题中的多个量词，我们约定从左到右的次序读出。注意序读出。注意: 量词的次序不能颠倒，否则量词的次序不能颠倒，否则将与原命题不符。将与原命题不符。2.5 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式赋值赋值/解释解释在谓词公式中常包含命题变元在谓词公式中常包含命题变元和客体变元，当客体变元由确定的客体所取和客体变元，当客体变元由确定的客体所取代，命题变元用确定的命题所取代时，就称代，命题变元用确定的命题所取代时，就称作对谓词公式赋值。一个谓词公式经过赋值作对谓词公式赋值。一个谓词
25、公式经过赋值以后，就成为命题。以后，就成为命题。等价等价给定任何两个谓词公式给定任何两个谓词公式wff A和和wff B，设它们有共同的个体域设它们有共同的个体域E，若对若对A和和B的变的变元的任一组真值指派，所得真值均相同，则元的任一组真值指派，所得真值均相同，则称谓词公式称谓词公式A和和B在在E上是等价的，并记作上是等价的，并记作AB。永真式永真式/逻辑有效式逻辑有效式给定任意谓词公式给定任意谓词公式wff A，其个体域为其个体域为E，对于对于A的任一组真值指派，的任一组真值指派，wff A皆为皆为1，则称公式则称公式A在在E上是上是有效的有效的/永永真的真的。不可满足式不可满足式/永假式
26、永假式一个谓词公式一个谓词公式wff A，如果在所有赋值下都为如果在所有赋值下都为0，则称该则称该wff A是是不可满足的不可满足的/永假的永假的。可满足式可满足式一个谓词公式一个谓词公式wff A，如果至少如果至少在一种赋值下为在一种赋值下为T，则称该则称该wff A是可满足的。是可满足的。2.5 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式谓词演算中的等价式和蕴涵式谓词演算中的等价式和蕴涵式命题演算中命题演算中的等价公式表和蕴含公式表都可推广到谓词的等价公式表和蕴含公式表都可推广到谓词演算中使用。演算中使用。消去量词的等价式消去量词的等价式量词否定的等价式量词否定的等价式（量词的转化律
27、）量词的转化律） ( 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 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式量词作用域的扩张与收缩的等价式量词作用域的扩张
28、与收缩的等价式 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) x A(x)B 证：左证：左 x( A(x)B) x A(x)B x
29、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(x) B(x)2.5 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式具
30、有两个量词的二元谓词公式（共八种）具有两个量词的二元谓词公式（共八种） 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 谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式2.6 前束范式前束范式前束范式前束范式一个公式如果量词均
31、包含在全式一个公式如果量词均包含在全式的开头，它们的作用域延伸到整个公式的末的开头，它们的作用域延伸到整个公式的末尾，则该公式叫做前束范式。其形式为尾，则该公式叫做前束范式。其形式为( 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(前束范式存在定理前束范式存在定理)任意一个谓词公任意一个谓词公式，均和一个前束范式等价。式，均和一个前束范式等价。本
32、本定定理理说说明明任任何何公公式式的的前前束束范范式式都都是是存存在在的的，但一般不是唯一的。但一般不是唯一的。求法：求法：1)利用对合律、德利用对合律、德摩根律、量词转化律把否摩根律、量词转化律把否定深入到命题变元和谓词填式的前面；定深入到命题变元和谓词填式的前面；2)利用换名和代入规则，量词作用域的扩张和利用换名和代入规则，量词作用域的扩张和收缩等价式，把量词提到前面。收缩等价式，把量词提到前面。 2.6 前束范式前束范式例例: 求下列公式的前束范式。求下列公式的前束范式。(1) x F(x) x G(x)解：解： xF(x) xG(x) xF(x) x G(x) (量词否定等价式量词否定
33、等价式) 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(y) (量量词词辖辖域域扩扩张张等等价价式式) x y(F(x) G(y) (量
34、量词词辖辖域域扩扩张张等等价价式式)(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)G(w,y) (量量词词辖辖域域扩扩张张等等价价式式)(5) x F(x) x G
35、(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如果具有如下形如果具有如下形式，则称为前束合取范式。式，则称为前束合取范式。 ( v1)( v2)( vn)(A11A12
36、A1k1) (A21A22A2k2)(Am1Am2Amkm) ， 其中其中 是量词是量词 或或 ，vi (i=1,2,n)是客体变是客体变元，元，Ai j是原子公式或其否定。是原子公式或其否定。Th2(前束合取范式存在定理前束合取范式存在定理)每一个每一个wff A都可转化为与其等价的前束合取范式。都可转化为与其等价的前束合取范式。2.6 前束范式前束范式前束析取范式前束析取范式一个一个wff A如果具有如下形如果具有如下形式，则称为前束析取范式。式，则称为前束析取范式。 ( v1)( v2)( vn)(A11A12A1k1) (A21A22A2k2)(Am1Am2Amkm) ， 其中其中 是
37、量词是量词 或或 ，vi (i=1,2,n)是客体变是客体变元，元，Ai j是原子公式或其否定。是原子公式或其否定。Th3(前束析取范式存在定理前束析取范式存在定理)每一个每一个wff A都可转化为与其等价的前束析取范式。都可转化为与其等价的前束析取范式。2.6 前束范式前束范式任一个任一个wff A转换为等价的前束合转换为等价的前束合(析析)取范取范式的步骤：式的步骤：1)消去公式中出现的多余量词；消去公式中出现的多余量词；2)利用换名、代入规则使所有约束变元均不利用换名、代入规则使所有约束变元均不相同，并且使约束变元和自由变元不同；相同，并且使约束变元和自由变元不同；3)将谓词公式中出现的
38、联结词均转化成将谓词公式中出现的联结词均转化成 , , ；2.6 前束范式前束范式4)利用对合律，德利用对合律，德摩根律及量词转化律，摩根律及量词转化律，将谓词公式中的将谓词公式中的 深入到命题变元和谓词填深入到命题变元和谓词填式的前面；式的前面；5)利用量词作用域的扩张和收缩等价式，将利用量词作用域的扩张和收缩等价式，将量词推到左边，扩大量词作用域至整个公量词推到左边，扩大量词作用域至整个公式。式。2.7 谓词演算的推理理论谓词演算的推理理论命题演算中的推理规则，如命题演算中的推理规则，如P、T和和CP规则规则等也可在谓词演算的推理理论中应用。等也可在谓词演算的推理理论中应用。但在谓词推理中
39、，某些前提与结论可能受量但在谓词推理中，某些前提与结论可能受量词限制，为了能使用命题演算中的等价式和词限制，为了能使用命题演算中的等价式和蕴含式，必须在推理过程中有消去和添加量蕴含式，必须在推理过程中有消去和添加量词的规则。词的规则。2.7 谓词演算的推理理论谓词演算的推理理论(1)全称指定规则（简记为全称指定规则（简记为US） ( ( x)P(x) x)P(x) P(c) P(c)如果对论域中所有客体如果对论域中所有客体x ，P(x)成立，则对成立，则对论域中某个任意客体论域中某个任意客体c ，P(c)成立。成立。2.7 谓词演算的推理理论谓词演算的推理理论(2)全称推广规则（简记为全称推广
40、规则（简记为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(c)P(c)成立。应注意，成立。应注意，指定的客体指定的客体c c不是任意的
41、。不是任意的。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) P (4) A(c)B(c)
42、 (3)US (5) B(c) (2)(4) 假言推理假言推理 (6) x B(x) (5)EG注意：注意：(1) (3)引入的顺序不可更改引入的顺序不可更改! 2.7 谓词演算的推理理论谓词演算的推理理论例：证明凡是人都是要死的。例：证明凡是人都是要死的。 苏格拉底是人。苏格拉底是人。 苏格拉底是要死的。苏格拉底是要死的。解解: 令令M(x): x是是人人。D(x): x是是要要死死的的。a: 苏苏格格拉底。即要证拉底。即要证 x(M(x)D(x) , M(a) D(a) 证明证明(1) x (M(x)D(x) P (2) M(a)D(a) (1)US (3) M(a) P (4) D(a)
43、 (2)(3) I2.7 谓词演算的推理理论谓词演算的推理理论例：学术委员会的每个成员都是博士并且是例：学术委员会的每个成员都是博士并且是教授。有些成员是青年人。因而有的成员是教授。有些成员是青年人。因而有的成员是青年博士。青年博士。解：先将命题符号化解：先将命题符号化.A(x):x是学术委员会成员。是学术委员会成员。B(x):x是博士。是博士。 J(x):x是教授。是教授。 H(x):x是青年人。是青年人。前提前提: x(A(x)B(x)J(x) , x(A(x)H(x)结论结论: x(A(x)H(x)B(x)2.7 谓词演算的推理理论谓词演算的推理理论证明证明 (1) x (A(x)H(x
44、) P (2) A(c)H(c) (1)ES (3) x (A(x)B(x) J(x) P (4) A(c)B(c)J(c) (3)US (5) A(c) (2) 化简化简 (6) H(c) (2) 化简化简 (7) B(c)J(c) (4)(5) 假言推理假言推理 (8) B(c) (7) 化简化简 (9) A(c)H(c)B(c) (5)(6)(8) 合取合取 (10) x(A(x)H(x)B(x) (9)EG2.7 谓词演算的推理理论谓词演算的推理理论例例：有有些些病病人人相相信信所所有有的的医医生生。但但是是病病人人都都不不相信骗子。所以，医生都不是骗子。相信骗子。所以，医生都不是骗子。解：先将简单命题符号化解：先将简单命题符号化A(x):x是病人。是病人。 B(x):x是医生。是医生。J(x):x是骗子。是骗子。 H(x,y):x相信相信y。前提前提: x(A(x) y(B(y)H(x,y) , x(A(x)y(J(y) H(x,y)结论结论: x(B(x) J(x)证明证明 (1) x(A(x) y(B(y)H(x,y) P (2) A(c) y(B(y)H(c,y) (1)ES
