离散数学(第五版)清华大学出版社第1章习题解答

（完整版）离散数学答案（尹宝林版）第一章习题解答第一章命题逻辑习题与解答⒈ 判断下列语句是否为命题，并讨论命题的真值。

⑴ 2x - 3 = 0。

⑵ 前进！⑶ 如果8 + 7 > 20，则三角形有四条边。

⑷ 请勿吸烟！⑸ 你喜欢鲁迅的作品吗？⑹ 如果太阳从西方升起，你就可以长生不老。

⑺ 如果太阳从东方升起，你就可以长生不老。

解⑶,⑹,⑺表达命题，其中⑶,⑹表达真命题，⑺表达假命题。

⒉ 将下列命题符号化：⑴ 逻辑不是枯燥无味的。

⑵ 我看见的既不是小张也不是老李。

⑶ 他生于1963年或1964年。

⑷ 只有不怕困难，才能战胜困难。

⑸ 只要上街，我就去书店。

⑹ 如果晚上做完了作业并且没有其它事情，小杨就看电视或听音乐。

⑺ 如果林芳在家里，那么他不是在做作业就是在看电视。

⑻ 三角形三条边相等是三个角相等的充分条件。

⑼ 我进城的必要条件是我有时间。

⑽ 他唱歌的充分必要条件是心情愉快。

⑾ 小王总是在图书馆看书，除非他病了或者图书馆不开门。

解⑴ p ：逻辑是枯燥无味的。

“逻辑不是枯燥无味的”符号化为 ?p 。

⑵ p ：我看见的是小张。

q ：我看见的是老李。

“我看见的既不是小张也不是老李”符号化为q p ?∧?。

⑶ p ：他生于1963年。

q ：他生于1964年。

“他生于1963年或1964年”符号化为p ⊕ q 。

⑷ p ：害怕困难。

q ：战胜困难。

“只有不怕困难，才能战胜困难”符号化为q → ? p 。

⑸ p ：我上街。

q ：我去书店。

“只要上街，我就去书店”符号化为p → q 。

⑹ p ：小杨晚上做完了作业。

q ：小杨晚上没有其它事情。

r ：小杨晚上看电视。

s ：小杨晚上听音乐。

“如果晚上做完了作业并且没有其它事情，小杨就看电视或听音乐”符号化为s r q p ∨→∧。

⑺ p ：林芳在家里。

q ：林芳做作业。

r ：林芳看电视。

“如果林芳在家里，那么他不是在做作业就是在看电视”符号化为r q p ∨→。

⑻ p ：三角形三条边相等。

