当前位置：文档之家 › 离散数学(刘任任版)习题2

离散数学(刘任任版)习题2

  • 格式：ppt
  • 大小：401.50 KB
  • 文档页数：38

下载文档原格式

  / 38

合集下载

湘潭大学刘任任版离散数学课后习题答案习题

湘潭大学刘任任版离散数学课后习题答案习题

习 题 一1. 用列举法表示下列集合：（1）1到100之间的自然数的集合； （2）小于5的正整数集合；（3）偶自然数的集合； （4）奇整数的集合.分析 本题主要考察集合的定义及怎样用列举法表示集合。

解：(1) A ={,,,,},123100 (2) B ={,,,}1234，(3) },8,6,4,2,0{ =C , (4) D =---{,,,,,,,} 531135.2. 用描述法表示下列集合：（1）偶整数的集合；（2）素数的集合；（3）自然数a 的整数幂的集合.分析 本题主要考察集合的定义及怎样用描述法表示集合。

解：(1) }2{整除的整数被是能x x E =(2) }11{数和自身整除的整且只能被是大于x x P =(3) }{是整数是自然数，n a a A n =3. 设},1,4,3},{{},4},3{,,2{a R a S ==请判断下面的写法正确与否：（1）S a ∈}{（2）R a ∈}{ （3）S a ⊆}}3{,4,{（4）R a ⊂}4,3,1},{{ （5）S R =（6）S a ⊆}{ （7）R a ⊆}{（8）R ⊆∅ （9）E R a ⊆⊆⊆∅}}{{（10）S ⊆∅}{ （11）R ∈∅ （12）}4},3{{⊆∅分析 本题主要考察集合的基本运算。

解：(1) 错; (2) 对; (3) 对; (4) 错; (5) 错; (6) 对; (7) 错; (8) 对; (9) 对; (10) 错;(11)错; (12) 对.4. 设A 、B 和C 为任意三个集合. 以下说法是否正确? 若正确则证明之, 否则举反例说明.（1）若B A ∈且C B ⊆，则C A ∈；（2）若B A ∈且C B ⊆，则C A ⊆；（3）若B A ⊆且C B ∈，则C A ∈；（4）若B A ⊆且C B ∈，则C A ⊆分析 本题主要考察集合的基本运算。

解：(1) 正确。

因B C ⊆，所以，对任何x B ∈均有x C ∈，今A B ∈，故A C ∈。

离散数学第2版课后习题答案

离散数学第2版课后习题答案

离散数学第2版课后习题答案离散数学是计算机科学和数学领域中一门重要的学科，它研究离散对象及其关系、结构和运算方法。

离散数学的应用非常广泛，包括计算机科学、信息科学、密码学、人工智能等领域。

而离散数学第2版是一本经典的教材，它系统地介绍了离散数学的基本概念、原理和方法。

本文将为读者提供离散数学第2版课后习题的答案，帮助读者更好地理解和掌握离散数学的知识。

第一章：基本概念和原理1.1 命题逻辑习题1：命题逻辑的基本符号有哪些？它们的含义是什么？答：命题逻辑的基本符号包括命题变量、命题联结词和括号。

命题变量用字母表示，代表一个命题。

命题联结词包括否定、合取、析取、条件和双条件等，分别表示“非”、“与”、“或”、“如果...则...”和“当且仅当”。

括号用于改变命题联结词的优先级。

习题2：列举命题逻辑的基本定律。

答：命题逻辑的基本定律包括德摩根定律、分配律、结合律、交换律、吸收律和否定律等。

1.2 集合论习题1：什么是集合？集合的基本运算有哪些？答：集合是由一些确定的对象组成的整体，这些对象称为集合的元素。

集合的基本运算包括并、交、差和补等。

习题2：列举集合的基本定律。

答：集合的基本定律包括幂等律、交换律、结合律、分配律、吸收律和德摩根定律等。

第二章：数理逻辑2.1 命题逻辑的推理习题1：什么是命题逻辑的推理规则？列举几个常用的推理规则。

答：命题逻辑的推理规则是用来推导命题的逻辑规则。

常用的推理规则包括假言推理、拒取推理、假言三段论和析取三段论等。

习题2：使用推理规则证明以下命题：如果A成立，则B成立；B不成立，则A不成立。

答：假言推理规则可以用来证明该命题。

根据假言推理规则，如果A成立，则B成立。

又根据假言推理规则，如果B不成立，则A不成立。

2.2 谓词逻辑习题1：什么是谓词逻辑？它与命题逻辑有何区别？答：谓词逻辑是一种扩展了命题逻辑的逻辑系统，它引入了谓词和量词。

与命题逻辑不同，谓词逻辑可以对个体进行量化和描述。

离散数学课后习题答案二

离散数学课后习题答案二

习题3.71. 列出关系}6|{=⋅⋅⋅∈><+d c b a d c b a d c b a 且，，，，，，Z 中所有有序4元组。

解 }6|{=⋅⋅⋅∈><+d c b a d c b a d c b a 且，，，，，，Z,2,1,3,1,3,1,2,1,2,3,1,1,3,2,1,1,1,1,1,6,1,1,6,1,1,6,1,1,6,1,1,1{><><><><><><><><=><><><><><><><><2,1,1,3,3,1,1,2,1,2,1,3,1,3,1,2,1,1,2,3,1,1,3,2,1,2,3,1,1,3,2,12. 列出二维表3.18所表示的多元关系中所有5元组。

假设不增加新的5元组，找出二维表3.18所有的主键码。

表3.18 航班信息航空公司 航班 登机口 目的地 起飞时间 Nadir 112 34 底特律 08:10 Acme 221 22 丹佛 08:17 Acme 122 33 安克雷奇 08:22 Acme 323 34 檀香山 08:30 Nadir 199 13 底特律 08:47 Acme 222 22 丹佛 09:10 Nadir 32234底特律09:44解 略3. 当施用投影运算5,3,2π到有序5元组><d c b a ，，，时你能得到什么？解 略4. 哪个投影运算用于除去一个6元组的第一、第二和第四个分量？ 解 略5. 给出分别施用投影运算4,2,1π和选择运算Nadir 航空公司＝σ到二维表3.18以后得到的表。

解对航班信息二维表进行投影运算5,3,2π后得到的二维表航班 登机口 起飞时间 112 34 08:10 221 22 08:17 122 33 08:22 323 34 08:30 199 13 08:47 222 22 09:10 3223409:44对航班信息二维表进行选择运算Nadir 航空公司＝ 后得到的二维表航空公司 航班 登机口 目的地 起飞时间 Nadir 112 34 底特律 08:10 Nadir 199 13 底特律 08:47 Nadir 32234底特律09:446. 把连接运算3J 用到5元组二维表和8元组二维表后所得二维表中有序多元组有多少个分量？解 略7. 构造把连接运算2J 用到二维表3.19和二维表3.20所得到的二维表。

离散数学答案第二章习题解答

离散数学答案第二章习题解答

第二章 谓词逻辑习题与解答1. 将下列命题符号化：(1) 所有的火车都比某些汽车快。

(2) 任何金属都可以溶解在某种液体中。

(3) 至少有一种金属可以溶解在所有液体中。

(4) 每个人都有自己喜欢的职业。

(5) 有些职业是所有的人都喜欢的。

解 (1) 取论域为所有交通工具的集合。

令x x T :)(是火车， x x C :)(是汽车， x y x F :),(比y 跑得快。

“所有的火车都比某些汽车快”可以符号化为))),()(()((y x F y C y x T x ∧∃→∀。

(2) 取论域为所有物质的集合。

令x x M :)(是金属， x x L :)(是液体， x y x D :),(可以溶解在y 中。

“任何金属都可以溶解在某种液体中” 可以符号化为))),()(()((y x D y L y x M x ∧∃→∀。

(3) 论域和谓词与(2)同。

“至少有一种金属可以溶解在所有液体中” 可以符号化为))),()(()((y x D y L y x M x →∀∧∃。

(4) 取论域为所有事物的集合。

令x x M :)(是人， x x J :)(是职业， x y x L :),(喜欢y 。

“每个人都有自己喜欢的职业” 可以符号化为))),()(()((y x L y J y x M x ∧∃→∀(5)论域和谓词与(4)同。

“有些职业是所有的人都喜欢的”可以符号化为))),()(()((x y L y M y x J x →∀∧∃。

2. 取论域为正整数集，用函数+（加法），•（乘法）和谓词<，=将下列命题符号化：(1) 没有既是奇数，又是偶数的正整数。

(2) 任何两个正整数都有最小公倍数。

(3) 没有最大的素数。

(4) 并非所有的素数都不是偶数。

解 先引进一些谓词如下：x y x D :),(能被y 整除，),(y x D 可表示为)(x y v v =•∃。

x x J :)(是奇数，)(x J 可表示为)2(x v v =•⌝∃。

湘潭大学刘任任版离散数学课后习题答案习题

湘潭大学刘任任版离散数学课后习题答案习题

习 题 十 一1．设11≥p ，证明任何p 阶图G 与G 总有一个是不可平面图。

分析： G 与G 是两个互补的图，根据互补的定义，互补的图有相同的顶点数，且G 的边数与G 的边数之和等于完全图的边数p(p-1)/2；而由推论11.2.2，有任何简单平面图G ，其顶点数p 和边数q 满足：q ≤3p-6。

证明. 若),(q p G 与),(q p G ''均是可平面图，则63-≤p q （1） 63-'≤'p q （2） 但q p p q p p --='=')1(21, （3）将（3）代入（2）有63)1(21-≤--p q p p 整理后得 q p p 21272≤+- 又由（1）有)63(21272-≤+-p p p 即 024132≤+-p p也即 224413132244131322⨯-+≤≤⨯--p .得 2731327313+≤≤-p 得112<<p此与11≥p 矛盾。

因此任何p 阶图G 与G 不可能两个都是可平面图，从而G 与G 总有一个是不可平面图。

2．证明或否定：两个p 阶极大简单平面图必同构分析：极大平面图是指添加任何一条边以后不构成平面图的平面图；两个p 阶极大简单平面图不一定同构。

解：令6=p ，三个6阶极大简单平面图321,,G G G 如下：顶点上标的数字表示该顶点的度，但显然不同构.3．找出一个8阶简单平面G ，使得G 也是平面图.分析：由第1题证明过程可知，当p<11时，G 和G 可以同时为平面图。

解：如下平面图G ，显然其补图也是平面图。

123G 3344454．证明或者否定：每个极大平面图是H 图. 分析：极大平面图是指添加任何一条边以后不构成平面图的平面图；而H 图是存在一个H 回路的图，即存在一条经过图中每一个顶点一次且仅一次的回路。

由定理11.1.2知极大平面图的每个面都是三角形，因此G 中必存在回路，利用最长回路的性质使用反证法可证明每个极大平面图都是H 图。

离散数学 习题答案(刘任任)

离散数学 习题答案(刘任任)
此为矛盾。故 A=B。
（2）
A B ( A B) ( A B) ( B A) ( B A) B A
( A B) C (( A B) ( B A)) C (( A B ) ( B A )) C (((A B ) ( B A)) C) (((A B ) ( B A)) C)
A B AC
(4) 错误。例如，令 A={2,3,4},B={1,2,3},C={3,4,5}; (5)错误。例如，令A={2,4},B={1,2},C={2,3};
8.
（1）设A=B。于是
A B ( A B) ( A B) A A 反之，设 A B 。若 A B ，则不妨 设 x A而x B 。于是， x A B, 而x A B 从而 A B
3.
(1) 错; (2) 对; (3) 对; (4) 错;
(5) 错;
(9) 对;
(6) 对;
(10) 错;
(7) 错;
(11)错;
(8) 对;
(12)对.
4.
（1）正确。因BC，所以，对任何x∈B均有x∈C， 令A∈B，故A∈C。 （2）错误。例如，令A={1}，B={{1}，2}， C={{1}，2，3}。
(B×A) 2 =(B × A) ×(A × B) ={<<2,1>,<2,1>>,<<2,1>,<2,2>>,<<2,1>,<3,1 >>,<<2,1>,<3,2>>,<<2,2>,<2,1>>,<<2,2>,< 2,2>>,<<2,2>,<3,1>>,<<2,2>,<3,2>>,<<3,1 >,<2,1>>,<<3,1>,<2,2>>,<<3,1>,<3,1>>,<< 3,1>,<3,2>>,<<3,2><2,1>>,<<3,2>,<2,2>>, <<3,2>,<3,1>>,<<3,2>,<3,2>>}

离散数学2_2


定义2-5、2 给定任意谓词公式wffA,其个体域
为E，对于A的所有赋值，wffA都为真，则称
wffA在E上是有效的（或永真的）。
定义2-5、3 一个谓词公式wffA，如果在所有
赋值下都为假，则称该wffA为不可满足的。
定义2-5、4 一个谓词公式wffA，如果至少在
一种赋值下为真，则称该wffA为可满足的。
（x）（A（x）∨B（x））
2）左边写成“有的人既喜欢打牌又喜欢下棋”，右 边写为“有的人喜欢打牌并且有的人喜欢下棋” 所以：左边可以推出右边，反之不成立 即：（x）（A（x）∧B（x）） （x）A（x）∧（x）B（x）
另外，如果将A（x）和B（x）看成是它们各自 的否定，则由上面的蕴含式可以得到 ：
y既是约束出现又是自由出现，z是自由出 现。
d)∀x(P(x)⋀∃xQ(x,z)→∃yR(x,y))⋁ Q(x,y) 解:(∀x)的作用域是
(P(x)⋀(∃x)Q(x,z)→(∃y)R(x,y)) ，其中， x 和y都是约束变元，z是自由变元，但 Q（x,z）中的x是受∃x的约束，而不是受 ∀ x 的约束。最后的 Q(x,y) 中的 x,y 是自由 变元。
即：量词在前件上，不能随意添加或去除括号
（B→(∀x)A(x) ) ⇔(∀x)（B→A(x)）
（B→(∃x)A(x) ) ⇔(∃x)（B→A(x)）
即：量词在后件上，可以添加或去除括号
（4）量词作用域的扩张与收缩
量词与命题联结词之间存在着不同的结合
情况，下面举例说明一些等价公式。
例如：联欢会上所有人既唱歌又跳舞和联
（3）量词作用域的扩张与收缩
量词的作用域中，常有合取或析取项，
如果其中为一个命题，则可将该命题移至量

