离散数学习题答案-2015

离散数学习题答案

习题一

1、利用逻辑联结词把下列命题翻译成符号逻辑形式

（1） 他既是本片的编剧，又是导演 --- P∧ Q （2） 银行利率一降低，股价随之上扬 --- P→ Q （3） 尽管银行利率降低，股价却没有上扬 --- P∧ Q （4） 占据空间的、有质量而且不断变化的对象称为物质 --- M (S∧P∧T) （5） 他今天不是乘火车去，就是随旅行团去了九寨沟 --- P▽ Q

（6） 小X身体单薄，但是极少生病，并且头脑好使 --- P∧ Q ∧ R （7） 不识庐山真面目，只缘身在此山中 --- P→ Q

〔解释：因为身在此山中，所以不识庐山真面目〕

（8） 两个三角形相似，当且仅当他们的对应角相等或者对应边成比例

--- S (E∨T)

（9） 如果一个整数能被6整除，那么它就能被2和3整除。如果一个整数能被3整除，

那么它的各位数字之和也能被3整除

解：设 P – 一个整数能被6整除 Q – 一个整数能被2整除 R – 一个整数能被3整除 S – 一个整数各位数字之和能被3整除 翻译为：〔P→ 〔Q ∧ R〕〕∧ 〔R→ S〕

2、判别下面各语句是否命题，如果是命题，说出它的真值

〔1〕BASIC语言是最完美的程序设计语言 --- Y，T/F 〔2〕这件事大概是小王干的 --- N 〔3〕x2 = 64 --- N 〔4〕可导的实函数都是连续函数 --- Y，T/F 〔5〕我们要发扬连续作战的作风，再接再厉，争取更大的胜利 --- N 〔6〕客观规律是不以人们意志为转移的 --- Y，T 〔7〕到2020年，中国的国民生产总值将赶上和超过美国 --- Y，N/A 〔8〕凡事都有例外 --- Y，F

3、构造下列公式的真值表，并由此判别哪些公式是永真式、矛盾式或可满足式

〔1〕〔P∨〔～P∧ Q〕〕→ Q 解： P 0 0 1 1 Q 0 1 0 1 ～P∧ Q 0 1 0 0 P∨〔～P∧ Q〕 0 1 1 1 〔P∨〔～P∧ Q〕〕→ Q 1 1 0 1 可满足式 〔2〕~〔4〕表略：〔2〕可满足式、〔3〕永真式 、〔4〕可满足式 .

.

4、利用真值表方法验证下列各式为永真式

〔1〕~〔8〕略

5、证明下列各等价式

〔3〕P→〔Q∨ R〕 〔P→ Q〕∨〔P→ R〕 证明：左式  ～P∨Q∨ R

 ～P∨Q∨～P∨ R

 〔～P∨Q〕∨〔～P∨ R〕

 〔P→ Q〕∨〔P→ R〕 右式

〔4〕〔P∧ Q〕∨〔R∧ Q〕∨〔R∧ P〕 〔P∨ Q〕∧〔R∨ Q〕∧〔R∨ P〕 证明：左式  (〔P∨R〕∧ Q〕∨〔R∧ P〕

 (〔P∨R〕∨R))∧(〔P∨R〕∨P))∧〔Q∨R〕∧〔Q∨P〕  〔P∨ Q〕∧〔R∨ Q〕∧〔R∨ P〕 右式

6、如果P∨ Q  Q∨R,能否断定 P  R ？ 如果P∧ Q  Q∧R，能否断定 P  R？如果～P  ～R，能否断定 P  R？

解： 〔1〕如果P∨ Q  Q∨R，不能判断P  R，因为如果 Q = P∨ R, 那么P∨ QP∨P∨ R  Q∨R，但P可以不等价于R. 〔2〕如果P∧ Q  Q∧R，不能判断P  R，因为如果 Q = P∧ R, 那么P∧ QP∧P∧ R  Q∧R，但P可以不等价于R.

〔3〕如果～P  ～R，那么有P  R，因为～P  ～R，则～P <-> ～R为永真式，与有P <-> R为永真式，所以P  R.

8、把下列各式用↑等价表示出来

〔1〕(P∧Q)∨～P

解：原式  ((P↑Q)↑(P↑Q))∨(P↑P)

 (((P↑Q)↑(P↑Q))↑((P↑Q)↑(P↑Q)))↑((P↑P)↑(P↑P))

9、证明：{ ～ →}是最小功能完备集合

证明: 因为{～,∨}是最小功能完备集合,所以,如果{ ～ →}能表示出∨,则其是功能完备集合。由于 P ∨ Q  (～P)→Q ,所以{ ～ →}是功能完备集合。因为～ →不能相互表示，所以{ ～ →}是最小功能完备集合；同理可证：{非，条件非}也能将或表示出来： P ∨ Q  ～(～P !→ Q)

8、分别利用真值表法和等价变换法求下列公式的主合取X式与主析取X式:

(3) P→(R∧(Q→P)) 解：真值表法

P Q R Q→P .

R∧(Q→P) P→(R∧(Q→P)) .

0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 0 0 1 1 1 1 0 1 0 0 0 1 0 1 1 1 1 1 0 1 0 1 所以： 主合取X式为 = (～P∨Q∨R)∧(～P∨～Q∨R) = M4∧M6

主析取X式为 = (～P∧～Q∧～R)∨(～P∧～Q∧R)∨(～P∧Q∧～R)∨(～P∧Q∧R)∨(P∧～Q∧R)∨(P∧Q∧R) = m0∨m1∨m2∨m3∨m5∨m7 等价变换法〔略〕

(4) (P→(Q∧R))∧(～P→(～Q∧～R)) 解：真值表法 P Q R Q∧R ～Q∧～R P→(Q∧R) ～P→(～Q∧～R) 1 0 0 0 1 1 1 1 (P→(Q∧R))∧(～P→(～Q∧～R)) 1 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 1 1 0 0 0 1 所以： 主合取X式为 = (P∨Q∨～R)∧(P∨～Q∨R)∧(P∨～Q∨～R)∧(～P∨Q∨R)∧(～P∨Q∨～R)∧(～P∨～Q∨R) = M1∧M2∧M3∧M4∧M5∧M6

主析取X式为 = (～P∧～Q∧～R)∨(P∧Q∧R) = m0∨m7 等价变换法〔略〕

14、从A,B,C,D 4个人中派2人出差，要求满足下列条件：如果A去，则必须在C或D中选一人同去；B和C不能同时去；C和D不能同时去。用构造X式的方法决定选派方案。

解：由题设 A：A去，B：B去，C：C去，D：D去则满足条件的选派应满足如下X式： 〔A→〔CD〕〕∧～〔B∧C〕∧～〔C∧D〕

构造和以上X式等价的主析取X式 〔A→〔CD〕〕∧～〔B∧C〕∧～〔C∧D〕

〔～A∧～B∧ ～C ∧D 〕∨〔～A∧～B∧～C∧～D〕∨〔～A∧～B∧C∧～D〕∨〔～A∧B∧～C∧～D〕∨〔A∧～B∧C∧～D〕∨〔A∧～B∧～C∧D〕∨〔～A∧B∧～C∧D〕∨〔A∧B∧～C∧D〕

.

.

共有八个极小项，但根据题意，需派两人出差，所以，只有其中三项满足要求： 〔A∧～B∧C∧～D〕，〔A∧～B∧～C∧D〕，〔～A∧B∧～C∧D〕 即有三种方案：A和C去或者A和D去或者B和D去。

15、证明下列蕴含试：

〔1〕P→Q=>P →(P∧Q)

证明：P→Q  ～P∨Q  T∧(～P∨Q)  (～P∨P)∧ (～P∨Q)  ～P∨(P∧Q)  P →(P∧Q)

所以，这是个等价式，因此也是个蕴含式 〔2〕(P→Q) →Q=> (P∨Q)

证明：(P→Q) →Q  ～(～P∨Q) ∨Q  (P∧～Q) ∨Q  (P∨Q) ∧(Q∨～Q)  (P∨Q) ∧ T  (P∨Q)

所以，这是个等价式，因此也是个蕴含式 〔3〕P∧～P∧R=>S

证明：P∧～P∧R  F => S (F可蕴含任何命题公式) 〔4〕P=>Q∨R∨～R

证明：P=>T Q∨R∨～R 〔任何公式可蕴含永真式〕

18、一个有钱人生前留下了一笔珍宝，藏在一个隐秘处。在他留下的遗嘱中指出寻找珍宝的线索如下：

（1） 如果藏宝的房子靠近池塘，那么珍宝不会藏在东厢房。 （2） 如果房子的前院栽有大柏树，那么珍宝就藏在东厢房。 （3） 藏宝房子靠近池塘。

（4） 要么前院栽有大柏树，要么珍宝埋在花园正中地下。 （5） 如果后院栽有香樟树，珍宝藏在附近。 请利用蕴含关系找出藏宝处

解：根据给定的条件有下述命题： P：珍宝藏在东厢房 Q：藏宝的房子靠近池塘 R：房子的前院栽有大柏树 S：珍宝藏在花园正中地下 T：后院栽有香樟树 M：珍宝藏在附近 根据题意，得出：

