当前位置：文档之家› 离散数学8习题解答

离散数学8习题解答

第8 章习题解答

8.1 图8.6 中,(1)所示的图为,3,1K (2) 所示的图为,3,2K (3)所示的图为,2,2K 它们分别各有不同的同构形式.

8.2 若G 为零图,用一种颜色就够了,若G 是非零图的二部图,用两种颜色就够了.

分析根据二部图的定义可知,n 阶零图(无边的图)是三部图(含平凡图),对n 阶零图的每个顶点都用同一种颜色染色,因为无边,所以,不会出现相邻顶点染同色,因而一种颜色就够用了.

8.3 完全二部图,,s r K 中的边数rs m -.

分析设完全二部图s r K ,的顶点集为V, 则?==2121,V V V V V ,且,||,||21s V r V ==s r K ,是简单图,且1V 中每个顶点与2V 中所有顶点相邻,而且1V 中任何两个不同顶点关联的边互不相同,所以,边数rs m -.

8.4 完全二部图s r K ,中匹配数},min{1s r =β,即1β等于s r ,中的小者. 分析不妨设,s r ≤且二部图s r K ,中,,||,||21s V r V ==由Hall 定理可知,图中存在1V 到的完备匹配,设M 为一个完备匹配,则1V 中顶点全为M 饱和点,所以,.1r =β

8.5 能安排多种方案,使每个工人去完成一项他们各自能胜任的任务.

分析设},,{

1丙乙甲=V ,则1V 为工人集合, },,{2c b a V =,则2V 为任务集合.

令}|),{(,21y x y x E V V V 能胜任== ,得无向图>=

8.7 所示.本题是求图中完美匹配问题. 给图中一个完美匹配就

对应一个分配方案.图8.7 满足Hall 定理中的相异性条件,所以,

存在完备匹配,又因为,3||||21==V V 所以,完备匹配也为完美匹配.

其实,从图上,可以找到多个完美匹配. 取

)},(),,(),,{(1c b a M 丙乙甲=

此匹配对应的方案为甲完成a,乙完成b, 丙完成c,见图中粗边所示的匹配. )},(),,(),,{(c a b M 丙乙甲=

2M 对应的分配方案为甲完成b,乙完成a,丙完成c.

请读者再找出其余的分配方案.

8.6 本题的答案太多,如果不限定画出的图为简单图,非常容易地给出4族图分别满足要求.

(1) n (n 为偶数,且2≥n )阶圈都是偶数个顶点,偶数条边的欧拉图.

(2) n (n 为奇数,且1≥n )阶圈都是奇数个顶点,奇数条边的欧拉图.

(3) 在(1) 中的圈上任选一个顶点,在此顶点处加一个环,所务图为奇数个顶点,偶数条边的欧拉图.

分析上面给出的4族图都是连通的,并且所有顶点的度数都是偶数,所以,都是欧拉图.并且(1),(2) 中的图都是简单图.而(3),(4)中的图都带环,因而都是非简单图. 于是,如果要求所给出的图必须是简单图,则(3),(4)中的图不满足要求.

其实,欧拉图是若干个边不重的图的并,由这种性质,同样可以得到满足

(3),(4)中要求的简单欧拉图.设k G G G ,,,21 是长度大于等于3的k 个奇圈(长度为奇数的圈称为奇圈),其中k 为偶数,将1G 中某个顶点与2G 中的某顶点重合,但边不重合, 2G 中某顶点与3G 中某顶点重合,但边不重合,继续地,最后将1-k G 中某顶点与k G 中某顶点重合,边不重合,设最后得连通图为G,则G 中有奇数个顶点,偶数条边,且所有顶点度数均为偶数,所以,这样的一族图满足(4)的要求,其中一

个特例为图8.8中(1)所示.在以上各图中,若k G G G ,,,21 中有一个偶圈,其他条件不变,构造方法同上,则所得图G 为偶数个顶点,奇数条边的简单欧拉图,满足

(3)的要求,图8.8中(2)所示为一个特殊的情况.

8.7 本题的讨论类似于8.6题,只是将所有无向圈全变成有向圈即可,请读者自己画出满足要求的一些特殊有向欧拉图.

8.8 本题的答案也是很多的,这里给出满足要求的最简单一些图案,而且全为简单图.

(1) n (3≥n )阶圈,它们都是欧拉图,又都是哈密尔顿图.

(2) 给定k (2≥k )个长度大于等于3的初级回路,即圈k G G G ,,,21 ,用8.6题方法构造的图G 均为欧拉图,但都不是哈密尔顿图,图8.8给出的两个图是这里的特例.

(3)n (4≥n )阶圈中,找两个不相邻的顶点,在它们之间加一条边,所得图均为哈密尔顿图,但都不是欧拉图.

(4) 在(2)中的图中,设存在长度大于等于4的圈,比如说1G ,在1G 中找两个

不相邻的相邻顶点,在它们之间加一条新边,然

后用8.6题方法构造图G,则G 既不是欧拉图,

也不是哈密尔顿图,见图8.9所示的图.

分析 (1) 中图满足要求是显然的.(2)

中构造的图G 是连通的,并且各顶点度数均为偶数,所以,都是欧拉图,但因为G 中存在割点,将割点从G 中删除,所得图至少有两个连通分支,这破坏了哈密尔顿图的必要条件,所以,G 不是哈密尔顿图.(3) 中构造的图中,所有顶点都排在一个圈上,所以,图中存在哈密尔顿回路,因而为哈密尔顿图,但因图中有奇度顶点(度数为奇数的顶点),所以,不是欧拉图. 由以上讨论可知,(4) 中图既不是欧拉

其实,读者可以找许多族图,分别满足题中的要求.

8.9 请读者自己讨论.

8.10 其逆命题不真.

分析若D 是强连通的有向图,则D 中任何两个顶点都是相互可达的,但并没有要求D 中每个顶点的入度都等于出度. 在图8.2 所示的3个强连通的有向衅都不是欧拉图.

8.11 除2K 不是哈密尔顿图之外, n K (3≥n )全是哈密尔顿图. n K (n 为奇数)为欧拉图. 规定1K (平凡图)既是欧拉图,又是哈密尔顿图.

分析从哈密尔顿图的定义不难看出,n 阶图G 是否为哈密尔顿图,就看是否能将G 中的所有顶点排在G 中的一个长为n 的初级回路,即圈上. n K (3≥n )中存在多个这样的生成圈(含所有顶点的图), 所以n K (3≥n )都是哈密尔顿图.

在完全图n K 中,各顶点的度数均为n-1,若n K 为欧拉图,则必有1-n 为偶数,即n 为奇数,于是,当n 为奇数时, n K 连通且无度顶点,所以, n K (n 为奇数) 都是欧拉图.当n 为偶数时,各顶点的度数均为奇数,当然不是欧拉图.

8.12 有割点的图也可以为欧拉图.

分析无向图G 为欧拉图当且仅当G 连通且没有奇度顶点.只要G 连通且无奇度顶点(割点的度数也为偶数),G 就是欧拉图.图8.8所示的两个图都有割点,但它们都是欧拉图.

8.13 将7个人排座在圆桌周围,其排法为.abdfgeca

分析做无向图>=

},,,,,,{g f e d c b a V =

},|),{(有共同语言与且v u V v u v u E ∈=

图G 为图8.10所示.图G 是连通图,于是,能否将这7个人排座在圆桌周围,使得每个人能与两边的人交谈,就转化成了图G 中是否存在哈密尔顿回路(也就是G 是否为哈密尔顿图).通过观察发现G 中存在哈密尔顿回路, abdfgeca 就是其

8.14 用i v 表示颜色.6,,2,1, =i i 做无向图>=

},,,,,,{654321v v v v v v V =

}.,,|),{(能搭配与并且且v u v u V v u v u E ≠∈=

对于任意的)(,v d V v ∈表示顶点v 与别的能搭配的颜色个数,易知G 是简单图,且对于任意的V v u ∈,,均有633)()(=+≥+v d u d ,由定理8.9可知,G 为哈密尔顿图,因而G 中存在哈密尔顿回路,不妨设1654321i i i i i i i v v v v v v v 为其中的一条,在这种回

路上,每个顶点工表的颜色都能与它相邻顶点代表的颜色相.于是,让1i v 与2i v ,3i v 与4i v ,5i v 与6i v 所代表的颜色相搭配就能织出3种双色布,包含了6种颜色.

8.15

∑=?======3

00321,10220)deg(.12)deg(,3)deg(,1)deg(,4)deg(i i R R R R R 而本图边

数m=10.

分析平面图(平面嵌入)的面i R 的次数等于包围它的边界的回路的长度,这里所说回路,可能是初级的,可能是简单的,也可能是复杂的,还可能由若干个回路组成.图8.1所示图中,321,,R R R 的边界都是初级回路,而0R 的边界为复杂回路(有的边在回路中重复出现),即432110987654321e e e e e e e e e e e e e e ,长度为12,其中边65,e e 在其中各出现两次.

8.16 图8.11中,实线边所示的图为图8.1中图G,虚线边,实心点图为它的

对偶图的顶点数*n ,边数*m ,面数*r 分别为4,10和8,于是有

分析从图8.11还可以发现,G 的每个顶点位于的一个面中,且的每个面只含G 的一个顶点,所以,这是连通平面图G 是具有k 个连通分支的平面图2≥k ,则应有1*+-=k n r .读者自己给出一个非连通的平面图,求出它的对偶图来验证这个结论.另外,用图8.1还可以验证,对于任意的*v (*G 中的顶点),若它处于G 的面i R 中,则应有)deg()(*i R v d =.

8.17 不能与G 同构.

分析任意平面图的对偶图都是连通的,因而与都是连通图,而G 是具有3个连通分支的非连通图,连通图与非连通图显然是不能同构的.

图 8.12 中, 这线边图为图8.2中的图G,虚线边图为G 的对偶图,带小杠的边组成的图是*G 的对偶图,显然.~**G G ≠

8.18 因为彼得森图中有长度为奇数的圈,根据定理8.1可知它不是二部图.图中每个顶点的度数均为3,由定8.5可知它不是欧拉图.又因为它可以收缩成5K ,由库拉图期基定理可知它也不是平面图.

其实,彼得森图也不是哈密尔顿图图,这里就不给出证明了.

8.19 将图8.4重画在图8.13中,并且将顶点标定.图中afbdcea 为图中哈密尔顿回路,见图中粗边所示,所以,该图为哈密尔顿图.

将图中边),(),,(),,(d f f e e d 三条去掉,所得图为原来图的子图,它为3,3K ,可取},,{1c b a V =},,{2f e d V =,由库拉图期基定理可知,该图不是平面图.

8.20 图8.14 所示图为图8.5所示图的平面嵌入.

分析该图为极大平面图.此图G 中,顶点数9=n ,边数.12=m 若G 是不是极大平面图,则应该存在不相邻的顶点,,v u 在它们之间再加一条边所得'G 还应该是简单平面图, 'G 的顶点数131,6''=+===n m n n ,于是会有

.126313''=->=n m

这与定理8.16矛盾,所以,G 为极大平面图.

其实,n ( 3≥n )阶简单平面图G 为极大平面图当且仅当G 的每个面的次数均为3.由图8.14可知,G 的每个面的次数均为3,所以,G 为极大平面图.

8.12 答案 A,B,C,D 全为②

分析 (1) 只有n 为奇数时命题为真,见8.11的解答与分析.

(2) 2≠n 时,命题为真,见8.11的解答与分析.

(3) 只有m n ,都是偶数时,m n K ,中才无奇度数顶点,因而m n K ,为欧拉图,其他情况下,即m n ,中至少有一个是奇数,这时m n K ,中必有奇度顶点,因而不是欧拉图.

(4) 只有m n =时, m n K ,中存在哈密尔顿回路,因而为哈密尔顿图. 当m n ≠时,不妨设m n <,并且在二部图m n K ,中,m V n V ==||,||21,则n V m V G p =>=-||)(11,这与定理8.8矛盾. 所以, m n ≠时, m n K ,不是哈密尔顿

图.

8.22 答案 A:②;B ②;C ②.

分析

图8.15中,两个实边图是同构的,但它们的对偶力(虚边图)是不同构的.

(2) 任何平面图的对偶图都是连通图.设G 是非连通的平面图,显然有.**~G G ≠ (3) 当G 是非连通的平面图时,,1*+-=k n r 其中k 为G 的连通分支数.

8.23 答案 A:④;B ②;C ②.

分析根据库期基定理可知,所求的图必含有5K 或3,3K 同胚子图,或含可收缩成5K 或3,3K 的子图.由于顶点数和边数均已限定,因而由3,3K 加2条边的图可满足要求,由5K 增加一个顶点,一条边的图可满足要求,将所有的非同构的简单图画出来,共有4个,其中由3,3K 产生的有2个,由5K 产生的有2个.见图8.16所示.

离散数学题库及答案

数理逻辑部分选择、填空及判断 ?下列语句不就是命题的( A )。 (A) 您打算考硕士研究生不？ (B) 太阳系以外的星球上有生物。 (C) 离散数学就是计算机系的一门必修课。 (D) 雪就是黑色的。 ?命题公式P→(P∨?P)的类型就是( A ) (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?A就是重言式,那么A的否定式就是( A ) A、矛盾式 B、重言式 C、可满足式 D、不能确定 ?以下命题公式中,为永假式的就是( C ) A、p→(p∨q∨r) B、(p→┐p)→┐p C、┐(q→q)∧p D、┐(q∨┐p)→(p∧┐p) ?命题公式P→Q的成假赋值就是( D ) A、 00,11 B、 00,01,11 C、10,11 D、 10 ?谓词公式) x xP∧ ?中,变元x就是 ( B ) R , ( x ) (y A、自由变元 B、既就是自由变元也就是约束变元 C、约束变元 D、既不就是自由变元也不就是约束变元 ?命题公式P→(Q∨?Q)的类型就是( A )。 (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 析取范式 ?设B不含变元x,) x x→ ?等值于( A ) A ) ( (B A、B (D、B x xA→ x ?) ( ( ?C、B x∧ A ?) (B、) ?) xA→ x ) ( A x (B x∨ ?下列语句中就是真命题的就是( D )。 A.您就是杰克不？ B.凡石头都可练成金。 C.如果2+2=4,那么雪就是黑的。 D.如果1+2=4,那么雪就是黑的。 ?从集合分类的角度瞧,命题公式可分为( B ) A、永真式、矛盾式 B、永真式、可满足式、矛盾式 C、可满足式、矛盾式 D、永真式、可满足式 ?命题公式﹁p∨﹁q等价于( D )。 A、﹁p∨q B、﹁(p∨q) C、﹁p∧q D、 p→﹁q ?一个公式在等价意义下,下面写法唯一的就是( D )。 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 ?下列含有命题p,q,r的公式中,就是主析取范式的就是( D )。

《离散数学》考试题库及答案(三)

《离散数学》考试题库及答案一、填空 10% （每小题 2分） 1、若P ，Q 为二命题，Q P ?真值为1，当且仅当。 2、对公式),()),(),((y x xR z x zQ y x yP ?∨?∧?中自由变元进行代入的公式为。 3、 )) (()(x xG x xF ??∧?的前束范式为。 4、设x 是谓词合式公式A 的一个客体变元，A 的论域为D ，A （x ）关于y 的自由的，则被称为全称量词消去规则，记为US 。 5、与非门的逻辑网络为。二、选择 30% （每小题 3分） 1、下列各符号串，不是合式公式的有（）。 A 、R Q P ?∧∧)(； B 、)()((S R Q P ∧→→； C 、R Q P ∧∨∨； D 、S R Q P ∨∧∨?))((。 2、下列语句是命题的有（）。 A 、2是素数； B 、x+5 > 6； C 、地球外的星球上也有人； D 、这朵花多好看呀！。 3、下列公式是重言式的有（）。 A 、)(Q P ??； B 、Q Q P →∧)(； C 、P P Q ∧→?)(； D 、P Q P ?→)( 4、下列问题成立的有（）。 A 、若C B C A ∨?∨，则B A ?； B 、若C B C A ∧?∧，则B A ?； C 、若B A ???，则B A ?； D 、若B A ?，则B A ???。 5、命题逻辑演绎的CP 规则为（）。 A 、在推演过程中可随便使用前提； B 、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果； C 、如果要演绎出的公式为C B →形式，那么将B 作为前提，设法演绎出C ；

离散数学试题与答案

试卷二试题与参考答案一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统,其中A={a,b,c}, 则幺元就是 ;就是否有幂等性 ;就是否有对称性。 6、4阶群必就是群或群。 7、下面偏序格就是分配格的就是。 8、n 个结点的无向完全图K n 的边数为 ,欧拉图的充要条件就是。 * a b c a b c a b c b b c c c b

二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。

离散数学试题及答案精选版

离散数学试题及答案 Company number【1089WT-1898YT-1W8CB-9UUT-92108】

一、填空题 1设集合A,B，其中A＝{1,2,3},B={1,2},则A-B＝____________________; (A)-(B)＝__________________________. 2.设有限集合A,|A|=n,则|(A×A)|=__________________________. 3.设集合A={a,b},B={1,2},则从A到B的所有映射是 _______________________________________,其中双射的是 __________________________. 4.已知命题公式G＝(PQ)∧R，则G的主析取范式是 _______________________________ __________________________________________________________. 6设A、B为两个集合,A={1,2,4},B={3,4},则从AB＝ _________________________;AB＝_________________________;A－B＝_____________________. 7.设R是集合A上的等价关系，则R所具有的关系的三个特性是 ______________________,________________________,__________________ _____________. 8.设命题公式G＝(P(QR))，则使公式G为真的解释有 __________________________， _____________________________,__________________________. 9.设集合A＝{1,2,3,4},A上的关系 R 1={(1,4),(2,3),(3,2)},R 2 ={(2,1),(3,2),(4,3)},则

离散数学习题

第一章习题 1.1判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题。（1）2是无理数。（2）5能被2整除。（3）现在开会吗？（4）x+5>0 （5）这朵花真是好看！（6）2是素数当且仅当三角形有三条边。（7）雪是黑色的当且仅当太阳是从东方升起。（8）2000年10月1日天气晴好。（9）太阳系以外的星球上有生物。（10）小李在宿舍里。（11）全体起立。（12）4是2的倍数或是3的倍数。（13）4是偶数且是奇数。（14）李明和王华是同学。（15）蓝色和黄色可以调配成绿色。 1..2 将上题中的命题符号化，并讨论他们的真值。 1.3判断下列各命题的真值。（1）若2+2=4，则3+3=6；（2）若2+2=4，则3+3≠6；（3）若2+2≠=4，则3+3=6；（4）若2+2≠=4，则3+3≠=6；（5）2+2=4，当且仅当3+3=6；（6）2+2=4，当且仅当3+3≠6；（7）2+2≠4，当且仅当3+3=6；（8）2+2≠4，当且仅当3+3≠6； 1.4将下列命题符号化，并讨论其真值。（1）如果今天是1号，则明天是2号；（2）如果今天是1号，则明天是3号； 1.5将下列命题符号化。（1）2是偶数不是素数；（2）小王不但聪明而且用功；（3）虽然天气冷。老王还是来了；（4）他一边吃饭，一边看电视；（5）如果天下大雨，他就乘公交汽车来；（6）只有天下大雨，他才乘公交汽车来；（7）除非天下大雨，否则他不乘公交汽车来；（8）不经一事，不长一智； 1.5设p,q的真值为0 ，r,s的真值为1，求下列命题公式的真值。（1）p∨(q∧r);

离散数学习题三含答案

离散数学习题三 11、填充下面推理证明中没有写出的推理规则。前提：p s r r q q ,,,p →∨?∨? 结论：s 证明：① p 前提引入 ②q ∨?p 前提引入 ③ q （①②析取三段论） ④r q ∨? 前提引入 ⑤ r （③④析取三段论） ⑥s r → 前提引入 ⑦ s （⑤⑥假言推理） 12、填充下面推理证明中没有写出的推理规则。前提：s)(r q r),(q p →→→→ 结论：s q)(p →∧ 证明：①q)(p ∧ （附加前提） ② p （①化简规则） ③ q （①化简规则） ④r)(q p →→ 前提引入 ⑤r q → （②④假言推理） ⑥ r （③⑤假言推理） ⑦s)(r q →→ 前提引入 ⑧s)(r → （③⑦假言推理） ⑨ s （⑥⑧假言推理） 13、前提：s r ,q p q,q)p (→∨∧→? 结论1：r 结论2：s 结论3：s ∨r （1）证明从此前提出发，推出结论1，结论2，结论3的推理都是正确的。（2）证明从此前提出发，推任何结论的推理都是正确的。证明：（1）①r s))r (q)(p q)q)p (((→→∨∨∨∧→? 1r s))r (q)p (q)q)p ((?∨?∧∨?∧?∨?∨∨??

②s ∨ → ∨ → ? ((→ ∨ ∧ s)) p( q) r( q) q) (p ∧ ? ? ∨ ∨ ∧ ? ? ? ∨ ∨ ? q) r( q) ∨ s 1 p s)) p ( q) ((? ③s) ∨ ∨ → ∨ ?r → → ∧ (p q) s)) ((∨ ( r( q) q) p( ? ∧ ∨ ∧ ? ? ? ?r ∨ ∨ ? ∨ ∨ r( q) ∨ s 1 p s)) ((? p q) ( q) 即结论1，结论2，结论3的推理都是正确的。（2）s) ∨ ∧ ∧ ∧ → (→ ? r( p( (p q) q) q) ∧ ? ∨ ? ∧ ? ∨ ∧ ∧ ∧ ? ? ? ∨ ? ∨ ∧ ∧ (∨ (p q) p( q) ( s) r s) q r p ( q) q) ( q) (p ∨ ? ∧ 0? ? ∨ ∧ s) (p r ( q) 即推任何结论的推理都是正确的。 14、在自然推理系统P中构造下面推理的证明：（1）前提：q → p， → (q r) p, r→ 结论：s 证明：①r) →前提引入 p→ (q ②p 前提引入 ③r) (q→①②假言推理 ④q 前提引入 ⑤r③④假言推理 r→⑤附加律 ⑥s 15、在自然推理系统P中用附加前提法证明下面的推理：前提：q → ， →s p→ (q p, r) s→ 结论：r 证明： ①s 附加前提引入 ②p s前提引入 → ③p①②假言推理 ④r) →前提引入 p→ (q ⑤r q→③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理即根据附加前提证明法，推理正确。

离散数学题库

常熟理工学院20 ～20 学年第学期《离散数学》考试试卷（试卷库01卷）试题总分： 100 分考试时限：120 分钟题号一二三四五总分阅卷人得分一、单项选择题（每题2分，共20分） 1.下列表达式正确的有( ) （A）（B）（C）（D） 2.设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列( )命题的真值为真。（A）（B）（C）（D） 3.集合A={1,2,…,10}上的关系R={|x+y=10,x,y A}，则R 的性质为( ) （A）自反的（B）对称的（C）传递的，对称的（D）传递的 4.设，，其中表示模3加法，*表示模2乘法，在集合上定义如下运算：有称为的积代数，则的积代数幺元是( ) （A）<0，0> （B）<0，1> （C）<1，0> （D）<1，1> 5.下图中既不是Eular图，也不是Hamilton图的图是( ) 6.设为无向图，，则G一定是( ) （A）完全图（B）树（C）简单图（D）多重图 7.设P：我将去镇上,Q：我有时间。命题“我将去镇上,仅当我有时间”符号化为（）。（A） P Q （B）Q P （C）P Q （D） 8.在有n个结点的连通图中,其边数（）（A）最多有n-1条（B）最多有n 条（C）至少有n-1条（D）至少有n条 9.设A－B＝,则有（）（A）B＝（B）B（C）A B （D）A B 10.设集合A上有3个元素,则A上的不同的等价关系的个数为（）（A）5 （B）7 （C）3 （D）6 二、填空题（每题2分，共20分）

1．n个命题变元组成的命题公式共有种不同的等价公式。 2．设〈L，≤〉为有界格，a为L中任意元素，如果存在元素b∈L,使，则称b是a 的补元。 3．设*，Δ是定义在集合A上的两个可交换二元运算，如果对于任意的x,y∈A,都有 ,则称运算*和运算Δ满足吸收律。 4．设T是一棵树，则T是一个连通且的图。 5．一个公式的等价式称作该公式的主合取范式是指它仅由组成。 6．量词否定等价式? ("x)P(x) ?，? ($x)P(x) ?。 7．二叉树有5个度为2的结点，则它的叶子结点数为。 8．设是一个群，是阿贝尔群的充要条件是。9．集合S={α，β，γ，δ}上的二元运算*为 * αβγδ αδαβγ βαβγδ γβγγγ δαδγδ 那么，代数系统中的幺元是，α的逆元是。 10．设A={<1，2>，<2，4>，<3，3>}，B={<1，3>，<2，4>，<4，2>} = 。 = 。三、判断题（每题1分，共10分） 1.命题公式是一个矛盾式。（） 2.，若，则必有。（） 3.设S为集合X上的二元关系，则S是传递的当且仅当(S S)S。（） 4.任何一棵二叉树的结点可对应一个前缀码。（） 5.代数系统中一个元素的左逆元一定等于该元素的右逆元。（） 6.一个有限平面图，面的次数之和等于该图的边数。（） 7.A′B = B′A （） 8.设*定义在集合A上的一个二元运算，如果A中有关于运算*的左零元θl和右零θr,则A中有零元。（） 9.一个循环群的生成元不是唯一的。（） 10.任何一个前缀码都对应一棵二叉树。（）四、解答题（5小题，共30分） 1.（5分）什么是欧拉路？如何用欧拉路判定一个图G是否可一笔画出？ 2.（8分）求公式 (P∨Q)R 的主析取范式和主合取范式。

离散数学例题整理

第一章定律证明: (1) A?B=B?A (交换律) 证?x x∈A?B ? x∈A 或x∈B, 自然有x∈B 或x∈A ? x∈B?A 得证A?B?B?A. 同理可证B?A?A?B. (2) A?(B?C)=(A?B)?(A?C) (分配律) 证?x x∈A?(B?C) ? x∈A或(x∈B且x∈C ) ?(x∈A或x∈B)且(x∈A或x∈C) ?x∈(A?B)?(A?C) 得证A?(B?C)?(A?B)?(A?C). 类似可证(A?B)?(A?C)?A?(B?C). (3) A?E=E (零律) 证根据并的定义, 有E?A?E. 根据全集的定义, 又有A? E?E. (4) A?E=A (同一律) 证根据交的定义, 有A?E?A. 又, ?x x∈A, 根据全集E的定义, x∈E, 从而x∈A且x∈E, ?x∈A?E 得证A?A?E. 例4 证明A?(A?B)=A（吸收律）证利用例3证明的4条等式证明 A?(A?B) = (A?E)?(A?B) (同一律) = A?(E?B) (分配律) = A?(B?E) (交换律) = A?E (零律) = A (同一律) 例5 证明(A-B)-C=(A-C)-(B-C) 证(A-C)-(B-C) = (A ?~C) ? ~(B ? ~C) (补交转换律) = (A ?~C) ? (~B ? ~~C) (德摩根律) = (A ?~C) ? (~B ? C) (双重否定律) = (A ?~C? ~B)?(A ?~C? C) (分配律) = (A ?~C? ~B)?(A ??) (矛盾律) = A ?~C? ~B (零律,同一律) = (A ?~B) ? ~C (交换律,结合律)

离散数学试题及答案(1)

离散数学试题及答案一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ρ(A) - ρ(B)＝__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B ＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________， _____________________________, __________________________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。

离散数学题目大汇总

离散数学试题一（A 卷答案）一、（10分）证明(A ∨B )(P ∨Q )，P ，(B A )∨P A 。二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4 种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。请推出哪两个人参加了围棋比赛。三、（10分）指出下列推理中，在哪些步骤上有错误为什么给出正确的推理形式。 (1)x (P (x ) Q (x )) P (2)P (y )Q (y ) T (1)，US (3)xP (x ) P (4)P (y ) T (3)，ES (5)Q (y ) T (2)(4)，I (6)xQ (x ) T (5)，EG 四、（10分）设A ＝{a ，b ，c}，试给出A 上的一个二元关系R ，使其同时不满足自反性、反自反性、五、（15分）设函数g ：A →B ，f ：B →C ， (1)若f o g 是满射，则f 是满射。 (2)若f o g 是单射，则g 是单射。六、（15分）设R 是集合A 上的一个具有传递和自反性质的关系，T 是A 上的关系，使得T R 且R ，证明T 是一个等价关系。七、（15分）若是群，H 是G 的非空子集，则是的子群对任意的a 、b ∈H 有 a * b －1∈H 。八、（15分）(1)若无向图G 中只有两个奇数度结点，则这两个结点一定是连通的。 (2)若有向图G 中只有两个奇数度结点，它们一个可达另一个结点或互相可达吗离散数学试题一（B 卷答案）一、（15分）设计一盏电灯的开关电路，要求受3个开关A 、B 、C 的控制：当且仅当A 和C 同时关闭或B 和C 同时关闭时灯亮。设F 表示灯亮。 u v w