湘潭大学计算机科学与技术刘任任版离散数学课后习题答案---第三学期--代数结构

习题十六（整 数）1. 请推导出本节定理16.1.3中计算k S 和k T 的递推公式.分析：本题主要是考察矩阵的推导过程。

解：由（P154）T V S U q q q k k kk k ⎛⎝ ⎫⎭⎪=⎛⎝ ⎫⎭⎪⎛⎝ ⎫⎭⎪⎛⎝ ⎫⎭⎪121101101101 () 有T V S U T V S U q q T V T q S U S k k k k k k k k k k k k k k k k k ⎛⎝ ⎫⎭⎪=⎛⎝ ⎫⎭⎪⎛⎝ ⎫⎭⎪=++⎛⎝ ⎫⎭⎪----------11111111111102 ()比较(2)式两端，可知U S V T T q T V S q S U k k k k k k k k kk k k ==⎧⎨⎩=+=+⎧⎨⎩------11111134 ()() 由(3)有U S V T k k k k ----==⎧⎨⎩1212 (5) 由(4)和(5)得S q S S T q T T k k k k k k k k =+=+⎧⎨⎩----12126 () 由(3)可令S U T V 01017==⎧⎨⎩ () 又由(1)有T V S U q 11111110⎛⎝ ⎫⎭⎪=⎛⎝ ⎫⎭⎪ 于是 S U T V S T q 0101111011====⎧⎨⎩==⎧⎨⎩ 这样，对任意k ≥2， 由(6)可求出S k 和 T k 。