〔Q→～P〕∧〔R→P〕∧Q∧〔R∨S〕∧〔T→M〕 ？ 〔Q→～P〕∧〔R→P〕∧Q∧〔R∨S〕∧〔T→M〕 ～P∧〔R→P〕∧〔R∨S〕∧〔T→M〕 ～R∧〔R∨S〕∧〔T→M〕 S∧〔T→M〕

S 即珍宝藏在花园正中地下

20、演绎证明下面各蕴含式：

.

.

〔4〕(R→Q)∧(R→S),(Q→E)∧(S→B),～(E∧B),(P→R) ～P 证明：运用反证方法，将结论的非纳入前提，证明步骤如下 [1] P p(附加前提) [2] P→R p

[3] R T [1,2] I [4] (R→Q)∧(R→S) p

[5] Q∧S T [3,4] I [6] (Q→E)∧(S→B) p

[7] E∧B T [5,6] I [8] ～(E∧B) p

[9] F(矛盾式) T [7,8] E

〔5〕P→(Q→R),Q→(R→S)  P→(Q→S)

证明：运用cp法，将结论条件式的前件作为前提，证明步骤如下 [1] P p(附加前提) [2] P→(Q→R) p

[3] Q→R T [1,2] I [4] Q→(R→S) p

[5] R→(Q→S) T [4] E [6] Q→S T [3,5] I [7] P→(Q→S) CP [1,6]

21、把下列句子演绎成逻辑形式，并给出证明

〔2〕某公司发生了一起盗窃案，经仔细侦察，掌握了如下一些事实：

 被盗现场没有留下任何痕迹

 失盗时，小花或则小英正在卡拉ok厅

 如果失窃时小胖正在附近，他就会习惯性地破门而入偷走东西后扬长而去  如果失盗时小花正在卡拉ok厅唱歌，那么金刚是最大的嫌疑者  如果失盗时小胖不在附近，那么他的女友小英会和他一起外出旅游  如果失盗时小英正在卡拉ok厅唱歌，那么瘦子是最大的嫌疑者 根据以上事实，请通过演绎推理找出偷窃者

解：根据给定的条件有下述命题： P：现场无任何痕迹

Q：失窃时，小花在OK厅 R：失窃时，小英在OK厅 S：失窃时，小胖在附近 T：金刚是偷窃者 M：瘦子是偷窃者

则根据案情有如下命题公式：

{P，Q∨R，S→～P，Q→T，～S→～R，R→M}

① P P ② S→～P P

.

.

③ ～S T①②I ④ ～S→～R P

⑤ ～R T③④I ⑥ Q∨R P

⑦ Q T⑤⑥I ⑧ Q→T P

⑨ T T⑦⑧I 即 金刚是偷窃者

23、利用消解法证明下列各蕴含式：

〔3〕P→(Q→R),Q→(R→S) P→(Q→S) 证明： P→(Q→R) ～P∨～Q∨R Q→(R→S) ～Q∨～R∨S ～〔P→(Q→S)〕 P∧Q∧～S

因此子句集合 = { ～P∨～Q∨R，～Q∨～R∨S，P，Q，～S } 消解过程如下：

[1] ～P∨～Q∨R p [2] P p

[3] ～Q∨R 由[1，2]归结 [4] Q p

[5] R 由[3，4]归结 [6] ～Q∨～R∨S p [7] ～S p

[8] ～Q∨～R 由[6，7]归结 [9] ～R 由[4，8]归结 [10] FLASE □由[5，9]归结

导出空子句

习题二

1、把下列谓词翻译成谓词公式

〔1〕每个有理数都是实数，但是并非每个实数都是有理数，有些实数是有理数 解： R(x) -- x是实数 Ra(x) -- x是有利数

翻译如下：(x)( Ra(x)→R(x))∧～(x)( R(x)→Ra(x))∧(x)( R(x))∧Ra(x)〕 〔2〕直线a和b平行当切仅当a和b不相交 解： A(x) -- x是直线 F(x，y) -- x与y平行 G〔x,y) -- ｘ与ｙ相交

翻译如下：(ａ)(ｂ)〔A(ａ)∧A(ｂ)→ (F(ａ，ｂ)～G〔ａ,ｂ)〕) 〔3〕除非所有的会员都参加，这个活动才有意义 解： A(x) -- ｘ是会员

.

.

B(x) -- x有意义 ａ -- 这个活动 F(x，y) -- ｘ参加ｙ

翻译如下：B〔ａ〕→(x)〔A(x)→F(x，ａ)〕 或 ～(x)〔A(x)→F(x，ａ)〕→～B〔ａ〕 〔4〕任何正整数不是合数就是质数 解： A(x) -- ｘ是正整数 Ｂ(x) -- ｘ是合数 Ｃ(x) -- ｘ是质数

翻译如下：(x)〔A(x)→Ｂ(x)Ｃ(x)〕

（6） 凡是存钱的人都想有利息，如果没有利息，人们就不会存钱 解： A(x) -- ｘ是存钱的人

F(x，y) -- ｘ想有ｙ P -- 存钱没有利息 Q: -- 人们不存钱 a: -- 利息

翻译如下：(x)〔A(x)→F(x，a)〕∧〔P→Q〕

2、设论域D = {0, 1, 2}，把下列公式用不含量词的公式表示出来

〔3〕(x)[～P(x)]∨(x)Q(x)

解：上式  〔～P(0)∧～P(1)∧～P(2)〕∨ Q(0)∨ Q(1)∨Q(2)

3、指出下列公式中的约束变元和自由变元，并确定公式的辖域

解：略

5、把下列语句符号化，并确定相应谓词公式是永真式、可满足式、还是矛盾式

〔1〕如果两个数的积等于0，那么至少其中一个数为0，数x-1不等于0，所以数x-1和x+1的积也不等于0

解：设论域在任意数域集合，运用常规的数学符号，翻译如下

(x)(y)( xy = 0 → (x=0 ∨ y=0)) ∧ ((x-1 ≠0) → ((x-1)(x+1)≠ 0))

这是一个可满足式，但不是永真式，因为存在x=-1时，谓词公式不成立，但其它情况均成立，如果论域中不包含-1，为真，包含就不成立

〔2〕诚实的人都讲实话。小林不是诚实的，因而小林不讲实话 解： H(x) -- x诚实 T(x) -- x讲真话 a -- 小林 翻译如下： 〔(x)(H(x)→T(x))∧～H(a)〕→～T(a) 这是一个可满足式，因为否定条件命题前件，不一定后件命题一定为假。与小林虽然不诚实，但也可能讲实话

6、对于题目给定的解释，求下列各公式相应的真值

.

.

〔1〕 A = (x)[P(x)∨Q(x)]∧R(a)，解释 D ={1,2,3}，P(x): x2+x=2; Q(x): x是素数；R(x): x<3; a = 1

解： 根据解释，A变为 〔P(1)∨Q(1)〕∧〔P(2)∨Q(2)〕∧〔P(3)∨Q(2)〕∧R(1)，根据P(x), Q(x), R(x)的定义，显然P(1)∨Q(1) = 1，P(2)∨Q(2) = 1，P(3)∨Q(2) = 1，R(1) =1，所以整个公式解释为真

〔2〕 A=P(a, f(b))∧P(b,f(a)), B=(x)(y)P(y,x), C = (y)(x)P(y,x), E = (x)(y)[P(x,y)→P(f(x),f(y))]，解释：D={2,3}, a = 3, b = 2, f(2)=3, f(3) =2，P(2,2)=0, P(2,3)=0, P(3,2)=P(3,3) = 1 解： 根据解释，

A变为 P( 3, 3 ) ∧ P( 2, 2 ) = 1 ∧ 0 = 0 ， 真值为假 B变为 (P(2,2)∨P(2,3))∧(P(3,2)∨P(3,3)) = 〔0∨0〕∧〔1∨1〕= 0， 真值为假 C变为 (P(2,2)∧P(2,3))∨(P(3,2)∧P(3,3)) = 〔0∧0〕∨〔1∧1〕= 1， 真值为真 E变为 (P(2,2)→P(3,3))∧(P(2,3)→P(3,2))∧(P(3,2)→P(2,3))∧(P(3,3)→P(2,2)) = 〔0→1〕∧〔0→1〕∧〔1→0〕∧〔1→0〕= 0， 真值为假

7、设论域为整数集合Z，试判定下面各公式是否是永真式，矛盾式或可满足式

2

〔1〕(x)[x>-10∧x≥0] 答：为假命题

〔2〕(x)[2x>8∧x2-6x+5≤0]

答：为真命题，当4，5使满足谓词公式 〔3〕(x)(y)[x+y=1024]

答：为真命题，对任意整数x，y取值为1024-x与可 〔4〕(y)(x)[xy<10∨x+y≥2] 答：为真命题，y=0与成立

9、证明下列各式成立：

〔1〕(x)(y)[P(x)→Q(y)] (x)P(x)→(y)Q(y)

证明：右式 (x)(y)[~P(x)∨Q(y)] (x)~P(x)∨(y)Q(y)(x)P(x)→(y)Q(y)

