离散数学填空题及答案

编号题目答案题型分值大纲难度1谓词公式x(P(x)yR(y))Q(x)中量词x的辖域是（）。答：P(x)yR(y)填空题23.132令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（）。答：x(R(x)Q(x))填空题23.133一棵无向树的顶点数n与边数m关系是()。答：m=n-1填空题27.134一个图的欧拉回路是一条通过图中()的回路。答：所有边一次且恰好一次填空题26.435有n个结点的树，其结点度数之和是()。答：2n-2填空题26.436设T是一棵树，则T是一个连通且()图。答：简单无回路填空题26.237任一有向图中，度数为奇数的结点有()个。答：偶数填空题26.138设}7|{)},5()(|{xExxBxNxxA且且（N：自然数集，E+正偶数）则BA（）。答：{0，1，2，3，4，6}填空题2129设P，Q的真值为0，R，S的真值为1，则答：1填空22.13)()))(((SRPRQP的真值=（）。题10公式PRSRP)()(的主合取范式为（）。答：)()(RSPRSP填空题22.3411设A={1，2，3，4}，A上关系为｛1,2,2,1,2,3,3,4｝则R2=()。答：{1,1,1,3,2,2,2,4}填空题24.1；4.2312设A={a，b，c，d}，其上偏序关系R的哈斯图为则R=（）。答：{a.b,a,c,a,d,b,d,c,d}IA填空题24.4413树是不包含树是不包含（）的（）图的。答：环;无向填空题28.1314设A={1，2，3}，则A上既不是对称的又不是反对称的关系R=()。答：R={1,2,1,3,2,1}填空题24.3315设f，g是自然数集N上的函数xxgxxfNx2)(,1)(,，则)(xgf（）。答：2(x+1)填空题25.2316设A={a，b，c}，A上二元关系R={a,a,a,b,a,c,c,c},则s（R）=（）。答：}a,c,a,b,c,c,c,a,b,a,a,a{填空题24.4517P，Q真值为0；R，S真值为1。则))()(())((SRQPSRPwff的真值为（）。答：1填空题22.2318RRQPwff))((的主合取范式为（）。答：)()()(RQPRQPRQP填空题22.3419设P（x）：x是素数，E(x)：x是偶数，O(x)：x是奇数N(x,y)：x可以整数y。则谓词))),()(()((xyNyOyxPxwff的自然语言是（）。答：)()()(RQPRQPRQP填空题23.1320谓词)),,()),(),(((uyxuQzyPzxPzyxwff的前束范式为（）。答：)),,(),(),((uyxQzyPzxPuzyx填空题23.2421若P，Q，为二命题，QP真值为0当且仅当（）。答：P真值为1，Q的真值为0填空题22.1322将量词辖域中出现的（）和指导变元交换为另一变元符号，公式其余的部分不变，这种方法称为换名规则。答：约束变元填空题23.1323设G为9阶无向图，每个结点度数不是5就是6，则G中至少有（）个5度结点。答：6填空题26.1324有向图中从v1到v2长度为2的通路有（）条。答：2填空题26.3325设],,[L是代数系统，则],,[L满足幂等律，即对La有（）。答：aaaaaa且填空题28.2426任何(n,m)图G=(V,E),边与顶点数的关系是（）。答：Vvmvd2)(填空题26.4327当n为（）时,非平凡无向完全图Kn是欧拉图。答：奇数填空题26.2328已知一棵无向树T有三个3顶点,一个2度顶点,其余的都是1度顶点,则T中有（）个1度顶点。答：5填空题27.1329集合A={,{}}的幂集P(A)=（）。答：}}}{,{}},{{},{,{填空题21330设|A|=3，则A上有（）个二元关系。答：29填空题24.1331Q：我将去上海，R：我有时间，公式)()(QRRQ的自然语言为（）。答：我将去上海当且仅当我有空填空题22.1332公式)()(QPPQ的主合取范式是（）。答：)()()()(QPQPQPQP填空题22.3333若},,,{21mSSSS是集合A的一个分划，则它应满足（）。答：ASjiSSimiji1)2()()1(填空题24.4334代数系统A,*中，|A|1，如果和e分别为A,*的幺元和零元，则和e的关系为（）。答：e填空题28.1335设},2|{NnxxAn，定义A上的二元运算为普通乘法、除法和加法，则代数系统A,*中运算*关于（）运算具有封闭性。答：乘法填空题28.1336设G,*是由元素Ga生成的循环群，且|G|=n，则G=()。答：},,{12eaaaaGnn，填空题28.3437一个图是平面图的充要条件是()。答：它不包含与K3,3或K5在2度结点内同构的子图填空题26.4338某人有三个儿子，组成集合A={S1,S2,S3}，在A上的兄弟关系具有（）性质。答：反自反性、对称性、传递性填空题24.1339若BAf:是函数，则当f是BA的（），ABfc:是f的逆函数。答：双射填空题25.2340设P：它占据空间，Q：它有质量，R：它不断运动，S：它叫做物质。命题“占据空间的，有质量的而且不断运动的叫做物质”的符号化为（）。答：RQPS填空题22.1341设A，B是两命题公式，BA当且仅当（）。答：TBA填空题22.1；2.2342对谓词公式),(),(),(yxxRzxzQyxyP的自由变元代入得()。答：),(),(),(wxxRzuzQyuyP填空题23.1；3.2343对集合X和Y，设|X|=m，|Y|=n，则从X到Y的函数有()个。答：nm填空题25.1344若关系R是等价关系,则R满足()性质。答：自反性、对称性、传递性填空题24.4345关系R的传递闭包t(R)=()。答：RRii1填空题24.3446代数系统,A是群，则它满足()。答：①运算*在A上封闭，②*在A上可结合，③*在A上存在幺元，④A中每个元素都有逆元；填空题28.2；8.3347设,,,,BA和是两代数系统，f是,,,,BA到的同态映射，则f具有()性质。答：)()()(,)()()(,,bfafbafbfafbafAba填空题28.2；8.3348若连通平面图EVG,共有r个面，其中eEvV,，则它满足的Euler公式为()。答：2rev填空题26.4349树T的边数e与点数v有关系()。答：1ve填空题27.1；7.2350n个命题变元有()个互不等价的极小项。答：n2填空题22.2；2.3351按De-Morgan定理，ininAAAA121=()。答：)(1iniA填空题22.2；2.3352公式)(RQP的主析取范式为()。答：7,5,4,3,2,1,0)()()()()()()(RQPRQPRQPRQPRQPRQPRQP填空题22.3453设P(x)：x是大象，Q(x)：x是老鼠，R(x,y)：x比y重，则命题“大象比老鼠重”的符号化为()。答：)),()()((yxRyQxPyx填空题23.1354设},,{cbaX，X上的关系R的关系矩阵是111011101RM，则RRM()。答：111111111填空题26.3455在具有n个结点的有向图中，任何基本通路的长度都不超过()。答：n-1填空题26.1356任何图的点连通度)(G，边连通度)(G，最小点度)(G的关系为()。答：)()()(GGG填空题26.1；6.2357结点数n（3n）的简单连通平面图的边数为m，则m与n的关系为()。答：63nm填空题26.4458群G的非空子集H是G的子群当且仅当若x,yH则()。答：Hyx1填空题28.3459代数系统,,A是环，若对运算“·”还满足()则,,A是整环。答：含幺元，可交换，无零因子填空题28.2；8.3560给定命题公式A、B，若（），则称A和B是逻辑相等的。答：对于A，B中原子变元nPPP,,,21任意一组真值指派，A和B的真值相同。填空题22.1361设},,{cbaA考虑下列子集}},{},,{{1cbbaS，}},{},,{},{{2cabaaS，}},{},{{3cbaS，}},,{{4cbaS}}{},{},{{5cbaS，}},{},{{6caaS则A的覆盖有（），A的划分有（）。答：54354321,,,,SSSSSSSS，，；填空题24.4462若EVG,为哈密顿图，则对于结点集V的每个非空子集S，均有P(G-S)（）S成立，答：≤填空题26.4463某班有学生50人,有26人在第一次考试中得优,有21人在第二次考试中得优,有17人两次考试都没有得优,那么两次考试都得优的学生人数是（）。答：14填空题21364给命题变元p、s和r指派真值1,q指派真值0,公式p→(┐(s∧r)→┐q)∧s)的真值为（）。答：1填空题22.1；2.2365设p：我生病，q：我去上课，命题“我虽然生病但我还是去上课”符号化为：（）。答：qp填空题22.1；2.2366公式xA(x)→xB(x)的前束范式为（）。答：))()(())()((xBxAxxBxAx或填空题23.2467若{1,2,3,4}上的二元关系R={1,1,1,2,2,4},则R的自反闭包r(R)=（）。答：r(R)=｛1,1,1,2,2,4,2,23,3,4,4｝填空题24.1；4.2468有向图D如下，则D的邻接矩阵A(D)=（）。答：0010100011001010填空题26.33695阶的群有（）个不同的子群。答：2填空题28.3470一棵高度为5的二元树结点数最多为（）。答：63填空题27.1；7.2371一个连通平面图G有10条边，G中度为1的顶点有2个，其余是度为6的顶点，则G中共有（）个顶点，（）个面。答：5，7填空题26.1；6.2372集合X={0,1,2,3}，R是X上的二元关系，R={0,1,0,2,1,1,1,3,2,0,2,3,3,1,}，则R的关系矩阵MR是（）。答：0010100110100110填空题26.2；6.3373无向图G中有n个结点m条边，且G中每个结点的度数不是k就是k+1,则G中度数为k的结点的个数是（）。答：(k+1)n-2m填空题26.1；6.2374设Z+={x│x∈Z∧x0}，*表示求两个数的最小公倍数的运算，则*运算的幺元是（）。答：1填空题28.1；8.2375群N7，＋7总共有（）个不同的子群。答：2填空题28.1；8.2476在个体域D={a,b}中，与公式xA(x)等价又不含量词的公式是（）。答：A(a)∧A(b)填空题23.1；3.2377具有4个结点的有向完全图的边数为（）条。答：24填空题26.1378若p：他聪明；q：他用功；则“他虽聪明，但不用功”，可符号化为（）。答：p∧┐q填空题22.1379若集合A={1,2,3}上的二元关系R1和R2的关系图如下所示，则R1oR2=（）。答：r(