課程名稱︰邏輯
課程性質︰通識A4
課程教師︰傅皓政
開課學院：
開課系所︰
考試日期（年月日）︰2015/04/27
考試時限（分鐘）：13:30~15:00(90分鐘)
試題 :
一、請建構適用的命題邏輯語言（提示：包括符號與形構規則兩個部分）。（10%）
　　(Construct a suitable language for propositional logic. Hint: two parts
involved, alphabets and formation rules)
二、請判斷下列句式那些是合宜的句式？哪些是不合宜的句式？（10%）
　　(Please consider the following formulae and distinguish the well-formed
formulae from ill-fromed ones.)
(a) (G^H)v(M→GvN) (b) (Bv┐(C^D)←→B (c) S^W→ (d) H←→G←→H
(e) ┐D (f) M^L,N (g) (P→Q^R←→R)^P (h) (A^B)→(B←→A)
(i) Kv┐M→L (j) (TvS)→P←→R
參考答案：合　宜：a.e.h.i
不合宜：b.c.d.f.g.j
三、請判斷下列陳述的真假，並且分別以Ｔ與Ｆ代表「真」與「假」。(10%)
(Please judge the following statements which are true or false.)
1. 前提與結論都實際上為真的論證可能是無效論證。
2. 有些無效論證的結論實際上為真。
3. 前提與結論不一致的論證可能是有效論證。
4. 前提不可能全部為真的論證可能是無效論證。
5. 有效論證的前提必定不可能全部同時為真。
6. 有效論證的結論可能是矛盾句。
7. 結論為恆真句的論證必定是有效論證。
8. 前提實際上為真而且結論實際上為假的論證可能是有效論證。
9. 前提實際上為假的論證必定是有效論證。
10. 前提一致的論證必定是有效論證。
參考答案：TTTFF,TTFFF
四、請用真值表法或簡易真值表法判斷下列句式哪些是恆真句、矛盾句或者是未定句。
注意，必須列出演算過程。（10%）
(Please use truth table or short-cut method to show whether the following
formulae are tautologies, contradictions, or indeterminate formulae.
Computational process is required.)
(a) (D→E)→D (b) (G^H)→(G←→H) (c) ┐(L^(MvN))←→((L^M)v(L^N))
(d) ┐A→(B^B) (e) (P^(QvR))←→((P^R)v(P^Q))
參考答案：(a)未定句　(b)恆真句　(c)矛盾句　(d)未定句　(e)恆真句
五、請以真值表法判斷下列各題中的兩個句式之間是蘊涵或是等值關係。如果是蘊涵
關係，以φ╞ψ表示；若為等值關係，則以╞φ←→ψ表示。注意，必須列出演
算過程。（20%）
(Please use truth-table method to determine the semantic relation
between the following formulae. If the entailment relation holds
then show them of the form φ╞ψ. On the other hand, show them of
the form ╞φ←→ψif they are equivalent. Computaional process is
required.)
(a) Dv┐D ; (┐D→┐E)→(E→D) (b) Mv(N→N) ; MvN
(c) (P^Q)v(Q^R) ; (┐P^┐Q)v(┐Q^┐R) (d) ┐(┐Av┐B) ; ┐B→A
參考答案：(a)等值　(b)蘊涵　(c)非等值非蘊涵　(d)等值
六、請寫出等值於真值表中語句φ的DNF及CNF。（10%）
　　(Find out the DNF and CNF each which is equivalent to the following
formulae φ.)
　　(a)┌─┬─┬─┬─┐
│Ｂ│Ｃ│Ｄ│φ│
├─┼─┼─┼─┤
│Ｔ│Ｔ│Ｔ│Ｔ│
├─┼─┼─┼─┤
│Ｔ│Ｔ│Ｆ│Ｆ│
├─┼─┼─┼─┤
│Ｔ│Ｆ│Ｔ│Ｔ│
├─┼─┼─┼─┤
│Ｔ│Ｆ│Ｆ│Ｆ│
├─┼─┼─┼─┤
│Ｆ│Ｔ│Ｔ│Ｔ│
├─┼─┼─┼─┤
│Ｆ│Ｔ│Ｆ│Ｔ│
├─┼─┼─┼─┤
│Ｆ│Ｆ│Ｔ│Ｆ│
├─┼─┼─┼─┤
│Ｆ│Ｆ│Ｆ│Ｔ│
└─┴─┴─┴─┘
　　(b)┌─┬─┬─┬─┐
│Ｐ│Ｑ│Ｒ│φ│
├─┼─┼─┼─┤
│Ｔ│Ｔ│Ｔ│Ｆ│
├─┼─┼─┼─┤
│Ｔ│Ｔ│Ｆ│Ｆ│
├─┼─┼─┼─┤
│Ｔ│Ｆ│Ｔ│Ｆ│
├─┼─┼─┼─┤
│Ｔ│Ｆ│Ｆ│Ｆ│
├─┼─┼─┼─┤
│Ｆ│Ｔ│Ｔ│Ｆ│
├─┼─┼─┼─┤
│Ｆ│Ｔ│Ｆ│Ｆ│
├─┼─┼─┼─┤
│Ｆ│Ｆ│Ｔ│Ｆ│
├─┼─┼─┼─┤
│Ｆ│Ｆ│Ｆ│Ｆ│
└─┴─┴─┴─┘
參考答案：(a) DNF：(B^C^D)v(B^┐C^D)v(┐B^C^D)v(┐B^C^┐D)v(┐B^┐C^┐D)
　　　　　　　CNF：(┐Bv┐CvD)^(┐BvCvD)^(BvCv┐D)
　　　　　(b) DNF：沒有DNF
　　　　　　　CNF：(┐Pv┐Qv┐R)^(┐Pv┐QvR)^(┐PvQv┐R)^(┐PvQvR)^
　　　　　　　　　 (Pv┐Qv┐R)^(Pv┐QvR)^(PvQv┐R)^(PvQvR)
七、請以真值樹法證明下列語法序列是否為有效論證，若為無效論證請顯示其反例
結構。（20%）
(Please use tableaux system to prove whether each of the following
argement is valid. And specify a counterexample if it is invalid.)
(a) K→L, M→N, ┐K^┐N ├ ┐M^┐L
(b) ┐C→D, ┐E→D, ┐D ├ (E^C)v(D^E)
參考答案：(a)有效論證　(b)有效論證
八、請說明為何我們需要一個形式語言來處理論證？(10%) (編按：老師說的驚喜題。)
(Please explain why we need a formal language to deal with the arguements?)
參考答案：因為日常語言具有(1)歧義　(2)含混性　(3)開放性。