《02离散数学课件资料.ppt》由会员分享，可在线阅读，更多相关《02离散数学课件资料.ppt（52页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、在在命命题题逻逻辑辑中中，命命题题是是命命题题演演算算的的基基本本单单位位，不不关关心心每每个个简简单单命命题题反反映映的的具具体体内内容容，没没有有进进一一步步研研究究命命题题的的内内部部结结构构，因因而而在在实实际应用中存在很多缺陷。际应用中存在很多缺陷。著名的苏格拉底三段论著名的苏格拉底三段论:“所有的人都是要死的所有的人都是要死的,苏格拉底是人苏格拉底是人,所以是苏所以是苏格拉底是要死的。格拉底是要死的。”p:所有的人是要死的所有的人是要死的;q:苏格拉底是人苏格拉底是人;r:苏格拉底是要死的苏格拉底是要死的.由上述文字构造的命题逻辑推理结构为由上述文字构造的命题逻辑推理结构为:(p
2、q)r 可知可知:(p q)r不是一个重言式不是一个重言式,因此因此,按命题逻辑按命题逻辑的方法的方法,无法证明上述问题无法证明上述问题.为为了了在在命命题题演演算算中中，反反映映命命题题的的内内在在联联系系，常常常常要要将将简简单单命命题题分分解解成成个个体体词词、谓谓词词、量量词词等等，并并对对它它们们的的形形式式结结构构及及逻逻辑辑关关系系加加以以研研究究，总总结结出出正正确确的的推推理理形形式式和和规规则则，这这就就是是本本章章一一阶阶逻逻辑辑要要研研究的内容。究的内容。12/20/20224离散数学个体词个体词：可以独立存在的客体，既可以是抽象的概念，：可以独立存在的客体，既可以是抽
3、象的概念，也可以是具体的事物。也可以是具体的事物。谓谓 词词：用来刻划个体词的：用来刻划个体词的性质性质或个体词之间或个体词之间关系关系的。的。如：李明、自然数、如：李明、自然数、如：如：(1)(1)是无理数是无理数(性质性质)(2)小李小李比比小赵小赵高高2 2厘米厘米(关系关系)简单命题总可以被分解成简单命题总可以被分解成个体词个体词和和谓词谓词两部分。两部分。2.12.1一阶逻辑基本概念一阶逻辑基本概念个体常项：指个体常项：指具体具体或或特定特定的个体的词，用小写字的个体的词，用小写字母母a,b,c,，表示。表示。个体变项：表示个体变项：表示抽象抽象的或的或泛指泛指的个体的词，用的个体的
4、词，用x,y,z,，表示。表示。个体域：个体变项的取值范围。个体域：个体变项的取值范围。全总个体域：当无特殊声明时全总个体域：当无特殊声明时,表示宇宙间的一切表示宇宙间的一切 事物组成的个体域，又称事物组成的个体域，又称全总域全总域。谓词常项谓词常项：表示具体性质或关系的谓词，用大写：表示具体性质或关系的谓词，用大写英文字母英文字母F，G，表示。表示。谓词变项谓词变项：表示抽象的或泛指的性质或关系的谓词，：表示抽象的或泛指的性质或关系的谓词，也用大写字母也用大写字母F，G，表示。表示。一般根据上、下文区分常项与变项。一般根据上、下文区分常项与变项。个体变项个体变项x具有性质具有性质F：记作记作
5、F(x)个体变项个体变项x、y具有关系具有关系L：记作记作L(x,y)(1)是无理数是无理数(性质性质)(2)小李小李比比小赵小赵高高2厘米厘米(关系关系)设设F(x):x 是无理数是无理数,，设设H(x,y):x 比比 y 高高2厘米厘米a:小李，小李，b:小赵小赵则则(2)可表示为可表示为：H(a,b)(不是不是H(b,a)将下列两命题符号化：将下列两命题符号化：则则(1)可表示为可表示为F(a)解：解：解：解：元数：在谓词中所包含的元数：在谓词中所包含的个体词个体词(变项变项)数数。n元谓词：元谓词：含含n(n 1)1)个个体词的谓词，可个个体词的谓词，可用用D(x1,x2,，xn)表示
6、。表示。一元谓词表性质；一元谓词表性质；二元或更多元谓词表示关系。二元或更多元谓词表示关系。0 0元谓词：元谓词：不含不含个体变项个体变项的谓词的谓词 。如：如：a为为2，b为为3，L(a，b)是是0元谓词。元谓词。例例1.1.将下列命题用将下列命题用0 0元谓词符号化元谓词符号化(1)2是素数且是偶数是素数且是偶数 ；(2)如果如果2 2大于大于3 3，则，则2 2大于大于4 4；(3)如果张明比李民高，李民比赵亮高，如果张明比李民高，李民比赵亮高，则张明比赵亮高则张明比赵亮高 ；（1 1）解：）解：）解：）解：设设F(x)：x是素数是素数，G(x)：x是偶数是偶数，a：2 2，则，则(1)
7、符号化为符号化为F(a)G(a)(0(0元谓词元谓词)（2 2）解：）解：）解：）解：引入二元谓词：引入二元谓词：L(x,y)：x比比y大大 a:2 2，b:3 3，c:4 4，(2)符号化为符号化为L(a,b)L(a,c)（3 3）解：）解：）解：）解：引入二元谓词：引入二元谓词：H(x,y)：x比比y高高 a:张张,b:李李,c:赵赵,(3)符号化为符号化为(H(a,b)H(H(b,c c)H(a,c)(1)(1)所有的人都是要死的所有的人都是要死的;(2)(2)有些人活百岁以上有些人活百岁以上;考虑以下形式命题的符号化考虑以下形式命题的符号化:量量 词词表示数量的词，分表示数量的词，分全
8、称量词全称量词与与存在量词存在量词。：一切、所有的、任意一切、所有的、任意的；的；：存在着、有一个、至少有一个；存在着、有一个、至少有一个；x：个体域中所有个体；个体域中所有个体；x：个体域中个体域中存在存在某个个体；某个个体；xF(x)：个体域中所有个体具有性质个体域中所有个体具有性质F F；xF(x)：个体域中存在着某个个体具有性质个体域中存在着某个个体具有性质F F。将命题将命题“所有的人都是要死的所有的人都是要死的”符号化符号化 (个体域为人类集合个体域为人类集合）符号化为：符号化为：xF(x)其中其中F(x)表示：表示：x是要死的。是要死的。将命题将命题“有的人活百岁以上有的人活百岁
9、以上”符号化符号化 (个体域为人类集合个体域为人类集合）符号化为：符号化为：xF(x)其中其中F(x)表示：表示：x活百岁以上。活百岁以上。特性谓词特性谓词：在全总个体域的情况下，为了：在全总个体域的情况下，为了指定指定某个某个个体变项的范围，引入特性谓词。个体变项的范围，引入特性谓词。将命题将命题(公式公式)“)“所有的人都是要死的所有的人都是要死的”符号符号化化 M(x)：x是人是人(特性谓词特性谓词)F(x)：x是要死的是要死的命题命题(公式公式)符号化为符号化为：x(M(x)F(x)分析一下：分析一下：它与它与 xF(x)有什么区别？有什么区别？解：解：解：解：有了个体词、谓词、量词等
10、概念，我们就可有了个体词、谓词、量词等概念，我们就可以更细致地刻划命题公式。以更细致地刻划命题公式。将命题将命题(公式公式)“)“有些人活百岁以上有些人活百岁以上”符号化符号化 M(x)：x是人是人(特性谓词特性谓词)F(x)：x活百岁以上活百岁以上命题命题(公式公式)符号化为符号化为：x(M(x)F(x)分析一下：分析一下：它与它与 xF(x)有什么区别？有什么区别？解：解：解：解：使用量词时使用量词时,应该注意以下几点应该注意以下几点:1 .在不同的个体域中，命题符号化的形式可能不一样在不同的个体域中，命题符号化的形式可能不一样;2.如没有事先给出个体域如没有事先给出个体域,都应以全总个体
11、域为个体域。都应以全总个体域为个体域。3.在引入特性谓词后，引入全称量词与存在量词符号化在引入特性谓词后，引入全称量词与存在量词符号化的形式是不同的的形式是不同的;4.当个体域为有限集时，如当个体域为有限集时，如D=a1,a2,a3,an,对于任对于任意的谓词意的谓词A(x)，都有，都有(1)xA(x)A(a1)A(a2).A(an)(2)xA(x)A(a1)A(a2)A(an)5.多个量词同时出现时，不能随意颠倒顺序多个量词同时出现时，不能随意颠倒顺序;x y H(x，y),其中其中H(x，y):x+y=5 量词颠倒顺序成立吗量词颠倒顺序成立吗?例例:对于任意的对于任意的x,存在存在y,使得
12、使得x+y=5,取个体域为实数集合取个体域为实数集合,该如何符号化该如何符号化?例例例例2.2.2.2.在谓词逻辑中将下列命题符号化在谓词逻辑中将下列命题符号化(1)(1)对所有的对所有的x，均有均有x21=(x+1)(x1)(个体域为自然数集个体域为自然数集)(2)(2)存在存在x,使得使得x+5=2 (个体域为自然数集个体域为自然数集)(4)(4)存在着偶素数存在着偶素数(5)(5)没有不犯错误的人没有不犯错误的人(3)(3)凡偶数均能被凡偶数均能被2 2整除整除(6)(6)在北京工作的人未必都是北京人在北京工作的人未必都是北京人(7)(7)一切人都不一样高一切人都不一样高(8)(8)每个
13、自然数都有后继数每个自然数都有后继数(9)(9)有的自然数无先驱数有的自然数无先驱数(10)(10)有的有理数是整数有的有理数是整数 (个体域为实数集个体域为实数集)(11)每个人都有一些缺点。每个人都有一些缺点。符号化方法符号化方法1、找到所有的个体词找到所有的个体词;2 2、是否要引入特性谓词是否要引入特性谓词;3 3、描述个体词性质：性质谓词描述个体词性质：性质谓词(一元一元););描述个体词关系：关系谓词描述个体词关系：关系谓词(二元二元););4 4、按原命题的实际意义进行刻划。按原命题的实际意义进行刻划。设设F(x)：x满足满足x21=(x+1)(x 1)(1)符号化符号化：xF(
14、x)解：解：解：解：(1)对所有的对所有的x，均有均有x2 1=(x+1)(x1)(个体域为自然数个体域为自然数集集)(2)存在存在 x,使得使得x+5=2 (个体域为自然数集个体域为自然数集)解：解：解：解：设设G(x)：x满足满足x+5=2(2)符号化符号化：xG(x)解：解：解：解：要引入特性谓词要引入特性谓词：F(x)：x是偶数是偶数G(x)：x能被能被2 2整除整除解：解：解：解：F(x)：x是偶数是偶数 G(x)：x是素数是素数 符号化：符号化：x(F(x)G(x)符号化符号化：x(F(x)G(x)(4)存在着偶素数存在着偶素数(3)凡偶数均能被凡偶数均能被2 2整除整除解：解：解
15、：解：特性谓词特性谓词M(x)：x是人是人解：解：解：解：F(x)：x是在北京工作的人是在北京工作的人，G(x)：x是北京人是北京人F(x)：x犯错误犯错误符号化：符号化：x(M(x)F(x)或或 x(M(x)F(x)符号化：符号化：x(F(x)G(x)(5)(5)没有不犯错误的人没有不犯错误的人(6)在北京工作的人未必都是北京人在北京工作的人未必都是北京人或：或：x(F(x)G(x)解：解：解：解：M(x)：x是人是人,L(x，y)：x与与y一样高一样高 H(x，y)：x与与y是同一个人是同一个人 符号化：符号化：x y(M(x)M(y)H(x，y)L(x,y)(7)7)一切人都不一样高一切
16、人都不一样高(8)每个自然数都有后继数每个自然数都有后继数解：解：解：解：F(x)：x自然数自然数 H(x，y)：y是是x的后继数的后继数符号化：符号化：x(F(x)y(F(y)H(x，y)或：或：x y(M(x)M(y)H(x，y)L(x,y)或：或：x(F(x)y(F(y)H(x，y)解：解：解：解：F(x)：x是自然数是自然数，H(x，y)：y是是x的先驱数的先驱数符号化：符号化：x(F(x)y(F(y)H(x，y)解：解：解：解：F(x)：x是有理数是有理数，G(x)：x是整数是整数符号化符号化：x(F(x)G(x)(9)9)有的自然数无先驱数有的自然数无先驱数(10)有的有理数是整数
17、有的有理数是整数 (个体域为实数集个体域为实数集)或：或：x(F(x)y(F(y)H(x，y)解：解：解：解：F(x,y)：x都有都有y，M(x)：x是人，是人，G(y)：y是缺点是缺点或或：(x)(y)(M(x)(G(y)F(x,y)符号化符号化：(x)(M(x)(y)(G(y)F(x,y)(11)每个人都有一些缺点。每个人都有一些缺点。2.2 2.2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释谓词演算中的合式公式：谓词演算中的合式公式：原子公式：不出现原子公式：不出现命题联结词命题联结词和和量词量词的命题的命题 函数函数P(x1,x2,xn)，其中其中x1，x2，xn为个体变项或常项。为
18、个体变项或常项。(1)(1)原子谓词公式是合式公式；原子谓词公式是合式公式；(2)(2)若若A A是合式公式，则是合式公式，则 A也是；也是；一、一阶逻辑合式一、一阶逻辑合式(谓词谓词)公式的概念公式的概念(3)(3)若若A和和B是合式公式，则是合式公式，则(A B),(A B)，(AB)和和(A B)也是也是 ；(4)(4)如果如果A是合式公式，是合式公式，x是是A中出现的个体变项，中出现的个体变项，则则 (x)A和和(x)A是合式公式是合式公式 ；(5)(5)只有有限次地应用规则只有有限次地应用规则(1)(1)、(2)(2)、(3)(3)、(4)(4)所所得到的公式才是合式公式得到的公式才
19、是合式公式。谓词合式公式即按规则谓词合式公式即按规则(1)(1)、(2)(2)、(3)(3)、(4)(4)、(5)(5)由原子公式、联结词、量词及括号组成的字符串，由原子公式、联结词、量词及括号组成的字符串，但最外层括号可以省略。但最外层括号可以省略。指导变元及作用域指导变元及作用域 在在谓谓词词公公式式中中，形形如如(x)P(x)或或(x)P(x)的的部分，叫做部分，叫做公式的约束部分公式的约束部分。量量词词，后后面面的的x叫叫做做量量词词的的作作用用变变元元，或或指指导变元导变元，P(x)叫做叫做量词的作用域量词的作用域。在在作作用用域域中中，x的的一一切切出出现现为为约约束束出出现现，非
20、非约束出现的其它变元叫约束出现的其它变元叫自由出现变元自由出现变元。在谓词公式中，我们还用到以下概念。在谓词公式中，我们还用到以下概念。二、谓词公式的改写二、谓词公式的改写解解解解：(y)R(x,y)中中，指指导导变变元元是是y，的的作作用用域域为为R(x,y)，其中其中y是约束出现，是约束出现，x是自由出现的。是自由出现的。(1)(x)(P(x)(y)R(x,y)；在整个合式公式中，在整个合式公式中，x是作用变元是作用变元(指导变元指导变元),),的作用域的作用域(P(x)(y)R(x,y)，x,y 都是约束出现都是约束出现的，的，x约束出现约束出现2 2次，次，y约束出现约束出现1 1次。
21、次。例例例例3 3 3 3.指出下列合式公式中的指导变元，量词的作指出下列合式公式中的指导变元，量词的作用域及变元约束的情况。用域及变元约束的情况。(2)(x)(y)(P(x,y)Q(y,z)(x)R(x,y)在在(x)R(x,y)中中，x是是指指导导变变元元，的的作作用用域域为为R(x,y)，其其中中x约约束束出出现现1 1次次，y自自由由出出现现1 1次次。在在整整个个合合式式公公式式中中，x约约束束出出现现2 2次次，y约约束束出出现现2 2次次，自自由由出出现现1 1次次，z自由出现自由出现1 1次。次。解：解：解：解：(x)(y)(P(x,y)Q(y,z)，x,y是作用变元，是作用变
22、元，两个量词两个量词 的作用域都是的作用域都是(P(x,y)Q(y,z)，其中其中x,y均为约束出现，均为约束出现，x约束出现约束出现1 1次，次，y约束出现约束出现2 2次，次，z为自由出现为自由出现1 1次。次。解解解解：(x)Q(x,z)中中x是是作作用用变变元元，的的辖辖域域为为Q(x，z)，其中其中 x 约束出现，约束出现，z自由出现；自由出现；(3)(x)(P(x)(x)Q(x,z)(y)R(x,y)Q(x,y)；(y)R(x,y)中，中，y是作用变元，是作用变元，的辖域为的辖域为R(x,y)，其中其中y约束出现，约束出现，x自由出现；自由出现；在在(x)(P(x)(x)Q(x,z
23、)(y)R(x,y)中，作用变元为中，作用变元为x，的作用域为的作用域为(P(x)(x)Q(x,z)(y)R(x,y),但但Q(x,z)中的中的x不是不是 的作用变元，的作用变元，x,y均为约束出现，均为约束出现，z自由出现；自由出现；Q(x,y)中，中，x,y为自由变元。为自由变元。在整个公式中，在整个公式中，x约束出现约束出现3 3次，自由出现次，自由出现1 1次次，y约束出现约束出现1 1次，自由出现次，自由出现1 1次次，z自由出现自由出现1 1次。次。1.1.换名规则换名规则：2 2.代替规则代替规则将量词作用域中出现的某个将量词作用域中出现的某个约束出现约束出现的个体变项及的个体变
24、项及对应的指导变项改成另一个作用域中没有出现过的对应的指导变项改成另一个作用域中没有出现过的个体变项符号，公式的其余部分不变。个体变项符号，公式的其余部分不变。考虑到谓词公式中，有的个体变项既可以约束出考虑到谓词公式中，有的个体变项既可以约束出现，又可以自由出现，为避免这种双重性可能引起的现，又可以自由出现，为避免这种双重性可能引起的混淆，我们要将谓词公式进行改写，改写规则如下混淆，我们要将谓词公式进行改写，改写规则如下：对某对某自由出现自由出现的个体变项用与原公式中所有个体的个体变项用与原公式中所有个体变项符号不同的变项符号去代替，且处处代替。变项符号不同的变项符号去代替，且处处代替。(1)
25、(x)(P(x)(y)R(x,y)；(2)(x)(y)(P(x,y)Q(y,z)(x)P(x,y)；(3)(x)(P(x)(x)Q(x,z)(y)R(x,y)Q(x,y)；换名规则与代替规则可避免有的个体变项既换名规则与代替规则可避免有的个体变项既可以约束出现，又可以自由出现。可以约束出现，又可以自由出现。例例4.4.试对下列公式换名或代替。试对下列公式换名或代替。第一步换名第一步换名:(x)(y)(P(x,y)Q(y,z)(u)R(u,y)；第二步代替第二步代替:(x)(y)(P(x,y)Q(y,z)(u)R(u,v)；第一步换名第一步换名:(x)(P(x)(u)Q(u,z)(y)R(x,y
26、)Q(x,y)第二步代替第二步代替:(x)(P(x)(u)Q(u,z)(y)R(x,y)Q(s,t)(2)(x)(y)(P(x,y)Q(y,z)(x)R(x,y)；(3)(x)(P(x)(x)Q(x,z)(y)R(x,y)Q(x,y)；解：解：(1)(x)(P(x)(y)R(x,y)；不用；不用改写改写例例例例5.5.5.5.求下列谓词公式的真值：求下列谓词公式的真值：(x)(P(x)Q(x)，其中其中P(x)：x=1，Q(x)：x=2，且个体域且个体域 E=1，2；当个体域是有限集时，如当个体域是有限集时，如D=a1,a2,an(x)A(x)A(a1)A(a2)A(an)则：则：(x)A(x
27、)A(a1)A(a2)A(an)从而谓词公式的真值等价于命题公式的真值。从而谓词公式的真值等价于命题公式的真值。解题思想解题思想解：解：(x)(P(x)Q(x)(P(1)Q(1)(P(2)Q(2)(10 0)(01 1)0 一个一阶逻辑合式公式中往往含有个体变项、一个一阶逻辑合式公式中往往含有个体变项、谓词变项等，一组使合式公式成为具有确定真值谓词变项等，一组使合式公式成为具有确定真值的常项（的常项（个体个体常项、常项、谓词谓词常项等）就构成了一个常项等）就构成了一个公式的公式的解释解释。三、谓词公式的解释例例6 6：给定解释给定解释I如下：如下：DI=2，3；DI中中特定的元素特定的元素a=
28、2;函数函数f(x)为为f(2)=3，f(3)=2；谓词谓词F(x)为为F(2)=0，F(3)=1;G(x,y)为为G(i，j)=1，i,j=2,3;L(x,y)为为L(2,2)=L(3,3)=1;L(2,3)=L(3,2)=0.确定下列谓词公式的真值。确定下列谓词公式的真值。（1）x(F(x)G(x,a)(F(2)G(2,2)(F(3)G(3,2)(0 1)(1 1)0（2）x(F(f(x)G(x,f(x)(F(f(2)G(2,f(2)(F(f(3)G(3,f(3)(F(3)G(2,3)(F(2)G(3,2)(11)(01)1（3）xy L(x,y)x(L(x,2)L(x,3)(L(2,2)
29、L(2,3)(L(3,2)L(3,3)(10)(01)1永真式永真式(逻辑有效式）逻辑有效式）：任一组解释皆使公式真值为任一组解释皆使公式真值为1 1永假式：永假式：(?)(?)可满足式：可满足式：(?)(?)没有一个可行的算法来判断一阶逻辑公式的类型，没有一个可行的算法来判断一阶逻辑公式的类型，只能对某些只能对某些特殊的特殊的公式进行判断公式进行判断。x(Fx(F (x x)F F(x x)；四、谓词公式的类型2.3 2.3 一阶逻辑等值式及前束范式一阶逻辑等值式及前束范式一、谓词演算中常见等值式：一、谓词演算中常见等值式：(I)(I)命题公式的推广命题公式的推广 2424个常用的命题演算等
30、值式及其代换可推广个常用的命题演算等值式及其代换可推广到谓词演算中使用到谓词演算中使用,如如2.(x)P(x)(y)R(x,y)(x)P(x)(y)R(x,y)3.(x)H(x,y)(x)H(x,y)F 1.(x)(P(x)Q(x)(x)(P(x)Q(x)()量词否定等值式量词否定等值式 (量词转换律量词转换律)(x)P(x)(x)P(x)(x)P(x)(x)P(x)实例：实例：“不是所有人今天都来上课不是所有人今天都来上课”“存在一些人今天没来上课存在一些人今天没来上课”“没有一个人今天来上课没有一个人今天来上课”“所有的人今天都没来上课所有的人今天都没来上课”。一、谓词演算中常见等值式：一
31、、谓词演算中常见等值式：()量词作用域的扩张与收缩等值式量词作用域的扩张与收缩等值式 xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)*xA(x)B x(A(x)B)B xA(x)x(BA(x)xA(x)Bx(A(x)B)xA(x)Bx(A(x)B)*xA(x)B x(A(x)B)B xA(x)x(BA(x)注意记住注意记住(*)*)，且各等价式中的，且各等价式中的B B可含其他非指导变元。可含其他非指导变元。()量词分配等价式量词分配等价式(x)(A(x)B(x)(x)A(x)(x)B(x)(对对 的分配的分配)(x)(A(x)B(x)(x)A(x)(x)B(x)(对对 的分配的分配
32、)注意：注意：对对 ，对对 不存在分配等价式。不存在分配等价式。(x)(A(x)B(x)(x)A(x)(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x)一、谓词演算中常见等值式：一、谓词演算中常见等值式：()多个量词的使用多个量词的使用(x)(y)A(x,y)(y)(x)A(x,y)(x)(y)A(x,y)(y)(x)A(x,y)注意：注意：其他情况下量词换序后一般不等价。其他情况下量词换序后一般不等价。一、谓词演算中常见等值式：一、谓词演算中常见等值式：前束范式前束范式：一个合式谓词公式，它的所有量词均：一个合式谓词公式，它的所有量词均 非否定非否定地出现在公式的最前面，且它
33、们的地出现在公式的最前面，且它们的作用域一直延伸到公式的末尾。作用域一直延伸到公式的末尾。如：如：(x)(y)(z)(P(x)F(y,z)Q(y,z)二、二、常见等值式的应用常见等值式的应用(前束范式前束范式)借助于常见等价式，我们仿照命题公式可以化成标借助于常见等价式，我们仿照命题公式可以化成标准形式，也想把谓词公式化成标准形式。准形式，也想把谓词公式化成标准形式。谓词逻辑中，谓词逻辑中，谓词逻辑中，谓词逻辑中，任何谓词公式的前束范式都存在，但一般不唯一。任何谓词公式的前束范式都存在，但一般不唯一。任何谓词公式的前束范式都存在，但一般不唯一。任何谓词公式的前束范式都存在，但一般不唯一。例例7
34、.将合式公式将合式公式(x)P(x)(y)R(y)(x)F(x)化为化为前束范式：前束范式：任一合式公式表示成前束范式可按如下步骤进行：任一合式公式表示成前束范式可按如下步骤进行：(1)消去公式中出现的多余量词；消去公式中出现的多余量词；解题思想解题思想二、二、常见等值式的应用常见等值式的应用(前束范式前束范式)(2)利利用用双双重重否否定定定定律律、德德 摩摩根根律律及及量量词词转转换换律律将将公公式式中中的的否否定定字字符符深深入入到到谓谓词词字字母母前前(否否定定符紧贴符紧贴)；(3)利利用用换换名名和和代代换换规规则则使使所所有有约约束束变变元元均均不不相相同同,并且使自由变元也与约束
35、变元不同并且使自由变元也与约束变元不同(更名更名)；(4)利利用用量量词词作作用用域域的的扩扩张张和和收收缩缩律律，扩扩大大量量词词的的作用域至整个公式作用域至整个公式(扩域扩域)。二、二、常见等值式的应用常见等值式的应用(前束范式前束范式)解解解解:(xP(x)yR(y)xF(x)(xP(x)yR(y)zF(z)(1)更换变元符号更换变元符号 x y z(P(x)R(y)F(z)(2)扩大作用域扩大作用域二、常见等值式的应用二、常见等值式的应用(前束范式前束范式)例例例例8.8.求下列合式公式的前束范式求下列合式公式的前束范式(1)(x)P(x)(x)Q(x)解：解：解：解：(x)P(x)(
36、x)Q(x)(x)P(x)(x)Q(x)(x)(P(x)Q(x)二、常见等值式的应用二、常见等值式的应用(前束范式前束范式)例例例例8.8.求下列合式公式的前束范式求下列合式公式的前束范式(2)(x)P(x)(x)Q(x)解：解：解：解：(x)P(x)(x)Q(x)(x)P(x)(x)Q(x)(x)P(x)(y)Q(y)(x)(y)(P(x)Q(y)二、常见等值式的应用二、常见等值式的应用(前束范式前束范式)(3)(x)P(x)(x)Q(x)(x)P(x)(y)Q(y)(x)(y)(P(x)Q(y)二、常见等值式的应用二、常见等值式的应用(前束范式前束范式)(4)(x)P(x)(x)Q(x)(
37、x)P(x)(y)Q(y)(x)(y)(P(x)Q(y)例例例例8.8.求下列合式公式的前束范式求下列合式公式的前束范式例例例例8.8.求下列合式公式的前束范式求下列合式公式的前束范式(5)(xF(x，y)yG(y)xH(x，y)二、二、常见等值式的应用常见等值式的应用(前束范式前束范式)(xF(x，z)yG(y)xH(x，z)(xF(x，z)yG(y)uH(u，z)x y(F(x，z)G(y)uH(u，z)x y u(F(x，z)G(y)H(u，z)前束合取范式：前束合取范式：前束范式前束范式(x)P(x)的命题公式部分即的命题公式部分即P(x)为合为合取范式。取范式。前束析取范式：前束析取范式：前束范式前束范式(x)P(x)的命题公式部分即的命题公式部分即P(x)为析为析取范式。取范式。二、常见等值式的应用二、常见等值式的应用