我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:小鱼儿玄机1站开奘结果 > 前束范式 >

一阶逻辑的详细内容

归档日期:06-16       文本归类:前束范式      文章编辑:爱尚语录

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  在一阶逻辑中描述一个数学理论,首先会涉及这个理论所讨论的对象、定义在这些对象上的函数、以及这些对象之间的关系或性质。数学理论所讨论的对象称为个体,由个体组成的非空集合称为论域或个体域。按通常数学中的定义,一个n元函数就是从论域A的个体的所有n元组的集合至A中的一个映射。A中个体的n元组(α1,α2,…,αn)经映射F对应到A中的个体表示为F(α1,α2,…,αn)。函数增加了个体的表达形式。人们也考虑论域A中哪些n元组满足关系R,即A中哪些n元组(α1,α2,…,αn)使得R(α1,α2,…,αn)为线,…,αn)就是一个命题。

  在各种关系中,相等关系是经常要用的。因为常常需要知道不同个体的表达式是否指称同一个对象。例如3+3与2×3是否表示同一个数。

  可以将关系或命题用命题连接词来构成更复杂的关系或命题。当描述一些个数为无穷的对象的性质时,就需要引进量词。例如说“对任何一个自然数,都有一个比它大的素数”时,就引进了量词“所有个体”及“存在个体”,并且将关系或命题经量词构成了更复杂的关系或命题。“论域中的所有个体”称为全称量词,由它所构成的命题“论域中所有的个体有某性质”,当论域中所有个体都有此性质时,此命题是真的,否则为假。“论域中存在个体”称为存在量词,由它所构成的命题“论域中存在个体有某性质”,当论域中某些个体有此性质时为真,否则为假。

  “所有个体”、“存在个体”中,量词加在论域的个体上,称为一阶量词。在一阶逻辑中使用的量词仅限于一阶量词。“所有函数”、“存在函数”、“所有关系”和“存在关系”是二阶量词。此外还有更高阶的量词。相应地也有二阶逻辑、高阶逻辑等。

  按照建立形式系统的一般原则(见逻辑演算),一阶逻辑的形式系统应包括它的语言,即一阶语言,以及逻辑公理和推理规则。一阶语言的符号包括以下几类。

  ② 函数符号(表示函数),g,h,…;个体符号(表示论域中的个体) α,b,с,…;及谓词(表示关系)p,Q,R,…。其中有一个二元谓词=,称为等词(表示恒同关系)。

  ② 若t1,t2,…,tn是项,是一个n元函数符号,则(t1,t2,…,tn)是项。

  ① 若t1,t2,…,tn是项,p是n元谓词符号,则p(t1,t2,…,tn)是公式,也称为原子公式。

  ② 若A是公式,则塡A是公式;若A,B是公式,则A∧B,A∨B,A→B,A凮B是公式。

  如果变元x出现在公式 A中形如xB或凬xB的部分,称这个出现为x在A中的约束出现;否则,称为x在A中的自由出现。例如在公式x=0∨x(x0)中,第一个x是自由出现,第二、三个x是约束出现。没有变元自由出现的公式称为闭公式。

  谓词演算作为一个形式系统,可以规定它的解释。给定一个论域,对于谓词演算中出现的个体符号、函数符号及谓词依次解释为论域中的个体及定义在此论域上的函数及关系。此论域及其对于谓词演算中形式符号的解释称为该演算的一个结构或模型。由对于个体符号和函数符号的解释可知,项可解释为复合函数,它指称个体。原子公式p(t1,t2,…,tn)解释为t1,t2,…,tn所指称的个体满足n元关系p。若公式A(x)表示关系,则凬xA(x)解释为论域中所有个体满足关系A,xA(x)解释为论域中存在某个体满足关系A。

  ① 命题公理 将重言式(见命题逻辑)中出现的命题变元代之以谓词演算中的任意公式后得到的公式;

  ③ 替换公理 Ax【α】→xA及凬xA→Ax【α】,其中Ax【α】表示将公式A中所有x的自由出现代之以项α。

  谓词演算的公理,即逻辑公理并不界定具体的函数或关系,而仅仅处理逻辑词项的一般性质。换言之,对它的个体符号、函数符号、及谓词的解释可以是任意论域中的任意个体、函数及关系。谓词演算的这个抽象性质对于近年来模型论的发展是本质的。

  在谓词演算的框架中,用形式语言表述数学的公理(并不一定能完全表述),就得到不同数学理论的形式系统。这类形式公理刻画了某些具体的非逻辑符号的性质,称为非逻辑公理。例如:

  全序理论的形式系统中仅有一个非逻辑符号二元谓词≤。除逻辑公理外,它还有非逻辑公理:①x≤y∧y≤z→x≤z;②x≤y∧y≤x→x=y;③x≤x;④x≤y∨y≤x。自然数集合及其上的顺序关系就是全序理论的一个模型。

  群论的形式系统中只有两个非逻辑符号:个体符号1及二元函数符号·。它的非逻辑公理为:① x·(y·z)=(x·y)·z;②x·1=x;1·x=x;③y(x·y=1∧y·x=1)。任何一个群都是它的模型。

  数论的形式系统中的非逻辑符号有:个体符号0,一元函数符号s及两个二元函数符号+及·。数论(或皮亚诺算术)的公理为:①塡s(x)=0,②s(x)=s(y)→x =y,③x+0=x,④ x+s(x)=s(x+y),⑤ x·0=0,⑥x·s(y)=(x·y)+x,⑦若A为系统内的公式,x0在A中自由出现,则对每个这样的公式A,有公理自然数的算术就是它的一个模型。

  陈述在一阶语言中,由逻辑公理、非逻辑公理及推理规则推出的全部形式定理(见逻辑演算)称为一阶理论,记为T。为区别不同的一阶理论T,只要指出T的语言中的非逻辑符号及非逻辑公理就够了。任何一阶理论都包含了谓词演算作为它的子系统。

  在谓词演算的任意模型中均为真的公式称为永真的或有效的公式。例如,公式A(x,y)∨塡A(x,y)就是有效的公式,而x≤y∨y≤x就不是有效的。因为在全序结构中,对x,y在个体域中的任意取值,该公式的解释均为真。而在半序结构中,例如该结构的论域为一个集合的全体子集的集合,≤解释为集合的包含关系,那么上式的解释当x,y取任意的两个子集时就不都是真的了。

  直观上看,逻辑的定理应当是在一切可能的世界中均为真的定理。在一定意义下,谓词演算满足这个性质。可以验证,谓词演算的公理均为有效的,它的推理规则的假设有效则结论也必有效。因此,谓词演算的所有定理都是有效的。这个性质称为谓词演算的有效性或可靠性。反之,任意有效的公式必为谓词演算的定理。这就是著名的哥德尔完备性定理。由K.哥德尔于1930年证明。用├A表示A是谓词演算的形式定理,即A 是系统内的定理。而可靠性与完备性刻画了整个形式系统的性质,是关于系统的定理,也称为元定理。形式系统的性质是数理逻辑主要的研究对象之一。

  由谓词演算的有效性及完备性容易推知一阶理论的可靠性与完备性。使一阶理论 T的所有公理为真的结构称为T 的一个模型。若T的一个公式A在T 的任意模型中均有效,称A在T中有效,记为T喺A。A是T的定理记为T├A。那么T的可靠性与完备性就可以陈述为T├ A的充分必要条件为T 喺A。

  形如x1,x2,…,xnB 的公式称为前束型公式,其中xi表示 xj或凬xj,B 是一个不含量词的公式。任何一个一阶理论T(当T 的非逻辑公理集为空集时就是一个谓词演算)的公式A,都有一个公式A′,使得T├A凮A┡,其中A┡为前束型公式x1,x2,…,xηB,且B中的非逻辑符号均在A中出现。A′也称为A的前束范式。此性质可用于对谓词演算或一阶理论的公式进行分类上。此时只需考虑前束范式中的量词,将它作为公式复杂性的一种测度。

本文链接:http://scrinzoom.com/qianshufanshi/234.html