2024年5月17日发(作者：赛扬g1840)

线

订

装

号

学

名

线

姓

订

装

级

班

场

考

线

订

装

山东建筑大学试卷 共 5 页 第1页

5. Let A= {3, 7, 12}, define a relation R on A by xRy if and only if x-y <4. Let

2012 至 2013 学年第 1 学期 考试时间： 120 分钟

M

R

=(m

ij

) be the matrix of the relation R, then m

21

= , m

22

= .

课程名称： 离散数学A B卷 考试形式：闭卷

年级： 11 专业： 信息与计算科学 ；层次：本科

6. Determine whether the lattice shown in Figure 1 is distributive (分配的).

题号 一 二 三 四 五 总分

_______.

分数

一、

填空题（每小题2分，共30分）

1. Let p be the proposition: "The message is scanned for viruses" and q: "The

message was sent from an unknown system”. Write the following statement in

terms of p, q and logical connectives. "It is necessary to scan the message for

7. In a poset whose Hasse diagram shown in Figure 2, the least upper

viruses whenever it was sent from an unknown system."___________

bound (最小上界) of B={ c, d, e} is .

2. Let P(x) be the statement "x can speak Russian" and let Q(x) be the

8. Let n be a positive integer and let D

n

be the set of all positive divisors of n.

statement "x knows the computer language C++." Express the statement

Then D

n

is a lattice under the relation of divisibility. Determine whether D

60

is a

“There is a student at your school who can speak Russian and who knows

Boolean algebra. _________

C++” in terms of P(x), Q(x), quantifiers(量词), and logical connectives

9. Is the poset A={2, 3, 6, 18} under the relation of divisibility a lattice? _______.

___________. The domain for quantifiers consists of all students at your

10. Suppose f : N  N has the rule f(n) = 3n+2. Determine whether f is

school.

one-to-one? ___________.

3. Let A={1，2，…，30}, define a relation R on A by aRb if and only if |

11. Use the Huffman code tree in Figure 3 to decode the message:

a-b| 5

(a, b A), determine whether R is symmetric.

(用图3中的Huffman编码树，译出信息: ) ___________.

4. Let A={a, b, c}, R={ (b, c), ( b, b) } be a relation on A, then the symmetric

12. Whether the graph shown in Figure 4 has an Euler circuit? (图4中是否具

closure (对称闭包) of R is ________________________.

有欧拉回路？) .

线

订

装

号

学

名

线

姓

订

装

线

订

装

山东建筑大学试卷 共 5 页 第2页

13. Let S={a, b}, for P(S), * is defined as intersection, then (P(S), *) is a monoid, 5. Let Q(x) be the statement “x+1<3

”. If the universe of discourse consists of the

and the identity is _____________. integers, in the following, which is false? ( )

14. If S is a nonempty set, for A, BP(S), * is defined as A*B=AB (symmetric A .Q(1) B . (x) Q (x) C. (x)Q(x) D. Q(-1)

difference), then ( P(S), *) is a group, and its identity is _________.

6. Let R={ (a, a), (b, b), (c, c)} be a relation on a set A={a, b, c}, which

15. Let A= {Ø, a, {a, c}} be a set. Determine whether “{a, c}A” is true or

is the best for R ? (哪一项最适合R) ( )

false ._______. A. R is an equivalence relation. B. R is reflexive

二、选择题(每小题2分，共20分)在每小题列出的四个选项中只

C. R is symmetric D. R is transitive

有一个选项符合题目的要求，请将其代码填写在题后的括号内。

7. Which of the following Hasse diagrams represents a Boolean algebra?

( )

1. Which of the following statements is the negation of “6 is even or -5 is

negative”? ( )

A. 6 is even or –5 is not negative. B. 6 is odd and –5 is not negative.

C. 6 is odd or –5 is not negative. D. 6 is even and –5 is negative.

2. When the proposition p(qr) is true? ( )

A . p=1, q=1, r=0 B. p=0, q=1, r=1

C. p=1, q=0, r=1 D. p=0, q=0, r=1

8. Let G be the graph shown in Figure 6. How many edges need to be removed to

3. In the following, which is true? ( )

produce a spanning tree in G .(在图6中, 需要删除多少条边才可能产生一棵

A. {}{}={} B. {}{0, 1, 3} C.  {0, 1} D.{0}{0, 1, 3}

生成树) ? ( )

A . 0 B. 1 C. 2 D. 3

4. Let A=Z, defined a relation R on A by aRb if and only if |a-b|=3, which is true

9. In the Boolean algebra D

30

, the complement (补元) of 3 is ( )

for R? ( )

A. 10 B. 6 C. 15 D. 30

A. R is antisymmetric B. R is reflexive

C. R is symmetric D. R is asymmetric

线

订

装

号

学

名

线

姓

订

装

线

订

装

山东建筑大学试卷 共 5 页 第3页

2. Let f: ZZ be a function given by

f(n)





n





5





. Is f one to one or onto?

Explain.

10. Let Z

4

be a group with operation  as the Table 1, which is the inverse of [3]?

( )

A . [0] B. [2] C. [3] D. [1]

三、 计算题(每小题6分， 共30分)

1. Solve the recurrence relation (求解递推关系) c

n

=-8c

n-1

-16c

n-2

with initial

conditions c

1

=-1 and c

2

=8.

3. Let S={1, 2, 3, 6, 12}, a*b is defined as GCD (a, b). Determine whether (S, *) is

a semigroup, a monoid. If it is a monoid, specify the identity.