南理工离散数学试卷

南理工离散数学试卷一、选择题（每题1分，共10分）

1.下列哪个命题是永假式？

A.p∨¬p

B.p∧¬p

C.¬(p∧¬p)

D.(p∨q)→p

2.设集合A={1,2,3},B={2,3,4},则A∩B等于？

A.{1,2}

B.{3,4}

C.{2,3}

D.{1,4}

3.下列哪个是命题公式？

A.p∧q→r

B.p∨≠q

C.(p∧q)∨r→s

D.p∧(q∨r)

4.设命题公式p=(q∧r)→p，则p的析取范式为？

A.q∧r

B.q∨r

C.¬q∧¬r

D.¬q∨¬r

5.下列哪个是图G的顶点数和边数的关系？

A.|E|=|V|-1

B.|E|=|V|+1

C.|E|=2|V|

D.|E|=|V|/2

6.设有向图G的邻接矩阵为：

0100

0010

0001

1000

则G中顶点4到顶点1的路径长度为？

A.1

B.2

C.3

D.4

7.下列哪个是欧拉图？

A.具有奇数个奇度顶点的连通图

B.所有顶点的度数均为偶数的连通图

C.至少有两个奇度顶点的连通图

D.不存在欧拉回路的连通图

8.设集合A={1,2,3},B={2,3,4},则A×B等于？

A.{(1,2),(2,3),(3,4)}