10、判别(x)[P(x) →Q(x)](x)P(x)→(x)Q(x)是否成立，如果成立，请给出证明；如果不成立，找一个解释予以说明

解：(x)[P(x)→Q(x)] (x)[～P(x)∨Q(x)] (x)～P(x)∨(x)Q(x) (x)P(x)→(x)Q(x) 显然和(x)P(x)→(x)Q(x)不等价，现构造如下解释

设论域为D={a,b}，P(a) = 0, P(b) = 1, Q(a) = 0, Q(b) = 0, 则(x)[P(x)→Q(x)]解释为真，而(x)P(x)→(x)Q(x)解释为假，所以不等价

11、把下列公式化为等价的前束X式，再求出对应的SKolemX式

〔4〕(x)[～P(x,0)→((y)P(y,f(x))∧(z)Q(x,z))]

解：原式 (x)[P(x,0)∨((y)P(y,f(x))∧(z)Q(x,z))] (x)(y) (z) [P(x,0)∨(P(y,f(x))∧Q(x,z))]

.

.

其SKolemX式为：(x)(z) [P(x,0)∨(P(g(x),f(x))∧Q(x,z))]

13、证明下列各式成立

〔1〕(x)(y)[P(x)∧Q(y)](x)P(x)

证明：左式 (x)P(x)∧(y)Q(y) (x)P(x) 〔2〕~((x)P(x)∧Q(a))(x)P(x)→~Q(a)

证明：左式  ~(x)P(x)∨~Q(a) (x)P(x)→~Q(a)

15、下面给出了对(x) [P(x) ∨Q(x)](x) P(x) ∨(x)Q(x)]的证明： 〔原证明过程略〕

试判断这个证明是否正确。你能给出一个证明吗？

答：这个证明不正确，因为：如果 P  Q 则~Q~P 而 ~P ~Q不一定成立，因此在这个证明过程中，第二步到第三步的蕴含不成立

17、判别下面各个推理是否正确，如果不正确，指出错在什么地方〔题目不再重复〕

〔1〕答：不正确，全称指定应该变为其他非x的变元，可修改为：P(y)→Q(x) 〔2〕答：正确

〔3〕答：不正确，全称指定应该使用相同的个体常量，可修改为：P(a)∨Q(a) 〔4〕答：题目不正确，存在量词的指导变元应该是另外的变元符号

〔5〕答：不正确，存在量词的辖域应该包含全部的谓词，可修改为：(x)[P(x)→Q(x) ] 〔6〕答：不正确，对不同的个体常元应该用不同的变元进行存在指定，可修改为：(x)[P(x)→Q(b) ]

〔7〕答：不正确，推理过程中，应该先使用存在指定，然后使用全称指定

习题三

4、仔细区分集合中的关系符号 ∈ 和，并判断下列各蕴含关系的真假 〔题目内容，见课本〕

〔1〕真，根据子集的定义，任何属于B集合的元素也属于C集合

〔2〕假，例如：A = {1,2} B = {{1,2}, 2, 3} C=B，1属于A，但并不是C集的元素 〔3〕假，例如：A={1,2} B={1,2,3} C={{1,2,3}}，A不是C的元素 〔4〕假，例如：A={1,2} B={1,2,3} C={{1,2,3}}，A不是C的子集 〔5〕假，例如：A=1 B={1,2,3} C={{1,2,3}}，A不是C的元素 〔6〕真，子集关系具有传递性

9、证明下列各式

〔1〕A∩(B-C) = (A∩B)-(A∩C)

证明：左式 = A∩(B∩~C) = (A∩B∩~C) ∪ (A∩B∩~A) = (A∩B) ∩(~C∪~A) = (A∩B) ∩~ (A∩C) = (A∩B)-(A∩C) = 右式

.

.

〔2〕A - (B∪C) = (A-B) ∩(A-C)

证明：右式 = (A∩~B)∩(A∩~C) = A∩~B∩~C = A∩~(B∪C) = A - (B∪C) = 左式 〔3〕(A-B)-C = A-(B∪C)=(A-C)-B

证明：(A-B)-C = A∩~B∩~C = A∩~(B∪C) = A-(B∪C) = A∩~C∩~B = (A-C)-B 〔4〕A∩(B∪C)=(A∩B)∪C CA 证明：充分性

∵ A∩(B∪C)=(A∩B)∪C (A∩B)∪(A∩C) = (A∩B)∪C

假设C不是A的子集，则C中必存在元素c在C中而不在A中，那么c一定不在等式的左端集合中，而一定在右端集合中，矛盾 ∴ CA 必要性

∵ CA ，∴ A∩C = C ，等式两端同时并上另一个集合，等式成立 ∴(A∩B)∪(A∩C) = (A∩B)∪C A∩(B∪C)=(A∩B)∪C 〔5〕A∩(B⊕C) = (A∩B)⊕(A∩C)

证明：左式 = A∩〔B ∪C-B∩C〕= A∩〔(B ∪C) ∩(~B∪~C)〕= A∩(B ∪C) ∩(~B∪~C)=AB~C + AC~B

右式 = 〔(A∩B)∪(A∩C)〕- 〔(A∩B)∩(A∩C)〕= 〔A∩(B∪C)〕∩~〔A∩B∩C〕=A∩(B∪C)∩(~A∪~B∪~C) = AB~C + AC~B 所以，左式 = 右式

10、下面三式中，哪个可得出B=C的结论

〔1〕A∪B=A∪C

答：不能得出此结论，因为如果 B≠ C,但B,C都是A的子集，A∪B=A∪C成立 〔2〕A∩B=A∩C

答：不能得出此结论，因为B≠ C，但A是C∩B子集，A∩B=A∩C成立 （2） A⊕B=A⊕C

答：能，因为A⊕A = Φ,Φ⊕A = A⊕Φ=A,同时，〔A⊕B〕⊕C = A⊕〔B⊕C〕 所以，已知等式两端 A⊕A⊕B=A⊕A⊕C Φ⊕B =Φ⊕C  B=C

16、求A={, a, {b}}的幂集

A

解：2 = {, {} , {a} , {{b}} , {,a} , {,{b}} , {a, {b}} , {, a, {b}}}

17、设A,B是任意两集合，证明

ABA B

〔1〕2 22 ，给出等号成立的条件

ABAB

证明：X 2 2 X 2 X  2  X  A  X  B => X  A  B

A B

 X 2 

等号成立的条件: A  B或B  A

A BA

(因为若A和B没有子集关系, 必有a A– B和 b B– A，使{a, b} 2 ，但{a, b} 2 B

2 )

.

.

〔2〕2 2 = 2 

ABAB

证明：X 2 2 X 2 X 2  X  A  X  B  X  A  B

A B

 X 2 

附加题：

证明等式(A⊕B) ⊕C = A⊕(B⊕C)

证明：A⊕(B⊕C) = A⊕((B-C)∪(C-B)) = (A - ((B-C)∪(C-B))) ∪(((B-C)∪(C-B))- A) = ~AB~C + ~A~BC + A~B~C + ABC (A⊕B) ⊕C = C⊕(A⊕B)

那么按上式的划简方式，就是把C替换为A, 把A替换为B,将B替换为C,所以

C⊕(A⊕B) = ~CA~B + ~C~AB + C~A~B + CAB = ~AB~C + ~A~BC + A~B~C + ABC习题

ABA B

四

1、设A={1,2,3,4},B={0,1,4,9,12}.分别把下面定义的从集合A到集合B的二元关系R用序偶的集合表示出来

〔1〕xRy x|y

解: R = {(1,0) ,(1,1),(1,4) ,(1,9) ,(1,12) ,(2,0) ,(2,4) ,(2,12) , (3,0) ,(3,9) ,(3,12) ,(4,0) ,(4,4) ,(4,12)} 〔2〕xRy  xy(mod 3)

解: R ={(1,1), (1,4) , (3,0) , (3,9) , (3,12) , (4,1) , (4,4)} 〔3〕xRy  y/x ∟(y-x)/2」

解: R ={(3,9), (3,12) , (4,9) , (4,12)}

2、用关系图和关系矩阵表示第1题中的各个关系

解：略

6、设在整数集Z上定义如下二元关系，试填写下表：

解：填表如下

R x|y x≡y(mod m) xy>0 xy≧0 x=y或|x-y|=1 x> y 22自反性 √ √ × √ √ × 反自反性 × × × × × √ .

对称性 × √ √ √ √ × 反对称性 × × × × × √ 传递性 √ √ √ × × √ .

(1) 因为x|x成立，所以自反性成立；所以反自反性不成立；因为x≠0时，x|0成立，但

0|x不成立，所以对称性不成立，因为 1|-1，和-1|1成立，所以反对称性不成立；但x|y,y|z成立，就一定有x|z成立，所以传递性成立

(2) 因为模m相等是整数集合上的等价关系，所以具有自反、对称、传递性

(3) 因为00 = 0，所以自反性不成立；因为x ≠ 0时必有 xx>0,所以反自反性不成立；因

