您好、欢迎来到现金彩票网!
当前位置:刘伯温四肖中特料 > 推理结点 >

离散数学习题答-2015doc

发布时间:2019-06-12 05:48 来源:未知 编辑:admin

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  离散数学习题答案 习题一 1、利用逻辑联结词把下列命题翻译成符号逻辑形式 他既是本片的编剧,又是导演 --- P ∧ Q 银行利率一降低,股价随之上扬 --- P → Q 尽管银行利率降低,股价却没有上扬 --- P ∧ Q 占据空间的、有质量而且不断变化的对象称为物质 --- M ??(S∧P∧T) 他今天不是乘火车去北京,就是随旅行团去了九寨沟 --- P ▽ Q 小张身体单薄,但是极少生病,并且头脑好使 --- P ∧ Q ∧ R 不识庐山真面目,只缘身在此山中 --- P → Q (解释:因为身在此山中,所以不识庐山真面目) 两个三角形相似,当且仅当他们的对应角相等或者对应边成比例 --- S ??(E∨T) 如果一个整数能被6整除,那么它就能被2和3整除。如果一个整数能被3整除,那么它的各位数字之和也能被3整除 解:设 P – 一个整数能被6整除 Q – 一个整数能被2整除 R – 一个整数能被3整除 S – 一个整数各位数字之和能被3整除 翻译为:(P → (Q ∧ R))∧ (R → S) 2、判别下面各语句是否命题,如果是命题,说出它的线)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 Q ~P ∧ Q P ∨(~P ∧ Q) (P ∨(~P ∧ Q))→ Q 可满足式 0 0 0 0 1 0 1 1 1 1 1 0 0 1 0 1 1 0 1 1 (2)~(4)表略:(2)可满足式、(3)永线、利用真值表方法验证下列各式为永线、证明下列各等价式 (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、分别利用真值表法和等价变换法求下列公式的主合取范式及主析取范式: (3) P→(R∧(Q→P)) 解:真值表法 P Q R Q→P R∧(Q→P) P→(R∧(Q→P)) 0 0 0 1 0 1 0 0 1 1 1 1 0 1 0 0 0 1 0 1 1 0 0 1 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以: 主合取范式为 = (~P∨Q∨R) ∧(~P∨~Q∨R) = M4∧M6 主析取范式为 = (~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) (P→(Q∧R)) ∧(~P→(~Q∧~R)) 0 0 0 0 1 1 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 0 1 0 0 1 0 0 0 1 0 1 0 1 0 1 0 0 0 1 0 1 1 0 0 0 0 1 0 1 1 1 1 0 1 1 1 所以: 主合取范式为 = (P∨Q∨~R) ∧( P∨~Q∨R) ∧( P∨~Q∨~R) ∧(~P∨Q∨R) ∧(~ P∨Q∨~R) ∧(~ P∨~Q∨R) = M1∧M2∧M3∧M4∧M5∧M6 主析取范式为 = (~P∧~Q∧~R)∨(P∧Q∧R) = m0∨m7 等价变换法(略) 14、从A,B,C,D 4个人中派2人出差,要求满足下列条件:如果A去,则必须在C或D中选一人同去;B和C不能同时去;C和D不能同时去。用构造范式的方法决定选派方案。 解:由题设 A:A去,B:B去,C:C去,D:D去则满足条件的选派应满足如下范式: (A→(C?D))∧~(B∧C)∧~(C∧D) 构造和以上范式等价的主析取范式 (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 (任何公式可蕴含永线、一个有钱人生前留下了一笔珍宝,藏在一个隐秘处。在他留下的遗嘱中指出寻找珍宝的线索如下: 如果藏宝的房子靠近池塘,那么珍宝不会藏在东厢房。 如果房子的前院栽有大柏树,那么珍宝就藏在东厢房。 藏宝房子靠近池塘。 要么前院栽有大柏树,要么珍宝埋在花园正中地下。 如果后院栽有香樟树,珍宝藏在附近。 请利用蕴含关系找出藏宝处 解:根据给定的条件有下述命题: P:珍宝藏在东厢房 Q:藏宝的房子靠近池塘 R:房子的前院栽有大柏树 S:珍宝藏在花园正中地下 T:后院栽有香樟树 M:珍宝藏在附近 根据题意,得出: (Q→~P)∧(R→P)∧Q∧(R∨S)∧(T→M) T? (Q→~P)∧(R→P)∧Q∧(R∨S)∧(T→M) T~P∧(R→P)∧(R∨S)∧(T→M) T~R∧(R∨S)∧(T→M) TS∧(T→M) TS 即珍宝藏在花园正中地下 20、演绎证明下面各蕴含式: (4)(R→Q) ∧(R→S),(Q→E) ∧(S→B), ~(E∧B),(P→R) T ~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) T 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) T 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)) 凡是存钱的人都想有利息,如果没有利息,人们就不会存钱 解: 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)) 这是一个可满足式,但不是永线时,谓词公式不成立,但其它情况均成立,如果论域中不包含-1,为线)诚实的人都讲实话。小林不是诚实的,因而小林不讲实话 解: H(x) -- x诚实 T(x) -- x讲真话 a -- 小林 翻译如下: ((x)(H(x) →T(x)) ∧~H(a)) →~T(a) 这是一个可满足式,因为否定条件命题前件,不一定后件命题一定为假。及小林虽然不诚实,但也可能讲实线、对于题目给定的解释,求下列各公式相应的线) A = (x)[ P(x) ∨Q(x)] ∧R(a),解释 D ={1,2,3},P(x): x2+x=2; Q(x): x是素数;R(x): x3; 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,所以整个公式解释为线) 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, 线) →P(2,3)) ∧(P(3,3) →P(2,2)) = (0→1)∧(0→1)∧(1→0)∧(1→0)= 0, 线、设论域为整数集合Z,试判定下面各公式是否是永真式,矛盾式或可满足式 (1)(x)[x-10∧x2≥0] 答:为假命题 (2)$(x)[2x8∧x2-6x+5≤0] 答:为线)(x) $(y)[x+y=1024] 答:为真命题,对任意整数x,y取值为1024-x及可 (4)$(y) (x)[xy10∨x+y≥2] 答:为线、证明下列各式成立: (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、把下列公式化为等价的前束范式,再求出对应的SKolem范式 (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))] 其SKolem范式为:(x) (z) [ P(x,0) ∨(P(g(x),f(x)) ∧ Q(x,z))] 13、证明下列各式成立 (1)$(x) $(y)[P(x) ∧Q(y)] T$(x)P(x) 证明:左式 ? $(x) P(x) ∧$(y)Q(y) T $(x)P(x) (2)~($(x)P(x) ∧Q(a)) T$(x)P(x) →~Q(a) 证明:左式 ? ~$(x)P(x) ∨~Q(a) ? $(x)P(x) →~Q(a) 15、下面给出了对(x) [P(x) ∨Q(x)] T(x) P(x) ∨(x)Q(x)]的证明: (原证明过程略) 试判断这个证明是否正确。你能给出一个证明吗? 答:这个证明不正确,因为:如果 P T Q 则~QT ~P 而 ~ P T ~ 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成立 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}}的幂集 解:2A = {?, {?} , {a} , {{b}} , {?,a} , {?,{b}} , {a, {b}} , {? 17、设A,B是任意两集合,证明 (1)2A è 2B í 2 A è 证明:X ? 2A è 2B ? X ? 2A ú X ? 2 ? X í A ú X í B = X í A è B ? X ? 2 A è 等号成立的条件: A í B或B í A (因为若A和B没有子集关系, 必有a ?A– B和 b ?B– A,使{a, b} ? 2 A è B ,但{a, b} ? 2A è 2 (2)2A? 2B = 2 A 证明:X ? 2A? 2B ? X ? 2A ù X ? 2 ? X í A ù X í B ? X í A ? B ? X ? 2 A ? 附加题: 证明等式(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 习题四 1、设A={1,2,3,4},B={0,1,4,9,12}.分别把下面定义的从集合A到集合B的二元关系R用序偶的集合表示出来 (1)xRy ?xy 解: 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 ? xoy(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 自反性 反自反性 对称性 反对称性 传递性 xy √ × × × √ x≡y(mod m) √ × √ × √ xy0 × × √ × √ xy≧0 √ × √ × × x=y或x-y=1 √ × √ × × x2 y2 × √ × √ √ 因为xx成立,所以自反性成立;所以反自反性不成立;因为x≠0时,x0成立,但0x不成立,所以对称性不成立,因为 1-1,和-11成立,所以反对称性不成立;但xy,yz成立,就一定有xz成立,所以传递性成立 因为模m相等是整数集合上的等价关系,所以具有自反、对称、传递性 因为00 = 0,所以自反性不成立;因为x ≠ 0时必有 xx0,所以反自反性不成立;因为xy 0 必有yx0,所以对称性成立;因此反对称性不成立;因为xy0,yz0,能得到x,y,z同号且不为0,所以,xz0,所以传递性成立 因为xx≧0,所以自反性成立;因此,反自反性不成立;因为xy≧0,所以yx≧0,因此对称性成立;因此,反对称性不成立;因为-1*0 ≧0,0*1≧0,但-1*1 0,所以传递性不成立 因为 x=x,所以自反性成立;因此反自反性不成立;因为x-y=1,所以 y-x =1,因此对称性成立;所以反对称性不成立;因为1-2=1,2-3=1,但1-3=2,所以传递性不成立 因为 xx = xx,所以自反性不成立;反自反性成立;因为x2 y2 成立,那么y2 x2就不成立,所以对称性不成立,反对称性成立;传递性成立 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 自反性 √ √ × √ × √ 反自反性 √ √ √ × × √ 对称性 √ √ √ × √ √ 反对称性 √ × √ × × √ 传递性 √ × × × × √ 自反性的保持情况说明: 因为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不具有自反性 因为(a,a)∈R,所以(a,a)∈R-1,因此R-1具有自反性 反自反性的保持情况说明: 因为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一定是自反的,一定不是反自反的 因为(a,a)不属于R,所以(a,a)也不属于R-1,因此R-1一定是反自反的 对称性的保持情况说明: 因为R,S是对称的,所以R= R-1,S= S-1 ,-R = (-R)-1= -R-1, -S = (-S)-1= -S-1 因为(R∩S)-1= R-1 ∩ S-1= R∩S, 所以R∩S具有对称性 因为(R∪S)-1= R-1 ∪ S-1= R∪S, 所以R∪S具有对称性 因为(R-S)-1= (R∩-S)-1=R-1 ∩ (-S)-1= R-1 ∩ -S-1 = R∩-S,所以R-S具有对称性 因为(R○S)-1 = S-1 ○ R-1 = S○R ,但S○R通常情况下与R○S不相同,所以对称性不一定保持,例如:R = {(a,b),(b,a)}, S = {(b,c),(c,b)},则R○S = {(a,c)},并不对称 因为(-R)-1 = -R-1 = -R,所以R的补是对称的 因为 R逆的逆就是R,既等于R的逆,所以R的逆是对称的 反对称性的保持情况说明: 因为R,S是反对称的,所以R∩ R-1í IA S∩ S-1í IA 因为(R∩S)∩(R∩S)-1 = (R∩R-1)∩(S∩S-1)í 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)},不是反对称的,所以反对称性在补集运算上不保持 因为R∩ R-1í IA,有因为 R = (R-1)-1,所以R-1是反对称的 传递性的保持情况说明: 因为R,S是传递的,所以R2íR, S2íS 因为(R∩S)2 = (R∩S)○(R∩S)í R2∩S2∩(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上不一定保持 因为R2íR,所以 (R2)-1íR-1 ,即(R-1)2íR-1,所以传递性在逆运算下保持 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 = Φ (3)R是对称的 ? R = R-1 证明: R是对称的 = R = R-1 因为对R中的任意元素(a,b),因为R是对称的,所以(b,a)∈R,那么(a,b)∈R-1,所以Rí R-1 因为对R-1中的任意元素(a,b),那么(b,a)∈R,因为R是对称的,那么(a,b)∈R,所以R-1í R 所以 R = R-1 R = R-1 = R是对称的 对R中的任意元素(a,b),因为R = R-1 ,所以(a,b)也属于R-1,所以(b,a)∈R,因此R是对称的 综上所述,R是对称的 ? R = R-1 (4)R是反对称的 ? R∩R-1íIA 证明: R是反对称的 = R∩R-1íIA 因为对任意(a,b) ∈R∩R-1 ,那么其就同时属于R和R-1 ,那么(b,a)也属于R,根据反对称的定义,a = b,所以(a,b)∈IA ,所以R∩R-1íIA R∩R-1íIA = R是反对称的 假设R不是反对称的,那么必定存在 a ≠b∧(a,b) ∈R ∧ (b,a) ∈R,那么(a,b)∈R∩R-1 ,但(a,b)不属于IA,矛盾;因此R必是反对称的 综上所述,R是反对称的 ? R∩R-1íIA R是传递的 ? R2íR 证明: R是传递的 = R2íR 因为对任意(a,b)∈R2 ,必存在c,使得(a,c),(c,b)属于R,因为R是传递的,所以(a,b)属于R,因此R2íR R2íR = R是传递的 因为对任意的R中的元素(a,b),(b,c),那么(a,c)必定属于R2,也就属于R,所以R是传递的 综上所述,R是传递的 ? R2íR 11、设A={1,2,3,4},定义A上的关系 R = {(a,b)a=b+2},S = {(x,y)y=x+1∨x=2y} 求:R。S,R。S-1。R,R2,(S-1)2 解:根据题意,R={(3,1),(4,2)},S={(4,2),(1,2),(2,3),(3,4)} 所以:R。S = {(3,2),(4,3)} S-1 = {(2,4),(2,1),(3,2),(4,3)} 所以:R。S-1 = {(4,4),(4,1)} R。S-1。R = {(4,2)} R2 = ? (S-1)2 = {(2,3),(3,4),(3,1),(4,2)} 12、设A={a,b,c,d,e,f,g,h},A上的二元关系R对应的关系图4-5所示,求使Rm=Rn的最小整数m和n(m n) 答:R = R16;简要说明如下:本关系图分为两个部分,R = R1 ∪ R2,因为 R1。R2 = R2。R1 = ?, 所以R2 = R12 ∪ R22 ,同理Rn = R1n ∪ R2n ,又因为 I1 = R13,I2=R25 ;3,5的最小公倍数为15,所以I = R15 ,所以R = I o R15 = R o R15 = R16 13、设R是集合A上的二元关系,证明: (1)IAn = IA 证明:因为单位关系的关系矩阵为单位矩阵,而复合运算就是矩阵的乘法,根据单位矩阵的性质,IAn = IA (2)IA o R=R oIA =R 证明:同上,因为单位矩阵左乘、右乘一个矩阵,结果不变;所以IA o R=R oIA =R (3)(R∪IA)n=IA∪R∪R2∪R3…∪Rn 证明:根据书中并集关系复合的定理(4.2),展开,并利用上述1,2的结论,及可得证(严格可用归纳法) 15、写出第12题中关系图对应的关系矩阵,并利用warshall算法求这个关系的传递闭包 解: 习题五 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的正因子构成的集合,“”表示整除。画出偏序集A,对应的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} 18 18 2 6 3 9 54 1 27 9、设A={a,b,c},画出偏序集合对应的Hasse图。试比较本题与上题Hasse图的异同 解: { {a,b,c} {a,b} {a,c} {b,c} {a} {b} {c} ? 两图的相同点 : 都有最大(小)元 不同点:最大线、设R是集合A上的一个等价关系。现在在等价类之间定义一个新关系S使得R的任何等价类[a]和[b]满足[a]S[b] ?aRb,判别S是一个什么关系 解:根据题目信息,猜测是等价关系,说明如下: 因为对任意的a?A,aRa成立(R是A上的等价关系,是自反的),所以[a] S [a],S是自反的 假设[a] S [b]成立,那么aRb;因为R是对称的,所以bRa,因此[b] S [a]成立,所以S是对称的 假设[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,02n1-n25} 答:此关系不满足全函数的定义,因为(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都不是他们的因数,因此他们就没有像,所以不是全函数 (5){(x,y)x,y ? Z,y=x2} 答:此关系是全函数,因为任意一个整数,都能求到唯一的平方数。所以按定义是全函数 7、确定下列映射是否单射、满射或双射: f1: N→R,f1(n)=lnn 答:如果0不属于N,那么这是一个单射函数,因为任意一个自然数都可以求其自然对数,同时ln是单调函数,所以是单射函数。但是并非任意一个实数其原像都是自然数,所以不是满射 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) f3:N×N→N,f3(n1,n2)=(n1+1)n2 答:这既不是单射,也不是满射(与0是否属于N无关,以下说明以0不属于N而言);因为任意两个自然数,都能求到此函数值,所以是全函数。因为f(1,2)=f(3,1)=4,所以不是单射函数;同时1没有原像,所以不是满射函数 f4:R→R,f4(x)=x2+2x-15 答:一元二次函数,既不是单射,也不是满射;其几何图像为抛物线 答:这是一个单射函数,但不是满射;因为3次曲线是单调函数,所以在定义域子集范围也是单调的,所以是单射函数。但任意一个整数像的原像却不一定是整数。所以不是满射 A是集合,f6:2A×2A→2A×2A,f6(x,y)=(x 答:假设A = ?,那么这是一个双射函数(请同学思考) 假设A不是空集,那么此函数既不是单射,也不是满射;因为:对f(x,y)=f(y,x),所以不是单射;另外对于(?,A),没有原像;所以不是满射 f7:R×R→R,f7(x,y)=x+y,f8:R×R→R,f8(x,y)=xy 答:此两个函数,都不是单射,但都是满射函数 8、设X是有限集合,f:X→X,证明: 如果f是单射,f必是双射 证明:假设f不是满射,那么就必定有元素没有原像,由于X是有限集合,根据鸽茏原理:原像元素个数(鸽子)就比像元素个数多(鸽笼),所以必定有多个原像会映射到相同的像上,所以不是单射。矛盾。所以f必定是满射,即是双射 如果f是满射,f必是双射 证明:假设f不是单射,那么必定存在多个元素映射到相同的像上。由于X集合是有限的,那么因变量的个数就少于自变量个数,因此f就不是满射。与题设矛盾。因此f必是单射,既是双射 9、设f是有限集X上的一个函数,满足?x?X,f2(x)=x;证明:f是双射 证明:因为f2(x) = f。f(x) = x, 既是f2 = Ix;所以f是自己的逆函数,根据逆函数的性质,f必是双射 18、证明下列集合A和B等势 (1)A = (0,1), B = (-2,2) 证明:如果能找到从A到B的双射函数,就能说明A和B等势,存在A到B上的这样的函数;例如:f(x) = 4x - 2 或 f(x) = 5x-3 (2)A = (-∞,+ ∞),B = (0,+ ∞) 证明:如果能找到从A到B的双射函数,就能说明A和B等势,存在A到B上的这样的函数;例如:f(x) = ex (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 代表简单无向图的平均点度值,所以平均值大于等于最小值,小于等于最大值,结论成立 6、设G是(n,m)简单二部图,证明:m≤n2/4 证明:设G的两个顶点集合中顶点个数分别为n1,n2,并有 n = n1 + n2 (1式);同时,在简单二部图中,当其为完全二部图是,其边数最大,及max(m) = n1 × n2 (2式);联立(1)(2)式,通过高等数学的知识,当n1=n2=1/2n时,max(m)取得最大值 n2/4 ,所以一般(n,m)简单二部图,其边数小于等于此最大值既 m≤n2/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的回路都是偶长回路(非平凡图, n1) 证明:(1)先证明在二部图中,所有奇长道路的两个端点必定分别在两个顶点集合中 使用归纳方法: A)当道路长度L(P)=1时,就是图G的边和其两个端点,根据二部图的定义,两个端点分别在两个顶点集合中 B)假设道路长度L(P)=2n+1 (n0)时结论成立,及P=V1V2….V2n+2,其中V1,V2n+2分别属于两个顶点集合 C) 当L(P)=2(n+1)+1 (n0)时,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的叶 证明: 首先证明在T中的任意最长道路P中,其起点u和终点v的所有邻结点必然在P中,否则此道路可以变长,与最长条件矛盾 假设在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的每个生成树中 证明: e是G的割边 ? e含于G的每个生成树中 假设e不包含在G的生成树T’中,那么删除e边后,T’依然包含在G-{e}中,因为T’连通,所以G-{e}连通,与e是割边矛盾,所以e必包含在G的任何生成树中 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(k0)个奇数度结点的连通图。证明:G中必存在k条边不相重的简单道路P1,P2,…,Pk, 使得E=E(P1) èE(P2) è… èE(Pk) 证明:把2k个奇数度结点分成两两一组的k组,然后每组结点新加一条边,所得图为欧拉图,故存在欧拉回路C;然后去掉欧拉回路C中的k条新加入的边,得到k条互无重复边的道路P1,P2,…,Pk, 即为所求 5、在图13-10中求中国邮递员问题的解 解: v9 v9 v6 v3 v1 v2 v4 v5 v7 v8 v10 2 2 1 1 1 1 3 3 v11 3 4 4 1 5 5 6 2 如上图标号: 图中有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定义; 判断代数系统S,.是否为广群,半群,含幺半群,群 答: 由运算表可知:” ? ”封闭,所以是广群; 由表可知: x,y ?S, x?y=y, 所以 (x?y)?z=z,x?(y?z)=x?z=z, 所以结合律成立,所以是半群; 由表可知: a,b,c皆为左幺元,无右幺元,所以S, ? 是半群 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=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上用加法运算+和-定义新运算“D”如下:a,b ?Z, a D b=a+b-2. 证明: Z, D 是群 证明:封闭性、结合性证明略。 设幺元为e, e D a=e+a-2=a, Te=2. 对a的逆b,有a D b=2,即a+b-2=2, 可见b=4-a 综上, Z, D 是群 11、设S, * 和T, * 都是G, * 的子群,,令S ?T={xx?S ùx?T}, ST={s*ts?Sùt?T}.(*可交换);证明: S ?T, * 和ST, * 也都是G, * 的子群 证明: 已知S, * 和T, * 都是G, * 的子群,任取a,b?S ?T, 所以a * b-1?S, a * b-1?T, 即a * b-1? S ?T, 所以 S ?T, * 是G, * 的子群 对于ST, * ,已知ST=TS,任取s1 * t1, s2 * t2?ST, (s1 * t1) * (s2 * t2)-1=(s1 * t1) * (t2-1* s2-1) = s1 * t3 * s2-1 = s1 * s2-1 * t3 = s3 * t3 ? ST 所以ST, * 是G, * 的子群 16、证明:每个阶数大于1的群必含有阶数大于1的交换子群 证明:因为群G的阶数大于大于1,任取a?G ∧ a≠e,构成 S = (a), 那么S及为满足要求的交换子群;因为 (a)是循环群,所以是交换群,并且是G的子群 e , a ? (a) ∧ a ≠ e, 所以 (a)的阶数大于1 17、证明:循环群的子群必是循环群 证明: 设G的生成元为a, H为G的子群,并且H中具有最小正幂的元是ak, 如果k = 1,那么a就是子群的生成元,所以是循环子群 如果k ≠ 1, 那么 G=(a), HíG, H={e, ak, ak2, ak3,…},设ak是H中具有最小正指数的元, 则 am?H,令m=tk+r (0£rk), 则am=(ak)t ar, 由k的选择知,r=0, 即am=(ak)t ar, H由ak生成;因为,假设r ≠ 0,又因为0£rk,那么 (ak) -t am = ar ? H,与k为最小正指数矛盾 18、证明:群中的每个元素和它的逆元有相同的周期 证明:设任意元素a的周期为n,那么(-a)n = a –n = -(an) = e ,所以n是-a的周期的倍数,假设m是 -a的周期,且 m 〈 n, 那么an (-a)m = ar = e ,0rn,与n 是a的周期矛盾,所以m = n,所以逆元的和原元素有相同的周期 30、设G, ·是群,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是双射, 证单射:f(x)=f(y), a·x·a-1 = a·y·a-1 Tx=y 证满射:令a·x·a-1 = y, x=a-1·y·a,即任意y,可以找到 x = a-1·y·a,使得f(x) = y 习题十六 1、设S是由有限个实数组成的非空集合;证明:S,+, ×不是环,其中+,×是实数的加法和乘法运算 证明:因为在有限实数集上,如果 S ≠ {0},那么加法和乘法都不封闭;但 S = {0}时,是环 3、设A依次为下列数集合,试确定A, +, ′是否成环、整环或域 (1)A={xx?Z且x 3 0} 答:在非负整数集合内,无加法逆元存在,不是环 (2)A={a+b√3a,b?Q} 答: A,+是加群(闭,结,幺,逆),〈A,′〉是含幺半群(闭,结,1为幺,0没有逆元),同时,〈A-{0},′〉是群,所以是域 (3)A={x($y)[y?Z且x=2y]} 答:A是由偶数集合,是环,但〈A,′半群无幺元,所以不是整环,不是域 (4)A={a/ba,b为正整数,且(a,b)=1} 答:A为正有理数,无加法逆元存在,不构成环 习题十七 2、设n为正整数, Dn为n的所有正因子构成的集合, 画出D6, 、 D8, 、 D30, 对应的Hasse图,并证明它们都是格 证明:(图略) D6, 菱形 D8, 链 D30, ≌ 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、设L, ú, ù 是格,”£” 是对应的偏序,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 A B C E D F 答:在上图中,A,B互为补元,补元唯一;E,D都是C的补元;F没有补元 17、设L, ∨,∧ 是有补分配格,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] 推论:当G,*是有限群时,对非空子集S,如对a,b?S, 有a*b?S,则S,*是G,*的子群。(即只需判断在S中运算是否封闭即可) 证明: 设G中有n个元素;因为S是封闭的,所以对任意S中元素a,那么a,a*a,a*a*a,…an+1,中一定有相同的元素,设ai=aj(ji,取最小值),那么aj-I = e,所以e在S中,且a 与 aj-i-1就为逆元,所以S,*是群,结论成立 [2] 定理15.5 设G,*是一个群,a?G, 构造映射ja:G→G,使对 x?G, ja(x)=a*x ,令H={ja a?G},则对于函数的复

http://mojdzwonek.com/tuilijiedian/208.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有