112年 - 112 教育部公費留學考試試題：離散數學#125724

1. (15%) Which of the following statements are tautology?(A) [p^(pq)]→q(B) [p→(qr)](C)(p^q)→(pvq)(D)

2. (10%) If three integers are selected, at random and without replacement, from {1,2,3,...,99,100}, what is the probability such that their sum is even ?

3. (10%) For three sets A,B, and C, please simplify the following set expression

4. (15%) For what base do we find that 251+445=1026.

A. (3%) List three functions from A to B.

B. (3%) How many functions f: A→B are there?

C. (3%) How many functions f: A→B are one-to-one?

D. (3%) How many functions g: B→A are there?

E. (3%) How many functions g: B→A are one-to-one?

F. (3%) How many functions f: A→B satisfy f(1)=x?

G. (3%) How many functions f: A→B satisfy f(1)=f(2)=x?

H. (3%) How many functions f: A→B satisfy f(1)=x and f(2)=y?

A. (3%) 0, 1, 0, 0, 0,...

B. (3%) 0, 1, 1, 1, 1,...

C. (3%) 0, 1, 2, 3, 4,...

D. (3%) 0, 1, 3, 6, 10,...

E. (4%) Use the above result 6D to find a formula for k.

7. (10%) The chromatic number of a graph is the minimum number of colors needed to label the vertices so that adjacent vertices receive different colors. Please determine the chromatic number of a bipartite graph.