离散数学模拟试题（四）1

离散数学是一门重要的计算机科学基础课程，主要研究离散对象的结构、性质和相互关系。这份模拟试题涉及了离散数学中的多个核心概念，包括命题逻辑、集合论、图论以及关系理论。 1. 命题公式分析：题目中提到了命题公式qqpp(())，这是关于命题逻辑的问题。在命题逻辑中，一个公式可以是永假式、永真式、可满足式或等价式。这里，qqpp(())是两个相同命题的合取（与运算），即“p且p”，这是一个永真式，因为无论p的真值如何，"p且p"总是真的。所以正确答案是C. 永真式。 2. 命题逻辑符号化：“他只有懂法律，才不会犯法”可以用蕴含表示，即如果他懂法律（p），那么他不会犯法（q），符号化为pq，因此答案是A．pq。 3. 二元关系的传递性：传递性是指如果a与b有关，且b与c有关，则a与c也有关。选项中，只有B选项acca满足传递性，因为a与b有关，b与c有关，所以a与c也有关。 4. 图论的性质：在任何图G中，根据握手引理，所有节点的度数之和为边数的两倍。因为度数是偶数或奇数，所以度数为偶数的节点的数目一定是偶数。答案是A. 度数为偶数的结点。 5. 连通图的边数：在有n个结点的连通图中，最少需要n-1条边才能使所有结点相连，因此答案是B. 至少1\(n-1\)条。 6. 集合与映射的关系：选项C正确，因为双射是既能从A到B又可以从B到A的映射，是可逆的。其他选项错误：A. A到B的关系不一定是映射；B. 映射不一定是可逆的；D. 当BA时，可能存在单射但不是双射。 7. 命题“没有不犯错误的人”的符号化：此命题等价于“所有人都会犯错误”，用谓词逻辑表示为：对于所有x，如果x是人，则x犯错误。符号化为：\( \forall x (x \in A \rightarrow x \in B) \)，答案是A. ))()()((xBxAx。 8. 命题逻辑公式的真值：在整数集的论域中，公式\( \exists y \exists x (y > x^2) \)是真实的，因为存在一个整数y大于另一个整数x的平方，比如y=4，x=2。答案是A. )0)()((￿￿￿￿yxyx。 判断题部分： 1. 正确，命题公式的合取（且）仍然是一个命题公式。 2. 错误，n阶完全图任意两个不同结点的距离可以为1到n-1，取决于它们之间的边数。 3. 错误，集合B的元素没有包含在集合A中，因此并集不是B的子集。 4. 正确，空集是任何集合的真子集，包括空集自身。 填空题： 1. 根据骑士和无赖的特性，A说B是骑士，而B说他们是两类人，这意味着B不能是骑士，因为骑士只会说真话，所以B是无赖。若B是无赖，他说的话是谎话，那么他和A不是两类人，所以A也是无赖。答案是A和B都是无赖。 2. 图中节点度数的总和等于所有边的数量的两倍，因为每条边贡献了两个度数。 3. 命题“不经一事, 不长一智”可以符号化为\(\neg p \rightarrow \neg q\)，表示如果不经历一件事（p），就不会增长智慧（q）。 4. 某些人对某些食物过敏可以符号化为\(\exists x \exists y (\text{人}(x) \land \text{食物}(y) \land \text{过敏}(x, y))\)，表示存在一个个体x（人）和一个个体y（食物），x对y过敏。 简答题部分： 1. 要证明\( rsqpsrqp \models ((rs)\cdot (qp)) \cdot (s\cdot (rq)) \)，这涉及到序列操作，需要通过代换规则和结合律来证明，具体步骤较复杂，此处略去。 2. 要求((p v q)→r)→p的析取范式，需要进行逻辑转换，先将蕴含转换为合取和否定，再简化得到最终的析取形式，同样过程较为复杂，此处不详述。 3. 有向图D的邻接矩阵A需要列出每个节点的出度和入度，以及它们之间的边。根据给出的边关系，可以构建邻接矩阵，并判断该图是强连通图、弱连通图还是树形结构，这里也需要具体计算和分析。 以上是离散数学模拟试题的部分内容解析，涵盖了命题逻辑、集合论、图论等相关知识点，旨在帮助理解和掌握离散数学的基本概念和技巧。