离散数学

离散数学 离散数学练习题 一、单项选择题 2(下列式子为重言式的是( A ) A(P?P?Q B((，P?Q)?(P?，Q) C(， (P Q) D((P?Q) (P?Q) 3(下列哪个关系矩阵所对应的关系具有自反性( B ) 101100，，，， ,,,,A( B( 111011,,,, ,,,,100101，，，， 001101，，，， ,,,,C( D( 001010,,,, ,,,,100100，，，， 4(右图的最小入度是( B ) A(0 B(1 C(2 D(3 5(下面既是汉密尔顿图又是欧拉图的图形是( B ) 6(一棵树有3个5度点、1个4度点、3个2度点，其它的都是1度， 那么它的边数是( C ) A(17 B(18 C(19 D(20 8(下列式子为矛盾式的是( A ) P,(P,Q)A( B( P,，P ，(P,Q)，P,，QC( D( P,，P 9(下列关系矩阵所对应的关系具有反自反性的是( C ) 101100，，，， ,,,,A( B( 011011,,,, ,,,,100101，，，， 001101，，，， ,,,,C( D( 001010,,,, ,,,,100100，，，，10(右图的最大入度是( D ) A(0 B(1 C(2 D(3 11(下列可一笔画成的图形是( A ) 12(一棵树有5个3度结点，2个2度结点，其它的都是l度结点，那 么这棵树的结点数是 ( B) A(13 B(14 C(16 D(17 14(下列式子为重言式的是( D ) A((?P?R)?Q B(P?Q?R??R C(P?(P?Q) D((?P?Q),(P?Q) 15(下列关系矩阵所对应的关系具有反对称性的是( B ) 101100，，，， ,,,,A( B( 011011,,,, ,,,,100101，，，， 001101，，，， ,,,,C( D( 001010,,,, ,,,,100100，，，， 16(下列图是欧拉图的是( D ) 17(一棵树的3个4度点，4个2度点，其它的都是1度，那么这棵 树的边数是( B ) A(13 B(14 C(15 D(16 18(下列为两个命题变元P，Q的极小项是(C ) A(P?Q?， P B(， P?Q C(， P?Q D(， P?P?Q 21(设P:我们划船，Q:我们跑步。命题“我们不能既划船又跑步” 符号化为( B ) ， P?， Q B(， P?， Q A( C(，(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，111 C(全体指派 D(无 24(集合A={1，2，„，10}上的关系R={|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?A B({1，2，3}A , ,C({{4，5}}A D(,?A 26(设G为有n个结点的简单图，则有( A ) A(Δ(G),n B(Δ(G)?n C(Δ(G),n D(Δ(G)?n 27(具有4个结点的非同构的无向树的数目是( C ) A(2 B(3 C(4 D(5 p:5,4,q:4,330(设，命题“除非，否则”应符号化为( A )5,44,3 A B( A(，p,qp,q C( D( ，p,，qq,p 31(设A是含n个命题变项的公式，下面4个结论中，错误的是 ( B ) A(若A的主析取范式不含任何极小项，则A的主析取范式为0 B(若A的主合取范式不含任何极大项，则A的主合取范式为0 n2C(若A的主析取范式含个极小项，则A是重言式 n2D(若A的主合取范式含个极大项，则A是矛盾式 x,R32(当，下列四个集合中是空集的是( C ) 22{xx,3x，2,0}{xx,x}A( B( 62{xx,2x，3,0}C( D( {xsinx，cosx,}5 33(设M，P是两个非空集合，定义M与P的差集为 M,(M,P)M,P,{xx,M且x,P}，则等于( B ) PM,PA( B( M,PMC( D( 34(集合A={1，2，„，10}上的关系R={|x+y=10，x?A，y?A}，则R的性质是( B ) A(自反的 B(对称的 C(传递的、对称的 D(反自反的、传递的 35(下列关系矩阵所对应的关系具有自反性的是( D ) 001101，，，， ,,,,A( B( 001010,,,, ,,,,100100，，，， 101100，，，， ,,,,C( D( 011011,,,, ,,,,100101，，，， 36(设R是整数集Z上的关系，下列关系R既为Z上的等价关系又为Z上的偏序关系的是( C ) A(R为Z上的小于等于关系 B(R为Z上的整除关系 C(R为Z上的全域关系 D(R为Z上的恒等关系 00100，， ,,00011,, ,,38(设无向图G的邻接矩阵为，则G的边数为( D )10000 ,,01001,, ,,01010，， D A(5 B(6 C(3 D(4 39(给定一个序列集合{1，01，10，11，001，000}，若去掉其中的元素( A )，则该序列集合构成前缀码( A(1 B(01 C(10 D(11 40(题13图的入度和出度之和的最大值是( D ) A(2 B(3 C(5 D(1 41(下列可一笔画成的图形是( A ) 42(一棵树的4个3度点，4个2度点，其它的都是1度，那么这棵 树的边数是( C ) A(11 B(12 C(13 D(14 (p,(p,q)),q45(命题公式是( C )C A(矛盾式 B(可满足式 C(重言式 D(等价式 46(设A是含n个命题变项的公式，下面4个结论中，错误的是 ( B ) A(若A的主析取范式不含任何极小项，则A的主析取范式为0 B(若A的主合取范式不含任何极大项，则A的主合取范式为0 n2C(若A的主析取范式含个极小项，则A是重言式 n2D(若A的主合取范式含个极大项，则A是矛盾式 47(设A={{1，2，3}，{4，5}，{6，7，8}}，下列选项正确的是( C ) A(1?A B({1，2，3}A , ,{{4，5}}A D(,?A C( 48(下列命题为假的是( B ) , B(,?, A(,, C(,{,} D(,?{,} , RR上的关系的关系图如右所示，则不具备的性质为49(设A,{1,2,3} ( A ) A(自反性 B(反自反性 C(反对称性 D(传递性 50(下列关系矩阵所对应的关系具有自反性的是( B ) 101100，，，， ,,,,A( B( 111011,,,, ,,,,100101，，，， 001101，，，， ,,,,C( D( 001010,,,, ,,,,100100，，，， 51(设R是整数集Z上的关系，下列关系R既为Z上的等价关系又为Z上的偏序关系的是( C ) A(R为Z上的小于等于关系 B(R为Z上的整除关系 C(R为Z上的全域关系 D(R为Z上的恒等关系 010，， ,,52(已知集合A,{a,b,c}上的二元关系R的关系矩阵M,，110R,, ,,100，，那么R,( D )， A({,,,} B({,,,} C({,,,} D({,,,} 00100，， ,,00001,, ,,53(设无向图G的邻接矩阵为，则G的边数为( C ) 10010 ,,00100,, ,,01000，， A(5 B(6 C(3 D(4 54(右图的最小入度是( B ) A(0 B(1 C(2 D(3 55(给定一个序列集合{1，01，10，11，001，000}，若去掉其中的元素( A )，则该序列集合构成前缀码( A(1 B(01 C(10 D(11 56(一棵树有3个5度点、1个4度点、3个2度点，其它的都是1度， 那么它的边数是( C) A(17 B(18 C(19 D(20 二、填空题 1(设命题变元为P，Q，R，则极小项m=________，极大项100 M=________。 010 ,,，2(请用联结词，

表

关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf

示联结词和联结词:________，________。 , 3(三个命题变项的极小项 对应的二进制编号是________，p,，q,，r 极大项对应的二进制编号是____________ p,，q,,，r 4(n个命题变元的____合取_______称为极小项，其中每个变元与它 的否定不能同时出现，但两者必须____出现一个_______。 5(n个命题变元的____析取____称为极大项，其中每个变元与它的否定不能同时出现，但两者必须__出现一个______。 6(两个重言式的析取是__重言______式，一个重言式与一个矛盾式的析取是_____重言___式。 7(若回路中，除_____看尾__外___顶点_____各不相同，则此回路称为圈(或初级回路)。 8(若图中存在___闭迹_____，它经过图中所有的边恰好____出现一____次，则称该图为欧拉图。 9(请写出表示分配律的两个命题公式等价定理________,________。 10(请写出表示德摩根律的两个命题公式等价定理___________， ___________。 11(请写出表示德摩根律的在集合论中的两个公式_______ __， _____ ______。 12(设A={1，2，3，4}，B={2，4，6}，则A-B=________，AB=________。 , 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(用等值演算求(Q R)的主析取范式。 P, 3(请通过等值演算法求?(P?Q)?(P?Q)的主析取范式。 4(求下列公式的主合取范式和主析取范式:P?(， P?(Q?(， Q?R))) 5(用等值演算求(P?Q)?Q的主析取范式。 (Q,P)((P,R),Q)5(列出 的真值表。 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中的最大元、最小元、 极大元、极小元。 11(已知无向简单图有n个顶点，m条边，各顶点的度数都是3，又2n – 3 = m。求n和m，并画出这种图。这种图是唯一的吗, 212(下图给出了一个有向图。(1)求出它的邻接矩阵A;(2)求出A， 3A及可达矩阵P。 13(用矩阵的方法求下图中结点v，v之间长度为2的路径的数目。 13 214(下图给出了一个有向图。(1)求出它的邻接矩阵A;(2)求出A，3A，及可达矩阵P。 15(用矩阵的方法求下图中结点u，u之间长i5 度为2的路径的数目。 16(开运动会时，高一某班共有28名学生参加比赛，有15人参加游泳比赛，有8人参加田径比赛，有14人参加球类比赛，同时参加游泳和田径比赛的有3人，同时参加游泳和球类比赛的有3人，没有人同时三项比赛(问同时参加田径和球类比赛的有多少人,只参加一项比 赛的有多少人, 17(对某单位的100名员工进行调查，结果发现他们喜欢看球赛和电影、戏剧。其中58人喜欢看球赛，38人喜欢看戏剧，52人喜欢看电影，既喜欢看球赛又喜欢看戏剧的有18人，既喜欢看电影又喜欢看戏剧的有16人，三种都喜欢看的有12人，则只喜欢看电影的有多少, 四、证明题 1(用推理方法证明:P?Q，P?R，Q?S?R?S。 ++3(设A={|a，b?Z，Z为整数集}，A上的关系R={<,>|ad=bc}，证明R是等价关系。 4(设图G有n个结点，n+1条边，证明:G中至少有一个结点度数 ?3。 ，(p,，q),，q,r,，r5(用推理方法证明:前提:，结论: ，p6(证明图论的握手定理:设图有n个顶点，m条边，则v,v,？,v12n n deg(v),2m ,i,1i 五、综合应用题 1(构造下面推理的证明。 如果小张和小王去看电影，则小李也去看电影。小赵不去看电影或 小张去看电影。小王去看电影。所以，当小赵去看电影时，小李也 去。 2(设七个英文字母在通信中出现的概率如下 a: 35%, b: 20%, c: 15%, d: 10%, e: 10%, f: 5%, g: 5%( 编一个最佳二元前缀码。画出对应的码树。 3(设字母a，b，c，d，e，f出现的频率如下 a: 30%, b: 25%, c: 20%, d: 10%, e: 10%, f: 5%( 构造一个表示a，b，c，d，e，f前缀码，使得传输的二进制位最少。