99年國立台灣大學電機所離散數學

Suppose the variable x represents students, F(x) means "x is a freshman", and M(x) means "x is a math major". What does the formula ¬∀x (¬F(x) ∨ ¬M(x)) mean:

Some freshmen are math majors

Every math major is a freshman.

No math major is a freshman.

Some freshmen are not math majors.

None of the above.

Which of the following statements is not correct?

Propositional formula (A ∧ B) ∨ (¬A) ∨ (¬B) is a tautology.

Propositional logic does not have a sound and complete deduction system.

First-order logic is more powerful than propositional logic.

"2 + 2 = 0" is a proposition.

Propositional formula p → (q → r) is satisfiable.

From the following four,
(1) (p → q) → r
(2) p → (q → r)
(3) q → (p → r)
(4) (q → p) → r
which are the two propositions that are logically equivalent?

1 and 2

1 and 3

2 and 3

2 and 4

None of the above

Using c for "it is cold", r for "it is rainy", and w for "it is windy", which of the following propositional formula means "It is rainy only if it is windy and cold" in symbols?

r → (w ∧ c)

¬r → (w ∨ ¬c)

(w ∧ c) → r

r ∧ (w ∧ c)

None of the above.

Let predicate P(m, n) mean "m ≤ n", where the universe of discourse for m and n is the set of nonnegative integers. Among the following four first-order formulas, how many of them are true? ∃n P(n, 0); ∀n P(0, n); ∃n ∀m P(m, n); ∀m ∃n P(m, n),

0

1

2

3

4

Consider the following five sets; N (the set of natural numbers), Z (the set of integers), Q (the set of rational numbers), R (the set of real numbers), and 2^N (the power set of N), how many of the above five sets are countably infinite?

0

1

2

3

4

Define predicate P(x, y) to be "x + 2y = xy", where x and y are integers. How many of the following four first-order formulas ∀x ∃y P(x, y), ∃x ∀y P(x, y), ∀y ∃x P(x, y), ∃y ∀x P(x, y) are "true"?

0

1

2

3

4

Let S = {∅, {∅, {∅}}}. What is 2^S (i.e., the power set of S)?

{(∅, ∅), (∅, {∅}), ({∅}, ∅), ({∅}, {∅})}

{∅, {∅}, {{∅}}, {∅, {∅}}}

{∅, {∅, {∅}}}

{∅, {∅}, {{∅}}}

None of the above.

Let S = {∅, {∅}}. What is the value of |S × {∅}|?

0

1

2

3

None of the above

Consider a binary relation S = {(a, c), (b, d), (d, a)}. What is S³?

{(a, a), (a, c), (b, c), (c, c), (d, b), (d, d)}

{(b, c)}

{(a, c), (b, a), (d, b), (d, d)}

{(a, a), (a, d), (d, c)}

None of the above.

Define a binary relation R(x, y) on the set of real numbers as: "x = y + 1 or x = y − 1". Consider the following four properties: reflexive, symmetric, anti-symmetric, and transitive. R(x, y) satisfies how many of the above four properties?

0

1

2

3

4

Suppose |A| = n. What is the number of symmetric binary relations on A?

2^n(n−1)/2

2^n(n+1)/2

2ⁿ

2ⁿ⁽ⁿ⁻¹⁾

None of the above.

Suppose |A| = n. What is the number of reflexive, symmetric binary relations on A.

2^n(n−1)/2

2^n(n+1)/2

2ⁿ

2ⁿ⁽ⁿ⁻¹

None of the above.

If R = {(1, 2), (1, 4), (2, 3), (3, 1), (4, 2)}, what is the size (i.e., the number of elements) of the symmetric closure of R?

8

9

10

11

None of the above.

The symmetric difference of two sets A and B (denoted by A ⊕ B) is the set of elements which are in A or B, but not in both. How many of the following four statements are correct?
−− {1, 3, 5} ⊕ {1, 2, 3} = {2, 5}
−− A ⊕ B = (A ∪ B) − (A ∩ B)
−− A ⊕ (B ⊕ C) = (A ⊕ B) ⊕ C
−− (A ⊕ B) ⊕ B = A

0

1

2

3

4

Consider f : N → Z where. Which of the following is correct?