为xy >0 必有yx>0,所以对称性成立；因此反对称性不成立；因为xy>0,yz>0,能得到x,y,z同号且不为0，所以，xz>0,所以传递性成立

(4) 因为xx≧0,所以自反性成立；因此，反自反性不成立；因为xy≧0,所以yx≧0，因此对

称性成立；因此，反对称性不成立；因为-1*0 ≧0，0*1≧0，但-1*1 < 0,所以传递性不成立

(5) 因为 x=x，所以自反性成立；因此反自反性不成立；因为|x-y|=1，所以| y-x |=1，因

此对称性成立；所以反对称性不成立；因为|1-2|=1，|2-3|=1，但|1-3|=2，所以传递性不成立

2222

因为 xx = xx，所以自反性不成立；反自反性成立；因为x> y成立，那么y>x就不成立，所以对称性不成立，反对称性成立；传递性成立

7、设R是集合A上的一个二元关系，合于xRy ∧ yRz => ~xRz,称R是A上的一个反传递关系。试举一个实际的反传递关系的例子

解：例如在人群集合上，建立父子关系，那么就是一个反传递关系，因为如果 甲是乙的父亲，乙是丙的父亲，那么甲和丙就一定不存在父子关系；另外，在正整数域上建立的倍数关系，也是一个反传递关系，因为如果 a 是 b的2倍，b是c的2倍，那么a 一定不是c的2倍

8、设R和S都是集合A上的二元关系，它们经过关系运算后得到A上的一个新关系。试判别当R和S同时具有下表左列某种指定性质时，经过指定的运算后所得到新关系也仍保持这种性质，把所得结论以√，×的形式填在下表中相应的位置上

自反性 反自反性 对称性 反对称性 传递性 R∩S √ √ √ √ √ R∪S √ √ √ × × R-S × √ √ √ × R○S √ × × × × -R × × √ × × R √ √ √ √ √ -1（1） 自反性的保持情况说明：

因为R,S都具有自反性，所以IAR,IAS，

因此IAR∩S,IAR∪S,所以自反性在R∩S，R∪S上保持

因为IAS，所以IA不是S补集的子集，因此也不是R∩-S的子集，所以自反性在R-S上不保持

因为R,S是自反的，所以对任意的a ∈A，〔a,a〕∈R,S，所以〔a,a〕∈R○S，因此自反性在R○S上保持

因为〔a,a〕∈R，所以〔a,a〕不属于-R,所以-R不具有自反性

-1-1

因为〔a,a〕∈R，所以〔a,a〕∈R，因此R具有自反性 （2） 反自反性的保持情况说明：

.

.

因为R,S都具有反自反性，等价于 IA∩R = Φ,IA∩S = Φ

因为IA∩R∩S =Φ，IA∩〔R∪S〕=Φ，所以R∩S，R∪S都是反自反的 因为IA∩R∩-S =Φ，所以 R-S也是自反的

对于R○S，假设〔a,b〕∈R,〔b,a〕∈S, 那么〔a,a〕∈R○S, 所以反自反在R○S上不一定保持

因为〔a,a〕不属于R，所以〔a,a〕一定属于-R，所以-R一定是自反的，一定不是反自反的

-1-1

因为〔a,a〕不属于R，所以〔a,a〕也不属于R，因此R一定是反自反的 （3） 对称性的保持情况说明：

-1-1-1-1-1-1

因为R,S是对称的，所以R=R,S=S，-R = (-R)=-R, -S = (-S)=-S

-1-1-1

因为〔R∩S〕=R∩ S= R∩S, 所以R∩S具有对称性

-1-1-1

因为〔R∪S〕=R∪ S= R∪S, 所以R∪S具有对称性

-1-1-1-1-1-1

因为〔R-S〕=〔R∩-S〕=R∩ 〔-S〕= R∩ -S = R∩-S，所以R-S具有对称性

-1-1-1

因为(R○S) = S○ R= S○R ,但S○R通常情况下与R○S不相同，所以对称性不一定保持，例如：R = {(a,b),(b,a)}, S = {(b,c),(c,b)},则R○S = {〔a,c〕},并不对称

-1-1

因为〔-R〕 = -R= -R，所以R的补是对称的

因为 R逆的逆就是R，既等于R的逆，所以R的逆是对称的 （4） 反对称性的保持情况说明：

-1-1

因为R,S是反对称的，所以R∩R IAS∩S IA

-1-1-1

因为〔R∩S〕∩〔R∩S〕= 〔R∩R〕∩〔S∩S〕 IA，所以R∩S具有反对称性

因为如果R = {(a,b)} S = {(b,a)},都是反对称的，但 R∪S = {(a,b),(b,a)}是对称的，所以R∪S不一定再保持对称性

因为R是反对称的，而R-S在R的基础上减少集合元素，因此也一定是反对称的 因为如果 R = {(a,b),(c,a)}, S = {(b,c),(a,a)}, 那么R○S = {〔a,c〕，〔c,a〕},变为对称的，所以反对称性，在复合运算下不一定保持

因为如果R = {〔a,b〕,(c,c)}是反对称的，但-R = {〔a,a〕,(b,b),(b,a),(a,c,),(c,a),(b,c),(c,b)},不是反对称的，所以反对称性在补集运算上不保持

-1-1-1-1

因为R∩R IA，有因为 R = (R),所以R是反对称的 （5） 传递性的保持情况说明：

22

因为R,S是传递的，所以RR, SS

222

因为〔R∩S〕 = 〔R∩S〕○〔R∩S〕 R∩S∩(R○S)∩(S○R)R∩S，所以传递性保持 如果R = {(a,b)}, S={(b,c)},都是传递关系，但R∪S = {(a,b),(b,c)}不再是传递关系，所以传递性在R∪S上不一定保持

如果R={(a,b),(b,c),(a,c)},S={(a,c)},分别是两个传递关系，但R-S = {(a,b),(b,c)}不再是传递关系，所以传递性在R-S上不一定保持

如果R={(a,b),(c,d)},S={(b,c),(d,e)},分别是两个传递关系，但R○S = {(a,c),(c,e)}不再是传递关系，所以传递性在R○S上不一定保持

如果A = {a,b,c}, R = {(a,b)}, 那么 –R = A ×A – R,显然不是传递的，所以传递性在-R上不一定保持

22-1-1-12-1

因为RR，所以 〔R〕R ，即〔R〕R，所以传递性在逆运算下保持

10、设R是集合A上的一个二元关系，证明

〔1〕R是自反的  IAR

.

.

证明:

R是自反的 => IAR

因为，R是自反的，所以对任意的A中元素a，有〔a,a〕∈R，即IA中任意元素都属于R，所以IAR

IAR => R是自反的

因为，对任意的A中元素a，有〔a,a〕∈IA，又IAR，所以〔a,a〕∈R，所以R是自反的 综上所述，R是自反的  IAR 〔2〕R是反自反的  IA∩R = Φ 证明：

R是反自反的 => IA∩R = Φ

因为，IA中的任意元素(a,a)，都不属于R，所以IA∩R = Φ IA∩R = Φ=> R是反自反的 因为IA∩R = Φ，所以IA中的任意元素(a,a)，都不属于R，即对任意的A中元素a，有〔a,a〕∈IA，都不属于R，所以R是反自反的 综上所述，R是反自反的  IA∩R = Φ

-1

〔3〕R是对称的  R = R 证明：

-1

R是对称的 => R = R

-1

因为对R中的任意元素〔a,b〕,因为R是对称的，所以〔b,a〕∈R，那么〔a,b〕∈R,所以

-1

RR

-1

因为对R中的任意元素〔a,b〕,那么〔b,a〕∈R，因为R是对称的，那么〔a,b〕∈R,所以-1

RR

-1

所以 R = R

-1

R = R => R是对称的

-1-1

对R中的任意元素〔a,b〕，因为R = R ,所以〔a,b〕也属于R，所以〔b,a〕∈R，因此R是对称的

-1

综上所述，R是对称的  R = R

-1

〔4〕R是反对称的  R∩RIA 证明:

-1

R是反对称的 => R∩RIA

-1-1

因为对任意(a,b)∈R∩R ,那么其就同时属于R和R ，那么〔b,a〕也属于R，根据反对称

-1

的定义，a = b，所以〔a,b〕∈IA ,所以R∩RIA

-1

R∩RIA => R是反对称的

-1

假设R不是反对称的，那么必定存在 a ≠b∧(a,b)∈R ∧ (b,a)∈R，那么〔a,b〕∈R∩R ,但〔a,b〕不属于IA，矛盾；因此R必是反对称的

-1

综上所述，R是反对称的  R∩RIA

2

（1） R是传递的  RR 证明：

2

R是传递的 => RR

2

因为对任意〔a,b〕∈R,必存在c，使得〔a,c〕,(c,b)属于R，因为R是传递的，所以(a,b)

2

属于R，因此RR 2

RR => R是传递的

2

因为对任意的R中的元素〔a,b〕，(b,c)，那么(a,c)必定属于R,也就属于R，所以R是传递的

.

.

综上所述，R是传递的  RR

11、设A={1,2,3,4},定义A上的关系 R = {(a,b)|a=b+2},S = {(x,y)|y=x+1∨x=2y} 求：

