计算机数学基础—复习题

数理逻辑练习一、 证明下面推理1） 前提：p(q(sr),sp 结论：2） 前提：x(F(x)G(x)，x(G(x)R(x)，xR(x)结论：x(F(x) 3) 前提：x(F(x)(G(a)H(x)，x F(x)结论：x (F(x)H(x)二、在谓词逻辑中，构造下面推理的证明:1、每个有理数都是实数，有的有理数是整数，因此有的实数是整数。2、任何人，如果他喜欢步行，他就不喜欢乘汽车。每一个人或者喜欢乘汽车，或者喜欢骑自行车。并非每个人都喜欢骑自行车。因此，有的人不爱步行。（个体域为人类集合）3) 如果2是偶数，则3是奇数。或者2是偶数或者2整除3，结果2整除3，所以3不是奇数。4) 如果A努力工作，那么B或C感到愉快；如果B愉快，那么A不努力工作；如果D愉快那么C不愉快。所以，如果A努力工作，则D不愉快。三、求下列命题公式的主析取范式和主合取范式，并求其成真赋值。1） P®(Q®R)2）3） 4） (ØPØQ)®(P«ØQ)四、求下列各公式的前束范式1）2）五、构造下列命题公式的真值表，并据此说明哪些是其成真赋值，哪些是其成假赋值？1） P(QR)。2） Ø(PQ)«(ØPØQ)。六、分别用真值表法和公式法判断下列命题公式的类型：(1)(PQ)®(PQ)。(3)(ØPQ)Ø(QØR)Ø(RØPØQ)。(5)(Q®P)(ØPQ)。集合论练习1.给定自然数集N的子集：A1，3，7，8，Bi|i230 ，Ci|i可以被3整除且0i20。求下列集合：(1)AB(2)BC。(3)B(AC)。(4)BC2、已知ABAC，ABAC，请用集合恒等式证明BC。 3.求由数字1、2、3、4、5、6组成的四位数(每个数字都不允许重复出现)中，数字2在5前面的四位数共有多少个？4. 求1到2500之间能被2，3，5和7中任何一个数整除的整数个数。5、今有111人购买A,B,C三种股票，已知只买了一种股票的共75人，买了A股和B股的共有20人，买了B股和C股的共有9人，买了A股和C股的共17人，只买A股的共31人，只买B股的共23人。试求：（10分）1） 三种股票都买的有几人？2） 买A股、B股和C股的各几人？关系练习1.设A1，2，构造集合P(A)×A。2.设R<0，2>，<1，1>，<1，2>，<2，0>，求DR、RR、R1、R1、RÆ、RÆ、RÆ和RÆ。3.证明RABRARB。4.设X1，2，3，4，R是X上的二元关系，R<1，2>，<2，2>，<2，1>，<3，3>，<3，1>，<4，3>，<4，1> (1)画出R的关系图。(2)写出R的关系矩阵。(3)说明R是否是自反、反自反、对称、传递的。5.令A=1,2,3;B=a,b,求R1=<1,a>,<1,b>,<2,b>,<3,a>的关系矩阵。6.令A=1,2,3;求R2=<1,1>,<1,3>,<2,1>,<3,2>的关系图。7.令F=<1,2>,<2,3>,<3,1>,<1,3>，G=<2,1>,<2,2>,<2,3>,<1,4>求F*G, G*F, F*F8.设集合A=a, b, c ,d上的二元关系R=<a, a>, <a, b>, <b, a>, <c, d>,<d, a>1） 试分析指出R所具有的性质（即是否具有自反性，反自反性，对称性，反对称性，传递性这五种性质）2） 求R0，R2，r(R)，s(R)，t(R)的集合表达式。9.设A=í1,2,3,4,5ý，A上的等价关系R定义为：R=í<1,2>,<2,1>,<3,4>,<4,3>ýIA画出关系图，找出所有等价类。10.求出下列各偏序集<A,>的盖住关系COV A，画出哈斯图，找出A 的子集B1、B2和B3的极大元、极小元、最大元、最小元。A=ía,b,c,d,eý，=í<a,b>,<a,c>,<a,d><a,e>,<b,e>,<c,e><d,e>ýIAB1=íb,c,d ý，B2=ía,b,c,d ý，B3=íb,c,d,eý A=P(ía,b,cý)，=í<x,y>½ xÎP(A)yÎP(A)xÍy ýB1=íÆ,íaý,íbýý，B2=ííaý,ícýý，B3=íía, cý,ía,b,cýý线性代数练习1. 若，求x。2设齐次线性方程组 只有零解， 则满足条件？3.计算行列式4. 计算行列式5. 设A=，B=.求（1）ABT；（2）|4A|. 6. 7. 求下列非齐次方程组的通解8.设A=,且矩阵A,X满足AX=A+X,求矩阵X9.10. 设11.编写矩阵乘法函数 void multi_matrix(int aMS,int bSN,int cMN); 并用主函数调用，验证12.求矩阵的秩13.求逆矩阵14.当时， 下面的向量组线性相关：，.15. 已知向量，则当时， 线性相关。16. 已知向量组，则该向量组的秩是？17. 向量组，线性相关， 则实数18. 设向量，则向量可表示为，的线性组合是？图论练习1.判断下列各非负整数列哪些是可图化的？哪些是可简单图化的？(1)(1，1，1，2，3)。(2)(2，2，2，2，2)。(3)(3，3，3，3)。(4)(1，2，3，4，5)。(5)(1，3，3，3)。2.有向图D如图10-51所示：(1)求D的邻接矩阵A。(2)D中v1到v4长度为4的路有多少？(3)D中v1到自身长度为3的回路有多少？(4)D中长度为4的路数为多少？其中有几条回路？(5)D中长度小于等于4的路有多少？其中有多少条回路？(6)D是哪类连通图？3. 如下图所示的赋权图表示某七个城市及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。4. 如下图所示的赋权图表示某六个城市a,b,c,d,e,f及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。5. 在二叉树中1） 求带权为2，3，5，7，8的最优二叉树T。2） 求T对应的二元前缀码。6. 用Huffman算法求带权为1，2，3，5，7，9最优二叉树，并计算其权值。 7. 一棵无向树T有8个顶点，4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有几片树叶？8. 一棵树的3个4度点，4个2度点，其它的都是1度，那么这棵树的边数是多少？