99年國立東華大學資工所離散數學

Let P(x) be the statement "student x knows Discrete Mathematics" and let Q(y) be the statement "class y contains a student who knows Discrete Mathematics." Express each of these as quantifications of P(x) and Q(y).

1.

Some students know Discrete Mathematics

Let P(x) be the statement "student x knows Discrete Mathematics" and let Q(y) be the statement "class y contains a student who knows Discrete Mathematics." Express each of these as quantifications of P(x) and Q(y).

2.

Not every student knows Discrete Mathematics

Let P(x) be the statement "student x knows Discrete Mathematics" and let Q(y) be the statement "class y contains a student who knows Discrete Mathematics." Express each of these as quantifications of P(x) and Q(y).

3.

Every class has a student in it who knows Discrete Mathematics.

Let P(x) be the statement "student x knows Discrete Mathematics" and let Q(y) be the statement "class y contains a student who knows Discrete Mathematics." Express each of these as quantifications of P(x) and Q(y).

4.

There is at least one class with no student who knows Discrete Mathematics.

5.

Show that given a set of n + 1 positive integers, none exceeding 2n, there is at least one integer in this set that divides another integer in the set.

A rooted spanning tree of a directed graph is a rooted tree containing edges of the graph such that every vertex of the graph is an endpoint of one of the edges in the tree

6.

Show that a connected directed graph in which each vertex has the same in-degree and out-degree has a rooted spanning tree

A rooted spanning tree of a directed graph is a rooted tree containing edges of the graph such that every vertex of the graph is an endpoint of one of the edges in the tree

7.

Propose an algorithm to construct a rooted spanning tree for connected directed graphs in which each vertex has the same in-degree and out-degree.

Let an denote the number of ways a person can climb up a ladder with n rungs. At each step he can climb one or two rungs.

8.

Define a_n recursively.

Let an denote the number of ways a person can climb up a ladder with n rungs. At each step he can climb one or two rungs.

9.

Find an explicit formula for a_n.

Find the probability that a randomly generated bit string of length 10 does not contain a 0 if bits are independent and if

10.

a 0 bit and a 1 bit are equally likely.

Find the probability that a randomly generated bit string of length 10 does not contain a 0 if bits are independent and if

11.

the probability that a bit is a 1 is 0.6.

Find the probability that a randomly generated bit string of length 10 does not contain a 0 if bits are independent and if

12.

the probability that the i-bit is a 1 isfor i = 1, 2, …, 10.

13.

Construct a nondeterministic finite-state automaton that recognizes the language generated by the regular grammar G = (V, Σ, S, P), where V = {A, S}, Σ = {a, b}, and P = {S → aA| b | λ, A → aA | bA | a}.