离散数学复习大纲.doc

离散数学复习大纲20101(说明:有些因为符号太多,不方便打出公式,不会的同学可以单独联系我辅导,答案中有些重点知识已经做出说明,请同学们掌握相关的方法,不要单纯背题)第一部分数理逻辑命题符号化设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.;;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 ),y是约束出现,,y既是约束出现又是自由出现,,y既是约束出现又是自由出现,,y是约束出现,~,很重要求谓词公式的前束范式求出的前束范式个体域D={-2,3,6},一元谓词P(x):Q(x):R(x):a:6,试求公式的真值。 设个体域是整数集合,命题的真值为在论域D={a,b}中与公式()A(x)等价的不含存在量词的公式是( ):集合论(1-,不再重复)幂集:集合的全体子集构成的集合为的________。集合则。集合则。集合的运算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,则() ∩Y=X∩Z=>Y=∪Y=X∪Z=>Y=-Y=X-Z=>Y=⊕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的元素,下列命题________为真。.。则为________。;(2);(3);(4)。已知为集合,若试证。下列命题正确的是( )( )在1~200的整数中(包括1和200),分别求满足以下条件的整数个数1)可以被3和5整除但不能被7整除。2)只被5,3和7中的一个整数整除。设A={a,b},求出。(4分)集合上的笛卡尔积以及关系设,,R是定义在A到B的二元关系,定义为,写出R的关系矩阵。设=设;s(R)=。A,B为集合,且则到间的笛卡尔积共有几个(mn),A到B的函数有多少个nm,A到B的关系有多少个2mn?A上的关系有多少znn,A上的函数有多少个mm,A上的等价关系有多少个(第二类斯特灵数,不要求)?给出一个关系矩阵,问有多少个自反关系2n(n-1),对称关系2n(n+1)??A的幂集的元素有多少个2n?偏序关系具有关系的哪三个性质。等价关系呢?等价类的定义要