桂电离散数学试卷

桂电离散数学试卷一、选择题（每题1分，共10分）

1.在集合论中，集合A={1,2,3}与集合B={3,4,5}的并集是？

A.{1,2,3,4}

B.{1,2,3,5}

C.{1,2,4,5}

D.{3,4,5}

2.下列哪个命题是永真式？

A.p∧¬p

B.p∨¬p

C.p→¬p

D.¬(p∨q)→¬p

3.在命题逻辑中，命题p:"今天下雨"，命题q:"我带伞"，命题p→q的逻辑含义是？

A.如果今天下雨，那么我带伞

B.如果今天不下雨，那么我带伞

C.如果我带伞，那么今天下雨

D.今天下雨且我带伞

4.设有向图G=(V,E)，其中V={a,b,c,d}，E={<a,b>,<b,c>,<c,d>,<d,a>}，则图G的阶数是？

A.2

B.3

C.4

D.5

5.在图论中，一棵树的边数与顶点数的关系是？

A.边数=顶点数

B.边数=顶点数-1

C.边数=顶点数+1

D.边数=顶点数×2

6.在数理逻辑中，谓词逻辑的符号∀表示什么？

A.合取

B.析取

C.蕴含

D.全称量化

7.设集合A={1,2,3}，集合B={2,3,4}，集合C={3,4,5}，则(A×B)∩(B×C)的结果是？

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

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

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

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

8.在关系代数中，关系R与关系S的笛卡尔积记作？

A.R∪S

B.R∩S

C.R×S

D.R-S

9.在布尔代数中，逻辑表达式(a∧b)∨(¬a∧¬b)等价于？

A.a∨b

B.a∧b

C.¬a

D.¬b

10.在组合数学中，从n个不同元素中取出k个元素的组合数记作？

A.P(n,k)

B.C(n,k)

C.A(n,k)

D.G(n,k)

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

1.下列哪些是命题逻辑的有效推理形式？

A.(p∧q)→p

B.p→(q→p)

C.(p→q)∧(q→r)→(p→r)

D.p∨¬p

2.在图论中，下列哪些是树的性质？

A.无环连通图

B.任意两个顶点之间有且只有一条路径

C.存在唯一一个顶点度数为0

D.边数等于顶点数减1

3.下列哪些是谓词逻辑的量词？

A.∃

B.∀

C.→

D.∧

4.在集合论中，下列哪些运算是封闭的？

A.并集

B.交集

C.差集

D.补集

5.在组合数学中，下列哪些公式是正确的？

A.C(n,k)=C(n,n-k)

B.P(n,k)=n!/(n-k)!

C.C(n,k)=n!/(k!(n-k)!)

D.A(n,k)=C(n,k)*k!

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

1.在命题逻辑中，表达式(p∨q)→¬r的对偶式是________。

2.设集合A={1,2,3}，集合B={2,3,4}，则A-B=________，B-A=________。

3.在图论中，一个有n个顶点的无向完全图有________条边。

4.谓词逻辑中的量词∀xP(x)表示________，量词∃xP(x)表示________。

5.组合数学中，从n个不同元素中取出k个元素的排列数记作P(n,k)，其计算公式为________。

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

1.已知命题逻辑公式P:"它下雨"，Q:"我出门"。用自然语言写出命题公式(P→Q)∧¬Q的逻辑含义，并判断其真假值（假设“它下雨”为真，“我出门”为假）。

2.设集合A={x|x是偶数,1≤x≤10},B={x|x是素数,1≤x≤10}。求A∩B,A∪B,A-B,B-A。

3.画出有向图G=(V,E)，其中V={1,2,3,4}，E={<1,2>,<2,3>,<3,4>,<4,1>}的所有强连通分量。

4.写出谓词逻辑公式∀x∃y(P(x,y)∧Q(y))的翻译，并用自然语言解释其含义。假设P(x,y)表示"x知道y"，Q(y)表示"y是诚实的"。

5.计算从10个不同元素中取出6个元素的组合数C(10,6)，并计算从10个不同元素中取出6个元素并排列的排列数P(10,6)。

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

一、选择题答案

1.C

2.B

3.A

4.C

5.B

6.D

7.B

8.C

9.A

10.B

二、多项选择题答案

1.A,B,C,D

2.A,B,D

3.A,B

4.A,B,C,D

5.A,B,C,D

三、填空题答案

1.(¬p∧¬q)∨r

2.{1},{4}

3.n(n-1)/2

4.对所有x，P(x)为真；存在某个x，使得P(x)为真

5.n!/(n-k)!

四、计算题答案

1.逻辑含义：如果它下雨，那么我出门并且我没出门。真值：假。解题过程：P为真，Q为假，P→Q为假，¬Q为真，假∧真为假。

2.A∩B={2},A∪B={2,3,4,6,8,10},A-B={4,6,8,10},B-A={2,3,7,9}。解题过程：列出A和B的元素，分别求交集、并集、差集。

3.强连通分量只有一个，包含所有顶点{1,2,3,4}。解题过程：遍历所有顶点，检查是否能从任一顶点到达其他所有顶点。

4.翻译：对所有x，存在y使得x知道y且y是诚实的。含义：每个人都知道至少一个诚实的人。解题过程：理解量词∀和∃的含义，以及谓词P和Q的定义。

5.C(10,6)=210,P(10,6)=720。解题过程：使用组合数公式C(n,k)=n!/(k!(n-k)!)和排列数公式P(n,k)=n!/(n-k)!。

知识点分类和总结

集合论：集合的基本运算（并、交、差、补）、集合的性质、集合的笛卡尔积。

命题逻辑：命题、联结词、真值表、推理形式、对偶式。

图论：无向图、有向图、路径、环、连通性、树、完全图、强连通分量。

谓词逻辑：量词（全称、存在）、谓词、翻译自然语言。

组合数学：排列、组合、公式（P(n,k),C(n,k)）。

各题型所考察学生的知识点详解及示例

选择题：考察学生对基本概念的理解和记忆，如集合运算、命题逻辑联结词、图论性质、谓词逻辑量词、组合数学公式等。示例：判断命题逻辑公式真假值，识别图论中的完全图，理解谓词逻辑量词含义。

多项选择题：考察学生对多个相关概念的理解和区分，要求学生能全面考虑所有选项。示例：识别所有有效的命题逻辑推理形式，列出图论中树的性质，区分谓词逻辑量词和联结词。

填空题：考察学生对基本概念的精确记忆和表达，要求学生能用自己的语言或符号准确填写答案。示例：写出命题逻辑公式的对偶式，列出集合运算的结果，写出图论中完全图的边数，解释谓词逻辑量词的含义，写出组合数学公式的表达式。

计算题：考察学生综合运用所学知识解决具体问题的能力，要求学生能按照步骤进行计算和推理。示例：求集合运算的结果，画出图的强