离散数学章节2 谓词逻辑

离散数学离散数学 章节章节2 2 谓词逻谓词逻辑辑 个体词、谓词与量词个体词、谓词与量词2.1谓词公式及其解释谓词公式及其解释2.2谓词公式的等价演算与范式谓词公式的等价演算与范式2.3谓词公式的推理演算谓词公式的推理演算2.4 2.1 2.1 个体词、谓词与量词个体词、谓词与量词 2.1.1 2.1.1 个体词与谓词个体词与谓词 定义定义2.1 2.1 在原子命题中，表示对象的在原子命题中，表示对象的词称为个体词；表示对象所具有的性质或词称为个体词；表示对象所具有的性质或多个对象之间关系的词称为谓词。多个对象之间关系的词称为谓词。个体词一般是原子命题中的主语或宾个体词一般是原子命题中的主语或宾语。个体词可以是具体事物，也可以是抽语。个体词可以是具体事物，也可以是抽象的概念，例如，小王，夏天，偶数，思象的概念，例如，小王，夏天，偶数，思想等都可以作为个体词。特定的个体词称想等都可以作为个体词。特定的个体词称为个体常元，用小写字母为个体常元，用小写字母 或或 表示；不确定的个体词称为表示；不确定的个体词称为个体变元，用小写字母个体变元，用小写字母 或或 表示。表示。谓词一般是原子命题中的谓语，通常谓词一般是原子命题中的谓语，通常用大写字母用大写字母 或或 表表示。含有示。含有n n个个 个体变元的谓词称为个体变元的谓词称为n n元谓词，也称为元谓词，也称为n n元简单命题函数，通常记元简单命题函数，通常记为为 。它实际上是它实际上是 到到00，11的一个函数，其中的一个函数，其中D Di i是个体变元是个体变元xixi的个体域。的个体域。所谓个体域（论域）就是个体变元遍所谓个体域（论域）就是个体变元遍历的非空集合。一般地，个体域应事先给历的非空集合。一般地，个体域应事先给定，如果没有给定，则约定个体域是全体定，如果没有给定，则约定个体域是全体事物构成的集合，称为全总个体域（全总事物构成的集合，称为全总个体域（全总论域）。另外，以后除非特别声明，否则论域）。另外，以后除非特别声明，否则认为一个认为一个n n元谓词的所有个体变元的个体域元谓词的所有个体变元的个体域是一样的。是一样的。由简单命题函数和命题连接词构成的由简单命题函数和命题连接词构成的表达式称为复合命题函数。表达式称为复合命题函数。n n元谓词元谓词 不是命题，只有当不是命题，只有当n n元元谓词中的全部个体变元在个体域中取定个谓词中的全部个体变元在个体域中取定个体常元后它才成为命题，此时，谓词已经体常元后它才成为命题，此时，谓词已经不含个体变元而只含个体常元。不含个体变元而只含个体常元。通常，我们将不含个体变元的谓词称通常，我们将不含个体变元的谓词称为为0 0元谓词，比如元谓词，比如 、等都是等都是0 0元谓词。元谓词。0 0元谓词是命题，命题逻元谓词是命题，命题逻辑中的命题都可表示为辑中的命题都可表示为0 0元谓词，因此可将元谓词，因此可将命题看成特殊的谓词。命题看成特殊的谓词。2.1.2 2.1.2 量词量词 定义定义2.2 2.2 设设D D为个体域，（为个体域，（1 1）“对对D D中任意的个体中任意的个体x”x”称为称为D D上的全称量词，记上的全称量词，记为为 ；（；（2 2）“在在D D中存在个体中存在个体x”x”称为称为D D上上的存在量词，记为的存在量词，记为 。用用d表示个体域，表示个体域，P(x)表示一元谓词，表示一元谓词，依据量词的定义，我们将依据量词的定义，我们将 和和 的含义总结如下：的含义总结如下：特别地，对于个体域特别地，对于个体域D为有限集，即为有限集，即 的情况，我们有：的情况，我们有：2.2 2.2 谓词公式及其解释谓词公式及其解释 2.2.1 2.2.1 谓词公式谓词公式 定义定义2.3 2.3 设设Di Di(1(1i in n)是相应于个是相应于个体变元体变元xixi的个体域，则相应于的个体域，则相应于DiDi的项是指的项是指按下列规则定义的符号串：按下列规则定义的符号串：（1 1）DiDi中的个体常元和个体变元是中的个体常元和个体变元是相应于相应于DiDi的项的项 （2 2）若是从）若是从D D11D D22DnDn到到DiDi的的元函数，元函数，titi(1(1i in n)是相应于是相应于DiDi的的项，则项，则 也是相也是相应于应于DiDi的项的项 （3 3）所有相应于）所有相应于DiDi的项都是有限次的项都是有限次使用（使用（1 1），（），（2 2）得到的符号串。）得到的符号串。例如，设例如，设f f和和g g分别表示一元和二元函分别表示一元和二元函数，数，a a是个体常元，是个体常元，x x，y y是个体变元，则是个体变元，则a a，x x，y y，f(x)f(x)，g(x,y)g(x,y)，g(f(x),x)g(f(x),x)，f(g(x,y)f(g(x,y)等都是项。等都是项。定义定义2.4 2.4 设设P(xP(x1 1,x,x2 2,x,x3 3,x,xn n)是是n n元元谓词，谓词，titi(1(1i in n)是相应于个体变元是相应于个体变元xixi的的个体域个体域DiDi的项，则称的项，则称P(tP(t1 1,t2,t,t2,t3 3,t,tn n)为为原子谓词公式，简称原子公式。原子谓词公式，简称原子公式。例如，设例如，设R(x,y,z)R(x,y,z)是三元谓词，是三元谓词，z z、f(z)f(z)、g(x,y)g(x,y)是三个项，则是三个项，则R(z,f(z),g(x,y)R(z,f(z),g(x,y)就是一个原子公式。就是一个原子公式。定义定义2.5 2.5 谓词公式是按下列规则定义谓词公式是按下列规则定义的符号串：的符号串：（1 1）0 0和和1 1是谓词公式；是谓词公式；（2 2）原子公式是谓词公式；）原子公式是谓词公式；（3 3）若）若A A、B B是谓词公式，则是谓词公式，则 、和和 是谓词公式；是谓词公式；（4）若）若x是个体变元，是个体变元，A是谓词公式，是谓词公式，则则 和和 是谓词公式；是谓词公式；（5 5）所有的谓词公式都是有限次使）所有的谓词公式都是有限次使用（用（1 1）、（）、（2 2）、（）、（3 3）、（）、（4 4）得到）得到的符号串。的符号串。例，例，、等都是谓词公式。等都是谓词公式。谓词公式是由原子公式，逻辑连接词，谓词公式是由原子公式，逻辑连接词，量词和圆括号等组成的符号串，命题逻辑量词和圆括号等组成的符号串，命题逻辑中的命题公式仅是它的特例，所以命题逻中的命题公式仅是它的特例，所以命题逻辑包含于谓词逻辑之中。辑包含于谓词逻辑之中。定义定义2.6 2.6 在谓词公式在谓词公式 和和 中，中，称称x x为指导变元，称为指导变元，称A A为相应量词的辖域或为相应量词的辖域或作用域，辖域中凡与指导变元相同的个体作用域，辖域中凡与指导变元相同的个体变元称为约束变元，不是约束变元的个体变元称为约束变元，不是约束变元的个体变元称为自由变元。变元称为自由变元。定理定理2.12.1（换名规则）（换名规则）在谓词公式中，在谓词公式中，将某量词辖域中出现的某个约束变元以及将某量词辖域中出现的某个约束变元以及对应的指导变元改成本辖域中未曾出现过对应的指导变元改成本辖域中未曾出现过的个体变元符号，其余部分保持不变，公的个体变元符号，其余部分保持不变，公式的等价性不变。式的等价性不变。定理定理2.22.2（代替规则）（代替规则）在谓词公式中，在谓词公式中，将某个自由变元的所有出现用其中未曾出将某个自由变元的所有出现用其中未曾出现过的某个体变元符号代替，其余部分保现过的某个体变元符号代替，其余部分保持不变，公式的等价性不变。持不变，公式的等价性不变。2.2.2 2.2.2 谓词公式的解释谓词公式的解释 定义定义2.7 2.7 谓词公式的一个解释由下面谓词公式的一个解释由下面四个部分组成：四个部分组成：（1 1）非空个体域）非空个体域D D（2 2）对）对A A中每个个体常元符号，指定中每个个体常元符号，指定D D中一个固定元素中一个固定元素 （3 3）对）对A A中每个函数符号，指定一个中每个函数符号，指定一个具体的函数；具体的函数；（4 4）对）对A A中每个谓词符号，指定一个中每个谓词符号，指定一个具体的谓词。具体的谓词。在定义在定义2.72.7中，所谓指定一个中，所谓指定一个n n元函数元函数和和n n元谓词就是分别给出元谓词就是分别给出 和和 的一个映射。的一个映射。定义定义2.8 2.8 设设A A是一谓词公式，若是一谓词公式，若A A在任在任何解释下均为真，则何解释下均为真，则A A称为永真式（有效式）称为永真式（有效式）。若。若A A在任何解释下均为假，则称在任何解释下均为假，则称A A为永假为永假式（矛盾式）。若存在解释使式（矛盾式）。若存在解释使A A为真，则称为真，则称A A为可满足式。为可满足式。定义定义2.9 2.9 设设 是命题公是命题公式式A A中出现的中出现的n n个命题变元，个命题变元，是是n n个谓词公式，用个谓词公式，用 处处代换处处代换A A中的中的pipi后所得谓词公式称为后所得谓词公式称为A A的代换实例。的代换实例。例如，谓词公式例如，谓词公式 ,，等都是命题公式，等都是命题公式 的代换实例，而的代换实例，而 不是不是 的代换实例。的代换实例。定理定理2.3 2.3 永真式的代换实例是永真式，永真式的代换实例是永真式，永假式的代换实例是永假式。永假式的代换实例是永假式。2.3 2.3 谓词公式的等价演算与范谓词公式的等价演算与范式式 2.3.1 2.3.1 基本概念与基本公式基本概念与基本公式 定义定义2.10 2.10 设设A A和和B B是两个谓词公式，是两个谓词公式，如果在任何解释下，如果在任何解释下，A A和和B B都有相同的真值，都有相同的真值，则称则称A A和和B B等价，记为等价，记为A=BA=B。依据等值运算依据等值运算“”“”和谓词公式等价和谓词公式等价关系关系“”的定义不难证明如下定理，它的定义不难证明如下定理，它与命题逻辑中的定理与命题逻辑中的定理1.21.2相对应。相对应。定理定理2.4 2.4 设设A A和和B B是两个谓词公式，则是两个谓词公式，则A=BA=B的充要条件是的充要条件是 是永真式。是永真式。定理定理2.52.5（量词否定律）（量词否定律）设设A A是谓词公是谓词公式，则有式，则有（1 1）（2 2）证明证明 只证明第一个等价关系，第二只证明第一个等价关系，第二个等价关系的证明类似。个等价关系的证明类似。任给解释任给解释I I（相应的个体域记为（相应的个体域记为D D），），在在I I下，若下，若 取值取值1 1，则，则 取值取值0 0，因此存在，因此存在 ，使得，使得A(a)A(a)取值取值0 0，即即 取值取值1 1，从而，从而 取值取值1 1；若若 取值取值0 0，则，则 取值取值1 1，因此对任意的因此对任意的 ，A(x)A(x)都取值都取值1 1，即，即对任意的对任意的 ，都取值都取值0 0，从而，从而 取值取值0 0。由解释。由解释I I的任意性可知（的任意性可知（1 1）式成立。）式成立。定理定理2.62.6（量词辖域的收缩与扩展律）（量词辖域的收缩与扩展律）设设A,BA,B是谓词公式，是谓词公式，B B不含个体变元不含个体变元x x，则有，则有（1 1）（2 2）（3 3）（4 4）定理定理2.72.7（量词分配律）（量词分配律）设设A,BA,B是谓词是谓词公式，则有公式，则有（1 1）（2 2）定理定理2.82.8（量词交换律）（量词交换律）设设A,BA,B是谓词是谓词公式，则有公式，则有（1 1）（2 2）2.3.2 2.3.2 等价演算等价演算 定理定理2.92.9（置换规则）（置换规则）设设 为含有子为含有子公式公式A A的谓词公式，的谓词公式，是用公式是用公式B B置换置换 中的中的A A（不要求处处置换）所得到的谓词公（不要求处处置换）所得到的谓词公式，若式，若A=BA=B，则，则 。2.3.3 2.3.3 前束范式前束范式 定义定义2.11 2.11 一个谓词公式称为前束范一个谓词公式称为前束范式，如果它具有如下形式：式，如果它具有如下形式：其中，其中，为为 或或 （1in），），A为不含量词的谓词公式。为不含量词的谓词公式。分别称分别称 和和A为前束为前束范式的首标和母式。范式的首标和母式。定理定理2.10 2.10 每一个谓词公式都存在与每一个谓词公式都存在与之等价的前束析取范式和前束合取范式。之等价的前束析取范式和前束合取范式。2.4 2.4 谓词公式的推理演算谓词公式的推理演算 2.4.1 2.4.1 基本概念与基本公式基本概念与基本公式 定义定义2.12 2.12 设设A A1 1,A,A2 2，,A,An n,B,B是谓词公是谓词公式，如果对式，如果对A A1 1,A,A2 2,A,An n都取值都取值1 1的任何解释，的任何解释，B B必取值必取值1 1，则称由前提，则称由前提A A1 1,A,A2 2,A,An n到到B B结论结论的推理是有效的（正确的），或者称的推理是有效的（正确的），或者称B B是前是前提提A A1 1,A,A2 2,A,An n的逻辑结论（有效结论），的逻辑结论（有效结论），记为记为 （）。）。定理定理2.11 2.11 设设A,BA,B是两个谓词公式，则是两个谓词公式，则A=BA=B的充要条件是的充要条件是 且且 。这个定理的证明可由谓词公式的等价定义这个定理的证明可由谓词公式的等价定义2.102.10和推理定义和推理定义2.122.12直接得到。直接得到。定理定理2.12 2.12 设设A A，B B是两个谓词公式，是两个谓词公式，则则 的充要条件是的充要条件是 是永真式。是永真式。2.4.2 2.4.2 演绎推理方法演绎推理方法（1 1）USUS规则（全称量词消去规则）规则（全称量词消去规则）或或 。（2 2）ESES规则（存在量词消去规则）规则（存在量词消去规则）。（3 3）UGUG规则（全称量词引入规则）规则（全称量词引入规则）。（4 4）EGEG规则（存在量词引入规则）规则（存在量词引入规则）或或 。结束语结束语谢谢大家聆听！谢谢大家聆听！55