离散数学总复习题2016选择填空

1设7|,5|XEXBXNXA且且（N自然数集，E正偶数）则B0，1，2，3，4，6；。2A，B，C表示三个集合，文图中阴影部分的集合表达式为。3设P，Q的真值为0，R，S的真值为1，则P的真值1。4设A1，2，3，4，A上关系图为则R2,。5设AA，B，C，D，其上偏序关系R的哈斯图为则R,IA。6图的补图为。7P你努力，Q你失败。“除非你努力，否则你将失败”的翻译为P；“虽然你努力了，但还是失败了”的翻译为。8设A2，3，4，5，6上的二元关系|,是质数XYXR，则R（列举法）。R的关系矩阵MR。ABC9设A1，2，3，则A上既不是对称的又不是反对称的关系R；A上既是对称的又是反对称的关系R。10N个结点的无向完全图KN的边数为12N，欧拉图的充要条件是图中无奇度结点且连通11设AA，B，C，A上二元关系R,则S（R）A,C,B,A,。12集合2的幂集A2,2。13若P，Q，为二命题，QP真值为0当且仅当P真值为1，Q的真值为0。14命题“对于任意给定的正实数，都存在比它大的实数”令FXX为实数，YXL,则命题的逻辑谓词公式为,0,XYLFYLFX。15谓词合式公式X的前束范式为PX。16将量词辖域中出现的约束变元和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为换名规则。17,则A的幂集。1P20N阶完全图结点V的度数DVN1。21设N阶图G中有M条边，每个结点的度数不是K的是K1，若G中有NK个K度顶点，NK1个K1度顶点，则NKNK12M。23任何N,M图GV,E,边与顶点数的关系是VVMD2。24当N为奇数时,非平凡无向完全图KN是欧拉图。27N阶完全图KN的边数为12。28右图的邻接矩阵A01。30集合A,的幂集PA。31设A1，2，3，4，A上二元关系R，画出R的关系图。32设A,B,则BA,，,、。,。33设|A|3，则，A上有29个二元关系。34A1，2，3上关系R,时，R既是对称的又是反对称的。35偏序集RA,的哈斯图为，则,IA。36Q我将去上海，R我有时间，公式QR的自然语言为我将去上海当且仅当我有空。37若,21MSS是集合A的一个分划，则它应满足。38若P，Q为二命题，QP真值为1，当且仅当P，Q的真值相同。39XGXF的前束范式为XGFX。40能够断真假的阵述句称为命题。41命题PQ的真值为0，当且仅当P的真值为1，Q的真值为0。42一个命题含有4个原子命题，则对其所有可能赋值有16种。43所有小项的析取式为永真式。44令P（X）X是质数，E（X）X是偶数，Q（X）X是奇数，D（X，Y）X除尽Y则,YDY的汉语翻译为任意两数X、Y,如果X是偶数且能除尽Y，则Y一定是偶数；。45若R是集合A上的偏序关系，则R满足自反性、反对称性、传递性46设G是N阶完全图，则G的边数M12N。47设集合A,B，其中A1,2,3,B1,2,则AB_3_AB_3,1,3,2,3,1,2,3_48设有限集合A,|A|N,则|AA|_2N49已知命题公式GPQR，则G的主析取范式是_PQR_51设A、B为两个集合,A1,2,4,B3,4,则从AB_4,_AB_1,2,3,4,_AB_1,2_52设R是集合A上的等价关系，则R所具有的关系的三个特性是_自反性；对称性；传递性_53设命题公式GPQR，则使公式G为真的解释有_1,0,0,1,0,1,1,1,0_54设集合A2,3,4,5,6，R是A上的整除，则R以集合形式列举法记为_2,2,2,4,2,6,3,3,3,6,4,4,5,5,6,655设一阶逻辑公式GXPXXQX，则G的前束范式是_XPXQX_56若，则X_。23,5,X57设谓词的定义域为A,B,将表达式XRXXSX中量词消除，写成与之对应的命题公式是_RARBSASB_58设集合A1,2,3,4，A上的二元关系R1,1,1,2,2,3。则R2_1,1,1,2,1,3_59设A1,2,3,4,A上的二元关系R,，则_，R2_，R12_。060令FXX是鸟，GXX会飞翔，则“所有鸟都会飞翔”应该符号化为_。二、选择题1、设A1，2，3，则A上的二元关系有（C）个。A23；B32；C3；D2。2设R，S是集合A上的关系，则下列说法正确的是（A）A若R，S是自反的，则SR是自反的；B若R，S是反自反的，则是反自反的；C若R，S是对称的，则是对称的；D若R，S是传递的，则S是传递的。3、设A1，2，3，4，P（A）（A的幂集）上规定二元系如下|,|TSAPTSR则P（A）/R（D）AA；BPA；C1，1，2，1，2，3，1，2，3，4；D，2，2，3，2，3，4，A4、设A，1，1，3，1，2，3则A上包含关系“”的哈斯图为（C）5、图中从V1到V3长度为3的通路有（D）条。A0；B1；C2；D3。6、下图中既不是EULAR图，也不是HAMILTON图的图是（B）7、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（A）个4度结点。A1；B2；C3；D4。8、设,1S，则S2有（D）个元素。A3；B6；C7；D8。9、设,2，定义上的等价关系,|CBDASDCSBADCBAR则由R产生的S上一个划分共有（B）个分块。A4；B5；C6；D9。10、设3,21S，S上关系R的关系图为则R具有（D）性质。A自反性、对称性、传递性；B反自反性、反对称性；C反自反性、反对称性、传递性；D自反性。11、在如下的有向图中，从V1到V4长度为3的道路有（B）条。A1；B2；C3；D4。12、在如下各图中（B）欧拉图。13、下述命题公式中，是重言式的为（C）。A、QP；B、PQPQ；C、；D、。14、设S1，2，3，R为S上的关系，其关系图为则R具有（D）的性质。A、自反、对称、传递；B、什么性质也没有；C、反自反、反对称、传递；D、自反、对称、反对称、传递。15、设2,1,S，则有（A）S。A、1,2；B、1,2；C、1；D、2。16、设A1,2,3，则A上有（D）个二元关系。A、23；B、32；C、32；D、23。17、全体小项合取式为（C）。A、可满足式；B、矛盾式；C、永真式；D、A，B，C都有可能。18、下列语句是命题的有（AC）。A、明年中秋节的晚上是晴天；B、0YX；C、0XY当且仅当X和Y都大于0；D、我正在说谎。19、下列各命题中真值为真的命题有（AD）。B、224当且仅当3是奇数；B、224当且仅当3不是奇数；C、224当且仅当3是奇数；D、224当且仅当3不是奇数；20、下列符号串是合式公式的有（CD）A、QP；B、P；C、QP；D、P。21、下列等价式成立的有（AD）。A、；B、R；D、P；D、RPP。22、若N21,和B为WFF，且BAN21则（BC）。A、称NA为B的前件；B、称B为NA21,的有效结论B、当且仅当FN21；D、当且仅当N21。23、A，B为二合式公式，且，则（ABCDE）。A、为重言式；B、A；C、；D、；E、BA为重言式。24、“人总是要死的”谓词公式表示为（C）。（论域为全总个体域）MXX是人；MORTALXX是要死的。A、MORTALX；B、XMORTALB、；D、25、公式XQPXA的解释I为个体域D2，PXX3,QXX4则A的真值为（A）。A、1；B、0；C、可满足式；D、无法判定。26、下列等价关系正确的是（B）。A、XXPXP；B、QQ；C、；C、XX。27、下面四组数能构成无向简单图的度数列的有（AB）。A、（2，2，2，2，2）；B、（1，1，2，2，3）；B、（1，1，2，2，2）；D、（0，1，3，3，3）。28、下图中是哈密顿图的为（BD）。29、如右图相对于完全图K5的补图为（A）。31、下面四组数能构成无向图的度数列的有B。A、2,3,4,5,6,7；B、1,2,2,3,4；C、2,1,1,1,2；D、3,3,5,6,0。32、图的邻接矩阵为C。A、01；B、1；C、01；D、01。33、下列几个图是简单图的有B。AG1V1,E1,其中V1A,B,C,D,E,E1AB,BE,EB,AE,DE；BG2V2,E2其中V2V1,E2,；CGV3,E3,其中V3V1,E3AB,BE,ED,CC；DGV4,E4,其中V4V1,E4（A,A）,（A,B）,（B,C）,（E,C）,（E,D）。34、下列图中是欧拉图的有A。35、图相对于完全图的补图为（A）。36、对图G则,K分别为（A）。A、2、2、2；B、1、1、2；C、2、1、2；D、1、2、2。37、一棵无向树T有8个顶点，4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有（C）片树叶。A、3；B、4；C、5；D、638、下列语句不是命题的有（AE）。A、X13；B、离散数学是计算机系的一门必修课；C、鸡有三只脚；C、太阳系以外的星球上有生物；E、你打算考硕士研究生吗39、RQP的合取范式为（BD）。A、；B、RQP；C、RQPRD、PRP。40、设|A|N，则A上有（C）二元关系。A、2N；B、N2；C、2N；D、NN；E、N2。41、集合A1，2，3，4上的偏序关系图为则它的哈斯图为（A）。42、下列各符号串，不是合式公式的有（BC）。A、RQP；B、SRQP；B、；D、。43、下列语句是命题的有（AC）。A、2是素数；B、X56；C、地球外的星球上也有人；D、这朵花多好看呀。44、下列公式是重言式的有（B）。A、QP；B、Q；C、P；D、45、下列问题成立的有（CD）。A、若C，则BA；B、若CA，则BA；B、若，则；D、若，则。46、命题逻辑演绎的CP规则为（C）。A、在推演过程中可随便使用前提；B、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果；C、如果要演绎出的公式为B形式，那么将B作为前提，设法演绎出C；C、设是含公式A的命题公式，A，则可用B替换A中的A。47、命题“有的人喜欢所有的花”的逻辑符号化为（D）。设D全总个体域，F（X）X是花，MXX是人，HX,YX喜欢YA、,YHFYMX；B、,XHFM；C、,X；D、YYX。48、公式,PZQPY换名（A）。A、XUU；B、,XX；D、,UZYY；D、,YPUP。49、给定公式，当DA,B时，解释（BC）使该公式真值为0。A、PA0、PB0；B、PA0、PB1；C、PA1、PB0；D、PA1、PB150、下面蕴涵关系成立的是（BD）。A、XQPXQXP；B、；C、；E、,YXAYX。51、集合A1，2，3，4上的偏序关系为，则它的HASS图为（C）。52、设集合A1，2，3，4，5上偏序关系的HASS图为则子集B2，3，4的最大元（）；最小元（）；极大元（）；极小元（）；上界（）；上确界（）；下界（）；下确界（）。AA、无，4，2、3，4，1，1，4，4；B、无，4、5，2、3，4、5，1，1，4，4；C、无，4，2、3，4、5，1，1，4，4；D、无，4，2、3，4，1，1，4，无。52、设R，S是集合A上的关系，则下列（A）断言是正确的。A、,自反的，则是自反的；B、若SR,对称的，则SR是对称的；53、若,传递的，则是传递的；D、若,反对称的，则S是反对称的54、设X为集合，|X|N，在X上有（D）种不同的关系。A、N2；B、2N；C、N2；D、2N。55、“没有不犯错误的人”的逻辑符号化为（BD）。设H（X）X是人，P（X）X犯错误。A、XPHX；B、XPHX；D、；D、。56、设N阶图G有M条边，每个结点度数不是K就是K1，若G中有NK个K度结点，则NK（D）。A、NK；B、NK1；C、NK1M；D、NK12M。57、一棵树有7片树叶，3个3度结点，其余全是4度结点，则该树有（A）个4度结点。A、1；B、2；C、3；D、4。58、有向图D，则41V到长度为2的通路有（B）条。A、0；B、1；C、2；D、3。59、在PETERSON图中，至少填加（D）条边才能构成EULER图。A、1；B、2；C、4；D、5。60、集合,的幂集为（B）。A、；B、,B；C、,；D、B，61、在（D）下有AB。A、；B、；C、；D、A或62、下列结果正确的是（BE）。A、；B、；C、AB；D、；E、；F、AAA。63、下列句子不是命题的是（D）A中华人民共和国的首都是北京B张三是学生C雪是黑色的D太好了64、下列式子不是谓词合式公式的是（B）A（X）PXRYBXP（X）XPXQXCXYPXQYXRXDXPX,YQX,ZZRX,Z65、下列式子为重言式的是（D）APRQBPQRRCPPQDPQPQ66、对于公式XYPXQYXRX,Y，下列说法正确的是（C）AY是自由变元BY是约束变元CX的辖域是RX,YDX的辖域是YPXQYXRX,Y67设论域为1,2，与公式XAX等价的是（C）AA1A2BA1A2CA1A2DA2A168下列关系矩阵所对应的关系具有反对称性的是（B）AB0110CD010169题13图的最大出度是（C）A0B1C2D370下列图是欧拉图的是（D）71一棵树的3个4度点，4个2度点，其它的都是1度，那么这棵树的边数是（B）A13B14C15D1672、设集合A2,A,3,4，BA,3,4,1，E为全集，则下列命题正确的是C。A2ABAACABEDA,1,3,4B73、设集合A1,2,3,A上的关系R1,1,2,2,2,3,3,2,3,3，则R不具备DA自反性B传递性C对称性D反对称性74、