离散数学考试试题与答案-1.docVIP

二、（8分）个体域为{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 四、（10分）已知A={1,2,3,4,5}和R={1,2,2,1,2,3,3,4,5,4}，求r(R)、s(R)和t(R)。 解：r(R)={1,2,2,1,2,3,3,4,5,4,1,1,2,2,3,3,4,4,5,5} s(R)={1,2,2,1,2,3,3,4,5,4,3,2,4,3,4,5} t(R)={1,2,2,1,2,3,3,4,5,4,1,1,1,3,2,2,2,4,1,4} 五、(10分) 75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元，公园游乐场总共收入70元，求有多少儿童没有乘坐过其中任何一种。 解 设、、分别表示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合，|∩∩|＝20，|∩|＋|∩|＋|∩|－2|∩∩|＝55，||＋||＋||＝70/0.5＝140。 由容斥原理，得 |∪∪|＝||＋||＋||―|∩|―|∩|―|∩|＋|∩∩| 所以 |∩∩|＝75－|∪∪|＝75－(||＋||＋||)＋(|∩|＋|∩|＋|∩|－2|∩∩|)＋|∩∩|＝75－140＋55＋20＝10 没有乘坐过其中任何一种的儿童共10人。 九、（10分）已知：D=V,E，V={1,2,3,4,5}，E={1,2,1,4,2,3,3,4,3,5,5,1}，求D的邻接距阵A和可达距阵P。 解：D的邻接距阵A和可达距阵P如下： 0 1 0 1 0 1 1 1 1 1 0 0 1 0 0 1 1 1 1 1 A= 0 0 0 1 1 P= 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 一、（10分）求命题公式?(P∧Q)??(?P?R)的主合取范式。 解：?(P∧Q)??(?P?R)?（?(P∧Q)??(?P?R)）∧（?(?P?R)??(P∧Q)） ?（(P∧Q)∨(?P∧?R)）∧（(P∨R)∨(?P∨?Q)） ?(P∧Q)∨(?P∧?R) ?(P∨?R)∧（Q∨?P）∧（Q∨?R） ?(P∨Q∨?R)∧(P∨?Q∨?R)∧（?P∨Q∨R）∧（?P∨Q∨?R） ?M1∧M3∧M4∧M5 五、(10分) 设A＝{a，b，c，d}，R是A上的二元关系，且R＝{a，b，b，a，b，c，c，d}，求r(R)、s(R)和t(R)。 解 r(R)＝R∪IA＝{a，b，b，a，b，c，c，d，a，a，b，b，c，c，d，d} s(R)＝R∪R-1＝{a，b，b，a，b，c，c，d，c，b，d，c} R2＝{a，a，a，c，b，b，b，d} R3＝{a，b，a，d，b，a，b，c} R4＝{a，a，a，c，b，b，b，d}＝R2 t(R)＝＝{a，b，b，a，b，c，c，d，a，a，a，c，b，b，b，d，a，d} 十、(10分)求叶的权分别为2、4、6、8、10、12、14的最优二叉树及其权。 解：最优二叉树为 权＝(2+4)×4+6×3+12×2+(8+10)×3+14×2＝148 3、（5分）树T有2个4度顶点，2个3度顶点，其余顶点全是树叶。问T有几片树叶？ 解、设T有x片树叶, n个顶点，m条边 n=2+2+x，m=n-1= 4+x-1 ，由握手定理2′(4+x-1)=2′4+2′3+x×1 解得x=8，故T有8片树叶. 2、（5分）设有向简单图D的度数序列为2、2、3、3,入度序列为0、0、2、3，试求D的出度序列和该图的边数，并在图4中画出该有向图。 解：出度序列为2、2、1、0边数m=（2+2+3+3）/2=5 解：出度序列为 2、2、1、0 边数m=（2+2+3+3）/2=5 2、写出对应下面推理的证明： 如果今天是星期一，则要进行英语或离散数学考试。如果英语老师有会，则不考英语。今天是星期一，英语老师有会。所以进行离散数学考试。（其中p：今天是星期一；q：进行英语考试；r：进行离散数学考试；s：英语老师有会。） 前提：p→（q∨r），s→┐q，p，s 结论：r 证明：①p→（q∨r） 前提引入 ②p 前提引入 ③q∨r ①②假言推理 ④s→┐q 前提引入 ⑤s 前提引入 ⑥┐q ④⑤假言推理 ⑦r ③⑥析取三段论 1、=，