2023年6月24日发(作者：)

课程组长〔签字〕 系主任〔签字〕

学院 姓名 学号 选课/座号号 任课教师

………密………封………线………以………内………答………题………无………效……

电子科技大学英才学院2022 -2022学年第 1学期期 末 考试 A卷

离散数学 课程考试题 A 卷 〔 120分钟〕 考试形式：闭卷 考试日期 2022 年 月 日

课程成绩构成：平时 分， 期中 分， 实验 分， 期末 100 分

一 二 三 四 五 六 七 八 九 十 合计

I.

Multiple Choice

(15%, 1.5 points each)

〔A 〕

1.

(p∧q)→(p∨q) is logically equivalent to

a) T b) p∨q c) F d) p∧q

〔A 〕

2.

If P(A) is the power set of A, and A = , what is |P(P(P(A)))|?a) 4 b) 24 c) 28 d) 216

〔C 〕

3. Which of these statements is NOT a proposition?

a) Today is Monday. ` b) 1+1=2.

c) Am I right? d) Go and play with me.

〔C 〕

4. Which of these propositions is not logically equivalent to the other three?

a) (p q)  (r  q) b) (p  r)  q

c) (pr)  q d) The contrapositive of ¬q  (¬p ^ ¬r)

〔B 〕

5.

Suppose  A   3 and  B   8. The number of 1-1 functions f  A  B is

a) 24 b) P(83).

c) 38

d) 83

〔B 〕

6. Let R be a relation on the positive integers where xRy if x is a factor of y. Which

of the following lists of properties best describes the relation R?

a) symmetric, transitive

b) antisymmetric, transitive, reflexive

c) antisymmetric, symmetric, reflexive

d) symmetric, transitive, reflexive

〔C 〕

7.

Which of the following are partitions of

U{a,b,c,d,e,f,g,h}?

{a},{a,b,c},{c,d,e,f,g,h}. b)

{a},{b,c},{c,d,e,f,g,h}

c)

{a,d,g},{b,c},{e,f},{h}. d)

{a,b},{b,c},{d,e,f,g,h}

a)

〔C 〕

8.

〔A 〕

9.

The function f(x)=x2log(x3+78) is big-Oof which of the following functions?

a) x2

b) x(logx)3 c) x2logx

d) xlogx

11If

MR11010101, then R is:

110101a) reflexive b) symmetric c) antisymmetric d) transitive.

〔B 〕

10. Which of the followings is a function from Z to R?

第 1 页 共 5页 课程组长〔签字〕 系主任〔签字〕

学院 姓名 学号 选课/座号号 任课教师

………密………封………线………以………内………答………题………无………效……

a)

f(n)(n1). ` b)

f(x)x1.

c)

f(x)

2x d)

f(n)1

n22II.

True or False (10%, 1 point each)

〔T 〕

1.

If 1  0, then 5  6.

〔F 〕

2.

〔F 〕

3.

〔T 〕

4.

〔F 〕

5.

〔T 〕

6.

〔T 〕

7.

〔F 〕

8.

(p ∧ q) ∨ r ≡ p ∧ (q ∨ r)

If A, B, and C are sets, then (A-C)-(B-C)=A-B.

Suppose A  abc, then a  P(A).

h(x)x100 is defined as a function with domain R and codomain R.

Suppose g  A  B and f  B  C, where f  g is 1-1 and f is 1-1. g must be 1-1?

If

p and

q are primes ( 2), then

p 

q is composite.

If the relation R is defined on the set Z where aRb means that ab  0, then R is an

equivalence relation on Z.

〔T 〕

9.

(A  B)  (A  C) = A  (B  C).

aa is the power set of some set

〔T 〕

10.

The set

III.

Fill in the Blanks

(20%, 2 points each)

1.

Let p and q be the propositions “I am a criminal〞 and “I rob banks〞. Express in simple

English the proposition “if p then q〞: If I am a criminal them I rob banks.

2.

P(xy) means “x  2y 

xy〞, where x and y are integers. The truth value of xyP(xy)

is False.

3.

The negation of the statement “No tests are easy.〞 is some tests are easy.

4.

5.

6.

7.

8.

9.

11If

Ai{x|xRx} then

Aiis

.

iii1Suppose

Axy. Then

P(A) is {, {x}, {y},{x,y}}.

Suppose

g

AA and

f

AA where

A1234,g(14)(21)(31)(42)and

f(13)(22)(34)(42).Then

fg

=(12)(23)(33)(42).

The sum of 2  4  8  16  32    210 is 211  2 .

The expression of gcd(45, 12) as a linear combination of 12 and 45 is 12  4  45  (1).

There are 5! permutations of the seven letters A,B,C,D,E,F have A immediately to

the left of E.