习题参考解答习题1.11、（3）P：银行利率降低Q：股价没有上升P∧Q（5）P：他今天乘火车去了北京Q：他随旅行团去了九寨沟PQ（7）P：不识庐山真面目Q：身在此山中Q→P，或～P→～Q（9）P：一个整数能被6整除Q：一个整数能被3整除R：一个整数能被2整除T：一个整数的各位数字之和能被3整除P→Q∧R ，Q→T2、（1）T （2）F （3）F （4）T （5）F（6）T （7）F （8）悖论习题 1.31（3）)()()()()()(R P Q P R P Q P R Q P R Q P →∨→⇔∨⌝∨∨⌝⇔∨∨⌝⇔∨→（4）()()()(())()(()())(())()()()()P Q Q R R P P R Q R P P R R P Q R P P R P R Q R Q P ∧∨∧∨∧=∨∧∨∧=∨∨∧∧∨∧=∨∧∨∧∨∧∨=右2、不， 不， 能习题 1.41(3) (())~((~))(~)()~(~(~))(~~)(~)P R Q P P R Q P P R T P R P R Q Q P R Q P R Q →∧→=∨∧∨=∨∧=∨=∨∨∧=∨∨∧∨∨、主合取范式)()()()()()()()()()()()()()())(())(()()(())()())(()((Q P R P Q R P Q R R Q P R Q P R Q P Q P R Q P R P Q R P Q R R Q P R Q P R Q P R Q P Q Q P R P P Q R R R Q Q P P R Q R P P Q R P P Q R P ∧∧∨∧⌝∧∨⌝∧⌝∧∨∧⌝∧⌝∨⌝∧∧⌝∨⌝∧⌝∧⌝=∧∧∨⌝∧∧∨∧⌝∧∨⌝∧⌝∧∨∧⌝∧⌝∨∧⌝∧⌝∨⌝∧∧⌝∨⌝∧⌝∧⌝=∨⌝∧∧∨∨⌝∧⌝∧∨∨⌝∧∨⌝∧⌝=∧∨⌝∧∨⌝=∨⌝∧∨⌝=→∧→ ————主析取范式(2) ()()(~)(~)(~(~))(~(~))(~~)(~)(~~)P Q P R P Q P R P Q R R P R Q Q P Q R P Q R P R Q →∧→=∨∧∨=∨∨∧∧∨∨∧=∨∨∧∨∨∧∨∨ 2、()~()(~)(~)(~~)(~)(~~)P Q R P Q R P Q P R P Q R P Q R P R Q →∧=∨∧=∨∧∧=∨∨∧∨∨∧∨∨∴等价3、解：根据给定的条件有下述命题公式：（A →（C ∇D ））∧～（B ∧C ）∧～（C ∧D ）⇔（～A ∨（C ∧～D ）∨（～C ∧D ））∧（～B ∨～C ）∧（～C ∨～D ）⇔（（～A ∧～B ）∨（C ∧～D ∧～B ）∨（～C ∧D ∧～B ）∨（～A ∧～C ）∨（C ∧～D ∧～C ）∨（～C ∧D ∧～C ））∧（～C ∨～D ）⇔（（～A ∧～B ）∨（C ∧～D ∧～B ）∨（～C ∧D ∧～B ）∨（～A ∧～C ）∨（～C ∧D ∧～C ）） ∧（～C ∨～D ）⇔（～A ∧～B ∧～C ）∨（C ∧～D ∧～B ∧～C ）∨（～C ∧D ∧～B ∧～C ）∨ （～A ∧～C ∧～C ）∨（～C ∧D ∧～C ∧～C ）∨（～A ∧～B ∧～D ）∨（C ∧～D ∧～B ∧～D ）∨（～C ∧D ∧～B ∧～D ）∨（～A ∧～C ∧～D ）∨ （～C ∧D ∧～C ∧～D ）（由题意和矛盾律）⇔（～C ∧D ∧～B ）∨（～A ∧～C ）∨（～C ∧D ）∨（C ∧～D ∧～B ）⇔（～C ∧D ∧～B ∧A ）∨ （～C ∧D ∧～B ∧～A ）∨ （～A ∧～C ∧B ）∨ （～A ∧～C ∧～B ）∨ （～C ∧D ∧A ）∨ （～C ∧D ∧～A ）∨（C ∧～D ∧～B ∧A ）∨（C ∧～D ∧～B ∧～A ）⇔（～C ∧D ∧～B ∧A ）∨ （～A ∧～C ∧B ∧D ）∨ （～A ∧～C ∧B ∧～D ）∨（～A ∧～C ∧～B ∧D ）∨ （～A ∧～C ∧～B ∧～D ）∨（～C ∧D ∧A ∧B ）∨ （～C ∧D ∧A ∧～B ）∨ （～C ∧D ∧～A ∧B ）∨ （～C ∧D ∧～A ∧～B ）∨（C ∧～D ∧～B ∧A ）∨（C ∧～D ∧～B ∧～A ） ⇔（～C ∧D ∧～B ∧A ）∨ （～A ∧～C ∧B ∧D ）∨ （～C ∧D ∧A ∧～B ）∨ （～C ∧D ∧～A ∧B ） ∨（C ∧～D ∧～B ∧A ）⇔（～C ∧D ∧～B ∧A ）∨ （～A ∧～C ∧B ∧D ）∨（C ∧～D ∧～B ∧A ） 三种方案：A 和D 、 B 和D 、 A 和C习题 1.51、 （1）需证()(())P Q P P Q →→→∧为永真式()(())~(~)(~())~~(~)(()(~))~(~)(~)()P Q P P Q P Q P P Q P P P Q P Q TP Q P Q T P Q P P Q →→→∧=∨∨∨∧∨=∨∨∧∨=∨∨∨=∴→⇒→∧（3）需证S R P P →∧⌝∧为永真式SR P P T S F S R F S R P P ⇒∧⌝∧∴⇔→⇔→∧⇔→∧⌝∧3A B A B ⇒∴→ 、为永真式。

第1章习题1.1(2) 简单命题（3），（4），（5）不是命题(6) 复合命题1.5p∧，其中，p：2是偶数，q：2是素数。

（1）qp→，其中，p：天下大雨，q：他乘公共汽车上班（5）qq→，其中，p，q的含义同（5）（6）pq→，其中，p，q的含义同（5）（7）p1.7（1）对（1）采用两种方法判断它是重言式。

真值表法表1.2给出了（1）中公式的真值表，由于真值表的最后一列全为1，所以，（1）为重等值演算法→)p∨∨q(rp∨⇔（蕴含等值式）∨⌝qp∨(r)p∨⌝⇔)(（结合律）p∨∨rqp⇔1（排中律）∨rq∨⇔（零律）1由最后一步可知，（1）为重言式。

（3）用等值演算法判（3）为矛盾式(→⌝)p∧qq⌝⇔)(（蕴含等值式）⌝q∨qp∧⇔（德·摩根律）⌝∧p∧qq∧⇔（结合律）⌝(q)qp∧0∧⇔p （矛盾律）0⇔（零律）由最后一步可知，（3）为矛盾式。

（10）非重言式的可满足式 1.8（1）从左边开始演算)()(q p q p ⌝∧∨∧)(q q p ⌝∨∧⇔ （分配律）1∧⇔p （排中律） .p ⇔ （同一律）（2）从右边开始演算)(r q p ∧→)(r q p ∧∨⌝⇔ （蕴含等值式） )()(r p q p ∨⌝∧∨⌝⇔ （分配律） ).()(r p q p →∧→⇔ （蕴含等值式）1.9（1）))((p q p →∧⌝ ))((p q p ∨∧⌝⌝⇔ （蕴含等值式）p q p ⌝∧∧⇔（德·摩根律） q p p ∧⌝∧⇔)(（结合律、交换律）q ∧⇔0 （矛盾式）.0⇔（零律）由最后一步可知该公式为矛盾式。

（2）)())()((q p p q q p ↔↔→∧→)()(q p q p ↔↔↔⇔（等价等值式）由于较高层次等价号两边的公式相同，因而此公式无成假赋值，所以，它为重言式。

1.12 (1) 设(1)中公式为A.)())((r q p r q p A ∧∧→∧∨⇔ )())((r q p r q p A ∧∧∨∧∨⌝⇔)()(r q p r q p A ∧∧∨⌝∨⌝∧⌝⇔ )()()(r q p r p q p A ∧∧∨⌝∧⌝∨⌝∧⌝⇔)())(())((r q p r q q p r r q p A ∧∧∨⌝∧⌝∨∧⌝∨∨⌝∧⌝∧⌝⇔)()()()()(r q p r q p r q p r q p r q p A ∧∧∨⌝∧∧⌝∨⌝∧⌝∧⌝∨∧⌝∧⌝∨⌝∧⌝∧⌝⇔)()()()(r q p r q p r q p r q p A ∧∧∨⌝∧∧⌝∨∧⌝∧⌝∨⌝∧⌝∧⌝⇔7210m m m m A ∨∨∨⇔于是,公式A 的主析取范式为7210m m m m ∨∨∨易知,A 的主合取范式为6543M M M M ∨∨∨A 的成真赋值为000, 001, 010, 111A 的成假赋值为011,100,101,110(2)设(2)中公式为B)()(p q q p B ∨⌝→→⌝⇔ )()(p q q p ∨⌝→∨⌝⌝⇔ )()(p q q p ∨⌝→∨⇔ )()(p q q p ∨⌝∨∨⌝⇔ p q q p ∨⌝∨⌝∧⌝⇔)())(())(()(q q p q p p q p ⌝∨∧∨⌝∧⌝∨∨⌝∧⌝⇔)()()()()(q p q p q p q p q p ∧∨⌝∧∨⌝∧∨⌝∧⌝∨⌝∧⌝⇔ )()()(q p q p q p ∧∨⌝∧∨⌝∧⌝⇔320m m m ∨∨⇔所以,B 的主析取范式为320m m m ∨∨.B 的主合取范式为1M B 的成真赋值为00,10,11. B 的成假赋值为01. 1.14 设p:A 输入;设q:B 输入; 设r:C 输入;由题的条件,容易写出C B A F F F ,,的真值表,见表1.5所示.由真值表分别写出它们的主析范邓范式,而后,将它们都化成与之等值的}{↓中的公式即可.)()()()(r q p r q p r q p r q p F A ∧∧∨⌝∧∧∨∧⌝∧∨⌝∧⌝∧⇔)()()()(r r q p r r q p ∨⌝∧∧∨∨⌝∧⌝∧⇔)()(q p q p ∧∨⌝∧⇔ )(q q p ∨⌝∧⇔ p ⇔)()(r q p r q p F B ∧∧⌝∨⌝∧∧⌝⇔)()(r r q p ∨⌝∧∧⌝⇔ )(q p ∧⌝⇔ )(q p ∧⌝⌝⌝⇔ )(q p ⌝∨⌝⇔q p ⌝↓⇔)(q q p ↓↓⇔. )(r q p F C ∧⌝∧⌝⇔r q p ∧∨⌝⇔)(r q p ∧↓⇔)( ))((r q p ∧↓⌝⌝⇔ ))((r q p ⌝∨↓⌝⌝⇔ r q p ⌝↓↓⌝⇔)()())()((r r q p q p ↓↓↓↓↓⇔1．19 (1)证明 ①r q ∨⌝ 前提引入②r ⌝ 前提引入③q ⌝ ①②析取三段论 ④)(q p ⌝∧⌝ 前提引入 ⑤q p ∨⌝ ④置换⑥p ⌝ ③⑤析取三段论 (2)附加前提证明法：证明 ①r 附加前提引入 ②r p ⌝∨ 前提引入③p ①②析取三段论④)(s q p →→ 前提引入 ⑤s q → ③④假言推理 ⑥q 前提引入 ⑦s ⑤⑥假言推理 (5)归缪法：证明 ①q 结论的否定引入②s r ∨⌝ 前提引入 ③s ⌝ 前提引入④r ⌝ ②③析取三段论 ⑤r q p →∧)( 前提引入 ⑥)(q p ∧⌝ ④⑤拒取式 ⑦q p ⌝∨⌝ ⑥置换⑧p 前提引入⑨q ⌝ ⑦⑧析取三段论 ⑩q q ⌝∧ ①⑨合取 ⑪0 ⑩置换 1.20 设p ：他是理科生q ：他是文科生 r ：他学好数学 前提 r p q r p ⌝→⌝→,,结论q通过对前提和结论的观察，知道推理是正确的，下面用构造证明法给以证明。

离散数学（第五版）清华大学出版社第1章习题解答1．1除（3），（4），（5），（11）外全是命题，其中，（1），（2），（8），（9），（10），（14），（15）是简单命题，（6），（7），（12），（13）是复合命题。

分析首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。

本题中，（3）为疑问句，（5）为感叹句，（11）为祈使句，它们都不是陈述句，所以它们都不是命题。

其次，4）这个句子是陈述句，但它表示的判断结果是不确定。

又因为（1），（2），（8），（9），（10），（14），（15）都是简单的陈述句，因而作为命题，它们都是简单命题。

（6）和（7）各为由联结词“当且仅当”联结起来的复合命题，（12）是由联结词“或”联结的复合命题，而（13）是由联结词“且”联结起来的复合命题。

这里的“且”为“合取”联结词。

在日常生活中，合取联结词有许多表述法，例如，“虽然……，但是……”、“不仅……，而且……”、“一面……，一面……”、“……和……”、“……与……”等。

但要注意，有时“和”或“与”联结的是主语，构成简单命题。

例如，（14）、（15）中的“与”与“和”是联结的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或“与”出现的命题时，要根据命题所陈述的含义加以区分。

1．2（1）p:2是无理数，p为真命题。

（2）p:5能被2整除，p为假命题。

（6）p→q。

其中，p:2是素数，q：三角形有三条边。

由于p与q都是真命题，因而p→q为假命题。

（7）p→q，其中，p：雪是黑色的，q：太阳从东方升起。

由于p为假命可编辑范本题，q为真命题，因而p→q为假命题。

（8）p:2000年10月1日天气晴好，今日（1999年2月13日）我们还不知道p的真假，但p的真值是确定的（客观存在的），只是现在不知道而已。

（9）p：太阳系外的星球上的生物。

它的真值情况而定，是确定的。

1（10）p：小李在宿舍里. p的真值则具体情况而定，是确定的。

#include<stdio.h>#include<stdlib.h>#include<malloc.h>#define MAX_STACK_SIZE 100typedef int ElemType;typedef struct{ElemType data[MAX_STACK_SIZE];int top;} Stack;void InitStack(Stack *S){S->top=-1;}int Push(Stack *S,ElemType x){if(S->top==MAX_STACK_SIZE-1){printf("\n Stack is full!");return 0;}S->top++;S->data[S->top]=x;return 1;}int Empty(Stack *S){return (S->top==-1);}int Pop(Stack *S,ElemType *x){if(Empty(S)){printf("\n Stack is free!");return 0;}*x=S->data[S->top];S->top--;return 1;}void conversion(int N){int e;Stack *S=(Stack*)malloc(sizeof(Stack));InitStack(S); while(N){Push(S,N%2);N=N/2;}while(!Empty(S)){Pop(S,&e);printf("%d ",e);}}void main(){ int n;printf("请输入待转换的值n：\n");scanf ("%d",&n);conversion(n);}习题1.判断下列语句是否是命题，为什么？若是命题，判断是简单命题还是复合命题？(1)离散数学是计算机专业的一门必修课。

离散数学第1章答案习题1.11、（1）否（2）否（3）是，真值为0（4）否（5）是，真值为12、（1）P：天下⾬ Q：我去教室┐P → Q（2）P：你去教室 Q：我去图书馆 P → Q（3）P，Q同（2） Q → P（4）P：2是质数 Q：2是偶数 P∧Q3、（1）0（2）0（3）14、（1）如果明天是晴天，那么我去教室或图书馆。

（2）如果我去教室，那么明天不是晴天，我也不去图书馆。

（3）明天是晴天，并且我不去教室，当且仅当我去图书馆。

习题1.21、（1）是（2）是（3）否（4）是（5）是（6）否2、（1）(P → Q) →R，P → Q，R，P，Q（2）(┐P∨Q) ∨（R∧P），┐P ∨ Q，R∧P，┐P，Q，R，P（3）((P → Q) ∧ (Q → P)) ∨┐(P → Q))，(P → Q) ∧(Q → P)，┐(P → Q)，P → Q，(Q → P)，P → Q，P，Q，Q，P，P，Q 3、（1）((P → Q) → (Q → P)) → (P → Q)（2）((P → Q) ∨ ((P → Q) → R))→ ((P → Q) ∧ ((P → Q) → R)) （3）(Q → P∧┐P) → (P∧┐P → Q)4、(P → Q) ∨ ((P∧Q) ∨ (┐P∧┐Q)) ∧ (┐P∨Q)习题1.31、（1）I(P∨(Q∧R)) = I(P)∨(I(Q)∧I(R)) = 1∨(1∧0) = 1（2）I((P∧Q∧R)∨(┐(P∨Q)∧┐(R∨S))) = (1∧1∧0)∨(┐(1∨1)∧┐(0∨1)) = 0∨(0∧0) = 0（3）I((P←→R)∧(┐Q→S)) = (1←→0)∧(┐1→1) = 0∧1 = 0（4）I((P∨(Q→R∧┐P))←→(Q∨┐S)) = (1∨(1→(0∧┐1)))←→(1∨┐1) = 1←→1 = 1（5）I(┐(P∧Q)∨┐R∨((Q←→┐P)→R∨┐S)) = ┐(1∧1)∨┐0∨((1←→┐1)→(0∨┐1)) = 0∨1∨1 = 13、（1）原式 <=> F→Q <=> T 原式为永真式（2）原式 <=> ┐T∨(┐(┐P∨Q)∨(┐┐Q∨┐P)) <=> (P∧┐Q)∨(Q∨┐P)<=> (P∧┐Q)∨┐(P∧┐Q) <=> T 原式为永真式（3）原式 <=> ┐(P∧Q) ←→┐(P∧Q) <=> T 原式为永真式（4）原式 <=> P∧(Q∨R) ←→ P∧(Q∨R) <=> T 原式为永真式（5）原式 <=> ┐(P∨┐Q)∨Q <=> (┐P∧Q)∨Q <=> Q 原式为可满⾜式（6）原式 <=> ┐(P∧Q)∨P <=> ┐P∨┐Q∨P <=> T∨┐Q <=> T 原式为永真式（7）原式 <=> (┐P∨P∨Q)∧┐P <=> (T∨Q)∧┐P<=> T∧┐P <=> ┐P 原式为可满⾜式（8）原式 <=> ┐((P∨Q) ∧(┐Q∨R))∨(┐P∨R) <=> (P∧┐Q)∨(Q∧┐R)∨(┐P∨R)<=> ((P∧┐Q)∨┐P)∨((Q∧┐R)∨R)<=>(( P∨┐P)∧(┐Q∨┐P))∨(( Q∨R)∧(┐R∨R))<=> (┐Q∧┐P)∨( Q∨R) <=> T 原式为永真式4、（1）左 <=> ┐P∨┐Q∨P <=> ┐┐P∨(┐P∨┐Q) <=> 右（2）左 <=> ┐(┐P∨Q) <=> 右（3）左 <=> ┐(P∧Q)∨P <=> ┐P∨┐Q∨P <=> T∨┐Q <=> 右（4）左 <=> ┐(P→Q)∨┐(Q→P) <=> (P∧┐Q)∨(Q∧┐P) <=> 中<=> ((P∧┐Q)∨Q)∧((P∧┐Q)∨┐P)<=> (P∨Q)∧(┐Q∨Q)∧(P∨┐P)∧(┐Q∨┐P)<=> (P∨Q)∧┐(P∧Q) <=> 右(5)左?(?P∨Q)∧(?R∨Q)??(P∨Q)∨Q?右5.(1)左?Q??P∨Q?右(2)(P→(Q→R))→((P→Q)→(P→R))(?P∨?Q∨R)∨?(?P∨Q) ∨(?P∨R)(P∧Q∧?R)∨(P∧?Q)∨?P∨R(P∧Q∧?R)∨((P∨?P)∧(?Q∨?P))∨R(P∧Q∧?R)∨(?Q∨?P∨R)(P∧Q∧?R) ∨?(P∧Q∧?R)T故P→(Q→R)?(P→Q)→(P→R)(3).(P→Q)→(P→P∧Q)(?P∨Q)∨?P∨(P∧Q)(?P∨Q)∨(?P∨P)∧(?P∨Q)(?P∨Q)∨(?P∨Q)T故P→Q?P→P∧Q(4).((P→Q) →Q) →P∨Q(?(?P∨Q) ∨Q) ∨P∨Q((P∨Q)∧?Q)∨P∨Q(P∧?Q)∨(Q∧?Q) ∨P∨Q(P∨Q)∨(P∨Q)T故(P→Q) →Q?P∨Q(5).((P∨?P)→Q)∧((P∨?P)→R)→(Q→R)((?T∨Q)∧(?T∨R)) ∨?Q∨R(Q∧R)∨?Q∨RQ∨?R∨?Q∨RQ∨TT故((P∨?P) →Q)∧((P∨?P)→R)?Q→R(6)左?(Q→F)∧(R→F)(Q∨F)∧(?R∨F)Q∧?RRR∨Q?右6.(1)原式?(?P∧?Q∧R)(2)原式??P∨?Q∨P??(P∧Q∧?P)(3)原式?P∨(Q∨?R∨P)?P∨Q∨?R??(?P∧?Q∧R)7.(1)原式??(?P∨?Q∨P)(2)原式?(?P∨Q∨?R) ∧?P∧Q??(?(?P∨Q∨?R)∨P∨?Q)(3)原式??P∧?Q∧ (R∨P) ??(P∨Q∨?(R∨P))8. (1) (P∨Q)∧((?P∧ (?P∧Q))∨R)∧?P(2)(P∨Q∨R)∧(?P∧R)(3)(P∨F)∧(Q∨T)习题1.41.(1)原式??(?P∨?Q)∨((?P∨?Q)∧(Q∨P))(?P∨?Q)∨(Q∨P)(P∧Q) ∨Q∨PQ∨P,既是析取范式⼜是合取范式(2)原式?((?P∨Q)∨(?P∨?Q))∧(?(?P∨Q) ∨?(?P∨?Q)) ?(P∧Q)∨(P∧?Q) 析取范式P∧(Q∨?Q)合取范式(3)原式??P∨Q∨?S∨ (?P∧Q)析取范式(P∨(?P∧Q))∨Q∨?SP∨Q∨?S合取范式(4)原式?P∨P∨Q∨Q∨R既是析取范式⼜是合取范式2.(1)原式?P∨?Q∨R为真的解释是：000，001，011，100，101，110，111故原式的主析取范式为:(?P∧?Q∧?R)∨(?P∧?Q∧R)∨(?P∧Q∧R)∨(P∧?Q∧?R)∨(P∧?∧QR)∨(P∧Q∧?R)∨(P∧Q∧R)(2)原式?(P∧?Q) ∨R(P∧?Q∧(R∨?R))∨((P∨?P)∧R)(P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q)∨( ?P∧R)(P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧(Q∨?Q)∧R)∨(?P∧(Q∨?Q)∧R) ?(P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R)∨(P∧?Q∧R)∨(? P∧Q∧R)∨(?P∧?Q∧R)(P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R) ∨(?P∧Q∧R)∨(?P∧?Q∧R)为真的解释是101，100，111，011，001(3)原式?(?P∨(Q∧R))∧(P∨(?Q∧?R))((P∨ (Q∧R)) ∧P)∨(( ?P∨ (Q∧R))∧( ?Q∧?R))(P∧P)∨(Q∧P∧R)∨( ?P∧?Q∧?R)∨(Q∧R∧?Q∧?R)(P∧Q∧R)∨(?P∧?Q∧?R)为真的解释是：000,111(4)原式?P∨P∨Q∨Q∨R?P∨Q∨R为真的解释是：001，010，011，100，101，110，111故原式的主析取范式为：(?P∧?Q∧R)∨(?P∧Q∧?R)∨(?P∧Q∧R)∨(P∧?Q∧?R)∨(P∧?Q∧R)∨(P∧Q∧?R)∨(P∧Q∧R)3.(1)原式??P∨Q∨?P∨?Q?T主合取范式，⽆为假的解释。

DMA#1《离散数学及其应⽤》第⼀章部分习题解答（⾃做，随时可能打脸）我读《离散数学及其应⽤》⼀书，所做习题将记录在此，随时打脸，看到哪做到哪写到哪。

本⽂记载第⼀章《基础：逻辑和证明》的练习第⼀章的内容范围很⼴，⽽且从⾼中必修三的基本逻辑学开始，逐渐加深，但开始⼏节的题⽬还不算难（希望后⾯别打脸）1.1 命题逻辑1# a,b,c,d是命题，e,f不是。

其中c是TRUE，d是FALSE，ab请⾃⼰搜索，我是不知道.......2# 命题只有c,e。

其中c⼤概是FALSE吧，e是FALSE。

d和f都不是命题，因为n和x都没有被赋值，因⽽⽆从谈论。

3# a) Linda不⽐Sanjay年轻； b) Mei并不⽐Isabella挣得多（对⽴的是相等和少，写起来⿇烦）； c)Moshe不⽐Monica⾼； d) Abby不⽐Ricardo富有。

8# TTFFT9# FTTTT10# a) 本周我没有买彩票（或者买了两张以上）；b) 本周我买了⼀张彩票，要么我赢得了百万⼤奖； c) 如果本周我买了⼀张彩票，那么我就赢得百万⼤奖；d) 本周我买了⼀张彩票并且赢得了百万⼤奖；e)我赢的百万⼤奖的充要条件是本周我买了⼀张彩票；f)如果我本周没有买彩票，就不会赢得百万⼤奖；g)我不仅没有在这周买彩票，也没有中奖；h)我要么这周没买彩票，要么就买了⽽且中了奖。

13# (cnblog在哪⾥可以⽤latex，挺难受的。

“与”表⽰为&&，“或”表⽰为||，“⾮”表⽰为not）a) p && q; b) p && (not q)； c) not p && not q; d) p||q; e)p → q; f) (p||q)&&(p→not q); g)p ←→ q。

