离散
初三 散文 4061字 189人浏览 free开心000

1、离散数学是数学中的一个分支,它以离散量作为其主要研究对象,非常重视 能行性问题的研究。

2要解决一个问题,首先要证明此问题解的存在性,还需要找出得到此问题的步

骤来,而且其步骤必须是有限的,有规则的,这就是所谓“能行性”问题的研究。

2、设{}4, 3, 2, 1=A ,{}9, 6, 4, 2=B ,那么集合A ,B 的对称差A+B= {}9, 6, 3, 1。

3、设集合{}2, 1=X 上的二元关系{}) 2, 2(), 1, 1(=R ,则R 既是等价关系又是偏序关系

4、{}}, {, , , , βα==B d c b a A ,那么可以定义 16 种不同的从A 到B 的映射。

5、设函数2) (, :, 12) (, :r r g R R g r r f R R f =→+=→,则f 有反函数。 6、A ,B 是无限集,则

7、如果A={1,2,3,4},B={3,4,5,6},则A ∩B=3,4},A+B={1,2,5,6} 。

8、对于关系,除了集合的表示形式外还有 关系图 、 关系矩阵 等表示法。

9、A={1,3,5,7,9},R 是A 上的模4同余关系,则A/R= {{1,5,9},{3,7}} 。

10、关系R 具有自反性,则它所对应的关系图具有 每个结点都有环 的特

性,它所对应的关系矩阵有 主对角线上的元素都为1 的特性。 12、设A ,B 为有限集,且

n B m A ==, ,那么A 与B 间存在双射,当且仅

当 m=n 。

13、凡与自然数集等势的集合都是可列集,那么整数集Z 是 可列集 ,实数集R 是 不可列的 。

14、试解释偏序关系和等价关系的概念,并给出一个集合上的关系,使它既是偏

序关系又是等价关系。

答:偏序关系:集合x 上的关系R 如果是自反的,反对称的,传递的,则称R 在x 上是偏序的

等价关系:一个在x 上的关系R ,如果它是自反的,对称的,传递的,则称此关

系为等价关系

