离散数学网上作业题

离散数学⽹上作业题

东北农业⼤学⽹络教育学院

离散数学复习题

复习题⼀

⼀、证明1、对任意两个集合B A 和，证明 ()()A B A B A =??-

2、构造下⾯命题推理的证明

如果今天是星期三，那么我有⼀次英语或数学测验；如果数学⽼师有事，那么没有数学测验；今天是星期三且数学⽼师有事，所以我有⼀次英语测验。

⼆ 、计算1、(1)画⼀个有⼀条欧拉回路和⼀条汉密顿回路的图。

(2)画⼀个有⼀条欧拉回路但没有汉密顿回路的图

(3)画⼀个没有欧拉回路但有⼀条汉密顿回路的图

2、设()(){

}212,，，个体域为为，整除为

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 b d a R d c b a dc b a +=+∈,,,,,,2＝ρ， 证明：ρ是2

R 上的等价关系。

六、设+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 +=,,,ο，试证

明>??

复习题⼆

⼀、设 上的整除关系

完成下列各⼩题。 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)2

k 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 a a 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)2

n 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 BCaBC CB BC aB ab bB bb bC bc cC cc

σσσσσ===→→→→→→→

求证 *n n n a 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 n G m n I =∈，?是普通乘法，证明：,G 是⼀个群。

⼋、设实数集合R ，+和x 是普通加法和乘法，定义映射:f R R →，,()x x 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 +上的⼆元关系{,|,,}2

x y R x y x y I I +-=<>∈∈，证明：R 为等价关系。 六、证明：若A B C D A B C D ??:::和，则。

七、设集合{5|}n G 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 成⽴。

2.对任意集合A ，B ，C ，证明：（A - B ）⊕ B = A ? B

3.设⼆元关系R={<{a},b>,, }求：

(1) dom R

(2) ran R

(3) R οR

4.求集合A={|p,q 都是整数}的势。

5. 在20名青年中有10名是公司职员，12名是学⽣，其中5名既是职员⼜是学⽣，问有⼏名既不是职员，⼜不是学⽣。

四、假设给定了正整数的序偶集合A ，在A 上定义⼆元关系R 如下：<,>∈R,当且仅当xv=yu ，证明R 为等价关系。

五、给出偏序集上偏序关系R 的关系图（如下图所⽰）。

（1）求偏序集的哈斯图。 （2）指出A 的最⼤、最⼩元（如果有的话），极⼤、极⼩元。

六、设为群。若在G 上定义⼆元运算о,使得对任何元素x ，y ∈G ，有x оy = y *x 。

证明也是群

七、设为群,a 为G 中给定元素。定义函数f ：G →G ，使得对每⼀x ∈G 有f(x)=a *x *a-1

证明：f 是到的⾃同构。

复习题七