18# TFTT21# 兼或：b,c ; 异或：a,d。

31# 2，16，64，16。

习题 1.11. 下列句子中，哪些是命题？哪些不是命题？如果是命题，指出它的真值。

⑴ 中国有四大发明。

⑵ 计算机有空吗?⑶ 不存在最大素数。

⑷ 21+3 < 5。

⑸ 老王是山东人或河北人。

⑹ 2 与 3 都是偶数。

⑺ 小李在宿舍里。

⑻ 这朵玫瑰花多美丽呀!⑼ 请勿随地吐痰!⑽ 圆的面积等于半径的平方乘以p。

⑾只有 6 是偶数， 3 才能是 2 的倍数。

⑿雪是黑色的当且仅当太阳从东方升起。

⒀如果天下大雨，他就乘班车上班。

解：⑴⑶⑷⑸⑹⑺⑽⑾⑿⒀是命题，其中⑴⑶⑽⑾是真命题，⑷⑹⑿是假命题，⑸⑺ ⒀的真值目前无法确定；⑵⑻⑼不是命题。

2. 将下列复合命题分成若干原子命题。

⑴ 李辛与李末是兄弟。

⑵ 因为天气冷，所以我穿了羽绒服。

⑶ 天正在下雨或湿度很高。

⑷ 刘英与李进上山。

⑸ 王强与刘威都学过法语。

⑹ 如果你不看电影，那么我也不看电影。

⑺我既不看电视也不外出，我在睡觉。

⑻ 除非天下大雨，否则他不乘班车上班。

解：⑴本命题为原子命题；⑵ p：天气冷；q：我穿羽绒服；⑶ p：天在下雨；q：湿度很高；⑷ p：刘英上山；q：李进上山；⑸ p：王强学过法语；q：刘威学过法语；⑹ p：你看电影；q：我看电影；⑺ p：我看电视；q：我外出；r ：我睡觉；⑻ p：天下大雨；q：他乘班车上班。

3. 将下列命题符号化。

⑴ 他一面吃饭，一面听音乐。

⑵ 3 是素数或 2 是素数。

⑶ 若地球上没有树木，则人类不能生存。

⑷ 8 是偶数的充分必要条件是 8能被 3 整除 ⑸ 停机的原因在于语法错误或程序错误。

⑹ 四边形 ABCD 是平行四边形当且仅当 它的对边平行 ⑺ 如果 a 和 b 是偶数，则 a +b 是偶数。

解：⑴ p ：他吃饭； q ：他听音乐；原命题符号化为： p ∧ q ⑵ p ：3 是素数； q ： 2是素数；原命题符号化为： p ∨q ⑶ p ：地球上有树木； q ：人类能生存；原命题符号化为： p → q⑷ p ：8 是偶数； q ：8能被 3整除；原命题符号化为： p ?q⑸ p ：停机； q ：语法错误； r ：程序错误；原命题符号化为： q ∨r →p⑹ p ：四边形 ABCD 是平行四边形； q ：四边形 ABCD 的对边平行；原命题符号化为： p ?q 。

