24-25-1-离散数学-期中

I. True or False Questions

1. The relation $\{(1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (1, 3), (2, 3)\}$ is a partial order on $\{1, 2, 3\}$.

2. If $p \lor q$ and $\neg p$ are both true, then $q$ is true.

3. Fifty-one points are placed in a square of side length 1. There must exist a circle of radius $1/7$ that contains three of the points.

4. $3^n \le (n + 2)!$ for all integer $n \ge 1$.

5. It is true that we have both that $\{2\} \in \mathcal{P}\{1, 2\}$ and $\{2\} \subseteq \mathcal{P}\{1, 2\}$.

6. Let $R$ and $S$ be relations on $X$. If $R$ and $S$ are symmetric, then $R \circ S$ is symmetric.

7. $R$ and $S$ are relations on $X$. If $R$ and $S$ are reflexive, then $R \cap S$ is reflexive.

8. For propositions $P = (p \to q) \land (q \to r)$, $Q = p \to r$, we have that $P \equiv Q$.

9. Suppose $p$ is true, $r$ is true, $s$ is false. The truth value of $(\neg p \lor s) \to (s \land r)$ is true.

10. The relation $\emptyset$ is always reflexive on a set $X$.

11. There do not exist two powers of 8 whose difference is divisible by 2003.

12. Let $P(n)$ be the propositional function ”$n$ divides 77”. The domain of discourse is $\mathbb{Z}^+$. The proposition $\neg(\forall n\ P(n))$ is true.

13. There are 10 lamps in a hall. Each of them can be switched on independently. The number of ways in which the hall can be illuminated is $2^{10}$.

14. The postage of 9 cents or more can be achieved by using only 3-cent and 7-cent stamps.

15. The sets $X$ and $Y$ are subsets of a universal set $U$. We have that $\mathcal{P}(X) \cup \mathcal{P}(Y) \subseteq \mathcal{P}(X \cup Y)$.

16. $R$ and $S$ are relations on $X$. If $R$ and $S$ are symmetric, then $R \cup S$ is symmetric.

17. The sets of $\{1, 2, 3\} \times \{1, 2\}$ and $\{1, 2\} \times \{1, 2, 3\}$ are equal.

18. There exists some integer $n \ge 1$ that $17^n + 11$ cannot be divided by 4.

II. Multiple Choice Questions

1. The sets $X, Y, Z$ are subsets of a universal set $U$. For the following two statements, determine whether they are true or false.

(1) $X \cup (Y - Z) = (X \cup Y) - (X \cup Z)$

(2) $X \times (Y \cup Z) = (X \times Y) \cup (X \times Z)$

2. In how many different ways can the letters of the word BOOKLET be arranged such that B and T always come together.

3. Determine whether the relation of $(x, y) \in R$ if 3 divides $x + 2y$ is symmetric and transitive.

4. Suppose $p$ is the statement ‘I play softball’ and $q$ is the statement ‘The moon is 250,000 miles from Earth.’ Select the correct statement corresponding to the symbols $\neg p \land q$.

5. Here is a group of 191 students, of which 10 are taking French, business, and music; 36 are taking French and business; 20 are taking French and music; 18 are taking business and music; 65 are taking French; 76 are taking business; and 63 are taking music. How many are taking French or business (or both)?

6. Determine whether the set $\{(a, 1), (a, 2), (c, 3), (d, 4)\}$ is a function from $X = \{a, b, c, d\}$ to $Y = \{1, 2, 3, 4\}$, and then determine if it is one-to-one, onto, or both.

7. Select the statement that is the negation of “You wear matching socks to the interview or you don’t get hired.”