东北农业大学网络教育学院离散数学复习题复习题一一、证明1、对任意两个集合B A 和,证明 ()()A B A B A =⋂⋃-2、构造下面命题推理的证明如果今天是星期三,那么我有一次英语或数学测验;如果数学老师有事,那么没有数学测验;今天是星期三且数学老师有事,所以我有一次英语测验。
二 、计算1、(1)画一个有一条欧拉回路和一条汉密顿回路的图。
(2)画一个有一条欧拉回路但没有汉密顿回路的图 (3)画一个没有欧拉回路但有一条汉密顿回路的图2、设()(){}212,,,个体域为为,整除为<x x Q y x y x P ,求公式: ()()()()()x Q y x P y x →∃∀,的真值。
3、一棵树有2n 个结点度数为2 ,3n 个结点度数为3,… ,k n 个结点度数为k ,问它有几个度数为1的结点。
4、设集合{}A A ,4,3,2,1=上的关系 {4,33,21,22,1,1,1=R ,求出它的自反闭包,对称闭包和传递闭包。
三、设{}45,36,27,15,9,6,5,3,2,1=A 上的整除关系{}212121,,,a a A a a a a R 整除∈=, R 是否为A 上的偏序关系?若是,则:1、画出R 的哈斯图;2、求{}{}{}9,2glb 9,2lub 9,2和最大下界的最小上界。
四、用推导法求公式()()R Q P →→的主析取范式和主合取范式。
五、设实数集2R 上的关系{}c bd a R d c b a dc b a +=+∈,,,,,,2=ρ,证明:ρ是2R 上的等价关系。
六、设+R R 和分别是实数集和正实数集,+和×分别是普通加法和乘法,定义函数+→R R f :为r r f 2)(=,证明 ),(),(⨯++R R f 到是从的同构映射。
七、设R 是实数集合,}0{*-=R R ,在R R ⨯*上定义二元运算ο为:()()()d bc ac d c b a +=,,,ο,试证明>⨯<ο,*R R 是一个群。
>⨯<ο,*R R 是否阿贝尔群?复习题二一、设 上的整除关系完成下列各小题。
1、 证明ρ是L 上的偏序关系。
2、 画出偏序集,L ρ<>的哈斯图。
3、 在L 上定义两个二元运算∧和∨:对任意,a b L ∈,(,)a b glb a b ∧=,(,)a b lub a b ∨=。
请填空(在横线上填是或不是):①代数系统,,L <∧∨> 格。
②代数系统,,L <∧∨> 有界格。
③代数系统,,L <∧∨> 有补格。
④代数系统,,L <∧∨> 分配格。
二、求布尔函数的析取范式和合取范式设°123122323(,,)()()()E x x x x x x x x x =∧∨∧∨∧是布尔代数{0,1},,,<∨∧>%上的一个布尔表达式。
试写出123(,,)E x x x 的析取范式和合取范式(用推导法或列函数表的方法均可)。
三、画出满足下列要求的图①有一条欧拉回路和一条汉密尔顿回路。
②有一条欧拉回路但没有汉密尔顿回路。
③没有欧拉回路但有汉密尔顿回路。
④既没有欧拉回路也没有汉密尔顿回路。
四、证明在完全二叉树中,边的总数等于2(n-1),这里n 是叶子数。
五、计算求带权2、3、5、7、11、13的最优二叉树。
六、证明在一个连通平面图中,若它有n 个结点,m 条边,且每个面由k 条边围成。
试证(2)2k n m k -=-七、证明设V 是有限字母表,给定代数系统*,V <>o ,其中o 是串的连接运算。
对于任一串*V α∈,建立*V 到N 的映射f ,()||f αα=。
证明f 是*,V <>o 到,N <+>的一个满同态,且当||1V =时,f 是同构映射。
{}1,2,3,4,12L ={}121212,,,a aa a L a a ρ=∈整除八、应用给定有限状态机(,,,,,)s M Q S R f h A =,它的状态图如附图所示。
1、 求状态A 的011010的后继以及可接受状态序列。
2、 求s M 对于激励010110的响应。
3、构造一台与s M 相似的转换赋值机t M ,画出t M 的状态图。
九、证明考察一个(8,4)码C ,它的校验位a 5,a 6,a 7,a 8满足下列方程 a 5=a 1+ a 2+ a 4 a 6=a 1+ a 3+ a 4 a 7=a 1+ a 2+ a 3 a 8=a 2+ a 3+ a 4其中a 1,a 2,a 3,a 4为信息位。
求出这个码的一致校验矩阵。
证明0min x C x ∈≠()4W X =。
复习题三一、设集合完成下列各小题。
1求S 的幂集()P S 。
2证明(),P S <⊆>是偏序集。
3画出偏序集(),P S <⊆>的哈斯图。
4在()P S 上定义两个二元运算∧和∨:对任意,()A B P S ∈,A B A B ∧=⋂,A B A B ∨=⋃。
请填空(在横线上填是或不是并回答为什么):①代数系统(),P S <⊆>格,因为 。
{},,S a b c =②代数系统(),P S <⊆> 有界格,因为 。
③代数系统(),P S <⊆> 有补格,因为 。
④代数系统(),P S <⊆> 分配格,因为 。
⑤代数系统(),,,~P S <⋂⋃> 布尔代数,因为 。
二、计算设°123122323(,,)()()()E x x x x x x x x x =∧∨∧∨∧是布尔代数{0,1},,,<∨∧>%上的一个布尔表达式。
试写出123(,,)E x x x 的析取范式和合取范式(用列函数表的方法)。
三、回答问题完全图n K 是否是欧拉图?是否是哈密尔顿图?为什么? 四、画图对于下图,利用克鲁斯克尔算法求一棵最小生成树。
五、计算一棵树有两个结点度数为2 ,1个结点度数为3,3个结点度数为4 ,其余结点度数为1。
问该树有几个度数为1的结点。
六、证明(,)G V E =图是无向简单图,其中||||V n E m ==,,证明:2)1(-≤n n m 。
证明 因为G 是简单图,所以图G 中没有环和平行边,任意两结点间最多有一条边,故2(1)2n n n m C -≤=。
七、证明已知(,,,),{,,},{,,},:(1)(2)(3)(4)(5)(6)(7)N T N T G V V P V B C V a b c P a BC aBC CB BC aB ab bB bb bC bc cC ccσσσσσ===→→→→→→→求证 *n n na b c σ⇒ 八、设计设计一台有限状态机M ,它的输出是已经输入符号数的模3数(即设计模3计数器)。
九、计算给定码C={00000,10001,01100,10101},求码C 中任两个码字的海明距和min ()d C 。
复习题四一、填空1、设A 和B 为有限集,|A|=m ,|B|=n ,则有 个从A 到B 的关系,有 个从A 到B 的函数,其中当m ≤n 时有 个入射,当m=n 时,有 个双射。
2、集合2{|}A n n N =∈ (是/不是)可数的。
二、计算1、用推导法求下列公式的主合取范式和主析取范式:(())P Q R ⌝∨→2设A A },4,3,2,1{=上二元关系{1,2,2,2,2,4,3,4}R =<><><><>,求其自反闭包、对称闭包、传递闭包。
三、证明1、设C B A ,,是三个集合,证明:()()A B C A C B ⋂-=-⋂ 2证明等价式:()(()())()()()()x A x B x x A x x B x ∃→⇔∀→∃ 四、将下列命题推理符号化并给出形式证明:已知张三或李四的彩票中奖了;如果张三的彩票中奖了,那么你是知道的;如果李四的彩票中奖了,那么王五的彩票也中奖了;现在你不知道张三的彩票中奖。
所以李四和王五的彩票都中奖了。
五、设复数集合{|,,0}C a bi a b R a =+∈≠,定义C R 上二元关系:,a bi c di R <++>∈当且仅当0ac >,证明:R 为等价关系。
六、证明:若A B C D A B C D ⨯⨯:::和,则。
七、设集合{23|,}m nG m n I =∈,⨯是普通乘法,证明:,G <⨯>是一个群。
八、设实数集合R ,+和x 是普通加法和乘法,定义映射:f R R →,,()xx R f x e ∀∈=,证明,,f R R <+><⨯>是从到的单一同态。
复习题五一、填空1、实数集合R (是/不是)可数的。
2、设A 和B 为有限集,|A|=m ,|B|=n ,则有 个从A 到B 的关系,有 个从A 到B 的函数,其中当m ≤n 时有 个入射,当m=n 时,有 个双射。
二、计算1、用推导法求下列公式的主合取范式和主析取范式:(())P Q R ⌝∨→2设A A },4,3,2,1{=上二元关系{1,1,2,3,2,4,3,2,3,4}R =<><><><><>,求其自反闭包、对称闭包、传递闭包。
三、证明1、设C B A ,,是三个集合,证明:()()A B C A C B --=-- 2证明等价式:()(()())()()()()x A x B x x A x x B x ∀→⇔∃→∀ 四、将下列命题推理符号化并给出形式证明:已知今天下雨或刮风;如果今天下雨,那么我在家看书;如果今天刮风,那么我去放风筝;今天我没有在家看书。
所以今天刮风并且我去放风筝了。
五、设正整数集合I +上的二元关系{,|,,}2x yR x y x y I I +-=<>∈∈,证明:R 为等价关系。
六、证明:若A B C D A B C D ⨯⨯:::和,则。
七、设集合{5|}nG n I =∈,⨯是普通乘法,证明:,G <⨯>是一个群。
八、设正实数集合R +和实数集合R ,+和x 是普通加法和乘法,定义映射:f R R +→,,()ln x R f x x +∀∈=,证明,,f R R +<⨯><+>是从到的同构。
复习题六一、 求公式q ∧(p ∨┐q)的析取范式、合取范式及主析取范式、主合取范式。
二、用推理规则证明:前提 (∃x)(F(x)∧S(x))→(∀y)(M(y) →W(y)),(∃y)(M(y)∧┐W(y)) 结论 (∀x)(F(x)→┐S(x)) 三、计算题1.证明逻辑等价式A →(A →B)⇔A →B 成立。