北京航空航天大学2000编译原理年考研试题研究生入学考试试题考研真题
● 摘要
北京航空航天大学数理逻辑与编译原理试题
(2000年)
一、(4’x2)在谓词逻辑中将下列命题符号化。
1. 如果一个人只说谎话，那么他说的话没一句可信的。
2. 每个人都有唯一的身份证号码。
二、(8’)甲、乙、丙三人报考王教授的研究生。考试后王教授谈了录取情况如下：
(1) 三人中只录取一人；
(2) 如果不录取甲，就录取乙；
(3) 如果不录取丙，就录取甲。
用命题逻辑确定王教授到底录取谁为他的研究生。
三、(8’)定义二元连接词△为p △q ⇔ ¬ (p →q ) 。
证明：{↔，△}是极小完全集。
四、(4’x2)判断以下逻辑推论关系是否成立，
1. ∀x ∀y (P (x ) ↔Q (y )) |=∀xP (x ) ↔∀xQ (x )
2. ∀xP (x ) ↔∀xQ (x ) |=∀x ∀y (P (x ) ↔Q (y ))
五、(8’)用归结法证明：有的职业是每个人都喜欢的。因此，每个人都有自己喜欢的职业。
六、填空题(18’，1-6题每空1’，7题每空0.5’)
1. 文法的形式定义为___________________________
语言的形式定义为___________________________。
2. 规范规约每次规约的是句型的______________。
3. 活动记录由___________、___________、___________三部分组成。
4. 表达式x +y ×z / (a +b ) 的后缀式为________________。
5. 错误的局部化处理是指_______________________________________。
6. 局部优化是指_______________________________________________； 循环优化是指_______________________________________________； 全局优化是指_______________________________________________。
7. 有文法R ::=i |(T ) ，T ::=T , R |R 完成其算符优化关系表。(填写第一二行)
i i
·> ·> ·> , <· <· ·> ·>
# <· <· ·=
七、判断题(1’x4)
1. 对任意一个右线性文法G ，都存在一个NF A M，满足L (G )=L (M ).( )
2. 对任意一个右线性文法G ，都存在一个DF A M，满足L (G )=L (M ).( )
3. 对任何正则表达式e ，都存在一个NF A M ，满足L (M )=L (e ).( )
4. 对任何正则表达式e ，都存在一个DF A M ，满足L (M )=L (e ).( )