FoundationsofLogic (1).pdf-得力文库

资源描述

《FoundationsofLogic (1).pdf》由会员分享，可在线阅读，更多相关《FoundationsofLogic (1).pdf（35页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.Online Course:Foundations of LogicDag Westerst ahlTsinghua LogicPractical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.PlanWelcome to

2、 the online Foundations of Logic course2020!We will cover the following:(week 1-2)background:syntax,semantics,and inference inFirst-Order Logic(FOL)(week 3)completeness of FOL(week 4)some model theory(week 5-8)incompleteness and undecidabilityWith corresponding chapters in the textbook(detailedinstr

3、uctions of what to read in the book will be given).1 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.TeachersLectures:Dag Westerst ahlTeaching Assistant:Jialiang Yan2 of 34Practical mattersContentNotationPropositional logic:syntaxPr

4、opositional logic:semanticsLogical consequence etc.Course materialEach of the following materials is essential for the course:Ithe lectures with the slides shown(will be recorded)Ithe textbook(selected sections)Ithe homeworkHomework:Logic(like mathematics,or physics,or computerscience,or.)is not a s

5、ubject you can learn by reading abook:you also need to do logic,i.e.do exercises.3 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.Slides and homeworkNot everything is written on the slides:ITo make the presentation more dynamic,I w

6、rite somethings by hand,using parts of the slides as a whiteboard.IAlso,some things will not be presented,you must readabout those in the book.In principle,you will get homework each week,to be sent toJialiang as pdf files.(If you write by hand clearly,you cantake pictures and reformat them as pdf f

7、iles.)IThe language of homework is English.IThe homework is part of the examination.4 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.Questions and communicationQuestions can be asked during the lectures:Ipress the Raise Hand button

8、 and either(when yourmicrophone has been unmuted)speak you question or write itas a chat.Outside of lectures(there are no office hours),you can askquestions byIusing the Wechat group to ask questions that you think maybe of general interest;Isend an email to Dag or Jialiang.On this kind of course th

9、ere is not so much directcommunication between students,so ask questions!5 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.AttendanceYou should attend all lectures.If you find at some point that this course is not what youwanted(it

10、is too difficult,too easy,too technical,toophilosophical,.),then:please let Jialiang and me know that you decided to drop thecourse!6 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.Preview week 3:completenessLogic is about conseque

11、nce:what follows from what.There are two ways to define logical consequence:(a)in terms of necessary preservation of truth(b)in terms of reasoning according to rules of inferenceThese are conceptually very different.Theorem(Completeness theorem(G odel 1930)A FOL sentence follows from certain premise

12、s according to(a)ifand only if it follows from those premises according to(b).7 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.Preview week 4:a glimpse of model theoryThe methods we use to prove completeness can be used tounderstan

13、d the expressive power of FOL.For example,in FOL you can say“there are at least 27 thingssuch that.”.We will show that you cannot say(with one sentence)“thereare infinitely many things such that.”,or(even with aninfinite numbers of sentences)“there are finitely many thingssuch that.”.This limitation

14、 of expressive power is both a weakness and astrength of FOL!8 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.Preview week 5-7:incompletenessThe point of theories,about e.g.numbers or electrons,is toprove using logics like FOL true

15、 statements about theseobjects.Thats how we can know these facts.For example,that there are infinitely many prime numbers.The incompleteness theorems state that there is a hugedifference between truth and proof!Theorem(1st incompleteness theorem,G odel 1931 and later)Every axiomatic theory T which i

16、s free from contradictions andcontains some elementary arithmetic is incomplete:there are truestatements which cannot be proved in T.9 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.Preview week 8:undecidabilityA problem is solvabl

17、e,or decidable,if there is a mechanicalmethod,specified in advance,that answers specific questionsabout the problem in a finite number of steps.Problem 1:Is n a prime number?Decidable.(How?)Problem 2:Does sentence follow logically(in FOL)frompremises 1,.,k?Theorem(Church,Turing 1936)FOL is undecidab

18、le.Not only have logicians so far been unable to find a decisionmethod for Problem 2 no such method exists!10 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.Lets begin!That was a taste of good things to come;now lets begin.Chapter

19、2 presents the syntax and semantics of First-OrderLogic(FOL),also called Predicate Logic.We will go through notation and terminology,assuming thatyou have seen some version of this before.(If not,its all there!)If you dont understand,ask!11 of 34Practical mattersContentNotationPropositional logic:sy

20、ntaxPropositional logic:semanticsLogical consequence etc.Greek lettersFirst piece of notation:these Greek letters for formulas:And some capital Greek letters for sets of formulas:12 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.Pr

21、opositional logic(PL):syntaxPropositional formulas are built from propositional letters,connectives,like,and parentheses().E.g:How to give a precise definition of the(infinite)set ofpropositional formulas?13 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semantics

22、Logical consequence etc.PL:formulas 1We give an INDUCTIVE DEFINITION,like this:1 Propositional letters are formulas.2 If is a formula,then is a formula.3 If and are formulas,then(),(),(),and()are formulas.4 Nothing else is a formula.(We usually skip this clause.)Inductive definitions are used all th

23、e time in this course!14 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.PL:formulas 2We can write the same definition of formulas in a morecompact form:=p|()|()|()|()Here p belongs to a given set L of propositional letters(calleda

24、vocabulary),usually taken from p0,p1,p2,.When it is important to specify L,we also call formulasL-formulas.15 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.PL syntax:parentheses and conventions16 of 34Practical mattersContentNotat

25、ionPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.Inductive definitionsInductive definitions allow you to prove true claims about aninfinite set of objects(formulas,numbers,.)in a finite way.To prove that all formulas have a property P,show this:(base)ISentential lett

26、ers(atomic formulas)are P.(ind.steps)IIf is P,then is also P.IIf and are P,then()is also P.ISimilarly for()and().You have then proved five facts,from which an infinitenumber of(non-trivial)facts follow!We will see many examples in this course.17 of 34Practical mattersContentNotationPropositional log

27、ic:syntaxPropositional logic:semanticsLogical consequence etc.PL-semantics:truth tablesYou know how to evaluate PL-formulas with truth tables.True=T=1False=F=0The truth tables say what the connectives mean.18 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semantic

28、sLogical consequence etc.PL-semantics:valuationsAn interpretation,or valuation,maps propositional letters totruth values.More precisely:if L is a vocabulary,an L-valuation is afunction V from L to 0,1.By means of the truth tables,given a valuation V,everyL-formula gets a unique truth value.We can wr

29、ite this more systematically as an(inductive!)truthdefinition;i.e.a definition of the relationV|=(is true in V,or V()=1)for any(L-)valuation V and any(L-)formula.19 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.PL-semantics:truth

31、emma 2.1.6)20 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.Logical consequence:the ideaLogic is about consequence:a relation among sentences.In PL,a sentence and a formula is the same thing:true orfalse under an interpretation.Le