-12-12

R。S,R。S。R,R,(S)

解：根据题意，R={(3,1),(4,2)}，S={(4,2),(1,2),(2，3)，〔3，4〕} 所以：R。S = {〔3，2〕，〔4，3〕}

-1

S = {〔2，4〕，〔2，1〕，〔3，2〕，〔4，3〕}

-1

所以：R。S = {(4,4),(4,1)}

-1

R。S。R = {(4,2)}

2

R = 

-12

(S) = {(2,3),(3,4),(3,1),(4,2)}

mn

12、设A={a,b,c,d,e,f,g,h}，A上的二元关系R对应的关系图4-5所示，求使R=R的最小整数m和n(m < n)

16

答：R = R；简要说明如下：本关系图分为两个部分，R = R1 ∪ R2,因为 R1。R2 = R2。

222nnn35

R1 = , 所以R = R1∪ R2 ,同理R = R1∪ R2 ,又因为 I1 = R1,I2=R2 ；3，5的

15 151516

最小公倍数为15，所以I = R,所以R = Iº R = Rº R = R

13、设R是集合A上的二元关系，证明：

n

〔1〕IA = IA

证明：因为单位关系的关系矩阵为单位矩阵，而复合运算就是矩阵的乘法，根据单位矩阵的

n

性质，IA = IA

〔2〕IAº R=RºIA =R

证明：同上，因为单位矩阵左乘、右乘一个矩阵，结果不变；所以IAº R=RºIA =R

n23n

〔3〕(R∪IA)=IA∪R∪R∪R…∪R

证明：根据书中并集关系复合的定理〔4.2〕，展开，并利用上述1，2的结论，与可得证〔严格可用归纳法〕

15、写出第12题中关系图对应的关系矩阵，并利用warshall算法求这个关系的传递闭包 解：

2

.

.

0010MR0000

1000000001000000000000010 0000001000010000000010000000010Mt(R)111000001110000011100000000000111111 1111000111110001111100011111

习题五

1、设 A = {(a,b)| a,b  N}，定义A上的一个二元关系 R = {((a,b),(c,d)) | ad = bc } 证明：R 是 A 上的等价关系

证明：

〔自反性〕因为 对任意〔a,b〕 A, 都有：ab = ba, 既(〔a,b〕,(a,b))  R，所以R是自反的

〔对称性〕如果〔〔a,b〕,(c,d)〕 R ,那么ad = bc, 所以 cb = ad,既〔〔c,d〕,(a,b)〕R, 所以R是对称的 〔传递性〕如果〔〔a,b〕,(c,d)〕 R, ((c,d),(e,f))  R, 那么 ad = bc ,cf = ed ,因此，adcf = bced (注：如果 0 ∉ N 中)， 那么af = eb, 所以〔〔a,b〕,(e,f)〕 R,R具有传递性

综上所证，R是A上的等价关系

3、集合 A = {1，2，3，4}的一个分化为 S0={{1,2,4},{3}},求由S0导出的A上的一个等价关系R

解：等价关系R = {1，2，4}×{1，2，4}∪{3}×{3} = {〔1，1〕，〔2，2〕，〔4，4〕，〔1，2〕，〔1，4〕，〔2，1〕，〔2，4〕，〔4，1〕,(4,2),(3,3)}

4、试确定在4个元素的集合上可以定义的等价关系数目 解：

在此集合上可以确定的4分划个数为：1

在此集合上可以确定的3分划个数为：c(4,2) = 6

在此集合上可以确定的2分划个数为：c(4,1) + c(4,2) /2 = 7 在此集合上可以确定的1分划个数为：c(4,4) = 1

所以共可定义15个等价关系

6、设R是非空集合A上的一个二元关系，具有对称性和传递性。证明：如果对每一个xA，

.

.

存在yA使xRy，那么，R是A上的等价关系

证明：因为对每一个xA，存在yA使xRy，由于R是对称的，所以yRx；又因为R是传递的，当xRy 并且 yRx，那么xRx。所以R是自反的。综上所述，R是自反的，对称的和传递的，因此R是A上的等价关系

8、设A是由54的正因子构成的集合，“|〞表示整除。画出偏序集对应的Hasse图

解：先求出偏序集，然后求处相应的cover，然后画出Hasse图 A={1，2，3，6，9，18，27，54}

COVER(|)={(1,2), (1,3), (2,6), (3,6), (3,9),(6,18), (9,18), (9,27), (18,54), (27,54)} 最大元：54 最小元：1

有4个包含元素最多的全序子集: L1={54,27,9,3,1} L1={54,18,9,3,1} L1={54,18,6,3,1} L1={54,18,6,2,1}

54 18 6 2 1

3 9 27

9、设A={a,b,c},画出偏序集合对应的Hasse图。试比较本题与上题Hasse图的异同

.

.

解：

{a,b,c} {a,b} {a} {a,c} {b} 

{b,c} {c}

两图的相同点 ： 都有最大〔小〕元 不同点：最大线序一个为5，一个为4

11、设R是集合A上的一个等价关系。现在在等价类之间定义一个新关系S使得R的任何等价类[a]和[b]满足[a]S[b]aRb，判别S是一个什么关系

解:根据题目信息，猜测是等价关系，说明如下：

（1） 因为对任意的aA，aRa成立〔R是A上的等价关系，是自反的〕，所以[a] S [a],S

是自反的

（2） 假设[a] S [b]成立，那么aRb；因为R是对称的，所以bRa,因此[b] S [a]成立，

所以S是对称的

（3） 假设[a]S[b],[b]S[c]成立，则aRb,bRc，因为R是传递的，所以aRc成立，因此[a]S[c]

成立，所以S是传递的

综上所述，S是等价类集合上的等价关系

习题六

1、设A={1，2，3，4}，B=A×A,确定下述集合是否为A到B的全函数或部分函数

〔1〕{〔1，〔2，3〕〕，〔2，〔2，2〕〕，〔3，〔1，3〕〕，〔4，〔4，3〕〕} 答：根据本书全函数的定义，这是从A到B的全函数 〔2〕{〔1，〔1，2〕〕，〔1，〔2，3〕〕，〔3，〔2，4〕〕}}

答：根据本书函数的定义，每个原像只能有一个像，所以此定义不是A到B的函数 〔3〕{〔1，〔3，3〕〕，〔2，〔3，3〕〕，〔3，〔2，1〕〕，〔4，〔4，1〕〕}

.

.

答：根据本书全函数的定义，这是从A到B的全函数

2、判别以下关系中哪些是全函数

〔1〕{〔n1,n2〕|n1,n2N,0<2n1-n2<5}

答：此关系不满足全函数的定义，因为〔3，5〕，〔3，4〕，〔3，3〕，〔3，2〕，〔3，1〕都属于此关系，但它违反了本书函数是单值的定义 〔2〕{〔n1,n2〕|n1,n2N,n1是n2的正因子个数}

答：如果N集合中不包含0，那么此关系是全函数，因为任意一个自然数按正因子个数的定义，都有确切的值，因此是全函数

〔3〕{〔S1,S2〕|S1,S2⊆{a,b,c,d} 且S1∩S2=}

答：此关系不满足全函数的定义，因为〔，{a}〕,(,{b})等属于此关系，但它违反了本书函数是单值的定义

〔4〕{〔a,b〕|a,b  N,gcd(a,b)=3}

答：此关系不满足全函数的定义，因为就1，2而言，3不是他们的因数；同时推论开，所有不是3的质数，3都不是他们的因数，因此他们就没有像，所以不是全函数

2

〔5〕{〔x,y〕|x,y  Z,y=x}

答：此关系是全函数，因为任意一个整数，都能求到唯一的平方数。所以按定义是全函数

7、确定下列映射是否单射、满射或双射：

（1） f1: N→R,f1(n)=lnn

答：如果0不属于N,那么这是一个单射函数，因为任意一个自然数都可以求其自然对数，同时ln是单调函数，所以是单射函数。但是并非任意一个实数其原像都是自然数，所以不是满射

（2） f2:N→N,f2(n)为不超过n的素数数目

答：这是一个满射函数，但不是单射。因为f(3)=f(4)=3,与不超过3，4的素数都是1，2，3，个数为3；同时因为自然数中的素数有无穷多，所以对任意一个自然数m，都能找到从第m个素数起到第m+1个素数〔但不包括第m+1个素数〕的所有自然数，其函数值都等于m，所以是满射，但不是单射〔注：7是第5个素数，11是第6个素数，所以f(7)=f(8)=f(9)=f(10)=5〕

n2

（3） f3:N×N→N,f3(n1,n2)=(n1+1)

答：这既不是单射，也不是满射〔与0是否属于N无关，以下说明以0不属于N而言〕；因为任意两个自然数，都能求到此函数值，所以是全函数。因为f(1,2)=f(3,1)=4,所以不是单射函数；同时1没有原像，所以不是满射函数

2

（4） f4：R→R,f4(x)=x+2x-15

答：一元二次函数，既不是单射，也不是满射；其几何图像为抛物线

3

（5） f5：Z→Z，f5(x)=1+2x

