課程名稱︰離散數學
課程性質︰必修
課程教師︰顏嗣鈞
開課學院：電資學院
開課系所︰電機系
考試日期（年月日）︰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)