課程名稱︰離散數學 課程性質︰電機系複選必修 課程教師︰陳和麟 開課學院：電機資訊學院 開課系所︰電機工程學系 考試日期（年月日）︰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).) --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.118.10 (臺灣) ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1562397041.A.685.html ※ 編輯: misomochi (1.162.118.10 臺灣), 07/06/2019 17:04:34