北京科技大学2009-2010离散数学试题解析

北京科技大学2009-2010学年度离散数学试题涵盖了离散逻辑、集合论、函数运算、代数系统、图论等多个关键知识点。以下是具体内容的详细解析： 一、单项选择题 1. 命题“只有今天是星期一，明天才是星期二”可以用命题逻辑表示为蕴含（Implication），即如果今天是星期一，则明天是星期二。符号化结果为 A、p→q。因为该命题表达的是“若P，则Q”，而不是“若非Q，则P”。 2. 合取范式是指一个逻辑公式可以被转化为仅包含AND（∧）操作的最简形式。选项C中的"P ∨ ([pic]P ∧ r)"不符合这一定义，因为它包含了括号和一个单独的变量。 3. 封闭公式是指其真假性不受额外自由变量影响的公式。选项C中的"[pic]x(P(x,a)→[pic]yQ(b,y))"含有两个自由变量x和y，其真假性会根据这两个变量的具体取值而改变，因此不是封闭公式。 4. 在集合论中，选项A的"{x}"属于{x，{x}}，选项B的{x}与{x，{x}}的关系是相同的元素；选项C表示A去掉空集等于A本身；选项D中，若A和B都为空集，则A-B的结果也是空集，所以D正确。这里考查的是集合的基本性质。 5. 对于集合S={1,2,3}上的二元关系，由于每个元素都可以作为第一个元素与S中的其他元素形成关系，共形成3×3=9个可能的关系，但由于关系是无序的，所以要去除重复的对称关系，因此不同的二元关系有9/2=4.5个，通常取整数部分，即4个。 6. 函数g(x)=2x应用到f(x)上，即先将x乘以2，然后再应用f，这里没有给出f的具体形式，但选项A是最符合常规函数复合的，即先计算g(x)再计算f(g(x))，所以gof(x)=[pic]。 7. 代数系统需要满足封闭性、结合律和分配律。选项A的乘法x*y=x^2-xy不满足结合律，因为(x*y)*z ≠ x*(y*z)，所以它不是一个代数系统。 8. 在给定的实数集运算中，a*b=a+b+ab，这个运算构成了一个半群，因为它满足封闭性和结合律，但不构成群，因为没有存在逆元使得ab=ba=1，排除了选项C和D。因此，正确答案是B。 9. 对于无向简单连通图，选项A是握手引理的推论，正确；选项B中最大度不超过顶点数减1，正确；选项C，简单图的最小度至少为1，故δ(G)≧1，选项C错误；选项D，简单连通图至少包含一个环，且环长至少为3，正确。 10. 度数列指的是图中各个顶点的度数之和。对于无向简单图，度数和必须是偶数。选项A和C满足条件，因为它们的度数总和为偶数；选项B中，2+2+2+4=10不是偶数，排除；选项D中，3+3+3+4=13也不是偶数。 二、填空题 1. 提供的公式未显示，无法确定其真值的个数，需要完整的公式才能判断。 2. 符号化形式为否定存在量词，即并非所有x为火车且所有y为汽车时，x比y快，可以写作：~∀x(F(x) ∧ ∀y(G(y) → ¬H(x,y)))。 3. 公式P(x)[pic]的类型取决于[pic]，若[pic]为全称量词，则为全称量词公式；若为存在量词，则为存在量词公式。 4. 需要知道A的幂集A'的具体元素，才能填空。 这些题目涉及离散逻辑的命题逻辑、集合论的运算性质、函数的复合、代数系统的定义、图论的性质以及基本的逻辑和集合概念。考生在解答这些问题时需要扎实的理论基础和一定的逻辑推理能力。