离散测试卷.doc
如有侵权，请联系网站删除，仅供学习与交流离散测试卷【精品文档】第 6 页一、选择题 (每小题 2 分，共 20分)1、已知图G的相邻矩阵为 则G有（ ）。 A、 5点，8边 B、 6点，7边 C、5点，7边 D、 6点，8边2、一个公式在等价意义下，下面哪个写法是唯一的（ ）。A、析取范式 B、合取范式 C、主析取范式 D、以上答案都不对3、下列命题正确的是（ ）。A、fÇf=f B、fÈf=f C、aÎa，b，c D、fÎa，b，c4、设（A，£）是偏序集，则A（ ）。A、必有最大元和极大元 B、不一定有最大元，肯定有极大元 C、不一定有极大元，肯定有最大元D、不一定有最大元，不一定有极大元5、设p:王华努力学习，q:王华取得好成绩，命题“如果王华努力学习，她取得好成绩” 的符号化形式为（ ）。 A、 q p B、 p q C、 p q D、 p q6、设图G是有6个顶点的连通图，总度数为20，则从G中删去（ ）边后所得连通图能成为一棵树。 A 、10 B、5 C、 4 D、27、设集合A中有4个元素，则在集合A上可以有多少种不同的关系？（ ） A、216 B、 28 C、24 D、 228、设X=a,b,c,IX是X上的恒等关系，要使IX<a,b>,<b,c>,<c,a>,<b,a>R为X上的等价关系，R应取（ ） A、<c,a>,<a,c> B、<c,b>,<b,a> C、<c,a>,<b,a> D、<a,c>,<c,b>9、下列语句中是命题的只有（ ） A、1+1=11 B、x+y=10 C、sinx+siny<0 D、今天天气多好！ 10、设I是如下一个解释，则在解释I下取真值为1的公式是（ ）。 ),(、);,(、);,(、);,(、yxyPxDxxxPCyxyPxByxyPxA$"""""$二、填空题 (每小题 3 分，共 15分)1、命题公式G=（PÙQ）®R，则G共有 个不同的解释；把G在其所有解释下所取真值列成一个表，称为G的 ；解释（ØP，Q，ØR）或（0，1，0）使G的真值为 。*abcdaabcdbbcdaccdcbddabc2、设代数系统为（S，*），S=a,b,c,d，运算*定义 如下表，则（S，*）的幺元为 ， 等幂元为 。3、设，是汽车，比快，则“每一列火车都比某些汽车快。”可符号化为 。4、设集合A=a, b, c, d ，A上关系R <a,a>,<a,c>,<b,d>,<d,a>, 则关系RoRc = 。5、序偶（a,b）=(x,y)的充分条件是 。三、证明题 (1，2每小题 5 分，3题10分，共 20分)1、设H，*和K，*都是群G，*的子群，试证明HK，*也是G，*的子群。（5）长江大学试卷 院（系、部） 专业 班级 姓名 学号 .密封.线.2、证明蕴涵（5）3、任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或者喜欢乘汽车或者喜欢骑自行车。有的人不爱骑自行车，因而有的人不爱步行。写出相应的谓词公式。 并证明其结论。（10）四、计算题 (1，2，3,5每小题 10 分，4题5分，共 45分)1、设集合，试求： 1）A×B 2）从A到B的所有函数，并指出哪些是入射函数。2、设*是实数集R上的运算，其定义如下： a*b=a+b+2ab 1)求2*3，3*（-5）和7*1/2。 2)<R，*>是半群吗？*可交换吗？ 3)求R中关于*的幺元（单位元）。4)R中哪些元素有逆元，逆元素是什么？长江大学试卷 院（系、部） 专业 班级 姓名 学号 .密封.线.3、设集合P=x1，x2，x3，x4，x5上的偏序关系如图所示，找出P的最大元素，最小元素，极小元素，极大元素。找出子集x2，x3，x4， x3，x4，x5和x1，x2，x3的上界、下界，上确界、下确界。 4、设有5个城市v1，v2，v3，v4，v5，任意两城市之间铁路造价如下：（以百万元为单位）w（v1，v2）=4， w（v1，v3）=7， w（v1，v4）=16， w（v1，v5）=10， w（v2，v3）=13， w（v2，v4）=8， w（v2，v5）=17， w（v3，v4）=3， w（v3，v5，）=10， w（v4，v5）=12试求出连接5个城市的且造价最低的铁路网。 5、设图G如下图所示，求可达性矩阵P。P1P2P3P5P4一、选择题（2X10=20） 1、A 2、C 3、A 4、B 5、B 6、B 7、A 8、D 9、A 10、D二、填空题（3X5=15）1、8；真值表；1或者真2、a；a、c3、4、<a，a>，<b，b>，<a，d>，<d，a>，<d，d>5、a=x，b=y三、证明题（20）1、(5)证明：设任意的a，b HK，因为H，*和K，*都是群G，*的子群，所以b-1HK，由于*在H和K中的封闭性，所以a* b-1HK，由定理，既得HK，*也是G，*的子群。2、(5)证明： PQ P P -> R I P -> Q I R -> S P QR P P -> S I Q -> R I3、(10)证明：Q（x）：x喜欢步行，R（x）：x喜欢乘汽车，I（x）：x喜欢骑自行车 则相应谓词公式为：（）（Q（x）->R（x）（）（R（y）I（y） （）I（z）（） Q（u） （）I（z） P （）（Q（x）->R（x） P I（a） ES Q（a）->R（a） US （）（R（y）I（y） P Q（a） I R（a）I（a） US （） Q（u） EG R（a） I四、计算题（45）1、(10) 解：1）A×B=（0，a），（0，b），（0，c），（1，a），（1，b），（1，c） (4) 2）f 1= （0，a），（1，a） f 6=（0，b），（1，a） f 2=（0，b），（1，b） f 7=（0，b），（1，c） f 3=（0，c），（1，c） f 8=（0，c），（1，a） f 4=（0，a），（1，b） f 9=（0，c），（1，b） f 5=（0，a），（1，c） (4) 其中f 4、f 5、 f 6、 f 7、f 8、f 9是入射函数。 (2)2、(10) 解：1) 2*3=17，3*（-5）=-32，7*1/2=14.5 (3) 2)运算*在R上是封闭的。 对任意a，b，cR， (a*b)*c=(a+b+2ab)*c=a+b+2ab+c+2(a+b+2ab )c =a+b+c+2ab+2ac+2bc+4abc a*(b*c)=a*(b+c+2bc)=a+b+c+2bc+2a(b+c+2bc) =a+b+c+2ab+2ac+2bc+4abc 所以(a*b)*c= a*(b*c)。因此<R，*>是半群。*可交换。(3) 3)R中关于*的幺元是0。(2) 4)R中除-1/2外所有元素都有逆元，a的逆元素是-a/（1+2a）。(2)3、（10） 解： P的最大元素为x1 ，无最小元素，极小元素为x4，x5 ，极大元为素x1 。 其余见下表。 子 集 上 界 下 界 上 确 界 下 确 界x2，x3，x4x3，x4，x5 x1，x2，x3 x1 x1 ， x3 x1 x4 无 x4 x1 x3 x1 x4 无 x44、（5） 解：该题即为求整个铁路的最小生成树，可得如下：5、（10）解： 0 1 0 0 0A= 0 0 0 1 01 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0A2= 0 0 0 0 10 1 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 1A3= 0 1 0 0 00 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0A4= 0 0 0 1 00 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 1 0A5= 0 0 0 0 10 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 1 0 1 1P= A A2 A3 A4 A5 = 0 1 0 1 11 1 0 1 1 0 1 0 1 1 0 1 0 1 1
