FoundationsofLogic (9).pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《FoundationsofLogic (9).pdf》由会员分享,可在线阅读,更多相关《FoundationsofLogic (9).pdf(26页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、IntroBasic functionsCompositionPrimitive recursionPrime numbersSequence codingCourse-of-values recursionOnline Course:Foundations of LogicDag Westerst ahlTsinghua LogicIntroBasic functionsCompositionPrimitive recursionPrime numbersSequence codingCourse-of-values recursionCharacteristic functionsMost
2、 of our work on first-order logic and first-order theories result in setsand relations,like the set of axioms of some theory,or the relationbetween a derivation in H and the sentence it derives.Via G odel numbering,we get corresponding sets and relations betweennumbers,such as the set axTof G odel n
3、umbers of axioms in T,or therelation prfT.But when dealing with computability,its easiest to start with functions.We then get sets an relations for free,through their characteristicfunctions:if R is a k-ary relation,the characteristic function of R,calledcR,is defined by:cR(n1,.,nk)=?1if R(n1,.,nk)0
4、if not R(n1,.,nk)We then say that R is computable if cRis computable.1 of 25IntroBasic functionsCompositionPrimitive recursionPrime numbersSequence codingCourse-of-values recursionNotationChapter 8 is not about logic or formal theories.It is a piece of informal number theory:we will define the class
5、 ofprimitive recursive functions,and look at several examples of suchfunctions and relations.So we will use standard mathematical notation.It is the same as whatwe have used already in our metalanguage,except for one detail:we usex,y,z,x1,.as variables for arbitrary numbers,ratherk,m,n,n1,.as we did
6、 before.This is to follow a notation that is both convenient andstandard in(much of)the literature.2 of 25IntroBasic functionsCompositionPrimitive recursionPrime numbersSequence codingCourse-of-values recursionBasic functionsThe basic functions are the following:(1)the zero function Z:Z(x)=0 for all
7、 numbers xIn what follows we leave out“for all numbers x”.(2)the successor function s:s(x)=x+1(3)the identity functions idni,for n 1 and 1 i n:idni(x1,.,xn)=xi(also called projection functions).As you see,these are pretty trivial functions,and obviously computable.3 of 25IntroBasic functionsComposit
8、ionPrimitive recursionPrime numbersSequence codingCourse-of-values recursionComposition:exampleTo get more functions,we compose the ones we have.For example,suppose we already have the functionsf(x,y)=x+yg1(z)=z2g2(z)=2z+1Then we can compose f with g1and g2,which yields the functionh(z)=f(g1(z),g2(z
9、)=g1(z)+g2(z)=z2+2z+1This kind of operation is done all the time.It is clear that if we start withcomputable functions,composing them will give new computablefunctions.4 of 25IntroBasic functionsCompositionPrimitive recursionPrime numbersSequence codingCourse-of-values recursionComposition definedLe
10、t f an m-ary function and let g1,.,gmbe n-ary functions.We define the n-ary function h byh(x1,.,xn)=f(g1(x1,.,xn),.,gm(x1,.,xn)h is the composition of f with g1,.,gm.We also give an official name to h:h=Cnf,g1,.,gm5 of 25IntroBasic functionsCompositionPrimitive recursionPrime numbersSequence codingC
11、ourse-of-values recursionComposition in practiceFunction composition often doesnt look like in the preceding definition.The book gives the example:f(x,y,z)=x+y+zfrom which a composed 2-ary function h is defined by(2)h(x,y)=f(x,s(y),id22(x,y)=x+y+1+id22(x,y)=x+2y+1Page 167 shows how to rewrite this i
12、n the official format,using theidentity functions.In practice one never does this (2)is fine butits nice to know that it can be done.The official function description of h becomesh=Cnf,id21,Cnid22,id21,Cns,id22,id22This is never used in practice(it is quite unreadable!),but its good toknow that to e
13、ach way of(repeatedly)applying function composition togiven functions corresponds a unique function description.6 of 25IntroBasic functionsCompositionPrimitive recursionPrime numbersSequence codingCourse-of-values recursionPrimitive recursion:examplesWe come to a typical way of defining new number-t
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- FoundationsofLogic 9
![提示](https://www.taowenge.com/images/bang_tan.gif)
限制150内