离散数学总复习.doc

szniubupt.edu.cn离散数学总复习一、判断题（如果下列命题为真,在题后的括号内记/, 否则记）（1） （ ）正确（2）如果，则或 （ ）错误（3）空集是任何集合的真子集 （ ）错误； （4）如果，则 （ ）错误；（5）设集合，则 （ ）错误（6）设集合，则 是到的关系 （ ）正确（7）设 都是有限集，则总共可以定义个不同的到的映射 （ ）正确（8）设是集合上的等价关系, 则当时， （ ）正确 （9）设是集合，则是可结合的 （ ）正确（10）单位元是可逆的 （ ）正确（11）设是群的元素，则对，有 （ ）错误（12）设是布尔代数，则对任意，有 （ ）正确（13）设图是连通的，则任意指定的各边方向后所得的有向图是弱连通的 （ ）正确（14）不论无向图或有向图，初级回路一定是简单回路 （ ）正确 （15）有向哈密尔顿图是强连通的 （ ）正确（17）设都是命题公式，则的充分必要条件为 （ ）正确（18）命题公式是重言式 （ ）正确（19）设都是谓词公式，则是永真式 （ ）正确（20）“张明和张亮是兄弟”是复合命题，因为该命题中出现了联结词“和” （ ）错误二、填空题（1）设集合中元素的个数分别为，且，则集合中元素的个数 3（2）设集合，则中元素的个数为 .（4）集合上的二元关系为传递的充分必要条件是 （5）循环群的所有子群为 ， （6）设是群，为单位元，若元素满足，则 . （7）在整数集合上定义运算为，则的单位元为 .-2（8）代数系统中（其中为整数集合，+为普通加法），对任意的，其 .（9）为了从（n，m）连通无向图得到一棵生成树，必须删除G的 条边 m-n1（15）阶完全图的任意两个不同结点的距离都为 1（16） 设的真值为0，的真值为1，则命题公式的真值为 .0（17）设天下雨， 我骑自行车上班，则命题“如果天不下雨, 我就骑自行车上班”符号化为 .（18）设经一事, 长一智，则命题：不经一事, 不长一智符号化为 （19）设是自然数，是奇数，是偶数，则命题“任何自然数不是奇数就是偶数。” 符号化为 .（20）设是金子，是发光的，则命题“金子是发光的, 但发光的不一定是金子”符号化为 . 三、选择题（每题后面有四个选项，四个选项中只有一个是正确的，请将正确的所对应的字母填在括号内）（1）设为实数集合，下列集合中哪一个不是空集 （ ）A. B C. D. 答案 A（2）设为集合，若，则一定有 （ ）A. B C. D. 答案 C（3）下列各式中不正确的是 （ ）A. B C. D. 答案 C（4）设，则下列各式中错误的是 （ ）A. B C. D. 答案 B答案 B（5）设上的二元关系如下，则具有传递性的为 （ ）A. B C. D. 答案 D（6）在整数集上，下列哪种运算是可结合的 （ ）A. B C. D. 答案 B（7）设集合，下面定义的哪种运算关于集合不是封闭的 （ ）A. B C. ，即的最大公约数D. ，即的最小公倍数答案 D（8）设是有理数集，在定义运算为，则的单位元为 （ ）A. ； B； C. 1； D. 0答案 D（11）在任何图中必有偶数个 （ ）A. 度数为偶数的结点； B度数为奇数的结点； C. 入度为奇数的结点； D. 出度为奇数的结点.答案 B.（12）设为有个结点的无向完全图，则的边数为 （ ）A. B C. D. 答案 C.（13）给定下列序列，哪一个可构成无向简单图的结点度数序列 （ ）A. BC. D. 答案 B（14）任何无向图中结点间的连通关系是 （ ）A. 偏序关系； B等价关系；C. 既是偏序关系又是等价关系； D. 既不是偏序关系也不是等价关系.答案 B.（15）有向图，其中，则有向图是 （ ）A. 强连通图； B单向连通图；C. 弱连通图； D. 不连通图.答案 C.（16）下面哪个联结词不可交换 （ ）A. ； B； C.； D. .答案 B.（17）命题“没有不犯错误的人”符号化为(设是人,犯错误) （ ）A. ； B.；C. ； D.答案 D.（18）设个体域，公式在上消去量词后应为 （ ）A. ； B. ；C. ； D. .答案 B.（19）在谓词演算中，下列各式中，哪一个是正确的 （ ）A.； B.；C.； D.答案 B.（20）“学习有如逆水行舟，不进则退”。设学习如逆水行舟，学习进步，学习退步。则命题符号化为 （ ）A. ； B； C. ； D. .答案 B.四、求解下列各题1设集合 , 是上的整除关系, 画出的哈斯图。解答 8 4 6 9 5 2 3 7 12. 设集合, 是上的整除关系,(1) 画出的哈斯图。；(2) 求集合的上界、下界、最小上界和最大下界。解：（1）的哈斯图为 24 36 12 6 2 3 上界为12,24,36，最小上界为12下界为2,3,6，最大下界为63在下面的无向图中，回答下列问题 （1）写出之间的所有初级通路； （2）写出之间的所有短程，并求； （3）判断无向图是否为欧拉图并说明理由。解：（1）之间的所有初级通路共有7条，分别为，（2）之间的长度最短的通路只有1条，即，因而它是之间唯一的短程，（3）由于无向图中有两个奇度顶点，所以无向图没有欧拉图回路，因而不是欧拉图。4. 判断下列图中，哪个无欧拉通路？哪个有欧拉通路但无欧拉回路？哪个是欧拉图？ a a b e a b b d c d c d c （1） （2） （3） 解 由于（1）只有两个奇度结点，b,e. 因此，(1)有欧拉通路，但无欧拉回路。非欧拉图。 由于（2）无奇度结点，因此，（2）是欧拉图。 由于（3）有4个奇度结点，因此，（3）无欧拉通路，非欧拉图。5. 下面的图形中，哪个没有哈密尔顿通路？哪个有哈密尔顿通路但无哈密尔顿回路？哪个是哈密尔顿图？ a a a b e b b d c d e c c d f e （1） （2） （3） 解 （1）中有哈密尔顿回路，例如 abcdea，（1）是哈密尔顿图；（2）中无哈密尔顿回路，也无哈密尔顿通路，不是哈密尔顿图。（3）中有哈密尔顿通路，例如 badce，无哈密尔顿回路，不是哈密尔顿图。6.设有向图，其邻接矩阵为（1） 画出有向图；（2） 写出有向图的可达矩阵；（3） 找出从结点出发到长度为3的所有通路.解答：（1）有向图为 （2） 有向图的可达矩阵为（3） 从结点出发到长度为3的所有通路有两条 和 五、构造下列推理的证明1. 证明 证明 前提引入 化简规则 前提引入 假言推理 前提引入 析取三段论2. 证明 证明 前提引入； 前提引入； 拒取式； 前提引入； 假言推理； 前提引入； 拒取式； 前提引入； 析取三段论。3. 证明 ， 证明： 前提引入； 量词否定等值式； 存在量词消去规则； 前提引入； 全称量词消去规则； 析取三段论； 前提引入； 全称量词消去规则； 拒取式； （10） 存在量词引入规则4. 证明 ， 证明： 前提引入； 存在量词消去规则； 化简规则； 前提引入； 全称量词消去规则； 假言推理规则； 全称量词消去规则； 置换； 化简规则； （10） 全称量词消去规则； （11） （10）假言三段论规则；（12） （11）全称量词引入规则；5. 所有的有理数都是实数，有的有理数是整数。因此有的实数是整数。解：设 是有理数，是实数，是整数。前提：结论：证明： 前提引入； EI规则； 化简； 化简； 前提引入； UI规则； 假言推理； 合取引入； EG规则6.“所有的舞蹈家都很有风度，王英是个学生并且是个舞蹈家，因此有些学生很有风度。”在一阶逻辑中证明以上推理是正确的。解：记是舞蹈家，有风度，是学生， 王英.则上述推理符号化为前提：，结论：证明： 前提引入； 全称量词消去规则； 前提引入； 化简规则； 假言推理规则； 化简规则； 合取引入； 存在量词引入规则；六、证明题1. 设为集合上的自反关系, 试证是传递且对称的充分必要条件是：对任意，当时有是.证明：充分性对任意元素，当时，由于为集合上的自反关系,因此有，根据题设，由，和，可得，即是对称的。当时，由是对称的，可得，根据题设可得，即是传递的。必要性对任意元素，当时，由于是对称的，则有，从而由并且以及是传递的，得到.2. 设是一个群，取定，定义 ， 证明是一个群。证明 显然，*是上的二元运算。先证结合律成立。，有 即运算是可结合的.由于，有 故是运算*的单位元. 最后证明，是在中的逆元。由于因此是一个群.