个人整理精品文档，仅供个人学习使用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!...
