第二章 第二节 项和公式 [兼容模式]

《第二章 第二节 项和公式 [兼容模式]》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2009-11-5第二章谓词逻辑§2.2项和公式§2.1谓词和量词本节讨论一阶逻辑的语法概念。§2.2项和公式项是用于表达个体的符号串，相当于汉语中的名词。公式是用于表达命题的符号串，相当于汉语中的句§2.3解释和赋值子。§2.4永真式项和公式是语法概念，它们都是符号串。两个项§2.5等值演算（公式）相同当且仅当它们是同样的符号串。与汉§2.6逻辑推论语不同，一阶逻辑的语言是形式语言，即一个符号作业串是不是项（公式）是可以用计算机判别的。§2.3讨论一阶逻辑的语义概念，即项和公式的解释。谓词逻辑中使用的符号分为以下几组。5.量词符

2、号∀。1.个体变元，简称变元，有无穷多个，用加或不6.联结词符号¬，→。加下标的小写英文字母x,y,z,u,v,w等表示。7.圆括号和逗号。2.个体常元，简称常元，有无穷多个，用加或不因为{¬,→}是联结词的完全集，其它联结词（除加下标的小写英文字母a,b,c,d等表示。了0元联结词）都可以用¬和→定义，所以只取3.函数符号，每个函数符号都联系一个正整数n，¬和→为初始符号，而将其它常用联结词符号作并称该函数符号为n元函数符号。对每个正整为被定义符号引入。数n，有无穷多个n元函数符号。用加或不加下标的小写英文字母f,g,h等表示函

3、数符号。有的书采用¬,∨或者¬,∧为初始符号。4.谓词符号，每个谓词符号都联系一个正整数n，因为用∀和¬可以定义存在量词∃，所以只取∀并称该谓词符号为n元谓词符号。对每个正整为初始符号，而将∃作为被定义符号引入。数n，有无穷多个n元谓词符号。用加或不加有的书采用∃为初始符号。下标的大写英文字母P,Q,R等表示谓词符号。在一阶逻辑中只有一种变元（个体变元）。如果有定义2.1项是按以下规则构成的有穷长符号串。函数变元和谓词变元，并且允许对它们量化，就成1.每个变元是项。为二阶谓词逻辑。二阶逻辑与一阶逻辑的性质有很大差别。二阶逻辑的表达

4、能力比一阶逻辑更强。例2.每个常元是项。如，论域的有穷性、良序集、自然数的归纳原理等3.若f是n元函数符号且t1,…,tn是项，则用一阶逻辑都无法表达，而可以用二阶逻辑表达。f(t1,…,tn)是项。例如，自然数的归纳原理可表达为二阶逻辑公式∀P(P(a)∧∀x(P(x)→P(f(x)))→∀xP(x))例如，x,c是项。其中P是一元谓词变元。若f是三元函数符号，g是二元函数符号，则取自然数集为论域，a：0，f(x)=x+1f(g(x,g(x,a)),b,f(x,c,y))该公式的意思是：对于任意性质P，若0有性质P，是项，而f(

5、x,a)不是项，因为三元函数符号f后面并且对于每个自然数x，只要x有性质P，只跟了两个项，而不是三个项。x+1就有性质P；那么每个自然数都有性质P。12009-11-5定义2.3公式是按以下规则构成的有穷长符号串。定义2.2若P是n元谓词符号且t1,…,tn是项，则1.每个原子公式是公式。称P(t1,…,tn)为原子公式。2.若A是公式，则¬A是公式。若f是一元函数符号，P是三元谓词符号，则3.若A,B是公式，则(A→B)是公式。P(x,f(a),b)4.若A是公式且x是变元，则∀xA是公式。是原子公式，而P(f(b),x)不是原

6、子公式，因为三若f,g是一元函数符号，P是一元谓词符号，Q元谓词符号P后面只跟了两个项，而不是三个项；是二元谓词符号，则P(x,f(b,x),x)不是原子公式，因为f(b,x)不是项。(Q(f(a),b)→∀x(P(x)→Q(f(x),g(f(x)))))显然：原子公式中不含有量词和连接词。是公式。定义2.4引进以下缩写约定：我们把联结词符号和量词符号分为两部分，一部分是原始符号（¬,→,∀），另一部分是被定义符号（∨,∧,↔,⊕,∃）。减少初始符号的个数，可以使得公式的定义更简短，因而使得用归纳法证明所有公式都有某性质时证明更短

7、。另一方面，引进被定义符号使缩写后的公式简单明了，更易读。在命题逻辑中，曾经对公式做过一些减少括号的约定，那些约定在这里仍然适用。定义2.5若公式B是公式A的子串，则称B为A的子公式。定义2.6称变元x在公式∀xA中的出现为约束出显然，每个公式都是自己的子公式。每个原子公式现，并称∀x的该次出现的辖域为A。如果变元x仅有的子公式是它自己。公式越复杂，它的子公式在公式A中的某次出现是在A的一个子公式中的越多。约束出现，则称x的该次出现为在A中的约束出公式¬∀x(P(x)→Q(x,y))的子公式为现。如果变元在公式A中的某次出现不是约

8、束出P(x)，Q(x,y)，(P(x)→Q(x,y))，现，则称该出现为在A中的自由出现。在公式A∀x(P(x)→Q(x,y))，¬∀x(P(x)→Q(x,y))中有自由出现的变元称为A的自由变元，在公式A公式¬∀x(P(x)→∃yR(x,y))的