计算机科学中使用的数理逻辑_期末考试题2006到2014.pdf

2006 年 秋 季 研究生课程《计算机科学中使用的数理逻辑》试卷 任课教师 刘西洋 考试时间： 1 月24 日上午8：30 －10：30 地点：西406 、407 、408 、409 、410 、411 （自然语言到谓词逻辑的翻译10 分） 1、(逻辑公式的结构 20 分) （1）给出命题逻辑公式 ( ( ( p ) ↔ (q r)) → (r p) ) 的语法树（10 分） （2 ）给出一阶谓词逻辑公式x ( F(b) → y(z G(y, z) H(u, x, y) ) ) 的语法树 （10 分） 2 （量词20 分） 基于全称量词、存在量词 以及 等词=或，定义以下扩展的量词： （1）存在至少2 个 （8 分） （2 ）存在至多2 个 （7 分） （3 ）存在恰好3 个 （5 分） 3 （有限论域上一阶谓词逻辑到命题逻辑的翻译20 分） 4 5 （《面向计算机科学的数理逻辑》引理4.4.1 结论 (i) 20 分） 6 (OBDD OBDD 论文 10 分)   → ↔    1 2007 年 秋 季 研究生课程《计算机科学中使用的数理逻辑》试卷 任课教师：刘西洋 考试时间：2 小时 地点：西大楼 班级： 学号： 姓名： 1、逻辑公式的结构（20 分) （1）给出命题逻辑公式 ( ( (¬p ) ↔ (q ⋁ r)) → (r ⋀ p) ) 的语法树（10 分） （2 ）给出一阶谓词逻辑公式∀x ( F(b) → ∃y(∀z G(y, z) ⋁ H(u, x, y) ) ) 的语法树（10 分） 2 、证明（20 分） （1）（A→B ）⋁ （A→C ）⊭A→(B⋀C) （10 分） （2 ）A→(B⋁C) ⊭ （A→B ）⋀ （A→C ） （10 分） 3、根据命题逻辑的形式推演证明下述定理（20 分） （1）¬¬A ⊢A （10 分） （2 ）A ⊢¬¬A （10 分） 4 、由（Ref ），（+ ），（→ + ）和下面的： 如果∑ ⊢¬¬A ，则∑ ⊢A. 证明（¬ − ）. （10 分） 其中：（Ref ） A ⊢A （+ ） 如果∑ ⊢A ，则∑ ，∑’ ⊢A. （→ + ）如果∑, A ⊢B,则∑ ⊢A→B. 5、语句集 { ∀x ∃yF(x,y), ∀x¬F(x,x), ∀x∀y∀z[F(x,y) ⋀ F(y,z) → F(x,z)] } 在无限论域中是可满足的，但在有限论域中是不可满足的。（10 分） p 6、设A ∈Form （ℒ ）含不同的原子公式p ,…,p , v 是真假赋值。对于i=1，…,n, 1 n  v p 如果p 1  i i 令 Ai  p 否则   i 证明： v （1）A =1⇒A ,…,A ⊢A 1 n v （2 ）A =0⇒A ,…,A ⊢¬A 1