离散数学（2015）复习题
一、填空题
1 设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A– B＝____{3}______;
P(A) – P(B)＝ ____{{1,3}，{2,3}，{1,2,3}，{3}_}_________ . 2. 设有限集合A, |A| = n, 则 |P(A×A)| = _______2n2_________________. 3. 设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是
{
G＝?(p?q)∧r，则
G
的主析取范式是
________________________________________________________________________ 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为___12_______，分枝点数为_________3_______.
6 设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_______________________; A?B＝_________________________;A－B＝ _____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个性质是
______________________, ________________________, _____________________. 8. p：你努力，q：你失败。“除非你努力，否则你将失败”的符号化为为 ?q? p ；
“虽然你努力了，但还是失败了”的符号化为为 p∧q
9. 设集合A＝{1,2,3,4}, A上的关系R1 = {<1,4>,<2,3>,<3,2>}, R1 =
{<2,1>,<3,2>,<4,3>}, 则 R1?R2 = __________________,R2?R1__________________, R12 =______________.
10. 设有限集A, B，|A| = m, |B| = n, 则| |P(A?B)| = _____________________________. 11 n个结点的无向完全图Kn的边数为 ，欧拉图的充要条件是
。 12.命题公式p→q的真值为假，当且仅当_______。
13. 设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设树T有m个顶点，n条边，则T中顶点与边的关系为_______________。 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。 16. 设谓词的定义域为{a, b},将表达式?xM(x)→?xF(x)中量词消除，写成与之对
应的命题公式是___________________________________________________.
17. 含10个顶点的完全图删掉 条边使之成为树。
18. 设G是连通平面图，有5个顶点，6个面，则G的边数是 二、1.权数1，4，9，16，25，36，49，64，81，100构造一棵最优二叉树。
2. 一颗二叉树如图，用中序行遍法还原逻辑表达式
3.设集合A={ a ,b , c , d }上关系R={< a, b > , < b , a > , < b , c > , < c , d >} 要求 1、写出R的关系矩阵和关系图。2、R所具有的性质。
4.举出集合A上的既是等价关系又是偏序关系的一个例子。( ) 答：A上的恒等关系 5、P→Q
解：P→Q??P?Q（主合取范式）
?(?P?(Q??Q))?((?P?P)?Q)
?(?P?Q)?(?P??Q)?(?P?Q)?(P?Q) ?(?P?Q)?(?P??Q)?(P?Q)（主析取范式）
6、 P??Q
解： P??Q （主合取范式）
?(P?(?Q?Q))?((?P?P)??Q） ?(P??Q)?(P?Q)?(?P??Q)?(P??Q） ?(P??Q)?(P?Q)?(?P??Q)（主析取范式）
7、P?Q
解：P?Q（主析取范式）?(P?(Q??Q))?((P??P)?Q)
?(P??Q)?(P?Q)?(P?Q)?(?P?Q) ?(P??Q)?(P?Q)?(?P?Q)（主合取范式）
8、设A={1,2,3},写出下列图示关系的关系矩阵，并讨论它们的性质：
?000???101???100??;它是反自反的、反对称的、传递的； （1）R={<2,1>,<3,1>,<2,3>};MR=??011????101??110??;它是反自反的、对称（2）R={<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>};MR=?的；
?011????100??001??;它既不是自反的、反自反的、也不（3）R={<1,2>,<2,1>,<1,3>,<3,3>};MR=?是对称的、反对称的、传递的。
9、设A={1,2,…,10}。下列哪个是A的划分？若是划分，则它们诱导的等价关系是什么？ （1）B={{1,3,6},{2,8,10},{4,5,7}}; （2）C={{1,5,7},{2,4,8,9},{3,5,6,10}}; （3）D={{1,2,7},{3,5,10},{4,6,8},{9}} 解：
（1）和（2）都不是A的划分。 （3）是A的划分。其诱导的等价关系是
IA?{<1,2>,<2,1>,<1,7>,<7,1>,<2,7>,<7,2>,<3,5>,<5,3>,<3,10>, <10,3>,<10,5>,<5,10>,<4,6>,<6,4>,<4,8>,<8,4>,<6,8>,<8,6>}。
10、R是A={1,2,3,4,5,6}上的等价关系，
R=IA?{<1,5>,<5,1>,<2,4>,<4,2>,<3,6>,<6,3>} 求R诱导的划分。 解：
R诱导的划分为{{1,5},{2,4},{3,6}}。 11.设A={1，2，3，4，5}，A上的偏序关系的哈斯图为
求A的子集{3，4，5}和{1，2，3}，的上界，下界，上确界和下确界。（6分）
12.设集合A＝{1, 2, 3, 4, 6, 8, 9, 12}，R为整除关系。
(1) 画出偏序关系R的哈斯图；
(2) 写出A的子集B = {3,6,9,12}的上界，下界，最小上界，最大下界；
(3) 写出A的最大元，最小元，极大元，极小元。 （1）
842112639
(2) B无上界，也无最小上界。下界1, 3; 最大下界是3. (3) A无最大元，最小元是1，极大元8, 12, 90; 极小元是1. 13、个体域为{1，2}，求?x?y（x+y=4）的真值。
解：?x?y（x+y=4）??x（（x+1=4）∨（x+2=4））
?（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+1=4）） ?（0∨0）∧（0∨1）
?1∧1?0
14、已知集合A和B且|A|=n，|B|=m，求A到B的二元关系数是多少？A到B的函数数是多少？
解：因为|P(A×B)|=2|A×B|=2|A||B|=2mn，所以A到B的二元关系有2mn个。因为|BA|=|B||A|=mn，所以A到B的函数mn个。
15、叙述并证明苏格拉底三段论
解：所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。 符号化：F（x）：x是一个人。G（x）：x要死的。a：苏格拉底。 前提：?x（F（x）?G（x）），F（a） 结论：G（a） 证明：
（1）?x(F(x)?G(x)) 前提引用 （2）F(a)?G(a) （3）F(a) 前提引用 （4）G(a)
20 设n阶无向简单图为3-正则图，且边数m与n满足2n-3=m
问：求m,n并判断这样的无向图有几种非同构的情况，并画出来。
?3n?2m解：? 得n=6,m=9.
2n?3?m?
离散数学复习题
