課程名稱︰離散數學
課程性質︰電機系複選必修
課程教師︰陳和麟
開課學院：電機資訊學院
開課系所︰電機工程學系
考試日期（年月日）︰2018/04/20
考試時限（分鐘）：110
試題 :
Please answer the following questions on the answer sheets provided. Be sure to
write your name and student ID on all the answer sheets you use. You may use
one A4-sized, hand-written, double-sided note and the logic tables on the class
website. No other books and notes may be used during the exam.
If tyou want to use any result or theorem that has been taught in class (
including homeworks), you may do so but you must state the result or theorem
clearly before using it.
Please read all the problems first. No questions allowed after 13:50.
Problem 1 (10%) Consider the following argument:
Premises:
"∀x(P(x) V Q(x))"
"∃x[P(x) → R(x)]"
Conclusion:
"∀x(Q(x) V R(x))"
The following is an incorrect proof of the validity of the argument. Identify
THREE mistakes in the following proof. Briefly explain your answer.
1 ∀x(P(x) V Q(x)) Premise
2 P(c) V Q(c) Universal Instantiation 1
3 ∃x[P(x) → R(x)] Premise
4 P(c) → R(c) Existential Instantiation 3
5 R(c) V Q(c) Modus Ponens 2,4
6 ∀x(R(x) V Q(x)) Universal Generalization 5
Problem 2 (10%) Let P(x) denote x lives in Taipei, Q(x) denote x lives within
100 kilometers to the ocean, and R(x) denote x has never eaten seafood. Prove
validity of the following arguement. You must strictly follow the format
taught in class.
Premise:
"Every person who lives i Taipei lives within 100 kilometers to the ocean."
"Some people who live in Taipei have never eaten seafood."
Conclusion:
"Some people live within 100 kilometers to the ocean but have never eaten
seafood."
Problem 3 (10%)
1. Prove that ￢(p Ｖ q) Λ (r Ｖ s)) ≡ (￢s Λ ￢r) Ｖ (￢p Λ ￢q). You
must strictly follow the format taught in class.
2. Prove that ~((A ∪ B) ∩ (C ∪ D)) = (~D ∩ ~C) ∪ (~A ∩ ~B) for any four
sets A, B, C, D.
Problem 4 (20%)
1. Let S1 ne the set of non-decreasing functions from N to {0,1,2}. In other
words, S1 = {f: N → {0,1,2} | f(i) ≦ f(i+1), ∀i}. Is S1 finite? Is S1
countable? Prove your answer.
2. Let S2 be the set of non-decreasing functions from N to N. In other words,
S2 = {f: N → N | f(i) ≦ f(i+1), ∀i}. Is S2 finite? Is S2 countable? Prove
your answer.
Problem 5 (30%) Let f(n), g(n), h(n) be positive functions. Prove the
following three statements or give counter ecamples. You may only use the
definitions of asymptotic notations. any other properties must be proved
before using.
1. n log2 n ∈ O(n).
2. If f(n) ∈ Ω(g(n)), then [f(n)]^2 ∈ Ω(g(n)).
3. Let f1(n), f2(n), ..., fk(n) be k functions. k is a constant. fi(n) = O(n)
for all i. If g(n) = Σ^{k}_{j=1}fj(n), then g(n) = O(n).
Problem 6 (10%)
1. Find the smallest x ∈ N such that
x ≡ 3 (mod 5)
x ≡ 4 (mod 7)
2. Compute 23^4817 mod 35. (Show your derivations)
Problem 7 (10%) For any prime p, is it always true that [(p-1)!]^2 ≡ 1 (mod p)
? Prove your answer. (hint: for any a, there exists an a' such that aa' ≡ 1 (
mod p).)