課程名稱︰邏輯
課程性質︰通識A4
課程教師︰傅皓政
開課學院：
開課系所︰
考試日期（年月日）︰2016.11.07
考試時限（分鐘）：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-formed ones.)
　　(a) P → ┐Q → R
　　(b) ┐┐H┐
　　(c) ┐┐A Λ B
　　(d) (L Ｖ M Λ N) → (M Ｖ M)
　　(e) (┐G Λ D) Ｖ (D ←→ ┐G Ｖ D)
　　(f) H ; ┐M ←→ N
　　(g) (D ←→ (E Λ ┐F)) ←→ E
　　(h) (K → ┐L) Λ (M ←→ L)) Λ ┐K
　　(i) A Λ (C → ┐B)
　　(j) →HK
三、請判斷下列陳述的真假，並且分別以Ｔ與Ｆ代表「真」與「假」。(10%)
　　(Please judge the following statements which are true or false. Notice,
　　please use the symbols "T" and "F" which stand for true and false
　　statements respectively.)
　　1. 有效論證的前提中至少必須有一個是實際上為真。
　　2. 前提與結論一致的論證一定是有效論證。
　　3. 前提與結論實際上為假的論證一定是無效論證。
　　4. 前提實際上為真而且結論實際上為假的論證可能是有效論證。
　　5. 結論為恆真句的論證可能是無效論證。
　　6. 前提與結論一致的論證可能是無效論證。
　　7. 前提與結論都是偶真句的論證可能是有效論證。
　　8. 結論是矛盾句的論證一定是無效論證。
　　9. 前提與結論不一致的論證一定是有效論證。
　　10. 前提實際上為假而且結論實際上為真的論證一定是有效論證。
四、請判斷下列句式哪些是恆真句、矛盾句或者是偶真句。你可以使用任何學過的方法，
　　包括真值表法、簡易真值表法或真值樹法，必須列出演算過程。(15%)
　　(Using some method (e.g. truth table, short-cut or tableaux system) shows
　　that each of the following formulae is tautology, contradiction, or
　　indeterminate formula. Computational process is required.)
　　(a) A → ((B Λ A) → B)
　　(b) (H → G) → (G → H)
　　(c) ┐((P → (Q → R)) → ((P → Q) → (P → R)))
五、請判斷下列各題中的兩個句式之間是蘊涵或是等值關係。如果是蘊涵關係，以φ╞ψ
　　表示；若為等值關係，則以╞φ←→ψ表示，必須列出演算過程。(15%)
　　(Using some methods 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. Computational process is required.)
　　(a) (L → M) → N ; (M → L) → N
　　(b) P Λ (Q Ｖ R) ; (P Λ Q) Ｖ (P Λ R)
　　(c) ((B Λ C) → D) Ｖ (C → ┐D) ; B → D
六、請寫出等值於真值表中語句φ的ＤＮＦ及ＣＮＦ。(10%)
　　(Find out the DNF and CNF each which is equivalent to the following
　　formulae φ.)
　　(a)　　　　　　　　　　　　(b)
　　┌─┬─┬─┬─┐　　　　　┌─┬─┬─┬─┐
　　│Ｐ│Ｑ│Ｒ│φ│　　　　　│Ｐ│Ｑ│Ｒ│φ│
　　├─┼─┼─┼─┤　　　　　├─┼─┼─┼─┤
　　│Ｔ│Ｔ│Ｔ│Ｔ│　　　　　│Ｔ│Ｔ│Ｔ│Ｆ│
　　├─┼─┼─┼─┤　　　　　├─┼─┼─┼─┤
　　│Ｔ│Ｔ│Ｆ│Ｆ│　　　　　│Ｔ│Ｔ│Ｆ│Ｔ│
　　├─┼─┼─┼─┤　　　　　├─┼─┼─┼─┤
　　│Ｔ│Ｆ│Ｔ│Ｔ│　　　　　│Ｔ│Ｆ│Ｔ│Ｆ│
　　├─┼─┼─┼─┤　　　　　├─┼─┼─┼─┤
　　│Ｔ│Ｆ│Ｆ│Ｔ│　　　　　│Ｔ│Ｆ│Ｆ│Ｔ│
　　├─┼─┼─┼─┤　　　　　├─┼─┼─┼─┤
　　│Ｆ│Ｔ│Ｔ│Ｔ│　　　　　│Ｆ│Ｔ│Ｔ│Ｆ│
　　├─┼─┼─┼─┤　　　　　├─┼─┼─┼─┤
　　│Ｆ│Ｔ│Ｆ│Ｔ│　　　　　│Ｆ│Ｔ│Ｆ│Ｆ│
　　├─┼─┼─┼─┤　　　　　├─┼─┼─┼─┤
　　│Ｆ│Ｆ│Ｔ│Ｔ│　　　　　│Ｆ│Ｆ│Ｔ│Ｔ│
　　├─┼─┼─┼─┤　　　　　├─┼─┼─┼─┤
　　│Ｆ│Ｆ│Ｆ│Ｆ│　　　　　│Ｆ│Ｆ│Ｆ│Ｔ│
　　└─┴─┴─┴─┘　　　　　└─┴─┴─┴─┘
七、請以真值樹法證明下列語法序列是否為有效論證，若為無效論證請顯示其反例結構。
　　(20%)
　　(Please use tableaux system to prove whether each of the following
　　argument is valid. And specify a counterexample if it is invalid.)
　　(a) P → (┐Q Ｖ R) ; Q ├ P → R
　　(b) ┐(K Λ L) → M, K Ｖ ┐K ├ ┐(K Ｖ ┐L)
八、當我們談到「不可能」這個語詞時，其實有不同的意義，請說明「現實上不可能」、
　　「物理上不可能」和「邏輯上不可能」有何不同？。(10%)
　　(Please explicate the difference among three kinds of "impossibility"
　　which are actually impossible, physical impossible and logically
　　impossible respectively.)