面向计算机科学的数理逻辑

贵州大学计算机科学与技术学院硕士研究生

2014-2015学年第一学期考试试卷

《面向计算机科学的数理逻辑》

注意事项：

1. 请考生按要求在试卷上写姓名、学号、年级和专业。

2. 请仔细阅读各种题目的回答要求, 不要在试卷上乱写乱画。 3. 满分100分，考试时间为180分钟。

学号_______________ 姓名________________专业__________________分数 _________

1、将下列命题翻译成公式（用原子公式表示简单命题）。（每小题5分，共15分） (1) 谦虚使人进步，骄傲使人落后. (2) 三角形的任何两边之和大于第三边.

(3) 任何有性质“所有小于它的自然数都是素数”而又不是素数的自然数都是素数.

2、由(Ref),(+),(→+)和下面的：

?A??B,B，则???A. （1）如果???证明(??) （15分）

3、令?1,?2是两个一阶公式集，且它们没有公共的模型。证明存在一个公式A使得 ?1|?A且?2|??A。（15分）

4、判断\y(F(x)?G(x))与xF(x)?（15分） xG(x)是否互为逻辑推论，并给出证明。

5、分别构作满足如下条件的语句A（可以使用相等符号）。(10分) A在论域D中是可满足的，当且仅当D有两个个体或三个个体.

6、计算公式?x?y(?zF(x,y,z)??zG(x,y,f(z))) 的无存在前束范式和其Herbrand域。（15分）

７、结合自己的研究方向或领域，举例说明自己对数理逻辑的理解。（15分）