[試題] 108-1 王柏堯 計算邏輯簡介 期中考
課程名稱︰計算邏輯簡介
課程性質︰資工選修
課程教師︰王柏堯
開課學院：電資
開課系所︰資工
考試日期（年月日）︰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%)
--
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
◇──────────── ▕◤ ▊ ▊ ▋▋ ㄟ▁↘ \◥▊▍▎ ｜ ▎ ▏ ▍ ▎▍-◇
╱╲Ｇrand ╳ ▍▎ ▍ ▍ ║▌ ▲◥▃▅▃▼▎|▏]▊▏▍/ |▊ ▊▏ψ
╳ Ｆate╳╳ ⊙rder ╳ ▎ ▉▎▉▲ ▍▲ [`◥▄◥-▼▍▎▲▲∕▲｜ ▎▋▎
╳ ╲╱ ▔▔▔▔ 丿 ▎▋▏| ▊ ▍▋ ▎‵爫‵` 圳▋◤八↙/▎|/\▍▊║
吼え立てよ、我が憤怒！ ▍▊◤▉ ◣[ \ ▉㇏ ▼↗▄▆▄↙∕ ▼▋[▎
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.247.122 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/NTU-Exam/M.1573668364.A.B35.html
※ 編輯: isaswa (140.112.247.122 臺灣), 11/19/2019 01:13:57