課程名稱︰離散數學
課程性質︰
課程教師︰林永松
開課學院：管理學院
開課系所︰資管系
考試日期（年月日）︰2010/5/4
考試時限（分鐘）：180分鐘
是否需發放獎勵金：
（如未明確表示，則不予發放）
試題 :
Discrete Mathematics
Midterm Exam
1.In the questions below determine whether the proposition is TRUE or FALSE:
a)If it is raining, then it is raining.
b)If 1+1=2 or 1+1=3, then 2+2=3 and 2+2=4.
2.Write the TRUE TABLE for the proposition
-(r →-q) ﹀ (p ︿-r)
3.Prove that (q ︿ (p →-q))→-p is a TAUTOLOGY using proposition equivalence
the laws of logic.
4.On the island of knights and knaves you encounter two people A and B.
Person A says, " B is a knaves. "
Person B says, " At least one of us is a knight. "
Determine whether each person is a knight or a knave.
5.In the questions below P(m,n) means "m≦n", where the universe of discourse
for m and n is the set of nonnegative integers. What is the TRUE VALUE of
the statment?
a) *1 n P(0,n) (註*1 倒"A"符號 註*2 反"E"符號)
b) *2 n *1 m P(m,n)
c) *1 m *2 n P(m,n)
6.What is the rule of inference used in the following: If it snows today,
the university will be closed. The university will not be closed today.
Therefore, it did not snow today.
7.Determine whether the following argument is valid:
p → r
q → r
-(p﹀q)
─────
∴ -r
8.Prove or disprove: For all real number x, │x +│x││=│2x│
└ └ ┘┘ └ ┘
9.Prove that the following is true for all positive integers n:
" n is even if and only if 3n^2+8 is even. "
10.Prove that A∩(B∪C) = (A∩B)∪(A∩C) by giving a proof using logical
equivalence.
11.In the questions below suppose A={a,b,c}. Mark the statement TRUE or FALSE.
a) {b,c} *3 P(A) (註*3 屬於符號 註*4 子集符號)
b) {{a}} *4 P(A)
c) ψ *4 A
d) {ψ} *4 P(A)
e) ψ *4 A ×A
f) {a,c} *3 A
g) {a,b} *3 A ×A
h) (c,c) *3 A ×A
12.Prove that between every two rational number a/b and c/d
a) there is a rational number
b) there are an infinite number of rational number
13.Suppose f:R→R wherw f(x)=│x/2│.
└ ┘
a) Draw the graph of f
b) Is f 1-1 ?
c) Is f onto R ?
14.Suppose g:A→B and f:B→C where A={1,2,3,4}, B={a,b,c}, C={2,7,10}, and
f and g are defined by g={(1,b),(2,a),(3,a),(4,b)} and f={(a,10),(b,7),
(c,2)}.Find f^-1(反函數).
15.Find the sum 2－4＋8－16＋32－...－2^28.
16.Use the definition of big-oh to prove that 1^2＋2^2＋...＋n^2 is O(n^3)
3n－8－4n^3
17.Use the definition of big-oh to prove that ─────── is O(n^2)
2n－1
x^3＋7x^2＋3
18.Prove that ─────── is Θ(x^2)
2x＋1
19.Analyze the computational complexity of the insertion sorting algorithm
discussed in the class, where binary search instead of linear search is
applied.
20.Propose an efficient and effective heuristic algorithm to slove 0-1
knapsack problem discussed in the class.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.4.192