离散数学试卷(一).doc

离散数学试卷(一)试题一：单项选择题 (共10 分，每题 2 分) 、设，则下列命题错误的是（ ）A CA、下列语句中，（）是命题请把门关上 x +2=5火星上有生命 下午开会吗？、下列四个图中，单向连通但不是强连通的图是（） B. 、下述性质中，不是等价关系所要求的是（）自反性对称性反对称性传递性、设A=1，2，3，A上的二元关系,，则具有（）自反性对称性反对称性传递性试题二：填空题(共 20 分，每空 2 分) 1、设A=1，2，3，B=2，3，4，则AB 2，3 ，AB= 1 2、设p表示“张三获得冠军”，q表示“李四获得亚军”，则命题“如果张三获得冠军，则李四获得亚军”可符号化为 p-q ；命题“张三获得冠军，而李四获得亚军”可符号化为 p q 、设A , B是任意两个集合，以A中元素作第一元素，B中元素作第二元素生成的所有有序对的集合称为A , B的 笛卡儿积 ，记作AB AB的任何子集R称为 A 到B 的一个二元关系 、设R是非空集合A上的二元关系，若R具有自反性、 反对称性 和 传递性 ，则称R是A上的偏序关系、设G为图如果G是 无向图 并且 连通无圈 ，则称G是树试题三：计算题(共 30 分，每题 6分) 、 利用辗转相除法求180和105的最大公因数和最小公倍数180 = 105 * 1 + 75105 = 75 * 1 +3075 = 30 * 2 +1530 = 15 * 2 最大公约数是15最小公倍数是180*105/15 = 1260、设解释I：个体域,谓词表示:,表示:是素数分别求下述两个谓词公式在解释I下的真值: (1)； =（P(2) Q(2)） (P(3) Q(3) (P(4) Q(4) (P(5) Q(5) (P(6) Q(6) (P(7) Q(7)=(1 1) (1 1) (0 0) (0 1) (0 0) (0 1)=1 1 0 0 0 0 =1(2) =(P(2)-Q(2) (P(3)-Q(3) (P(4)-Q(4) (P(5)-Q(5) (P(6)-Q(6) (P(7)-Q(7)=(1-1) (1-1) (0-0) (0-1) (0-0) (0-1)=1 1 1 1 1 1=1、 设树T有2个5度结点,2个4度结点,2个2度结点,其余全为树叶问T有几个结点？ 解：设T有x个节点 边的条数为：x-1 树叶的个数为：x-（2+2+2）=x-6 由握手定理知：2*5+2*4+2*2+1*（x-6） = 2（x-1）解得：x=18故，T有18个节点。、 假设在通信中，字符A，B，C，D，E，F出现的频率分别为30%,25%,20%,10%,10% ,5%，求传输它们的最优二元前缀码1由题意知： 2最优二叉树100% 30% 25% 20% 10% 10% 5%55%45% -30%25%25%20%30% 25% 20% 10% 15%10%15% - C 30% 25% 20% 25% B B A10%5% - D30% 25% 45% F E- 55% 45% 3前缀码是：A ：11、B：10 、C：00 100% D：010、E：0111、F：0110、设，R为A上的偏序关系，其Hasse图如下图所示求关系R bcdeaR=、试题四：综合题(共 30分，每题10 分) 、 列出下述命题公式的真值表,并由真值表求出其主析取范式及主合取范式:成假赋值为：001、011、100、101、1113极大项为：M1=-p-qr M3=-pqrM4=p-q-r M5=p-qrM7=pqr4主合取范式：M1M3M4M5M7=(1,3,4,5,7)5主析取范式：（0，2，6）=m0m2m6=(-p-q-r)(-pq-r)(pq-r) 1真值表 2成假赋值 0 1 0 1 1 0 0 1 0 0 0 1 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 0 1 0 1 0 0 0 0 1 1 1 1 1 1 0 1 1 1 0 0 1、设A上的关系）求R ，并写出R的矩阵表示；R = 、 1 1 11 1 00 0 0 R = ）求的自反闭包r(R)、对称闭包及传递闭包.r（R）=RIA=、s（R）=、t ( R ) = RR2R3 、有向图G如下图所示:v4v31(1) 写出图G的邻接矩阵A.0 3 2 21 2 1 10 0 1 11 3 2 1(2) 问G中到的长为3的有向通路有多少条？为什么？并写出所有这样的通路A3 = 试题五 证明题 (共 10分，每小题5分) 证明下列两个推理是有效的 1、 前提: pq,sp ,s结论: