离散数学合取和条件的区别_百度知道
离散数学合取和条件的区别
到底什么时候应该用合取 什么时候应该用条件? 有什么一般性的规律可循吗?比如:A(x)表示x是有素质的
B(x)表示x是受过教育的---问题---受过教育的人是有素质的---这句话的表达应该是条件:B(x)--&A(x)还是合取B(x)∧A(x)?
如果x受过教育则x是有素质的。用B(x)--&gt，可表示为(&#8704一般的，对全称量词用条件来连接，对存在量词用合取。如果没有这个的话就可以这样来判断如;x)(B(x)--&A(x)),如果改成存在一些受过教育的人是有素质的则表示为（∃x）(B(x)∧A(x))。如全部受过教育的人都是有素质的
采纳率：35%
只有Q；除非Q；条件相当于因果，条件与全称量词搭配，即如果满足A，那么肯定满足B。条件语句常用形式：B(x)--&gt，合取与存在量词搭配。受过教育的人是有素质的：只要P，就Q；因为P，所以Q；P仅当Q，才P；除非Q，才P，否则非P。至于规律合取相当于“并”，即A与B要同时满足
为您推荐：
其他类似问题
您可能关注的内容
合取的相关知识
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。理解析取范式及合取范式的意义
时间： 19:01:50
&&&& 阅读：354
&&&& 评论：
&&&& 收藏：0
标签：&&&&&&&&&& & 初学离散数学的同学一定会对析取范式与合取范式的意义有所困惑。首先单就它的使用环境来分析，析取范式有一点想电路里的或门，合取范式有一点像电路里的与门。而且它们的真值表是一模一样的。我们就会纳闷，怎么不叫“或取范式”、“与取范式”，这样不是更加的明了直观吗？& & 当然它这么叫肯定是有它的道理在的。要不然，离散数学就不像离散数学了，而是像电路离散数学了。& & 离散数学，作为多门学科的一个核心指导学科。它有很强概括作用和实际作用。很多你很费劲才能搞懂的问题，用了离散数学，你就会发现其中简单的东西来。在这里“析取”与“合取”也具有这样的意义在，它把“或”与“与”进行了一个概念的提升，“析取”，其实顺其自然，我们可以把它理解成，“析而取之”，当然“合取”我们把它理解成“合而取之”。如果对我们古文很熟悉的同学，一定会瞬间理解其中的意义。& & 当然，在这里我们把它翻译成大白话。就是，通过分析，来对其取舍，来选择其中的某一个（析取范式）。以及把所有的东西放在一起进行考虑，从而得到他们的一个整体的结果。（合取范式）当然，对于一个要求十分严格的人来说，一定要，都对才会罢休，那么那个人是谁呢？他就是：“离散数学！”标签：&&&&&&&&&原文：http://stickydream.blog.51cto.com/4505
教程昨日排行
&&国之画&&&& &&&&&&
&& &&&&&&&&&&&&&&
鲁ICP备号-4
打开技术之扣，分享程序人生！The requested URL '/xueask-790-7904644.html' was not found on this server.当前位置： >>
离散数学第四版 课后答案
离散数学第四版 课后答案 第 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 为真。 21．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” 仅当 q” “p “只有 q 才 p” “除非 q，否则? “没有 q，就没有 p”等都表 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 个命题变项，因而它应该有 23=8 个赋值：000， 3 001，?，111 题中指派 p, q 为 0, r 为 1，于是就是考查 001 是该公式 p∧(q∧r)的成真赋值， 还是成假赋值，易知 001 是它的成假赋值。 2° 在公式 （2） 3） 4） ， ， 中均含 4 个命题就项， （ （ 因而共有 24=16 个赋值： 0000， 0001， ?， 1111。现在考查 0011 是它的成假赋值。 1.7 （1）（2）（4）（9）均为重言式， ， ， ， ， （3）（7）为矛盾式， ， ， ， （5）（6）（8）（10） 为非重言式的可满足式。一般说来，可用真值表法、等值演算法、主析取范式（主合取范式）法等判断公式的类 型。 （1）对（1）采用两种方法判断它是重言式。 真值表法 表 1.2 给出了（1）中公式的真值表，由于真值表的最后一列全为 1，所以， （1）为重言 式。 p∨q∨r p 0 0 0 0 1 1 1 1 q 0 0 1 1 0 0 1 1 p→(p∨q∨r) r 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1等值演算法 p→(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 ?? ∨q)∧q (p? ? p∨? q∧q ? p∨(? q∧q) ? p∧0 ?0 （蕴含等值式） （德?摩根律） （结合律）（矛盾律） （零律）由最后一步可知， （3）为矛盾式。 （5）用两种方法判（5）为非重言式的可满足式。 真值表法 p 1 0 1 1 q ? p ? p→q q→? p (? p→q)→(q→? p)0 0 1 0 11 0 11 0 01 1 11 1 01 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 的 o 真值表的最后一旬全为 1；A 为矛盾式当且仅当 A 的真值表的最后一列全为 0；A 为非重言 式的可满足式当且仅当 A 的真值表最后一列至少有一个 1，又至少有一个 0。真值表法不易 出错，但当命题变项较多时，真值表的行数较多。 2o 用等值演算法判断重言式与矛盾式比较方例，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 的主析取范式含 2n （n 为 A 中所含命题变项的个数）个极小项；A 为矛盾式当且仅当 A 的主析取范式中不含 任何极小项， 记它的主析取范式为 0； 为非重言式的可满足式当且仅当 A 的主析取范式中 A 含极小项，但不是完全的。 当命题变项较多时，用主析取范式法判公式的类型，运算量是很大的。 用主合取范式判断公式的类型也是万能的。A 为重言式当且仅当 A 的主合取范式中不 含任何极大项，此时记 A 的主合取范式为 1；A 为矛盾式当且仅当 A 的主合取范式含 2n 个 极大项（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∧? p)∧q （矛盾式）?0. （德?摩根律）? p∧q∧? p （零律）8 由最后一步可知该公式为矛盾式。 （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， H， 都是 2 元真值函数。 G， R 给出的 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∧? 记为 B. q 则 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.4 11 p 0 0 1 1 q 0 1 0 1 A 0 0 1 0 B 0 0 1 1 C 0 0 1 1 AVC 0 0 1 1 0 0 1 1 BVC(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 1.12 (1) 设(1)中公式为 A. A?(p∨(q∧r))→(p∧q∧r) (双重否定律) (? A?? B) (双重否定律)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∨m7 12 于是,公式 A 的主析取范式为 m0∨m1∨m2∨m7 易知,A 的主合取范式为 M3∨M4∨M5∨M6A 的成真赋值为 000, 001, 010, 111A 的成假赋值为 011,100,101,110(2)设(2)中公式为 B B?(? 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 的主合取范式为 M1 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 的主合取范式为 M0∧M1∧M2∧M3 C 的成假赋值为 00,01,10,11 C 无成真赋值,C 为矛盾式. 分析 1° 设公式 A 中含 n(n≥1)个命题变项,且 A 的主析取范式中含 l(0≤l≤2n)个极 小项,则 A 的主合邓范式中含 2n?l 个极大项,而且极大项的角标分别为 0 到 2n?1 这 2n 个十 进制数中未在 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).由于演算过程较长,可以分别先求出由? q,r 派生的极小项.注意,本公式中含 3 个命题 p,? 变项,所以,极小项长度为 3.14 ? p?? p∧(? q∨q)∧(? r∨r) ?(? 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∨m5 r?(? 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) 15 ?m0∨m1∨m2. ②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 A 0 0 0 0 1 q B 0 0 1 1 0 r C 0 1 0 1 0 0 0 0 0 1 0 1 1 0 0 1 0 0 0 0 F F F1 1 10 1 11 0 11 1 10 0 00 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 16 ?? (p∧q) ? ?? (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,17 或 ? A?? (A∨A)?A↓A.使用双重否定律 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) 18 ?(? p∧? q∧p∧? r∧p∧r) ∨(? p∧? q∧p∧r∧? p∧? r) ?0∨0?0 F3?(甲对一半)∧(乙全对)∧(丙全错) ?((? 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)19?(p∧q∧? p∧r∧p∧r∨(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 (1)证明 ①? q∨r ②? r ③? q前提引入前提引入 ①②析取三段论④? (p∧? q) 前提引入 ⑤? p∨q ⑥? p （2） 证明 ①p→(q→s) 前提引入 ②q→(q→s) ③q ④p→s ⑤p∨? r 21 ⑥r→ p ⑦r→s （3） 证明 ①p ③q ④p∧q 或者 证明 ①p→q ③(? p∨p)∧(? p∨q) ②置换 前提引入②? p∨q ①置换 附加前提引入②p→q ①②假言推理 ①③合取 前提引入 ⑤置换 ④⑥假言三段论 ①置换 前提引入 ②③假言推理 前提引入 ④置换 ②⑤析取三段论④? p∨(p∧q) ⑤p→(p∧q) （4） 证明 ① ③ ④t∧r ⑤t ⑥s ⑧(q→s)∧(s→q) ⑨s?q ⑩q ②化简③置换 ④置换前提引入②(s→t)∧(t→s)①置换前提引入③⑤假言推理⑦ ⑦置换 ⑧化简 ⑥⑨似言推理?q? p前提引入前提引入22 ?r?p ④化简⑩? 假言推理?p∧q∧s∧r 分析 由于⑥⑩??合取(A1∧A2∧L∧Ak)→(C→B) ?? (A1∧A2∧L∧Ak)∨(? C∨B) ?? (A1∧A2∧L∧Ak∧C)∨B ?A1∧A2∧L∧Ak∧C→B 所以,当推理的结论也为蕴含式时,可以将结论的前件作为推理的前提,称为附加前提,并 称使用附加前提的证明方法为附加前提证明法.(3)中第一个证明,即为附加前提证明法. 1.18 设 p：他是理科生q：他是文科生 r：他学好数学 前提 p→r,? q→p,? r 结论 q 通过对前提和结论的观察，知道推理是正确的，下面用构造证明法给以证明。 证明 ① p→r ? 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 答案 A：③； B：④； C：②分析 解本题的方法不限于求主析取范式或主合取范式，也可以利用真值表法。 方法 1： 求主析取范式 ? (p∧q)→r?(p∧q)∨r ?(p∧q)∧(r∨? r)∨(p∨? p)∧(q∨? q)∧r ?m1∨m3∨m5∨m6∨m7 从上式可知，? (p∧q)→r 的主析取范式中含 5 个极小项。极小项角码的二进制表示为成 真赋值，因而成真赋值为 001，011，101，110，111。由成真赋值立即可知成假赋值为 000， 010，100，成假赋值的十进制的十进表示为极大项的角码，因而极大项为 M0,M2,M4， 故有 3 个极大项。 方法 2：求主合取范式，分析类似主析取范式法。 方法 3：真值表法 由真值表，求出成真赋值，将成真赋值转化成十进制数做为极小项的角码，这样就求出 了全部极小项，也容易求出极大项。 1．21 答案 A：③； B：⑤； C：⑥分析 可用构造证明法解此题。 （1） ①? q∨r ②? r ③? q 前提引入前提引入 ①②析取三段论24 ④? (p∧? q) 前提引入 ⑤? p∨q ⑥? p ④置换 ③⑤析取三段论至此可知? 是（1）的逻辑结论。 p （2） ①? r∨s ②? s 前提引入 前提引入③? r①②析取三段论④(p∧q)→r 前提引入 ⑤? (p∧q) ⑥? p∨? q ④置换 ⑤置换至此可知? p∨? 是（2）的国逻辑结论。 q （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=x2+2x+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, 题。 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）取解释 I1 为：个体域 D=R（实数集合） ，F(x):x 为有理数，G(x):x 能表示成分 数，在 I1 下，?x(F(x)→G(x))的含义为 “对于叙何实数 x 而言，若 x 为有理数，则 x 能表示成分数” ，简言之为“有理数都能表 示成分数。 ”在此蕴含式中，当前件 F(x)为真时，后件 G(x)也为真，不会出现前件为真，后 件为假的情况，所以在 I1 下，?x(F(x)→G(x))为真命题。 在在 I1 下，?x(F(x)∧G(x))的含义为 “对于任何实数 x,x 既为有理数，又能表示成分数。 ” 取 x= 2，则 F( 2)∧g( 2)显然为假，所以，在 I1 下，?x(F(x)∧G(x))为假命题. (2) 取解释 I2 为:个体域 D=N(自然数集合), F(x):x 为奇数, G(x):x 为偶数,在 I2 下,?x(F(x) ∧G(x))的含义为 “存在自然数 x,x 发既为奇数，又为偶数。 ” 取 x=2，则 F(2)为假，于是 F(2)→G(2)为真，这表明?x(F(x)→G(x)为真命题。 ?y=0，在(a),(b)中为真命题，在(c),(d)中为假命分析 本题说明 ?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?2y). 易知，在解释 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 为闭式。 给定解释 I1：个体域 D=N（整数集合） ，F(x):x 为正数，G(x):x 为负数，L(x,y):x&y， 在 I1 下，A 的含义为 31 “对于任意的整数 x 和 y，如果 x 为正整数，y 为负整数，则 x&y。 ” 这是真命题。 设解释 I2：个体域 D=R（R 整数集合） ，F(x):x 为有理数，G(y):y 为无理数，L(x,y):x≤ y，在 I2 下，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 ， ?yL(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)∧?z2? G(x,z2) ??z1?z2(? F(z1,y)∧? G(x,z2) 在以上演算中分别使用了德?摩根律、量词否定等值式、约束变项换名规则等。 分析 公式的前束范式是不唯一的。 （1）中最后两步都是前束范式，其实?y?z(F(z) ∨G(x,y))也是（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) 前提引入 前提引入 ①② 假言推理 ②EI ④附加⑥F(c)∨G(c))→R(c) ⑦R(c) ⑧?xR(x) （2）证明： ①?xF(x) ② F(c)③UI ⑤⑥假言推理 ⑦ EG前提引入 ①EI37 ③ ? x(F(x) → (G(y) ∧ R(x))) ③UI ⑤ G(y) ∧ R(c) ⑤ 化 简 ⑦ F(c) ∧ R(c) ⑦ EG 2．18 令 F(x):x 是大熊猎。 G(x):x 产在中国。 a:欢欢 前提：?x(F(x)→(G(x)),F(a) 结论：G(a) 证明： ① ? x(F(x) → G(x)) 前提引入③F(a)→G(a) ④G(a) G(x):x 为实数。 H(x):x 为整数。 前 提 引 入 ② ①UI ②③假言推理 2．19 令 F(x):x 为有理数。 F(a) 前 提 引 入 ④ F(c) → (G(y) ∧ R(c))② ④ 假 言 推 理 ⑥ R(c) ② ⑥ 合 取 ⑧ ? x(F(x) ∧ R(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?x(F(x,z)→G(x,y)) ??x?y(F(x,z)→G(x,y)) 所以，⑧也是（3）的前束范式。 2．22 答案 A：⑤。 （将自由出现的 y 改名为 z）分析 （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 A：③； B：④； C：⑤； D：⑦；E：⑧ 3.2 A：③；B：①； 3.3 A：①；B：③； 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”则意味着 AIB=?。 例如，3.1 题（3）和 3.2 题（3）都是这种形式。 3° 通过集合运算差别 B?A,如果 AUB=A， BIA=B， B?A=?三个等式中有任何一个成立， 则有 B?A.。 4° 通过文氏图观察，如果代表 B 的区域落在代表 A 的区域内部，则 B?A.。42 这后两种方法将在后面的解答中给出实例。 3.4 A：②； B：④； C：⑦； D：⑥；E：⑧3.5 A：②；B：④； 3.6 A：①；B：⑨； 3.7 A：④；B：⑨；C：⑤； D：⑥； E：⑨ C：④； D：⑦； E：⑧ C：①； D：⑧； E：①分析 设只买 1 本、2 本及 3 本书的学生集合分别为 S1,S2 和 S3，它们之间两两不交， 由题意可知， |S3|=20, |S2US3|=55.又知|S2IS3|=?,所以, |S2|=|S2US3|?|S3|=55?20=35. 然后列出下面的方程: |S1|+2|S2|+3|S3|=140 求得|S1|=10.因此,没有买书的人数是 75-(10+35+20)=10. 3.8 (1)和(4)为真,其余为假. 分析 这里可以应用集合运算的方法来差别集合之间的包含或相等关系.如题(3)中的条 件 S?T=?意味着, S?T,这时不一定有 S=T 成立.而对于题(4),由条件~SUT=E 可推出 SI(~SUT)=SIE?(SI~S)U(SIT)=S ??U(SIT)=S?SIT =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)中的 A={x|x?N∧? 2≤x≤ 2},B={1,1}. 2 而对于题(4),不难看出 A=B=R,是实数集合. 3.13 (1) AUB={{a,b},c,d}, AIB={c}. A?B={{a,b}}, AB={{a,b}},d}.(2) AUB={{a{b}},c,{c},{a,b},{b}}. AIB={{a,b},c}, A?B={{a,{b}},{c}}, AB={{a{b},{c},{b}}. (3) AUB=N,AIB={2},A?B={0,1}AB=N?{2} (4)观察到 B?A,故 44 AUB=A,AIB=B,AB=A?B={x|x?R?Z∧x&1}. (5) 观察到 AIB=?,故 AUB=Z?{0,1} AIB=? A?B=A AB=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∧x3?2x2?x+2=0}化简为 A={?1,1,2}。 3．1545 3．16 （1）（2）（3）和（6）为真。 ， ， （4）和（5）不为真。 分析 如果给出的是集合恒等式， 可以用两种方法验证。 一是分别对等式两边的集合画 出文氏图， 然后检查两个图中的阴影区域是否一致。 二是利用集合恒等式的代入不断对等式 两边的集合公式进行化简或者变形，直到两边相等或者一边是另一边的子集为止。例如，题 （1）中的等式左边经恒等变形后可得到等式右边，即 (AUB)?C=(AUB)I~C =(AI~C)U(BI~C)=(A?C)U(B?C) 类似地，对题（2）和（3）中的等式分别有 A?B(B?C)=AI~(BI~C) =AI(~BUC)=(AI~B)U(AIC) =(A?B)UAIC) A?(BUC)=(A?B)I(A?C) =(A?B)I(AI~C)=((A?B)IA)I~C =(A?B)I~C=(A?B)?C 但对于等式（4） ，左边经变形后得 (AUBUC)?(AUB)=((AUB)?(AUB))U(C?(AUB)) =?U(C?(AUB))=C?(AUB). 易见，C?(AUB)?C,但不一定有 C?(AUB)=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={1},B={1,4},C={2},D={2,3},则 A?B 且 C?B，但 AIC=BID，与结论矛盾。46 分析 （2）由于 C?D?~D?~C,又由 A?B 可得 AIC~D?BI~C,即 A?D?B?C 成立。 （3）由于 AU(B?A)=AUB，故有 B=AU(B?A)?B=AUB?A?B。 这里用到 A?B 的充要条件为 B=AUB 或 B=AIB 或 A?B=?. （4）易见，当 A=B 成立时，必有 A-B=B-A。反之，由 A-B=B-A 得 (A?B)IB=(B?A)IB 化简后得 B?A=?，即 B?A，同理，可证出 A?B，从而得到 A=B。 3．18 由|P(B)|=64 可知|B|=6。又由|P(AUB)|=256 知|AUB|=8，代入包含排斥原理得 8=3+6?|AIB|, 从而有|AIB|=1,|A?B|=2,|AB|=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,|AIB|=10 代入包含排斥原理得 . |AIB|=|S|?(|A|+|B|)+|AIB| =00+100)+10 =99891047 第4章 习题解答4．1 A：⑤； B：③； C：①； D：⑧； E：⑩4．2 A：②； B：③； C：⑤； D：⑩； E：⑦ 4．3 A：②； B：⑦； C：⑤； D：⑧； E：④ 分析 题 4.1-4.3 都涉及到关系的表示。先根据题意将关系表示成集合表达式，然后再 进行相应的计算或解答，例如，题 4.1 中的 Is ={&1,1&,&2,2&}, Es ={&1,1&,&1,2&,&2,1&,&2,2&} Is ={&1,1&,&1,2&,&2,2&}; 而题 4.2 中的 R={&1,1&,&1,4&,&2,1&,&3,4&,&4,1&}. 为得到题 4.3 中的 R 须求解方程 x+3y=12，最终得到 R={&3,3&,&6,2&,&9,1&}. 求 RoR 有三种方法，即集合表达式、关系矩阵和关系图的主法。下面由题 4.2 的关系 分别加以说明。 1°集合表达式法 将 domR,domRUran,ranR 的元素列出来，如图 4.3 所示。然后检查 R 的每个有序对，若 &x,y&?R， 则从 domR 中的 x 到 ranR 中的 y 画一个箭头。 danR 中的 x 经过 2 步有向路径 若 到达 ranR 中的 y，则&x,y&?RoR。由图 4.3 可知 RoR={&1,1&,&1,4&&4,1&,&4,4&,&2,1&,&2,4&,&3,1&}. 如果求 FoG，则将对应于 G 中的有序对的箭头画在左边，而将对应于 F 中的有序对的 箭头画在右边。对应的三个集合分别为 domG,ranUdomF,ranF，然后，同样地寻找 domG 到 ranF 的 2 步长的有向路径即可。 2° 矩阵方法 若 M 是 R 的关系矩阵，则 RoR 的关系矩阵就是 M?M，也可记作 M，在计算 248 乘积时的相加不是普通加法，而是逻辑加，即 0+0=0，0+1=1+0=1+1=1，根据已知条件得? 1 0 0 1? ? 1 0 0 1? ? 1 0 0 0? ? 1 0 0 0? 2 ? ? ? ? ?? ? ? ? =? ? ?? 1 0 0 1? ? 1 0 0 1?M =?? 0 0 0 1? ? 0 0 0 1? ? 1 0 0 0? ? 1 0 0 0?? 1 0 0 0? ? 1 0 0 1?M2 中含有 7 个 1，说明 RoR 中含有 7 个有序对。图 4.3图 4.43°关系图方法 n ' '设 G 是 R 的关系图。为求 R 的关系图 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，所以， '中有从 1 到 4 的边。结点 1 检查完毕。类似地检查 其他 3 个结点，2 G 步长的路径还有 2→1→1，2→1→4，3→4→1，4→1→1，4→1→4。将这些路径 ' 2对应的边也加到 G 中，最终得到 R 的关系图。这个图给在图 4.4(2). 4．4 A：④； B：⑧； C：⑨； D：⑤； E：⑩ 分析 根据表 4.1 中关系图的特征来判定 R1,R2,LR5 的性质，如表 4.2 所示。 表 4.249 自反 R 1 R2 R 3 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,L.Bt。若 Bi ={x1,x2,L,xj}，j ≥2，则&xs,xt &?Ri,s,t=1,2,L,j,s≠t.求出 R1,R2,L,Rt。 2°R=R1UR2ULURtUIA. 本题中的π 的划分块都是单元集，没有含有个以上元素的划分块，所以， 1R=IA,π2 含有两个划分块， 故对应地等价关系含有两个等价类。 3 中只有一个划分块 Z+.Z+ π 包含了集合中的全体元素，这说明&x,y&?R ?x,y?Z+,因此， 1 这个划分块对应的关系 R 就 Z+上的全域关系，从而得到 R=R UI 也是 Z+上的 1 1 A全域关系。 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。根据结 点位置可以看出满足如下的偏序关系： apb,apc,bpc,apd,bpd 从而得到 apbpc 和 apbpd。这就说明 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 A：④； B：⑤； C：③； D：①； E：⑦ 4.8 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 就是所有有序对的第二元素构成的集合。 本题中只有 f1 是定义于实数区间上的初等函数。易见，指数函数的图像是严格单调上 升的，并且所有的函数值都大于 0。从而知道 f1 是单射的，但不是满射的。对于 f2，由 f2(1) = f2(?1) = 1 可知，它不是单射的。但 ranf2=N，所以，它是满射的。f3 既不是单 射的，也不是满射的，因为 f3(3)= f3(0)=0,且 f3={0,1,2}.f4 是 53 单射的，但不是满射的。因为 m≠n 时,必有&m,m+1&≠&n,n+1&,但&1,1&?ranf4. 4.9 A：③； B：①； C：⑦； D：⑤； E：⑨ 分析 1）先求出 T 的特征函数χ T ={&a,1&,&b,1&,&c,0&}，它是从 S 到{0,1}的函数。而 Ss 中的函数是从{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 R1oR2={&c,d&}, R2oR1={&a,d&,&a,c&}, R2={&a,a&,&a,b&,&a,d&}, 1 R3={&b,c&,&c,b&,&b,d&}, 2 4.14图 4.7 分析 根据闭包的计算公式 r(R)=RUR0,s(R)=RUR?1,t(R)=RUR2UL 可以得到由关系图求闭包的方法. 设 G 是 R 的关系图,G 的结点记为 x1,x2,L,xn,r(R),s(R),t(R)的关系图分别记作 Gr,Gs 和 Gt. 为求 Gr,先将图 G 的结点和边拷贝到 Gr 中缺少环的结点都加上环就得到了 r(R)的关系 图. 为求 Gs,也须将图 G 拷贝到 Gs,然后检查 Gs 的每一对结点 xi 和 xj(i≠ j).如果在 xi 和 xj 之间只存在一条单向的边,就在这两个结点间加上一条方向相反的边.当 Gs 中所有的单向 边都变成双向边以后就得到了 s(R)的关系图. 最后拷虑 Gt.首先将图 G 拷贝到 Gt,然后从 x1 开始依次检查 x1,x2,L,xn.在55 检查结点 xi(i=1,2,L,n 时，要找出从 xi 出发经过有限步（至少 1 步，至多 n 步）) 可达的所结点 （包括 xi 自己在内）如果从 xi 到这种结点之间缺少边， 。 就把这条边加到 G 中， 当 n 个结点全部处理完毕，就得到 t(R)的关系图。 t 以本题为例， 依次检查结点 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=IS 时满足要求。56 4．19 fof,gof,fog,hog,fogoh?NN，且 fof(n)=n+2. fog(n)=2n+1. go f(n)=2n+2, hog(n)=0,goh=?0 n 为偶数 ?2 n 为奇数, ? ?1 n 为偶数 fogoh(n)=? ?3 n 为奇数. 分析 注意合成的正确表示方法。表示 f 和 g 合成的方法有两种： 1°说明 fog 是从哪个集合到个集合的函数，然后给出 fog(x)的计算公式。 2° 给出 fog 的集合表达式。 本题中的结果都采用了第一种表示方法，先说明地果函数是从 N 到 N 的函数，然后分 别给出函数值的计算公式。也可以彩用第二种方法，如 fof ={&n,n+2&|n?N}, fogoh={&x,1&,&y,3&z|x,y?N 且 x 为偶数,y 为奇数}. 但是，如果写成 fo f =n+2 就错了，因为 fo f 是函数，是有序对的集合，与函数值 fof(n)是根本不同的两回事，不能混为一谈。 4．20 f?1:R×R→R× R, ?1 x+y x?yf (&x,y&)=& 2 , 2 &. 分析 首先由 f 的双射性确定 f?1 一定存在， 然后通过 f 的定义求出反函数的对应法则。 设 f 将&x,y&对应到&u,v&。根据 f 的定义有 &u,v&=&x+y,x?y&?x+y=u∧x?y=v ?2x=u+v∧2y=u?v?x=u+v∧y=u?v. 2 2因而反函数的对应法则是&u,v&对应到 u+v,u?v 。 2 24．21 （1） 如下列出 gof 的对应关系 57 x f(x) 0 1 2 3 4 5 1 2 3 4 0 6 7 8…5 6 7 8… 3 3 3 4…g(f(x)) 3 1 3 2 0 从而得到 gof:N→N ??3 x=0,2 或大于等于 5 的奇数 ?1 x=1 gof(x)=?2 x=3 ? ?x x≥6 且 x 为偶数?2 ?0 x=4 ? gof 是满射的，但不是单射的。 （2） gof({0,1,2})={1,3}. 4．22 （1）P(A)={?,{a},{b},{a,b}}, BA={f,f ,f ,f },其中 1 2 3 4 f1={&a,0&,{b,0&, f2 ={&a,0&&b,1&},f2={&a,1&,{b,0&, f4={&a,1&&b,1&}, （2）令 f:P(A)→BA，且 f(?)= f1,f({a})= f2,f({b})= f3,f({a,b})= f4 分析 对于任意集合 A，都可以构造从 P(A)到{0,1}A 的双射函数，任取 A 的子集 B? P(A),B 的特征函数χ B:A→{0,1}定义为 ?1 x?B χ (x)=? B ? 不同的子集的特征函数也不同，因此，令 ?:P(A)→{0,1}A 0 x?A?B?(B)=χB? 是 P(A)到{0,1}A 的双射，在本题的实例中的 ? 是 ?(?)= f,?({a})= f ,1 583?({b})= f2,?({a,b})= f4.4．23 （1） f:A→B,f(x)=2x （2） f:A→B,f(x)=sinx . 分析 给定集合 A，B，如何构造从 A 到 B 的双射？一般可采用下面的方法处理。 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)=4x?2. 这种通过直线方程构造双射函数的方法对任意两个同类型的实数区间(同为闭区间、开 区间或音开半闭的区间)都是适用的。但对半开半闭的区间要注意开端点与开端点对应，闭 端点与闭端点对应。 此外还要说明一点， 对于某些特殊的实数区间可能选择其他严格单调的 初等函数更方便，例如，A=[?1,1],B=[?π,π]，那么取 f(x)=arcsinx 即可。 2 2 3°A 是一个无穷集合，B 是自然数集 N。为构造从 A 到 B 的双射只须将 A 中的元素排成一个有序序列，且指定这个序列的初始 元素，这就叫做把 A“良序化” 。比如说 A 良序化以后，是集合{x0,x1,x2L}，那令 f:A→ B, f(xi)=i,i=0,1,2,Lf 就是从 A 到 B 的双射。 59 例如，构造从整数集 Z 到自然数集 N 到自然数集 N 的双射。如下排列 Z 中元素，然后 列出对应的自然数，即Z:0,?1,1,?2,2,?3,3,L Z:0, 1,2,?2,2,3,4,,5,6L观察这两个序列，不难找到对应法则。?2xx≥0f:Z→N,f(x)=? ??2x?1 x&0显然 f 是从 Z 到 N 的双射。 最后要指出，并不是任何两个集合都可以构造双射的。比如说，含有元素不一样多的有 穷集之间不存在双射。即使都是无穷集也不一定存在双射，如实数集 R 和自然数集 N 之间 就不存在双射。这就涉及到集合“大小”的描述和度量方法，限于篇幅地此就不进行探入讨 论了，有兴趣的读者可以阅读其他的《离散数学》书籍。 4．24 f1(x)= f1(y)?x=y,R1 为 N 上的恒等关系，且有 N/R1={{n}}|n?N}. f2(x)= f2(y)?x 与 y 的奇偶性相同。在 N 中的所有奇数构成一个等价类，所有的偶数构 成另一个等价类。因此， N/R2={{2n|n?N},{2n+1|n?.N}}. f3(x)= f3(y)?x=y(mod3)，即 x 除以 3 的余数与 y 除以 3 的余数相等。根据余数分别这0，1，2，可将 N 中的数分成 3 个等价类，因而 N/R3={{3n|n?N},{3n+1|n?.N}}. 4．25 （1） fog:N→R,fog(x)=x2?x60 fog 不是单射也不是满射。fog(A)={2,12,30,56,90} fog(B)={0}。 x2 （2） fog:Z→R,fog(x)=efog 不是单射也不是满射。 n2 fog(A)={e |n?N}. 4n2 fog(B)={e |n?N}.61第5章习题解答5.1 A:③; B:⑥; C:⑧; D:⑩; E:⑨ 分析 n2 S 为 n 元集,那么 S×S 有 n2 个元素.S 上的一个二元运算就是函数 n2 个.因此{a,b}上的二元运算有 n =16 个.f:S×S→S.这样的函数有 n下面说明通过运算表判别二元运算性质及求特导元素的方法. 1 °交换律 若运算表中元素关于主对角线成对称分布,则该运算满足交换律. 2 °幂等律 设运算表表头元素的排列顺序为 x1,x2,Lxn,如果主对角线元素的排列也 为 x1,x2,Lxn,则该运算满足幂等律.其他性质,如结合律或者涉及到两个运算表的分配律和吸收律,在运算表中没有明显的特 征,只能针对所有可能的元素 x,y,z 等来验证相关的算律是否成立. 3 ° 幺元 e 设运算表表头元素的排列顺序为 x1. 的元素排列顺序也是 x1,x2,Lxn,则 xi 为幺元. ,x2,Lxn,如果元素 xi 所在的行和列4 ° 零元θ .如果元素 xi 所在的行和列的元素都是 xi,则 xi 是零元. 5 ° 幂等元.设运算表表头元素的排列顺序为 x1,x2,Lxn,如果主对角线上第 i 个元素恰 为 xii?{1,2,L,n}那么 xi 是幂等元.易见幺元和零元都是幂等元. 6 ° 可逆元素及其逆元.设 xi 为任意元素,如果 xi 所在的行和列都有幺元,并且这两个幺元 关于主对角线成对称分布,比如说第 i 行第 j 列和第 j 行第 i 列的两个位置,那么 xj 与 xi 互为 逆元.如果 xi 所在的行和列具有共同的幺元,则幺元一定在主对角线上,那么 xi 的逆元就是 xi 自己.如果 xi 所在的和地或者所在的列没有幺元,那么 x 不是可逆元素.不难看出幺元 e 一定 是可逆元素,且 e?1=e;而 i 零元θ 不是可逆元素. 以本题为例,f1,f2,f3 的运算表是对称分布的,因此,这三个运算是可交换的, 62 而 f4 不是可交换的.再看幂等律.四个运算表表头元素排列都是 a,b,其中主对角线元素排列为 a,b 的只有 f4,所以, f4 遵从幂等律.下面考虑幺元.如果某元素所在的行和列元素的排列都是 a,b,该元素就是幺元.不难看出只有 f2 中的 a 满足这一要求,因此,a 是 f2 的幺元,其他三个运算 都不存在幺元.最后考虑零元.如果 a 所在的行和列元素都是 a,那么 a 就是零元;同样的,若 b 所在的行和列元素都是 b,那么 b 就是零元.检查这四个运算表,f1 中的 a 满足要求,是零元,其他 运算都没有零元.在 f4 的运算表中,尽管 a 和 b 的列都满足要求,但行不满足要求.因而 f4 中也 没有零元. 5.2 A:①; B:③; C:⑤; D:⑦; E:⑩ 分析 对于用解析表达式定义的二元运算 °和 *,差别它们是否满足交换律,结合律,幂 等律,分配律和吸收律的方法总结如下: 任取 x,y,根据 °运算的解析表达式验证等式 xoy=yox 是否成立.如果成立 °运算就满 足交换律. 2 ° °运算的地合律 任取 x,y,z 根据 °运算的解析表达式验证等式(xoy)oz=xo(yoz)是否成立. 如果成立, °运算就是可结合的. 3 ° °运算的幂等律 任取 x,根据 °运算的解析表达式验证等式 xox=x 是否成立.如果成立,°运算满足幂等 律. 4 ° °运算对*运算的分配律 任 取 x,y,z , 根 据 ° 和 * 运 算 的 解 析 表 达 式 验 证 等 式 xo(y*z)=(xoy)*(xoz)和(y*z)ox=(yox)*(zox)是否成立。如果成立，则°运算对*运算满足分配 律。 5 ° °和*运算的吸收律 首先验证 °和*运算是可交换的。然后任取 x,y 根据 °和 *运算的解析表, 达式验证等式 xo(x*y)=x 和 x*(xoy)=x 是否成立。如果成立，则°和 *运算 63 满足吸收律。 设°是用解析表达式定义的 A 上的二元运算，求解对于该运算的特导元素可以采用下 述方法： 1 ° 求幺元 e。根据幺元定义，?x?A,e 应满足等式 xoe=eox=x。将等式中的 xoe=和 eox 用 关于°运算的解析表达式代入并将结果化简，然后由 x 的任意性来确定 e . 2° 求零元θ .根据零元定义，?x?A,θ 应该满足等式 xoθ=θox=θ。将等式中的 xoθ 和θ ox 用关于 ° 运算的解析表达式代入并将结果化简，然后由 x 的任意性确定θ . 3 ° 求幂等元. 将 xox=x 等式中的 xox 用关于 °运算的解析表达式代入并化简单,然 后求解该议程,所得到的解就是幂等元. 4 ° 求可逆元素的逆元. 任取 x?A,设 x 的逆元为 y,则 x 与 y 应该满足等式 xoy=yox=e. 将等式中的 xoy 与 yox 用关于°运算的解析表达式代入,并将 e 用 °运算的幺元代入,然后化 简等式.观察使得该等式成产的 x 应该满足的条件,然后将 y 用含有 x 的公式表示出来,从而得 到 x 的逆元.这里特别要说明一点,如果°运算不存在幺元 e 则所有有元素都是不可逆的. , 以本题为例,具体的分析过程如下: 任取&a,b&,&x,y&?Q×Q,由&a,b&?&x,y&=&ax,ay+b& &x,y&?&a,b&=&xa,xb+y& 可知一般情况下 ay+b≠xb+y,所以?运算不是可交换的. 任取&a,b&,&x,y&,&u,v&?Q×Q,由 (&a,b&?&x,y&?&u,v&=&ax,ay+b&?&u,v& =&axu,axv+ay+b& &a,b&?&x,y&?&u,v&=&a,b&?&xu,xv+y&64 =&axu,a(xv+y)+b&=&axu,axv+ay+b&, 可知?运算是可结合的. 设?运算的幺元为&e1,e2&,则?&a,b&?Q× 有 Q &a,b&?&e1,e2&=&a,b&, &e1,e2&?&a,b&=&a,b&, 代入关于?运算的解析表达式得 &ae1,ae2+b&=&a,b&, &e1a,e1b+e2&=&a,b&. 从而得到 ae1=a,ae2+b=b,e1a=a,e1b+e2=b 由于 a,b 是任意有理数,要使得上述四个等式都成立,必有 e1=1,e2=0 所以,?运算的幺元为&1,0&. 对于任意的&a,b&?Q× Q,设&a,b&的逆元为&x,y&,那么有&a,b&?&x,y&=&1,0& &x,y&?&a,b&=&1,0&代入关于?运算的解析表达式得 &ax,ay+b&=&1,0& &xa,xb+y&=&1,0& 从而得到 ax=1,ay+b=0,xa=1,xb+y=0 解得 x=1(a≠0),y=?b(a≠0) a a65 这说明对一切&a,b&?Q× Q,只要 a≠0 都存在逆元&1,?b&. a a最后补充说明一点.不难验证, ?运算没有零元.而关于?运算的幂等元是&1,0&和&0,b&,其 中 b 为任意有理数. 5.3 A:⑦; B:⑥; C:⑤; D:③; E:② 分析 怎样检验运算 o 是否为 S 上的二元运算,或者说 S 是否关于 o 运算封闭?主要是验 证以下两个条件是否满足; 1°任何 S 中的元素都可以作为参与运算的元素. 2° 运算的结果仍旧是 S 中的元素. 如果给定了两个以上的运算,在讨论封闭性时要分别对每个运算讨论. 容易验证本题中的 6 个函数全是实数集 R 上的二元运算.它们的可交换性,结合性, 幺元 和零元的判别结果如下. 交换 f √ 结合 √ 幺元 为0 零元 ×1 f 2 f3 √ √ f4 f 5 f6 5.4 A:②; B:⑤; C:⑦; D:⑧; E:⑧ 分析 对于给定的自然数 n,n=0,1,2,L , nZ={nk|k?Z} 是 V 的子代数,因为? nk,nk ?nZ 有 1 2 √ × × × √ √ × × × × × √ × √ × 为1 × 为0nk1+nk2=n(k1+k2)?nZ . nk1?nk2=n(k1nk2)?nZ. 这说明 nZ 关于+和?运算都是封闭的,满足子代数的定义.由于 n 可以取任何 66 自然数,这样的子代数有无数多个.其中当 n=0 时, nZ={0}是有穷集合.即有限的子代数,其余都 是无限的子代数. 对于 T2 来说,它是奇整数的集合.而奇数加奇数等于偶数,因而 T2 关于加法不封闭.类似 地, T3 关于加法也不封闭,因为 1?T3,但 1+1=2?T3.因而可以判定 T2 和 T3 都不是 V 的子代数,尽管 T2 和 T3 对于乘法是封闭的. 5.5 A:④; B:⑨; C:①; D:①; E:④分析 构成代数系统的要素有三个:集合,二元或一元运算及代数常数.如果 ? 是代数系 统 V1 和 V2 的同态,那么 ? 必须满足以下条件:1°?:V1→V2 即 ? 是 V1 和 V2 的函数.2° 对 V 和 V 上任意对应的二元运算 o 和 o 有' 1 2?(xoy)=?(x)o?(y),?x,y?V'1 对 V 和 V 上任意对应的二元运算Δ 和Δ 有' 1 2?(Δx)=Δ?(x),?x?V.'1 3° 对 V 和 V 上任意对应的代数常数 k 和 k'有 1 2?(k)=k.'以本题为例.因为只有一个二元运算,验证时只要检验条件 1° 即可.具体的验证过程如 ,2° 下:?,? ,?,? 都是 R+到 R+的映射, 且1 2 3 4?x,y?R+,?(x?y)=|x?y|=|x|?|y|=?(x)??(y).111?x,y?R+,? (x?y)=(xy)2=x2?y2 =? (x)?? (y).3 +3 13 11?x,y?R ,?4(x?y)== ? =?4(x)??4(y).xux y所以 ?1,?3 和 ?4 是 V 的自同态.但是 ?2 和 ?5 不是 V 的自同态.原因如下:?2(1?2)=?2(2)=4.?2(1)??2(2)=(2?1).(2?2)=8,67 故 ?2(1?2)≠?2(1)??2(2),破坏了同态映射的条件 2° .而对于 ?5,它将正数映到负数,根 本不是 R+到 R+的函数,破坏了条件 1° ,当然更谈不到同态了. 通过上面的分析已经知道了判别同态及其性质的基本方法.下面补公介绍一些典型同态 映射的实例,以供读者参考. 1° V=&Z,+&是整数加群.令 ?a:Z→Z,?a=(x)=ax?, x?Z,这里的 a 是给定的整数.那么? x?Z 有 ?a(x+y)=a(x+y)=ax+ay=?a(x)+?a(y).?2 是 V 的自同态.当 a=0 时,?a 不是单同态,也不是满同态,其同态象为&{0},+&.当 a± 时, ?a 为自同态. 1当 a≠0,± 时,?a 为单自同态,其同态象为&aZ,+&,其中 aZ={ak|k?Z}. 12° =&Zn,&是模 n 整数加群,其中 Zn ={0,1,L,n?1}.可以证明 ?p 是 V 的自同态.因为 V ?x,y?Zn 有 ?p(xy)=(p(xy))modn=(pxpy)modn=(px)modn(py)modn=?p(x)?p(y).由于 p 有 n 种取值,这里定义了 n 个自同态. ={0,1,L5}.V=&Z6,&上有 6 个自同态,即 ?0,?1,L?5.其中例如,n=6Z6,?0(x)=0,?x?Z6,?1(1)=x,?x?Z6,?2(1)=2,?2(2)=4,?2(3)=0,?2(4)=2,?2(5)=4,?2(0)=0.?3(1)=3,?3(2)=0,?3(3)=3,68 ?3(4)=0,?3(5)=3,?3(0)=0.?4(1)=4,?4(2)=2,?4(3)=0,?4(4)=4,?4(5)=2,?4(0)=0,?5(1)=5,?5(2)=4,?5(3)=3,?5(4)=2,?5(5)=1,?5(0)=0.这 3 个自同态中 ?1 和 ?5 是自同构,其他的既不是单同态,也不是满同态.?0 的同态象 为&{0},&.?2 和 ?4 的同态象为&{0,2,4},&,?3 的同态象为&{0,3},&.3° 设 V1=&R,+&,V2&Zn,
& 分 别 为 整 数 加 群 和 模 Zn,?(x)=(x)modn 容易证明 ? 是 满同态.n整 数 加 群 .?:Z →4° 设 V =&R,+&,V =&R,?&,其中 R 和 R* 1 2*分别代表实数集和非零实数集,+和?分别代表普能加法和乘法.?:R→R,?(x)=e*x 是 V 和 V 的单同态,其12同态象为&R+,?&,这里的 R+是正实数集. 5° 设 V1=&Ao, &,V2=&B,*&是具有一个二元运算和代数系统. V1 和 V2 的积代数为 &A×B,?&.令 ?:A× B→A,?(&a,b&)=a,那么 ? 是积代数 V1× V2 到 V1 同态的,因为对任意 &a1,b1&,&a2,b2 &?A× 有 B ?(&a1,b1&?&a2,b2&)=?(&a1oa2,b1*b2&)=a1oa2=?(&a1,b1&)o?(&a2,b2&).容易看出 ? 是满同态.只有当 B 为单元集时 ? 为同构.5.6 A:⑤; B:③; C:②; D:①; E:⑧ 5.7 (1)和(4)是代数系统. (2)不是,例如 1cm(9,10)=90,90?S (3)不是,例如 9*10=90,90?S. 69 (5)不是,例如 9*10=0,0?S. 5.8 (1)封闭,若 xs,y 是 16 的倍数,则(x+y)t s+t 也是 16 的倍数.(2)不封闭,例如 2 和 5 互质,3 也和 5 互质,但 2+3=5 却不和 5 互质. (3)不封闭,3 和 5 都是 30 的因子,但是 3+5=8 不是 30 的因子. (4)封闭 5.9 (1)可交换,不幂等.a 是幺元,且 a?1=a,b 和 c 互逆元. (2)不可交换,有幂等性,元幺元,当然不考虑逆元了. (3)可交换,有幂等性, 幺元是 a,a?1=a,b 和 c 都没有逆元. 分析 这里补谈谈结合律的判定问题.在验证结合律(x*y)*z=x*(y*z)是否成立时,等式中 的 x,y,z 可以取 a,b,c 中的任何元素,共有 27 种可能的选法.这意味着必须要要验证 27 个等式, 工作量很大.若 x,y,z 中有幺元或零元存在,则等式显然成立.考虑到这个因素,在验证时可以不 选取集合中的幺元和零元.下面以本题为例来判定结合律是否成立. (1)a 是幺元.只须对 b 和 c 进行验证.又由于*运算的可交换性,全是 b 或全是 c 情况可以 忽略,因而需要验证的只有下面六种情况: (b*b)*c=c*c=b=b*a=b*(b*c), (b*c)*b=a*b=b=b*a=b*(c*b), (b*c)*c=a*c==c*c=c*(b*b),(c*b)*b=a*b=b=c*c=c*(b*b), (c*b)*c=a*c=c=c*a=c*(b*c), (c*c)*b=b*b=c=c*a=c*(c*b). 由以上验证可知*运算是可结合的. (2)通过观察发现,?x,y?S 有 x*y=y.每个元素都是右零元.因而必有?x,y,z?S,70 (x*y)*z=y*z=z,x*(y*z)=x*z=z. 这就证明了结合律是成立的. (3)c 是零元,故只须对 a 和 b 验证.显然(a*a)*a=a*(a*a),因此,只须考虑至少含有一个 b 的 等式.由 a*b=b*a=b,b*b=b 可知无论 b 处在哪一个位置,等式两边都等于 b,因此结合律成立. 5.10 结果如表 5.2 所示 表 5.2 &0,0& &0,1& &1,0& &1,1& &2,0& &2.1&&0,0& &0,0& &0,0& &1,0& &1,0& &2,0& &2,0&&0,1& &0,0& &0,1& &1,1& &1,1& &2,0& &2,1&&1,0& &1,0& &1,0& &2,0& &2,0& &0,0& &0,0&&1,1& &1,0& &1,1& &2,0& &2,1& &0,0& &0,1&&2,0& &2,0& &2,0& &0,0& &0,0& &1,0& &1,0&&2,1& &2,0& &2,1& &0,0& &0,1& &1,0& &1,1& 其中&0,1&为幺元. 5.11 o 运算表如表 5.3 所示. Δx * 1 2 5 10 x1 2 5 101 2111 1 121 11 21 2 5 10 2 2 10 101 210 55 10115 5 1 2 5 105 105 10 5 10 10 10 10 105 102 15.12 (1)可交换,不可结合,无幺元,无可逆元素. (2)不可交换,不可结合,无幺元,无可逆元素. * ?1 1(3)可交换,可结合, 幺元是 1,?a?R 有 a =a. 5.13 表 5.4 71 * 0 1 2 3 4 幺元 1 1?1=1,2?1=3, 逆元 ?1 ?1 0 1 2 3 4 0 0 0 0 0 0 1 2 3 4 0 2 4 1 0 3 1 4 0 4 3 2 3 2 1 零元 0 结果如表 5.4 所示.3 =4 =4, 0 元逆元. 5.14 A 其中A ={f1,f2,f3,f4},f1(1)=1f(2)=1; f2(1)=1,f2(2)=2; f3(1)=2,f3(2)=272第6章习题解答6.1A:⑨; B:⑨; C:④; D:⑥; E:③分析 对于给定的集合和运算判别它们是否构成代数系统的关键是检查集合对给定运 算的封闭性,具体方法已在 5.3 节做过说明. 下面分别讨论对各种不同代数系纺的判别方法. 1°给定集合 S 和二元运算°,判定&S, °&是否构成关群、独导点和群. 根据定义，判别时要涉及到以下条件的验证： 条件 1 S 关于 °运算封闭： 条件 2 °运算满足结合集 条件 3 °运算有幺元， 条件 4 ° ?x?S,x?1?S. 其中关群判定只涉及条件 1 和 2；独导点判定涉及条件 1、2、和 3；而群的判定则涉及 到所有的四个条件。 2 ° 给定集合 S 和二元运算 °和 *，判定&S, °, *&是否构成环,交换环,含幺环,整环, 域.根据有关定义需要检验的条件有: 条件 1 &S, °&S 构成交换群, 条件 2 &S, *& 构成关群, 条件 3 * 对 °运算的分配律, 条件 4 * 对运算满足交换律, 条件 5 * 运算有幺元,条件 6 * 运算不含零因子――消去律， 条件 7 |S|≥2,?x?S,x≠0,有 x?1?S（对*运算）.其中环的判定涉及条件 1,2 和 3;交换环的判定涉及条件 1,2,3 和 4;含幺环的判定涉及条 件 1,2,3 和 5;整环的判定涉及条件 1-6;而域的判定则涉及全部 7 个条件. 3° 判定偏序集&S,≤&或代数系统&S,o,*&是否构成格、分本配格、有补格和布尔格. 73 若&S,≤&为偏序集,首先验证?x,y∧y 和 x∨y 是否属于 S.若满足条件则 S 为格,且&S, ∨,∧&构成代数系统.若&S,o,*&是代数系统且°和*运算满足交换律、结合律和吸收律，则 &S,o,*&构成格。 在此基础上作为分配格的充分必要条件是不含有与图 6.3 所示的格同构的子格。 而有补 格和布尔格的判定只要根据定义进行即可。 注意对于有限格，只要元素个数不是 2 的幂，则一定 不是布尔格。但元素个数恰为 2n 的有限格中只有唯一 的布尔格。 以本题为例具体的判定过程如下： （1） 由 n+n=2n?S1