99年私立銘傳大學電通所離散數學

Let p and q be two propositions. Suppose that p → q is known to be false. Give the true values for

1.

p ∨ q

Let p and q be two propositions. Suppose that p → q is known to be false. Give the true values for

2.

q → p

Express the negations of each of these statements

3.

∀x (x² > x)

Express the negations of each of these statements

4.

∃x (x² = 2)

5.

Use mathematical induction to prove the inequality n < 2ⁿ for all positive integers n.

6.

Given an indirect proof of the theorem "If 3n + 2 is odd, then n is odd."

7.

Show that f(x) = x² + 2x + 1 is Θ(x²).

Let R be a relation from a set A to a set B. The inverse relation from B to A, denoted by R⁻¹, is the set of ordered pairs {(b, a) | (a, b) ∈ R}. The complementary relation  is the set of ordered pairs {(b, a) | (a, b) ∉ R}. Let R be the relation R = {(a, b) | a < b} on the set of integers. Find

8.

R⁻¹.

Let R be a relation from a set A to a set B. The inverse relation from B to A, denoted by R⁻¹, is the set of ordered pairs {(b, a) | (a, b) ∈ R}. The complementary relation  is the set of ordered pairs {(b, a) | (a, b) ∉ R}. Let R be the relation R = {(a, b) | a < b} on the set of integers. Find

9.

10.

Draw the Hasse diagram representing the partial ordering {(a, b) | a divides b} on {1, 2, 3, 4, 6, 8, 12}.

The complete bipartite graph K_m,n is the graph that has its vertex set partitioned into two subsets of m and n vertices, respectively. There is an edge between two vertices if and only if one vertex is in the first subset and the other vertex is in the second subset. Answer the following questions about the graph K_3,4.

11.

How many vertices and how many edges are in this graph?

The complete bipartite graph K_m,n is the graph that has its vertex set partitioned into two subsets of m and n vertices, respectively. There is an edge between two vertices if and only if one vertex is in the first subset and the other vertex is in the second subset. Answer the following questions about the graph K_3,4.

12.

Is this graph planar? Justify your answer

The complete bipartite graph K_m,n is the graph that has its vertex set partitioned into two subsets of m and n vertices, respectively. There is an edge between two vertices if and only if one vertex is in the first subset and the other vertex is in the second subset. Answer the following questions about the graph K_3,4.

13.

Does this graph have an Euler circuit? Give reasons for your answer.

An undirected graph is displayed in Figure 1.

14.

Use an adjacency matrix to represent this graph

An undirected graph is displayed in Figure 1.

15.

Use an incidence matrix to represent this graph.

16.

Find a recurrence relation for the number of bit strings (strings of 0's and 1's) of length n with an even number of 0s.