10.

The two's complement of 13 is 1 0011 .

IV.

Answer the Questions

(32%,

4points each)：

1. Determine whether the following argument is valid:

第 2 页 共 5页 课程组长〔签字〕 系主任〔签字〕

学院 姓名 学号 选课/座号号 任课教师

………密………封………线………以………内………答………题………无………效……

p  r

q  r

q  r

________

 p

Ans: Not valid: p true, q true, r true

2. Suppose you wish to prove a theorem of the form “if p then q〞.

(a) If you give a direct proof, what do you assume and what do you prove?

(b) If you give an indirect proof, what do you assume and what do you prove?

(c) If you give a proof by contradiction, what do you assume and what do you prove?

Ans: (a) Assume p, prove q.

(b) Assume q, prove p.

(c) Assume p  q, show that this leads to a contradiction.

3. Prove that

ABAB by giving a proof using logical equivalence.

ABxxABxxABx(xAB) Ans:

x(xAxB)x(xA)(xB)

xxAxBxxAxBxxABAB4. Suppose f  R  R where f(x)  x2.

(a) If S  x  1  x  6, find f(S).

(b) If T  345, find f1(T).

Ans: (a) 0123

(b) [612).

5. Use the definition of big-oh to prove that

6n4n547n23 is O(n3).

第 3 页 共 5页 课程组长〔签字〕 系主任〔签字〕

学院 姓名 学号 选课/座号号 任课教师

………密………封………线………以………内………答………题………无………效……

6n4n546n54n510n553n, if n  2. Ans:

22227n37nn6n36. Solve the linear congruence 5x  3 (mod 11).

Ans: 5  11k.

3n117. Use the Principle of Mathematical Induction to prove that

139273 for all

2nn  0.

Ans: P(0):

3111 ,

which is true since

1  1.

P(k)  P(k  1):

23k11k13k1123k13k213.

222133

k18．Encrypt the message NEED HELP by translating the letters into numbers, applying the encryption function f

(p)  (3p  7) mod 26, and then translating the numbers back into letters.

Ans: Encrypted form: UTTQ CTOA.

V. (6%)

Without using the truth table, show that the following are tautologies

a) [p(pq)]→q

b) [p(p→q)]→q

Ans:

a)

p(pq)≡(pp)(p q)≡flase

[p(pq)]→q ≡ false→q≡falseq≡trueq≡true (3points)

b)[p(p→q)]→q≡([p(pq)])q≡(p(pq))q≡((pp)pq))q≡pqq≡true

(3points)

VI. (6%) Devise an algorithm which will find the minimum of n integers. What is the worst case time

第 4 页 共 5页 课程组长〔签字〕 系主任〔签字〕

学院 姓名 学号 选课/座号号 任课教师

………密………封………线………以………内………答………题………无………效……

complexity of this algorithm?

a) procedure min(a1, a2, …, an: integers) (4points)

v := a1 {largest element so far}

for i := 2 to n {go thru rest of elems}

if ai < v then v := ai {found smaller?}

{at this point v’s value is the same as the smallest integer in the list}

return v

b) the worst case time complexity of this algorithm is O(n). (2points)

VII.

(5%)

Give the definition of a transitive relation, and

Prove or disprove that the union of two

transitive relations is transitive.

Ans:

A relation R on a set A is called transitive if only if (a,b)

R and (b,c)

R ,then

(a,c)

R ,for a,b,c

A.

(2points)

The union of two transitive relations may be not transitive. A counter-example:

A={1,2,3}, R1= {<1,1>, <2,3>}, R2={<1,2><3,3> }

R1∪R2={<1.1>, <2,3><1,2><3,3>}, which is not transitive. (3points)

VIII. (6%)

Give an argument using rules of inference to show that the conclusion follows from the

hypotheses. List all the steps in your argument.

Hypotheses: All computer scientists like Star Trek. Sarah does not like Star Trek. Therefore,

Sarah is not a computer scientist.

Solution:

Hypotheses: ∀x(ComputerScientist(x) → Likes(x, StarTrek))

¬Likes(Sarah, StarTrek)

Conclusion: ¬ComputerScientist(Sarah)

Step 1: ∀x(ComputerScientist(x) → Likes(x, StarTrek)) (Hypothesis)

Step 2: ComputerScientist(Sarah) → Likes(Sarah, StarTrek) (Univ. Inst. Step 1)

Step 3: ¬Likes(Sarah, StarTrek) (Hypothesis)

Step 4: ¬ComputerScientist(Sarah) (Modus Toll. St. 2+3)

The argument is sound.

Grading rubric: -3 points for making wrong assumptions.

-2 points for not being able to complete the proof.

-1 to -3 points for illegal usage of inference rules.

第 5 页 共 5页