25-26-2-离散数学（上）-期末

1. (12 points)

(1)

Let pp be the proposition “I will do every exercise in this book” and qq be the proposition “I will get an A in this course.” Express each of these as a combination of pp and qq.

  1. I will get an A in this course only if I do every exercise in this book.

  2. For me to get an A in this course it is necessary and sufficient that I do every exercise in this book.

  3. Either I will not get an A in this course or I will not do every exercise in this book.

(2)

Express each of these mathematical statements using predicates, quantifiers, logical connectives, and mathematical operators.

  1. The sum of two negative integer is negative.

  2. For any integer n>0, there exists a sequence of n consecutive composite integers.

  3. Every positive real number has exactly two square roots.

2. (8 points)

  1. How many different truth tables of compound propositions are there that involve the propositional variables p, q and r?

  2. Find a compound proposition involving the propositional variables p, q and r that is true when exactly two of p, q, and r are true and is false otherwise.

  3. Finally, give the principal disjunctive normal form and the principal conjunctive normal form of this compound proposition.

3. (10 points)

Show that the premises “Some employees do not have a valid ID card” and “Every employee can access the server”, imply the conclusion “Someone who can access the server does not have a valid ID card.”

4. (6 points)

Prove that given a nonnegative integer n, there is a unique nonnegative integer m such that m2≤n<(m+1)2m^2 \le n < (m+1)^2.

5. (4 points)

A, B and C are sets. Determine whether each of these properties is correct. [Fill in with ‘true’ or ‘false’].

  1. A−(B∩C)=(A−B)∪(A−C)A-(B\cap C)=(A-B)\cup(A-C) 【暂无答案】

  2. (A∩B)∪C=A∩(B∪C)(A\cap B)\cup C = A\cap(B\cup C) 【暂无答案】

  3. A⊕(B∩C)=(A⊕B)∩(A⊕C)A\oplus(B\cap C)=(A\oplus B)\cap(A\oplus C) 【暂无答案】

  4. A⊕(B−C)=(A⊕B)−CA\oplus(B-C)=(A\oplus B)-C 【暂无答案】

6. (4 points)

Determine the types of these functions. [Fill in with ‘injection’, ‘surjection’, ‘bijection’ or ‘other’]

  1. f:Z→N, f(n)=∣n∣f:\mathbb Z\to N,\ f(n)=|n| where N={0,1,2,… }N=\{0,1,2,\dots\} 【暂无答案】

  2. f:R→R, f(x)=x2−2xf:\mathbb R\to\mathbb R,\ f(x)=x^2-2x 【暂无答案】

  3. f:{1,2,3,4}→{a,b,c}, f(1)=a,f(2)=b,f(3)=c,f(4)=cf:\{1,2,3,4\}\to\{a,b,c\},\ f(1)=a,f(2)=b,f(3)=c,f(4)=c 【暂无答案】

  4. f:Z→Z, f(n)={n+1,if n is evenn−1,if n is oddf:\mathbb Z\to\mathbb Z,\ f(n)= \begin{cases} n+1,& \text{if }n\text{ is even}\\ n-1,& \text{if }n\text{ is odd} \end{cases} 【暂无答案】

7. (4 points)

Determine whether these sets are finite, countably infinite or uncountable. [Fill in with ‘finite’, ‘countably infinite’ or ‘uncountable’].

  1. all rational numbers 【暂无答案】

  2. all real numbers between 0 and 1 【暂无答案】

  3. S={(m∈N, n∈N)∣m+n=100}, N={0,1,2,… }S=\{(m\in\mathbb N,\ n\in\mathbb N)\mid m+n=100\},\ \mathbb N=\{0,1,2,\dots\} 【暂无答案】

  4. all finite strings of characters from the English alphabet {a,b,c,…,z}\{a,b,c,\dots,z\} 【暂无答案】

8. (6 points)

Fill in the blank.

  1. Let sets A={1,2}, B={a,b,d}, C={b,c,d}\mathbf{A}=\{1,2\},\ \mathbf{B}=\{a,b,d\},\ \mathbf{C}=\{b,c,d\}, then (A×B)∩(A×C)=(\mathbf{A}\times \mathbf{B})\cap(\mathbf{A}\times \mathbf{C})= 【暂无答案】

  2. Suppose that g:A→Bg:A\to B and f:B→Cf:B\to C, where A=B=C={1,2,3,4}, g={(1,4),(2,1),(3,1),(4,2)}, and f={(1,3),(2,2),(3,4),(4,2)}. So f∘g=A=B=C=\{1,2,3,4\},\ g=\{(1,4),(2,1),(3,1),(4,2)\},\ \text{and }f=\{(1,3),(2,2),(3,4),(4,2)\}.\text{ So }f\circ g= 【暂无答案】

  3. Let 0-1 Matrix A=[101011100] solve A[3]=\mathbf{A}= \begin{bmatrix} 1 & 0 & 1\\ 0 & 1 & 1\\ 1 & 0 & 0 \end{bmatrix} \text{ solve }\mathbf{A}^{[3]}= 【暂无答案】

9. (8 points)

Show that if f1(x)f_1(x) is O(g1(x))O(g_1(x)) and f2(x)f_2(x) is O(g2(x))O(g_2(x)), then (f1+f2)(x)(f_1+f_2)(x) is O(g(x))O(g(x)), where g(x)=max⁡(∣g1(x)∣,∣g2(x)∣)g(x)=\max(|g_1(x)|,|g_2(x)|) for all xx.

10. (8 points)

Use the construction in the proof of the Chinese remainder theorem to find all solutions to the system of congruences x≡2(mod3), x≡1(mod4), and x≡3(mod5)x \equiv 2 \pmod 3,\ x \equiv 1 \pmod 4,\ \text{and }x \equiv 3 \pmod 5.

11. (8 points)

Use Fermat’s little theorem to evaluate 3402(mod19)3^{402}\pmod{19}.

12. (6 points)

Use mathematical induction to prove that 43 divides 6n+1+72n−16^{n+1}+7^{2n-1} for every positive integer nn.

13. (8 points)

There are 42 students in a seminar, and each student can choose one or more courses from three elective subjects: Computer Science, Mathematics, Physics. Prove that at least three students have exactly the same combination of elective courses.

14. (8 points)

A fruit shop provides 3 kinds of fruits: apples, bananas, oranges. Fruits of the same type are identical. How many distinct ways to select 9 fruits if we need at least 2 bananas?