答：这是一个单射函数，但不是满射；因为3次曲线是单调函数，所以在定义域子集X围也是单调的，所以是单射函数。但任意一个整数像的原像却不一定是整数。所以不是满射

AAAA

（6） A是集合，f6:2×2→2×2,f6(x,y)=(x∪y,x∩y) 答：假设A = ，那么这是一个双射函数〔请同学思考〕

假设A不是空集，那么此函数既不是单射，也不是满射；因为：对f(x,y)=f(y,x),所以不是单射；另外对于〔，A〕,没有原像；所以不是满射

.

.

（7） f7:R×R→R,f7(x,y)=x+y,f8:R×R→R,f8(x,y)=xy 答：此两个函数，都不是单射，但都是满射函数

8、设X是有限集合，f:X→X,证明：

（1） 如果f是单射，f必是双射

证明：假设f不是满射，那么就必定有元素没有原像，由于X是有限集合，根据鸽茏原理：原像元素个数〔鸽子〕就比像元素个数多〔鸽笼〕，所以必定有多个原像会映射到相同的像上，所以不是单射。矛盾。所以f必定是满射，即是双射 （2） 如果f是满射，f必是双射

证明：假设f不是单射，那么必定存在多个元素映射到相同的像上。由于X集合是有限的，那么因变量的个数就少于自变量个数，因此f就不是满射。与题设矛盾。因此f必是单射，既是双射

2

9、设f是有限集X上的一个函数，满足∀xX,f(x)=x；证明：f是双射

22

证明：因为f(x) = f。f(x) = x, 既是f = Ix；所以f是自己的逆函数，根据逆函数的性质，f必是双射

18、证明下列集合A和B等势

〔1〕A = (0,1), B = (-2,2) 证明：如果能找到从A到B的双射函数，就能说明A和B等势，存在A到B上的这样的函数；

x

例如：f(x) = 4x - 2 或 f(x) = 5-3 〔2〕A = (-∞,+∞),B = (0,+∞) 证明：如果能找到从A到B的双射函数，就能说明A和B等势，存在A到B上的这样的函数；

x

例如：f(x) = e

〔3〕A = (0,1),B = (1/4,1/2) 证明：如果能找到从A到B的双射函数，就能说明A和B等势，存在A到B上的这样的函数；例如：f(x) = 1/4 x + 1/4

〔4〕A = N, B = {(m,n)|m,n  N ∧ m≤n}

证明：如果将B集合写成如下的分化并集形式：B = B1∪B2∪B3……,这样B成为可数个集合的并集，其中Bi = {〔i,i〕,(i,i+1),(i,i+2)……},是一个可数集合，根据书中定理，可数个可数集合的并集合依然是可数集，那么就和N等势，证毕

习题八

26、证明：在任何人数不少于2的人群中，至少有2个人在其中有同样多的熟人

证明：设人群人数为n〔≥〕，那么每个人有可能有的熟人数为〔0，1，…n-1〕n 种情况,但是，当有人没有熟人时，就不可能有人有n-1个熟人；同理，当有人认识其余的所有人时，就不存在有人没有熟人，因此每个人可能有的熟人数只有n-1种。而一共有n 个人，那么根据鸽笼原理，必存在至少有2个人在其中有同样多的熟人的情况

习题十

.

.

1、设G是一个〔n,m〕简单图；证明：m≤C(n,2)等号成立，当且仅当G是完全图

证明：此题有两个内容，第一方面证明简单图满足 m≤C(n,2)，第二证明 ，m=C(n,2)当且仅当G是完全图

(1): 因为在简单无向图中，每个结点的最大度数为n-1，所以图的总度数的上限为n(n-1),所以边的上限为n(n-1)/2，因此任意一个简单无像图G，其边数满足：m≤n(n-1)/2=C(n,2) (2)： m=C(n,2) ⇒ G是完全图

因为，当m=C(n,2)时，全图的总度数为n(n-1),因此其平均点度为(n-1)，因为n阶简单无向图中点度的最大值为〔n-1〕,所以此时每个点的度数都相同并为〔n-1〕,根据完全图的定义，此图为完全图

G是完全图⇒ m=C(n,2) 当G为完全图时，既每个结点都和其他结点相邻，所以全图的总边数 m = n(n-1)/2 = C(n,2)

4、证明：在〔n,m〕图中 δ≤2m/n≤Δ

证明：因为2m/n 代表简单无向图的平均点度值，所以平均值大于等于最小值，小于等于最大值，结论成立

2

6、设G是〔n,m〕简单二部图，证明：m≤n/4

证明：设G的两个顶点集合中顶点个数分别为n1,n2，并有 n = n1 + n2 (1式)；同时，在简单二部图中，当其为完全二部图是，其边数最大，与max(m) = n1 × n2 (2式)；联立

2

〔1〕〔2〕式，通过高等数学的知识，当n1=n2=1/2n时，max(m)取得最大值 n/4 ，所以一

2

般〔n,m〕简单二部图，其边数小于等于此最大值既 m≤n/4

9、如果G ≌ G’，称G是自补图；确定一个图为自补图的最低条件：画出一个自补图

解：因为G和自己的补图同构，那么G和G’应该有相等条数的边，所以 m = m’，又因为m + m’= n(n-1)/2，所以G的边的条数必须满足m = n(n-1)/4.因此图G的阶数或阶数减一必需是4的倍数，这就是最低条件。图略〔4阶或5阶这样的图都容易画出〕

10、判断图10-29中的两个图是否同构，并说明理由

答：这两个图不同构，因为这两个图中，都有唯一的3度点，因此在同构映射中一定相互对应，但一个图中的3度点连接两个一度点，而在另一个图中其3度点只连接了一个一度点，不能相互映射。因此不同构

15、如果u和v是图G中仅有的两个奇数度结点，证明u和v必是连通的

证明：假设u,v分别在图G的两个分中G1,G2中，那么G1，G2各自的总结点度数就是奇数，与握手定理矛盾。因此，u,v必在一个连通分支中，所以是连通的

16、证明：G是二部图当且仅当G的回路都是偶长回路〔非平凡图， n>1〕

.

.

证明：〔1〕先证明在二部图中，所有奇长道路的两个端点必定分别在两个顶点集合中 使用归纳方法：

A〕当道路长度L(P)=1时，就是图G的边和其两个端点，根据二部图的定义，两个端点分别在两个顶点集合中

B〕假设道路长度L(P)=2n+1 (n>0)时结论成立，与P=V1V2….V2n+2,其中V1,V2n+2分别属于两个顶点集合

C) 当L(P)=2(n+1)+1 〔n>0〕时，P=V1V2….V2n+2V2n+3V2n+4；当我们删除此道路的最后两个结点，道路长度变为L(P’)=2n+1，根据(B)的假设，那么V1,V2n+2就分别在两个顶点集合。现在把V2n+3加入到道路中，因为V2n+3是V2n+2的邻结点，所以V2n+3在V2n+2的对集中，既和V1在一个顶点集合中；同理V2n+4就在V1的对集中，也就是V1,V2n+4在不同的顶点集合中 综上所述，〔1〕结论成立

〔2〕G是二部图 ⇒ G的回路都是偶长的 设C是G中的任意回路，那么C = V1…..V1，假设L(C)为奇数，那么根据〔1〕的结论，V1,V1应该在不同的集合中，矛盾；所以L(C)必为偶数 G的回路都是偶长的 ⇒ G是二部图

首先，按如下方式对G的连通分支进行着色，任选一个结点，着红色，然后将其所有邻结点着为黑色，〔将红色结点标记〕，然后逐一对黑色结点的邻结点着为红色并标记黑结点，如此往复，值到全部结点着色标记完成，或遇到已着色的结点被重新着色为相反的颜色〔此图有奇长度回路〕。下面说明，如果是偶长的，那么就是二部图：

证明：从染色的顺序看，红点到黑点之间的距离为单数，红点到红点的距离为双数，并且相同颜色的点不会相邻。所以可以将图的顶点集合分成两个集合，每个集合的点的颜色一致。根据二部图的定义，这是一个二部图。

如果着色过程中出现已着色点被重新着色成相反颜色，例如：v1是开始的红点，如果现在有点为u1点为黑色，并且开始对他的邻结点进行早色，我们发现w1是u1的邻结点，但已经被着色成黑色，那么，我们就找到得到v1到u1的距离为单数的道路p1，v1到w1距离为单数的道路p2，如果p1 + u1w1 + p1，就形成一个回路，此回路为奇数，与前提矛盾。所以不可能出现这种情况。

〔注:对其他分支重复这种方法，如果遇到孤立结点，则交替着红色和黑色〕

19、设G=(V,E)是点度均为偶数的连通图，证明：对任何 uV, ω(G-u) ≤d(u)/2

证明：因为G的点度都为偶数，因此G-u最多形成d(u)个奇数度点，而奇数度点必须成对出现在连通分支中，所以ω(G-u)的最大值为d(u)/2，所以ω(G-u)≤d(u)/2

23、证明：在具有n(n≥2)个结点的简单无向图G中，至少有两个结点度数相同

