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 ∨→