离散数学

离散数学练习题一、单项选择题2．下列式子为重言式的是(A)A．P→P∨QB．(﹁P∧Q)∧(P∨﹁Q)C．﹁(PQ)D．(P∨Q)(P→Q)3．下列哪个关系矩阵所对应的关系具有自反性(B)A．001111101B．101110001C．001100100D．0010101014．右图的最小入度是(B)A．0B．1C．2D．35．下面既是汉密尔顿图又是欧拉图的图形是(B)6．一棵树有3个5度点、1个4度点、3个2度点，其它的都是1度，那么它的边数是(C)A．17B．18C．19D．208．下列式子为矛盾式的是(A)A．PPB．)(QPPC．PPD．)(QPQP9．下列关系矩阵所对应的关系具有反自反性的是(C)A．001110101B．101110001C．001100100D．00101010110．右图的最大入度是(D)A．0B．1C．2D．311．下列可一笔画成的图形是(A)12．一棵树有5个3度结点，2个2度结点，其它的都是l度结点，那么这棵树的结点数是(B)A．13B．14C．16D．1714．下列式子为重言式的是（D）A．(┐P∧R)→QB．P∨Q∧R→┐RC．P∨(P∧Q)D．(┐P∨Q)(P→Q)15．下列关系矩阵所对应的关系具有反对称性的是（B）A．001110101B．101110001C．001100100D．00101010116．下列图是欧拉图的是（D）17．一棵树的3个4度点，4个2度点，其它的都是1度，那么这棵树的边数是（B）A．13B．14C．15D．1618．下列为两个命题变元P，Q的极小项是（C）A．P∧Q∧PB．P∨QC．P∧QD．P∨P∨Q21．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（B）A．P∧QB．P∨QC．（PQ）D．（P∨Q）22．命题公式（P∧（P→Q））→Q是（C）A．矛盾式B．蕴含式C．重言式D．等价式23．命题公式（P∧Q）→R的成真赋值是（B）A．000，001，110，B．001，011，101，110，111C．全体指派D．无24．集合A={1，2，…，10}上的关系R={x，y|x+y=10，x∈A，y∈A}，则R的性质是（B）A．自反的B．对称的C．传递的、对称的D．反自反的、传递的25．设A={{1，2，3}，{4，5}，{6，7，8}}，下列选项正确的是（C）A．1∈AB．{1，2，3}AC．{{4，5}}AD．∈A26．设G为有n个结点的简单图，则有（A）A．Δ(G)＜nB．Δ(G)≤nC．Δ(G)＞nD．Δ(G)≥n27．具有4个结点的非同构的无向树的数目是（C）A．2B．3C．4D．530．设34:,45:qp，命题“除非45，否则34”应符号化为（A）AA．qpB．qpC．qpD．pq31．设A是含n个命题变项的公式，下面4个结论中，错误的是（B）A．若A的主析取范式不含任何极小项，则A的主析取范式为0B．若A的主合取范式不含任何极大项，则A的主合取范式为0C．若A的主析取范式含n2个极小项，则A是重言式D．若A的主合取范式含n2个极大项，则A是矛盾式32．当Rx，下列四个集合中是空集的是（C）A．}023{2xxxB．}{2xxxC．}032{2xxxD．}56cossin{xxx33．设M，P是两个非空集合，定义M与P的差集为}{PxMxxPM且，则)PMM（等于（B）A．PB．PMC．PMD．M34．集合A={1，2，…，10}上的关系R={x，y|x+y=10，x∈A，y∈A}，则R的性质是（B）A．自反的B．对称的C．传递的、对称的D．反自反的、传递的35．下列关系矩阵所对应的关系具有自反性的是（D）A．001100100B．001010101C．001110101D．10111000136．设R是整数集Z上的关系，下列关系R既为Z上的等价关系又为Z上的偏序关系的是（C）A．R为Z上的小于等于关系B．R为Z上的整除关系C．R为Z上的全域关系D．R为Z上的恒等关系38．设无向图G的邻接矩阵为0101010010000011100000100，则G的边数为（D）DA．5B．6C．3D．439．给定一个序列集合{1，01，10，11，001，000}，若去掉其中的元素（A），则该序列集合构成前缀码．A．1B．01C．10D．1140．题13图的入度和出度之和的最大值是（D）A．2B．3C．5D．141．下列可一笔画成的图形是（A）42．一棵树的4个3度点，4个2度点，其它的都是1度，那么这棵树的边数是（C）A．11B．12C．13D．1445．命题公式qqpp))((是（C）CA．矛盾式B．可满足式C．重言式D．等价式46．设A是含n个命题变项的公式，下面4个结论中，错误的是（B）A．若A的主析取范式不含任何极小项，则A的主析取范式为0B．若A的主合取范式不含任何极大项，则A的主合取范式为0C．若A的主析取范式含n2个极小项，则A是重言式D．若A的主合取范式含n2个极大项，则A是矛盾式47．设A={{1，2，3}，{4，5}，{6，7，8}}，下列选项正确的是（C）A．1∈AB．{1，2，3}AC．{{4，5}}AD．∈A48．下列命题为假的是(B)A．B．∈C．{}D．∈{}49．设{1,2,3}A上的关系R的关系图如右所示，则R不具备的性质为（A）A．自反性B．反自反性C．反对称性D．传递性50．下列关系矩阵所对应的关系具有自反性的是（B）A．001111101B．101110001C．001100100D．00101010151．设R是整数集Z上的关系，下列关系R既为Z上的等价关系又为Z上的偏序关系的是（C）A．R为Z上的小于等于关系B．R为Z上的整除关系C．R为Z上的全域关系D．R为Z上的恒等关系52．已知集合A＝{a,b,c}上的二元关系R的关系矩阵MR＝001011010，那么R＝(D)，A．{a,b,b,a,b,b,a,c}B．{a,b,b,a,b,b,c,b}C．{a,b,a,a,b,b,c,a}D．{a,b,b,a,b,b,c,a}53．设无向图G的邻接矩阵为0001000100010011000000100，则G的边数为（C）A．5B．6C．3D．454．右图的最小入度是（B）A．0B．1C．2D．355．给定一个序列集合{1，01，10，11，001，000}，若去掉其中的元素（A），则该序列集合构成前缀码．A．1B．01C．10D．1156．一棵树有3个5度点、1个4度点、3个2度点，其它的都是1度，那么它的边数是（C）A．17B．18C．19D．20二、填空题1．设命题变元为P，Q，R，则极小项m100=________，极大项M010=________。2．请用联结词，表示联结词和联结词：________，________。3．三个命题变项的极小项rqp对应的二进制编号是________，极大项rqp对应的二进制编号是____________4．n个命题变元的____合取_______称为极小项，其中每个变元与它的否定不能同时出现，但两者必须____出现一个_______。5．n个命题变元的____析取____称为极大项，其中每个变元与它的否定不能同时出现，但两者必须__出现一个______。6．两个重言式的析取是__重言______式，一个重言式与一个矛盾式的析取是_____重言___式。7．若回路中，除_____看尾__外___顶点_____各不相同，则此回路称为圈(或初级回路)。8．若图中存在___闭迹_____，它经过图中所有的边恰好____出现一____次，则称该图为欧拉图。9．请写出表示分配律的两个命题公式等价定理________,________。10．请写出表示德摩根律的两个命题公式等价定理___________，___________。11．请写出表示德摩根律的在集合论中的两个公式_________，___________。12．设A={1，2，3，4}，B={2，4，6}，则A-B=________，AB=________。13．设A={1，2}，B={2，3}，则A-A=________，A-B=________。14．设A=,B={2,4}，则P(P(A))=___________，A×B___________。15．设A有2个元素，那么，在A上有_______个关系，有_________个等价关系。16．设A有3个元素，那么，在A上有_______个关系，有_________个等价关系。17．给出A={a，b}上的一个等价关系________，并给出其对应的划分________。18．给出A={l，2，3}上的一个等价关系________，并给出其对应的划分________。19．若图中存在__闭路______，它经过图中所有的___点_____，则称该图为汉密尔顿图。21．设G是n阶无向简单图，若G中任何一对不相邻的顶点的度数之和________大于等于N__，则G一定是哈密顿图。23．若无向图G是平凡图，或G中任意两顶点都是连通的，则称G是_____连通图___。三、计算题1．用等值演算求(P→Q)→R的主合取范式。2．用等值演算求P(QR)的主析取范式。3．请通过等值演算法求┐(P∧Q)→(P∨Q)的主析取范式。4．求下列公式的主合取范式和主析取范式：P∨（P→（Q∨（Q→R）））5．用等值演算求(P→Q)→Q的主析取范式。5．列出)(PQ))((QRP的真值表。6．列出(P→(Q∨R))(P→Q)的真值表。7．构造命题公式（（P∧Q）→P）∨R的真值表。8．已知A={{}，{，1}}，B={{，1}，{1}}，计算A∪B，A○+B，A的幂集P（A）。9．设A={2，3，6，12，24，36}，请画出A上整除关系的哈斯图，并给出子集{6，12，24，36}的下界、下确界、极大元、最大元。10．设A={1，2，3，4，6，8，12，24}，R为A上的整除关系，试画A，R的哈斯图，并求A中的最大元、最小元、极大元、极小元。11．已知无向简单图有n个顶点，m条边，各顶点的度数都是3，又2n–3=m。求n和m，并画出这种图。这种图是唯一的吗？12．下图给出了一个有向图。（1）求出它的邻接矩阵A；（2）求出A2，A3及可达矩阵P。13．用矩阵的方法求下图中结点v1，v3之间长度为2的路径的数目。14．下图给出了一个有向图。（1）求出它的邻接矩阵A；（2）求出A2，A3，及可达矩阵P。15．用矩阵的方法求下图中结点ui，u5之间长度为2的路径的数目。16．开运动会时，高一某班共有28名学生参加比赛，有15人参加游泳比赛，有8人参加田径比赛，有14人参加球类比赛，同时参加游泳和田径比赛的有3人，同时参加游泳和球类比赛的有3人，没有人同时三项比赛．问同时参加田径和球类比赛的有多少人？只参加一项比赛的有多少人？17．对某单位的100名员工进行调查，结果发现他们喜欢看球赛和电影、戏剧。其中58人喜欢看球赛，38人喜欢看戏剧，52人喜欢看电影，既喜欢看球赛又喜欢看戏剧的有18人，既喜欢看电影又喜欢看戏剧的有16人，三种都喜欢