习题2
本章目录 · 1 节
本章导读
本章习题按教材2.1—2.50保留顺序。下列解答中,复合均按“先左后右”的右复合约定;关系矩阵按题目所列底集顺序排列,行表示起点、列表示终点。图上的未标记交点不是顶点。证明题不仅验证性质,还说明所用条件。
【习题2.1】设 ,求 。
解:令 ,则 ,。答案是 ,共8对。这里 与包含 的集合 不能混淆。
【习题2.2】若 ,是否一定有 ?
解:不一定。当 时,两个积均为空,前提成立而结论不成立。补充 后结论成立:固定 ,任取 ,由 得 。
【习题2.3】证明 ;判断 与 是否恒成立。
解:第一式两侧的成员条件均是 ,故相等。后两式均不恒成立。并式取 ,左侧有 ,右侧没有。差式取 ,左侧为空,右侧为 。积属于差集只要求“不同时属于两个被减条件”,不要求两个条件都失败。
【习题2.4】判断:(1);(2);(3)存在 使 ;(4)。
解:(1)假,取 ,左侧元素是空集,右侧元素是有序对,两者不同。(2)真,由成员条件 证明。(3)真,取空集即可。(4)假,取 ;左侧为 ,右侧为 ,有序对不是空集。
【习题2.5】证明: 蕴含 。
解:任意 ,对角对 ,所以 ;反向同理。该证明也涵盖空集情形,无需额外假定非空。
【习题2.6】列出从 到 的全部关系。
解:积有两对,全部关系为 、、、,共 个。
【习题2.7】列出 上的 ,其中后两者为通常小于等于关系和整除关系。
解:,(全部9对);,。
【习题2.8】求 上的包含关系。
解:依次把四个元素记作 ,它们满足 。所求关系为 ,共10对。这里比较的是四个集合的包含关系,不是把它们各自展开成新的底集。
【习题2.9】在 上分别列出:(1);(2);(3);(4) 为素数所定义的关系。
解:(1),共15对。(2)。(3)。(4)。第四项只限制第二坐标,不要求第一坐标也为素数。
【习题2.10】在 上定义 、,判断指定有序对的归属。(1):;(2):;(3)以全域关系为全集的 :。
解:(1)依次为属于、属于、不属于、不属于;0不在正整数底集中,不能因 就纳入关系。(2)只有 属于。(3)三对均属于整除关系,所以均不属于其补关系。
【习题2.11】设 , 由 定义, 由 定义, 由 定义,记 ,求 。
解:依次为 、、、、。例如第二种关系代入 得 ,还须取 中的整数; 已超过底集所有可能输出。
【习题2.12】,,写矩阵并画关系图。
解:。
【习题2.13】,,求并、交、。
解:并为 ,交为 ;后面七个集合依次为 、、、、、、。域要同时收集第一、第二坐标。
【习题2.14】,求 。
解:;逆关系将原来的六对逐对交换坐标,得到 ;限制为原关系去掉 ;像为 。
【习题2.15】,求 。
解:记 ,则 ,,,。后五项依次为 、、、、。空集的像为空集,与含空集的单元素集不同。
【习题2.16】,,,求 。
解:依次为 、、、。最后一项的 也必须计入。
【习题2.17】在 上给出不同的 ,使 。
解:可取 。若希望两者均非空,也可取 和 ;恒等步骤不改变有序对,全域关系的任意一对均能通过底集中的中间元素实现两步连接。
【习题2.18】证明定理2.3.4的(1)、(2)、(4)。
解:对第一项, 当且仅当存在 ,有 且 或 ,等价于 或 。第二项同理,把第一步的 分成两种可能,即得 。第四项中,若 ,存在同一个 使 ,故分别属于 ,得到包含关系。反向不成立的原因是右侧可使用不同的中间元素。
【习题2.19】证明定理2.3.5的(2)、(3)。
解:限制对交分配: 当且仅当 ,即该对同时属于两个限制。像对并分配: 当且仅当存在 使 ,可按 或 分类,恰得到 。两式都来自定义,不能把像对交的单向包含擅自改为等式。
【习题2.20】证明 、。
解:把有序对两坐标交换,分别将条件“属于至少一个关系”和“同时属于两个关系”保留不变。逐对写出 属于左侧当且仅当 满足相应并、交条件,即得到两式的双向包含。
【习题2.21】, 当且仅当 ,判断五种性质。
解:不自反,因为 不成立;不反自反,因为 成立;对称,因为加法交换;不反对称,因为 和 且两数不同;不传递,因为 却无 。注意10没有任何对应的第二元素,并不因此退出底集。
【习题2.22】,,画图并判断性质。
解:反自反、反对称、传递;不自反、不对称。需要检查的两步路径为 和 ,它们要求的 已有。没有任何双向不同点,故反对称成立。
【习题2.23】底集 ,对教材图中的12个关系分别写出关系矩阵,并判断自反、反自反、对称、反对称、传递五种性质。
解:各图均按1、2、3的顺序给出矩阵;五种性质互相独立,特别“对称”与“反对称”不是简单的互斥选项。
(a)。成立:自反;不成立:反自反、对称、反对称、传递。
(b)。成立:无;不成立:自反、反自反、对称、反对称、传递。
(c)。成立:自反、对称、传递;不成立:反自反、反对称。
(d)。成立:自反、传递;不成立:反自反、对称、反对称。
(e)。成立:无;不成立:自反、反自反、对称、反对称、传递。
(f)。成立:对称;不成立:自反、反自反、反对称、传递。
(g)。成立:自反、反对称;不成立:反自反、对称、传递。
(h)。成立:自反、对称;不成立:反自反、反对称、传递。
(i)。成立:对称;不成立:自反、反自反、反对称、传递。
(j)。成立:反对称;不成立:自反、反自反、对称、传递。
(k)。成立:自反、反对称、传递;不成立:反自反、对称。
(l)。成立:反对称;不成立:自反、反自反、对称、传递。
【习题2.24】对表2.4.2中保持性质的结论给出证明,不保持的结论给出反例。
解:交保持五种性质。自反由共同保留全部对角项得到;反自反由无对角项得到;对称由交中的对在两个关系中都可反向得到;反对称由任一原关系排除不同点的双向对得到;传递由两步均在两个关系中,故传递推出的对也在两个关系中得到。并保持自反、反自反和对称:对角项的存在或不存在及边的反向均可直接检查。差保持反自反和反对称,因为它是第一个关系的子关系;差保持对称,因为若某对保留而反向被第二个对称关系删去,则原对也应被删去,矛盾。两个自反关系的复合自反:每个 可经 衔接自身。
下列反例覆盖表中其余全部不保持项:
并不保持反对称:在底集 上取 ,运算后为 ,可直接验证原关系均有该性质,而结果没有。
并不保持传递:在底集 上取 ,运算后为 ,可直接验证原关系均有该性质,而结果没有。
差不保持传递:在底集 上取 ,运算后为 ,可直接验证原关系均有该性质,而结果没有。
差不保持自反:在底集 上取 ,运算后为 ,可直接验证原关系均有该性质,而结果没有。
右复合不保持对称:在底集 上取 ,运算后为 ,可直接验证原关系均有该性质,而结果没有。
右复合不保持反自反:在底集 上取 ,运算后为 ,可直接验证原关系均有该性质,而结果没有。
右复合不保持反对称:在底集 上取 ,运算后为 ,可直接验证原关系均有该性质,而结果没有。
右复合不保持传递:在底集 上取 ,运算后为 ,可直接验证原关系均有该性质,而结果没有。
【习题2.25】由教材关系图求三种闭包的关系图。
解:原关系为 。各闭包严格按同一个底集补边,不删除原边。
有序对集合为 。
有序对集合为 。
有序对集合为 。
有序对集合为 。
【习题2.26】,由教材关系图求 。
解:。
。
。
。
。
。
【习题2.27】证明定理2.5.1的(2),即对称闭包公式。
解: 包含 ,并有 ,所以对称。任意对称且包含 的关系 必包含 ,从而 。同时具备性质、包含和最小性,故 。
【习题2.28】证明定理2.5.2的(2)、(3)。
解:若 对称,则 ,由公式得 ;若 ,因闭包对称, 也对称。若 传递,归纳得全部正次幂均包含于 ,而 是其中第一项,故 ;反向由传递闭包本身传递立即得到。
【习题2.29】证明定理2.5.3,即三种闭包的单调性。
解:若 ,取逆仍保持包含,并上相同的 也保持包含,分别得自反、对称闭包结论。对传递闭包,任意 中的有限路径也是 中的路径,故 对全部正整数成立,再取并即得 。
【习题2.30】证明定理2.5.4的(1)、(3)。
解:(1)若 自反,,而 ,故两个闭包仍包含全部对角项。(3)若 传递,考察 ,故 传递。新增的恒等步骤不会产生新的不同起终点要求。
【习题2.31】 上等价关系的等价类为 、,求 。
解:,共10对。等价关系对称,故 ;又因自反和传递,,所以后两项均等于 。
【习题2.32】判断以下关系是否等价:(1)实数上 ;(2) 上 ;(3)正整数上 为奇数;(4) 上 或 ,其中 ;(5) 上 ,其中固定 。
解:(1)否,不自反且不对称。(2)否,,但 不成立,传递性失败。(3)否,偶数与自身的乘积为偶数,所以不自反。(4)否,取不同 ,有 ,但两个单元素集不可比。(5)是,条件等价于 ,即只忽略 内的差异;集合相等的自反、对称和传递性立即给出三种性质。也可用 证明传递。
【习题2.33】,,画图并求等价类。
解:,,商集为 。
【习题2.34】判断以下集族是否划分正整数集:(1)素数集合与其补集组成的两块;(2)全部单元素集 。
解:两者都是划分。第一项的素数块和非素数块都非空、互不相交并覆盖全部正整数;1属于非素数块。第二项每个正整数恰在自己的单元素块中。
【习题2.35】对非空 ,全部非空子集 是否构成 的划分?
解:当且仅当 只有一个元素时是划分。若至少有两个不同元素 ,则 与 是不同非空子集但相交,不满足划分条件。若 ,集族仅含块 ,满足全部条件。
【习题2.36】,在 上规定 当且仅当 。证明等价并给出划分。
解:条件等价于 ,即按两坐标之差分类,所以三种性质来自数值相等。全部类为 ,。依次为 、、、、、、,共覆盖16对。
【习题2.37】,,令 ,求其矩阵和商集。
解:加自环、反向边并补齐传递关系后,分量分别为 ,每一分量内为全域关系,不同分量间无关系。
商集为 。这里星号按本题指定表示等价闭包,不能未经说明改解释成另一种闭包。
【习题2.38】 自反且传递,证明 等价。
解:交仍含全部自环,故自反;取逆得到自身,故对称;若 ,则 ,由传递性得 ,从而 。
【习题2.39】 自反,证明它等价当且仅当“ 且 蕴含 ”。
解:必要性用对称性将 变成 ,再与 传递。充分性中,若 ,又有 ,代入条件得 ,所以对称;若 ,先用对称得 ,再在共同起点 下应用条件,得到 ,所以传递。自反性由前提给出,三项齐全。
【习题2.40】在 上, 当且仅当 ,证明等价并求商集。
解:按第二坐标相等分类,故等价。每个类为 ,商集为 。本书自然数包含0,因此也有第二坐标为0的类。
【习题2.41】,在 上规定 当且仅当 ,证明等价并求划分。
解:按坐标和相等分类,故等价。全部类为 ,;各类大小依次为1、2、3、4、3、2、1,共16对。这里与2.36按差分类不同;例如 。
【习题2.42】 自反且传递,定义 当且仅当 且 ,证明 等价。
解:这正是2.38的 。自反来自 ;交换 不改变定义,故对称;两条相反方向的两步路径分别用 的传递性合成,即得 。
【习题2.43】画整除偏序的哈斯图:(1);(2)。
解:
覆盖对为 。所有自反、传递有序对省画,但仍属于关系。
覆盖对为 。所有自反、传递有序对省画,但仍属于关系。
【习题2.44】对教材三个哈斯图写出底集和完整偏序关系。
解:完整关系必须在覆盖边外补上自反项及所有传递项。
(a),。
(b),。
(c),。
【习题2.45】对教材两个哈斯图写出底集和完整偏序关系。
解:完整关系必须在覆盖边外补上自反项及所有传递项。
(a),。
(b),。
【习题2.46】画两组偏序的哈斯图,求极大元、极小元、最大元、最小元。(1),;(2),。
解:
极小元为 ,极大元为 ;均无最小元和最大元。
极小元为 ,极大元为 ;均无最小元和最大元。
【习题2.47】 按整除排序,,求 的上下界及确界。
解:,共同倍数在底集中只有12,所以全体上界为 ,上确界为12;共同约数只有1,所以全体下界为 ,下确界为1。12和1均不属于 ,不妨碍它们作为界。不能把通常数值最小的2误作整除顺序的下确界,因为2并不整除3。
【习题2.48】 是偏序集,定义 当且仅当 且 ,证明 是积集上的偏序。
解:两坐标分别用自反性得 自反;若两个方向均成立,则由 的反对称性分别得到 ,从而有序对相等;两步复合时对两坐标分别用传递性,即得 传递。这里是两个坐标同时比较的积偏序,不是字典序。
【习题2.49】偏序 的对偶 定义为 。(1)证明 偏序;(2)说明整数通常 的对偶及正整数整除关系的对偶;(3)说明极值之间的对应。
解:(1)自反不变;若 ,则 ,由反对称得 ;若 ,则 ,由传递得 ,即 。(2)通常 的对偶是 ;整除关系的对偶为 ,即 是 的倍数。(3)同一子集的极大元与极小元互换,最大元与最小元互换;上界与下界、上确界与下确界也互换。
【习题2.50】12个任务的先后约束如教材图,箭头从前驱指向后继,给出一个拓扑排序。
解:一个可行结果为 。对每条箭头逐项检查,其起点在序列中均先于终点。初始入度为0的是 ,因此排序通常不唯一;不能遗漏独立链 ,也不能把 排在 或 前面。
