101成大資工離散[參考解答]

一、單選題

1. (5%) For an alphabet $\Sigma,$ let $A, \, B, \, C \subseteq \Sigma^*.$ Which statement is FALSE?

(A) $(AB)C = A(BC)$
(B) $AB \cup AC = A(B \cup C)$
(C) $AB \cap AC \subseteq A(B \cap C)$
(D) $(A \cup B)^* = (A^* B^*)^*$
(E) $A^* A^* = A^*$

參考解答：C

---

2. (5%) Which statement is FALSE?

(A) If $A = \{1, \, 2, \, 3, \,…, \, 10\},$ the number of functions $f: A \rightarrow A$ satisfy $f^1 (\{1, \, 2, \, 3\}) = \varnothing, \, f^1 (\{4, \, 5\}) = \{1, \, 3, \, 7\},$ and $f^1 (\{8, \, 10\}) = \{8, \, 10\}$ is 7776.
(B) The number of nonnegative integer solutions of $x_1 + x_2 + x_3 + … + x_7 = 37$ and $x_1 + x_2 + x_3 = 6$ where $x_1, \, x_2, \, x_3 > 0$ is $10 \times \binom{34}{31}.$
(C) The coefficient of $x^5$ in $f(x) = (1-2x)^{-7}$ is $32 \times \binom{11}{5}.$
(D) The coefficient of $x^2yz^2$ in the expansion of $[(x/2) + y – 3z]^5$ is $\dfrac{145}{2}.$

參考解答：D

---

3. (5%) Which statement is TRUE?

(A) Let $(A, \, R)$ be a poset. If $(A, \, R)$ is a lattice, then it is a total order.
(B) If $A = \{1, \, 2, \, 3, \, 4, \, 5, \, 6, \, 7\}$ and the relation $R$ is defined as if $(x, \, y) \in R, \, x-y$ is a multiple of 3, then $R$ is an equivalent relation on $A.$
(C) The subset relation is a total ordered relation.
(D) If $(A, \, R)$ is a poset and $B \subseteq A,$ then $B$ has more than one lub.

參考解答：B

---

4. (5%) Define the connective “Nand” by $(p \uparrow q) \iff \neg (p \wedge q),$ for any statements $p, \, q.$ Which statement is FALSE?

(A) $\neg p \iff (p \uparrow p).$
(B) $(p \vee q) \iff (p \uparrow p) \uparrow (q \uparrow q).$
(C) $(p \wedge q) \iff (p \uparrow q) \uparrow (p \uparrow q).$
(D) $p \rightarrow q \iff p \uparrow (p \uparrow q).$

參考解答：題目有問題

---

5. (5%) Let $f: X \rightarrow Y$ and $g: Y \rightarrow Z$ be functions. Which statement is FALSE?

(A) If $g \circ f$ is one-to-one, $f$ is one-to-one.
(B) If $g \circ f$ is one-to-one, $g$ is one-to-one.
(C) If $g \circ f$ is onto, $g$ is onto.
(D) If $g \circ f$ is bijection, $g$ is onto.
(E) If $g \circ f$ is bijection, $f$ is one-to-one.

參考解答：B

---

二、計算題

1. (15%) Use the recurrence relation to determine the number of n-digit quaternary $(0, \, 1, \, 2, \, 3)$ sequences in which there is never a ‘0’ anywhere to the right of a ‘3’.

參考解答：
$a_n = 3a_{n-1} + 3^{n-1}, n \geq 2. \\ a_1 = 4.$

---

2. (10%) Let $A = \{1, \, 2, \, 3, \, 4, \, 5\}$ and $B = \{u, \, v, \, w, \, x, \, y\}.$ Determine the number of one-to-one functions $f:A \rightarrow B$ where $f(1) \neq v, \, w, \, f(2) \neq u, \, w, \, f(3) \neq x, \, y$ and $f(4) \neq v, \, x, \, y.$

參考解答：$5! – 9(4!) + 26(3!) – 27(2!) + 8(1!)$

---

試題(pdf)：連結

有任何問題，或想要完整解釋的，歡迎在下方留言唷！