离散数学期末考试试题有几套带答案

离散试卷及答案第1页共22页离散数学试题A卷及答案）一、证明题（10分）1PQRQRPRR证明左端PQRQPRPQRQPRPQRQPRPQQPRPQPQRTR置换R2XAXBXXAXXBX证明XAXBXXAXBXXAXXBXXAXXBXXAXXBX二、求命题公式PQRPQR的主析取范式和主合取范式（10分）证明PQRPQRPQRPQR（PQR）PQRPQPRPQRPQRPQRPQRPQRPQRM0M1M2M7M3M4M5M6三、推理证明题（10分）1）CD,CDE,EAB,ABRSRS证明1CDE2EAB3CDAB4ABRS5CDRS6CD离散试卷及答案第2页共22页7RS2XPXQYRX，XPXQYXPXRX证明（1）XPX2PA3XPXQYRX4PAQYRA5QYRA6QY7RA8PA9PARA10XPXRX11QYXPXRX四、设M是一个取定的正整数，证明在任取M1个整数中，至少有两个整数，它们的差是M的整数倍证明设，为任取的M1个整数，用M去除它们所得余1A21A数只能是0，1，M1，由抽屉原理可知，这M11A2A个整数中至少存在两个数和，它们被M除所得余数相同，因此和STS的差是M的整数倍。TA五、已知A、B、C是三个集合，证明ABCABAC（15分）证明XA（BC）XAX（BC）XA（XBXC）（XAXB）（XAXC）X（AB）X（AC）X（AB）（AC）A（BC）（AB）（AC）六、已知R、S是N上的关系，其定义如下R|X,YNYX2，S|X,YNYX1。求R1、RS、SR、R1,2、S1,2（10分）解R1|X,YNYX2，RS|X,YNYX21，SR|X,YNY（X1）2，七、若FAB和GBC是双射，则（GF）1F1G1（10分）。离散试卷及答案第3页共22页证明因为F、G是双射，所以GFAC是双射，所以GF有逆函数（GF）1CA。同理可推F1G1CA是双射。因为F1G1存在Z（G1F1）存在Z（FG）GF（GF）1,所以（GF）1F1G1。R1,2,，S1,21,4。八、（15分）设是半群，对A中任意元A和B，如AB必有ABBA，证明1对A中每个元A，有AAA。2对A中任意元A和B，有ABAA。3对A中任意元A、B和C，有ABCAC。证明由题意可知，若ABBA，则必有AB。1由AAAAAA，所以AAA。2由AABAAABAABAAABAA，所以有ABAA。3由ACABCACABCABCABCABCACABCAC，所以有ABCAC。九、给定简单无向图G，且|V|M，|E|N。试证若N2，则G是哈密尔顿图1MC证明若N2，则2NM23M6（1）。1M若存在两个不相邻结点、使得DDM，则有UVUV2NMM2M3MM23M6，与（1）矛盾。所以，对VWD于G中任意两个不相邻结点、都有DDM，所以G是哈密尔UVUV顿图。离散试卷及答案第4页共22页离散数学试题B卷及答案）一、证明题（10分）1PQPQRPQPRT证明左端PQPQRPQPR摩根律PQPQPRPQPR分配律PQPRPQPR等幂律T代入2XPXQXXPXXPXQX证明XPXQXXPXXPXQXPXXPXQXPXXPXQXXPXXQXXPXQX二、求命题公式PQPQ的主析取范式和主合取范式（10分）解PQPQPQPQPQPQPQPQPPQQPQPQM1M0M2M3三、推理证明题（10分）1PQSRPQRS证明（1）R附加前提2RPP3PT12,I4PQSP5QST34,I6QP7ST56,I8RSCP2XPXQX，XPXXQX证明1XPXP2PC离散试卷及答案第5页共22页T1,US3XPXQXP4PCQCT3,US5QCT24,I6XQXT5,EG四、例5在边长为1的正方形内任意放置九个点，证明其中必存在三个点，使得由它们组成的三角形（可能是退化的）面积不超过1/8（10分）。证明把边长为1的正方形分成四个全等的小正方形，则至少有一个小正方形内有三个点，它们组成的三角形（可能是退化的）面积不超过小正方形的一半，即1/8。五、已知A、B、C是三个集合，证明ABCABAC（10分）证明XA（BC）XAX（BC）XA（XBXC）（XAXB）（XAXC）X（AB）XACX（AB）（AC）A（BC）（AB）（AC）六、A1，A2，AN是集合A的一个划分，定义R|A、BAI，I1，2，N，则R是A上的等价关系（15分）。证明AA必有I使得AAI，由定义知ARA，故R自反。A,BA，若ARB，则A,BAI，即B,AAI，所以BRA，故R对称。A,B,CA，若ARB且BRC，则A,BAI及B,CAJ。因为IJ时AIAJ，故IJ，即A,B,CAI，所以ARC，故R传递。总之R是A上的等价关系。七、若FAB是双射，则F1BA是双射（15分）。证明对任意的XA，因为F是从A到B的函数，故存在YB，使F，F1。所以,F1是满射。离散试卷及答案第6页共22页对任意的XA，若存在Y1,Y2B，使得F1且F1,则有F且F。因为F是函数，则Y1Y2。所以，F1是单射。因此F1是双射。八、设是群，和是的子群，证明若ABG，则AG或BG（10分）。证明假设AG且BG，则存在AA，AB，且存在BB，BA（否则对任意的AA，AB，从而AB，即ABB，得BG，矛盾。）对于元素ABG，若ABA，因A是子群，A1A，从而A1ABBA，所以矛盾，故ABA。同理可证ABB，综合有ABABG。综上所述，假设不成立，得证AG或BG。九、若无向图G是不连通的，证明G的补图是连通的（10分）。证明设无向图G是不连通的，其K个连通分支为、。任取结1G2KG点、G，若和不在图G的同一个连通分支中，则，不是图G的边，UVUVUV因而，是图的边；若和在图G的同一个连通分支中，不妨设其在连UV通分支（1）中，在不同于的另一连通分支上取一结点，则，和IIKIWUW，都不是图G的边，因而，和，都是的边。综上可知，不WVUWVG管那种情况，和都是可达的。由和的任意性可知，是连通的。UVV一、选择题每小题2分，总计301给定语句如下（1）15是素数（质数）（2）10能被2整除，3是偶数。（3）你下午有会吗若无会，请到我这儿来（4）2X30（5）只有4是偶数，3才能被2整除。离散试卷及答案第7页共22页6明年5月1日是晴天。以上6个语句中，是简单命题的为（A）,是复合命题的为（B）,是真命题的为（C）,是假命题的是（D）,真值待定的命题是（E）A13461461（6）B2424625C1256无真命题（5）D12无假命题1245E46（6）无真值待定的命题2将下列语句符号化（1）4是偶数或是奇数。（A）设P4是偶数，Q4是奇数（2）只有王荣努力学习，她才能取得好成绩。（B）设P王荣努力学习，Q王荣取得好成绩（3）每列火车都比某些汽车快。（C）设FXX是火车，GYY是汽车，HX,YX比Y快。APQPQPQBPQQPPQCXYFXGYHX,YXFXYGYHX,YXFXYGYHX,Y3设S1,2,3,下图给出了S上的5个关系,则它们只具有以下性质R1是（A）,R2是B,R3是C。离散试卷及答案第8页共22页ABC自反的，对称的，传递的反自反的，对称的自反的反对称的对称的自反的，对称的，反对称的，传递的4设S，1，1，2，则有（1）（A）S（2）BS（3）PS有（C）个元数。（4）（D）既是S的元素，又是S的子集A1,21B1,21C3678D1二、证明（本大题共2小题，第1小题10分，第2小题10分，总计20分）1、用等值演算算法证明等值式PQPQP2、构造下面命题推理的证明如果今天是星期三，那么我有一次英语或数学测验；如果数学老师有事，那么没有数学测验；今天是星期三且数学老师有事，所以我有一次英语测验。三、计算（本大题共4小题，第1小题5分，第2小题10分，第3小题15分，总计30分）1、设，求公式212,，个体域为为，整除为XQYXP的真值。,2、设集合上的关系，求出它的自反闭包，A432,14,3,R对称闭包和传递闭包。3、设上的整除关系，是否为上的,8,A2121,AAA整除RA偏序关系若是，则1、画出的哈斯图；（10分）R离散试卷及答案第9页共22页2、求它的极小元，最大元，极大元，最大元。（5分）四、用推导法求公式的主析取范式和主合取范式。（本大题10分）PQ答案一、选择题1ABCDE2ABC3ABC4ABCD二、证明题1证明左边（PQP）（PQQ）（分配律）P（PQQ）吸收律P（PQQQ）（分配律）P（PQ1）（排中律）PPQ（同一律）P（吸收律）2解P今天是星期三。Q我有一次英语测验。R我有一次数学测验。S数学老师有事。前提PQR,SR,PS结论Q证明PS前提引入P化简PQR前提引入离散试卷及答案第10页共22页QR假言推理S化简SR前提引入R假言推理Q析取三段论推理正确。三、计算1,12,11,22,XYPQXPYPQPQ1,2,0,00该公式的真值是1，真命题。或者TFTFQPPQPPXXXYX2,21,2,2、4,3,24,3,12,RRS,1,1,T3、（1）是上的偏序关系。RA（2）极小元、最小元是1,极大元、最大元是24。四、离散试卷及答案第11页共22页2301PQPQPQ，主合取范式，安徽大学20042005学年第二学期离散数学期末考试试卷（A卷）参考答案一、单项选择1在自然数集上，下列哪种运算是可结合的（）NABBA,MAXBCD23OD2下列代数系统中，哪个是群（）SA，是模7加法B（有理数集合），是一般乘5,310SQS法C（整数集合），是一般减法D，是模11乘法Z9,54313若是的真子群，且，则有（）。HGNHMGA整除B整除NMC整除且整除D不整除且不整除NNN4下面哪个集合关于指定的运算构成环（）A，关于数的加法和乘法,|23ZBAB阶实数矩阵，关于矩阵的加法和乘法NC，关于数的加法和乘法,|D，关于矩阵的加法和乘法ZBA,ABCDEFG离散试卷及答案第12页共22页5在代数系统中，整环和域的关系为（）。A域一定是整环B域不一定是整环C整环一定是域D域一定不是整环6是自然数集，是小于等于关系，则是（）。N,NA有界格B有补格C分配格D有补分配格7图11给出的哈斯图表示的格中哪个元素无补元（）ABCD图11ACEF8给定下列序列，可构成无向简单图的结点度数序列的是（）。A（1，1，2，2，3）B（1，3，4，4，5）C（0，1，3，3，3）D（1，1，2，2，2）9欧拉回路是（）。A路径B简单回路C既是基本回路也是简单回路D既非基本回路也非简单回路10哈密尔顿回路是（）。A路径B简单回路C既是基本回路也是简单回路D既非基本回路也非简单回路二、填空题（以下每个下划线为一空，请按要求填入合适的内容。每空2分，共30分）。1设是非空有限集，代数系统中，对运算的单位元是S）,SPSP，零元是，对运算的单位元是。2在运算表21中空白处填入适当符号，使成为群。,CBA，。3设，是群的子群，其中8,40H12,12,NABCAABABCCC离散试卷及答案第13页共22页，是模12加法，则有1,201N1212,N个真子群，的左陪集，。H3H44设是一个布尔代数，如果在上定义二元运算为,AA，则是一个。表21BABA,A5任何一个具有个元素的有限布尔代数都是。N26若连通平面图有4个结点，3个面，则有条边。GG7一棵树有两个结点度数为2，一个结点度数为3，三个结点度数为4，它有个度数为1的结点。8无向图是由（）棵数组成的森林，至少要添加条边才能使GK成为一棵树。三、求解题（20分）1试写出中每个子群及其相应的左陪集。（6分）6,N2若一个有向图是欧拉图，它是否一定是强连通的若一个有向图是强GG连通的，它是否一定是欧拉图说明理由。（6分）3有向图如图31所示。（1）求的邻接矩阵；（2分）GA（2）中到长度为4的路径有几条（2分）1V4（3）中到自身长度为3的回路有几条（2分）（4）是哪类连通图（2分）G图31四、证明题（30分）1设是一群，。定义，。证明也是一群。,GGXBXAGA,2E74V412V31365离散试卷及答案第14页共22页2证明（1）证明在格中成立。（5分）DBCADCBA（2）证明布尔恒等式。（5分）A3证明（1）在6个结点12条边的连通平面简单图中，每个面由3条边围成。（5分）（2）证明当每个结点的度数大于等于3时，不存在有7条边的简单连通平面图。安徽大学20042005学年第二学期离散数学期末考试试卷（A卷）参考答案一、单项选择1B2D3A4C5A6C7B8D9B10C二、填空题1，；2，；35，；4交换群；SCBA1,70,85同构；65；79；8。1K三、求解题1解子群有，。6,06,306,420的左陪集为，6,0135的左陪集为，3,5,的左陪集为，6,424202答（1）一个有向欧拉图一定是强连通图。因为是欧拉图，存在欧拉回G路，中的每个结点至少在中出现一次。因而中任意两点，都在CGCUV中，相互可达，故是强连通的。（2）一个强连通图不一定是有向欧拉图。因为强连通图中每个结点的入度不一定等于其出度。离散试卷及答案第15页共22页3解（1）012A10322A013423A104624（2）由中可知，到长度为4的路径有条（，4AA1V4641E674E，）。651E6531（3）由中可知，到自身长度为3的回路有1条（）。1V1E（4）是单向连通图。G四、证明题1证明显然是上的二元运算（即满足封闭性），要证是群，需证结合G律成立，同时有单位元，每个元素有逆元。，有GCBA,CBACXBACXBA运算是可结合的。其次，是的单位元。事实上，有1X,GG；AA1AXX11最后证明，是在中的逆元。事实上，,1111XXXAAAX由以上证明，是群。,G2证明（1）（公式13分配不等式）DBCBDCB1V45678离散试卷及答案第16页共22页又因为，所以。ABBDBCADCBA（2）因为，所以有，1CCCCBACBA（吸收律）C即等式成立。3证明（1）因图中结点数和边数分别为，根据欧拉公式6N12M，得。又，而简单连通平面图的每个面至少由2KMN8K24DEGMVI3条边围成，所以在6个结点12条边的连通平面简单图中，每个面由3条边围成。（2）设图为简单连通平面图，有个面。（反证法）,MNK若，由欧拉公式知，而每个面至少由3条边围成，有792K，则，且是整数，所以；又对任结点，K3314K4KVV，有，故，且是整数，所以。这样就有DEGVN2314NN4N，与矛盾，所以结论正确。84KN9K安徽大学20072008学年第2学期离散数学（下）考试试卷（A卷）一、单项选择题（每小题2分，共20分）1下列集合关于数的加法和乘法运算不能构成环的是（）A自然数集合；B整数集合；C有理数集合；D实数集合。2设为整数集合，则下列集合关于数的加法运算不能构成独异点的是（I离散试卷及答案第17页共22页）A；B；C；D。I2|KI21|KI35|,MNI3设，为模加法，则下列元素是的生成元的是（60,15N66,N）A2；B3；C4；D5。4设是整环，则不一定是（）,F,FA可交换环；B无零因子环；C含么环；D域。5格不一定具有（）A交换律；B结合律；C分配律；D吸收律。6设，和分别表示求最小公倍数和最大公约数运算，则1,248S是（）,A有补格；B分配格；C有补分配格；D布尔代数。7一个含个结点的无向图中有个结点的度数分别为，则第个结点的431,234度数不可能是（）A0；B1；C2；D4。8设连通的简单平面图中有10条边和5个面，则的结点数为（）GGA6；B7；C8；D9。9设无向树中有个结点度数为，个结点度数为，个结点度数为，T1234则中的树叶数为（）A10；B11；C12；D13。离散试卷及答案第18页共22页10设为连通的无向图，若仅有个结点的度数是奇数，则一定具有（GG2G）A、欧拉路径；B、欧拉回路；C、哈密尔顿路径；D、哈密尔顿回路。二、填空题（每小空2分，共20分）1设为实数集合，则在代数中，R|01SXRX,MAXS关于运算的么元是，零元是。SMAX2设为模加法，则在中，元素的阶为，的阶为1010,9,56。3设，和分别为求最大公约数和最小公倍数运10,25,1,0SGCDLM算，则在布尔代数中，原子的个数为，元素的补元为10,GCDLS2。4在格中，当且仅当当且仅当,L,ABLABAB。5一个具有个结点的简单连通无向图的边数至少为，至多为N。三、解答题（第1小题12分，第2小题8分，共20分）1设图如图1所示，G1求的邻接矩阵；A2求，说明从到的长为的路234,A1V42,34径各有几条；离散试卷及答案第19页共22页3求的可达矩阵；GP4求的强连通分图。2求群的所有子群及由元素确定的各子群的左陪集，其中8,N5，是模加法。80,17N四、证明题（每小题10分，共40分）1证明布尔恒等式。ABCBAC2设为实数集合，和为数的加法和乘法运算，对，R,ABR，BABA证明为独异点。,3