离散数学复习题一.docVIP

离散数学 复习题（一） 一、选择题 1. 设个体域，则公式消去量词后，可表示为-------（ C ） A、 B、 C、 D、 2、非空集合上的空关系不具备的性质是-----------------------------------------（ A ） A、自反性 B、反自反性 C、对称性 D、传递性 3、设分别为实数集、非负实数集、正整数集，下列函数为单射而非满射的是----------------------------------------------------------------------------------------------（ B ） A、 B、； C、 D、 4、在自然数集上定义的下列四种运算，其中满足结合律的是-----------------------（ C ） A、 B、 C、D、 5、设有向线图G的顶点集，邻接矩阵，则的入度------------------------------------------------------------------------------------（ D ） A、 B、 C、 D、 6、在有个结点的连通图中，其边数----------------------------------------------------（ B ） A、 最多有条 B、至少有条 C、最多有条 D、至少有条 填充题 1、任意两个不同极大项的析取式真值为1，而全体极大项的合取式真值为0. 2、设集合分别含有个不同元素，则的基数为． 3、设是阶循环群的生成元， 则是阶元素. 4、设〉是一棵树，若，则中至少存在片树叶. 三、填表计算题 对命题公式 ，要求 （1）用或填补其真值表的空格处； （2）求该命题公式的主析取范式与主合取范式. 解： 0 0 1 0 0 0 0 1 1 0 1 0 1 0 0 1 1 1 1 1 1 0 1 0 ----------------------------------------------------------------------------------------------------------6 主析取范式 ；----------------------------------------------------------------------2 主合取范式---------------------------------------2 四、计算题 集合上的关系 ， 写出关系矩阵，画出关系图并讨论的五种性质． 解：的关系矩阵为 ，------------------------------------------------2 的关系图为 ----------------------------------------------------------------------------------------------------------2 因对角元皆为，故是自反的，不是反自反的；---------------------------------------2 因为对称矩阵，故是对称的；-------------------------------------------------------------1 因，故不是反对称的；----------------------------------------------1 又因，但，故无传递性．----------------------------2 五、问答计算题 设R是实数集，R上的二元运算*定义为：a*b=a+b+ab， 问R,*是独异点吗？并写出其么元和零元． 答：由于实数经加法和乘法运算后，其运算结果仍为实数， 所以运算*对于R是封闭的；----------------------------------------------------------------------2 由于a*b=a+b+ab=a(b+1)+(b+1)?1=(a +1) (b+1)?1 从而有(a*b)*c=((a +1)(b+1)?1)*c =(((a +1)(b+1)?1)+1)(c+1)?1=(a +1)(b+1)(c +1)?1 a*(b*c)=a*((b +1)(c+1)?1)=(a +1)(((b +1)(c+1)?1)+1)?1=(a +1)(b+1)(c +1)?1 于是 (a*b)*c=a*(b*c)，所以*是可结合运算；--------------------------