B.{(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}

C.{(2,1),(3,1),(4,1),(2,2),(3,2),(4,2),(2,3),(3,3),(4,3)}

D.{(1,2),(2,3),(3,4),(4,1)}

9.下列哪个是偏序集？

A.(N,<)

B.(N,>)

C.(N,≤)

D.(N,≠)

10.设函数f:N→N定义为f(x)=x^2，则f是？

A.单射

B.满射

C.双射

D.非一一对应

二、多项选择题（每题4分，共20分）

1.下列哪些是命题逻辑的永真式？

A.p∨¬p

B.p∧¬p

C.¬(p∧¬p)

D.(p∨q)→p

2.设集合A={1,2,3},B={2,3,4},C={3,4,5},则下列哪些是正确的？

A.A∩(B∪C)={2,3}

B.(A∩B)∪C={2,3,4,5}

C.A∩B∩C={3}

D.A×(B∩C)={(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}

3.下列哪些是图G的欧拉回路？

A.所有顶点的度数均为偶数的连通图

B.具有奇数个奇度顶点的连通图

C.经过每条边恰好一次且回到起点的回路

D.不存在欧拉回路的连通图

4.设有向图G的邻接矩阵为：

0100

0010

0001

1000

则下列哪些是正确的？

A.G是强连通图

B.G是单向连通图

C.G是连通图

D.G不是强连通图

5.下列哪些是偏序集？

A.(N,<)

B.(N,>)

C.(N,≤)

D.(N,≠)

三、填空题（每题4分，共20分）

1.设命题公式p=q∧(r∨¬s)，则p的合取范式为_______。

2.一个具有n个顶点的简单无向图，其最大边数为_______。

3.设集合A={a,b,c}，B={1,2}，则A到B的函数个数共有_______个。

4.在偏序集(N,≤)中，小于等于5的元素组成的子集是_______。

5.设函数f:A→B，如果对于任意b∈B，都存在a∈A使得f(a)=b，则称f为_______。

四、计算题（每题10分，共50分）

1.对于命题公式p∧(q∨r)→¬q，求其主析取范式。

2.设集合A={1,2,3},B={2,3,4},C={3,4,5}，求(A∩B)×(B∪C)。

3.给定有向图G的邻接矩阵如下：

```

0100

0010

0001

1000

```

求图G中从顶点1到顶点4的所有简单路径。

4.设偏序集(P,≤)中，P={a,b,c,d}，偏序关系≤如下所示：

```

a≤b,a≤c,b≤d,c≤d

```

画出该偏序集的哈斯图，并写出所有极小元和极大元。

5.设函数f:R→R定义为f(x)=x^2，求f的反函数f^(-1)的定义域和值域。

本专业课理论基础试卷答案及知识点总结如下

一、选择题答案

1.B

2.C

3.A

4.C

5.A

6.B

7.B

8.B

9.C

10.C

二、多项选择题答案

1.A,C

2.A,B,C

3.A,C

4.A,B,C

5.A,B,C

三、填空题答案

1.(q∧¬r∧¬s)∨(q∧¬r∧s)∨(q∧r∧¬s)∨(q∧r∧s)

2.n(n-1)/2

3.2^3=8

4.{1,2,3,4,5}

5.满射

四、计算题答案

1.主析取范式为(p∧¬q∧¬r)∨(¬p∧¬q∧¬r)

2.(A∩B)×(B∪C)={(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}

3.从顶点1到顶点4的所有简单路径为：1→2→3→4和1→4

4.哈斯图略，极小元为{a},极大元为{d}

5.f^(-1)的定义域为[0,+∞)，值域为[0,+∞)

知识点总结

离散数学是计算机科学和信息技术的基础课程，主要研究离散量及其结构。本试卷涵盖了离散数学中的命题逻辑、集合论、图论、函数和关系、偏序关系等基础知识。

一、选择题知识点详解及示例

1.命题逻辑：考查永真式（重言式）的判断。永真式在任意赋值下都为真。例如，p∨¬p是永真式，因为p和¬p必有一个为真。

2.集合论：考查集合的交集运算。A∩B表示A和B的公共元素。例如，A={1,2,3},B={2,3,4}，则A∩B={2,3}。

3.命题公式：考查命题公式的定义。命题公式是由命题变元、逻辑联结词和括号组成的字符串。例如，p∧q→r是一个命题公式。

4.命题公式：考查命题公式的等价变换。¬(p∧¬p)等价于¬p∨p，根据排中律，这是一个永真式。

5.图论：考查无向图的边数关系。简单无向图的最大边数是n(n-1)/2，其中n是顶点数。例如，n=4时，最大边数为6。

6.图论：考查有向图中的路径长度。路径长度是指路径上边的数量。例如，1→2→3→4的路径长度为3。

7.图论：考查欧拉回路的定义。欧拉回路是经过每条边恰好一次且回到起点的回路。所有顶点的度数均为偶数的连通图存在欧拉回路。

8.集合论：考查集合的笛卡尔积。A×B表示A和B的所有有序对组合。例如，A={1,2,3},B={2,3,4}，则A×B={(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,2),(3,3),(3,4)}。

9.偏序关系：考查偏序集的定义。偏序关系是自反的、antisymmetric的、传递的。例如，(N,≤)是一个偏序集。

10.函数：考查函数的双射性。双射函数是一一对应且满射的函数。例如，f(x)=x^2是一个双射函数，因为每个正数都有一个唯一的平方根。

二、多项选择题知识点详解及示例

1.命题逻辑：考查永真式的判断。永真式在任意赋值下都为真。例如，p∨¬p是永真式，因为p和¬p必有一个为真。¬(p∧¬p)也是永真式，因为p∧¬p是永假式。

2.集合论：考查集合的运算和笛卡尔积。A∩(B∪C)表示A与B和C的并集的交集。例如，A={1,2,3},B={2,3,4},C={3,4,5}，则A∩(B∪C)={2,3}。(A∩B)∪C表示A和B的交集与C的并集。例如，A∩B={2,3}，(A∩B)∪C={2,3,4,5}。A∩B∩C表示A、B和C的交集。例如，A∩B∩C={3}。A×(B∩C)表示A与B和C的交集的笛卡尔积。例如，B∩C={3,4}，A×(B∩C)={(1,3),(1,4),(2,3),(2,4),(3,3),(3,4)}。

3.图论：考查欧拉回路的定义。欧拉回路是经过每条边恰好一次且回到起点的回路。所有顶点的度数均为偶数的连通图存在欧拉回路。具有奇数个奇度顶点的连通图不存在欧拉回路。

4.图论：考查有向图的连通性。强连通图是指任意两个顶点之间都有双向路径的图。单向连通图是指任意两个顶点之间都有单向路径的图。连通图是指任意两个顶点之间都有路径的图。例如，给定的有向图是单向连通图和连通图，但不是强连通图，因为顶点之间的路径不是双向的。

5.偏序关系：考查偏序集的定义。偏序关系是自反的、antisymmetric的、传递的。例如，(N,<)是一个偏序集，因为小于关系是自反的、antisymmetric的、传递的。(N,>)也是一个偏序集，因为大于关系是自反的、antisymmetric的、传递的。(N,≤)也是一个偏序集，因为小于等于关系是自反的、antisymmetric的、传递的。(N,≠)不是一个偏序集，因为不等关系不满足antisymmetric和transitive。

三、填空题知识点详解及示例

1.命题逻辑：考查命题公式的主析取范式。主析取范式是命题公式所有真值指派下的真值组合的合取范式。例如，p∧(q∨r)→¬q的主析取范式为(p∧¬q∧¬r)∨(¬p∧¬q∧¬r)。

2.图论：考查无向图的边数关系。简单无向图的最大边数是n(n-1)/2，其中n是顶点数。例如，n=3时，最大边数为3。

3.函数：考查函数的个数。A到B的函数个数等于B的元素个数的A的元素次方。例如，A={a,b,c}，B={1,2}，则A到B的函数个数共有2^3=8个。

4.偏序关系：考查偏序集中的子集。例如，在偏序集(N,≤)中，小于等于5的元素组成的子集是{1,2,3,4,5}。

5.函数：考查满射的定义。满射函数是指对于B中的每个元素，都存在A中的一个元素映射到它。例如，f:A→B，如果对于任意b∈B，都存在a∈A使得f(a)=b，则称f为满射。

四、计算题知识点详解及示例

1.命题逻辑：考查命题公式的主析取范式。主析取范式是命题公式所有真值指派下的真值组合的合取范式。例如，p∧(q∨r)→¬q的主析取范式为(p∧¬q∧¬r)∨(¬p∧¬q∧¬r)。

2.集合论：考查集合的运算和笛卡尔积。A∩B表示A和B的公共元素。B∪C表示B和C的并集。A×(B∪C)表示A与B和C的并集的笛卡尔积。例如，A={1,2,3},B={2,3,4},C={3,4,5}，则A∩B={2,3}，B∪C={2,3,4,5}，A×(B∪C)={(1,2),(1,3),(1,4),(1,5),(2,2),(2,3),(2,4),(2,5),(3,2),(3,3),(3,4),(3,5)}。

3.图论：考查有向图中的路径。路径是指顶点序列，其中相邻顶点之间有边。简单路径是指不重复经过任何顶点的路径。例如，给定的有向图，从顶点1到顶点4的所有简单路径为：1→2→3→4和1→