[离散数学复习大纲20101.doc

（说明：有些因为符号太多，不方便打出公式，不会的同学可以单独联系我辅导，答案中有些重点知识已经做出说明，请同学们掌握相关的方法，不要单纯背题） 第一部分数理逻辑 命题符号化 设p:天气很热,q:湿度很小,则命题“天气炎热但湿度很小”的符号化形式为 令天下雪，我去市里，我有时间，则命题“如果天不下雪，我有时间，那么我就去市里”符号化为。 设p:小王走路,q:小王听音乐,则命题“小王边走路边听音乐”的符号化形式为 设T(x):x是火车，C(y):y是卡车， H(x,y): x比y快，在谓词逻辑中，命题“所有火车都比某些卡车快”的符号化形式为 真值表 的成假赋值为_110__的成假赋值为___001________。 个命题变项的公式最多有__2个极小项。熟悉极小项与极大项的性质 使命题公式的类型是___(3)___________。 (1) 重言式; (2) 矛盾式; (3) 可满足式; (4) 不属于(1)、(2)、(3)任何类型。 一价逻辑公式的类型是___(1)_____。 (1) 重言式; (2) 矛盾式; (3) 可满足式; (4) 不属于(1)、(2)、(3)任何类型。 的类型是__(1)______。 重言式 ； (2) 矛盾式 ；(3) 可满足式 ； (4) 不属于(1),(2),(3) 任 何 类 型。 从此处开始往下的知识要求融会贯通 公式的主析取范式中包含小项__A_______。 A. ;B.C; D 。 使命题公式为假的真值指派是 (1) 。 (1) (0,0,0); (2) (1,0,1); (3) 1,1,0); (4) (1,0,0). 试给出命题公式的真值表并判别公式的类型。试判断命题公式的类型(重言式、矛盾式或可满足式)。 逻辑连接词的最小连接词完备集：将公式用只含的等价式表示 范式： 含有三个命题变项的公式的主析取范式为 。(主要掌握方法) 命题公式的主合取范式为_______ 下列含有命题p，q，r的公式中，是主析取范式的是（　　　） 下列式子正确的是（　　　） 用等价演算法求命题公式的主合取范式和成真指派。 求出命题的主合取范式（可以使用真值表或等价推理），再用主合取范式求出主析取范式（要求写出具体的表示）。用真值表法判断命题公式和是否等价,并说明两个公式的类型。 命题的自然推理系统 用“假设前件为真，推证后件也为真或者假设后件为假，推证前件也为假”的方法证明蕴含式（了解性质） 证明（掌握自然推理系统，是重点） 构造下面的推理证明前提:结论: （掌握自然推理系统，是重点） 谓词逻辑部分 。 对公式) x是约束出现，y是约束出现，z是自由出现（ ） 对公式的说法正确的是（　B　　） A.x是约束出现，y是约束出现，z是自由出现 B.x是约束出现，y既是约束出现又是自由出现，z是自由出现 C.x是约束出现，y既是约束出现又是自由出现，z是约束出现 D.x是约束出现，y是约束出现，z是约束出现 6.4~6.8要求掌握前束范式的求解和量词消去方法，很重要 求谓词公式的前束范式 求出的前束范式 个体域D={-2,3,6},一元谓词P(x)： Q(x)： R(x)： a：6， 试求公式的真值。 设个体域是整数集合,命题的真值为 在论域D={a,b}中与公式（）A（x）等价的不含存在量词的公式是（　　　） A. B. C. D. 第二部分：集合论(1-3.3课堂已讲，不再重复) 幂集： 集合的全体子集构成的集合为的________ 。 集合则 。 集合则 。 集合的运算 A,B为集合,命题的真值为 对任意集合有(A-B)-C=A-(B∪C)。（ ） 集合,则________。 {1,3}; (2) {2,4,6}; (3) {1,3,6,8}; (4) {1,2,3,4,6,8}。 对于任意集合X,Y,Z，则（ ）　　 A. X∩Y=X∩Z=Y=Z B. X∪Y=X∪Z=Y=Z C. X－Y=X－Z=Y=Z D. X⊕Y=X⊕Z=Y=Z 集合,则________。 A.{1,3}; B. {2,4,6}; C. {1,3,6,8}; D.{1,2,3,4,6,8}。 是集合A的元素，下列命题________为真。 A. B. C. D. 。 则为________。 ; (2) ; (3) ; (4) 。 已知为集合，若试证。 下列命题正确的是（　　　） 7.以下系统是代数系统的是（　　） 在1~200的整数中（包括1和200）