课程名称︰离散数学
课程性质︰电机系复选必修
课程教师︰陈和麟
开课学院：电机资讯学院
开课系所︰电机工程学系
考试日期（年月日）︰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).)