离散数学习题答案-2015

离散数学习题答案

习题一

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

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

（6） 小张身体单薄，但是极少生病，并且头脑好使 --- 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） （P ∨（～P ∧ Q））→ Q 可满足式 0 1 1 1 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、分别利用真值表法和等价变换法求下列公式的主合取范式及主析取范式:

(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 所以： 主合取范式为 = (～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) 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 所以： 主合取范式为 = (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 （任何公式可蕴含永真式）

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、把下列公式化为等价的前束范式，再求出对应的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)] ??(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 B

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

AB

b} ? 2 ? 2 )

ABA B

（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

习题四

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，所以传递性不成立

22 22

因为 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? IA S∩ 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是反对称的

假设R不是反对称的，那么必定存在 a ≠b∧(a,b) ∈R ∧ (b,a) ∈R，那么（a,b）∈R-1

∩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是传递的

2

综上所述，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 o R = R o R = R

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

n

（1）IA = IA

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

n

性质，IA = IA

（2）IA o R=R oIA =R

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

n23n

（3）(R∪IA)=IA∪R∪R∪R?∪R

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

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

?0??0?1??0MR???0?0??0?0?

100001000000000100000000000 0100000010000000001000??0?0??0??0?0??1?0??Mt(R)?1??1?1??0???0?0??0?0?111011100001000100010001001111001111 0011110011110??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、设一个树中度为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?r

mktrk

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

k -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 ,0

30、设是群，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上的双射函数；下面所明是群

本文来源：https://www.bwwdw.com/article/73t6.html