您好、欢迎来到现金彩票网!
当前位置:2019欢乐棋牌 > 指称语义 >

逻辑学03_图

发布时间:2019-07-02 07:47 来源:未知 编辑:admin

  逻辑学03_教育学_高等教育_教育专区。高级逻辑学 ----计算机科学中的逻辑学 Logic in Computer Science 第三讲 形式系统的元语言和元理论 谢 冰 北大信息学院软件研究所 .ed

  高级逻辑学 ----计算机科学中的逻辑学 Logic in Computer Science 第三讲 形式系统的元语言和元理论 谢 冰 北大信息学院软件研究所62759627(O)理科1号楼1508室 2004年9月 1 第三讲 形式系统的元语言和元理论 何谓 元(Meta)? 在层次式定义框架中,用来定义下层概念的上层概念称为对下层 概念的元概念。(邵老师) 例如: 1、语言的层次性 “鸟在飞” “是啊,鸟是会飞的” 2、模型的层次性 系统模型、元模型、元元模型 ——对象语言 ——元语言 区分语言的层次是重要的: 悖论:“此刻你读的这句话为假” 若把这句话记为a,则a的内容是“a假”,因而a线、形式系统的元语言和元理论 对象语言 ! 形式系统本身的语言(FS的语言部分规定的语言) 其中的符号表示的是客观对象的抽象 公理、规则模式中则是一类符号的表示 元语言 ! 描述、说明形式系统的语言。 关于形式系统本身的理论。 元理论 ! 元语言是研究形式系统所使用的语言,元理论是研究形式系统的 理论成果的总和。 元语言是元理论的语言。 2004年9月 3 元语言 元语言成分包括: ! 对形式系统各组成部分的称谓 如术语项、公式、公理等 ! 对系统分析讨论时所使用的逻辑术语(元逻辑术语) 如“如果…那么…”、“当前仅当”、“存在”、“所有”等,并 不是形式系统中的符号 ! 描述形式系统有关性质的元语言术语 如“一致性”、“可判定性”等 2004年9月 4 元语言的形式符号 1. 元语言中继续使用的对象语言中的符号 ! ! 对象语言:符号的客观实体 元语言:作为对象语言中符号实体的名 2. 元语言中使用语法变元表示对象语言中的一类符号或 表达式 ! ! 如 t 表示系统中的任意项 模式:一类规则或公理 如┣, ┣FS, ╞╡等 3. 元语言自身的符号 ! 2004年9月 5 元理论 元理论:关于形式系统本身的理论 包括:研究所使用的理论工具以及研究的理论成果 元理论中使用的是最基本、直觉上毫无异议的成分 ! ! ! 概念:易理解 推理:依直觉进行 理论和方法:简单,有穷的 2004年9月 6 元理论关于形式系统的研究内容 关于语构(syntax,语法)的研究 ! 研究形式系统作为一个形式(无具体意义)的符号 系统中的符号串的推演(重写)规律 关于语义(semantics)的研究 ! 如何赋以形式符号一定的意义,以及这些赋值的相 关性质 关于语构和语义关系的研究 2004年9月 7 3.1 系统语构的研究 形式系统的文法(形式语言理论) 语言的构成规律(基于公理和重写规则的系统性 质:如演绎特性、结构特性等) 2004年9月 8 元理论的概念 定义 1.7 形式系统FS称为独立的(independent),如果它 的每一个公理都是独立的,即若把任一公理A从FS中删 去后,所得的系统FS’不满足┣FS’A 。 FSPC是独立的。 独立性保证了系统的定义简洁性、优美(简单、完整)。 但牺牲了系统的实用性(应用简单),可通过定理 扩展提高系统的应用方便性。 2004年9月 9 定义 1.8. 形式系统FS称为一致的(consistent,协调的), 如果不存在FS的公式A,使得┣FSA与┣FS ┐A同时成立。 一致性是系统必须具备的性质。 否则,该系统就没有意义了,成了可以胡说八道的系统。 2004年9月 10 定义 1.9. 形式系统FS称为完全的(complete),如果对FS的任一公 式A,或者┣FSA,或者┣FS ┐A。 定义 1.10. 形式系统FS称为可判定的(decidable),如果存在一个 算法,对FS的任一公式A,可确定┣FSA是否成立。 否则,称FS为不可判定的(undecidable)。 如果上述算法不一定存在,但有一个过程,可对该系统的定理作 出肯定的判断,但对非定理的公式过程未必终止,这时FS称为半 可判定的(partial decidable)。 2004年9月 11 定义 1.11. 形式系统 FS1=∑1,TERM1,FORMULA1,AXIOM1,RULE1 称为形式系统 FS2=∑2,TERM2,FORMULA2,AXIOM2,RULE2 的扩充 (extensions), 如果∑2?∑1, TERM2?TERM1, FORMULA2?FORMULA1,RULE2?RULE1,AXIOM2?Th(FS1)。 易证: 若FS1是FS2的扩充,则Th(FS2) ?Th(FS1)。 2004年9月 12 定义 1.12. 称FS的公式集Γ是一致的,如果FS是一致的, 并且它的扩充 ∑, TERM, FORMULA, AXIOM∪Γ, RULE 是一致的。 对公理的扩充,不能引入不一致性。 但对非单调逻辑,如何理解? 2004年9月 13 定义 1.13. FS的公式A,B称为演绎等价的(deductively equivalent),如果A┣FSB且B┣FSA,记为A┣┫FSB 。 定理1.5. 对FSPC中的任意定理A,B, A┣┫B。 定理1.6. FSPC是一致的,即不存在FSPC的公式A,使得 ┣A和┣ ┓A 都成立。 2004年9月 14 定理1.7. FSPC不是完全的,即存在FSPC的公式A,使得 ┣A和┣ ┓A 都不成立。 定理1.8. FSPC的不一致扩充必定是完全的,但至少有一 个公式不是FSPC的一致扩充的定理。特别的,当公式 集Γ不一致时,扩充FSPC∪Γ是完全的;当Γ一致时, 至少有一个公式A不是FSPC∪Γ的定理。 2004年9月 15 定理1.9. FSPC是可判定的。 定理1.10. 对FSPC中的任意公式集Γ和公式A,B, Γ;A┣ B当且仅当Γ┣ A →B。(元定理:演绎定理) 证明: (归纳法),要求自己看。 2004年9月 16 3.2 系统语义的研究 形式系统不针对某一个特定的客体范畴、或特定的性质关系(只是 符号串) 但可以对它作出种种解释 ! ! 赋予它一定的论域:研究对象的集合 赋予它一定的结构:用论域中的客体、客体上的运算和客体间的关 系解释系统中的抽象符号 形式系统的语义结构:赋予形式系统的论域及解释。 语义(semantics) : 结构连同该结构下公式所取真值的 规定。指称语义(denotational semantics) 2004年9月 17 定义 1.14. 形式系统FS的结构Ц (1)当FS的TERM≠Ф时由下列集合U及规则组I 所组成 (有时称为 Ц =U, I): (1.1)非空集合U,称为论域(universe),也称为个体域(domain of individuals). (1.2)一组规则I,称为解释(interpretation),据此规定如何对项指称 U 中个体;规定如何对原子公式指称U 中个体的性质(或U 的子集)、 关系(或U n 的子集). (2)当FS的TERM=Ф时,结构Ц为一映射v v: ATOMIC → VALUE v常称为赋值映射,这里VALUE为一确定的集合,至少含有 成员0,1,他们分别表示真值假和真,VALUE仍称为真值集合,但 是可以有更广义的真值集。(多值逻辑、模糊逻辑) 2004年9月 18 例1.10 (1) FSPC中TERM=Ф时,因此,任一赋值映射 v:{p1,p2,…} → {0,1}即为一个结构。 (2) 考虑FSEN的一个结构Ц,其论域为{0,1,2,3,…},解 释I把符号0解释为数0,把符号 ‘ 解释为“后继”,即 I(t’)= I(t)+1,把符号解释≌为N上的相等关系。 2004年9月 19 定义1.15. 若形式系统FS的VARIABLE≠Ф,那么下列映射称 为指派(assignments): s:VARIABLE → U 当给定结构Ц后,对每一指派s可作出其扩展s’: TERM→U, 使 s’(t)= s(t) s指派t中变元后由解释I确定 当t为变元 当t为非变元 如:扩充FSEN使之含有变元x1,x2,x3,…,那么s(x1)=s(x2)=s(x3)=…=1为 一指派,且s’(x1)=s’(x2)=s’(x3)=…=1,s’(x1(n))=I(1(n))=n+1. 2004年9月 20 在给定一结构Ц和一指派s后, ! ! FS的每一个项t均对应于U中的一个体s’(t) FS的每一个公式A对应于有关论域U的一个命题,记为AЦ[s] FORMULAЦ,s={AЦ[s]A?FORMULA } ATOMICЦ,s={AЦ[s]A?ATOMIC } 令 定义1.16. 赋值(valuation)是指一组给公式赋真值的规 则,据此规则,可对每一结构Ц和指派s确定一映射, v: ATOMICЦ,s→VALUE,并据此规则扩展v为赋值函数 v’: FORMULAЦ,s→VALUE 使 v’(AЦ[s])=v(AЦ[s]) 当 A ? ATOMIC 时 赋值实际规定了联结词的语义。 2004年9月 21 例:对于FSPC,TERM=Ф,赋值确定的映射v已由结构Ц 直接给出,赋值还应包括扩展v为v’的下列规则: v’(┓A)= v’(A→B)= 0 当v’(A)=1 1 0 1 当v’(A)=0 当v’(A)=1且v’(B)=0 否则 每一组Ц,s,v,v’构成FS的一个语义。 2004年9月 22 定义1.17. 称公式A在结构Ц中指派s下真,或Ц,s弄真A, 如果v’(AЦ[s])=1,记为╞═ЦA[s]。 否则称公式A在结构Ц中指派s下假,或Ц,s弄假A, 记为╞═ЦA[s]。 称A在Ц中真,或Ц弄真A,或Ц为A的模型(model), 如果对一切s, 有╞═ЦA[s],记为╞═ЦA。 否则称Ц不是A的模型,记为╞═ЦA。 称A为永真(valid),如果对所讨论的一类结构M中的 每一个结构Ц,均有╞═ЦA,记为╞═MA。 (这里是针对二值结构的讨论) 2004年9月 23 定义1.18. 公式A称可满足的,如果存在结构Ц,指派s, 使╞═ЦA[s]。 否则称A是不可满足的。 公式集Γ称为可满足的,如果存在Ц,s,弄真Γ中 的每一公式。 否则称Γ是不可满足的。 Ц称为Γ的模型,如果Ц为Γ中每一公式的模型。 2004年9月 24 定义1.19. 设Γ为FS的公式集合,A,B为公式,称Γ逻辑蕴 含(logically implies)A,或A为Γ的逻辑结果(logical consequence),如果弄真Γ中每一公式的Ц,s也必弄真 A,记为 Γ╞═MA。M为所论的结构类。 称A,B逻辑等价(logically equivalent),若A╞═MB且 B╞═MA,记为A╞╡M B。 由此,可证,对FSPC的任意公式A,A╞╡v┓┓A。 2004年9月 25 3.3 系统语构和语义关系的研究 形式系统中的每一定理是否在所讨论的一类结 构中永真? 所讨论的一类结构中永真的公式是否是形式系 统内的定理? 是否对任意公式集Γ和公式A,有“A是Γ的演 绎结果当且仅当A是Γ的逻辑结果” 2004年9月 26 定义1.20. 称形式系统FS是合理的(sound),如 果对FS中的任意公式A有:若┣FSA,则╞MA。 其中M是对FS所讨论的一类结构。 定理1.11. FSPC是合理的,即对FSPC中的任一公式A, ┣FSA,蕴含╞vA。 定理1.12. 若FSPC的公式集Γ可满足,则Γ是一致的。 定理1.13. 对FSPC的任意公式集Γ和公式A,若Γ┣FS A, 则 Γ╞v A。 2004年9月 27 定义1.21. 称形式系统FS具有完备性(completeness),如 果对FS中的任意公式A有:若╞MA ,则┣FSA 。其中M 是对FS所讨论的一类结构。 正确的东西是否都可以由FS推导出来? 不协调的FS肯定是完备的。 定理1.14. FSPC具有完备性,即对FSPC中的任一公式A, ╞vA ,蕴含┣FSA 。 定理1.15. 对FSPC的任意公式集Γ和公式A,若Γ╞v A , 则Γ┣FS A 。 2004年9月 28 定义1.22. 称形式系统FS具有紧致性(compactness),如 果对FS中的任意公式集Γ有:若Γ的所有有穷子集可 满足,那么Γ也是满足的。 (紧致性使得可以使用有穷子集来扩展到无限集上去) 定理1.16. 若FSPC的公式集Γ是一致的,那么Γ是可满 足的,且其逆亦线. FSPC具有紧致性。 2004年9月 29 歌德尔(Godel)不完备性定理 定理1.18. 设FS为任一包括初等数论的形式系统,如果 FS是一致的,那么FS在下述意义下是不完备的:存在 FS的公式A,它是初等数论的真命题,但A和┓A却都 不是FS的定理。 只要FS中可定义初等数论基本概念,FS的一致性和上述意义下的完 备性就不能两全。 即无论怎样扩展一个FS,只要维持其一致性,就不能在该系统中推出 一切数论真命题。 所以FS也不是万能的。 2004年9月 30

http://acetechpng.com/zhichenyuyi/159.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有