证明：在n 个结点的简单无向图中，每个结点的可能度数为0、1、2…n-1，共n种，但是如果有结点度为0，那么就不存在有结点度数为n-1；同理，有结点度数为n-1，那就不存在孤立结点，所以可能的点度只能有n-1种，但有n 个结点，所以必有两个结点度数要相同

30、略

习题十一

.

.

1、设一个树中度为k的结点数是nk(2≤k),求它的叶的数目

解：设T中叶结点数目为t，那么根据握手定理，与数的点边关系可以得到： n = t + n2 + n3 + … + nk (1) Σd(v) = 2m = t + 2n2 + 3n3 + … + knk = 2(n-1) (2)

所以：t + 2n2 + 3n3 + … + knk = 2〔t + n2 + n3 + … + nk〕- 2 t = n3 + 2n4 +…+(k-2)nk + 2

2、证明：树T中最长简单道路的起点和终点必都是T的叶

证明:

a) 首先证明在T中的任意最长道路P中，其起点u和终点v的所有邻结点必然在

P中，否则此道路可以变长，与最长条件矛盾

b) 假设在T中存在最长道路P,其起点u或终点v不是叶结点(假设是u)，那么

d(u)>1，与u至少有两个邻结点u1,u2，他们都将出现在道路中，既P = uu1…u2…v，因为u2是u的邻结点，所以在T中就存在C=uu1..u2u的简单回路，与树的基本性质矛盾，所以u,v必是叶结点

10、设e是连通图G的一条边，证明：e是G的割边当且仅当e含于G的每个生成树中

证明：

a) e是G的割边 ⇒ e含于G的每个生成树中

假设e不包含在G的生成树T’中，那么删除e边后，T’依然包含在G-{e}中，因为T’连通，所以G-{e}连通，与e是割边矛盾，所以e必包含在G的任何生成树中 b) e含于G的每个生成树中 ⇒ e是G的割边

假设e不是割边，那么G-{e}依然连通，所以存在生成数T’，当然T’也是G的生成树，但e不包含在T’中，与题设矛盾，因此e是G的割边

12、略

23、略〔参考课堂ppt〕讲解

习题十二

1、证明：图12-7中的图都是平面图

略〔只需要画处其平面图的形式即可〕

3、设G是阶数不小于11的图，证明：G或G’(代表G的补图)中至少有一个是非平面图

证明：假设G和G’都是平面图，因为m(G) + m(G’) = n(n-1)/2,因此至少有一图的边至少为n(n-1)/4，根据平面图边与点的关系，n(n-1)/4 ≤ 3n – 6，得到n1 -13n + 24 ≤ 0,因此 n ≤ 10, 与题设矛盾；因此必有一图为非平面图

.

.

5、证明：少于30条边的简单平面图至少有一个顶点的度不大于4

证明：少于30条边的简单平面图所有的定点的度都大于等于5，那么根据握手定理和平面图的性质有：

5n ≤2m 〔1〕

m ≤ 3n – 6 〔2〕 ⇒ 5n ≤ 6n – 12 ⇒ n ≥ 12 根据〔1〕式，60 ≤2m，既 m ≥ 30 与题设矛盾，因此至少有一个顶点的度不大于4

7、证明：对K3,3的任意一条边e，K3,3-e是平面图；同样，对K5的任何边e，K5-e也是平面图

证明：因为K3,3的任意一条边ei,ej，K3,3-ei,K3,3-ej都是同构的，而根据题1〔a〕的结论，我们可以平面嵌入它，因此K3,3-e是平面图；同理，K5-e也是平面图

9、如果一平面图于其对偶图同购，则称这个平面图为自对偶图，推导自对偶图必须满足的结点数n与边数m的关系，并找出一些自对偶图

解：如果一个图是平面图，那么满足欧拉公式： n – m + f = 2 〔1〕

其对偶图也是平面图，因此也应满足欧拉公式： n* -m* + f* = 2 (2) 因为对偶关系，因此： n = f*

f = n* 又因为此二图同构，因此

n = n*, m = m*

所以： n = f, 并且 2n – m = 2

据此可以找到一些自对偶图： K1, G(2,2) – 有两种图像， K4

习题十三

1、构造(n,m)欧拉图，使其满足条件：〔1〕m,n奇偶性相同；〔2〕m,n奇偶性相反

答：略

2、设G=〔V，E〕是一个具有2k(k>0)个奇数度结点的连通图。证明：G中必存在k条边不相重的简单道路P1,P2,…,Pk, 使得E=E(P1) E(P2) … E(Pk)

证明：把2k个奇数度结点分成两两一组的k组，然后每组结点新加一条边，所得图为欧拉图，故存在欧拉回路C；然后去掉欧拉回路C中的k条新加入的边，得到k条互无重复边的道路P1,P2,…,Pk, 即为所求

5、在图13-10中求中国邮递员问题的解

.

.

解：

v1 2 v5 v10 6 5 4 3 v6 1 v7 1 v8 4 v3

3 v2 2 v11 3 1 v9 5 2 1 1 v4 如上图标号：

图中有4个奇数度结点v1,v6,v9,v3, 求两两之间最短长度： Pv1v6=3 (v1v6), Pv1v9=7 (v1v2v3v4v9), Pv1v3=4 (v1v2v3), Pv6v9=7 (v6v7v8v9), Pv3v6=6 (v3v8v7v6), Pv3v9=3 (v3v4v9), Pv1v6和Pv3v9满足最小性要求，

复制v1v6和v3v4v9的边，图中欧拉回路即为所求解

6、设G是有两个奇数度点的连通图，设计一个构造G的欧拉道路的算法

解：此算法只要在书中欧拉回路的算法中，添加起点为奇数结点即可，详细描述略

9、证明：凡有割点的图都不是哈密顿图

证明：假设e为图G的割点，根据割点的定义，ω(G-e) > 1，因此不满足哈图的必要条件；所以不是哈图

13、假定在n(≥2)个人的团体中，任何2人合起来认识其余的n-2个人，证明：

〔1〕这n个人可以排成一排，使得站在中间的每个人的两旁都是自己认识的人，站在两端的人旁边各有1个认识的人

〔2〕当n≥4时，这n个人可以围成一个圆圈，使得每个人两旁都是自己所认识的人

证明：如果团体中的个人看成是结点，而人于人的关系看成是边，那么就构成一个认识与否的图，对于问题〔1〕，就转化为此图中存在哈道路问题；问题〔2〕，就转化为图中存在哈圈的问题，现说明如下： 在此题中，任何2人合起来认识其余的n-2个人蕴含任何人最多只有一人不认识，因为如果

.

.

a，不认识b和c,那么b和c就不能认识完剩下的全部人，因此在图既为d(u)≥ n-2

那么，任意两个结点u,v，d(u) + d(v) ≥ n-2 + n -2，因为n≥2，所以d(u) + d(v) ≥ n-1，根据书中定理，此图存在哈道路

如果n≥4，那么d(u) + d(v) ≥ n-2 + n -2 ≥ n，根据书中定理，此图存在哈圈

习题十四

4、设S={a,b,c},运算“.〞由表14-2定义；

判断代数系统是否为广群，半群，含幺半群，群 答：

由运算表可知：〞 ·〞封闭，所以是广群； 由表可知：

x,y S, x·y=y, 所以 (x·y)·z=z,x·(y·z)=x·z=z, 所以结合律成立，所以是半群； 由表可知：

a,b,c皆为左幺元，无右幺元，所以是半群

5、表14-3中所列运算定义在实数集合R上，请在下表的各栏上填上该运算是否具有指定性质 封闭性 结合性 交换性 存在幺元 存在零元 每元有逆元 + √ √ √ √ × √ - √ × × × × × × √ √ √ √ √ × max √ √ √ × × × min √ √ √ × × × |x-y| √ × √ × × × 答：

+：是封闭的，有结合性，可交换，0为幺员，无零元，每个数的相反数为其逆元a,-a -: 是封闭的，没有结合性 〔3-2〕-1 ≠ 3 - 〔2-1〕，不可交换 3-2 ≠ 2-3，没有幺〔不可交换〕，没有零元，没有逆元〔无幺〕

×：是封闭的，有结合性，可交换，1为幺元，0为零元，0没有逆元 Max:是封闭的，max(max(a,b),c) = max(a,max(b,c)) 有结合性，max(a,b)=max(b,a) 具有交换性，无幺元，无零元，无逆元 Min：〔同上〕

|x-y|:是封闭的，||5-3|-2| ≠ |5-|3-2|| 没有结合性，|x-y|=|y-x| 可交换，没有幺 |-1-0| ≠ -1，没有零，没有逆

习题十五

3、在实数集合R上定义二元运算“*〞如下：∀a,bR, a*b = a+ b+ab；证明：〈R,*〉是含幺半群

.

.

证明：

因为定义运算中只包含初等运算+，×，所以是封闭的；

因为对任意实数a,b,c, 〔a*b〕*c = (a+b+ab) + c + (a+b+ab)c = a*(b*c) 具有结合性； 0是幺元，a*0 = a + b + 0.a = a = 0*a 所以是含幺半群

〔注：-1没有逆元，因此不是群〕