祝清顺习题一(第1章集合)1.(1)A＝{0, 1, 2, 3};(2)A＝{(-2, 3), (-1, 0), (0, -1), (1, 0), (2, 3)};(3)A＝{-1, -2, -3};(4)A＝{1, 2, 3, 4, 5};(5) A＝{-6, 1}.2.(1) {x | x＝2k, k∈N+, k≤50};(2) {x | x＝6k, k∈Z};(3) {(x, y) | (x-x0)2+(y-y0)2＝r2};(4) {x | 15＜x＜40, x为素数}.3.(1)c＝a或c＝b;(2)a, b为任意值;(3)a＝c＝∅, b＝{∅};(4)b＝c＝d.4.当a=0时, 解得x=2/3满足题意; 当a≠0时, 由∆=9-8a≤0, 得a≥9/8.综上, 满足条件的a的范围是: {a | a≥9/8或a=0}.5.(1)∅, {a}, {{b}}, {c}, {a, {b}}, {a, c}, {{b}, c}, {a, {b}, c};(2)∅, {∅};(3)∅.6.(1) 2n;(2) 2n-1, n≥1, 当n＝0时不存在;(3) 没有. 因为集合只有n个元素, 其子集所含元素个数不可能比整个集合的元素个数多.7.(1) 成立; (2) 不成立; (3) 成立; (4) 成立.8.(1) 不正确, 例如A={a}, B={a, b}, C={{a}, {b}}, 从而A∈B且B∈C, 但A∈C.(2) 不正确, 例子同(1);(3) 不正确, 例如, A＝{1}, B＝{{1}, 2}, C＝{{1}, 3};(4) 不正确, 例如, A＝{1}, B＝{1, 2}, C＝{{1}, {1, 2}}.9.(1) 错误; (2) 正确; (3) 正确; (4) 错误; (5) 错误; (6) 错误; (7) 正确; (8) 正确; (9) 错误; (10) 错误.10.(1) {d }; (2) {a , c , e }; (3) {a , b , c , e }; (4) {b , d , e }. 11.各集合的文氏图如图所示(阴影部分).12.(a) B ∩(C -A );(b) (A -(B ∪C )∪(B ∩(C -A )); (c) C B A ∪(B ∩(C -A )). 13.A ∩B ＝{2, 3}; A ∪B ＝{1, 2, 3, 4, 5}; A -B ＝{1, 4}; B -A ＝{5}; A ⊕B ＝{1, 4, 5}. 14.(1) 不一定. 例如, A ={1, 2, 3}, B ={2, 3}, C ={1, 3}, 则A ∪B ＝A ∪C , 但是B ≠C . (2) 不一定; 例如, A ={1, 2, 3}, B ={2, 3}, C ={2, 3, 4}, 则A ∩B ＝A ∩C , 但是B ≠C . (3) 一定. 由条件有A ⊕(A ⊕B )＝A ⊕(A ⊕C ), 利用对称差的结合律, 有(A ⊕A )⊕B = (A ⊕A )⊕C ,因为A ⊕A = ∅, 有∅⊕B = ∅⊕C , 故有B =C .15.(1) 正确, 证明: 因为A ∩C ⊆ A ⊆ B , A ∩C ⊆ C ⊆ D , 故A ∩C ⊆ B ∩D . (2) 错误, 如A ＝C ＝{1}, B ＝{1, 2}, D ＝{1, 3}. 16.(1) {0, 1, 2, 3, 4, 5, 6, 7, 8}; (2) {1, 2}; (3) {4, 5}; (4) N . 17.由于A ∪B ＝B , 故有A ⊆B , 而B ＝{x | x ＞3}, 故a ≥3. 18.由题意可得 x =3是x 2＋cx ＋15＝0的根, 故有9+3c +15=0, 解之得c = -8, x 2＋cx ＋15＝0即x 2-8x ＋15＝0, 解之得 x =3或x =5, 故B ={3, 5}.由已知条件可得A ={3}, 故有9+3a+b =0, 且 a 2-4b =0. 解之得a = -6, b = 9. 综上可得 a ＝-6, b ＝9, c ＝-8. 19.(1) 因为集合B ＝{x | x 2-5x ＋6＝0}={2, 3}. 又A ∩B ＝A ∪B , 故集合A ＝{x | x 2-ax ＋(A ∩B )∪C B EA BA B E A C C B A -⊕)( B A C B E A C )()(B C B A -a2-19＝0} ={2, 3}, 由根与系数的关系, 有2+3=a, 即a=5.(2) 因为集合C＝{x | x2＋2x-8＝0}={2, -4}, 而∅⊊A∩B, A∩C=∅, 所以3∈A, 2∉A. 故9-3a+a2-19=0, 4-2a+a2-19≠0; 解之得, a = -2.20.因为A∩B＝{-3}, 所以-3∈B, 而x2+1>-3, 所以只可能x-3= -3或2x-1= -3.若x-3 = -3, 则x=0, 此时A={-3, 0, 1}, B={-3, -1, 1}, 故A∩B={-3, 1}, 不合题意.若2x-1= -3, 则x = -1, 此时A={-3, 1, 0}, B={-4, -3, 2}, 故A∩B={-3}, 满足题意.综上所述, x = -1, 且A∪B={-4, -3, 0, 1, 2}.21.由于B=(A∩B)∪(A∩B), 故B={1}∪{3}={1, 3}, B={2, 4}. 由此知A∩B＝{3}, 3∈A, 1∉A; 由A∩B＝{2}知, 2∈A, 4∉A, 从而2∉A, 4∈A, 故A={3, 4}.22.A- (B-C)＝)A=)B(CAB(C=)A=(A-B)∪(A∩C).B()(CA23.(1) ((A∪(B-C))∩A)∪(B- (B-A)) = ((A∪(B∩C))∩A)∪(B∩)B )(A= A∪(B∩(B∪A))= A∪(∅∪(B∩A))=A.(2) ((A∪B)∩B)-(A∪B) = ((A∪B)∩B)∩)A(B= ((A∪B)∩B)∩(A∩B)= (A∪B)∩B∩A∩B=∅(3) ((A∪B∪C)-( B∪C))∪A = ((A∪B∪C) ∩)(CB )∪A= ((A∪B∪C) ∪A) ∩(CB ∪A)= (A∪B∪C) ∩()B )∪A)(C= A∪((B∪C) ∩)(CB )= A∪∅=A.24.将不超过100的正整数排列如下：1 2 3 4 5 6 7 8 9 1011 12 13 14 15 16 17 18 19 2021 22 23 24 25 26 27 28 29 3031 32 33 34 35 36 37 38 39 4041 42 43 44 45 46 47 48 49 5051 52 53 54 55 56 57 58 59 6061 62 63 64 65 66 67 68 69 7071 72 73 74 75 76 77 78 79 8081 82 83 84 85 86 87 88 89 9091 92 93 94 95 96 97 98 99 100可以依次得到素数2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.25.由恒等式mq + np = (mn + pq) − (m− p)(n−q)及条件(m-p) | (mn+pq)可知, (m-p) | (mq+np).26.设n=2k+1, n2-1=(2k+1)2-1=4k(k+1). 因为k(k+1)是相邻两个自然数的乘积, 必然是2的倍数, 所以原式是8的倍数.27.101小于11的平方, 这样就可以只用2、3、5、7这四个质数来验证. 101无法被2、3、5、7整除, 所以101是质数.28.240=2⋅120=22⋅60=23⋅30=24⋅15=24⋅3⋅5.504=2⋅252=22⋅121=22⋅112.654=2⋅327=2⋅3⋅109=2⋅3⋅7⋅1751480 = 2⋅25740 = 22⋅12870 = 23⋅6435= 23⋅5⋅1287 = 23⋅5⋅3⋅429 = 23⋅5⋅32⋅143 = 23⋅32⋅5⋅11⋅13.29.(1) 因为258=21⨯12+6, 所以q=21, r=6.(2) 因为258=(-39)⨯( -15)+12, 所以q= -39, r=12.(3) 因为-367=(-16)⨯24+17, 所以q= -16, r=17.(4) 因为-334=26⨯(-13) +4, 所以q= 26, r=4.30.4475÷8=559⋅8+3559÷8=69⋅8+769÷8=8⋅8+58÷8=1⋅8+01÷8=0⋅8+1所以4475=(10573)8.31.(1) 运用辗转相除法可得934 = 4 ∙ 195 + 154195 = 1 ∙ 154 + 41 154 = 3 ∙ 41 + 31 41 = 1 ∙ 31 +10 31 = 3 ∙ 10 +1 10=10 ∙ 1 +0所以, gcd(934, 195) = 1. 代回去, 有gcd(540, 168) = 1 = 31 - 3 ∙ 10 = 31 - 3 ∙ (41 - 1∙31) = 4 ∙ 31 - 3 ∙ 41 = 4 ∙ (154 - 3 ∙ 41) - 3 ∙ 41 = 4 ∙ 154 - 15 ∙ 41= 4 ∙ 154 - 15 ∙ (195-1 ∙ 154) = 19 ∙ 154 - 15 ∙ 195 = 19 ∙ (934 - 4 ∙ 195) - 15 ∙ 195 = 19 ∙ 934 - 91 ∙ 195故gcd(540, 168) = 19 ∙ 934 - 91 ∙ 195, 其中m =19, n = - 91.(2) 方法同(1). 计算可得：gcd(369, 25) = 1, gcd(369, 25)= 4 ∙ 369 - 59 ∙ 25, 其中m =4, n = - 59. (3) 方法同(1). 计算可得：gcd(369, 25) = 33, gcd(369, 25)= 8 ∙ 165 - 1 ∙ 1287, 其中n =8, m = - 1. (4) 方法同(1). 计算可得：gcd(369, 25) = 2, gcd(369, 25)= 17 ∙ 42 - 2 ∙ 256, 其中n =8, m = - 1. 32.由定理1.3.8, 可得ab =lcm(a , b )⋅gcd(a , b )=24 ∙ 144. 由已知条件a +b =120, 根据根与系数的关系可构造一个一元二次方程x 2-120x +24 ∙ 144=0解之得, x 1=72, x 2=48. 由此可得a =72, b =48或a =48, b =72.33.(1) 运用辗转相除法可得10920 = 1 ∙ 8316 + 2604 8316 = 3 ∙ 2604 + 504 2604 = 5 ∙ 504 + 84 504 = 6 ∙ 84 +0所以, gcd(934, 195) = 84.(2) 对于(1)中各式回代过去, 有gcd(10920, 8316) = 84 = 2604 - 5 ∙ 504 = 2604 - 5 ∙ (8316 - 3 ∙ 2604)= 16 ∙ 2604 - 5 ∙ 8316= 16 ∙ (10920- 1 ∙ 8316) - 5 ∙ 8316 = 16 ∙ 10920- 21 ∙ 8316故gcd(10920, 8316) = - 21 ∙ 8316+16 ∙ 10920, 其中m = - 21, n =16.(3) 由最大公因子与最小公倍数的关系, 有84109208316),gcd(),(lcm ⨯==b a ab b a =1081080.34.记gcd(a , b )=d , 则有d | a 且d | b , 从而d | (ma+nb ), 即d | 1, 所以d =1. 35.由容斥原理, 得| A ∪B ∪C |＝| A |＋| B |＋| C |-| A ∩B |-| A ∩C |-| B ∩C |＋| A ∩B ∩C | | A ∩B ∩C |=| A ∪B ∪C |-(| A |＋| B |＋| C |-| A ∩B |-| A ∩C |-| B ∩C |)=11-(6+8+6-3-2-5) = 1.36.设A , B 分别表示在第一次和第二次考试中得5分的学生的集合, 那么有|S |=50, |A |=26, |B |=21, |)|B A =17. 由|)|B A = |S | – (|A | + |B |) + |A ∩B |, 得|A ∩B | =|)|B A – |S | + (|A | + |B |) = 17 – 50 + 26 + 21=14故有14人两次考试都得5分．37.令A ={修数学的学生}, B ={修物理的学生}, C={修化学的学生}, 则|A |=170, |B |=130, |C|=120, | A ∩B |=45, | A ∩C |=20, | B ∩C |=22, | A ∩B ∩C |=3, 故由容斥原理| A ∪B ∪C |＝| A |＋| B |＋| C |-| A ∩B |-| A ∩C |-| B ∩C |＋| A ∩B ∩C |=170+130+120-45-20-22+3=336.38.设A 3={被3整除的数}, A 5={被5整除的数}, 则|A 3|=166, |A 5|=100, |A 3∩A 5| = 33, 所以由容斥原理, 有| A 3∪A 5 |＝| A 3 |＋| A 5 |-| A 3∩A 5|=166+100-33=233. 39.(1) 取全集S = {1, 2,…, 1000}, 令A 1 = { i ︱i ∈S 且5整除i }, A 2 = { i ︱i ∈S 且6整除i }, A 3 ={ i ︱i ∈S 且8整除i }, 于是|A 1| =⎥⎦⎤⎢⎣⎡51000=200, |A 2| =⎥⎦⎤⎢⎣⎡61000=166, |A 3| =⎥⎦⎤⎢⎣⎡81000=125, |A 1∩A 2| =⎥⎦⎤⎢⎣⎡⨯651000=33,|A 1∩A 3| =⎥⎦⎤⎢⎣⎡⨯851000=25, |A 2∩A 3| =⎥⎦⎤⎢⎣⎡}8,6{lcm 1000=41, | A 1∩A 2∩A 3| =⎥⎦⎤⎢⎣⎡}8,6,5{lcm 1000=8, 则由容斥原理得| A 1∪A 2∪A 3 |＝|A 1|＋|A 2|＋|A 3|-|A 1∩A 2|-|A 1∩A 3|-|A 2∩A 3|＋|A 1∩A 2∩A 3 | = 200+166+125-33-25-41+8=400.(2) |1A ∩2A ∩3A |=|S |-| A 1∪A 2∪A 3 |=1000-400=600.即在1, 2, …, 1000中不能被5, 6和8中的任何一个数整除的数的个数为400个40.设U ={到游乐场去玩的儿童}, A ={骑旋转木马的儿童}, B ={坐滑行轨道的儿童}, C ={乘宇宙飞船的儿童}. 由题意得|U |=75, | A ∩B ∩C |=20, | A ∩B |+ |A ∩C |+ |B ∩C|-2| A ∩B ∩C |=55, 得| A∩B|+ A∩C|+ |B∩C|=55+2| A∩B∩C |=55+40=95,由700÷5=140知| A|+|B|+ |C|=140.| A∪B∪C |＝| A |＋| B |＋| C |-| A∩B |-| A∩C |-| B∩C |＋| A∩B∩C |=140-95+20=65.|A∩B∩C|=|U|-| A1∪A2∪A3|=75-65=10.因此有10名儿童没有玩过其中任何一种玩具.41.设U={被调查的大学生}, A={选修线性代数课程}, B={选修概率课程}, C={选修计算机科学课程}. 由题意得|U|=260, |A|=64, |B|=94, |C|=58, | A∩B|=26, |A∩C|=28, |B∩C|=22, | A∩B∩C |=14.利用容斥原理, 得(1) |A∩B∩C|=|U|-| A∪B∪C |=|U|-(| A |＋| B |＋| C |-| A∩B |-| A∩C |-| B∩C |＋| A∩B∩C|)=260-(64+94+58-26-28-22+14)=106.即三门课程都不选修的学生有106人.(2) |A∩B∩C|=|B|-| A∩B |-| B∩C |＋| A∩B∩C|)=94-26-22+14=60.即只选计算机科学课程的学生有60人.42.(1){∅, {a}, {{a}}, {a, {a}}}; (2){ ∅, {{1, {2, 3}}}};(3){∅, {∅}, {a}, {{b}}, {∅, a}, {∅, {b}}, {a, {b}}, {∅, a, {b}}}; (4){∅, {∅}};(5){∅, {∅}, {{∅}}, {∅, {∅}}}.43.A＝{m, n}.44.(1) C∈ρ(A)∩ρ(B) ⇔C∈P(A)∧C∈ρ(B)⇔C ⊆A∧C⊆B⇔C ⊆A∩B⇔C∈ρ(A∩B)所以, ρ(A)∩ρ(B)＝ρ(A∩B).(2) 由幂集的定义易知, B∈ρ(A) ⇔B⊆A. …..(*)必要性：对任意的C∈ρ(A), 则由(*)得C⊆A. 又A⊆B, 所以C ⊆ B. 再由(*)得B∈ρ(B). 所以, ρ(A) ⊆ρ(B).充分性：若ρ(A) ⊆ρ(B), 则由A∈ρ(A)得A∈ρ(B), 再由(*)得A⊆B.(3) 因为C∈ρ(A)∪ρ(B) ⇒C∈ρ(A) 或C∈ρ(B)⇒C ⊆A或C⊆B⇒C ⊆A∪B⇒C∈ρ(A∪B)所以, ρ(A)∪ρ(B) ⊆ρ(A∪B).例如, 设A={1}, B={2}, 则P(A)={∅, {1}}, ρ(B)={∅, {2}}, ρ(A)∪ρ(B)={∅, {1}, {2}}. 而A∪B={1, 2}, ρ (A∪B)={∅, {1}, {2}, {1, 2}}, 所以ρ(A)∪ρ(B) ≠ρ(A∪B).45.(1) A×B×C ={〈a, 1, α〉, 〈a, 1, β〉, 〈a, 2, α〉, 〈a, 2, β〉, 〈a, 4, α〉, 〈a, 4, β〉, 〈b, 1, α〉, 〈b, 1, β〉, 〈b, 2, α〉, 〈b, 2, β〉, 〈b, 4, α〉, 〈b, 4, β〉, 〈c, 1, α〉, 〈c, 1, β〉, 〈c, 2, α〉, 〈c, 2, β〉, 〈c, 4, α〉, 〈c, 4, β〉};(2) B×A ={〈1, a〉, 〈1, b〉, 〈1, c〉, 〈2, a〉, 〈2, b〉, 〈2, c〉, 〈4, a〉, 〈4, b〉, 〈4, c〉};(3)A×B2={〈a, 〈1, 1〉〉, 〈a, 〈1, 2〉〉, 〈a, 〈1, 4〉〉, 〈a, 〈2, 1〉〉, 〈a, 〈2, 2〉〉, 〈a, 〈2, 4〉〉, 〈a, 〈4, 1〉〉, 〈a, 〈4, 2〉〉, 〈a, 〈4, 4〉〉, 〈b, 〈1, 1〉〉, 〈b, 〈1, 2〉〉, 〈b, 〈1, 4〉〉, 〈b, 〈2, 1〉〉, 〈b, 〈2, 2〉〉, 〈b, 〈2, 4〉〉, 〈b, 〈4, 1〉〉, 〈b, 〈4, 2〉〉, 〈b, 〈4, 4〉〉, 〈c, 〈1, 1〉〉, 〈c, 〈1, 2〉〉, 〈c, 〈1, 4〉〉, 〈c, 〈2, 1〉〉, 〈c, 〈2, 2〉〉, 〈c, 〈2, 4〉〉, 〈c, 〈4, 1〉〉, 〈c, 〈4, 2〉〉, 〈c, 〈4, 4〉〉};(4)A×C={〈a, α〉, 〈b, α〉, 〈c, α〉, 〈a, β〉, 〈b, β〉, 〈c, β〉}×{〈a, α〉, 〈b, α〉, 〈c, α〉, 〈a, β〉, 〈b, β〉, 〈c, β〉}.(A×C)2={〈〈a, α〉, 〈a, α〉〉, 〈〈a, α〉, 〈b, α〉〉, 〈〈a, α〉, 〈c, α〉〉, 〈〈a, α〉, 〈a, β〉〉, 〈〈a, α〉, 〈b, β〉〉, 〈〈a, α〉, 〈c, β〉〉, 〈〈b, α〉, 〈a, α〉〉, 〈〈b, α〉, 〈b, α〉〉, 〈〈b, α〉, 〈c, α〉〉, 〈〈b, α〉, 〈a, β〉〉, 〈〈b, α〉, 〈b, β〉〉, 〈〈b, α〉, 〈c, β〉〉, 〈〈c, α〉, 〈a, α〉〉, 〈〈c, α〉, 〈b, α〉〉, 〈〈c, α〉, 〈c, α〉〉, 〈〈c, α〉, 〈a, β〉〉, 〈〈c, α〉, 〈b, β〉〉, 〈〈c, α〉, 〈c, β〉〉, 〈〈a, β〉, 〈a, α〉〉, 〈〈a, β〉, 〈b, α〉〉, 〈〈a, β〉, 〈c, α〉〉, 〈〈a, β〉, 〈a, β〉〉, 〈〈a, β〉, 〈b, β〉〉, 〈〈a, β〉, 〈c, β〉〉, 〈〈b, β〉, 〈a, α〉〉, 〈〈b, β〉, 〈b, α〉〉, 〈〈b, β〉, 〈c, α〉〉, 〈〈b, β〉, 〈a, β〉〉, 〈〈b, β〉, 〈b, β〉〉, 〈〈b, β〉, 〈c, β〉〉, 〈〈c, β〉, 〈a, α〉〉, 〈〈c, β〉, 〈b, α〉〉, 〈〈c, β〉, 〈c, α〉〉, 〈〈c, β〉, 〈a, β〉〉, 〈〈c, β〉, 〈b, β〉〉, 〈〈c, β〉, 〈c, β〉〉}46.(1) 对于任意a∈A, b∈B, 使得〈a, b〉∈A×B. 由于A ⊆C, B ⊆D, 故〈a, b〉∈ C×D, 即A×B ⊆C×D.(2) 对于任意a∈A, 因为〈a, a〉∈A×A, 而A×A＝B×B, 所以〈a, a〉∈B×B, 即a∈B, 从而有A⊆B. 反之, 类似地可以证明B ⊆ A, 因此A＝B.(3) 对于任意a∈A∪B, b∈A∩B, 使得〈a, b〉∈(A∪B)×(A∩B). 由于a∈A∪B, b∈A∩B, 而A∩B≠∅, 则有a∈A或a∈B, 从而〈a, b〉∈A×A或〈a, b〉∈B×B, 因此〈a, b〉∈(A×A)∪(B×B), 亦即(A∪B)×(A∩B) ⊆ (A×A)∪(B×B)成立.(4) 对于任意a∈ A∩B, b∈C∩D, 使得〈a, b〉∈(A∩B)×(C∩D). 由于a∈ A∩B, b∈C∩D,则有a∈A且a∈B, b∈C且b∈D, 从而〈a, b〉∈A×C且〈a, b〉∈B×D, 因此〈a, b〉∈(A×C)∩(B×D), 亦即(A∩B)×(C∩D)⊆ (A×C)∩(B×D)成立.类似地, 可以证明(A×C)∩(B×D)⊆(A∩B)×(C∩D)也成立. 故(A∩B)×(C∩D)＝(A×C)∩(B×D).习题 二 (第2章 关系)1.(1) R ={〈0, 0〉, 〈0, 2〉, 〈2, 0〉, 〈2, 2〉}; (2) R ={〈1, 1〉, 〈4, 2〉};(3) R ={〈5, 6〉, 〈5, 7〉, 〈5, 9〉, 〈4, 25〉, 〈4, 7〉, 〈4 9〉, 〈35, 6〉, 〈35, 9〉, 〈49, 6〉, 〈49, 25〉, 〈49, 9〉};(4) R ={〈2, 6〉, 〈4, 6〉, 〈5, 3〉, 〈5, 7〉, 〈11, 3〉, 〈11, 7〉}.2.dom(R )={a | a =2k , k ∈Z }, ran(R )={b | b =3k , k ∈Z }. 3.(1) 〈25, 5〉∈R ; (2) 〈1, 7〉∉R ; (3) 〈8, 2〉∈R ; (4) 〈3, 3〉∈R ; (5) 〈216, 6〉∈R . 4.(1) M R ＝⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0001100010000010, 关系图为: (2) M R ＝⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0000011100111001110011100, 关系图为:(3) M R ＝⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡000000100000, 关系图为:(4) M R ＝⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡0000000100000000000001110000111100000000000000000, 关系图为: 5.R ＝{〈x , y 〉 | x ∈R , y ∈R 且0≤x ≤3, 0≤y ≤2}. 6.R ＝{〈b , a 〉, 〈b , d 〉, 〈b , e 〉, 〈c , c 〉, 〈c , a 〉, 〈c , e 〉, 〈d , f 〉, 〈d , c 〉, 〈f , e 〉}. 关系矩阵为:3∙14562 ∙0 ∙∙∙∙∙4 ∙ ∙ 1 23 ∙ ∙ ∙∙∙∙1 2 34 ∙0∙ ∙ ∙ ∙ 3 5 27 ∙ 6 8 1 ∙ ∙M R ＝⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡010000000000100100010101011001000000.7.(1) 对于任意x ∈dom(R ∪S ), 有x ∈dom(R ∪S ) ⇔ 存在y 使得〈x , y 〉∈ R ∪S ⇔存在y 使得〈x , y 〉∈R 或〈x , y 〉∈S⇔ 存在y 使得〈x , y 〉∈R 或存在y 使得〈x , y 〉∈S ⇔ x ∈ dom(R ) 或 x ∈ dom(S ) ⇔ x ∈dom(R )∪dom(S ).(2) 设b ∈ ran (R ∩S ), 则必存在a ∈A , 使得〈a , b 〉 ∈ R ∩S , 于是〈a , b 〉 ∈ R 且〈a , b 〉 ∈ S , 因此b ∈ran(R )且b ∈ran(S ), 由交集的定义, b ∈ran(R )∩ran(S ), 故ran(R ∩S ) ⊆ ran(R )∩ ran(S ).但是ran (R )∩ran (S )⊄ran (R ∩S ).设A ={1, 2, 3}, B ={2, 4, 5}, 且令R ={〈1, 2〉, 〈1, 4〉}, S ={〈3, 2〉, 〈1, 4〉, 〈3, 5〉}, 则R ∩S ={〈1, 4〉}. 于是ran(R )={2, 4}, ran(S )={2, 4, 5}, 因此ran(R )∩ran (S )={2, 4}, 而ran(R ∩S ) ={4}, 所以ran (R )∩ran (S )⊄ran (R ∩S ).8.(1) R ∪S ＝{〈1, 2〉, 〈1, 3〉, 〈2, 4〉, 〈3, 4〉, 〈4, 4〉, 〈4, 2〉, 〈4, 3〉}; R ∩S ＝{〈2, 4〉};R -S ＝{〈1, 2〉, 〈3, 4〉, 〈4, 4〉}, R -1＝{〈1, 2〉, 〈2, 4〉, 〈3, 4〉, 〈4, 4〉}.(2) dom(R )＝{1, 2, 3, 4}, ran R ＝{2, 4}, dom(R S )＝{2}, ran(R S )＝{4}. 9．R S ＝{〈1, 3〉 〈1, 2〉, 〈2, 4〉, 〈3, 3〉, 〈3, 2〉}, S R ＝{〈1, 1〉, 〈1, 3〉, 〈2, 4〉, 〈3, 4〉},R 2={〈1, 1〉, 〈1, 2〉, 〈1, 4〉, 〈3, 1〉, 〈3, 2〉, 〈3, 4〉}, R -1={〈1, 1〉, 〈2, 1〉, 〈4, 2〉, 〈1, 3〉, 〈3, 3〉}, S -1＝{〈3, 1〉, 〈2, 2〉, 〈2, 3〉, 〈4, 4〉}, R -1 S -1＝{〈1, 1〉, 〈4, 2〉, 〈4, 3〉, 〈3, 1〉}. 各关系图如下:R S S RR 2 R -1∙∙∙∙3 2 4 1 ∙∙∙∙1 3 4 2 1 23 ∙∙4∙∙∙∙∙∙3 1 2 4∙ ∙ ∙ ∙1 32 4 ∙ ∙ ∙ ∙1 32 4 ∙ ∙ ∙ ∙1 3 42 R -1 S -1 S -1 10．由已知条件, 可得关系R 1={〈0, 0〉, 〈0, 1〉, 〈1, 2〉, 〈2, 3〉, 〈2, 1〉}, R 2＝{〈2, 0〉, 〈2, 1〉}. 经计算得:R 1R 2＝{〈1, 0〉, 〈2, 1〉};R 2R 1＝{〈2, 0〉, 〈2, 1〉, 〈3, 2〉}; R 1R 2R 1＝{〈1, 0〉, 〈1, 1〉, 〈2, 3〉};21R ＝{〈0, 0〉, 〈0, 1〉, 〈0, 2〉, 〈1, 3〉, 〈1, 1〉, 〈2, 2〉}; 22R ＝∅.11.(1) R 1R 2＝{〈b , a 〉, 〈b , d 〉}, R 2R 1={〈d , a 〉}.(2) 写出相应R 1, R 2的关系矩阵为: ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=00000001011000001R M , ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=01001001000100002R M , 计算 ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=0000000101100000121R R R M ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0100100100010000⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0000000101100000=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0000000000000000= O . =21R M ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0000000101100000⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0000000101100000=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0000000001110000. =32R M ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0100100100010000⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0100100100010000⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0100100100010000=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0100100100000000 由此可得, R 1 R 2 R 1＝∅, 21R ＝{〈b , a 〉, 〈b , b 〉, 〈b , c 〉}, 32R ＝{〈c , a 〉, 〈c , d 〉, 〈d , c 〉}.(3) 由关系R 1, R 2可得其逆关系为: 1-1R ={〈b , b 〉, 〈c , b 〉, 〈a , c 〉}, 1-2R ={〈a , b 〉, 〈d , c 〉, 〈a , c 〉, 〈c , d 〉}, 由(1)得(R 1R 2)-1＝{〈a , b 〉, 〈d , b 〉}, 从而有关系矩阵:⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=000000100010010011-R M , ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=010010000000011012-R M , ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=-0010000000000010121)(R R M . 12.(1) R ＝{〈1, 3〉, 〈2, 2〉, 〈3, 1〉, 〈4, 4〉}, 关系图:︒︒︒︒︒︒︒(2) 依次计算出R 的各次幂.⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=10000001001001001R M , ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=10000001001001002R M ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡1000000100100100=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡1000010000100001=E 4 (单位矩阵), =3R M ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡1000010000100001⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡1000000100100100=⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡1000000100100100=M R , =4R M E 4. 故有⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=1000010000100001nR M , n ＝2k , k ∈N ; ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=1000000100100100n R M , n ＝2k +1, k ∈N . 13.(1) 设〈x , y 〉∈ R 1 R 3, 则存在z ∈A , 使得〈x , z 〉∈ R 1且〈z , y 〉∈R 3, 由于R 1 ⊆ R 2, 所以〈x , z 〉∈ R 2, 由关系复合的定义, 有〈x , y 〉∈ R 2 R 3, 从而有R 1 R 3⊆ R 2 R 3.(2) 类似于(1)的方法证明. 14.写出相应R , S 的关系矩阵为: ⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=0000000000010000001000010R M , ⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=0000000010000011000000010S M , 计算M R ∩S ＝⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0000000000000000000000010, M R ∪S ＝⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡000000010010011001000010, M R S ＝⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡0000000000000101000010000.15.由R , S 可得R -1＝{〈x , x 〉, 〈z , x 〉, 〈x , y 〉, 〈y , y 〉, 〈x , z 〉, 〈y , z 〉, 〈z , z 〉}, S -1＝{〈a , x 〉, 〈d , x 〉, 〈a , y 〉, 〈c , y 〉, 〈e , y 〉, 〈b , z 〉, 〈d , z 〉}, (R S )-1={〈a , x 〉, 〈a , y 〉, 〈a , z 〉, 〈b , x 〉, 〈b , z 〉, 〈c , y 〉, 〈c , z 〉, 〈d , x 〉, 〈d , y 〉, 〈d , z 〉, 〈e , y 〉, 〈e , z 〉}.写出相应的矩阵为:⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=-1011101111R M , ⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=-011010101000111S M , ⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=-1101111101011111)(S R M ,o x y 11 o x y1 -1 o x y 11 -1 -1 而⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=⨯--1101111101011111011101110110101010001111R S M M 所以111)(---⨯=R S S R M M M .16.R 是自反的; S 是反自反的; T 既不是自反的也不是反自反的. 17.R 既是对称的也是反对称的; S 是对称的但不是反对称的; T 是反对称的但不是对称的; U 既不是对称的也不是反对称的.18.对于任意a ∈A , (a -a )/2=0, 所以〈a , a 〉∈R , 即R 是自反的.对于任意〈a , b 〉∈R , 则(a -b )/2是整数, 因为整数的相反数也是整数, 所以(b -a )/2是整数, 即〈b , a 〉∈R , 亦即R 是对称的.对于任意〈a , b 〉∈R , 〈b , c 〉∈R , 则(a -b )/2, (b -c )/2都是整数. 设(a -b )/2=m , (b -c )/2=k , 则a -b =2m , b -c =2k , 从而有a -c =2(m -k ), 即(a -c )/2=m -k , 故〈a , c 〉∈R , 因此R 是传递的.19.(1) 例如, 〈1, 2〉, 〈2,1〉∈R , 但〈1,1〉∉R , 故R 是不可传递的.(2) 例如, R 1={〈1,1〉, 〈1, 2〉, 〈2, 1〉, 〈2, 2〉, 〈3, 1〉, 〈3, 2〉, 〈4, 1〉, 〈4, 2〉, 〈4, 3〉}, 是包含R 且具有传递性的关系.(3) 因为R 1并非全域关系(否则, 当R 1是全域关系时, 就找不到了), 所以只要取R 2=A ×A 是A 上的全域关系就可满足R 2⊇R , R 2≠R , 并且全域关系R 2显然是一个传递关系.当然这样的R 2可以构造多个, 如, R 2={〈1,1〉, 〈1, 2〉, 〈2,1〉, 〈2, 2〉, 〈3, 1〉, 〈3, 2〉, 〈3, 3〉, 〈4, 1〉, 〈4, 2〉, 〈4, 3〉}也是满足R 2⊇R , R 2≠R 是一个传递关系.20.(1) 如图(a), 满足: 自反性, 对称性, 反对称性, 传递性. (2) 如图(b), 满足: 反对称性和传递性. (3) 如图(c), 满足: 传递性.(a) (b) (c )21.(1) 满足: 自反性、对称性与传递性, 不满足: 反自反性与反对称性. (2) 满足: 反自反性、反对称性与传递性, 不满足: 自反性、对称性.∙ ∙∙b c a (3) 不满足: 自反性、反自反性、对称性、反对称性、传递性.(4) 满足: 自反性、对称性、反对称性与传递性, 不满足: 反自反性. (5) 不满足: 自反性、反自反性、对称性、反对称性、传递性. 22.图2.26满足: 反对称性与传递性, 不满足: 自反性、反自反性与对称性. 图2.27满足: 反自反性、反对称性与传递性, 不满足: 自反性与对称性. 23.R 是反自反的, 既不是自反的, 对称的, 也不是反对称的, 也不具有传递性. R 的关系图如图所示.24.(1) 如, R ={〈1, 2〉, 〈2, 1〉, 〈4, 2〉, 〈2, 4〉}∪I A . (2) 如, R ={〈2, 1〉, 〈4, 2〉, 〈4, 1〉}∪I A . (3) 如, R ={〈4, 1〉, 〈1, 2〉}∪I A .(4) 如, R ={〈1, 1〉, 〈1, 2〉, 〈1, 3〉, 〈1, 4〉, 〈2, 2〉, 〈2, 3〉, 〈2, 4〉, 〈3, 3〉, 〈3, 4〉, 〈4, 4〉}. 25.(1) 对于R 的关系矩阵M R , 由于对角线上全为0, R 是反自反的, 但不是自反的; 由于矩阵是对称的, 所以R 是对称的, 而M R 关于对角线对称位置上的元素不同时为1, 故R 是反对称的.经过计算可得, ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=10101101101111012R M , 故R 2⊄R , 因此R 不具有传递性. (2) 对于R 的关系矩阵, 由于对角线上不全为1, R 不是自反的; 由于对角线上元素全部非0元, R 不是反自反的; 由于矩阵是对称的, 所有R 是对称的; 因为R -1∩R =R ⊄ I A , 所以R 不是反对称的.经过计算可得, =2R M ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡1000010000110011=M R , 故R 2=R , 所以R 是传递的. 26.(1) 取最小集合A ＝{1, 2}, A 上关系R ＝{〈1, 1〉, 〈1, 2〉}, R 既不是自反的也不是反自反的.(2) 取最小集合A ＝{1, 2, 3}, A 上关系R ＝{〈1, 2〉, 〈2, 1〉, 〈2, 3〉}, R 既不是对称的也不是反对称的.(3) 空集合上的关系既是自反的, 又是反自反的; 既是对称的, 又是反对称的. 因此, 结果同(1), (2).(1) 设R 是自反的, 对任意的a ∈A , 〈a , a 〉∈R , 则〈a , a 〉∈R -1, 故R -1也是自反的.(2) 设R 是传递的. 对于任意〈a , b 〉∈R -1, 〈b , c 〉∈R -1. 所以〈c , b 〉∈R , 〈b , a 〉∈R ; 又因为R 是传递的, 所以〈c , a 〉∈R , 因此〈a , c 〉∈R -1, 故R -1也是传递的.(3) 设R 是反自反的, 对任意的a ∈A , 〈a, a 〉∉R , 则〈a, a 〉∉R -1, 故R -1也是自反的. (4) 对于任意的〈a, b 〉∈ R -1, 则〈b , a 〉∈R , 因为R 是对称的, 故〈a, b 〉∈R , 所以〈b , a 〉∈ R -1. 因此R -1是对称的.(5) 反证法证明. 设R -1不是反对称的, 则存在〈a , b 〉∈R -1, 〈b , a 〉∈R -1, a ≠b , 则〈a , b 〉∈ R , 〈b , a 〉∈R , 与R 是反对称的矛盾.28.(1) 因为R 和S 是自反的, 对任意的a ∈A , 〈a , a 〉∈R 并且〈a , a 〉∈S , 则〈a , a 〉∈R ∩S , 〈a , a 〉∈R ∪S , 故R ∩S 和R ∪S 也是自反的.(2) 对任意的a , b ∈A , a ≠b , 使得〈a , b 〉∈R ∩S . 因为〈a , b 〉∈R ∩S , 所以〈a , b 〉∈R 并且〈a , b 〉∈S ; 因为R 和S 是对称的, 所以〈b , a 〉∈R 并且〈b , a 〉∈S , 则〈b , a 〉∈R ∩S , 〈b , a 〉∈R ∪S , 故R ∪S 和R ∩S 也是对称的.(3) 任意的〈a, b 〉∈R ∩S , 〈b , c 〉∈R ∩S , 则〈a , b 〉∈ R , 〈a , b 〉∈S , 〈b , c 〉∈R , 〈b , c 〉∈S , 因为R 和S 是传递的, 因此〈a , c 〉∈R , 〈a , c 〉∈S , 所以〈a , c 〉∈ R ∩S , 即R ∩S 也是传递的.29.由关系R 可直接写出r (R )和s (R )r (R )＝{〈1, 1〉, 〈1, 2〉, 〈2, 2〉, 〈2, 3〉, 〈3, 1〉, 〈3, 3〉}. s (R )＝{〈1, 2〉, 〈2, 1〉, 〈2, 3〉, 〈3, 2〉, 〈3, 1〉, 〈1, 3〉}. 由关系R 写出关系矩阵M R , 并依次计算其幂为:M R =⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡001100010, 2R M =⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡010001100, 3R M =⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡100010001, M t (R )=M R +2R M +3R M =⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡111111111, 亦即t (R )为A 上的全域关系. 故t (R )＝{〈1, 1〉, 〈1, 2〉, 〈1, 3〉, 〈2, 1〉, 〈2, 2〉, 〈2, 3〉, 〈3, 1〉, 〈3, 2〉, 〈3, 3〉}. 30.由关系R 写出关系矩阵M R 并依次计算其幂为:M R =⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡1000010000111001, ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=10000100101110012R M =3R M =4R M . M t (R )=M R +2R M +3R M +4R M =⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡1000010010111001, 故 t (R )＝{〈1, 1〉, 〈1, 4〉, 〈2, 1〉, 〈2, 2〉, 〈2, 4〉, 〈3, 3〉, 〈4, 4〉}.由关系R 的关系矩阵M R , 经计算得M r (R )＝⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡1101010111100101, M s (R )＝⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0111111111001101, ⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡=01010101010101012R M =3R M ＝4R M , M t (R )=M R +2R M =⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎣⎡0101010101010101. 32.(a) 自反闭包为: ; 对称闭包 ; 传递闭包 .(b) 自反闭包为: ; 对称闭包为: ; 传递闭包为: .(c) 自反闭包为: ; 对称闭包为: ; 传递闭包为: . 33.由关系R 的关系矩阵M R , 可直接写出r (R )和s (R )r (R ) =⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡1010001110001111011011001, s (R ) =⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡1011100111111111110011101.依次计算关系矩阵M R 的各次幂得2R M =⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡1011110111111111011111111, 3R M =⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡1111111111111111111111111=4R M =5R M ,因此有M t (R )=M R +2R M +3R M +4R M +5R M =⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡1111111111111111111111111, 亦即t (R )为A 上的全域关系.34.∙ ∙ ∙∙ ∙∙∙∙∙∙∙ ∙∙∙∙ ∙ ∙ ∙∙∙∙(1) r (R ), s (R ), t (R )的关系图如图所示.R 的自反闭包 R 的对称闭包 R 的传递闭包(2) r (R )={〈a , c 〉, 〈b , d 〉}∪I A ;s (R )={〈a , a 〉, 〈a , c 〉, 〈c , a 〉, 〈b , d 〉, 〈d , b 〉}; t (R )={〈a , a 〉, 〈b , d 〉, 〈a , c 〉}. 35.(1) 因为R 自反, 得r (R )=R , 即R ∪I A =R ,r (s (R ))=s (R )∪I A =(R ∪R -1)∪I A = (R ∪I A )∪R -1=r (R )∪R -1 =R ∪R -1 =s (R ),所以s (R )自反的.类似可以证明t (R )也是自反的. (2) 证明t (R )对称:(t (R ))-1=(R ∪R 2∪…∪R n ∪…)-1= R -1∪(R 2)-1 ∪…∪(R n )-1∪… = R -1∪(R -1)2 ∪…∪(R -1)n ∪…=R ∪R 2∪…∪R n ∪… (∵R 对称，∴R -1 =R ) =t (R )所以t (R )是对称的. 类似可以证明r (R )也是对称的.(3) 证明r (R )传递: 先用归纳法证明下面结论:(R ∪I A )i = I A ∪R ∪R 2∪…∪R i .(i) 当i =1时, R ∪I A = I A ∪R , 结论成立. (ii) 假设i ≤k 时结论成立, 即(R ∪I A )k = I A ∪R ∪R 2∪…∪R k .(iii) 当i =k +1时(R ∪I A )k +1=(R ∪I A )k (R ∪I A )= (I A ∪R ∪R 2∪…∪R k )(I A ∪R )= (I A ∪R ∪R 2∪…∪R k )∪(R ∪R 2∪…∪R k +1) = I A ∪R ∪R 2∪…∪R k ∪R k +1所以结论成立.t (r (R ))=t (R ∪I A )= (R ∪I A )∪(R ∪I A )2∪(R ∪I A )3∪…=(I A ∪R )∪(I A ∪R ∪R 2)∪(I A ∪R ∪R 2∪R 3)∪… = I A ∪R ∪R 2∪R 3∪…= I A ∪t(R ) = I A ∪R (R 传递t(R )=R ) =r (R )所以r (R )是传递的.∙∙ ∙∙a c b d ∙∙a cb ∙ ∙d ∙∙ ∙∙a c b d36.(1) 左边= r (R 1∪R 2)=R 1∪R 2 ⋃I A右边= r (R 1)∪r (R 2) =R 1∪I A ∪R 2∪I A =R 1∪R 2∪I A(1)式得证.(2) 左边=s (R 1∪R 2)=(R 1∪R 2)∪(R 1∪R 2)-1= R 1∪R 2∪R 1-1∪R 2-1= (R 1∪R 1-1)∪(R 2∪R 2-1)=s (R 1)∪s (R 2)(2)式得证.(3) 证明t (R 1∪R 2)⊇t (R 1)∪t (R 2).t (R 1∪R 2)=(R 1∪R 2)∪(R 1∪R 2)2∪┄∪(R 1∪R 2)n而 (R 1∪R 2)2= (R 1∪R 2)o(R 1∪R 2)=((R 1∪R 2)o R 1)∪((R 1∪R 2)o R 2)= R 12∪R 2o R 1∪R 1o R 2∪R 22 ⊇R 12∪R 22 ………(R 1∪R 2)n ⊇R 1n ∪R 2n . 于是有(R 1∪R 2)∪(R 1∪R 2)2 ∪…∪(R 1∪R 2)n ⊇R 1∪R 12∪…∪R 1n ∪R 2∪R 22∪R 22…∪R 2n 即t (R 1∪R 2) ⊇ t (R 1)∪t (R 2), (3)式得证．37.(1) 不满足自反性、反对称性, 所以不是偏序关系; (2) 是偏序关系;(3) 不是偏序关系. 因为若取a =2, 则22|/2, 所以〈2, 2〉∉R , 即R 不具有自反性.38.(a) R={〈5, 2〉, 〈5, 3〉, 〈5, 4〉, 〈5, 1〉, 〈2, 3〉, 〈2, 4〉, 〈1, 3〉, 〈1, 4〉, 〈3, 4〉} I A ; 关系矩阵为：M R =⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡11111010*******0111001101.(b) R={〈1, 2〉, 〈1, 3〉, 〈1, 4〉, 〈5, 2〉, 〈5, 3〉, 〈5, 4〉, 〈3, 4〉, 〈2, 4〉} I A ; 关系矩阵为: M R =⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡1111001000011000101001111.39. . 40. (a) ; (b) ; (c), 全序关系.∙∙∙∙∙12345∙∙∙∙1234∙∙∙∙1234∙∙∙∙123441. 哈斯图为：(1) ; (2) ; (3) ; (4) ,其中(2)、(3)是全序关系.42.因为R 1不满足自反性, 但满足反自反性和传递性, 因而R 1是拟序关系; 而R 2, R 3满足自反性, 反对称性和传递性, 故R 2, R 3是偏序关系.43.(1) 因为R 是S 上的偏序, 所以R 是自反的、反对称的、传递的. 因而对于任意x ∈S , 〈x , x 〉∈R , 又对于任意x ∈S ', 有〈x , x 〉∈ S '⨯S '. 所以对于任意x ∈S ', 有〈x , x 〉∈ R ', 所以R '是自反的.设〈x , y 〉∈ R ', 〈y , x 〉∈ R ', 则〈x , y 〉∈ R , 〈y , x 〉∈ R , 由R 是反对称的, 故x =y . 因而若R 是反对称的, 则R '也是反对称的.若R 在S 上是传递的, 则由〈a , b 〉∈ R ', 〈b , c 〉∈ R ', 有〈a , b 〉∈ R , 〈a , b 〉∈ S '⨯S ', 〈b , c 〉∈ R ', 〈b , c 〉∈ S '⨯S ', 故〈a , c 〉∈ R , 〈a , c 〉∈ S '⨯S ', 因此〈a , c 〉∈ R ', 即R '是传递的, 因此R 是也是传递的, 所以R '是偏序.(2) 因为R 是S 上的拟序, 所以R 是反自反的、传递的. 因而对于任意x ∈ S ', 〈x , x 〉∉R ,所以〈x , x 〉∉ R ', 因而R '也是反自反的. 由(1)的证明过程可以知道, R '是传递的, 因此R '是拟序.(3) 若R 是线序的, 则R 是偏序的, 且对于任意的a , b ∈S , 或者〈a , b 〉∈ R 或者〈b , a 〉∈ R .因而对于任意的x , y ∈ S ', 也有〈x , y 〉∈ R 或〈y , x 〉∈ R . 但〈x , y 〉∈ S '⨯S ', 〈y , x 〉∈ S '⨯S ', 所以, 或者〈x , y 〉∈ R '或者〈y , x 〉∈ R '. 因而S '上任一元素是可比较的, 又由(1)知R '也是偏序, 所以R '是S '上的线序.44.对于任意x ∈N , 则x 为自然数, 所以x ≥x , 所以〈x , x 〉∈ R ≥, 即为自反关系. 若〈x , y 〉∈ R ≥, 〈y , x 〉∈ R ≥, 则x ≥y 且y ≥x , 故x=y , 因此R ≥是反对称的. 若〈x , y 〉∈ R ≥, 〈y , z 〉∈ R ≥, 则x ≥y 且y ≥z , 故x ≥z , 因此R ≥是可传递的.综上所述, 关系R ≥是一种偏序关系. 又在N 上任意两个自然数都可以比较大小, 也就是在N 上关于关系R ≥都是可比较的, 因此R ≥是全序关系.45.由于包含关系R ⊆是一种偏序关系, 对于ρ的元素按照包含关系有：∅⊆{a }⊆{a , b }⊆{a , b , c }.由此可知ρ的元素按照包含关系存在一条链, 因此R ⊆是全序关系.46．在集合A ＝{x | x 是一个实数且-5≤x ≤20}中, 因为任意一个实数自身不会小于自身, 所以小于关系是反自反的; 又因为小于关系具有传递性; 所以小于关系是A 上的拟∙∙∙∙∙24816 32 ∙∙∙∙∙3612 36 72 ∙∙∙∙24 36 2 ∙ ∙ 36 12 ∙∙ 10 3 2 6 4 12∙ ∙ ∙ ∙ ∙130 ∙序关系.47.因为I A ⊆R , 所以R 具有自反性. R 的关系矩阵为:M R =⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡1000000011000000001000000011000000101000001111000011101000000001. 由关系矩阵可知, r ij +r ji ≤1, 故R 是反对称的; 可计算对应的关系矩阵为:⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡=10000000110000000010000000110000001010000011110000111010000000012R M = M R 由以上矩阵可知R 是传递的. 所以, R 是偏序关系, 即〈A , R 〉是偏序集. 所对应的哈斯图如图所示:极大元：a , f , h ; 极小元：a , b , c , g.48.哈斯图为：(1) 上界12, 24, 36, 下界2; (2) 无上界, 下界2, 4, 6, 12. 49.(1) 哈斯图和关系图如图所示:∙ ∙ ∙∙ f c d b ∙ e ∙∙g h a∙∙∙ ∙ ∙ 24 2 4 8 ∙∙612 36 ∙(2) 没有最小元素 最大元素为a ; (3) 极小元为d , e , 极大元为a ;(4) 各子集的上界、下界, 最小上界、最大下界情况如下表:子集 上界 下界 最小上界最大下界{b , c , d } a , c d , c c d {c , d , e } a , c 不存在 c 不存在 {a , b , c }ab , dab50.最大元：9, 极大元：9, 上界：27, 18, 9, 最小上界：9, 最小元：3, 极小元：3, 下界：3, 最大下界：3.51.上界为f , 下界为a , b , 最大上界为f , 最小下界不存在. 52.B 的极大元为19, 极小元为2, 最大元为19, 最小元为2. 53.哈斯图如图所示. 对于集合B : 无最小元素, 最大元素, 下界和最大下界为1, 上界和最小上界不存在, 极大元不存在, 极小元为1.54.(1) 等价关系;(2) 不是等价关系; 因为〈2, 1〉, 〈1, 3〉∈R , 但〈2, 3〉∉R , 即传递性不成立. (3) 等价关系; (4) 等价关系; (5) 等价关系. 55.(1) 等价关系. 因为M R 主对角线上元素全为1, 所以R 是自反的; 又M R 是对称矩阵, 所以关系R 是对称的; 又⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=1101100012R M=M R , 亦即R 2=R , 故R 具有传递性, 所以R ∙∙ ∙∙ a c b d e ∙ ∙ ∙ ∙ 5 13 6 ∙24∙∙ c ∙ ∙ ∙a eb d ∙是等价关系.(2) 不是等价关系. 因为M R不是对称矩阵, 所以关系R不具有对称性, 故R不是等价关系.56.(1) 不是A上等价关系. 因为A×A-R1不再满足自反性. 例如, A={a, b}, R1={〈a, a〉, 〈b, b〉}, 则A×A-R1={〈a, b〉, 〈b, a〉}, 显然A×A-R1不是A上等价关系.(2) 不是A上等价关系. 因为R1-R2不再满足自反性. 例如, A={a, b, c}, R1={〈a, b〉, 〈b, a〉, 〈b, c〉, 〈c, b〉, 〈a, c〉, 〈c, a〉, 〈a, a〉, 〈b, b〉, 〈c, c〉}, R2={〈b, c〉, 〈c, b〉, 〈a, a〉, 〈b, b〉, 〈c, c〉}, 则R1-R2={〈a, b〉, 〈b, a〉, 〈a, c〉, 〈c, a〉}, 显然R1-R2不是A上等价关系.(3) 21R是A上等价关系. (见67题证明)(4) r (R1-R2)不一定是A上等价关系. 例如, (2)中所设R1和R2是集合A上的等价关系, 但r (R1-R2)={〈a, b〉, 〈b, a〉, 〈a, c〉, 〈c, a〉, 〈a, a〉, 〈b, b〉, 〈c, c〉}不是A上等价关系.例如, A={a, b}, R1={〈a, b〉, 〈b, a〉, 〈a, a〉, 〈b, b〉}, R2={〈a, a〉, 〈b, b〉}, 则r (R1-R2)={〈a, b〉, 〈b, a〉, 〈a, a〉, 〈b, b〉}是A上等价关系.(5) 不是A上等价关系, 因为R1 R2不再满足对称性. 例如, A={a, b}, R1={〈a, b〉}, R2={〈b, a〉}, 则R1 R2={〈a, a〉}, 显然R1 R2不是A上等价关系.57.若任取〈x, y〉∈A, 因为|x-y|=|x-y|, 故〈x, y〉R〈x, y〉, 所以R是自反的;任取〈x, y〉,〈u, v〉∈A, 使得〈x, y〉R〈u, v〉, 则|x-y|=|u-v|, 故〈u, v〉 R〈x, y〉, 所以R是对称的;任取〈x, y〉, 〈u, v〉, 〈w, z〉∈A, 使得〈x, y〉R〈u, v〉, 〈u, v〉R〈w, z〉, 则有|x-y|=|u-v |, |u-v| = |w-z|, 从而有|x-y|= |w-z|, 即〈x, y〉R〈w, z〉, 所以R是传递的.综上, R是等价关系.A/R={{〈1, 1〉, 〈2, 2〉, 〈3, 3〉}, {〈1, 2〉, 〈2, 1〉, 〈2, 3〉, 〈3, 2〉, 〈3, 4〉}, {〈1, 3〉, 〈2, 4〉, 〈3, 1〉}, {〈1, 4〉}}.58.(1) 对于任意〈a, b〉∈A, 有a2+b2= a2+b2, 故〈a, b〉R〈a, b〉, 自反性成立.对于任意〈a, b〉∈A, 有a2+b2= a2+b2, 则有〈a, b〉R〈b, a〉, 对称性成立.若任意〈a, b〉, 〈c, d〉, 〈e, f〉∈A, 有〈a, b〉R〈c, d〉, 〈c, d〉R〈e, f〉, 即a2+b2= c2+d 2, c2+d 2= e2+f 2, 故a2+b2= e2+f 2, 则必有〈a, b〉R〈e, f〉, 传递性成立.综上R是A上等价关系.(2)A/R的等价类是以(0, 0)为中心的无穷多个同心圆, 包括半径为0的圆.59.(1) 由关系矩阵可知: 对角线元素全为1, 故R自反性成立; M R是对称矩阵, 故R是对称的; 又因为因为对于任意的a ij = 1, a jk = 1, 有a ik = 1, 故R传递性成立.综上R是等价关系.(2) 由等价关系可得其等价类为：[1]R= [2]R = [3]R =[5]R ={1, 2, 3, 5}, [4]R ={4}, 故A/R={{1, 2, 3, 5}, {4}}.(1)A上最大的等价关系是全域关系R=A×A={〈a, b〉 | a, b∈A}, 因此有n2个元素在A 上的最大的等价关系R中, 因为所有n2个二元组都在R=A×A中.(2) A上的最大的等价关系R的秩是1. 这是因为A中任何两个元素都有全域关系R= A×A, 因此R的等价块包含了A的所有元素, 即A的所有元素都在同一个等价块中. 所以商集只有一个等价块{A}, 它包含了A的所有元素.(3) A上的最小的等价关系是恒等关系I A={〈a, a〉 | a∈A }, 它中有n个元素, 即n个自反对.(4) A上的最小的等价关系的商集包含n个元素, 因为恒等关系的每一个元素都自成一个等价块, 每一等价块中也只有一个元素.61.等价关系R的等价类为[1]=[5]={1, 5}, [2]=[4]={2, 4}, [3]=[6]={3, 6}, 故R诱导的划分π={{1, 5}, {2, 4}, {3, 6}}.62.(1) 不是划分; 因为A≠{1, 3, 6}∪{2, 8, 10}∪{4, 5, 7}.(2) 不是划分; 因为{1, 5, 7}∩{3, 5, 6, 10}={5}≠∅.(3) 是划分, 它诱导的等价关系为：R={1, 2, 7}⨯{1, 2, 7}∪{3, 5, 10}⨯{3, 5, 10}∪{4, 6, 8}⨯{4, 6, 8}∪{9}⨯{9}={〈1, 1〉, 〈1, 2〉, 〈1, 7〉, 〈2, 1〉, 〈2, 2〉, 〈2, 7〉, 〈7, 1〉, 〈7, 2〉, 〈7, 7〉, 〈3, 3〉, 〈3, 5〉, 〈3, 10〉, 〈5, 3〉, 〈5, 5〉, 〈5, 10〉, 〈10, 3〉, 〈10, 5〉, 〈10, 10〉, 〈4, 4〉, 〈4, 6〉, 〈4, 8〉, 〈6, 4〉, 〈6, 6〉, 〈6, 8〉, 〈8, 4〉, 〈8, 6〉, 〈8, 8〉, 〈9, 9〉}.(4) 是划分, 它诱导的等价关系为：R={1, 2, 5}⨯{1, 2, 5}∪{3, 4}⨯{3, 4}∪{6, 7, 8}⨯{6, 7, 8}∪{9, 10}⨯{9, 10}={〈1, 1〉, 〈1, 2〉, 〈1, 5〉, 〈2, 1〉, 〈2, 2〉, 〈2, 5〉, 〈5, 1〉, 〈5, 2〉, 〈5, 5〉, 〈3, 3〉, 〈3, 4〉, 〈4, 3〉, 〈4, 4〉, 〈6, 6〉, 〈6, 7〉, 〈6, 8〉, 〈7, 6〉, 〈7, 7〉, 〈7, 8〉, 〈9, 9〉, 〈9, 10〉, 〈10, 9〉, 〈10, 10〉}.63.只要求出A上的全部划分, 即为等价关系.划分为一个块的情况: 1种, 即{a, b, c, d};划分为两个块的情况: 7种, 即{{a, b}, {c, d}}, {{a, c}, {b, d}}, {{a, d}, {b, c}}, {{a}, {b, c, d}}, {{b}, {a, c, d}}, {{c}, {a, b, d}}, {{d},{a, b, c}};划分为三个块的情况: 6种, 即{{a, b}, {c}, {d}}, {{a, c}, {b}, {d}}, {{a, d}, {b}, {c}}, {{a}, {b}, {c, d}}, {{a}, {c}, {b, d}}, {{a}, {d}, {b, c}};划分为四个块的情况: 1种, 即{{a}, {b}, {c}, {d}},因此, 共有15种不同的等价关系.。