您的当前位置:首页离散数学习题答案-2015

离散数学习题答案-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) -- x与y相交

翻译如下:(a)(b)〔A(a)∧A(b)→ (F(a,b)~G〔a,b)〕) 〔3〕除非所有的会员都参加,这个活动才有意义 解: A(x) -- x是会员

.

.

B(x) -- x有意义 a -- 这个活动 F(x,y) -- x参加y

翻译如下:B〔a〕→(x)〔A(x)→F(x,a)〕 或 ~(x)〔A(x)→F(x,a)〕→~B〔a〕 〔4〕任何正整数不是合数就是质数 解: A(x) -- x是正整数 B(x) -- x是合数 C(x) -- x是质数

翻译如下:(x)〔A(x)→B(x)C(x)〕

(6) 凡是存钱的人都想有利息,如果没有利息,人们就不会存钱 解: A(x) -- x是存钱的人

F(x,y) -- 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 图论:

.

因篇幅问题不能全部显示,请点此查看更多更全内容