99年國立中正大學資工所離散數學

Let C(x), B(x) and P(x) denote the following statements.
C(x): x is in this class.
B(x): x has read the book.
P(x): x passed the first exam.
Express each of the following statements in (a), (b) and (c), using quantifiers, logical connectives, C(x), B(x) and P(x), and then prove (d).

1.

A student in this class has not read the book

Let C(x), B(x) and P(x) denote the following statements.
C(x): x is in this class.
B(x): x has read the book.
P(x): x passed the first exam.
Express each of the following statements in (a), (b) and (c), using quantifiers, logical connectives, C(x), B(x) and P(x), and then prove (d).

2.

Everyone in this class passed the first exam.

Let C(x), B(x) and P(x) denote the following statements.
C(x): x is in this class.
B(x): x has read the book.
P(x): x passed the first exam.
Express each of the following statements in (a), (b) and (c), using quantifiers, logical connectives, C(x), B(x) and P(x), and then prove (d).

3.

Someone who passed the first exam has not read the book

Let C(x), B(x) and P(x) denote the following statements.
C(x): x is in this class.
B(x): x has read the book.
P(x): x passed the first exam.
Express each of the following statements in (a), (b) and (c), using quantifiers, logical connectives, C(x), B(x) and P(x), and then prove (d).

4.

Prove that (a) and (b) implies (c), using rules of inference.

Probabilities
We have two boxes. The first contains two green balls and seven red balls; the second contains four green balls and three red balls. Bob selects a ball by first choosing one of the two boxes at random. He then selects one of the balls in this box at random. Consider the following events E and F.
  E: the event then Bob has selected a red ball.
  F: the event that Bob has selected a ball from the first box

5.

What is the probability P(E|F)?

Probabilities
We have two boxes. The first contains two green balls and seven red balls; the second contains four green balls and three red balls. Bob selects a ball by first choosing one of the two boxes at random. He then selects one of the balls in this box at random. Consider the following events E and F.
  E: the event then Bob has selected a red ball.
  F: the event that Bob has selected a ball from the first box

6.

Probabilities
We have two boxes. The first contains two green balls and seven red balls; the second contains four green balls and three red balls. Bob selects a ball by first choosing one of the two boxes at random. He then selects one of the balls in this box at random. Consider the following events E and F.
  E: the event then Bob has selected a red ball.
  F: the event that Bob has selected a ball from the first box

7.

What is the probability P(E)?

Probabilities
We have two boxes. The first contains two green balls and seven red balls; the second contains four green balls and three red balls. Bob selects a ball by first choosing one of the two boxes at random. He then selects one of the balls in this box at random. Consider the following events E and F.
  E: the event then Bob has selected a red ball.
  F: the event that Bob has selected a ball from the first box

8.

What is the probability P(E ∩ F)?

Probabilities
We have two boxes. The first contains two green balls and seven red balls; the second contains four green balls and three red balls. Bob selects a ball by first choosing one of the two boxes at random. He then selects one of the balls in this box at random. Consider the following events E and F.
  E: the event then Bob has selected a red ball.
  F: the event that Bob has selected a ball from the first box

9.

What is the probability P(F|E)?

Two sets have the same cardinality if and only if there is a bijection, i.e., one-to-one correspondence, between them. Consider the following sets.
A(x) = {x : x is an integer}
B(x) = {x : x is a positive integer and is a multiple of 3}
C(x) = {x : x is an integer, and 100 < x < 1000}
D(x) = {x : x is a subset of B}
Indicate True or False for each of the following statements. Briefly explain each of your answers

10.

A and B have the same cardinality.

Two sets have the same cardinality if and only if there is a bijection, i.e., one-to-one correspondence, between them. Consider the following sets.
A(x) = {x : x is an integer}
B(x) = {x : x is a positive integer and is a multiple of 3}
C(x) = {x : x is an integer, and 100 < x < 1000}
D(x) = {x : x is a subset of B}
Indicate True or False for each of the following statements. Briefly explain each of your answers

11.

B and C have the same cardinality.

Two sets have the same cardinality if and only if there is a bijection, i.e., one-to-one correspondence, between them. Consider the following sets.
A(x) = {x : x is an integer}
B(x) = {x : x is a positive integer and is a multiple of 3}
C(x) = {x : x is an integer, and 100 < x < 1000}
D(x) = {x : x is a subset of B}
Indicate True or False for each of the following statements. Briefly explain each of your answers

12.

A and D have the same cardinality.

13.

The Fibonacci number f₀, f₁, f₂, …, are defined by the equations f₀ = 0, f₁ = 1, and f_n = f_n−1 + f_n−2 for n = 2, 3, 4, …. Use mathematical induction to prove that whenever n is a positive integer.

14.

Find the solution to the recurrence relation a_n = 6a_n−1 − 9a_n−2 with initial conditions a₀ = 2, a₁ = 9.

15.

A simple graph is called regular if every vertex of this graph has the same degree. How many vertices does a regular graph of degree 8 with 36 edges have?