令}) 3, 3(), 2, 2(), 1, 1({},3, 2, 1{==Q x 恒等关系

1、设集合{}1, 0=A ,{}3, 2=B ,{}4, 1=C ,试求:(1)B C A ⨯) ( ,(2)C A ⨯) (ρ,

(3)C B A ⨯⨯

解:A∪C={0,1,4},)}3, 4(), 2, 4(), 3, 1(), 2, 1(), 3, 0(), 2, 0{() (=⨯⋃B C A

}}1, 0{},1{},0{, {) (Φ=A ρ,)}4},1, 0({), 1},1, 0({), 4},1({), 1},1({), 4},0({), 1},0({), 4, (), 1, {() (ΦΦ=⨯C A ρ

)}4, 3, 1(), 1, 3, 1(), 4, 2, 1(), 1, 2, 1(), 4, 3, 0(), 1, 3, 0(), 4, 2, 0(), 1, 2, 0{(=⨯⨯C B A

2、设集合{}4, 3, 2, 1=A ,A 上二元关系{}2) , (+==a b b a R ,

{}2/1) , (a b a b b a S =+==或,求(1)复合关系R S S R , ,(2)求S R 的逆关系的关系矩阵。

解:R={(1,3),(2,4)} S={(1,2),(2,3),(3,4),(2,1),(4,2)} )}4, 4(), 3, 2(), 4, 1{()},2, 2(), 4, 1{(==R S S R

⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡==--0001000000100000)},2, 2(), 1, 4{() (1

) (1S R M S R 3、设{}f e d c b a S , , , , , =,S 上的偏序关系R={(a,a), (b,a), (b,b),

(c,a),(c,c),(d,a),(d,b),(d,c),(d,d),(e,a),(e,c),(e,e),(f,f)}。

(1)试画出偏序集(S ,R )的哈斯图;

(2)写出(S ,R )的最大(小) 元,极大(小)元。

最大元与最小元都不存在.

极大元是a,f, 极小元是d,e ,f.

17、证明题

设A ,B ,C 为任意三个集合,试证明:) () () (C B C A C B A ---=--。

证明:)()C B C A C B C A ∽∽∽() () (⋂⋂⋂=---

=(A ∩∽C )∩(∽B ∪C )

=(A ∩∽B ∩∽C )∪(A ∩∽C ∩C )

=(A ∩∽B ∩∽C )∪φ

=(A-B )-C

1、群(G ,*)中,其中G 的元素个数为n ,那么它产生的变换个数为

n! 。

2、一个群(G , ),的子群(N , )是正规子群的充要条件是N n G a a N a n a ∈∈∈--, , , 11 。

3、下面的代数系统(G ,*)中,*是普通加法运算,则G 为自然数集合不是群。

4、设G 是群,若G 中有 6 个元素,则不能肯定G 是可换集。

5、在群()88, +Z 中,其单位元为[0],[2]的逆元素为[6],而[2]的周期为 4 。

6、布尔代数)) (() 1(c a b a +∙+∙的对偶式是 ) () 0(a b ∙+∙+ 。

8、简答题:群的条件:(1)满足结合律(2

9、化简:如:复习与思考中关于布尔代数式的化简。

解: ) () () () () (c b a c b a c b c b a c b a ∧∧∨∧∧∨∧∨∧∧∨∧∧ =)) () (() ()) () ((c b a c b a c b c b a c b a ∧∧∨∧∧∨∧∨∧∧∨∧∧ =) () () (c b b b a ∧∨∧∨∧

=) (c b b ∧∨

=b

10、试证若群(G ,*)的每个元素的逆元素都是它自己,则该群必是可换群。 证:不妨设该群为(G ,0)

由题意可知:对任意的b a b a b b a a

G b a ===∈---111) (, , , 都有 而1

) 1() () (1) 1() () (========b b b b b a a b b a a b a a a a a b b a a b b a )()( a b b a =∴-1) (

由逆元的唯一性得:a b b a =即满足交换律,则它必是可换群

1、设G 是由5个顶点组成的完全图,则从G 中删去 6 条边可以得到树。

2、一有向图G=<V,E>,

其对应的邻接矩阵为n n ij a A ⨯=) (,则对于V v i ∈∀,它的引入次数为∑=n k ki a

1 3、设连通图G=<V,E>,其中m E n ==, ,则要删去G 中m-n+1条边,才能

确定G 的一棵生成树。 4、无向连通图G 中结点j i v v 和间存在欧拉通路的充要条件是G 中j i v v 和的次数均为奇数 ,而其他结点的次数为偶数。

5、一个有向(n, m)图中任何基本通路长度均小于或等于n-1,而任何基本回路长度均小于或等于 n。

6、在图G=<V ,E >中,结点次数与边数的关系是

m vi n i 2) deg(1=∑=(或所有结点的度数之和等于边数的2倍)

。 n n ij a A ⨯=) (中,第i 行元素之和为 Vi的引出次数,

而3A B =中的任一个元素ij b 代表的含义为从i 到j 长度为3的通路数 。 9、设无向图G=<V,E>,其中

)},, (), , (), , (), , (), , (), , (), , (), , (), , (), , {(},

, , , , , , , {g f h d h c g c d c g b f b e b e a b a E h g f e d c b a V ==试求:(1)a到h 所有基本通路;(2)从a 到h 的所有简单通路;(3)从a 到h 的距离。(书上习题8.4)

解:(1)从a 到h 的基本通路有如下8条:

(abgch);(abfgch);(abgcdh);(abfgcdh);(aebgch);(aebfgch);

(aebgcdh);(aefgcdh)

(2)从a 到h 的简单通路有与基本通路相同的8条,如上。

(3)从a 到h 的距离为4。

1、n n 2 2、下列命题中,P Q P →∧)

(是重言式。 3、公式)

, () (y x yQ x xP ∃→∀的前束范式为 )) , () ((y u Q x P y x ∨⌝∃∃。

4、设A ,B 为任意集合,命题B A B A =⇔=-φ的真值是 F 。

5、若命题变元P ,Q ,R ,的一个指派为(T ,F ,T ),则命题公式) () ) ((Q P R Q P G ∨⌝∨→∧=的真值是。

6、设P :天下雪,Q :我去市里,R :我有时间,则命题“如果天不下雪,我有时间,那么我就去市里”符号化为 Q R P →∧⌝ 。

8、试求公式) () (R P Q P ∧

⌝∨∧的特异析取范式和特异合取范式。 解:

则特异析取范式为:) () () () (R Q P R Q P R Q P R Q P ∧∧∨⌝∧∧∨∧∧⌝∨∧⌝∧⌝ 特异合取范式为:) () () () (R Q P R Q P R Q P R Q P ⌝∨∨⌝∧∨∨⌝∧∨⌝∨∧∨∨

10、证明:) () ())) (((R P Q R Q Q P ∨→=→→⌝∨⌝。

证明:) ()) (() ())) (((R Q Q P R Q Q P ∨⌝∨⌝∨=→→⌝∨⌝

=R Q Q P ∨⌝∨⌝∨

=R Q P ∨⌝∨

=) (R P Q ∨∨⌝

=) (R P Q ∨→