課程名稱︰離散數學 課程性質︰必修 課程教師︰顏嗣鈞 開課學院：電資學院 開課系所︰電機系 考試日期（年月日）︰2008/04/21 考試時限（分鐘）：120分鐘 是否需發放獎勵金：是 （如未明確表示，則不予發放） 試題： （以下邏輯語句，以'V'表示'or'、'^'表示'and'、'~'表示'negation'，與這門課使用 的符號略有不同，此外，以下以A代表for any，以E代表there exist。） 1. (15 pts) True or false? No explanations needed. Score= {Right-1/2Wrong}; so do not make uninformed guesses. (Please mark O for 'true' and X for 'false'.) (a) ExAyP(x,y)→AyExP(x,y) is a valid formula. (b) The sentence 'Today is Thursday.' is a proposition. (c) P(d)^(~Ex(R(x)^~Q(x)))‧(~Ex(Q(x)^P(x)))├ ~R(d). (d) (p_1→q_1)^(p_2→q_2)├ (p_1 V p_2→q_1 V q_2) can be proven using Natural Deduction of propositional logic. (e) (~q^(~p→q))→~p is a tautology. (f) AxP(x) V AyQ(y) and Ax(P(x) V Q(x)) are logically equivalent. (g) ExEyP(x,y) and EyExP(x,y) are logically equivalent. (h) ExAyEzP(x,y,z) and EzAyExP(x,y,z) are logically equivalent. (i) A formula ψ in propositional logic is satisfiable if ψ always evaluates to True for every truth assignment. (j) There exists a set A such that A is a subset of 2^A. (Note: 2^A, the power set of A, ={B| B is a subset of A}) (k) If A is countably infinite, so is 2^A (l) Every infinite set contains a countably infinite subset. (m) {ψ, {{a}}} is the power set of some set. (n) If A is countably infinite and B is an arbitrary set, then A∩B is either finite of countably infinite. (o) The union of infinitely many countably infinite sets is countably infinite. 2. (10 pts) Use the following predicates D(x): x is a dog C(x): x is a dog catcher T(x): x is a town L(x,y), x lives in y B(x,y), x has bitten y to obtain a first-order formula corresponding to the following: At least one town has a dog catcher who has been bitten by none of the dogs in town. 3. (10 pts) Write a propositional formula to express the following statement: If Clifton does not live in France, then he does not speak French. Clifton does not drive a Datsun. If Clifton lives in France, then he rides a bicycle. Either Clifton speaks French, or he drives a Datsun. Hence, Clifton rides a bicycle. (Note: you need to identify the propositions first.) 4. (10 pts) Prove that for an arbitrary infinite set A, there is no one-to-one correspondence between A and 2^A. (Hint: proof by contradiction. Assuming f to be such a one-to-one correspondence, define S={x| x belongs to A ^x does not belong to f(x)}…) 5. (10 pts) Prove formally that if for any i≧1, A_i is countably infinite, then ∪A_i=A_1∪A_2∪…∪A_i∪... i≧1 is also countably infinite. 6. (15 pts) Prove that the following program is totally correct. (Do not forget to show that the program always terminates.) (Hint: For partial correctness, use loop invariant { z=x(y-n+1)‧n≧1 }.) {y>0} z:=x; n:=y; while n>1 do begin z:=z+x; n:=n-1; end {z=x*y} 7. (15 pts) Calculate (in detail) the following weakest preconditions (WPs): (Recall that WP(S,{Q}) represents the "weakest condition" P such that P{S}Q.) (a) WP(if x<0 then x:=x+2 else y:=x+3, {x>0^y<0}). (b) WP(if odd(x) then x:=x+1, {x=10}). (odd(x) means x is an odd number.) (c) WP(if y<0 then x:=y-v, {x=y-v^y>0}) 8. (15 pts) Answer the following two questions: (a) (7 pts) Use the truth table method to prove ((p→r)^(q→r))╞ ((p V q)→ r) (b) (8 pts) Use natural deduction (see the following table) to prove ((p→r)^(q→r))├ ((p V q)→r). --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.133.169.66 ※ 編輯: boggart0803 來自: 220.133.169.66 (06/18 10:44) ※ 編輯: boggart0803 來自: 220.133.169.66 (06/18 10:45)