离散数学是计算机科学中的基础课程，涉及到许多重要的概念，如逻辑公式、关系、映射、图论等。以下是对给定试题中涉及知识点的详细解释：
1. **命题逻辑与重言式**：
- 重言式是指无论变量取何值，命题公式始终为真的表达式。在给定的选项中，`C.（┐P∨Q）∧┐（┐P∧Q）`等价于`P↔Q`，是永真式，即重言式。这表示命题`P`和`Q`的关系是等价的，无论`P`和`Q`的真值如何，整个表达式总是为真。
2. **计数问题**：
- 在1到300中，同时不能被3、5、7整除的数可以通过排除法计算，这是一个组合问题。
- 能被3整除但不能被5和7整除的数，首先计算能被3整除的数，再排除掉同时被5和7整除的数。
3. **映射性质**：
- 映射`f: R→R, f(x) = -x^2 + 2x - 1`是一个二次函数，它在实数集上可能没有反函数，因为对于某些x值，可能存在多个y值对应，这表明`f`不是单射；同时，整个函数图像不会覆盖整个y轴，因此也不是满射。所以正确答案是`D.既不是单射，也不是满射`。
4. **一阶逻辑**：
- 前束范式是一阶逻辑公式的特定形式，要求所有的量词都在最前面。公式`∀x P(x)∀y Q(y)`的前束范式为`∀x∀y (P(x) ∧ Q(y))`。
- 命题“凡人都呼吸”可以符号化为`∀x[F(x) → H(x)]`，其中`F(x)`表示"x是人"，`H(x)`表示"x呼吸"。
5. **等价关系**：
- 在集合`A={a,b,c}`上，等价关系的数目等于将集合`A`划分为不同子集的方式数，这涉及到组合数学中的划分问题。
6. **图论**：
- 简单通路是从起点到终点不重复经过任何边的路径。对于给定的图G=<V,E>，需要具体分析图形来确定从a到d的简单通路数量。
- 一个3阶有向图的度序列描述了每个顶点的入度和出度之和，所以如果度序列为2,2,4，则出度序列可能是2,0,2，因为总度数必须等于2*3=6。
7. **关系运算**：
- 对于关系的运算，如BA、A⊕B、R1-1、R1·R2以及R1在A上的限制，需要理解这些操作的定义：
- BA是关系R2在B上的逆在A上的像。
- A⊕B是关系R1和R2的对称差。
- R1-1是R1的逆关系。
- R1·R2是关系的复合，表示先应用R1后应用R2。
- R1在A上的限制是指只保留R1中关于A中元素的那些关系。
8. **关系的性质**：
- 给定关系R及其在集合A={4,3,2,1}上的表示，需要通过关系图来判断R的性质，例如是否为自反、对称、传递等。
9. **图的构造**：
- 含有5个顶点，3条边的不同构的简单图，可以通过枚举所有可能的边连接方式来确定，注意图必须是无环且边数有限的。
离散数学的这些概念在计算机科学中有着广泛的应用，包括数据库设计、算法分析、编译器设计、人工智能等领域。掌握这些基本概念是理解和解决问题的关键。
评论0