4、设半群中任何两个不同元素关于运算“·〞不可交换；证明：对任何aA,a·a=a

证明：〔注：应该是非平凡半群，即元素个数≥2〕假设存在aA,a·a≠a, 设a·a=b,那么(a·a) ·a = b·a = a· (a·a) = a·b (运用半群的结合性)，所以a，b，可交换；与题设矛盾，假设不成立；因此原命题结论成立

6、证明：群中只有幺元是幂等元

证明：假设a是幂等元，那么对任意群中元素b，ba=baa ,根据消去率，b = ba；同理 ab = aab ,所以 b = ab，根据幺元的定义，a = e；既群中幂等元是幺元

9、在整数集Z上用加法运算+和-定义新运算“〞如下：a,b Z, a  b=a+b-2. 证明: 是群

证明：封闭性、结合性证明略。

设幺元为e, e  a=e+a-2=a, e=2.

对a的逆b，有a  b=2，即a+b-2=2, 可见b=4-a 综上， 是群 11、设和都是的子群，，令S T={x|xS xT}, ST={s*t|sStT}.(*可交换)；证明：< S T, * >和也都是的子群

证明：

-1-1

已知和都是的子群，任取a,bS T, 所以a * bS, a * bT, 即

-1

a * bS T, 所以< S T, * >是的子群

对于，已知ST=TS，任取s1 * t1, s2 * t2ST,

-1-1-1-1

(s1 * t1) * (s2 * t2)=(s1 * t1) * (t2* s2) = s1 * t3* s2

-1

= s1 * s2* t3 = s3 * t3ST

所以是的子群

16、证明：每个阶数大于1的群必含有阶数大于1的交换子群

证明：因为群G的阶数大于大于1，任取aG ∧ a≠e，构成 S = (a), 那么S与为满足要求的交换子群；因为

（1） (a)是循环群，所以是交换群，并且是G的子群 （2） e , a  (a) ∧ a ≠ e, 所以 〔a〕的阶数大于1

.

.

17、证明：循环群的子群必是循环群

证明：

k

设G的生成元为a, H为G的子群，并且H中具有最小正幂的元是a, （1） 如果k = 1,那么a就是子群的生成元，所以是循环子群 （2） 如果k ≠ 1, 那么

kk

G=(a), HG, H={e, a, ak2, ak3,…}，设a是H中具有最小正指数的元，

mmktr

则aH，令m=tk+r (0rmktrk

由k的选择知，r=0, 即a=(a) a, H由a生成；因为，假设r ≠ 0，又因为0rk-tmr

么 (a) a = a H，与k为最小正指数矛盾

18、证明：群中的每个元素和它的逆元有相同的周期

n–nn

证明：设任意元素a的周期为n，那么〔-a〕 = a = -(a) = e ,所以n是-a的周期的

nmr

倍数，假设m是 -a的周期，且 m 〈 n, 那么a (-a) = a = e ,030、设是群，a是G中一个固定元素，定义映射f:G → G使得对任何x G，f(x)=a·x·a-1. 求证：f是G的自同构映射

证明：

容易证明f是G的同态映射， f(x·y) =a·x·y·a-1 =a·x·a-1·a·y·a-1 =f(x) · f(y) 再证明f是双射，

-1-1

证单射：f(x)=f(y), a·x·a=a·y·ax=y

-1-1-1

证满射：令a·x·a= y, x=a·y·a，即任意y，可以找到 x = a·y·a，使得f(x) = y

习题十六

1、设S是由有限个实数组成的非空集合；证明：不是环，其中+，×是实数的加法和乘法运算

证明：因为在有限实数集上，如果 S ≠ {0}，那么加法和乘法都不封闭；但 S = {0}时，是环

3、设A依次为下列数集合，试确定是否成环、整环或域

(1)A={x|xZ且x  0}

答：在非负整数集合内，无加法逆元存在，不是环 (2)A={a+b√3|a,bQ}

答： 是加群〔闭，结，幺，逆〕，〈A，〉是含幺半群〔闭，结，1为幺，0没有逆元〕，同时，〈A-{0}，〉是群，所以是域 (3)A={x|(y)[yZ且x=2y]}

.

.

答：A是由偶数集合，是环，但〈A,>半群无幺元，所以不是整环，不是域 (4)A={a/b|a,b为正整数，且(a,b)=1}

答：A为正有理数，无加法逆元存在，不构成环

习题十七

2、设n为正整数, Dn为n的所有正因子构成的集合, 画出、 、 对应的Hasse图，并证明它们都是格

证明：〔图略〕 菱形 链

≌ 2{a,b,c}

他们都满足格的定义，有最大元，最小元，任意两个元素都可求最大下界最小上界

5、证明：在任何格中下述结论成立：

〔1〕如果a∧b∧c=a∨b∨c,则a=b=c

证明：因为a∧b∧c≤a≤a∨b∨c,而a∧b∧c=a∨b∨c，所以a∧b∧c=a∨b∨c=a 同理，a∧b∧c=a∨b∨c=a=b=c

〔2〕a∨[(a∨b)∧(a∨c)] = (a∨b)∧(a∨c)

证明：因为a ≤a∨b, a ≤a∨c, 所以 a ≤(a∨b)∧(a∨c),所以 (a∨b)∧(a∨c)

8、设是格,〞〞 是对应的偏序，a,b,c,d是L中任意元素，证明：

(1) (ab) (cd) (ac) (bd) 证明：

因为ab  a, cdc,所以 (ab) (cd) (ac) 同理(ab) (cd) (bd)

所以 (ab) (cd) (ac) (bd)

(2) (ab)(bc)(ca)(ab)(bc)(ca) 证明：

因为a ab, a ca, 所以 a (ab)(ca) 同理 b(bc)(ab)

所以 ab (ab)(bc)(ca) 同理 bc (ab)(bc)(ca), ca (ab)(bc)(ca),

所以(ab)(bc)(ca)(ab)(bc)(ca)

10、确定下列各Hasse图对应的格中哪些是分配格，哪些是有补格

答: (图略)

图a, 其子格不包含5点禁格，所以是分配格，但有元素没有补元，不是有补格

图b，其子格不包含5点禁格，所以是分配格，除最大元与最小元外，其它元素没有补元，

.

.

不是有补格

图c，其子格包含5点禁格，所以不是分配格，其中有元素没有补元，所以不是有补格

15、作一个十元格的Hasse图，使其中某些元素有多个补元，某些元有一个补元，某些元没有补元

A F E

D C

B

答：在上图中，A,B互为补元，补元唯一；E，D都是C的补元；F没有补元

17、设是有补分配格，x,y,zL；证明：

〔1〕如果x≤y,y∧z=0,则z≤-x

证明：因为x≤y，所以x∧y=x，因此 -〔x∧y〕=-x, 与-x∨-y = -x，-y≤-x 因为y∧z=0,所以 -y∨〔y∧z〕= (-y∨y)∧(-y∨z) = -y∨z = -y∨0 = -y 所以 z ≤ -y ≤ -x ,z≤-x

补充证明:

[1] 推论：当是有限群时，对非空子集S，如对a,bS， 有a*bS，则是的子群。〔即只需判断在S中运算是否封闭即可〕

n+1

证明: 设G中有n个元素；因为S是封闭的，所以对任意S中元素a，那么a,a*a,a*a*a,…a，

ijj-Ij-i-1

中一定有相同的元素，设a=a(j>i，取最小值),那么a = e，所以e在S中，且a 与 a就为逆元，所以是群，结论成立

[2] 定理15.5 设是一个群，aG，构造映射a：G→G，使对 xG， a〔x〕=a*x，令H={a| aG}，则对于函数的复合运算“〞， 是群。

证明：〔1〕证明a：G→G是G上的双射函数

.

.

a) 是单射：因为假设a〔x1〕= a〔x2〕，那么a*x1 = a*x2 ,根据群中具有消去律，所

以x1 = x2

-1-1

b) 是满射，因为G中任意元素，y，那么a*y就是其原像，与a〔a*y〕=y,所以是满射 所以H中的元素，是G上的双射函数；下面所明是群 a) 封闭性：对H中任两个元素a,,那么a,依然是G上的双射，但它是否是H中的元素呢？

因为a〔x〕= a〔b*x〕= a*(b*x) = (a*b)*x = (a*b)(x),所以是H中元素，所以是封闭的

b) 结合性：因为函数的复合运算具有结合性，所以结论成立

c) 因为e〔x〕= e*x = x，所以G上的恒等函数在H中，又因为恒等函数和其他任何G上

的函数复合都等于原来的函数，所以e就是系统中的幺元

-1-1-1-1

d) 对H中任意函数a，那么a,就是其逆函数，因为aa(x)=(a*a*x)=(a*a

-1

*x)=aa 〔x〕= x = e〔x〕；所以H中每元有逆元 综上所述，是群

==========特殊符号===========

集合：∩∪⊕~×≠ - ## ∉⊆⊂⊇⊃∩∪⊕≠ 逻辑：~ ∧∨▽→

↔⇒∀∃∃!

∵∴

代数：≈≡÷×≤≥<>∞√ ·

nn

关系：。º IA IA R 图论：

.