第二章谓词逻辑详解课件

离散数学 第一章第二章第二章谓词逻辑谓词逻辑2 2-1-1谓词的概念与表示谓词的概念与表示2-22-2命题函数与量词命题函数与量词2 2-3-3谓词公式与翻译谓词公式与翻译2 2-4-4变元的约束变元的约束2 2-5-5谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式2 2-6-6前束范式前束范式2-72-7谓词演算的推理理论谓词演算的推理理论离散数学 第一章q在命题逻辑中，主要研究命题和命题演算在命题逻辑中，主要研究命题和命题演算。命题命题的基本组成单位是原子命题，并把它看作是不可的基本组成单位是原子命题，并把它看作是不可再分解的。再分解的。q两个或多个原子命题之间，常常有一些共同特征，两个或多个原子命题之间，常常有一些共同特征，为了刻划命题内部的逻辑结构，就需要研究谓词为了刻划命题内部的逻辑结构，就需要研究谓词逻辑。逻辑。q另外，命题逻辑的推理证明中有着很大的局限性，另外，命题逻辑的推理证明中有着很大的局限性，有些简单的论断不能用命题逻辑进行推理证明。有些简单的论断不能用命题逻辑进行推理证明。离散数学 第一章 例如，一个简单而著名的例如，一个简单而著名的苏格拉底三段论苏格拉底三段论：所有的人都是要死的，苏格拉底是人，所以所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。苏格拉底是要死的。这个显然成立的推理在使用第一章的知识这个显然成立的推理在使用第一章的知识是不能进行证是不能进行证明明的的。假设假设,P P：所有的人都是要死的所有的人都是要死的 Q Q：苏格拉底是人苏格拉底是人 R R：苏格拉底是要死的苏格拉底是要死的 所以所以,该推理可以表示为该推理可以表示为PQPQ R R 但是，用第一章命题逻辑的方法并不能证明该但是，用第一章命题逻辑的方法并不能证明该推理成立，因为推理成立，因为PQRPQR不是重言式。不是重言式。比如比如,当当P P、Q Q为为T T，R R为为F F时，时，PQRPQR的真值为的真值为F F。离散数学 第一章q 苏格拉底三段论在命题逻辑中不能推证的原苏格拉底三段论在命题逻辑中不能推证的原因是因是命题公式描述能力的局限性命题公式描述能力的局限性。比如：比如：“所有的人都是要死的所有的人都是要死的”和和“苏格拉苏格拉底是要死的底是要死的”这两个命题所表述的性质都为：这两个命题所表述的性质都为：“是要死的是要死的”。但在命题逻辑中需用两个不同的命题符号但在命题逻辑中需用两个不同的命题符号P P和和R R来表示，两个不同的符号显然掩盖了两个命题描来表示，两个不同的符号显然掩盖了两个命题描述性质的共同性。述性质的共同性。因此因此,必须要对命题的内部关系进行深入地研必须要对命题的内部关系进行深入地研究才能解决某些问题的推理。究才能解决某些问题的推理。离散数学 第一章命题是反映判断的句子，不反映判断的句子命题是反映判断的句子，不反映判断的句子不是命题。不是命题。一般来说，反映判断的句子是由主语和谓语一般来说，反映判断的句子是由主语和谓语两部分组成。两部分组成。例如，电子计算机是科学技术的工具。例如，电子计算机是科学技术的工具。其中其中“电子计算机电子计算机”是是主语主语，“是科学技术的工是科学技术的工具具”是是谓语谓语。主语主语一般是客体，客体可以独立存在，它可一般是客体，客体可以独立存在，它可以是具体的，也可以是抽象的。以是具体的，也可以是抽象的。例如：例如：小王、老师、小王、老师、3、*代表团、唯物主义代表团、唯物主义等。等。2-1谓词的概念与表示谓词的概念与表示离散数学 第一章用以刻划客体的性质或关系的是用以刻划客体的性质或关系的是谓词。谓词。例如：例如：张三是个大学生张三是个大学生李四是个大学生李四是个大学生这两个命题可以用不同的符号这两个命题可以用不同的符号p、q表示。表示。但是，但是，p和和q的谓语有同样的属性：的谓语有同样的属性：“是个是个大学生大学生”。引入一个符号表示引入一个符号表示“是个大学生是个大学生”，再引，再引入一种方法表示客体的名称。入一种方法表示客体的名称。这样就能把这样就能把“*是个大学生是个大学生”这个命题的这个命题的本质属性刻划出来。本质属性刻划出来。离散数学 第一章又如：又如：(a)他是三好学生。他是三好学生。(b)7是质数。是质数。(c)每天早晨做广播操是好习惯。每天早晨做广播操是好习惯。(d)5大于大于3。(e)哥白尼指出地球绕着太阳转。哥白尼指出地球绕着太阳转。在上述语句中在上述语句中“是三好学生是三好学生”、“是质数是质数”、“是好习惯是好习惯”、“大于大于”、“指出指出”都是谓都是谓词。词。前三个是前三个是指明客体性质的谓词指明客体性质的谓词后两个是后两个是指明两个客体之间关系的谓词指明两个客体之间关系的谓词离散数学 第一章 一般一般,用大写字母表示谓词用大写字母表示谓词，用小写字母表示客用小写字母表示客体名称体名称。例如例如,A,A表示表示“是个大学生是个大学生”，c c表示表示“张三张三”，e e表示表示“李四李四”，则，则 A(A(c c）表示表示“张三张三”是个大学生是个大学生 A(e A(e）表示表示“李四李四”是个大学生是个大学生 用谓词表达命题，必须包括客体和谓词字母两个用谓词表达命题，必须包括客体和谓词字母两个部分部分。一般地说，一般地说，“b b是是A A”类型的命题可用类型的命题可用A(A(b)b)表达。表达。离散数学 第一章 对于对于“a a是小于是小于b b”这种两个客体之间关系的这种两个客体之间关系的命题，可表达为命题，可表达为B(B(a,b)a,b)，这里这里B B表示表示“是小于是小于”。又如又如,命题命题“点点a a在在b b与与c c之中之中”,可以用可以用L L表示表示：在在和和之中之中 故可记为故可记为 L(L(a a，b b，c)c)。通常把通常把A(A(b)b)称作称作一元谓词一元谓词，B(B(a a，b)b)称作称作二元二元谓词谓词，L(L(a a，b b，c c)称作称作三元谓词三元谓词，依次类推。，依次类推。离散数学 第一章q注意注意:代表客体名称的字母，它在多元谓词表代表客体名称的字母，它在多元谓词表示式中出现的次序与事先约定有关示式中出现的次序与事先约定有关。因此因此,未经约定前，上例记作未经约定前，上例记作 L(L(a，b，c)或或L(L(b，c，a）等都可以，但一经约定等都可以，但一经约定 L(L(a，b，c)与与L(L(b，c，a）就代表两个不同的命题。就代表两个不同的命题。单独一个谓词不是完整的命题，把谓词单独一个谓词不是完整的命题，把谓词字母后填以客体所得的式子称为字母后填以客体所得的式子称为谓词填式谓词填式。谓词和谓词填式是两个不同的概念。谓词和谓词填式是两个不同的概念。离散数学 第一章一般来说，一般来说，n元谓词需要元谓词需要n个客体名称插入个客体名称插入到固定的位置上。到固定的位置上。如果如果A为为n元谓词，元谓词，a1，a2，an是客是客体的名称，则体的名称，则A(a1，a2，an)就可成为一个命题。就可成为一个命题。通常，一元谓词表达了客体的通常，一元谓词表达了客体的“性质性质”，而多元谓词表达了客体之间的，而多元谓词表达了客体之间的“关系关系”。离散数学 第一章1.命题函数命题函数客体有客体常元和客体变元之分，当一个客体表示确客体有客体常元和客体变元之分，当一个客体表示确定的客体时，称为定的客体时，称为客体常元客体常元；当一个客体表示不确定的客体时，称为当一个客体表示不确定的客体时，称为客体变元客体变元。下面先举例解释命题与谓词的关系。下面先举例解释命题与谓词的关系。设设H是是谓词表示谓词表示“能够到达山顶能够到达山顶”，l表示客体名称李表示客体名称李四，四，t表示老虎，表示老虎，c表示汽车，那么表示汽车，那么H(l)，H(t)，H(c)等分别表示各个不同的命题，但它们有一个共同的形式等分别表示各个不同的命题，但它们有一个共同的形式:H(x)当当x分别取分别取l、t、c时就表示时就表示“李四能够到达山顶李四能够到达山顶”，“老虎能够到达山顶老虎能够到达山顶”，“汽车能够到达山顶汽车能够到达山顶”。2-2命题函数与量词命题函数与量词x为客体变元客体变元离散数学 第一章同理，若同理，若L(x,y)表示表示x小于小于y，那么那么L(2,3)表示一个命题：表示一个命题：“2小于小于3”,为真。为真。而而L(5,1)表示一个命题：表示一个命题：“5小于小于1”,为假。为假。又如又如,A(x,y,z)表示一个关系表示一个关系“x加上加上y等于等于z”则则A(3,2,5)表示了真命题表示了真命题“3+2=5”，而，而A(1,2,4)表示了一个假命题表示了一个假命题“1+2=4”。从上述三个例子中可以看到从上述三个例子中可以看到H(x)，L(x,y)，A(x,y,z)中的中的x，y，z等都是等都是客体变元客体变元。它们很象数学中的函数，这种函数就是它们很象数学中的函数，这种函数就是命题函数命题函数。离散数学 第一章 定义定义2-2.12-2.1 由一个谓词，一些客体变元组成的表由一个谓词，一些客体变元组成的表达式称为达式称为简单命题函数简单命题函数。由一个或由一个或n n个简单命题函数以及逻辑联结词组合个简单命题函数以及逻辑联结词组合而成的表达式称为而成的表达式称为复合命题函数复合命题函数。根据这个定义可以看到：根据这个定义可以看到：n n元谓词就是有元谓词就是有n n个个客体变元的命题函数客体变元的命题函数。当当n=0n=0时，称为时，称为0 0元谓词元谓词。它本身就是一个命题它本身就是一个命题。例如例如:命题常量或命题变元命题常量或命题变元。命题是命题是n n元谓词的一个特殊情况元谓词的一个特殊情况。逻辑联结词逻辑联结词:，、,意义与命意义与命题演算中的解释完全相同。题演算中的解释完全相同。离散数学 第一章 例例1 1 设设S(x)S(x)表示表示“x x学习很好学习很好”(简单命题函数简单命题函数)，用，用W(x)W(x)表示表示“x x工作很好工作很好”(简单命题函数简单命题函数),),则则 S(x)S(x)表示表示:“x:“x学习不是很好学习不是很好”。(复合命题函数复合命题函数)S(x)W(x)S(x)W(x)表示表示:“x “x的工作，学习都很好的工作，学习都很好”。(复合命题函数复合命题函数)S(x)W(x)S(x)W(x)表示表示:“若若x x的学习很好，则的学习很好，则x x的工作得很好。的工作得很好。”(复合命题函数复合命题函数)离散数学 第一章 例例2 2 用用H(x,y)H(x,y)表示表示“x x比比y y长得高长得高”。设。设l 表示李表示李四，四，c c表示张三表示张三,则则 H(H(l,c),c)表示表示:“李四不比张三长得高李四不比张三长得高”。H(H(l,c),c)H(c,H(c,l)表示表示:“李四不比张三长得高李四不比张三长得高”且且“张三不比李四长得高张三不比李四长得高”即即“张三与李四同样高张三与李四同样高”。离散数学 第一章2.个体域个体域 命题函数不一定是一个命题，只命题函数不一定是一个命题，只有客体变元有客体变元取特定的值取特定的值(名称名称)时，才能成为一个命题。时，才能成为一个命题。客体变元在哪些范围内取哪些值，这对客体变元在哪些范围内取哪些值，这对命题命题函数函数是否成为命题及该命题的真值有很大的影响。是否成为命题及该命题的真值有很大的影响。离散数学 第一章 例例3 设设Q(x,y)表示表示“x比比y重重”。当当x,y指人或物时，它是一个命题，但指人或物时，它是一个命题，但若若x,y指实数时，指实数时，Q(x,y)就不是一个命题。就不是一个命题。离散数学 第一章例例4R(x)表示表示“x是大学生是大学生”。如果如果x的讨论范围为某大学里班级中的学的讨论范围为某大学里班级中的学生，则生，则R(x)是是永真式永真式。如果如果x的讨论范围为某中学里班级中的学的讨论范围为某中学里班级中的学生，则生，则R(x)是是永假式永假式。如果如果x的讨论范围为一个剧场中的观众，的讨论范围为一个剧场中的观众，观众中有大学生也有非大学生，那么，对某些观众中有大学生也有非大学生，那么，对某些观众，观众，R(x)为真，对另一些观众，为真，对另一些观众，R(x)为假。为假。真值不能确定真值不能确定!离散数学 第一章例例5(P(x,y)P(y,z)P(x,z)若若P(x,y)解释为解释为“x小于小于y”，当当x,y,z都在实数域中取值，则都在实数域中取值，则这个式子表示为：这个式子表示为：若若x小于小于y且且y小于小于z,则则x小于小于z。这是一个这是一个永真式永真式。如果如果P(x,y)解释为解释为“x为为y的儿子的儿子”。当。当x,y,z都指人，则都指人，则“若若x为为y的儿子且的儿子且y是是z的儿子则的儿子则x是是z的儿子的儿子”。这个式子是一个这个式子是一个永假式永假式。如果如果P(x,y)解释为解释为“x距离距离y10米米”，若，若x,y,z表示地面上的表示地面上的房子，那么房子，那么“x距离距离y10米且米且y距离距离z10米米,则则x距离距离z10米米”。这个命题的真值将由这个命题的真值将由x,y,z的具体位置而定的具体位置而定,它可能为它可能为T，也可能为也可能为F。真值不能确定真值不能确定!离散数学 第一章从上面的例子可以看到从上面的例子可以看到:命题函数确定为命题，与客体变元的命题函数确定为命题，与客体变元的论述范围论述范围有关。有关。在命题函数中，客体变元的论述范围称作在命题函数中，客体变元的论述范围称作个体域个体域。个体域可以是有限的，也可以是无限的，把各种个体域个体域可以是有限的，也可以是无限的，把各种个体域综合在一起作为论述范围的域称综合在一起作为论述范围的域称全总个体域全总个体域。个体域个体域（或论域）（或论域）客体变元的取值范围客体变元的取值范围。例如：例如：P(x)：x是大学生。是大学生。个体域个体域 u=人类人类 全总个体域全总个体域 各种个体域的综合各种个体域的综合。(由由宇宙间一切事物组成宇宙间一切事物组成)如果在讨论中没有指明论域，则是以全总个体域如果在讨论中没有指明论域，则是以全总个体域 为论为论域。域。离散数学 第一章3.量词量词使用上面所讲的一些概念，还不能用符号很好地表达日常使用上面所讲的一些概念，还不能用符号很好地表达日常生活中的各种命题。生活中的各种命题。例如：例如：S(x)表示表示x是大学生，是大学生，x的个体域为某单位的职工。的个体域为某单位的职工。S(x)可以表示某单位职工可以表示某单位职工都是都是大学生，也可以表示某大学生，也可以表示某单位单位存在一些存在一些职工是大学生。职工是大学生。为了避免这种理解上的混乱，需要引入量词，以刻划为了避免这种理解上的混乱，需要引入量词，以刻划“所所有的有的”和和“存在一些存在一些的不同概念。的不同概念。例如例如:(1)所有的人都是要呼吸的。所有的人都是要呼吸的。(2)每个学生都要参加考试。每个学生都要参加考试。(3)任何整数或是正的或是负的。任何整数或是正的或是负的。这三个例子都需要表示这三个例子都需要表示“对所有的对所有的x”的概念，为此，引入符的概念，为此，引入符号：号：(x)或或(x)表示表示“对所有的对所有的x”。离散数学 第一章例如：例如：若设若设M(M(x)x)：x x是人是人 H(H(x x）：）：x x要呼吸。要呼吸。P(x P(x）：）：x x是学生是学生 Q(Q(x x）：）：x x要参加考试。要参加考试。I(x I(x）：）：x x是整数是整数 R(x R(x）：）：x x是正数是正数 N(N(x x）：）：x x是负数，是负数，则则 所有的人都要呼吸：所有的人都要呼吸：(x)(M(xx)(M(x）H(x)H(x)每一个学生都要考试：每一个学生都要考试：(x)(P(xx)(P(x）Q(x)Q(x)任何一个整数不是正数就是负数：任何一个整数不是正数就是负数：(x)(I(x)R(x)N(x)x)(I(x)R(x)N(x)符号符号“”称为称为全称量词全称量词，用来表示，用来表示“对所有的对所有的”,“每一个每一个”,“对任何一个对任何一个”等。等。离散数学 第一章 还有一个量词记作还有一个量词记作(x)x)，表示表示“存在一些存在一些 x x”。例如例如:（1 1）存在一个数是质数。存在一个数是质数。（2 2）一些人是聪明的。一些人是聪明的。（3 3）有些人早饭吃面包。有些人早饭吃面包。设设 P(P(x x）：）：x x是质数。是质数。M(x M(x）：）：x x是人。是人。R(x R(x）：）：x x是聪明的。是聪明的。E(x E(x）：）：x x早饭吃面包。早饭吃面包。则上面三个命题可表示为：则上面三个命题可表示为：（1 1）(x x）P(xP(x）（2 2）(x x）M(x)R(x)M(x)R(x)（3 3）(x x）M(x)E(x)M(x)E(x)符符号号“”称称为为存存在在量量词词，可可用用来来表表达达“存存在在一一些些”“至少有一个至少有一个”“对于一些对于一些”等。等。离散数学 第一章q全称量词与存在量词统称为全称量词与存在量词统称为量词量词，在上述有关，在上述有关量词的例子中可以看出，每个由量词确定的表达式，量词的例子中可以看出，每个由量词确定的表达式，都与个体域有关。都与个体域有关。例如：例如：(x)(M(x)(M(x）H(x)表示所有的人都要表示所有的人都要呼吸呼吸。如果把个体域限制在如果把个体域限制在“人类人类”这个范围内，那这个范围内，那么亦可简单地表示为么亦可简单地表示为(x)(x)(H(x)注意注意:在这个例子中指定论域，不仅与表达形式在这个例子中指定论域，不仅与表达形式有关，而且有关，而且不同的指定论域会有不同的问题真值不同的指定论域会有不同的问题真值。假如设论域为假如设论域为“人类人类”则这个命题的真值为则这个命题的真值为T，如果论域为自然数，则命题的真值为如果论域为自然数，则命题的真值为F。离散数学 第一章q在讨论带有量词的命题函数时，必须确定其个体域。在讨论带有量词的命题函数时，必须确定其个体域。可以将所有命题函数的个体域全部统一，使用全总个体域。可以将所有命题函数的个体域全部统一，使用全总个体域。用了这个全总个体域后，对每一个客体变元的变化范用了这个全总个体域后，对每一个客体变元的变化范围，用围，用特性谓词特性谓词加以限制。加以限制。一般地，对全称量词，此特性谓词常作蕴含的前件。一般地，对全称量词，此特性谓词常作蕴含的前件。对存在量词，此特性谓词常作合取项。对存在量词，此特性谓词常作合取项。例如：例如：在全总个体域中在全总个体域中 (x)(H(x)(H(x x)可写成可写成 (x)(M(x)(M(x x）H(H(x)x)其中其中M(M(x)x)为为H(H(x)x)的特性谓词。的特性谓词。(x)x)(H(x)(H(x)可写成可写成 (x)(M(x)(M(x x）H(x)H(x)特性谓词特性谓词M(M(x)x)限定了限定了H(H(x)x)中变元的范围。中变元的范围。离散数学 第一章1.谓词公式谓词公式简单命题函数与逻辑联结词可以组合成一些谓词简单命题函数与逻辑联结词可以组合成一些谓词表达式。表达式。有了谓词与量词的概念，谓词表达式所能刻划的有了谓词与量词的概念，谓词表达式所能刻划的日常命题就能广泛而且深入得多。日常命题就能广泛而且深入得多。但是，怎样的谓词表达式才能成为谓词公式但是，怎样的谓词表达式才能成为谓词公式,并能并能进行谓词演算呢进行谓词演算呢?通常把通常把A(x1，x2，xn)称作称作谓词演算的原子公谓词演算的原子公式式，其中，其中x1，x2，xn是客体变元是客体变元。例如：例如：Q,A(x)，A(x,y)，A(f(x)，y)，A(x,y,z)，A(a,y)等。等。这些都是这些都是原子谓词公式的各种特例原子谓词公式的各种特例。2-3谓词公式与翻译谓词公式与翻译离散数学 第一章定义定义2-3.1谓词演算的谓词演算的合式公式合式公式，可由下述各条规，可由下述各条规定组成：定组成：(1)原子谓词公式是合式公式。原子谓词公式是合式公式。(2)若若A是合式公式，则是合式公式，则A是一个合式公式。是一个合式公式。(3)若若A和和B都是合式公式，则都是合式公式，则(AB)，(AB),（AB）和（和（AB）是合式公式。是合式公式。(4)如果如果A是合式公式，是合式公式，x是是A中出现的任何变元，中出现的任何变元，则则(x)A和和(x)A都是合式公式。都是合式公式。(5)只有经过有限次地应用规则只有经过有限次地应用规则(1)，(2)，(3)，(4)所得到的公式是合式公式。所得到的公式是合式公式。离散数学 第一章在讨论命题公式时，在讨论命题公式时，最外层的括号可以省略最外层的括号可以省略，在谓词合式公式中亦将遵守同样的约定在谓词合式公式中亦将遵守同样的约定。注意：注意：量词后面若有括号则不能省略量词后面若有括号则不能省略。谓词合式公式，通常简称为谓词合式公式，通常简称为谓词公式谓词公式。离散数学 第一章2.翻译翻译把自然语言中的一些命题用谓词公式表达称为把自然语言中的一些命题用谓词公式表达称为翻译翻译。例题例题1并非每个实数都是有理数。并非每个实数都是有理数。解解:R(x):x是实数是实数Q(x):x是有理数是有理数(x)(R(x)Q(x)例题例题2没有不犯错误的人。没有不犯错误的人。解解:F(x):x犯错误犯错误M(x):x是人是人(x)(M(x)F(x)离散数学 第一章例题例题3尽管有人聪明，但未必一切人都聪明。尽管有人聪明，但未必一切人都聪明。解解:P(x):x聪明聪明M(x):x是人是人(x)(M(x)P(x)(x(M(x)P(x)离散数学 第一章例题例题4这只大红书柜摆满了那些古书。这只大红书柜摆满了那些古书。解法解法1设设F(x,y)：x摆满了摆满了yR(x)：x是大红书柜是大红书柜Q(y)：y是古书是古书a：这只：这只b：那些：那些R(a)Q(b)F(a,b)离散数学 第一章解法解法2设设A(x)：x是书柜是书柜B(x)：x是大的是大的C(x)：x是红的是红的D(y)：y是古老的是古老的E(y)：y是图书是图书F(x,y)：x摆满了摆满了ya：这只这只b：那些那些A(a)B(a)C(a)D(b)E(b)F(a,b)离散数学 第一章由本例可知，对于命题翻译成谓词演算公式，由本例可知，对于命题翻译成谓词演算公式，不不唯一唯一。这是因为这是因为对个体描述性质的刻划深度不同，对个体描述性质的刻划深度不同，一个一个命题可翻译成不同形式的谓词公式命题可翻译成不同形式的谓词公式。本例中本例中:R(x)表示表示x是大红书柜是大红书柜而而A(x)B(x)C(x)也可表示大红书柜也可表示大红书柜。但是后一种更方便于对书柜的大小颜色进行讨但是后一种更方便于对书柜的大小颜色进行讨论，这样对个体刻划深度的不同就可翻译成不同的谓论，这样对个体刻划深度的不同就可翻译成不同的谓词公式。词公式。离散数学 第一章例题例题5在数学分析中的极限定义为：任给一个小正在数学分析中的极限定义为：任给一个小正数数，则存在一个正数则存在一个正数，使得当使得当0|x-a|时时,有有|f(x)-b|。此时此时,称称limf(x)=b(用谓词演算公式表达极限定义用谓词演算公式表达极限定义)xa解解:P(x,y)表示表示“x大于大于y”，Q Q(x,y)表示表示“x小于小于y”，故，故lim(x)=b可表示为可表示为xa ()()(x)(P(,0)P(,0)Q(|x-a|,)P(|x-a|,0)Q(|f(x)-b|,)离散数学 第一章1.作用域作用域(辖域辖域)q给定给定为一个谓词公式，其中有一部分公式的形式为一个谓词公式，其中有一部分公式的形式:(x)P(x)或或(x)(P(x)其中其中、后面的后面的x称做称做量词的指导变元或作用变元量词的指导变元或作用变元，P(x)叫做叫做相应量词的作用域或辖域相应量词的作用域或辖域。2.约束变元和自由变元约束变元和自由变元q在作用域中在作用域中x的一切出现，称为的一切出现，称为x在在中约束出现中约束出现，x亦称为亦称为被相应量词中的指导变元所约束。被相应量词中的指导变元所约束。q在在中除去约束变元以外所出现的变元称作中除去约束变元以外所出现的变元称作自由变元自由变元。q自由变元是不受约束的变元，虽然它有时也在量词的作用自由变元是不受约束的变元，虽然它有时也在量词的作用域中出现，但它不受相应量词中指导变元的约束，故可以域中出现，但它不受相应量词中指导变元的约束，故可以把自由变元看作是公式中的把自由变元看作是公式中的参数参数。2-4变元的约束变元的约束离散数学 第一章 例题例题1 1 说明以下各式的作用域与变元约束的情况。说明以下各式的作用域与变元约束的情况。a)(a)(x)(P(x)Q(x)x)(P(x)Q(x)解：解：(x）的作用域的作用域:P(x)Q(x)x为约束变元为约束变元 b)(b)(x)(P(x)(x)(P(x)(y)R(x,y)y)R(x,y)解：解：(x)的作用域的作用域:P(x)(y)R(x，y)(y)的作用域的作用域:R(x,y)x,y都是约束变元。都是约束变元。c)(c)(x)(x)(y)(P(x,y)Q(y,z)(y)(P(x,y)Q(y,z)(x)P(x,y)x)P(x,y)解：解：(x)和和(y)的作用域是的作用域是:(P(x,y)Q(y,z)，其中其中x,y是约束变元，是约束变元，z是自由变元。是自由变元。(x)的作用域的作用域:P(x,y)，其中其中x是约束变元，是约束变元，y是自由是自由变元。变元。在整个公式中，在整个公式中，x是约束出现，是约束出现，y既是约束出现又是自既是约束出现又是自由出现，由出现，z是自由出现。是自由出现。离散数学 第一章 d)(d)(x)(P(x)(x)(P(x)(x)Q(x,z)(x)Q(x,z)(y)R(x,y)Q(x,y)y)R(x,y)Q(x,y)解：解：(x)的作用域的作用域:P(x)(x)Q(x,z)(y)R(x,y)x和和y都是约束变元，但都是约束变元，但Q(x,z)中的中的x是受是受 x的约束，而不的约束，而不是受是受 x的约束的约束,z是自由变元。是自由变元。Q(x,y)中的中的x,y是自由变元。是自由变元。离散数学 第一章从约束变元的概念可以看出：从约束变元的概念可以看出：P(x1，x2，xn)是是n元谓词，它有元谓词，它有n个相互独立的自由变元个相互独立的自由变元。若对其中若对其中k个变元进行约束则成为个变元进行约束则成为n-k元谓词，因此，元谓词，因此，谓词公式中如果没有自由变元出现，则该式就成为一个谓词公式中如果没有自由变元出现，则该式就成为一个命题命题。例如：例如：(x)P(x，y，z)是二元谓词。是二元谓词。(y)(x)P(x，y，z)是一元谓词。是一元谓词。离散数学 第一章3.约束变元的换名约束变元的换名为了避免由于变元的约束与自由同时出现，引起概念上为了避免由于变元的约束与自由同时出现，引起概念上的混乱，故可对约束变元进行换名。的混乱，故可对约束变元进行换名。使得一个变元在一个公式中只呈一种形式出现，或呈自使得一个变元在一个公式中只呈一种形式出现，或呈自由出现或呈约束出现。由出现或呈约束出现。一个公式的约束变元一个公式的约束变元所使用的名称符号是无关紧要的所使用的名称符号是无关紧要的。(x)P(x)与与(y)P(y)具有相同的意义。具有相同的意义。设设A(x)表示表示x不小于不小于0，那么，那么(x)A(x)表示一切表示一切x都使得都使得x不小于不小于0(y)A(y)表示一切表示一切y都使得都使得y不小于不小于0(t)A(t)表示一切表示一切t都使得都使得t不小于不小于0在实数域中都在实数域中都表示假命题表示假命题“一切实数均不小于一切实数均不小于0”。同理同理,(x)P(x)与与(y)P(y)意义亦相同。意义亦相同。离散数学 第一章因此，可以对谓词公式因此，可以对谓词公式中的约束变元更改名中的约束变元更改名称符号，这种遵守一定规则的更改，称为称符号，这种遵守一定规则的更改，称为约束变元的约束变元的换名换名。约束变元更改名称的约束变元更改名称的规则规则：(1)对于约束变元可以换名，其更改的变元名称对于约束变元可以换名，其更改的变元名称范围是量词中的指导变元，以及该量词作用域中范围是量词中的指导变元，以及该量词作用域中所出现的该变元，在公式的其余部分不变。所出现的该变元，在公式的其余部分不变。(2)换名时一定要更改为作用域中没有出现的变换名时一定要更改为作用域中没有出现的变元名称。元名称。离散数学 第一章解：解：例题例题2 2 对对(x)(P(x)(P(x x)R R(x,y)(x,y)Q(Q(x x,y),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)因为后因为后两种更改都将使公式中量词的两种更改都将使公式中量词的约束约束范围有所变动范围有所变动。离散数学 第一章4.自由变元的代入自由变元的代入对于公式中的自由变元，也允许更改，这种更改叫做对于公式中的自由变元，也允许更改，这种更改叫做代入代入。自由变元的代入，亦需要遵守一定的规则，这个规。自由变元的代入，亦需要遵守一定的规则，这个规则叫做则叫做自由变元的代入规则自由变元的代入规则。代入规则代入规则如下：如下：(1)对于谓词公式中的自由变元，可以作代入，代入时对于谓词公式中的自由变元，可以作代入，代入时需要对公式中出现该自由变元的每一处进行。需要对公式中出现该自由变元的每一处进行。(2)用以代入的变元与原公式中所有变元的名称不能相用以代入的变元与原公式中所有变元的名称不能相同。同。离散数学 第一章例题例题3 3 对对(x)x)(P(P(y)(y)R(x,y)R(x,y)代入代入解解：对对y实施代入，经代入后公式为实施代入，经代入后公式为 (x)x)(P(P(z)(z)R R(x,z)(x,z)但但是，是，(x)(p(x)RR(x,x)与与(x)(p(z)RR(x,y)这这两种代入都是与规则不符的两种代入都是与规则不符的。离散数学 第一章需要指出需要指出:量词作用域中的约束变元，当论量词作用域中的约束变元，当论域的元素是有限时，客体变元的所有可能的取代域的元素是有限时，客体变元的所有可能的取代是可枚举的。是可枚举的。设论域元素为设论域元素为 a a1 1,a,a2 2,a,an n,则有如则有如下等价式：下等价式：(x)A(x)x)A(x)A(a(a1 1)A(a)A(a2 2)A(a)A(an n)(x)A(x)x)A(x)A(a A(a1 1)A(a)A(a2 2)A(a)A(an n)量词对变元的约束，往往与量词的出现顺序量词对变元的约束，往往与量词的出现顺序有关。有关。离散数学 第一章命题中有多个量词时，命题中有多个量词时，约定从左到右的次序约定从左到右的次序读出读出。例如例如,(y)(y)(x)(x(y-2)x)(x(y-2)表示任何表示任何y y均有均有x x，使得使得xy-2xy-2 (y)(y)(x)(x(y-2)x)(x(y-2)表示存在表示存在y y有有x x，使得使得xy-2 xy-2 注意注意:量词次序不能颠倒，否则将与原题意量词次序不能颠倒，否则将与原题意义不符。义不符。离散数学 第一章2-5谓词演算的等价式和蕴涵式谓词演算的等价式和蕴涵式1.谓词公式的赋值谓词公式的赋值q谓词公式中包含有命题变元和客体变元，当命谓词公式中包含有命题变元和客体变元，当命题变元用确定的命题取代，客体变元用确定的题变元用确定的命题取代，客体变元用确定的客体所取代时，就称作客体所取代时，就称作对谓词公式对谓词公式赋值赋值。q一个谓词公式经过赋值后，就成为真值确定的一个谓词公式经过赋值后，就成为真值确定的命题命题（T或或F）。离散数学 第一章2.谓词公式的分类谓词公式的分类定义定义2-5.1给定任何两个谓词公式给定任何两个谓词公式A和和B，设设它们有共同的个体域它们有共同的个体域E。若对若对A和和B的任意一组变元进行赋值，所得命的任意一组变元进行赋值，所得命题的真值相同，则称题的真值相同，则称谓词公式谓词公式A和和B在在E上是等价上是等价的的。记为记为AB离散数学 第一章定义定义2-5.2任意给定谓词公式任意给定谓词公式A，其个体其个体域为域为E。若对若对A的任意变元赋值，的任意变元赋值，A都为真，则都为真，则称该称该A在在E上是上是有效的有效的（或（或永真的永真的）。）。离散数学 第一章定义定义2-5.3对于一个谓词公式对于一个谓词公式A，如果在所有赋如果在所有赋值下，该公式的真值都为假，则称该值下，该公式的真值都为假，则称该A为为不可满不可满足的足的。离散数学 第一章定义定义2-5.4对于一个谓词公式对于一个谓词公式A,如果至少在如果至少在一种赋值下为真一种赋值下为真,则称则称该该谓词公式谓词公式A为可满足的。为可满足的。离散数学 第一章有了有了谓词公式的等价和永真的概念以后就谓词公式的等价和永真的概念以后就可以讨论谓词演算的等价可以讨论谓词演算的等价公公式和式和蕴含公式蕴含公式。离散数学 第一章3.命题公式的推广命题公式的推广在命题演算中，任意一个永在命题演算中，任意一个永真的命题公式真的命题公式，若对同名的命题变元，用同一公式取代，若对同名的命题变元，用同一公式取代，得到的得到的命题公式也命题公式也是永真公式是永真公式。可以把这种情况推广到谓词公式之中，当谓可以把这种情况推广到谓词公式之中，当谓词演算中的公式代替命题演算中永真公式的变元词演算中的公式代替命题演算中永真公式的变元时，所得的谓词公式也是永真的时，所得的谓词公式也是永真的,即为有效公式即为有效公式。因此因此,命题演算中的等价公式表和蕴含公式表命题演算中的等价公式表和蕴含公式表都可以推广到谓词演算中使用。都可以推广到谓词演算中使用。离散数学 第一章例如：例如：(x)(P(x)Q(x)(x)(P(x)Q(x)E16P(x)Q(x)P(x)Q(x)(x)P(x)(y)(R(x,y)(x)P(x)(y)(R(x,y)E9(PQ)PQ(y)(x)(H(x,y)H(x,y)F (P P)F离散数学 第一章4.量词与联结词量词与联结词 之间的关系之间的关系例例1设设P(x)表示表示x今天来校上课，则今天来校上课，则 P(x)表示表示x今天没有来校上课。今天没有来校上课。不是所有人今天来上课与存在一些人今天不是所有人今天来上课与存在一些人今天没有来上课在意义上相同，没有来上课在意义上相同，即即(x)P(x)(x)P(x)另外，不是存在一些人今天来上课与所有的另外，不是存在一些人今天来上课与所有的人今天都没有来上课在意义上相同，即人今天都没有来上课在意义上相同，即(x)P(x)(x)P(x)离散数学 第一章可以推广到一般可以推广到一般情况情况得到公式：得到公式：(量词转化律量词转化律)(x)P(x)(x)P(x)(x)P(x)(x)P(x)注意注意:出现在量词之前的否定出现在量词之前的否定,不是否定该量词而是不是否定该量词而是否定该量化了的命题否定该量化了的命题。离散数学 第一章对于量词转化律对于量词转化律,可以在有限个体域上证明。可以在有限个体域上证明。证明证明:设有限个体域设有限个体域=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)量词转化律在无限个体域上也能推广量词转化律在无限个体域上也能推广。离散数学 第一章从量词转化律可以看到从量词转化律可以看到：当当把量词前面把量词前面的的 移到量词的后面去时移到量词的后面去时,全称量词改为存在全称量词改为存在量词量词。反之反之,把量词后面的把量词后面的 移到量词的前面去移到量词的前面去时时,存在量词改为全称量词存在量词改为全称量词。这种量词与这种量词与 的关系普遍成立。的关系普遍成立。离散数学 第一章5.量词辖域的扩张与收缩量词辖域的扩张与收缩在量词的作用域中，在量词的作用域中，常常有常常有合取或析取项，合取或析取项，如果其中有一个为如果其中有一个为命题命题，则可将，则可将该命题该命题移至量词移至量词作用域之外。作用域之外。例如例如:(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)(A(x)B)(x)A(x)B这是因为在这是因为在B中不出现约束变元中不出现约束变元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)(A(x)B)x)(A(x)B)B(B(x)A(x)x)A(x)(x)(BA(x)x)(BA(x)B(B(x)A(x)x)A(x)(x)(BA(x)x)(BA(x)注意：注意：上面几式中，上面几式中，B中不能出现约束变元中不能出现约束变元x。离散数学 第一章例例2证明证明:(x)(A(x)B)(x)(A(x)B)证明：证明：(x)(A(x)B)(x)(A(x)B)(E16)(x)A(x)B(前面公式前面公式)(x)A(x)B(量词转化律量词转化律)(x)（A(x)B）(E16)也可以反过来证也可以反过来证(x)(A(x)B)(x)(A(x)B)(x)A(x)B(x)A(x)B(x)（A(x)B）离散数学 第一章 当谓词的变元与量词的指导变元不同时，亦能有类似当谓词的变元与量词的指导变元不同时，亦能有类似于上述的公式。于上述的公式。例如例如:(x)(P(x)x)(P(x)Q(y)Q(y)(x)P(x)x)P(x)Q(y)Q(y)(x)(x)(y)P(x,y)y)P(x,y)Q(z)Q(z)(x)(x)(y)P(x,y)y)P(x,y)Q(z)Q(z)离散数学 第一章 6.6.量词与命题联结词之间的一些等价公式量词与命题联结词之间的一些等价公式 量词与命题联结词之间存在不同的结合情况，下面举例量词与命题联结词之间存在不同的结合情况，下面举例说明一些等价公式。说明一些等价公式。例如例如:联欢会上所有人既唱歌又跳舞和联欢会上所有人联欢会上所有人既唱歌又跳舞和联欢会上所有人唱歌且所有人跳舞。唱歌且所有人跳舞。因为这两个语句意义相同因为这两个语句意义相同,故有故有 (x)(A(x)x)(A(x)B(B(x)x)(x)A(x)x)A(x)(x)B(x)x)B(x)根据上式有：根据上式有：(x)(x)(A(A(x)x)B(B(x)x)(x)(x)(A(A(x)x)(x)x)B(B(x)x)故故 (x)(A(x)x)(A(x)B(B(x)x)(x)A(x)x)A(x)(x)B(x)x)B(x)即即 (x)(A(x)x)(A(x)B(B(x)x)(x)A(x)x)A(x)(x)B(x)x)B(x)可以推广到一般情况。可以推广到一般情况。离散数学 第一章7.量词分配的蕴含关系量词分配的蕴含关系 量词与命题联结词之间存在一些不同的结合情况，有些量词与命题联结词之间存在一些不同的结合情况，有些是蕴含公式。是蕴含公式。例如例如:这些学生都聪明或这些学生都努力，可以推出这些这些学生都聪明或这些学生都努力，可以推出这些学生都聪明或努力。学生都聪明或努力。但是，这些学生都聪明或努力却不能推出这些学生都但是，这些学生都聪明或努力却不能推出这些学生都聪明或这些学生都努力。聪明或这些学生都努力。故有故有 (x)A(x)x)A(x)(x)B(x)x)B(x)(x)(A(x)x)(A(x)B(B(x)x)由上式可得由上式可得(x)x)(A(A(x)x)(x x）（B(B(x)x)(x)x)(A(A(x)x)B(B(x)x)即即 （(x)A(x)x)A(x)(x)B(x)x)B(x)(x)(A(x)x)(A(x)B(B(x)x)因此因此 (x)(A(x)x)(A(x)B(x)B(x)(x)A(x)x)A(x)(x)x)B(B(x)x)可以推广到一般情况。可以推广到一般情况。离散数学 第一章类似地有类似地有 (x)(A(x)x)(A(x)B(B(x)x)(x x）A(A(x)x)(x x）B(B(x)x)(x)(x)(A(A(x)x)B(B(x)x)(x x）A(A(x)x)(x)B(x)x)B(x)离散数学 第一章序号序号表达式表达式E23(x)(A(x)B(x)(x)A(x)(x)B(x)E24(x)(A(x)B(x)(x)A(x)(x)B(x)E25(x)A(x)(x)A(x)E26(x)A(x)(x)A(x)E27(x)(A B(x)A(x)B(x)E28(x)(A B(x)A(x)B(x)E29(x)(A(x)B(x)(x)A(x)(x)B(x)E30(x)A(x)B(x)(A(x)B)E31(x)(A(x)B)(x)(A(x)B)E32A(x)B(x)(x)(AB(x)E33A(x)B(x)(x)(AB(x)I17(x)A(x)(x)B(x)(x)(A(x)B(x)I18(x)(A(x)B(x)(x)A(x)(x)B(x)I19(x)A(x)(x)B(x)(x)(A(x)B(x)离散数学 第一章8.多个量词的使用多个量词的使用对于二元谓词不考虑自由变元有八种情况：对于二元谓词不考虑自由变元有八种情况：1.(x)(y)A(x,y)2.(x)(y)A(x,y)3.(x)(y)A(x,y)4.(x)(y)A(x,y)5.(y)(x)A(x,y)6.(y)(x)A(x,y)7.(y)(x)A(x,y)8.(y)(x)A(x,y)离散数学 第一章例例如如:设设A(x,y)表表示示x和和y同同姓姓,论论域域x是是甲甲村村的的人人,y是乙村的人是乙村的人。(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)：乙村与甲村有人都同姓乙村与甲村有人都同姓故故(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)(y)(x)A(x,y)(x)(y)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)(y)(x)A(x,y)(x)(y)A(x,y)离散数学 第一章1.前束范式前束范式定义定义2-6.1一个公式，如果量词均在全式的一个公式，如果量词均在全式的开头，它们的作用域，延伸到整个公式的末尾，开头，它们的作用域，延伸到整个公式的末尾，则该公式叫做则该公式叫做前束范式前束范式。前束范式的前束范式的一般形式一般形式：(v1)(v2)(vn)A其中其中是量词是量词 或量词或量词，vi(i=1,2,3,n)是客体变是客体变元，元，A是没有量词的谓词公式。是没有量词的谓词公式。例如例如:(x)(x)(y)(y)(z)(Q(x,y)z)(Q(x,y)R(R(z)z)(y)(y)(x)(x)(P(P(x,y)x,y)Q(y)Q(y)等都是前束范式。等都是前束范式。2-6前束范式前束范式离散数学 第一章 定理定理2-6.12-6.1任意一个谓词公式，均和一个前任意一个谓词公式，均和一个前束范式等价。束范式等价。证明证明:首先利用量词转化公式，把否定深入到命题首先利用量词转化公式，把否定深入到命题变元和谓词填式的前面，然后利用等价公式变元和谓词填式的前面，然后利用等价公式:(x)(A B(x)A(x)B(x)(x)(A B(x)A(x)B(x)把量词移到全式的最前面，这样便得到前束把量词移到全式的最前面，这样便得到前束范式。范式。离散数学 第一章 例题例题1 1把公式把公式(x)P(x)x)P(x)(x)Q(x)x)Q(x)转化为前束转化为前束范式范式。解解:(x)P(x)x)P(x)(x)Q(x)x)Q(x)(x)x)P(P(x)x)(x)Q(x)x)Q(x)(E16,量词转化公式量词转化公式)(x)(x)(P(P(x)x)Q(x)x)(E23,量词分配律量词分配律)离散数学 第一章例题例题2 2化公式化公式 (x)(x)(y)(y)(z)(z)(P(x,y)P(x,y)p(y,z)p(y,z)(u)Q(x,y,u)u)Q(x,y,u)为前束范式。为前束范式。解解:原式原式 (x)(x)(y)(y)(z)(P(x,z)z)(P(x,z)P(y,z)P(y,z)(u)Q(x,y,u)u)Q(x,y,u)(E16,量词转化量词转化公式）公式）(x)(x)(y)(y)(z)(z)(P(P(x,z)x,z)P(P(x,z)x,z)(u)Q(x,y,u)u)Q(x,y,u)(x)(x)(y)(y)(z)(z)(u)(u)(P(P(x,z)x,z)P(P(x,y)x,y)Q(Q(x,y,u)x,y,u)离散数学 第一章例题例题3把公式把公式(x)(y)A(x,y)(x)(y)B(x,y)(y)(A(y,x)B(x,y)化化为前束范式。为前束范式。解：解：第一步：否定深入第一步：否定深入原式原式(x)(y)A(x,y)(x)(y)B(x,y)(y)(A(y,x)B(x,y)(x)(y)A(x,y)(x)(y)B(x,y)(y)(A(y,x)B(x,y)第二步：改名第二步：改名,把量词提到前面把量词提到前面(x)(y)A(x,y)(u)(R)B(u,R)(z)(A(z,u)B(u,z)(x)(y)(u)(R)(z)A(x,y)B(u,R)(A(z,u)B(u,z)离散数学 第一章2.前束合取范式前束合取范式定义定义2-6.2如果一个谓词公式如果一个谓词公式A具有如下形式，具有如下形式，则称其为一个则称其为一个前束合取范式前束合取范式。(v1)(v2)(vn)(A11 A12 A1k1)(A21 A22 A2k2)(Am1 Am2 Amkm)其中其中为为 或或，vi(i=1,2,1,2,n n)是客体变元，是客体变元，Aij是原是原子公式或其否定。子公式或其否定。例例如如：(x)(z)(y)P(xa)(z=b)Q(y)(a=b)就是一个就是一个前束合取范式前束合取范式。离散数学 第一章 定理定理2-6.2任何一个谓词公式都可以转化为与任何一个谓词公式都可以转化为与其等价的其等价的前束合取范式前束合取范式。离散数学 第一章 例例4将谓词公式将谓词公式D:(x)(y)P(x)(z)Q(z,y)(y)R(x,y)化为与之等价的前束合取范式。化为与之等价的前束合取范