f(n) is onto but not 1 − 1

f(n) is onto and 1 − 1

f(n) is 1 − 1 but not onto

f(n) is not onto and not 1 − 1

f(n) is not a function.

How many permutations of the seven letters A, B, C, D, E, F, G have A immediately to the left of E?

2 ⋅ 5!

6!

5 ⋅ 6!

7! − 2 ⋅ 6!

None of the above

How many one-to-one functions are there from a set with three elements to a set with eight elements?

512

336

128

270

None of the above

What is the largest coefficient in the expansion of (x + 1)⁶?

6

15

20

30

None of the above.

Suppose g : A → B and f : B → C where A = {1, 2, 3, 4}, B = {a, b, c}, C = {2, 8, 10}, and g and f are defined by g = {(1, b), (2, a), (3, b), (4, a)} and f = {(a, 8), (b, 10), (c, 2)}. What is f ë g?

{(2, c), (8, a), (10, b)}

{(2, 2), (8, 8), (10, 10)}

{(1, 10), (2, 8), (3, 10), (4, 8)}

{(1, 1), (2, 1), (3, 2), (4, 1)}

None of the above.

What is the value of 50! mod 49!?

0

1

25

48

None of the above.

What is the number of times that "hello" is printed after the following program is executed?

Θ(1)

Θ(n)

Θ(n²)

Θ(n log n)

None of the above.

Which of the following functions has the largest growth rate asymptotically?

0.1n^1.5 + 3n

(0.001)ⁿ

(log n)²

Consider a binary relation R on {1, 2, 3, 4} whose matrix representation is,For the following four properties: reflexive, symmetric, anti-symmetric, and transitive, R satisfies how many of them?

0

1

2

3

4

Given a partial order relation R with its Hasse diagram shown in Figure 1. What is lub({g, j, m})?

{l, m}

{m}

{l}

{g, j, m}

None of the above

Consider Figure 1 again. What is the set of least elements of R?

{a}

{a, b, c}

{c}

∅

None of the above.

Consider relation R in Figure 1 again. Which of the following is false?

aRa

eRm

R does not have a greatest element

R is a lattice

None of the above

The chromatic polynomial χ_G(k) of a graph G is the number of proper colorings of G with k colors. Consider graph G in Figure 2. What is χ_G(k)?

k(k − 1)(k − 2)(k − 3)

k⁴

k²(k − 1)²

k(k − 1)³

None of the above.

What is the number of positive integers not exceeding 100 (i.e., ≤ 100) that are not divisible by 5 or by 7?

65

66

67

68

None of the above

What is the transitive closure of R = {(1, 1), (2, 2), (3, 3), (2, 3), (3, 1)}?

{(1, 1), (2, 2), (3, 3), (2, 3), (3, 1)}

{(1, 1), (2, 1), (2, 2), (3, 3), (2, 3), (3, 1)}

{(1, 1), (2, 2), (3, 3)}

∅

None of the above.

Which of the following statements is correct?

If A ∪ C = B ∪ C, then A = B

If A ∩ C = B ∩ C, then A = B

{∅, {a}, {∅, a}} is the power set of some set.

∅ ⊆ {∅}

A ∩ (B ∪ C) = (A ∪ B) ∩ (A ∪ C).

Which of the following statements is correct?

The union of an infinite number of countably infinite sets is always countably infinite

A × B is always countably infinite, if both A and B are countably infinite.

If f : A → B and B is countable infinite, then A is always countably infinite.

If A is countably infinite, then 2^A is always countably infinite.

For complete bipartite graph K_m,n to be planar, what is the maximum value of m + n?

5

6

7

8

None of the above.

If f : X → Y is a one-to-one and onto function, and Y is a proper subset of X, which of the following statements is correct?

X must be countably infinite

Y must be countably infinite.

X must be infinite.

The cardinality of X is larger than Y.

None of the above.

What is the number of distinct binary trees with 4 nodes?

10

12

14

16

None of the above.

Let (S,≦) be a POSET. (S, ≦) is well-ordered if ≦is a total ordering such that every　nonempty subset of S has a least element according to ≦. Which of the following is　well-ordered (hence ≤ denotes the "less than or equal to" relation in arithmetic)?

