离散数学 章节2 谓词逻辑.ppt

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