课程名称︰计算逻辑简介
课程性质︰资工选修
课程教师︰王柏尧
开课学院：电资
开课系所︰资工
考试日期（年月日）︰2019/11/13
考试时限（分钟）：09:10~12:10
试题 :(open book)
(x |- y means y is provable from x.)
(x |= y means x semantically entails y.)
Introduction to Computational Logic
Midterm
1. In the class, we have used ﹁﹁e to derive RAA and LEM.
(a) Please show ﹁﹁φ |- φ is valid using RAA and the baisc
proof rules except ﹁﹁e. (10%)
(b) Please show ﹁﹁φ |- φ is valid using LEM and the basic
proof rules except ﹁﹁e. (10%)
2. For each n>0, define the formula
n i-1
φn = ︿ (Ai ﹀ ﹀ ﹁Aj).
i=1 j=1
(a) Write down φ3. (5%)
(b) Is φn in conjunctive normal form for every n? (5%)
(c) Is φn satisfiable for every n? (10%)
3. Show the following sequents are valid using the basic
natural deduction prrof rules:
(a) ∀xφ︿∀xψ |- ∀x(φ︿ψ). (10%)
(b) ∃x(φ﹀ψ) |- ∃xφ﹀∃xψ. (10%)
4. Is there a predicate logic sentence φ without function nor
predicate symbols such that
for any model M, M |= φ iff the size of universe of M is even?
Why? (20%)
5. Show a second-order logic sentence ψ such that
for any finite model M, M |= ψ iff the size of universe
of M is even. (20%)