96年國立雲林科技大學資工所資管所離散數學

1.

Given any positive integers a and b. Prove that there exists a unique positive integer c that is the greatest common divisor of a and b.

2.

Let R[x] be the set of all polynomials in the indeterminate x with coefficients from R. Given that R is a ring. Prove that under the operations of polynomial addition (+) and multiplication (∗), (R[x], +, ∗) is a ring

3.

(a) If A is a set, then prove any equivalence relation R on A induces a partition of A.

4.

(b) If A is a set, then prove that any partition of A gives rise to an equivalence relation R on A.

5.

Define the Fibonacci numbers as follows:
F₁ = 1, F₂ = 1, F_n = F_n−1 + F_n−2, for n ≥ 2.
Prove that any two consecutive Fibonacci numbers are relatively prime.

6.

Which of the following are statements?

(A)

The moon is made of green cheese

(B)

He is certainly a tall man.

(C)

Two is a prime number.

(D)

Will the game be over soon?

(E)

Next year interest rates will rise.

7.

Prove that for any positive integer n, the number 2²ⁿ − 1 is divisible by 3.
 

8.

How many distinct permutations are there of the characters in the word HAWAIIAN?

9.

How many of these must begin with H?

Consider the following Turing machine:
(0, 0, 0, 1, R)
(0, 1, 0, 0, R)
(0, b, b, 0, R)
(1, 0, 1, 0, R)
(1, 1, 1, 0, R)

10.

What is the final tape, given the initial tape?

Consider the following Turing machine:
(0, 0, 0, 1, R)
(0, 1, 0, 0, R)
(0, b, b, 0, R)
(1, 0, 1, 0, R)
(1, 1, 1, 0, R)

11.

Describe the behavior of the machine when started on the tape.

Consider the following Turing machine:
(0, 0, 0, 1, R)
(0, 1, 0, 0, R)
(0, b, b, 0, R)
(1, 0, 1, 0, R)
(1, 1, 1, 0, R)

12.

Describe the behavior of the machine when started on the tape.

13.

Let ρ be a binary relation on a set S. Then a binary relation called the inverse of ρ, denoted ρ⁻¹, is defined by x ρ⁻¹ y ↔ y ρ x. Prove that if a binary relation ρ on a set S is reflexive and transitive, then the relation ρ ∩ ρ−1 is an equivalence relation.