2. 求1331和5709的最大公因数，并表为它们的倍数之和.分析：本题主要是考察用辗转相除法来求两个数的最大公因数。

解：用辗转相除法求最大公因数，逐次得出商及余数并计算S k 和T k 。

今列表如下： k 0 1 2 3 4 5 r k 385 176 33 11 0 q k 4 3 2 5 3S k 0 1 3 7 38 空T k 1 4 13 30 163 空 由上表知，最大公因数为 r 411=, 且有r S T 44144415709113313857091631331=-⋅+-⋅=-⨯+⨯-()() 3. 求证：任意奇数的平方减1必是8的倍数.分析：本题首先根据奇数的概念，然后进行变形即得。

《离散数学》考试题库及答案(二)

《离散数学》考试题库及答案试卷五试题与答案一、填空15%（每空3分）1、设G 为9阶无向图，每个结点度数不是5就是6，则G 中至少有 个5度结点。

2、n 阶完全图，K n 的点数X (K n ) = 。

3、有向图 中从v 1到v 2长度为2的通路有 条。

4、设[R ，+，·]是代数系统，如果①[R ，+]是交换群 ②[R ，·]是半群③ 则称[R ，+，·]为环。

5、设],,[⊕⊗L 是代数系统，则],,[⊕⊗L 满足幂等律，即对L a ∈∀有 。

二、选择15%（每小题3分）1、 下面四组数能构成无向简单图的度数列的有（ ）。

A 、（2，2，2，2，2）； B 、（1，1，2，2，3）； C 、（1，1，2，2，2）； D 、（0，1，3，3，3）。

2、 下图中是哈密顿图的为（ ）。

3、 如果一个有向图D 是强连通图，则D 是欧拉图，这个命题的真值为（ ）A 、真；B 、假。

4、 下列偏序集（ ）能构成格。

5、 设}4,41,3,31,2,21,1{=s ，*为普通乘法，则[S ，*]是（）。

A 、代数系统；B 、半群；C 、群；D 、都不是。

三、证明 48%1、（10%）在至少有2个人的人群中，至少有2 个人，他们有相同的朋友数。

2、（8%）若图G 中恰有两个奇数度顶点，则这两个顶点是连通的。

3、（8%）证明在6个结点12条边的连通平面简单图中， 每个面的面数都是3。

4、（10%）证明循环群的同态像必是循环群。

5、（12%）设]1,0,,,,[-+⨯B 是布尔代数，定义运算*为)()(*b a b a b a ⨯+⨯=，求证[B ，*]是阿贝尔群。

四、计算22%1、在二叉树中1） 求带权为2，3，5，7，8的最优二叉树T 。

（5分） 2） 求T 对应的二元前缀码。

（5分）2、 下图所示带权图中最优投递路线并求出投递路线长度（邮局在D 点）。

答案：一、填空（15%）每空3 分1、 6；2、n ；3、2；4、+对·分配且·对+分配均成立；5、a a a a a a =⊕=⊗且。

离散数学(刘任任版)第2章答案

(4) 反对称关系矩阵 M R (rij )nn 的元素满足： 当i≠j 时 ， rij rji 0 。
而关系图中任何两个结点之间的有向弧是单向的。 （即若关系R是反对称的，当且仅当关系矩阵中 以对角线对称的元素不能同时为1，在关系图上 任两个结点的定向弧线不可能成对出现）
5.
R·S={<1,4>,<1,3>},S·R={<3,4>}; R 2={<1,1>,<1,2>,<1,4>}; S 2={<2,2>,<3,4>,<3,3>}.
β(A×A-{<x,x>})=2n2-n
(4)共有2n 2n(n1)/ 2 2n(n1)/ 2 种定义在A上
的不同的对称关系; 说明: ∵A上的对称关系必须满足：如果<x,y>在
这个关系中，则<y,x>也必须在这个关系中。 ∴在构造A上的对称关系的时候可以先将所有 的<x,y>和<y,x>（其中x≠y）看成是一个整体。 ∴要考虑的序偶的个数有：
s(R1) s(R2 ) (R1 R11) (R2 R21)任取 x, y s(R1 R2 ) (R1 R2 ) (R1 R2 )1 (i)若 x,y (R1 R2 ),
则 x, y R1 R1 R11,且 x, y R2 R2 R21,从而 x,y (R1 R11) (R2 R21)
14.
证明 S {Ai Bj | Ai Bj } (1)由S定义知, Ai Bj (2)任取Ai Bi S和Al Bm S, 1 i, j r,1 j, m s ( Ai Bj ) ( Al Bm ) ( Ai Am ) (Bj Bm )
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

12.
设R1 R2, 则显然A / R1 A / R2 反之, 设A / R1 A / R2 若R1 R2, 则不妨设 x, y R1 但 x, y R2 于是[ x]R1 [ y]R1 ,[ x]R2 [ y]R2 由划分之定义得知 A / R1 A / R2 , 矛盾 故R1 R 2
(4). 令A={1,2,3},R={<1,2>,<2,1>,<1,3>}, 于是R既不是对称又不是反对称的。
3.
设|A|=n，于是 2 n (1)共有 2 种定义在A上的不同的二元关系； 2 n (2)共有 2 n种定义在A上的不同的自反关系； (3)共有 n2 n 种定义在A上的不同的反自反关 系； 2 (4)共有 n n ( n1) / 2 种定义在 A 上的 n ( n 1) / 2 2 2 不同的对称关系 ; 2 (5)共有 n m k 种定义在 A 上的不同 mk 2 C 2 其中， m 的反对称， 。
（3）证明：因为
2 t ( R1 ) R1 R12 ,t ( R2 ) R2 R2 ,
t ( R1 R2 ) ( R1 R2 ) ( R1 R2 )2 , 2 2 于是t ( R1 ) t ( R2 ) ( R1 R1 ) ( R2 R2 ) ( Rl1 R m 2 )
13.
设R { y, x | x y(mod5)},于是
[0]R {... 15,10,5,0,5,10,15...} [1]R {... 14,9,4,1,6,11,16...} [ 2]R {... 13,8,3,2,7,12,17...} [3]R {... 12,7,2,3,8,13,18...} [ 4]R {... 11,6,1,4,9,14,19...} A / B {[ 0]R, [1]R , [ 2]R, [3]R , [ 4]R}
1
设A {1,2},R1 { 1,2 },R2 { 2,1 }, 于是, 1 s( R1 R2 ) ( R1 R2 ) ( R1 R2 ) 1 , 而 1 s(R1 ) R1 R1 { 1,2 , 2,1 }, 1 s(R2 ) R2 R2 { 1,2 , 2,1 } 因此, s( R1 ) s( R2 ) { 1,2 , 2,1 }, 故s( R1 R2 ) s( R1 ) s( R2 )
(3)错误。例如，设对称关系 R={<x,z>,<z,x>},S={<z,y>,<y,z>}。 于是 x, y R S 但 y,x R S
故R· S不是对称的。
(4) 错误。例如，设反对称关系 R={<x,z>,<y,w>},S={<z,y>,<w,x>},x≠y。 于是，<x,y>,<y,x>∈R· S。故R· S不是反 对称的。 (5) 错误。例如，设传递关系 R={<x,w>,<y,v>},S={<w,y>,<v,z>},w≠v。 于是，x(R· S)y，y(R· S)z，但因为w ≠v， 所以，<x,z>∈R· S。
1
(ii)若 x, y ( R1 R2 ) , 则 y,x ( R1 R2 ),即
y,x R1 ,且 y,x R2 , 从而, 1 1 x, y R1 R1 R1 , 且, 1 1 x, y R2 R2 R2 , 于是, 1 1 x, y ( R1 R1 ) ( R2 R2 ) s( R1 ) s( R2 ) 故s( R1 R2 ) s( R1 ) s( R2 ). 举例说明 " "成立 :
11.
设R是等价关系。若<x,y>,<x,z>∈R，则由 R的对称性知, <y,x> ∈R。再由R的传递 性有<y, z>∈R。 反之, 假设只要<x, y>, <x, z> ∈R，就有<y, z>∈R。 (1)对称性。 设< x, y >∈R，由自反性有 <x, x>∈R。于是<y, x>∈R。 (2)传递性。 设<x, y>, <y, z>∈R。 由对 称性有<y, x>∈R, 再由假设有<x, z>∈R。
8.
(1)r ( R1 R2 ) ( R1 R2 ) ( R1 R2 ) 0 0 (R1 R2 ) (R1 R2 ) 0 0 (R1 R1 ) (R2 R2 ) r ( R1 ) r ( R2 )
0
(2)s( R1 R2 ) ( R1 R2 ) ( R1 R2 ) 1 1 (R1 R2 ) (R1 R2 ) 1 1 (R1 R1 ) (R2 R2 ) s( R1 ) s( R2 )
又(S T ) P ,S P { 1,1 }, T P { 3,1 , 1,1 } 因此(S P) (T P) { 1,1 } 从而(S T ) P (S P) (T P)
7.
(1) 正确。因为对任意 x∈A，有xRx，xSx,所以 x(R· S)x。故R· S是自反的。 (2) 错误。例如，设 x,y∈A， x≠y, 且 xRy ， ySx ， 于是x(R · S)x。故R · S不是反自反的。
l , m 1
所以也有 x, y Ri 2就有 x, y Ri 1 Ri 2，即（R1 R2 )i Ri 1 Ri 2，
又设A {1,2,3}, R1 { 1, 2 , 2, 3 }, R2 { 1,3 }, 于是,
R1 R2 , t ( R1 R2 ) , 而, t ( R1 ) { 1,2 , 2,3 , 1,3 },
习题二
1.
(1). R={<1,1>,<1,3>,<3,1>,<3,3>}
(2). R={<1,0>,<2,1>,<4,2>,<8,3>}
2.
设R是定义在集合A上的二元关系。 (1). 相等关系. (2). 令A={1，2}，R={<1，1>}，于是R既 不是自反又不是反自反的； (3). 令A={1，2}，R={<1,1>,<2,2>},于是R 既是对称又是反对称的；
0
设R1和R2是集合A上的二元关系。注意到
0 1 0
(2)s( R1 R2 ) ( R1 R2 ) ( R1 R2 ) 1 1 s( R1 ) R1 R1 , s( R2 ) R2 R2 1 1 s(R1 ) s(R2 ) (R1 R1 ) (R2 R2 )任取 1 x, y s( R1 R2 ) ( R1 R2 ) ( R1 R2 ) (i)若 x, y ( R1 R2 ), 1 则 x, y R1 R1 R1 , 且 1 x, y R2 R2 R2 , 从而 1 1 x, y ( R1 R1 ) ( R2 R2 ) s( R1 ) s( R2 )
k 0
n( n 1) m 2
4.
(1) 自反关系矩阵的主对角线上元素全为 1； 而关系图中每个结点上都有圈。 (2) 反自反关系矩阵的主对角线上元素全为0; 而关系图中每个结点上均无圈。 (3) 对称关系矩阵为对称矩阵; 而关系图中任 何两个结点之间的有向弧是成对出现的, 方 向相反。
(4)反对称关系矩阵 M R (rij ) nn的元素满足： 当i≠j 时 ， 。
2
x,z1 R1 R1 R2 , z1 ,z2 R1 R1 R2 ,, zn1,zn R1 R1 R2 , zn , y R1 R1 R2
从而 x, y ( R1 R2 )
n
举例说明“ ” 1,2 },R2 { 2,3 }于是
rij rji 0
5.
R· S={<1,4>,<1,3>},S· R={<3,4>}; R 2={<1,1>,<1,2>,<1,4>}; S 2={<2,2>,<3,4>,<3,3>}.
6.
设 R={<3,1>,<3,2>},T={<1,3>,<3,2>},S={<1,2 >,<2,3>},P={<2,1>,<3,1>},
t ( R1 R2 ) { 1,2 , 1,3 , 2,3 } t ( R1 ) t ( R2 ) { 1,2 , 1,3 }
9.
R R2 (R1 R2 ) ，于是 0 (1)r ( R1 R2 ) ( R1 R2 ) ( R1 R2 ) 0 ( R1 R2 ) R1 0 0 ( R1 R1 ) ( R2 R1 ) 0 0 (R1 R1 ) (R2 R2 ) r ( R1) r ( R2)
1
(3)由定义，
t ( R1 ) R1 R ,t ( R2 ) R2 R ,
2 1 2 2
t ( R1 R2 ) ( R1 R2 ) ( R1 R2 ) , 2 2 于是t (R1 ) t ( R2 ) R1 R1 R2 R2 2 2 ( R1 R2 ) ( R1 R2 ) n n 下证对任意 n 1有R1 R2 (R1 R2 )n n n n 任取 x, y R1 R2 不妨设 x, y R1 于是存在 z1, z2 , zn A, 使得