个人整理精品文档,仅供个人学习使用1/11程序设计理论各年试卷参考答案林祺颖试卷预测(这些为本人意见,仅供参考):题目前有为考试必考内容,即类似的题目一定会出,一定要灵活掌握。题目前没有符号的为可能考内容,一定要知道怎样做。题目前有*符号的为基本不考内容,浏览一下即可。答案参考(如有任何补充或者感觉不对的地方,一定要向我提出来噢):黑色的为个人感觉没有问题的部分,如果发现有错误,那一定要跟我说。红色的为个人感觉可以修改或者不确定,甚至不太会做的部分,大家一起讨论。绿色的为提示或者需要注意的部分。联系方式:在群上找林祺颖,或者加:,我基本都在。下面有些符号为了录入方便,都作了一些替代,标准符号可要看书。如ω用代替。程序设计理论试卷年月日该卷答案基本是一个师兄做的,红色为我补充的部分.((),),({},)解释:()为自然数集合的集合。即的。取第个集合为,第个集合为{},。。。,第个集合为{},则可以产生一个(无穷递降序列),所以((),)不是.设{},若(,)不是,则必然存在一个,设为,⋯⋯,则1⋯⋯,从而>>⋯>⋯.,因为属于(>),即是一个有限集,所以是一个有限的自然数,不能形成一个无限下降的序列,矛盾,所以(,)是..,∨.证明与∨逻辑等价,即是要证明∨.对于任意的,(∨)(σ)等价于()(σ)()(σ)()(σ)∨()(σ),因为:∑,所以()(σ)或者()(σ),()(σ)或者()(σ)。若()(σ),()(σ),则(∨)(σ)(∨);其余三种情况类似地也有(∨)(σ)=.所以∨,从而与∨逻辑等价。*..():Bool.这题不会写。师兄也没给出答案。^^题目意思是,对于一个只有操作的语言逻辑表达式,建立起抽象机,并且给出对于给定的表达式,给出对应的():Bool的定义.(,mBoolBool).??这是一个定义在由ω映射到ω的函数的偏序集。并且是具有<关系,所以某些映射是不能成立的,如{(ω),(,ω)..}ωmω共有个元素,用(<<)表示如下:个人整理精品文档,仅供个人学习使用2/11:{(ω,ω),(,ω),(,ω)}:{(ω,ω),(,ω),()}:{(ω,ω),(,ω),()}:{(ω,ω),(),(,ω)}:{(ω,ω),(),()}:{(ω,ω),(),()}:{(ω,ω),(),(,ω)}:{(ω,ω),(),()}:{(ω,ω),(),()}:{(ω),(),()}:{(ω),(),()}共有个极大元。.:()()*().()().()函数程序计算序列:()>(*())>(*())(),()>*()(*(),*())>*(*())>*(*())(),()>*(*())(*(),*())>*(*)(())>(*(*))()对应逻辑程序如下:().()()*目标是()这里要注意,最后会出现不为空的情况(即不是),有一种理解是具有默认的式子:.另一种是需要加式子()逻辑程序的:θ()()()*{}>()*()()*{}>()**(){}>**>,>再根据和替换(),可以归到□。个人整理精品文档,仅供个人学习使用3/11.Φ.?假设在()下,定义函数程序为:()<()则指称语义函数Φ:[ωω][ωω],定义为Φ()[λ.[λ()]]下面证明Φ是恒等函数,即对于任意的,都有Φ().在下,对于任意的∈[ωω],和任意的∈ω,都有Φ()()([λ.[λ()]])(γ[][]),即Φ()()ω,ω;()≠ω;所以对于任意的∈ω,如果ω,则Φ()()=ω=(),如果≠ω,也同样有Φ()()=(),所以Φ(),即Φ是恒等函数.(α),α.这题首先必须要加入这个:就是指对于输入,()()(()(σ))((α))()然后下面的内容是和的定义,不是该题的重点,是否写上看情况吧。令是谓词逻辑的,是的两个公式,∈BL1是一个程序(,⋯)是程序中的一条路径,()根据的取值递归地定义()如下:如果,则定义();当>时,设β(,⋯),(β),根据处的语句类型,分成两种情况来定义().如果是平行的赋值语句,设形式如下所示::(,⋯)(,⋯);;则定义()tntxnxr,...,1,...,1;如果是条件转移语句,设形式如下所示::’;则定义()如下:如果且≠’如果≠且’()定义的验证条件()为().令为谓词逻辑的,为的两个公式,∈BL1是一个程序,对于任意的,程序在中,对于和是的,当且仅当如果对于中的任意一条路径,都有验证条件()在中为。“”.??,{}{},(){}whileedoSod{q}prreSrreqp∈,∈,∈.设为的集合个人整理精品文档,仅供个人学习使用4/11{{txp}{}∈∈,∈}{((,{∧}{},(∧)),{}{})∈∈∈BL2}推导出来的集合是里面的公式集的一个子集。推导过程:>{^}{}^>{}{^}{}{}个人整理精品文档,仅供个人学习使用5/11程序设计理论试卷(即老师的样题).1-in0,NatnNatnin!...