32、t be a sentence and a set of sentences.With the relation true in at our hands,we can give a precisedefinition of the intuitive idea that (the conclusion)followsfrom(the premises in)if it holds that:IWhenever all the sentences in are true,must be true.This is the semantic notion of consequence.The im

33、portant word is“must”.21 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.Logical consequence in PLLet be a PL-sentence and a set of PL-sentences(in somevocabulary).Definition(PL-consequence)is a logical consequence of,in symbols|=if

34、 no interpretation that makes all sentences in true also makes false.NB Same symbol|=,different meaning!We can write the definition more compactly as:|=ifffor all V,V|=implies V|=22 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.Re

35、lated notions is logically true(in PL,a tautology),in symbols|=,if is contradictory if and are logically equivalent,in symbols ,if is satisfiable,if23 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.Useful equivalencesThere are a nu

36、mber of logical equivalences in PL one needs toknow about:(11)in Ch.2)Ide Morgans lawsIdouble negationIexcluded middleIdefinitions of,in terms of other connectivesIdistributive laws24 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.

37、Useful to know:normal formsWith these equivalences,each PL-formula can be written in:negation normal form(nnf):only,occur,and occursonly in front of atoms;disjunctive normal form(dnf)(if p1,.,pnoccur in):adisjunction 1.k,where each iis a conjunctionp1.pn,where each piis either pior pi.(Exercise2.3.7

38、)conjunctive normal form(cnf):as in dnf with and switched.25 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.Useful to know:truth functionsAn n-ary truth function is a function f from 0,1nto 0,1.There are 4 1-ary truth functions(den

39、otes one of these),162-ary truth functions(,denote three of these),etc.Every n-ary truth function can be expressed by a PL-formulain the atoms p1,.,pn.(Exercise 2.3.5)(That is,PL is truthfunctionally complete.)26 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:sema

40、nticsLogical consequence etc.A proof by inductionLet p indicate that may have some occurrences of p,andlet result from replacing these occurrences by.(So if has no occurrences of p,then =.)Also,if V is a valuation,let V()be the value of under V,i.e.V()=1 if V|=,and V()=0 if V 6|=.TheoremIf V()=V(0),

41、then V()=V(0).Corollary(Lemma 2.1.8)If 0,then 0.(Exercise 2.3.4 indicates another proof of this lemma.)27 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.If V()=V(0),then V()=V(0).Proof.Induction on.Case 1:(base)is an atom.This is c

42、lear if this atom is not p.(Why?)If is p,we have:V(p)=V()=V(0)(assumption)=V(p0)Case 2:(ind.step)is.NB()=Calculate:28 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.If V()=V(0),then V()=V(0).Proof.Continued.Case 3:(ind.step)is 1 2.

43、NB(1 2)=1 2.(Thisis why we didnt require that p necessarily occurs in.)29 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.30 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequ

44、ence etc.31 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.32 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.33 of 34Practical mattersContentNotationPropositional logic:syntaxPropositional logic:semanticsLogical consequence etc.34 of 34

展开阅读全文