FoundationsofLogic (5).pdf
《FoundationsofLogic (5).pdf》由会员分享,可在线阅读,更多相关《FoundationsofLogic (5).pdf(21页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、The completeness problemReformulationMaximal consistent setsTruth LemmaLindenbaums LemmaOnline Course:Foundations of LogicTsinghua University,spring 2020Dag Westerst ahlTsinghua LogicThe completeness problemReformulationMaximal consistent setsTruth LemmaLindenbaums LemmaThis is Chapter 4We have two
2、notions of consequence:|=iffevery interpretation making all sentences in true also makes true.H iffthere is a derivation in H of from.These are conceptually very different!One talks about the existence of a finite syntactic object(aderivation),the other quantifies over all interpretations.In Proposi
3、tional Logic(PL)the difference is not so great:interpretations are valuations,and for every sentence onlyfinitely many different valuations are relevant.(Why?)But in FOL the difference is huge.(Why?)1 of 20The completeness problemReformulationMaximal consistent setsTruth LemmaLindenbaums LemmaSoundn
4、ess and completenessAn inference system S is sound ifI S implies|=and it is complete ifI|=implies SSoundness is(usually)easy:Show that the axioms(if any)arelogically true,and that the rules preserve truth.This is easy to check for H(or ND);you can find the proof(by induction)in Chapter 4.1.The hard
5、part is completeness.2 of 20The completeness problemReformulationMaximal consistent setsTruth LemmaLindenbaums LemmaCompleteness for PLToday we consider the completeness of the system H for PL.We must show that if is true in every valuation in which(all sentences in)is truethenthere is a derivation
6、of in H from.That doesnt seem obvious.Actually there are fairly simple ways of showing completeness for PL(this was first done in 191820 by Paul Bernays and(independently)Emil Post);see Exercise 4.7.11.We will use another technique,because it generalizes almost directlyto FOL.3 of 20The completeness
7、 problemReformulationMaximal consistent setsTruth LemmaLindenbaums LemmaA reformulation of the problemRecall that a set of sentences is satisfiable if there is aninterpretation making(all sentences in)true,and that(1)|=iff is unsatisfiable.We say that is consistent if 6 (where is some PL-sentencesuc
8、h that H,such as(p0 p0).We have:(2)H iff is inconsistent.4 of 20The completeness problemReformulationMaximal consistent setsTruth LemmaLindenbaums LemmaThe Consistency LemmaThis means that to show completeness,it is enough to showLemma(Consistency Lemma)If is consistent,then is satisfiable.For then:
9、So we focus on proving the Consistency Lemma.5 of 20The completeness problemReformulationMaximal consistent setsTruth LemmaLindenbaums LemmaThe Consistency LemmaSo suppose is consistent.How can we find a valuation V makingall sentences in true?Idea 1:Let tell us the truth value of every sentence let
10、ter p:IIf p ,let V(p)=1;otherwise V(p)=0.So if p ,then p 6 (since is consistent),so V(p)=0,which is good!But there is a problem:may not contain enoughinformation.Example:suppose p but p 6.Example:suppose p q and p ,but q 6.Solution:Add the missing sentences to!But how do we know which sentences are
11、missing,and how can weadd them systematically?6 of 20The completeness problemReformulationMaximal consistent setsTruth LemmaLindenbaums LemmaMaximal consistent setsIdea 2:Extend to a maximal consistent set.Definition(maximal consistency)is maximal consistent if it is consistent,and no further senten
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- FoundationsofLogic 5
限制150内