我的图书馆
&&&& &1、平面图和印刷电路板的设计&&&& &有时候，实际问题要求我们把图画在平面上，使得不是节点的地方不能有边交叉，这在图论中就是判断一个图是否是平面图的问题。&&&&& 像印刷电路板(Printed Circuit Board，PCB)（单层印刷电路板，多层印刷电路板）几乎会出现在每一种电子设备中。PCB的主要功能是提供上头各项零件的相互电气连接。随着电子设备越来越复杂，需要的元件越来越多，PCB上头的导线与元件也越来越密集了。 &&&&& 板子本身的基板是由绝缘隔热、不易弯曲的材料制作而成。在表面可以看到的细小线路材料是铜箔，原本铜箔是覆盖在整个板子上的，而在制造过程中部份被蚀刻处理掉，留下来的部份就变成网状的细小线路了。这些线路被称作导线或布线，并用来提供PCB上元件的电路连接。 &&&& &因此在设计和制造印刷电路板时，首先要解决的问题是判定一个给定的电路图是否能印刷在同一层板上而使民线不发生短路？若可以，怎样给出具体的布线方案？&&&&& 将要印刷的电路图看成是一个无向简单连通图G，其中顶点代表电子元件，边代表导线，于是上述问题归结为判定G是否是平面图？若G是平面图，由怎样给出它的一个平面表示来？&&&&& 平面图的判断问题，在数学上已由波兰数学家库拉托夫斯基(Kuratowski) 于1930年解决。库拉托夫斯基定理给出的充要条件看似简单，但实现起来很难。但是许多研究拓扑图论的数学家提出了比较有效的图的平面性判定的准则，如DMP方法以就是其中的一个有代表性方法。
&&&& &2、图的着色和四色问题&&&& &图的着色起源于“四色问题”。四色问题又称四色猜想，是世界近代三大数学难题之一。&&&&& 四色问题是说画在纸上的每张地图只需要用4种颜色就能使具有共同边界的国家不会有相同的颜色。用数学语言表示，就是将平面任意地细分为不相重迭的区域，每一个区域总可以用1，2，3，4这四个数字之一来标记，而不会使相邻的两个区域得到相同的数字。&&&&& 这里所指的相邻区域，是指有一整段边界是公共的。如果两个区域只相遇于一点或有限多点，就不叫相邻的。因为用相同的颜色给它们着色不会引起混淆。&&&& &四色猜想的提出来自英国。1852年，毕业于伦敦大学的格思里(F.Guthrie)来到一家科研单位搞地图着色工作时，发现了一种有趣的现象：“看来，每幅地图都可以用四种颜色着色，使得有共同边界的国家都着上不同的颜色。”这个现象能不能从数学上加以严格证明呢？他和在大学读书的弟弟格里斯决心试一试。兄弟二人为证明这一问题而使用的稿纸已经堆了一大叠，可是研究工作没有进展。&&&& &日，他的弟弟就这个问题的证明请教了他的老师、著名数学家德?摩尔根(De Morgan)，摩尔根也没有能找到解决这个问题的途径，于是写信向自己的好友、著名数学家汉密尔顿爵士(W.R. Hamilton)请教。汉密尔顿接到摩尔根的信后，对四色问题进行论证。但直到1865年汉密尔顿逝世为止，问题也没有能够解决。&&&&& 起初，这个问题并没有引起数学家们的注意，认为这是一个不证即明的事实。但经过一些尝试之后，发现并不是那么回事。1878年，英国当时最著名的数学家凯利(A. Cayley)正式向伦敦数学学会提出了这个问题，于是四色猜想成了世界数学界关注的问题。世界上许多一流的数学家都纷纷参加了证明四色猜想的大会战。&&&&& 年两年间，著名的律师兼数学家肯普(Kempe)和泰勒(Taylor)两人分别提交了证明四色猜想的论文，宣布证明了四色定理，大家都认为四色猜想从此也就解决了。&&&&& 但是后来人们发现他们都错了。后来，越来越多的数学家虽然对此绞尽脑汁，但一无所获。于是，人们开始认识到，这个貌似容易的题目，其实是一个可与费马大定理相媲美的难题。&&&&& 不过肯普的证明虽然失败了，但它在证明中提供的思想和方法仍然是后来许多数学家冲击四色问题的基础。美国数学家富兰克林于1939年证明了22国以下的地图都可以用四色着色。1950年，有人从22国推进到35国。1960年，有人又证明了39国以下的地图可以只用四种颜色着色；随后又推进到了50国。但是这种推进仍然十分缓慢。&&&&& 电子计算机问世以后，由于演算速度迅速提高，加之人机对话的出现，大大加快了对四色猜想证明的进程。1976年6月，美国伊利诺大学的阿佩尔(Appel)、哈肯(Haken)和柯齐(Koch)三人合作编制了一个程序，在美国伊利诺斯大学的两台不同的电子计算机上，用了1260个小时，作了100多亿次逻辑判断，给出了四色猜想证明，轰动了世界。&&&& &这是一百多年来吸引许多数学家与数学爱好者的大事，当两位数学家将他们的研究成果发表的时候，当地的邮局在当天发出的所有邮件上都加盖了“四色足够”的特制邮戳，以庆祝这一难题获得解决。&&&&& “四色问题”的被证明不仅解决了一个历时100多年的难题，而且成为数学史上一系列新思维的起点。在“四色问题”的研究过程中，不少新的数学理论随之产生，也发展了很多数学计算技巧。如将地图的着色问题化为图论问题，丰富了图论的内容。不仅如此，“四色问题”在有效地设计航空班机日程表、设计计算机的编码程序上都起到了推动作用。&&&&& 不过不少数学家并不满足于计算机取得的成就，他们认为应该有一种简捷明快的书面证明方法。直到现在，仍由不少数学家和数学爱好者在寻找更简洁的证明方法。
&&&&& 3、运输网络&&&&& 自从克希霍夫运用图论从事电路网络的结构分析以来，网络理论的研究和应用就越来越广泛。特别是近几十年来，电路网络、运输网络、通讯网络等与工程和应用密切相关的课题受到了高度的重视。&&&&& 无自回路的有向赋权图称为网络(Network)。在一个网络中，有向边上的权称为容量(Capacity)。网络中入度为0的结点称为源(Source)，用字母s表示；出度为0的结点称为汇(Trap),用字母t表示。&&&&& 在某些问题，只考虑有单一源和单一汇的网络（即运输网络），而在另一些问题中（如通讯网络），根本就不考虑源和汇。&&&& &运输网络的实际意义可以用公路网、铁路网、和供水系统、电网等来说明，也就是“货物从产地s，通过若干中转站，到达目的地t”这类情形的一般模型。这里将源和汇分别看成是货物的产地和目的地，其他结点是中转站，有向边是连接两站的道路（公路、铁路、水管或电线等），容量则是某一段道路允许的通行能力的上限。&&&&& 在运输网络中要考虑的是从源到汇的实际流通量，显然它与每条有向边的容量有关，也和每个结点的转运能力有关。对运输货物来讲，除了容量之外，每条边还被赋予一个非负实数，这一组数若满足以下条件：单位时间内通过每条道路运送的货物总量不能超过道路的容量；每一个中转站的流入量等于流出量；源的流出量等于汇的总流入量（即网络的流量(Discharge)）。则称这组数为该运输网络的一个流(Flow)。&&&&& 一个运输网络中具有可能的最大值的流称为最大流。在一个运输网络中，可能不止一个最大流，即可能有几个不同的流，都具有最大值。&&&&& 给定运输网络求其最大流的问题，就是怎样使给定网络在单位时间运输量最大的问题，并且确定当网络的流量最大时的流。&&&&& 最大流问题的解决显然在现实生活中有很重大的应用价值。
&&&& &4、通讯网络&&&&& 网络应用的另一重要方面是通讯网络，如电话网络、计算机网络、管理信息系统、医疗数据网络、银行数据网络、开关网络等等。这些网络的基本要求是网络中各用户能够快速安全地传递信息，不产生差错和故障，同时使建造和维护网络所需费用低。&&&&& 通讯网络中最重要的整体问题是网络的拓扑结构。根据用途和性能指标的不同要求，通讯网络有不同的拓扑结构，如环形网络、树形网络、星形网络、分布式网络、网状网络及混合型网络等等。通讯网络是一个强连通的有向图。&&&& &除了网络的拓扑结构之外，通讯网络还要考虑流量和控制问题、网络的可靠性等问题。图论中的连通度在通讯网络中有着重要的应用，是大规模互连容错网络可靠性的有效性分析的基础。当然网络的可靠性涉及的因素很多，但是从通讯网络作为一个强连通的有向图来说，一个具有最佳连通性的网络就不易出现阻碍问题。
&&&& &5、二元树的应用----前缀码(哈夫曼编码)&&&& &在通讯系统中，常用二进制来表示字符。但由于字符出现的频率不一样以及为了保密的原因，能否用不等长的二进制数表示不同的字符，使传输的信息所用的总码元尽可能少呢？&&&&& 但是不等长的编码方案给编码和译码带来了困难。为了解决这个问题，我们引入了前缀码（哈夫曼编码）。&&&& &设ab…cd为一个长为n的字符串，则a,ab,…,ab…c分别为它的长为1,2,…,n-1的前缀(Prefix)。&&&& &设A是一个字符串集，若其中的任一字符串都不是其它字符串的前缀，则称A为一个前缀码(哈夫曼编码)(Prefixed Code)。若组成A的字符串的只有字符0和1，则称A为二元前缀码(Binary Prefixed Code)。如{000，001，01，10，110，111}是一个二元前缀码，而{000，001，01，10，11，111}不是一个二元前缀码。&&&&& 那么如何构造一个二元前缀码并用它进行编码和译码呢？&&&&& 我们利用二元树来产生一个二元前缀码：&&&&& 1) 构造一棵二元树，树根的左侧用0标记，右侧用1标记；&&&& &2)分支点v的左侧(右侧)的标记就是标记v的二进制数最右端加上0(1)；&&&& &3)任一片树叶的标记串不是其它树叶的标记串的前缀；&&&& &4)将所有树叶的标记串取来就可构成一个二元前缀码。然后对要发送的信息中的每个字符分别用这个二元前缀码中的字符串代表，当然应该用越长的字符串代表出现频率越最低的字符串。&&&&& 当接收方接到发送方发过去的信息（实际上是二进制位组成的一个序列），他也将按照那棵标记过的二元树来进行译码，还原出真正的信息。过程如下：&&&&& 接收方一边接收一边译码，从第一个接收的二进制位开始，按接收到的是0还是1，分别从当前结点的左子树和右子树往下走。如果遇到一片树叶，说明已得到一个字符的码元。从下一个接收的位开始又从根结点起重复上述过程。&&&& &如我们由一棵二元树得到一个二元前缀码{010(确)，011(实)，11(爱)，10(我)，00(你)}对应的二元树，现将下列二进制串“111100”译码。译码的结果是：10，11，00，10，010，011，11，00。翻译成中文就是“我爱你，我确实爱你。”
TA的推荐TA的最新馆藏[转]&[转]&[转]&[转]&
喜欢该文的人也喜欢当前位置： >>
离散数学习题解答(第四版)清华大学出版社
第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 的真值则具体情况而定，是确定的。 （12） p ? q ，其中， p : 4 是偶数， q : 4 是奇数。由于 q 是假命题，所以，q 为假命题， p ? q 为真命题。 （13）p ? q ， 其中，p : 4 是偶数，q : 4 是奇数， 由于 q 是假命题， 所以，p ? q 为假命题。 （14） p：李明与王华是同学，真值由具体情况而定（是确定的） 。 （15） p：蓝色和黄色可以调配成绿色。这是真命题。 分析 命题的真值是唯一确定的，有些命题的真值我们立即可知，有些则不能马上知道，但它们的真值不会变化，是客观存在的。 1．3 令 p : 2 ? 2 ? 4, q : 3 ? 3 ? 6, 则以下命题分别符号化为 （1） p ? q （2） p ? ?q （3） ?p ? q （4） ?p ? ?q （5） p ? q （6） p ? ?q （7） ?p ? q （8） ?p ? ?q 以上命题中， （1） ， （3） ， （4） ， （5） ， （8）为真命题，其余均为假命题。 分析 本题要求读者记住 p ? q 及 p ? q 的真值情况。 p ? q 为假当且仅当p 为真,q 为假,而 p ? q 为真当且仅当 p 与 q 真值相同.由于 p 与 q 都是真命题， 在 4 个蕴含式中，只有（2） p ? r ，其中，p 同（1） ，r：明天为 3 号。 在这里，当 p 为真时，r 一定为假， p ? r 为假，当 p 为假时，无论 r 为真 还是为假， p ? r 为真。21．5 （1） p ? q ，其中，p：2 是偶数，q：2 是素数。此命题为真命题。 （2） p ? q ，其中，p：小王聪明，q：小王用功 （3） p ? q ，其中，p：天气冷，q：老王来了 （4） p ? q ，其中，p：他吃饭，q：他看电视 （5） p ? q ，其中，p：天下大雨，q：他乘公共汽车上班 （6） p ? q ，其中，p，q 的含义同（5） （7） p ? q ，其中，p，q 的含义同（5） （8） ?p ? ?q ，其中，p：经一事，q：长一智 分析 1°在前 4 个复合命题中，都使用了合取联结词，都符号化为合取式，这正说明合取联结词在使用时是很灵活的。在符号化时，应该注意，不要将联结 词部分放入简单命题中。例如，在（2）中，不能这样写简单命题：p：小王不但 聪明，q：小王而且用功。在（4）中不能这样写：p：他一边吃饭， q ：他一边 看电视。 2° 后 4 个复合命题中，都使用了蕴含联结词，符号化为蕴含式，在这里， 关键问题是要分清蕴含式的前件和后件。p ? q 所表达的基本逻辑关系为，p 是 q 的充公条件，或者说 q 是 p 的必要条件，这种逻辑关系在叙述上也是很灵活的。例如， “因为 p，所以 q” ， “只要 p， 就 q” “p 仅当 q” “只有 q 才 p” “除非 q，否则 ?p ” “没有 q，就没有 p”等都表 达了 q 是 p 的必要条件，因而都符号化为 p ? q 或 ?p ? ?q 的蕴含式。 在（5）中，q 是 p 的必要条件，因而符号化为 p ? q ，而在（6） （7）中， p 成了 q 的必要条件，因而符号化为 q ? p 。 在（8）中，虽然没有出现联结词，但因两个命题的因果关系可知，应该符 号化为蕴含式。 1．6 （1） ， （2）的真值为 0， （3） ， （4）的真值为 1。 分析 1° （1）中公式含 3 个命题变项，因而它应该有 2 3 ? 8 个赋值：000，3001，…，111 题中指派 p, q 为 0, r 为 1，于是就是考查 001 是该公式 p ? (q ? r ) 的成真赋值，还是成假赋值，易知 001 是它的成假赋值。 2° 在公式（2） ， （3） ， （4）中均含 4 个命题就项，因而共有 2 4 ? 16 个赋值： ，…，1111。现在考查 0011 是它的成假赋值。 1.7 （1） ， （2） ， （4） ， （9）均为重言式， （3） ， （7）为矛盾式， （5） ， （6） ，（8） ， （10）为非重言式的可满足式。 一般说来，可用真值表法、等值演算法、主析取范式（主合取范式）法等判 断公式的类型。 （1）对（1）采用两种方法判断它是重言式。 真值表法 表 1.2 给出了（1）中公式的真值表，由于真值表的最后一列全为 1，所以， （1）为重言式。p0 0 0 0 1 1 1 1 等值演算法q0 0 1 1 0 0 1 1r0 1 0 1 0 1 0 1p?q?rp ? ( p ? q ? r)0 1 1 1 1 1 1 11 1 1 1 1 1 1 1p ? ( p ? q ? r)? ?p ? ( p ? p ? r ) ? (?p ? p) ? p ? r ? 1? q ? r?1（蕴含等值式） （结合律） （排中律） （零律）4由最后一步可知， （1）为重言式。 （2）用等值演算法判（2）为重言式。( p ? ?p) ? ?p ? (?p ? ?) ? ?p? ?p ? ?p ? p ? ?p ?1（蕴含等值式） （等幂律） （蕴含等值式） （排中律）（3）用等值演算法判（3）为矛盾式?( p ? q) ? q ? ?( p? ? q) ? q? p ? ?q ? q（蕴含等值式） （德?摩根律） （结合律） （矛盾律） （零律）? p ? (?q ? q) ? p?0?0由最后一步可知， （3）为矛盾式。 （5）用两种方法判（5）为非重言式的可满足式。 真值表法pq?p?p ? qq ? ?p(?p ? q) ? (q ? ?p)0 0 1 10 1 0 11 1 0 00 1 1 11 1 1 01 1 1 0由表 1.3 可知（5）为非重言式的可满足式。 主析取范式法(?p ? q) ? (q ? ?p) ? ( p ? q) ? (?q ? ?p)5? ?( p ? q) ? (?q ? ?p) ? (?p ? ?q) ? ?q ? ?p? ?p ? ?q? (?p ? 1) ? (1 ? ?q) ? (?p ? (?q ? q) ? ((?p ? p) ? ?q) ? (?p ? ?q) ? (?p ? q) ? (?p ? ?q) ? ( p ? ?q) ? (?p ? ?q) ? (?p ? q) ? (?p ? ?q)? m0 ? m1 ? m2 .在（3）的主析取范式中不含全部（4 个）极小项，所以（3）为非重言式的 可满足式，请读者在以上演算每一步的后面，填上所用基本的等值式。 其余各式的类型，请读者自己验证。 分析1? 真值表法判断公式的类别是万能。公式 A 为重言式当且仅当 A 的真值表的最后一旬全为 1；A 为矛盾式当且仅当 A 的真值表的最后一列全为 0；A 为非重言式的可满足式当且仅当 A 的真值表最后一列至少有一个 1，又至少有一 个 0。真值表法不易出错，但当命题变项较多时，真值表的行数较多。2?用等值演算法判断重言式与矛盾式比较方例， A 为重言式当且仅当 A 与1 等值；A 为矛盾式当且仅当 A 与 0 等值，当 A 为非重言式的可满足式时，经过 等值演算可将 A 化简，然后用观察法找到一个成真赋值，再找到一个成假赋值， 就可判断 A 为非重言式的可满足式了。例如，对（6）用等值演算判断它的类型。( p ? ?p) ? q ?0?q ? ( p ? q) ? (q ? 0) ? (?0 ? q) ? (?q ? 0) ? (1 ? q) ? ?q ? 1 ? ?q（矛盾律） （等价等值式） （蕴含等值式） （同一律） （零律）6? ?q（同一律）到最后一步已将公式化得很简单。由此可知，无论 p 取 0 或 1 值，只要 q 取 0 值，原公式取值为 1，即 00 或 10 都为原公式的成真赋值，而 01，11 为成假赋 值，于是公式为非重言式的可满足式。 用主析取范式判断公式的类型也是万能的。A 为重言式当且仅当 A 的主析取 范式含 2 n （ n 为 A 中所含命题变项的个数）个极小项；A 为矛盾式当且仅当 A 的 主析取范式中不含任何极小项，记它的主析取范式为 0；A 为非重言式的可满足 式当且仅当 A 的主析取范式中含极小项，但不是完全的。 当命题变项较多时，用主析取范式法判公式的类型，运算量是很大的。 用主合取范式判断公式的类型也是万能的。A 为重言式当且仅当 A 的主合取 范式中不含任何极大项，此时记 A 的主合取范式为 1；A 为矛盾式当且仅当 A 的 主合取范式含 2 n 个极大项（ n 为 A 中含的命题变项的个数） ；A 为非重言式的可 满足式当且仅当 A 的主析取范式中含含极大项，但不是全部的。 1.8 （1）从左边开始演算( p ? q) ? ( p ? ?q) ? p ? (q ? ?q)（分配律） （排中律） （同一律）? p ?1? p.（2）从右边开始演算p ? (q ? r ) ? ?p ? (q ? r ) ? (?p ? q) ? (?p ? r ) ? ( p ? q) ? ( p ? r ).（蕴含等值式） （分配律） （蕴含等值式）（3）从左边开始演算?( p ? q)7? (( p ? q) ? (q ? p)) ? ?((?p ? q) ? (?p ? q))? ?((?p ? q) ? (?p?) ? (q ? ?q) ? ( p ? q))? ?((?p ? ?q) ? ( p ? q)) ? ( p ? q) ? ?( p ? q).请读者填上每步所用的基本等值式。 本题也可以从右边开始演算( p ? q) ? ?( p ? q) ? ??(( p ? q) ? ?( p ? q) ? ?(?( p ? q) ? ??( p ? q)) ? ?((?p ? ?q) ? ( p ? q)) ? ?((?p ? q) ? (?p ? q) ? (?q ? p) ? (?q ? q)) ? ?(1 ? p ? q) ? (?q ? p) ? 1 ? ?(( p ? q) ? (q ? p)) ? ?( p ? q).读者填上每步所用的基本的等值式。 1.9 （1）?(( p ? q) ? p) ? ?(?( p ? q) ? p ? ?(?( p ? q) ? p)? p ? q ? ?p（蕴含等值式） （德?摩根律） （结合律、交换律） （矛盾式） （零律）8? ( p ? ?p) ? q? 0.由最后一步可知该公式为矛盾式。 （2） (( p ? q) ? (q ? p)) ? ( p ? q)? ?(?( p ? q) ? p)（蕴含等值式）由于较高层次等价号两边的公式相同，因而此公式无成假赋值，所以，它为 重言式。 （3） (?p ? q) ? (q ? ?p)? ( p ? q) ? (?q ? ?p) ? ?( p ? q) ? (?q ? ?p) ? (?p ? q) ? ?q ? ?p? ?q ? ?p ? ?p ? ?q.（蕴含等值式） （蕴含等值式） （德?摩根律） （吸收律）（交换律）由最后一步容易观察到，11 为该公式成假赋值，因而它不是重言式，又 00， 01，10 为成真赋值，因而它不是矛盾式，它是非重言式的可满足式。 1.10 题中给出的 F，G，H，R 都是 2 元真值函数。给出的 5 个联结词集都是全功能集，可以用观察法或等值演算法寻找与真值函数等值的公式。 首先寻找在各联结词集中与 F 等值的公式。 （1）设 A ? ?( p ? q) ，易知 A 是 {?, ?} 中公式且与 F 等值，即 F ? A. （2）设 B ? p ? ?q ，易知 B 是 {?,?} 中公式且与 F 等值，即 F ? B. （3）设 C ? ?(?p ? q) ，易知 C 是 {?,?} 中公式，且 F ? C. （4）设 D ? ( p ? (q ? q)) ? ( p ? (q ? q)) ，易知 D 为 {?} 中公式，且 F ? D. （5）设 E ? ( p ? p) ? q ，易知 E 为 {?} 中公式，且 F ? E. 分析1?只要找到一个联结词集中与 F 等值的公式， 经过等值演算就可以找出其他联结词集中与 F 等值的公式。例如，已知 A ? ?( p ? q) 是 {?, ?} 公式， 且 F ? A 。进行以下演算，就可以找到 F 等值的其他联结词集中的公式。对 A 进行等值演算，消去联结词 ? ，用 ? ， ? 取代，得9A ? ?( p ? q) ? ?(?p ? q)? p ? ?q记为B.则 B 为 {?,?} 中公式，且 F ? B 。再对 A 进行等值演算，消去 ? ，用 ? ， ? 取代，得A ? ?( p ? q)? ?(?p ? q)记为 C.则 C 为 {?,?} 中公式， 且 F ? C 。再对 B 进行演算，消去 ? ，? ，用 ? 取代， 在演算中，注意，对于任意的公式 A，有?A ? ?( A ? A) ? A ? A.B ? p ? ?q? p ? ( q ? q) ? ??( p ? (q ? q)) ? ?( p ? (q ? q))? ( p ? (q ? q)) ? ( p ? (q ? q)记为D.则 D 为 {?} 中公式，且 F ? D. 再对 C 进行演算，消去 ?,?, 用 ? 取代，在演算 中注意，对于任意的公式 A?A ? ?( A ? A) ? A ? A.C ? ?(?p ? q)? ?p ? q? ( p ? p) ? q记为E.则 E 为 {?} 中公式，且 F ? E.2?开始找一个与某真值函数等值的公式的方法，除观察法外，就是根据10该真值函数的真值表，求它的主析取范式，而后进行等值演算即可。例如，由 G 的真值表可知 G 的主析取范式为 m1 ? m3 ，于是G ? m1 ? m3? (?p ? q) ? ( p ? q) ? (?p ? p) ? q? q.由于公式 q 不带联结词，所以，它应该为任何联结词集中的合式公式。3?在各联结词集中找到的与某真值函数等值的公式并不唯一。例如，取A ? ?q ? q. B ? q ? q. C ? q ? q. ({?, ?} 中公式) ({?,?} 中公式) ({?,?} 中公式)D ? (q ? q) ? (q ? q). E ? (q ? q) ? (q ? q).({?} 中公式) ({?} 中公式)则 G ? A ? B ? C ? D ? E, 对于同一个真值函数 G ，找到与它等值的形 式各异的公式。 对于 H 和 R，请读者自己去完成。 1.11 （1）对 C 是否为矛盾式进行讨论。 当 C 不是矛盾式时， A ? C ? B ? C ，则一定有 A ? B ，这是因为，此时，A ? C ? A, B ? C ? B ，所以，有A ? A ? C ? B? ? B必有 A ? B 而当 C 不是矛盾式时， A ? C ? B ? C ，不一定有 A ? B ，举反例如下： 设 A,B,C 均为含命题变项 p, q 的公式，A，B，C 及 A ? C, B ? C 的真值表如表 1.4 所示，从表 1.4 可看出， A ? C ? B ? C ，但 A ? B。 表 1.411p 0 0 1 1q 0 1 0 1A 0 0 1 0B 0 0 1 1C 0 0 1 1AVC 0 0 1 1BVC 0 0 1 1(2) 对 C 是否为重言式进行讨论: 若 C 为重言式,则 A ? C ? A, C ? B, 于是A ? A ? C ? B ? C ? B.因而有A? B当 C 不是重言式时 , 请读者举反例说明 , A ? C ? B ? C 时 , 不一定有A? B.(3) 若 ?A ? ?B, 则 A ? B .证明如下:A ? ??A ? ??B ?B(双重否定律) ( ?A ? ?B ) (双重否定律)所以A? B1.12 (1) 设(1)中公式为 A.A ? ( p ? (q ? r )) ? ( p ? q ? r ) A ? ?( p ? (q ? r )) ? ( p ? q ? r ) A ? ?p ? (?q ? ?r ) ? ( p ? q ? r ) A ? (?p ? ?q) ? (?q ? ?r ) ? ( p ? q ? r ) A ? (?p ? ?q ? (?r ? r )) ? (?p ? q ? r ) ? ?r ) ? ( p ? q ? r ) ? (?p ? q ? ?r ) ? ( p ? q ? r )A ? m0 ? m1 ? m712于是,公式 A 的主析取范式为m0 ? m1 ? m2 ? m7易知,A 的主合取范式为M3 ? M4 ? M5 ? M6A 的成真赋值为 000, 001, 010, 111 A 的成假赋值为 011,100,101,110 (2)设(2)中公式为 BB ? (?p ? q) ? (?q ? p) ? (??p ? q) ? (?q ? p) ? ( p ? q) ? (?q ? p) ? ?( p ? q) ? (?q ? p) ? (?p ? ?q) ? ?q ? p? ?q ? p(吸收律)? ((?p ? q) ? ?) ? p ? (?q ? p) ? (?p ? ?q) ? p ? ( p ? ?q) ? ( p ? q)? m0 ? m2 ? m3所以,B 的主析取范式为 m0 ? m2 ? m3 . B 的主合取范式为 M 1 B 的成真赋值为 00,10,11. B 的成假赋值为 01. (3)设(3)中公式为 C.C ? ?( p ? q) ? q ? r ? ( p ? ?q) ? q ? r ]13? p ? (?q ? q) ? r ? p?0?r? 0.所以,C 的主析取范式为 0. C 的主合取范式为 M 0 ? M 1 ? M 2 ? M 3 C 的成假赋值为 00,01,10,11 C 无成真赋值,C 为矛盾式. 分析 1 °设公式 A 中含 n(n ? 1) 个命题变项 , 且 A 的主析取范式中含l (0 ? l ? 2 n ) 个极小项,则 A 的主合邓范式中含 2 n ? l 个极大项,而且极大项的角标分别为 0 到 2 n ? 1 这 2 n 个十进制数中未在 A 的主析取范式的极小项角标中出现过 的十进制数. 在(1)中,n=3,A 的主析取范式中含 4 个极小项,所以,A 的主合取范式中必含23 ? 4 ? 4 个极大项,它们的角标为 0 到 7 中未在主析取范式的极小项角标中出现过的 3,4,5,6. 这样,只要知道 A 的主析取范式,它的主合邓范式自然也就知道了, 在(2),(3)中情况类似. 2° A 的主析取范式中极小项角标的二进制表示即为 A 的成真赋值.在(1)中, 由于主析取范式中的极小项角标分别为 0,1,2,7, 它们的二进制表示分别为 000,001,010,111,所以,A 的成真赋值为以上各值.类似地,A 的主合取范式中所 含极大项角标的二进制表示,即为 A 的成假赋值. 1.13 (1) 首先求 p ? (q ? r ) 的主析取范式. 错误！链接无效。? ?p ? (?q ? r ) ? ?p ? ?q ? r ) .由于演算过程较长,可以分别先求出由 ?p, ?q, r 派生的极小项.注意,本公式 中含 3 个命题变项,所以,极小项长度为 3.?p ? ?p ? (?q ? q) ? (?r ? r )14? (?p ? ?q ? r ) ? (?p ? ?q ? r ) ? (?p ? q ? ?r ) ? (?p ? ?q ? r )? m0 ? m1 ? m2 ? m3?p ? (?p ? p) ? ?q ? (?r ? r ) ? (?p ? ?q ? ?r ) ? (?p ? ?q ? r ) ? (?p ? ?q ? ?r ) ? ( p ? ?q ? r )? m0 ? m1 ? m4 ? m5r ? (?p ? p) ? (?q ? q) ? r ? (?p ? ?q ? r ) ? (?p ? ?q ? r ) ? ( p ? ?q ? r ) ? ( p ? q ? r )? m1 ? m31 ? m5 ? m7 p ? (q ? r ) ? m0 ? m1 ? m2 ? m3 ? m4 ? m5 ? m7类似地,可求出 q ? ( p ? r ) 主的析取范式也为上式,由于公式的主析取范式 的唯一性,可知,( p ? (q ? r )) ? (q ? ( p ? r )).(2) ①p?q? ?( p ? q)? ?p ? ?q? (?p ? (?q ? q)) ? ((?p ? p) ? ?q) ? (?p ? ?q) ? (?p ? q)) ? ((?p ? ?p) ? ( p ? ?q) ? (?p ? ?q) ? (?p ? q) ? ( p ? ?p)? m0 ? m1 ? m2 .15②p?q? ?( p ? q)? ?p ? ?q? m0 .由于 p ? q 与 p ? q 的主析取范式不同.因而它们不等值,即 p ? q ? p ? q . 1.14 设 p:A 输入;设 q:B 输入; 设 r:C 输入; 由题的条件,容易写出 FA , FB , FC 的真值表,见表 1.5 所示.由真值表分别写出 它们的主析范邓范式,而后,将它们都化成与之等值的 {?} 中的公式即可. 表 1.5 p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 r 0 1 0 1 0 1 0 1FA0 0 0 0 1 1 1 1FB0 0 1 1 0 0 0 0FC0 1 0 0 0 0 0 0FA ? ( p ? ?q ? ?r ) ? ( p ? ?q ? r )) ? ( p ? q ? ?r ) ? ( p ? q ? r )? ( p ? ?q) ? (?r ? r ) ? ( p ? q) ? (?r ? r ) ? ( p ? ?q) ? ( p ? q)?p? ??( p ? q)16? ?( p ? q) ? ?( p ? q) ? ( p ? q) ? ( p ? p)FB ? (?p ? q ? ?r ) ? (?p ? q ? r )? (?p ? q) ? (?r ? r ) ? (?p ? q) ? ??(?p ? q) ? ?( p ? ?q)? p ? ?q) ? p ? ( q ? q) . FC ? (?p ? ?p ? r )? ?( p ? q) ? r? ( p ? q) ? r ? ??(( p ? q) ? r ? ?(?( p ? q) ? ?r ? ?( p ? q) ? ?r ? (( p ? q) ? ( p ? q)) ? (r ? r ) \分析在将公式化成 {?} 或 {?} 中公式时,应分以下几步:(1)先将公式化成全功能集 {?,?,?} 中的公式. (2) 使用?A ? ?( A ? A) ? A ? A,或?A ? ?( A ? A) ? A ? A.17使用双重否定律A ? B ? ??( A ? B) ? ?( A ? B) ? ( A ? B) ? ( A ? B)或A ? B ? ??( A ? B) ? ?( A ? B) ? ( A ? B) ? ( A ? B)使用德?摩根律A ? B ? ??( A ? B) ? ?(?A ? ?B)? ?A ? ?B ? ( A ? A) ? ( B ? B)或A ? B ? ??( A ? B) ? ?(?A ? ?B)? ?A ? ?B ? ( A ? A) ? ( B ? B)1．15设 p：矿样为铁；q：矿样为铜； r：矿样为锡. 设F1 ? (甲全对) ? (乙对一半) ? (丙全错) ，? (?p ? ?q) ? ((?p ? ?r ) ? ( p ? r )) ? (?p ? r ) ? (?p ? ?q ? ?p ? ?r ? ?p ? r ) ? (?p ? ?q ? p ? r ? ?p ? r )? 0? 0 ? 0.F2 ? (甲全对) ? (乙全错) ? (丙对一半)? (?p ? ?q) ? ( p ? ?r ) ? (( p ? r ) ? (?p ? ?r ) ? (?p ? ?q ? p ? ?r ? p ? r )18? (?p ? ?q ? p ? r ? ?p ? ?r )? 0?0 ? 0F3 ? (甲对一半) ? (乙全对) ? (丙全错)? ((?p ? q) ? ( p ? ?q)) ? (?p ? r ) ? (?p ? ?r ) ? (?p ? q ? ?p ? r ? ?p ? r ? ( p ? ?q ? ?p ? r ? ?p ? r ) ? (?p ? q ? r ) ? 0? ?p ? q ? r.F4 ? (甲对一半) ? (乙全错) ? (丙全对)? ((?p ? q) ? ( p ? ?q)) ? ( p ? ?r ) ? ( p ? ?r ) ? (?p ? q? ? ?r ? p ? ?r ? ( p ? ?q ? p ? ?r ? p ? ?r ) ? 0 ? ( p ? ?q ? ?r )? p ? ?q ? ?r.F5 ? (甲会错) ? (乙对一半) ? (丙全对)? ( p ? q) ? ((?p ? ?r ) ? ( p ? r )) ? ( p ? ?r ) ? ( p ? q ? ?p ? ?r ? p ? ?r ? ( p ? q ? p ? r ? p ? ?r )? 0?0 ? 0.F6 ? (甲全错) ? (乙全对) ? (丙对一半)? ( p ? q) ? ((?p ? r ) ? (( p ? r ) ? (?p ? ?r ) ? ( p ? q ? ?p ? r ? p ? r19? ( p ? q ? ?p ? r ? ?p ? ?r )? 0?0 ? 0.设F ? (一人全对) ? (一人对一半) ? (一人全错)则 F 为真命题，并且F ? F1 ? F2 ? F3 ? F4 ? F5 ? F6? (?p ? q ? r ) ? ( p ? ?q ? ?r ) ? 1.但， 矿样不可能既是铜又是锡， 于是 q,r 中必有假命题， 所以 ?p ? q ? r ? 0, 因而必有p ? ?q ? ?r ? 1.于是，必有 P 为真，q 与 r 为假，即矿样为铁。 1.16 令 p：今天是 1 号； q：明天是 5 号. 由于本题给出的推理都比较简单， 因而可以直接判断推理的形式结构是否为 重言式。 （1）推理的形式结构为( p ? q) ? p ? q.可以用多种方法判断上公式为重言式，其实，本推理满足假言推理定律，即( p ? q) ? p ? q.所以，推理正确。 （2）推理的形式结构为( p ? q) ? p ? q.可以用多种方法证明上公式不是重言式，其实，当 p 为假（即今天不是 1 号） ，q 为真（明天真是 5 号） ，也即 01 是上面公式的成假赋值，所以，推理的 形式结构不是重方式，故，推理不正确。20（3）推理的形式结构为( p ? q) ? ?p ? ?q.可以用多种方法证明上面公式为重言式，其实，它满足拒取式推理定律，即( p ? q) ? ?p ? ?q.所以，推理正确。 （4）推理的形式结构为( p ? q) ? ?p ? ?q.可以用多种方法证明上公式不是重言式，01 为上公式的成假赋值，所以， 推理不正确。 分析 对于前提与结论都比较简单的推理， 最好直接判推理的形式结构是否为重言式，来判断推理是否正确，若能观察出一个成假赋值，立刻可知，推理不 正确。 1．17 证明 ② ?r ③ ?q ④ ?( p ? ?q) ⑤ ?p ? q ⑥ ?p （2） 证明 ① p ? (q ? s) 前提引入 (1) ① ?q ? r 前提引入前提引入 ①②析取三段论 前提引入 ④置换 ②⑤析取三段论② q ? (q ? s) ③q ④p?s ⑤ p ? ?r①置换 前提引入 ②③假言推理 前提引入21⑥r ? p ⑦r ?s （3） 证明 ①p⑤置换 ④⑥假言三段论附加前提引入 前提引入 ①②假言推理 ①③合取② p?q ③q ④ p?q 或者 证明 ① p?q前提引入 ①置换 ②置换 ③置换 ④置换② ?p ? q ③ (?p ? p) ? (?p ? q) ④ ?p ? ( p ? q) ⑤ p ? ( p ? q) （4） 证明 ①前提引入 ①置换② (s ? t ) ? (t ? s) ③ ④t ? r ⑤t ⑥s ⑦ ⑧ ( q ? s ) ? ( s ? q) ⑨s ?q ⑩q ?q ? p②化简 前提引入③⑤假言推理 前提引入 ⑦置换 ⑧化简 ⑥⑨似言推理 前提引入22?p ?r ? p?q?s?r 分析 由于⑩? 假言推理 ④化简 ⑥⑩??合取( A1 ? A2 ? ? ? Ak ) ? (C ? B) ? ?( A1 ? A2 ? ? ? Ak ) ? (?C ? B) ? ?( A1 ? A2 ? ? ? Ak ? C ) ? B ? A1 ? A2 ? ? ? Ak ? C ? B所以,当推理的结论也为蕴含式时,可以将结论的前件作为推理的前提,称为 附加前提,并称使用附加前提的证明方法为附加前提证明法 .(3)中第一个证明, 即为附加前提证明法. 1.18 设 p：他是理科生 q：他是文科生 r：他学好数学 前提 结论 q 通过对前提和结论的观察， 知道推理是正确的， 下面用构造证明法给以证明。 证明?rp ? r, ?q ? p, ?r①p?r前提引入 前提引入 ①②拒取式 前提引入 ③④拒邓式 ⑤置理③ ?p ④ ?q ? p ⑤ ??q ⑥q 1．19本题可以用多种方法求解，根据要求回答问题，解本题最好的方法是真值表示或主析取范式法。这里采用主析取范式的主析取范式（过程略）23p ? (q ? ?r )? m2 ? m4 ? m5 ? m6 ? m7所以，成真赋值为 010，100，101，110，111，由④给也，成假赋值为 000， 001，011，由③给出，公式是非重言式的可满足式，由③给出。 1．20 分析 法。 方法 1： 求主析取范式?( p ? q) ? r ? ( p ? q) ? r ? ( p ? q) ? (r ? ?r ) ? ( p ? ?p) ? (q ? ?q) ? r答案A：③；B：④；C：②解本题的方法不限于求主析取范式或主合取范式， 也可以利用真值表? m1 ? m3 ? m5 ? m6 ? m7从上式可知， ?( p ? q) ? r 的主析取范式中含 5 个极小项。极小项角码的二 进制表示为成真赋值，因而成真赋值为 001，011，101，110，111。由成真赋值 立即可知成假赋值为 000， 010，100，成假赋值的十进制的十进表示为极大项的角码，因而极大项为M 0 , M 2 , M 4 ，故有 3 个极大项。方法 2：求主合取范式，分析类似主析取范式法。 方法 3：真值表法 由真值表，求出成真赋值，将成真赋值转化成十进制数做为极小项的角码， 这样就求出了全部极小项，也容易求出极大项。 1．21 分析 答案 A：③； B：⑤； C：⑥可用构造证明法解此题。 前提引入（1） ① ?q ? r ② ?r ③ ?q前提引入 ①②析取三段论24④ ?( p ? ?q) ⑤ ?p ? q ⑥ ?p前提引入 ④置换 ③⑤析取三段论至此可知 ?p 是（1）的逻辑结论。 （2） ① ?r ? s ② ?s ③ ?r ④ ( p ? q) ? r ⑤ ?( p ? q) ⑥ ?p ? ?q 前提引入 前提引入 ①②析取三段论 前提引入 ④置换 ⑤置换至此可知 ?p ? ?q 是（2）的国逻辑结论。 （3） ① ?p ? q ② p?q ③ ?q ? r ④q ?r ⑤ p?r ⑥r ?s ⑦ p?s 前提引入 ①置换前提引入 前提引入 ③置换 ②④假言推理 前提引入 ⑤⑥假言推理至此可知 p ? s 是（3）的逻辑结论。 1．22 分析 答案 A：④在本题中，设 A，B，C 分别表示 3 个开关状态的命题变项，开关的扳键向上时，对应命题变项的真值为 1，否则为 0，由真值表易知。F ? (?A ? ?B ? C) ? (?A ? B ? ?C) ? ( A ? ?B ? ?C) ? ( A ? B ? C)25? ?A ? ((?B ? C) ? ( B ? ?C)) ? A ? ((?B ? ?C) ? ( B ? C)) ? (?A ? ( B ? C)) ? ( A ? (?B ? C) ? ( B ? ?C)) ? (?A ? ( B ? C)) ? ( A ? ?(( B ? ?C) ? (?B ? C)) ? (?A ? ( B ? C)) ? ( A ? ?( B ? C))? A? B ? C26第2章习题解答2.1 (1)本题没有给出个体域,因而使用全 总个体域. 令 F ( x) : x 是鸟G( x) : x 会飞翔.命题符号化为?x( F ( x) ? G( x)) .(2)令 F ( x) : x 为人.G( x) : x 爱吃糖命题符号化为??x( F ( x) ? G( x))或者?x( F ( x) ? ?G( x))(3)令 F ( x) : x 为人.G( x) : x 爱看小说.命题符号化为?x( F ( x) ? G( x)) .(4) F ( x) : x 为人.G( x) : x 爱看电视.命题符号化为??x( F ( x) ? ?G( x)) .分析 1°如果没指出要求什么样的个体域，就使用全总个休域，使用全总个 体域时，往往要使用特性谓词。 （1）-（4）中的 F ( x) 都是特性谓词。 2° 初学者经常犯的错误是，将类似于（1）中的命题符号化为27?x( F ( x) ? G( x))即用合取联结词取代蕴含联结词，这是万万不可的。将（1）中命题叙述得 更透彻些，是说“对于宇宙间的一切事物百言，如果它是鸟，则它会飞翔。 ”因 而符号化应该使用联结词→而不能使用 ? 。若使用 ? ，使（1）中命题变成了“宇 宙间的一切事物都是鸟并且都会飞翔。 ”这显然改变了原命题的意义。 3° （2）与（4）中两种符号化公式是等值的，请读者正确的使用量词否定 等值式，证明（2） ， （4）中两公式各为等值的。 2.2 (1)d (a),(b),(c)中均符号化为?xF ( x)其中 F ( x) : ( x ? 1) 2 ? x 2 ? 2 x ? 1, 此命题在 (a), (b), (c) 中均为真命题。 （2） 在 (a), (b), (c) 中均符号化为?xG ( x)其中 G( x) : x ? 2 ? 0 ，此命题在（a）中为假命题，在(b)(c)中均为真命题。 （3）在 (a), (b), (c) 中均符号化为?xH ( x)其中 H ( x) : 5x ? 1. 此命题在 (a), (b) 中均为假命题，在(c)中为真命题。 分析 1°命题的真值与个体域有关。2° 有的命题在不同个体域中，符号化的形式不同，考虑命题 “人都呼吸” 。 在个体域为人类集合时，应符号化为?xF ( x)这里， F ( x) : x 呼吸，没有引入特性谓词。 在个体域为全总个体域时，应符号化为?x( F ( x) ? G( x))这里， F ( x) : x 为人，且 F ( x) 为特性谓词。 G( x) : x 呼吸。282．3 因题目中未给出个体域，因而应采用全总个体域。 （1） 令： F ( x) : x 是大学生， G( x) : x 是文科生， H ( x) : x 是理科生，命题 符号化为?x( F ( x) ? (G( x) ? H ( x))（2）令 F ( x) : x 是人， G( y) : y 是化， H ( x) : x 喜欢，命题符 号化为?x( F ( x) ? ?y(G( y) ? H ( x, y)))（3）令 F ( x) : x 是人， G( x) : x 犯错误，命题符号化为??x( F ( x) ? ?G( x)),或另一种等值的形式为?x( F ( x) ? G( x)（4）令 F ( x) : x 在北京工作， G( x) : x 是北京人，命题符号化为??x( F ( x) ? G( x)),或?x( F ( x) ? ?G( x)),（5）令 F ( x) : x 是金属， G( y) : y 是液体， H ( x, y) : x 溶解在 y 中，命题符号 化为?x( F ( x) ? ?y(G( y) ? H ( x, y))).（6）令 F ( x) : x 与 y 是对顶角， H ( x, y) : x 与 y 相等，命题符号化为?x?y( F ( x, y) ? H ( x, y)).分析 （2） ， （5） ， （6）中要使用 2 无谓词，用它们来描述事物之间的关系。 2.4（1） 对所有的 x， 存在着 y， 使得 x ? y ? 0 ， 在 (a), (b) 中为真命题， 在 (c), (d ) 中为假命题。 （2）存在着 x, 对所有的 y，都有 x ? y ? 0 ，在 (a), (b) 中为真命题，在 (c), (d ) 中为假命题。29（3） 对所有 x， 存在着 y， 使得 x ? y ? 1 ， 在 (a), (b)(c) 中均为假命题， 而在 (d ) 中为真命题。 （4）存在着 x，对所有的 y，都有 x ? y ? 1 ，在 (a), (b)(c)(d ) 中都是假命题。 （5）对所有的 x，存在着 y，使得 x ? y ? x 在 (a), (b)(c)(d ) 中都是真命题。 （6）存在 x，对所有的 y，都有 x ? y ? x ，在 (a), (b) 中为真命题，在 (c)(d ) 中 为假命题。 （7）对于所有的 x 和 y，存在着 z，使得 x ? y ? z ，在 (a), (b) 中为真命题， 在 (c)(d ) 中为假命题。 2.5 （1） 取解释 I 1 为： 个体域 D ? R （实数集合） ， F ( x) : x 为有理数， G ( x) : x 能表示成分数，在 I 1 下， ?x( F ( x) ? G( x)) 的含义为 “对于叙何实数 x 而言， 若 x 为有理数， 则 x 能表示成分数” ， 简言之为 “有 理数都能表示成分数。 ”在此蕴含式中，当前件 F ( x) 为真时，后件 G( x) 也为真， 不会出现前件为真，后件为假的情况，所以在 I 1 下，?x( F ( x) ? G( x)) 为真命题。 在在 I 1 下， ?x( F ( x) ? G( x)) 的含义为 “对于任何实数 x,x 既为有理数，又能表示成分数。 ” 取 x ? 2 ，则 F ( 2 ) ? g ( 2 ) 显然为假，所以，在 I 1 下， ?x( F ( x) ? G( x)) 为 假命题. (2) 取解释 I 2 为:个体域 D=N(自然数集合), F ( x) : x 为奇数, G( x) : x 为偶 数,在 I 2 下, ?x( F ( x) ? G( x)) 的含义为 “存在自然数 x,x 发既为奇数，又为偶数。 ” 取 x ? 2 ，则 F (2) 为假，于是 F (2) ? G(2) 为真，这表明 ?x( F ( x) ? G( x) 为 真命题。 分析 本题说明?x( F ( x) ? G( x)) ? ?x( F ( x) ? G( x)),30?x( F ( x) ? G( x)) ? ?x( F ( x) ? G( x)),这里， A ? B 表示 A 与 B 不等值，以后遇到 ? ，含义相同。 在一阶逻辑中，将命题符号化时，当引入特性谓词（如题中的 F ( x)) 之后， 全称量词 ? 后往往使用联结词→而不使用 ? ，而存在量词 ? 后往往使用 ? ，而不 使用→，如果用错了，会将真命题变成假命题，或者将假命题变成真命题。 2．6 在解释 R 下各式分别化为 （1） ?x(? x ? 0); （2） ?x?y( x ? y ? x); （3） ?x?y?z( x ? y) ? ( x ? z ? y ? z)); （4） ?x?y( x ? x ? 2 y). 易知，在解释 R 下， （1） ， （2）为假； ， （3） （4）为真。 2．7 给定解释 I 为：个体域 D=N（自然数集合） ，F ( x) : x 为奇数，G( x) : x 为 偶数。 （1）在解释 I 下，公式被解释为 “如果所有的自然数不是奇数就是偶数，则所有自然数全为奇数，或所有自 然数全为偶数。 ”因为蕴含式的前件为真，后件为假，所以真值为假。 （2）在 I 下，公式解释为 “如果存在着自然数为奇数，并且存在着自然为偶数，则存在着自然数既是 奇数，又是偶数。 ” 由于蕴含式的前件为真，后件为假，后以真值为假。 分析 律。 2.8 令 A ? ?x?y( F ( x) ? G( y) ? L( x, y)), 在 A 中，无自由出现的个体变项， 本题说明全称量词对析取不满足分配律， 存在量词对合取不满足分配所以 A 为闭式。 给定解释 I 1 ：个体域 D=N（整数集合） ， F ( x) : x 为正数， G( x) : x 为负数，L( x, y) : x ? y ，在 I 1 下，A 的含义为31“对于任意的整数 x 和 y，如果 x 为正整数，y 为负整数，则 x ? y 。 ” 这是真命题。 设解释 I 2 ： 个体域 D=R （R 整数集合） ，F ( x) : x 为有理数，G( y) : y 为无理数，L( x, y) : x ? y ，在 I 2 下，A 的含义为“对于任意的实数 x 和 y，如果 x 为有理数，y 为元理数，则 x ? y 。 ” 这是假命题。 分析 闭式在任何解释下不是真就是假， 不可能给出解释 I, 使得闭式在 I下真值不确定， 这一点是闭式的一个重要特征。 而非封闭的公式就没有这个特征。 2.9 取 A1 ? L( f ( x, y), g ( x, y)) 和 A2 ? ?x( f ( x, y), x) ， 则 A1 和 A2 都是非土产的 公式，在 A1 中，x, y 都是自由出现的，在 A2 中，y 是自出现的。 取 解 释 I 为 ， 个 体 域 D=N （ N 为 自 然 数 集 合 ），f ( x, y, ) ? x ? y, g ( x, y) ? x ? y L( x, y) 为 x ? y 。在 I 下， A1 为 x ? y ? x ? y 为假，所以在 I 下， A1 真值不确定，即在 I 下 A2 的真值也是命题。 在 I 下， A2 为 ?x( x ? y ? x), 当 y ? 0 时，它为真； y ? 0 时为假，在 I 下 A2 的 真值也不确定。 分析 非闭式与 闭式的显著区别是，前者可能在某些解释下，真值不确定，而后者对于任何解释真值都确定，即不是真就是假。 当然非闭式也可以是逻辑有效式（如 F ( x) ? F ( x) ） ，也可能为矛盾式（如F ( x) ? ?F ( x)) ，也可能不存在其值不确定的解释。2．10（1） （消去量词等值式） （德?摩根律） （消去量词等值式）??xA( x) ? ?( A(a) ? A(b) ? A(c)) ? ?A(a) ? ?A(b) ? ?A(c) ? ?x?A( x)（2）??xA( x) ? ?( A(a) ? A(b) ? A(c))32（消去量词等值式）? ?A(a) ? ?A(b) ? ?A(c) ? ?x?A( x)（德?摩根律） （消去量词等值式）2．11 （1） 令 F ( x) : x 为人。G( x) : x 长着绿色头发。本命题直接符号化验为??x( F ( x) ? G( x)) ]而??x( F ( x) ? G( x)) ? ?x?( F ( x) ? G( x))（量词否定等值式） （德?摩根律） （蕴含等值式）? ?x(?F ( x) ? ?G( x)) ? ?x( F ( x) ? ?G( x))最后一步得到的公式满足要求（使用全称量词） ，将它翻译成自然语言，即 为 “所有的人都不长绿色头发” 。 可见得“没有人长着绿色头发。 ”与“所有人都不长绿色头发。 ”是同一命题 的两种不同的叙述方法。 （2）令 F ( x) : x 是北京人G( x) : x 去过香山。命题直接符号化为?x( F ( x) ? ?G( x)) ]而?x( F ( x) ? ?G( x)) ? ???x( F ( x) ? ?G( x))（双重否定律）? ??x?( F ( x) ? ?G( x)) ? ??x(?F ( x) ? G( x)) ? ??x( F ( x) ? G( x))（理词否定等值式） （德?摩根律） （蕴含等值式）33最后得到的公式满足要求（只含全称量词） ，将它翻译成自然语言，即为 “并不是北京人都去过香山。 ” 可见， “有的北京人没过过香山。 ”与“并不是北京人都去过香山。 ”是同一 命题不同的叙述方法。 2.12 （1） ?xF ( x) ? ?yG( y)? ( F (a) ? F (b) ? F (c) ? (G(b) ? G(c)).（2） ?xF ( x) ? ?yG( y)? ?xF ( x) ? ?yG( y)（量词辖域收缩扩张等值式）? ( F (a) ? F (b) ? F (c)) ? (G(a) ? G(b) ? (c)).（3） ?x?yH ( x, y)? ?x( H ( x, a) ? H ( x, b) ? H ( x, c) ? ( H (a, a) ? H (a, b) ? H ( x, c) ? ( H (b, a) ? H (b, b) ? H (b, c) ? ( H (c, a) ? H (c, b) ? H (c, c)分析在有穷个体域内消去量词时， 应将量词的辖域尽量缩小， 例如， 在 （2）中，首先将量词辖域缩小了（因为 ?yG ( y) 中不含 x，所以，可以缩小） 。否则， 演算是相当麻烦的。见下面的演算：?x( F ( x) ? ?yG( y) ? ( F (a) ? ?yG( y)) ? ( F (b) ? ?yG( y)) ? F (c) ? ?yG( y)) ? ( F (a) ? (G(a) ? G(b) ? G(c) ? ( F (b) ? (G(a) ? G(c)) ? ( F (c) ? (G(a) ? G(b) ? G(c)) ? ( F (a) ? ( F (b) ? (G(a) ? G(b) ? (c)).显然这个演算比原来的喾算麻烦多了。342.13 在 I 下 （1） ?x( F ( x) ? G( x))? ( F (?2) ? G(?2)) ? ( F (3) ? G(3)) ? F (6) ? G(6)) ? (1 ? 0) ? (1 ? 0) ? (0 ? 1) ? 0,所以， ?x( F ( x) ? G( x) 在 I 下为假。 （2） ?x( R( x) ? F ( x)) ? G(5)? (( R(?2) ? F (?2)) ? ( R(3) ? F (3)) ? ( R(6) ? F (6))) ? 0 ? ((1 ? 1) ? (1 ? 1) ? 0,所以，此公式在 I 下也是假命题。 （3） ?x( F ( x) ? G( x))? ?xF ( x) ? ?xG( x)（量词分配等值式）? ( F (?2) ? F (3) ? F (6)) ? (G(?2) ? G(3) ? G(3) ? (1 ? 1 ? 0) ? (0 ? 0 ? 1) ? 1,所以，此公式在 I 下为真 2．14 （1）??xF ( x) ? ?yG( x, y) ? ?x?F ( x) ? ?yG( x, y) ? ?z?F ( z) ? ?yG( x, y) ? ?z?y(?F ( z) ? G( x, y) ? ?z?y( F ( z) ? G( x, y)（量词否定等值式） （约束变项换名规则） （量词辖域收缩扩张等值式）（2）?(?xF ( x, y) ? ?yG( x, y)) ? ?x?F ( x, y) ? ?y?G( x, y)35? ?z1?F ( z1 , y) ? ?z 2 ?G( x, z 2 ) ? ?z1?z 2 (?F ( z1 , y) ? ?G( x, z 2 )在以上演算中分别使用了德?摩根律、量词否定等值式、约束变项换名规则 等。 分析?y?z ( F ( z) ? G( x, y)) 也是（1）中公式的前束范式。公式的前束范式是不唯一的。 （ 1）中最后两步都是前束范式，其实2．15（1）?xF ( x) ? ?yG( x, y) ? ?xF ( x) ? ?yG( z, y) ? ?x?y( F ( x) ? G( z, y))（2）?x( F ( x) ? ?yG( x, y, z)) ? ?zH ( x, y, z) ? ?x( F ( x) ? ?yG( x, y, u)) ? ?zH (v,? , z) ? ?x?y( F ( x) ? G( x, y, u)) ? ?zH (v,? , z) ? ?x?y( F ( x) ? G( x, y, u)) ? H (v,? , z)在以上演算中分别使用了自由变项换名规则和量词辖域收缩扩张等值式。 2.16 （1）②错。使用 UI，UG，EI，EG 规则应对前束范式，而①中公式下 不是前束范式，所以，不能使用 UI 规则。 （2） 。 ①中公式为 ?xA( x) ，这时，A( x) ? F ( x) ? G( x) ，因而使用 UI 规则时， 应得 A(a) （或 A( y) ） ，故应有 F (a) ? G(a), 而不可能为 F (a) ? G(b). （3）②错。应对 A(c) ? F (c) ? G(c) 使用 EG 规则，其中 c 为特定的使 A 为 真的个体常项，而不能为个体变项。 （4）②错。①中公式含个体变项 x，不能使用 EG 规则。 （5）②错。①公式含两个个体常项，不能使用 EG 规则。36（6）⑤错。对①使用 EI 规则得 F (c) ? G(c) ，此 c 应使 F (c) ? G(c) 为真， 此 c 不一定使 H (c) ? R(c) 为真。 分析 由于⑤的错误，可能由真前提，推出假结论。反例如下：设个体域为自然数集合 N .F ( x) : x 为偶数， G( x) : x 为素数， H ( x) : x 能被 3 整除， R( x) : x 能被 4 整数，显然此时，?x( F ( x) ? G( x)) 与 ?x( H ( x) ? R( x))均为真，但 ?x( F ( x) ? G( x)) 为假。其实在（6）中，③应为 F (2) ? G(2) ，它 是 真 命 题 ， 而 H (2) ? R(2) 为 假 命 题 。 对 ?x( H ( x) ? R( x)) 使 用 EI 规 则 ， 得H (12) ? R(12) 才为真。所以，对两个公式使用 EI 规则使用同一个个体常项是会犯错误的。 2.17 （1）证明 ① ?xF ( x) ? ?y(( F ( y) ? G( y)) ? R( y) ② ?xF ( x) ③ ?y(( F ( y) ? G( y)) ? R( y)) ④ F (c ) ⑤ F (c) ? G(c) ⑥ F (c) ? G(c)) ? R(c) ⑦ R (c ) ⑧ ?xR( x) （2）证明： ① ?xF ( x) ② F (c ) 前提引入 ①EI 前提引入 前提引入 ①② 假言推理 ②EI ④附加 ③UI ⑤⑥假言推理 ⑦ EG37③ ?x( F ( x) ? (G( y) ? R( x))) ④ F (c) ? (G( y) ? R(c)) ⑤ G( y) ? R(c) ⑥ R (c ) ⑦ F (c) ? R(c) ⑧ ?x( F ( x) ? R( x)) 2．18 令 F ( x) : x 是大熊猎。G( x) : x 产在中国。前提引入 ③UI ②④假言推理 ⑤化简 ②⑥合取 ⑦ EGa : 欢欢前提： ?x( F ( x) ? (G( x)), F (a) 结论： G(a) 证明： ① ?x( F ( x) ? G( x)) ② F (a) ③ F ( a) ? G ( a ) ④ G (a) 2．19 令 F ( x) : x 为有理数。G( x) : x 为实数。前提引入 前提引入 ①UI ②③假言推理H ( x) : x 为整数。前提： ?x( F ( x) ? G( x)), ?xF ( x) ? H ( x)). 结论： ?x(G( x) ? H ( x)). 证明： ① ?xF ( x) ? ?y(( F ( y) ? G( y)) ? R( y)38前提引入② ?xF ( x) ③ ?y(( F ( y) ? G( y)) ? R( y)) ④ F (c ) ⑤ F (c) ? G(c) ⑥ F (c) ? G(c)) ? R(c) ⑦ R (c ) ⑧ ?xR( x) （2）证明： ① ?xF ( x) ? H ( x) ② F (c) ? H (c) ③ ?x( F ( x) ? G( x) ④ F (c) ? G(c) ⑤ F (c ) ⑥ G (c ) ⑦ H (c ) ⑧ G(c) ? H (c) ⑨ ?x(G( x) ? H ( x)) 分析 在以上证明中，不能如下进行。前提引入 ①② 假言推理 ②EI ④附加 ③UI ⑤⑥假言推理 ⑦ EG前提引入 ①EI 前提引入 ③UI ②化简 ④⑤假言推理 ②化简 ⑥与⑦合取 ⑧EG① ?x( F ( x) ? H ( x) ② ?x( F ( x) ? G( x)) ③ F (c) ? G(c) ④ F (c) ? H (c)前提引入 前提引入 ②UI ①EI至 此 ， 可 能 犯 了 错 误 ， 在 ③ 中 取 c ? 2 , 则 F ( 2 ) ? G( 2 ) 为 真 ， 但39E ( 2 ) ? H ( 2 ) 为假，就是说，由 UI 规则得到的 c 不一定满足 EI 规则，但反之为真，这一点务必注意。 2.20 分析 答案 A：③； B：②（7）式为非闭式，在个体域为整数集 Z 时， ?x( x? y ? x) 的真值不能确定，当 y ? 1 时为真，当 y ? 1 时为假，所以，它不是命题，其余各式都是命题。 （5）虽然不是闭式，但它为真。 2．21 分析 答案 A：②； B：④，⑤，⑨ C：⑦； D：⑧注意约束变项和自由变项改名规则的使用。供选答案中， （1）的前束范式只有一个，就是②。而②的前束范式有 3 个，当然它们都是等值的。 （3）的 前 束 范 式 有 2 个 ， 就 是 ⑦ 和 ⑧ 。 注 意 ， 在 （ 3 ） 式 中 ， ?x 的 辖 域 为( F ( x, y) ? ?yG( x, y)) ，这就决定了它们的前束范式为 ?x?y( F ( x, z) ? G( x, y)) ，（将自由出现的 y 改名为 z）但由于?y?x( F ( x, z) ? G( x, y)) ? ?x?y( F ( x, z) ? G( x, y))所以，⑧也是（3）的前束范式。 2．22 答案 分析 A：⑤。（1） ， （4）正确；可以构造证明。（1）证明： ① ?yF ( y) ② F (c ) ③ ?x( F ( x) ? G( x) ④ F (c) ? G(c) ⑤ F (c ) ⑥ ?yG ( y) 前提引入 ①EI 前提引入 ③UI ②④假言推理 ⑤EG40注意应先使用 EI 规则。 （4）证明： ① ?x( F ( x) ? H ( x)) ② F ( y) ? H ( y) ③ ?H ( y) ④ ?F ( y) ⑤ ?x(?F ( x) (2),(3)推理不正确,只要举出反例即可. 在自然数集合中 , 令 F ( x) : x 是偶数 , G( x) : x 是素数 , 则 ?x( F ( x) ? G( x)) 为 真命题,而 ?yF ( y) 为假命题,所以, ?x( F ( x) ? G( x)) ? ?yF ( y) 不是逻辑有效蕴 含式,这说明(2)是推理不正确,读者可举反例说明(3)中推理也不正确. 2.23 答案 A: ② B:① C: ⑦ D:⑤ 前提引入 ①UI 前提引入 ②③拒取式 ④UG41第3章习题解答3.1 3.2 3.3A：③； B：④； A：③；B：①； A：①；B：③；C：⑤；D：⑦；E：⑧C：⑤； D：⑥； E：⑦ C：⑧； D：⑤； E：⑩分析 对于给定的集合或集合公式，比如说是 A 和 B，判别 B 是否被 A 包含， 可以有下述方法： 1° 若 A 和 B 是通过列元素的方式给出的， 那么依次检查 B 中的每个元素是 否在 A 中出现，如果都在 A 中出现，则 B ? A, 否则不是。例如，3.3 题给的答案 中有{{1， 2}}和{1}， 谁是 S ? {?,{1},{1,2}} 的子集呢?前一个集合的元素是{1,2}, 要 S 中出现,但后一个集合的元素是 1,不在 S 中出现,因此,{{1,2}} ? S. 2° 若 A 和 B 是通过用谓词概括元素性质的主试给出的,B 中元素的性质为 P,A 中元素的性质为 Q,那么, “如果 P 则 Q”意味着 B ? A, “只有 P 才 Q”意味着 A ? B, “除去 P 都不 Q”意味着 A ? B, “P 且仅 P 则 Q”意味着 A ? B. 例如，3.1 题（1）是“如果 P 则 Q”的形式，其中“计算机专业二年级学生” 是性质 P， “学《离散数学》课”是性质；题（2）是“P 且仅 P 则 Q”的形式， 此外 “如果 P 就非 Q”则意味着 A ? B ? ? 。 例如，3.1 题（3）和 3.2 题（3）都是这种形式。 3° 通过集合运算差别 B ? A, 如果 A ? B ? A ， B ? A ? B ， B ? A ? ? 三个 等式中有任何一个成立，则有 B ? A. 。 4° 通过文氏图观察， 如果代表 B 的区域落在代表 A 的区域内部， 则 B ? A. 。42这后两种方法将在后面的解答中给出实例。 3.4 3.5 3.6 3.7 分析 A：②； B：④； A：②；B：④； A：①；B：⑨； A：④；B：⑨； C：⑦； D：⑥；E：⑧C：⑤； D：⑥； E：⑨ C：④； D：⑦； E：⑧ C：①； D：⑧； E：①设只买 1 本、2 本及 3 本书的学生集合分别为 S1 , S 2 和 S 3 ，它们之间两两不交，由题意可知，| S 3 |? 20, | S 2 ? S 3 |? 55.又知 | S 2 ? S 3 |? ? ,所以,| S 2 |?| S 2 ? S 3 | ? | S 3 |? 55 ? 20 ? 35.然后列出下面的方程:| S1 | ?2 | S 2 | ?3 | S 3 |? 140求得 | S1 |? 10 .因此,没有买书的人数是 75-(10+35+20)=10. 3.8 分析 (1)和(4)为真,其余为假. 这里可以应用集合运算的方法来差别集合之间的包含或相等关系.如题(3)中的条件 S ? T ? ? 意味着, S ? T ,这时不一定有 S=T 成立.而对于题(4), 由条件~ SUT ? E 可推出S ? (~ SUT ) ? S ? E ? ( S ? ~ S ) ? ( S ? T ) ? S ? ? ? (S ? T ) ? S ? S ? T ? S.这是 S ? T 的充公必要条件,从而结论为真. 对于假命题都可以找到反例 , 如题 (2) 中令 S ? {1,2}, T ? z{1}, M ? {2} 即可 ; 而对于题(5),只要 S ? ? 即可. 3.9 (2),(3)和(4)为真,其余为假. 3.10 (1) A ? {0,1,2}. (2) A ? {1,2,3,4,5}43(3) A ? {?1} (4) A ? {? 0,0 ?, ? 0,1 ?? 1,0 ?, ? 0,2 ?, ? 1,1 ?, ? 2,0 ?, ? 0,3 ?,? 1,2 ?, ? 2,1 ?, ? 3,0 ?? 0,4 ?, ? 1,3 ?, ? 2,3 ?, ? 2,2 ?, ? 3,1 ?, ? 4,0 ?}3.11(1) a ? c 或 c ? b (2) 任何 a, b(3) b ? c ? d (4) a ? b ? c (5) a ? c ? ? 且 b ? {?} . 3.12 分析 (1),(2)和(6)都是 B ? A, 而(3),(4),(5)是 A=B. 对于用谓词给定的集合先尽量用列元素的方法表示,然后进行集合之间包含关系的判别.如果有的集合不能列元素,也要先对谓词表示尽可能化简.如 题(3)中的 A 可化简为{x | x ? N ? x ? 2};题(5)中的 A 和 B 都可以化简为 {1,?2} ;题(6)中的1 A ? {x | x ? N ? ? 2 ? x ? 2}, B ? {1, }. 2而对于题(4),不难看出 A=B=R,是实数集合. 3.13 (1) A ? B ? {{a, b}, c, d}, A ? B ? {c}.A ? B ? {{a, b}}, A ? B ? {{a, b}}, d}.(2) A ? B ? {{a{b}}, c,{c},{a, b},{b}}.A ? B ? {{a, b}, c}, A ? B ? {{a{b},{c},{b}}. A ? B ? {{a,{b}},{c}},(3) A ? B ? N , A ? B ? {2}, A ? B ? {0,1}A ? B ? N ? {2}(4)观察到 B ? A, 故44A ? B ? A, A ? B ? B, A ? B ? A ? B ? {x | x ? R ? Z ? x ? 1}.(5) 观察到 A ? B ? ? ,故A ? B ? Z ? {0,1} A ? B ? ?A? B ? AA ? B ? N ? {0,1}3.14(1) P( A) ? {?,{?}}.(2) P( A) ? {?,{{1}},{1},{{1},1}}. (3) P( A) ? {?,{?},{{1}},{{2}},{{1,2}},{?{2}},{?{2}},{?,{1,2}},{{1},{2}},{{1},{1,2}},{{2},{1,2}},{{2},{1,2}},{?,{1},{2}} {?,{1},{2}},{?{1},{1,2}},{?,{2},{1,2}},{{1},{2}{1,2}} , {?,{1},{2},{1,2}}}.(4) P( A) ? {?,{{1}},{{1,2}},{{1}},{{1,2}} (5) P( A) ? {?,{?1},{1},{2},{?1,1},{?1,2}{1,2}{?1,1,2}. 分析 在做集合运算前先要化简集合 ,然后再根据题目要求进行计算.这里的化简指的是元素,谓词表示和集合公式三种化简. 元素的化简――相同的元素只保留一个，去掉所有冗余的元素。 谓词表示的化简――去掉冗余的谓词，这在前边的题解中已经用到。 集合公工的化简――利用简单的集合公式代替相等的复杂公式。 这种化简常 涉及到集合间包含或相等关系的判别。 例如，题（4）中的 A ? {{1,1},{2,1},{1,2,1}} 化简后得 A ? {{1},{1,2}} ，而题（5） 中 的 A ? {x | x ? R ? x 3 ? 2 x 2 ? x ? 2 ? 0} 化简为 A ? {?1,1,2} 。 3．15453．16 （1） ， （2） ， （3）和（6）为真。 （4）和（5）不为真。 分析 如果给出的是集合恒等式，可以用两种方法验证。一是分别对等式两边的集合画出文氏图， 然后检查两个图中的阴影区域是否一致。二是利用集合恒 等式的代入不断对等式两边的集合公式进行化简或者变形， 直到两边相等或者一 边是另一边的子集为止。例如，题（1）中的等式左边经恒等变形后可得到等式 右边，即( A ? B) ? C ? ( A ? B)? ~ C ? ( A? ~ C) ? ( B? ~ C) ? ( A ? C) ? ( B ? C)类似地，对题（2）和（3）中的等式分别有A ? B( B ? C) ? A? ~ ( B? ~ C) ? A ? (~ B ? C) ? ( A? ~ B) ? ( A ? C) ? ( A ? B) ? A ? C ) A ? ( B ? C) ? ( A ? B) ? ( A ? C) ? ( A ? B) ? ( A? ~ C) ? (( A ? B) ? A)? ~ C ? ( A ? B)? ~ C ? ( A ? B) ? C但对于等式（4） ，左边经变形后得( A ? B ? C) ? ( A ? B) ? (( A ? B) ? ( A ? B)) ? (C ? ( A ? B))= ? ? (C ? ( A ? B)) ? C ? ( A ? B). 易见， C ? ( A ? B) ? C, 但不一定有 C ? ( A ? B) ? C. 如令 A ? B ? C ? {1}. 时， 等式 （4） 不为真。 类假地， 等式 （5） 的左边经化简后得 ( A ? C ) ? B ， 而 ( A ? C) ? B 不一定恒等于 A-C。 3．17 （1）不为真。 （2） ， （3）和（4）都为真。对于题（1）举反例如下： 令 A ? {1}, 但 A?C ? B ? D， 与 A ? {1}, B ? {1,4}, C ? {2}, D ? {2,3}, 则 A ? B 且 C ? B ， 结论矛盾。46分析 （2）由于 C ? D ?~ D ?~ C, 又由 A ? B 可得 A ? C ~ D ? B? ~ C, 即A ? D ? B ? C 成立。（3）由于 A ? ( B ? A) ? A ? B ，故有B ? A ? ( B ? A) ? B ? A ? B ? A ? B 。这里用到 A ? B 的充要条件为 B ? A ? B 或 B ? A ? B 或 A ? B ? ?. （4）易见，当 A=B 成立时，必有 A-B=B-A。反之，由 A-B=B-A 得( A ? B) ? B ? ( B ? A) ? B化简后得 B ? A ? ? ，即 B ? A ，同理，可证出 A ? B ，从而得到 A=B。 3．18 由 | P( B) |? 64 可知|B|=6。又由 | P( A ? B) |? 256 知 | A ? B |? 8 ，代入包 含排斥原理得8 ? 3 ? 6? | A ? B |,从而有 | A ? B |? 1, | A ? B |? 2, | A ? B |? 2 ? 5 ? 7. 3．19 令 S ? {x | x ? N ? 1 ? x ? 1000000}.A ? {x | x ? S ? x 是完全平方数}， B ? {x | x ? S ? x 是完全立方数}，从而有 | S |? 1000000, | A |? 1000, | B |? 100, | A ? B |? 10. 代入包含排斥原理得| A ? B |?| S | ?(| A | ? | B |) ? | A ? B |? 1000000 ? (1000 ? 100) ? 10=99891047第4章习题解答4．1 4．2 4．3A：⑤； B：③； C：①； D：⑧； E：⑩ A：②； B：③； C：⑤； D：⑩； E：⑦ A：②； B：⑦； C：⑤； D：⑧； E：④分析 题 4.1-4.3 都涉及到关系的表示。先根据题意将关系表示成集合表达 式，然后再进行相应的计算或解答，例如，题 4.1 中的I s ? {? 1,1 ?, ? 2,2 ?}, Es ? {? 1,1 ?, ? 1,2 ?, ? 2,1 ?, ? 2,2 ?} I s ? {? 1,1 ?, ? 1,2 ?, ? 2,2 ?};而题 4.2 中的R ? {? 1,1 ?, ? 1,4 ?, ? 2,1 ?, ? 3,4 ?, ? 4,1 ?}.为得到题 4.3 中的 R 须求解方程 x ? 3 y ? 12 ，最终得到R ? {? 3,3 ?, ? 6,2 ?, ? 9,1 ?}.求 R ? R 有三种方法，即集合表达式、关系矩阵和关系图的主法。下面由题 4.2 的关系分别加以说明。 1°集合表达式法 将 domR, domR ? ran, ranR 的元素列出来，如图 4.3 所示。然后检查 R 的每 个有序对， 若 ? x, y ?? R ， 则从 domR 中的 x 到 ranR 中的 y 画一个箭头。 若 danR 中的 x 经过 2 步有向路径到达 ranR 中的 y，则 ? x, y ?? R ? R 。由图 4.3 可知R ? R ? {? 1,1 ?, ? 1,4 ?? 4,1 ?, ? 4,4 ?, ? 2,1 ?, ? 2,4 ?, ? 3,1 ?}.如果求 F ? G ，则将对应于 G 中的有序对的箭头画在左边，而将对应于 F 中 的有序对的箭头画在右边。对应的三个集合分别为 domG, ran ? domF, ranF ，然 后，同样地寻找 domG 到 ranF 的 2 步长的有向路径即可。 2° 矩阵方法 若 M 是 R 的关系矩阵，则 R ? R 的关系矩阵就是 M?M，也可记作 M2，在计算48乘积时的相加不是普通加法，而是逻辑加，即 0+0=0，0+1=1+0=1+1=1，根据已 知条件得?1 ?1 2 M ?? ?0 ? ?10 0 1 ? ?1 ? 0 0 0? ? ? ?1 0 0 1? ?0 ? ? 0 0 0? ?10 0 1 ? ?1 ? 0 0 0? ? ? ?1 0 0 1? ?1 ? ? 0 0 0? ?10 0 1? 0 0 1? ? 0 0 0? ? 0 0 1?M 2 中含有 7 个 1，说明 R ? R 中含有 7 个有序对。图 4.3 3°关系图方法图 4.4设 G 是 R 的关系图。为求 R n 的关系图 G ' ，无将 G 的结点复制到 G ' 中，然后 依次检查 G 的每个结点。如果结点 x 到 y 有一条 n 步长的路径，就在 G ' 中从 x 到 y 加一条有向边。当所有的结点检查完毕，就得到图 G ' 。以题 4.2 为例。图 4.4（1）表示 R 的关系图 G。依次检查结点 1，2，3，4。从 1 出发，沿环走 2 步仍回到 1，所以， G ' 中有过 1 的环。从 1 出发，经&1,1&和&1,4&，2 步可达 4， 所以， G ' 中有从 1 到 4 的边。结点 1 检查完毕。类似地检查其他 3 个结点，2 步长的路径还有 2→1→1，2→1→4，3→4→1，4→1→1，4→1→4。将这些路径 对应的边也加到 G ' 中，最终得到 R 2 的关系图。这个图给在图 4.4(2). 4．4 A：④； B：⑧； C：⑨； D：⑤； E：⑩分析 根据表 4.1 中关系图的特征来判定 R1 , R2 ,? R5 的性质， 如表 4.2 所示。 表 4.249自反反自反对称反对称传递R1 R2 R3 R4 R5√ √ √ √ √ √ √ √ √ √从表中可知 R1 , R2 和 R3 不是传递的，理上如下：在 R1 中有边&3,1&和&1,2&， 但缺少边&3,2&.在 R2 中有边&1,3&和&3,2&，但缺少边&1,2&。在 R3 中有边&1,2& 和&2,1&，但缺少过 1 的环。 4.5 分析 A：①； B：③； C：⑧； D：⑨； E：⑤ 等价关系和划分是两个不同的概念，有着不同的表示方法，等价关系是有序对的集合，而划分是子集的集合，切不可混淆起来，但是对于给定的集合 A，A 上的等价关系 R 和 A 的划分 ? 中一一对应的，这种对应的含义是? x, y ?? R ? x 和 y 在 ? 的同一划分块里。拘句话说，等价说系 R 的等价类就是划分 ? 的划分块，它们表示了对 A 中元 素的同一种分类方式。 给定划分 ? ，求对应的等价关系 R 的方法和步骤说明如下： 1 ° 设 ? 中 含 有 两 个 以 上 元 素 的 划 分 块 有 l 块 ， 记 作 B1 , B2 ,?.Bt 。 若Bi ? {x1 , x2 ,?, x j } ， j ? 2 ， 则 ? xs , xt ?? Ri , s, t ? 1,2,?, j, s ? t. 求出 R1 , R2 ,?, Rt 。2° R ? R1 ? R2 ? ? ? Rt ? I A. 本题中的 ? 1 的划分块都是单元集，没有含有个以上元素的划分块，所以，R ? I A , ? 2 含有两个划分块，故对应地等价关系含有两个等价类。 ? 3 中只有一个划分块 Z ? .Z ? 包含了集合中的全体元素，这说明 ? x, y ?? R1 ? x, y ? Z ? , 因此， 这个划分块对应的关系 R1 就 Z ? 上的全域关系， 从而得到 R ? R1 ? I A 也是 Z ? 上的 全域关系。 4．6 A：③； B：⑩； C：⑤； D：⑩； E：⑤50分析画哈斯图的关键在于确定结点的层次和元素间的盖住关系， 下面讨论一下画图的基本步骤和应该注意的问题。 画图的基本步骤是： 1° 确定偏序集 ? A, ?? 中的极小元，并将这些极小元放在哈斯图的最底层， 记为第 0 层。 2° 若第 n 层的元素已确定完毕，从 A 中剩余的元素中选取至少能盖住第 n 层中一个元素的元素， 将这些元素放在哈斯图的第 n+1 层。在排列第 n+1 层结点 的位置时， 注意把盖住较多元素的结点放在中间，将只盖住一个元素的结点放在 两边，以减少连绩的交叉。 3° 将相邻两层的结点根据盖住关系进行连线。 以本题的偏序集为例，1 可以整除 S 中的全体整数，故 1 是最小元，也是唯 一的极小元应该放在第 0 层。是 1 的倍数，即 2，3，5，7，S 中剩下的元素是 4， 6，8，9，10。哪些应该放在第 2 层呢？根据盖住关系，应该是 4，6，9 和 10。 因为 4 盖住，2，6 盖住 2 和 3，9 盖住 3，10 盖住 2 和 5. 8 不盖住 2，3，5，7 中的任何一个元素， 最后只剩下一个 8 放在第 3 层。图 4.5 给出了最终得到的哈 斯图。 在整除关系的哈斯图中， 盖住关系体现为最小的倍数或最小的公倍数关系。 如果偏序集是 ? P( A), ?? ，那么哈斯图的结构将呈现出十分规则的形式。第 0 层是空集 ? ，第 1 层是所有的单元集，第 2 层是所有的 2 元子集，…，直到最 高层的集合 A。这里的盖住关系就体现为包含关系。在画哈斯图时应该注意下面几个问题。 1°哈斯图中不应该出现三角形，如果出现三角形，一定是盖住关系没有找51对。 纠正的方法是重新考察这 3 个元素在偏序中的顺序中的顺序，然后将不满足 盖住关系的那条边去掉。请看图 4.6(1)中的哈斯图。图中有两个三角形，即三 角形 abc 和 abd。根据结点位置可以看出满足如下的偏序关系：a ? b, a ? c, b ? c, a ? d , b ? d从而得到 a ? b ? c 和 a ? b ? d 。这就说明 c 和 d 不盖住 a，应该把 ac 边和 ad 边从图中去掉，从而得到正确的哈斯图，如图 4.6(2)所示。 2° 哈斯图中不应该出现水平线段。根据哈斯图的层次结构，处在同一水平 位置的结点是同一层的，它们没有顺序上的“大小”关系，是不可比的。出现这 种错误的原因在于没有将“较大”的元素放在“较小”元素的上方。纠正时只要 根据“大小”顺序将“较大”的元素放到更高的一层，将水平线改为斜一就可以 了。 3° 哈斯图中应尽量减少线的交叉，以使得图形清晰、易读，也便于检查错 误， 图形中线的交叉多少主要取决于同一层结点的排列顺序， 如果出现交叉过多， 可以适当调正结点的排列顺序，注意变动结点时要同时移动连线。 最后谈谈怎样确定哈斯图中的极大元、极小元、最大元、最小元、最小上界 和最大下界，具体的方法是： 1° 如果图中有孤立结点，那么这个结点既是极小元，也是极大元，并且图 中既元最小元，也元最大元（除了图中只有唯一孤立结点的特殊情况） 。 2° 除了孤立结点以外， 其他的极小元是图中所有向下通路的终点，其他的 极大元是图中所有向上通路的终点。 3° 图中唯一的极小元是最小元，唯一的极大元是最大元；否则最小元和最 大元不存在。 4° 设 B 为偏序集 ? A, ?? 的子集，若 B 中存在最大元，它就是 B 的最小上 界； 否则从 A-B 中选择那些向下可达 B 中每一个元素的结点， 它们都是 B 的上界， 其中的最小元是 B 的最小上界。类似地可以确定 B 的最大下界。 观察图 4.5,1 是所有向下通路的终点，是极小元，也是最小元，向上通路的 终点有 9，6，8，10 和 7，这些是极大元。由于极大元不是唯一的，所以，没有 最在元。地于整个偏序集的最小上界和最大下界，就是它的最在元和最小元，因 此，该偏序集没有最小上界，最大下界是 1。524.7 4.8A：④； B：⑤； C：③； D：①； E：⑦ A：②； B：①； C：④； D：②； E：⑨分析 给定函数 f : A ? B ， 怎样判别它是否满足单射性呢？通常是根据函数 的种类采取不同的方法。 1° 若 f : A ? B 是实数区间上的连续函数，那么，可以通过函数的图像来 判别它的单射性。如果 f 的图像是严格单调上升（或下升）的，则 f 是单射的。 如果在 f 的图像中间有极大或极小值，则 f 不是单射的。 2° 若 f 不是通常的初等函数。那么，就须检查在 f 的对应关系中是否存在 着多对一的形式，如果存在 x1 , x2 ? A, x1 ? x2 但 f ( x1 ) ? f ( x2 ) ，这就是二对一， 即两个自变量对应于一个函数值，从而判定 f 不是单射的。 下面考虑满射性的判别，满射性的判别可以归结为 f 的值域 ranf 的计算。 如果 ranf ? B ，则 f : A ? B 是满射的，否则不是满射的。求 ranf 的方法说明如 下： 1° 若 f : A ? B 是实数区间上的初等函数，为了求 ranf 首先要找到 f 的单 调区间。 针对 f 的每个单调区间求出 f 的该区音的最小和最大值，从而确定 f 在 这个区间的局部值域。 ranf 就是所有局部值域的并集。对于分段的初等函数也 可以采用这种方法处理。 2° 若 f 是用列元素的方法给出的，那么 ranf 就是所有有序对的第二元素 构成的集合。 本题中只有 f 1 是定义于实数区间上的初等函数。 易见， 指数函数的图像是严 格单调上升的，并且所有的函数值都大于 0。从而知道 f 1 是单射的，但不是满射 的。对于 f 2 ，由f 2 (1) ? f 2 (?1) ? 1 可知，它不是单射的。但 ranf 2 ? N ，所以，它是满射的。 f 3 既不是单射的， 也不是满射的， 因为 f 3 (3) ? f 3 (0) ? 0, 且 f 3 ? {0,1,2}. f 4 是53单 射 的 ， 但 不 是 满 射 的 。 因 为 m ? n 时 , 必 有 ? m, m ? 1 ??? n, n ? 1 ?, 但? 1,1 ?? ranf 4 .4.9 A：③； B：①； C：⑦； D：⑤； E：⑨分析（1） 先求出 T 的特征函数 ? T ? {? a,1 ?, ? b,1 ?, ? c,0 ?} ， 它是从 S 到 {0,1} 的函数。而 S s 中的函数是从 {a, b, c} 到 {a, b, c} 的函数，这就是说该函数应包含 3 个有序对，有序对的第一元素是 a, b, c ，而第二元素应该从 a, b, c 中选取（可以重 复选取） 。不难年出只有①满足要求。 （2） 等价关系 R 对应的划分就是商集 S/R。 检查 R 的表达式， 如果 ? x, y ?? R ， 那么 x,y 就在同一个等价类。不难看出 S 中的元素被划分成两个等价类：{a, b},{c} ，因而对应的划分有 2 个划分块。考虑自然映射 g : S ? S / R, 它将 S 中的元素所在的等价类，即将 a 映到[a] ? {a, b} ，将 b 映到 [b] ? {a, b} ，将 c 映到 [c] ? {c} ，将 g 写成集合表达式就是 g ? {? a,{a, b} ?, ? b,{a, b} ?, ? c{c} ?}.通常的自然映射是满射的，但不一定是单射的，除非等价关系为恒等关系， 这时每个等价类只含有一个元素，不同元素的等价类也不同，g 就成为双射函数 了。 4.11 (1)R ? {? 1,1 ?, ? 1,2 ?, ? 1,3 ?, ? 1,4 ?, ? 1,5 ?, ? 1,6 ?, ? 2,2 ?, ? 2,4 ?, ? 2,6 ?, ? 3,3 ?, ? 3,6 ?? 4,4 ?, ? 5,5 ?, ? 6,6 ?}.(2)R ? {? 1,1 ?, ? 2,1 ?, ? 2,2 ?, ? 3,1 ?, ? 3,3 ?, ? 4,1 ?, ? 4,2 ?, ? 4,4 ?, ? 5,1 ?, ? 5,5 ?, ? 6,1 ?? 6,2 ?, ? 6,3 ?, ?`6,6 ?}.(3) R ? {? 1,2 ?, ? 1,3 ?, ? 2,1 ?, ? 2,3 ?, ? 2,4 ?, ? 3,1 ?, ? 3,2 ?, ? 3,4 ?, ? 3,5 ?,? 4,2 ?, ? 4,3 ?? 4,5 ?, ? 4,6 ?, ? 5,3 ?, ? 5,6 ?, ? 6,4 ?, ? 6,5 ?}. ]544.12 4.13对称性R1 ? R2 ? {? c, d ?},R2 ? R1 ? {? a, d ?, ? a, c ?},R12 ? {? a, a ?, ? a, b ?, ? a, d ?},3 R2 ? {? b, c ?, ? c, b ?, ? b, d ?},4.14图 4.7 分析 根据闭包的计算公式r ( R) ? R ? R 0 , s( R) ? R ? R ?1 , t ( R) ? R ? R 2 ? ?可以得到由关系图求闭包的方法. 设 G 是 R 的关系图,G 的结点记为 x1 , x2 ,?, xn , r ( R), s( R), t ( R) 的关系图分别记 作 Gr , G s 和 G t . 为求 Gr ,先将图 G 的结点和边拷贝到 Gr 中缺少环的结点都加上环就得到了r ( R) 的关系图.为求 G s ,也须将图 G 拷贝到 G s ,然后检查 G s 的每一对结点 xi 和 x j (i ? j ) .如 果在 xi 和 x j 之间只存在一条单向的边 ,就在这两个结点间加上一条方向相反的 边.当 G s 中所有的单向边都变成双向边以后就得到了 s( R) 的关系图. 最后拷虑 Gt .首先将图 G 拷贝到 Gt ,然后从 x1 开始依次检查 x1 , x2 ,?, xn .在55检查结点 xi (i ? 1,2,?, n) 时，要找出从 xi 出发经过有限步（至少 1 步，至多 n 步） 可达的所结点（包括 xi 自己在内） 。如果从 xi 到这种结点之间缺少边，就把这条 边加到 Gt 中，当 n 个结点全部处理完毕，就得到 t ( R) 的关系图。 以本题为例，依次检查结点 a, b, c, d . 从 a 出发可达 b, c, d , e 四个结点，所以图Gt 中应该加上 a ? c, a ? d 和的边。从 b 出发可达 c, d , e 三个结点，所以，图 Gt中应该加上 b ? d 的边。从 c 出发可达 c 和 d，在 Gt 中应该加上边 c ? c ，即通 过 c 的环，类似地分析可以知道，在 Gt 中还应该加上过 d 的环。 4．15 若 S 不是单元集，则 P(S ) ? {?} 不构成 S 的划分。 4．16 在图 4.8（1）中极小元、最小元是 1，极大元、最大元是 24，在图 4.8(2)中极小元、最小元是 1，极大元是 5，6，7，8，9，没有最大元。4．17 （1）不能； （2）能； 分析（3）不能。函数和关系的区别在于它们的对应法则。在关系 R 的表达式中，如果? x, y ?? R ，就说 x 对应到 y，对于二元关系 R，这种对应可以是一对一的，多对一的和一对多的。这里的一对多指的是一个 x 对应到多个 y，但是对于函数， 则不允许这种一对多的对应。至于单射函数，不但不允许一对多，也不允许多对 一，只能存在一对一的对应。为了判别一个关系是否为函数，就要检查关系的对 应中是否存在一对多的情况。如本题中的（1）式，&1,2&和&1,1&同时在关系中 出现，因此不是函数。又如（3）式，&1,1&和&1,-1&也同时在关系中出现，破坏 了函数定义。 4．18 当 R ? I S 时满足要求。564．19 f ? f , g ? f , f ? g , h ? g , f ? g ? h ? N N ，且f ? f (n) ? n ? 2. f ? g (n) ? 2n ? 1. g ? f (n) ? 2n ? 2,h ? g (n) ? 0,?0 n为偶数 g?h ? ? ?2 n为奇数, ?1 n为偶数 f ? g ? h ( n) ? ? ?3 n为奇数.分析 注意合成的正确表示方法。表示 f 和 g 合成的方法有两种： 1°说明 f ? g 是从哪个集合到个集合的函数， 然后给出 f ? g ( x) 的计算公式。 2° 给出 f ? g 的集合表达式。 本题中的结果都采用了第一种表示方法， 先说明地果函数是从 N 到 N 的函数， 然后分别给出函数值的计算公式。也可以彩用第二种方法，如f ? f ? {? n, n ? 2 ?| n ? N} ,f ? g ? h ? {? x,1 ?, ? y,3 ? z | x, y ? N且x为偶数, y为奇数}.但是，如果写成 f ? f ? n ? 2 就错了，因为 f ? f 是函数，是有序对的集合， 与函数值 f ? f (n) 是根本不同的两回事，不能混为一谈。 4．20 f ?1 : R ? R ? R ? R,f ?1 (? x, y ?) ??分析 首先由 f 的双射性确定 f?1x? y x? y , ?. 2 2一定存在，然后通过 f 的定义求出反函数的对应法则。设 f 将 ? x, y ? 对应到 ? u, v ? 。根据 f 的定义有? u, v ??? x ? y, x ? y ?? x ? y ? u ? x ? y ? v ? 2x ? u ? v ? 2 y ? u ? v ? x ? u?v u?v ?y? . 2 2因而反函数的对应法则是 ? u, v ? 对应到 4．21 （1） 如下列出 g ? f 的对应关系57u?v u?v 。 , 2 2xf ( x)0 1 31 2 12 3 33 4 24 0 05 5 36 6 37 7 38… 8… 4…g ( f ( x))从而得到g? f :N ?N? ?3 ? ?1 ? g ? f ( x) ? ?2 ?x ? ?2 ? ?0x ? 0,2或大于等于5的奇数 x ?1 x?3 x ? 6且x为偶数 x?4g ? f 是满射的，但不是单射的。（2） g ? f ({0,1,2}) ? {1,3}. 4．22 （1） P( A) ? {?,{a},{b},{a, b}},B A ? { f1 , f 2 , f 3 , f 4 }, 其中f1 ? {? a,0 ?,{b,0 ?, f 2 ? {? a,1 ?,{b,0 ?,f 2 ? {? a,0 ?? b,1 ?},f 4 ? {? a,1 ?? b,1 ?},（2）令 f : P( A) ? B A ，且f (?) ? f1 , f ({a}) ? f 2 , f ({b}) ? f 3 , f ({a, b}) ? f 4分析对于任意集合 A，都可以构造从 P( A) 到 {0,1} A 的双射函数，任取 A 的子集 B ? P( A), B 的特征函数 ? B : A ? {0,1} 定义为? B ( x) ? ??1 x ? B ?0 x ? A ? B不同的子集的特征函数也不同，因此，令? : P( A) ? {0,1} A ? ( B) ? ? B? 是 P( A) 到 {0,1} A 的双射，在本题的实例中的 ? 是 ? (?) ? f1 , ? ({a}) ? f 3 ,58? ({b}) ? f 2 , ? ({a, b}) ? f 4 .4．23 （1） f : A ? B, f ( x) ? 2 x （2） f : A ? B, f ( x) ? sin x. 分析 处理。 1° 若 A，B 都是有穷集合，可以先用列元素的方法表示 A，B，然后顺序将 A 中的元素与 B 中的元素建立对应，如习题 4.22. 1° 若 A，B 都是有穷集合，可以先用列元素的方法表示 A，B，然后顺序将 A 中的元素与 B 中的元素建立对应，如习题 4.22。 2° 若 A，B 是实数区间，可以采用直线方程 作为从 A 到 B 的双射函数。 例如，A ? [1,2], B ? [2,6] 是实数区间。 如图 4.9 所示，先将 A，B 区间分别标记在直角坐标系的 x 轴和 y 轴上，过（1，2）和（2，6）两点的直线方 程将 A 中的每个数映到 B 中的每个数，因此，该直线方程所代表的一次函数就是 从 A 到 B 的双射函数。由解析几何的知识可以得到双射函数f : A ? B, f ( x) ? 4 x ? 2.给定集合 A，B，如何构造从 A 到 B 的双射？一般可采用下面的方法这种通过直线方程构造双射函数的方法对任意两个同类型的实数区间(同为 闭区间、开区间或音开半闭的区间)都是适用的。但对半开半闭的区间要注意开 端点与开端点对应，闭端点与闭端点对应。此外还要说明一点，对于某些特殊的 实数区间可能选择其他严格单调的初等函数更方便，例如，A ? [?1,1], B ? [?? ?, ] ，那么取 f ( x) ? arcsin x 即可。 2 23°A 是一个无穷集合，B 是自然数集 N。 为构造从 A 到 B 的双射只须将 A 中的元素排成一个有序序列， 且指定这个序 列的初始元素，这就叫做把 A “良序化” 。比如说 A 良序化以后，是集合{x0 , x1 , x2 ?} ，那令 f : A ? B, f ( xi ) ? i, i ? 0,1,2,? f 就是从 A 到 B 的双射。59例如， 构造从整数集 Z 到自然数集 N 到自然数集 N 的双射。如下排列 Z 中元 素，然后列出对应的自然数，即Z : 0,?1,1,?2,2,?3,3,? Z : 0, 1,2,?2,2,3,4, ,5,6?观察这两个序列，不难找到对应法则。x?0 ?2 x f : Z ? N , f ( x) ? ? ?? 2 x ? 1 x ? 0显然 f 是从 Z 到 N 的双射。 最后要指出，并不是任何两个集合都可以构造双射的。比如说，含有元素不 一样多的有穷集之间不存在双射。即使都是无穷集也不一定存在双射，如实数集 R 和自然数集 N 之间就不存在双射。 这就涉及到集合 “大小” 的描述和度量方法， 限于篇幅地此就不进行探入讨论了，有兴趣的读者可以阅读其他的《离散数学》 书籍。 4．24 f1 ( x) ? f1 ( y) ? x ? y, R1 为 N 上的恒等关系，且有N / R1 ? {{n}} | n ? N}. f 2 ( x) ? f 2 ( y) ? x 与 y 的奇偶性相同。在 N 中的所有奇数构成一个等价类，所有的偶数构成另一个等价类。因此，N / R2 ? {{2n | n ? N},{2n ? 1 | n ? .N}}.f 3 ( x) ? f 3 ( y) ? x ? y(mod 3) ，即 x 除以 3 的余数与 y 除以 3 的余数相等。根据余数分别这 0，1，2，可将 N 中的数分成 3 个等价类，因而N / R3 ? {{3n | n ? N},{3n ? 1 | n ? .N}}.4．25 （1） f ? g : N ? R, f ? g ( x) ? x 2 ? x60f ? g 不是单射也不是满射。 f ? g ( A) ? {2,12,30,56,90} f ? g ( B) ? {0} 。（2） f ? g : Z ? R, f ? g ( x) ? e xf ? g 不是单射也不是满射。2f ? g ( A) ? {e n | n ? N}. f ? g ( B) ? {e4n | n ? N}.2261第5章习题解答5.1 分析A:③; B:⑥; C:⑧; D:⑩; E:⑨ S 为 n 元集,那么 S ? S 有 n 2 个元素.S 上的一个二元运算就是函数2f : S ? S ? S .这样的函数有 n n 个.因此 {a, b} 上的二元运算有 n n ? 16 个.2下面说明通过运算表判别二元运算性质及求特导元素的方法. 1 °交换律 律. 2 °幂等律 设运算表表头元素的排列顺序为 x1 , x2 ,? xn , 如果主对角线元 若运算表中元素关于主对角线成对称分布,则该运算满足交换素的排列也为 x1 , x2 ,? xn , 则该运算满足幂等律. 其他性质,如结合律或者涉及到两个运算表的分配律和吸收律 ,在运算表中 没有明显的特征,只能针对所有可能的元素 x, y, z 等来验证相关的算律是否成立. 3 ° 幺元 e. 设运算表表头元素的排列顺序为 x1 , x2 ,? xn , 如果元素 xi 所在的 行和列的元素排列顺序也是 x1 , x2 ,? xn , 则 xi 为幺元. 4 ° 5 ° 零元 ? . 如果元素 xi 所在的行和列的元素都是 xi ,则 xi 是零元. 幂等元.设运算表表头元素的排列顺序为 x1 , x2 ,? xn , 如果主对角线上第 i 个元素恰 为 xi i ? {1,2,?, n} 那么 xi 是幂等元.易见幺元和零元都是幂等元. 6 ° 可逆元素及其逆元.设 xi 为任意元素,如果 xi 所在的行和列都有幺元, 并且这两个幺元关于主对角线成对称分布,比如说第 i 行第 j 列和第 j 行第 i 列的 两个位置, 那么 x j 与 xi 互为逆元 .如果 xi 所在的行和列具有共同的幺元 , 则幺元 一定在主对角线上,那么 xi 的逆元就是 xi 自己.如果 xi 所在的和地或者所在的列 没有幺元 ,那么 x i 不是可逆元素. 不难看出幺元 e 一定是可逆元素 ,且 e ?1 ? 而 零元 ? 不是可逆元素. 以本题为例, f1 , f 2 , f 3 的运算表是对称分布的,因此,这三个运算是可交换的,62而 f 4 不是可交换的.再看幂等律.四个运算表表头元素排列都是 a, b ,其中主对角 线元素排列为 a, b 的只有 f 4 ,所以, f 4 遵从幂等律.下面考虑幺元.如果某元素所 在的行和列元素的排列都是 a, b ,该元素就是幺元.不难看出