(Z, ≤), where Z is the set of integers

(Q, ≤), where Q is the set of rational numbers

(N × N, ≤), where (a, b) ≤ (c, d) if and only if a ≤ c and b ≤ d, where N is the set of
natural numbers

([0, 1], ≤), where [0, 1] denotes the set {x | 0 ≤ x ≤ 1, x is a real number}

None of the above.

If a planar graph has 12 vertices, each of degree 3, how many edges and faces does the graph have?

number of edges = 18; number of faces = 7;

number of edges = 18; number of faces = 8;

number of edges = 36; number of faces = 25

number of edges = 36; number of faces = 26

None of the above.

Consider the following recurrence relation: f(n + 2) − 3f(n + 1) + 2f(n) = 2ⁿ subject to f(0) = 1, f(1) = 4. Suppose we know that the solution of the above recurrence relation is of the form f(n) = an2ⁿ + b2ⁿ + c, where a, b, and c are three constants. What is the value of a + b + c?

1

1.5

2.5

3

None of the above

Among the four graphs displayed in Figure 3, how many of them are planar?

0

1

2

3

4

Which of the following is a possible sequence of vertex degrees of an undirected simple graph?

2, 2, 2, 3, 4, 4

0, 1, 2, 3, 4, 5, 6, 7

1, 1, 2, 4

0, 1, 2, 2, 3

None of the above

Consider the graph G shown in Figure 4. Which of the following is true:

G has an Euler circuit but no Hamilton circuit.

G has an Euler path but no Euler circuit

G has an Euler circuit and a Hamilton circuit

G has no Euler circuit and no Hamilton circuit.

None of the above.

How many solutions does the equation x₁ + x₂ + x₃ = 13 have, where x₁, x₂, x₃ are nonnegative integers less than 6?

5

6

7

8

None of the above.

Which one is the smallest partial order relation on {1, 2, 3} that contains (3, 2), (1, 3)?

{(3, 2), (1, 3)}

{(1, 1), (2, 2), (3, 3), (3, 2), (2, 3), (1, 3), (3, 1), (1, 2), (2, 1)}

{(1, 1), (2, 2), (3, 3), (3, 2), (1, 3), (1, 2)}

{(1, 1), (3, 2), (1, 3), (2, 3), (3, 1)}

None of the above.

Consider the following four statements:
If a ≡ b (mod m), and a ≡ c (mod m), then a ≡ b + c (mod m).
If a ≡ b (mod m), and c ≡ d (mod m), then ac ≡ b + d (mod m).
If a ≡ b (mod m), then 2a ≡ 2b (mod m).
If a ≡ b (mod m), then 2a ≡ 2b (mod 2m).
how many of them are correct?

0

1

2

3

4

Let Q_n denote the n-dimensional hypercube. (Q₃ is shown in Figure 5.)

What is the number of edges of Q_n?

2ⁿ⁺¹ − 4

n2ⁿ⁻¹

(n + 1)n

4n

None of the above.

Which of the following recurrence relations characterizes the so-called Fibonacci numbers:

a_n = 2a_n−1 − a_n−2, a₁ = 1, a₂ = 1.

a_n−1 = a_n + a_n−2, a₁ = 1, a₂ = 1.

a_n = a_n−1 + a_n−2, a₁ = 1, a₂ = 1.

a_n = na_n−1, a₁ = 1.

None of the above.

Given two functions g : A → B and f : B → C, which of the following is not correct:

If both f and g are onto, so is f o g.

If both f and g are one-to-one, so is f o g.

If both f and f o g are one-to-one, g need not be one-to-one.

If both g and f o g are onto, f must be onto.

f o g is a function from A to C.

Given a finite set S, consider (2^S, ⊆). which of the following is not correct:

∅ is the least element

S is the greatest element

⊆ is a total ordering

(2^S, ⊆) is a lattice

A ∪ B is the least upper bound of {A, B}, where A ⊆ S and B ⊆ S.

Which of the following is true?

A − (B − C) = (A − B) − C

(A − C) − (B − C) = A − B

A ∪ (B ∩ C) = (A ∩ B) ∪ (A ∩ C)

If A − C = B − C, then A = B.

What is the value of 

22

23

24

25

None of the above.