资源描述：
《离散数学 章节2 谓词逻辑.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第2章谓词逻辑个体词、谓词与量词2.1谓词公式及其解释2.2谓词公式的等价演算与范式2.3谓词公式的推理演算2.42.1个体词、谓词与量词2.1.1个体词与谓词定义2.1在原子命题中，表示对象的词称为个体词；表示对象所具有的性质或多个对象之间关系的词称为谓词。个体词一般是原子命题中的主语或宾语。个体词可以是具体事物，也可以是抽象的概念，例如，小王，夏天，偶数，思想等都可以作为个体词。特定的个体词称为个体常元，用小写字母或表示；不确定的个体词称为个体变元，用小写字母或表示。谓词一般是原子命题中的谓语，通常用大写字母或表示。含有n个个体变元的谓词称
2、为n元谓词，也称为n元简单命题函数，通常记为。它实际上是到{0，1}的一个函数，其中Di是个体变元xi的个体域。所谓个体域（论域）就是个体变元遍历的非空集合。一般地，个体域应事先给定，如果没有给定，则约定个体域是全体事物构成的集合，称为全总个体域（全总论域）。另外，以后除非特别声明，否则认为一个n元谓词的所有个体变元的个体域是一样的。由简单命题函数和命题连接词构成的表达式称为复合命题函数。n元谓词不是命题，只有当n元谓词中的全部个体变元在个体域中取定个体常元后它才成为命题，此时，谓词已经不含个体变元而只含个体常元。通常，我们将不含个体变元的谓词
3、称为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(1≤i≤n)是相应于个体变元xi的个体域，则相应于Di的项是指按下列规则定义的符号串：（1）Di中的个体
4、常元和个体变元是相应于Di的项（2）若是从D1×D2×…×Dn到Di的元函数，ti(1≤i≤n)是相应于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(1≤i≤n)是相应于个体变元xi的个体域Di的项，则称P(t1,t2,t3,…,tn)为原子谓词公式，简称原子公式。例如，设R(x
5、,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在
6、谓词公式和中，称x为指导变元，称A为相应量词的辖域或作用域，辖域中凡与指导变元相同的个体变元称为约束变元，不是约束变元的个体变元称为自由变元。定理2.1（换名规则）在谓词公式中，将某量词辖域中出现的某个约束变元以及对应的指导变元改成本辖域中未曾出现过的个体变元符号，其余部分保持不变，公式的等价性不变。定理2.2（代替规则）在谓词公式中，将某个自由变元的所有出现用其中未曾出现过的某个体变元符号代替，其余部分保持不变，公式的等价性不变。2.2.2谓词公式的解释定义2.7谓词公式的一个解释由下面四个部分组成：（1）非空个体域D（2）对A中每个个体常元
7、符号，指定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永真式的
8、代换实例是永真式，永假式的代换实例是永假式。2.3谓词公式的等价演算与范式2.3.1基本概念与基本公式定义2.10设A和B是两个谓词公式，如果在任何解
