我要投搞

标签云

收藏小站

爱尚经典语录、名言、句子、散文、日志、唯美图片

当前位置:小鱼儿玄机1站开奘结果 > 前束范式 >

离散数学习题答案全doc

归档日期:07-14       文本归类:前束范式      文章编辑:爱尚语录

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  离散数学习题解答(第四版)清华大学出版社 第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为线整除,p为假命题。 (6)。其中,是素数,q:三角形有三条边。由于p与q都是真命题,因而为假命题。 (7),其中,p:雪是黑色的,q:太阳从东方升起。由于p为假命题,q为真命题,因而为假命题。 (8)年10月1日天气晴好,今日(1999年2月 13日)我们还不知道p的真假,但p的真值是确定的(客观存在的),只是现在不知道而已。 (9)p:太阳系外的星球上的生物。它的真值情况而定,是确定的。 (10)p:小李在宿舍里. p的真值则具体情况而定,是确定的。 (12),其中,是偶数,是奇数。由于q是假命题,所以,q为假命题,为线),其中,是偶数,是奇数,由于q是假命题,所以,为假命题。 (14) p:李明与王华是同学,真值由具体情况而定(是确定的)。 (15) p:蓝色和黄色可以调配成绿色。这是真命题。 分析 命题的真值是唯一确定的,有些命题的真值我们立即可知,有些则不能马上知道,但它们的真值不会变化,是客观存在的。 1.3 令则以下命题分别符号化为 (1) (2) (3) (4) (5) (6) (7) (8) 以上命题中,(1),(3),(4),(5),(8)为真命题,其余均为假命题。 分析 本题要求读者记住及的真值情况。为假当且仅当p为真,q为假,而为真当且仅当p与q真值相同.由于p与q都是线号。 在这里,当p为真时,r一定为假,为假,当p为假时,无论r为线是素数。此命题为线),其中,p:小王聪明,q:小王用功 (3),其中,p:天气冷,q:老王来了 (4),其中,p:他吃饭,q:他看电视 (5),其中,p:天下大雨,q:他乘公共汽车上班 (6),其中,p,q的含义同(5) (7),其中,p,q的含义同(5) (8),其中,p:经一事,q:长一智 分析 1°在前4个复合命题中,都使用了合取联结词,都符号化为合取式,这正说明合取联结词在使用时是很灵活的。在符号化时,应该注意,不要将联结词部分放入简单命题中。例如,在(2)中,不能这样写简单命题:p:小王不但聪明,q:小王而且用功。在(4)中不能这样写:p:他一边吃饭, q:他一边看电视。 2° 后4个复合命题中,都使用了蕴含联结词,符号化为蕴含式,在这里,关键问题是要分清蕴含式的前件和后件。 所表达的基本逻辑关系为,p是q的充公条件,或者说q是p的必要条件,这种逻辑关系在叙述上也是很灵活的。例如,“因为p,所以q”,“只要p,就q”“p仅当q”“只有q才p”“除非q,否则”“没有q,就没有p”等都表达了q是p的必要条件,因而都符号化为或的蕴含式。 在(5)中,q是p的必要条件,因而符号化为,而在(6)(7)中,p成了q的必要条件,因而符号化为。 在(8)中,虽然没有出现联结词,但因两个命题的因果关系可知,应该符号化为蕴含式。 1.6 (1),(2)的线个命题变项,因而它应该有个赋值:000,001,…,111题中指派p, q为0, r为1,于是就是考查001是该公式的成真赋值,还是成假赋值,易知001是它的成假赋值。 2° 在公式(2),(3),(4)中均含4个命题就项,因而共有个赋值:0000,0001,…,1111。现在考查0011是它的成假赋值。 1.7 (1),(2),(4),(9)均为重言式,(3),(7)为矛盾式,(5),(6),(8),(10)为非重言式的可满足式。 一般说来,可用真值表法、等值演算法、主析取范式(主合取范式)法等判断公式的类型。 (1)对(1)采用两种方法判断它是重言式。 线)中公式的真值表,由于线)为重言式。 p q r 0 0 0 0 1 0 0 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 1 等值演算法 (蕴含等值式) (结合律) (排中律) (零律) 由最后一步可知,(1)为重言式。 (2)用等值演算法判(2)为重言式。 (蕴含等值式) (等幂律) (蕴含等值式) (排中律) (3)用等值演算法判(3)为矛盾式 (蕴含等值式) (德·摩根律) (结合律) (矛盾律) (零律) 由最后一步可知,(3)为矛盾式。 (5)用两种方法判(5)为非重言式的可满足式。 线 1 0 1 0 0 由表1.3可知(5)为非重言式的可满足式。 主析取范式法 . 在(3)的主析取范式中不含全部(4个)极小项,所以(3)为非重言式的可满足式,请读者在以上演算每一步的后面,填上所用基本的等值式。 其余各式的类型,请读者自己验证。 分析 真值表法判断公式的类别是万能。公式A为重言式当且仅当A的线;A为矛盾式当且仅当A的线;A为非重言式的可满足式当且仅当A的真值表最后一列至少有一个1,又至少有一个0。真值表法不易出错,但当命题变项较多时,真值表的行数较多。 用等值演算法判断重言式与矛盾式比较方例,A为重言式当且仅当A与1等值;A为矛盾式当且仅当A与0等值,当A为非重言式的可满足式时,经过等值演算可将A化简,然后用观察法找到一个成真赋值,再找到一个成假赋值,就可判断A为非重言式的可满足式了。例如,对(6)用等值演算判断它的类型。 (矛盾律) (等价等值式) (蕴含等值式) (同一律) (零律) (同一律) 到最后一步已将公式化得很简单。由此可知,无论取0或1值,只要取0值,原公式取值为1,即00或10都为原公式的成线为成假赋值,于是公式为非重言式的可满足式。 用主析取范式判断公式的类型也是万能的。A为重言式当且仅当A的主析取范式含(为A中所含命题变项的个数)个极小项;A为矛盾式当且仅当A的主析取范式中不含任何极小项,记它的主析取范式为0;A为非重言式的可满足式当且仅当A的主析取范式中含极小项,但不是完全的。 当命题变项较多时,用主析取范式法判公式的类型,运算量是很大的。 用主合取范式判断公式的类型也是万能的。A为重言式当且仅当A的主合取范式中不含任何极大项,此时记A的主合取范式为1;A为矛盾式当且仅当A的主合取范式含个极大项(为A中含的命题变项的个数);A为非重言式的可满足式当且仅当A的主析取范式中含含极大项,但不是全部的。 1.8 (1)从左边开始演算 (分配律) (排中律) (同一律) (2)从右边开始演算 (蕴含等值式) (分配律) (蕴含等值式) (3)从左边开始演算 请读者填上每步所用的基本等值式。 本题也可以从右边开始演算 读者填上每步所用的基本的等值式。 1.9 (1) (蕴含等值式) (德·摩根律) (结合律、交换律) (矛盾式) (零律) 由最后一步可知该公式为矛盾式。 (2) (蕴含等值式) 由于较高层次等价号两边的公式相同,因而此公式无成假赋值,所以,它为重言式。 (3) (蕴含等值式) (蕴含等值式) (德·摩根律) (吸收律) (交换律) 由最后一步容易观察到,11为该公式成假赋值,因而它不是重言式,又00,01,10为成真赋值,因而它不是矛盾式,它是非重言式的可满足式。 1.10 题中给出的F,G,H,R都是2元线个联结词集都是全功能集,可以用观察法或等值演算法寻找与真值函数等值的公式。 首先寻找在各联结词集中与F等值的公式。 (1)设,易知A是中公式且与F等值,即 (2)设,易知B是中公式且与F等值,即 (3)设,易知C是中公式,且 (4)设,易知D为中公式,且 (5)设,易知E为中公式,且 分析 只要找到一个联结词集中与F等值的公式,经过等值演算就可以找出其他联结词集中与F等值的公式。例如,已知是公式,且。进行以下演算,就可以找到F等值的其他联结词集中的公式。对A进行等值演算,消去联结词,用,取代,得 则B为中公式,且。再对A进行等值演算,消去,用,取代,得 则C为中公式,且。再对B进行演算,消去,,用取代,在演算中,注意,对于任意的公式A,有 则D为中公式,且再对C进行演算,消去用取代,在演算中注意,对于任意的公式A 则E为中公式,且 开始找一个与某真值函数等值的公式的方法,除观察法外,就是根据该真值函数的真值表,求它的主析取范式,而后进行等值演算即可。例如,由G的真值表可知G的主析取范式为,于是 由于公式不带联结词,所以,它应该为任何联结词集中的合式公式。 在各联结词集中找到的与某真值函数等值的公式并不唯一。例如,取 中公式) 中公式) 中公式) 中公式) 中公式) 则对于同一个真值函数,找到与它等值的形式各异的公式。 对于H和R,请读者自己去完成。 1.11 (1)对C是否为矛盾式进行讨论。 当C不是矛盾式时,,则一定有,这是因为,此时,,所以,有 必有 而当C不是矛盾式时,,不一定有,举反例如下: 设A,B,C均为含命题变项的公式,A,B,C及的线 p q A B C AVC BVC 0 0 1 1 0 1 0 1 0 0 1 0 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 (2) 对C是否为重言式进行讨论: 若C为重言式,则于是 因而有 当C不是重言式时,请读者举反例说明, 时, 不一定有. (3) 若则.证明如下: (双重否定律) () (双重否定律) 所以 1.12 (1) 设(1)中公式为A. 于是,公式A的主析取范式为 易知,A的主合取范式为 A的成线 (2)设(2)中公式为B (吸收律) 所以,B的主析取范式为. B的主合取范式为 B的成线)中公式为C. ] 所以,C的主析取范式为0. C的主合取范式为 C的成假赋值为00,01,10,11 C无成真赋值,C为矛盾式. 分析 1°设公式A中含个命题变项,且A的主析取范式中含个极小项,则A的主合邓范式中含个极大项,而且极大项的角标分别为0到这个十进制数中未在A的主析取范式的极小项角标中出现过的十进制数. 在(1)中,n=3,A的主析取范式中含4个极小项,所以,A的主合取范式中必含个极大项,它们的角标为0到7中未在主析取范式的极小项角标中出现过的3,4,5,6. 这样,只要知道A的主析取范式,它的主合邓范式自然也就知道了,在(2),(3)中情况类似. 2° A的主析取范式中极小项角标的二进制表示即为A的成线)中,由于主析取范式中的极小项角标分别为0,1,2,7,它们的二进制表示分别为000,001,010,111,所以,A的成真赋值为以上各值.类似地,A的主合取范式中所含极大项角标的二进制表示,即为A的成假赋值. 1.13 (1) 首先求的主析取范式. 错误!链接无效。 . 由于演算过程较长,可以分别先求出由派生的极小项.注意,本公式中含3个命题变项,所以,极小项长度为3. 类似地,可求出主的析取范式也为上式,由于公式的主析取范式的唯一性,可知, (2) ① ② 由于与的主析取范式不同.因而它们不等值,即. 1.14 设p:A输入; 设q:B输入; 设r:C输入; 由题的条件,容易写出的线所示.由真值表分别写出它们的主析范邓范式,而后,将它们都化成与之等值的中的公式即可. 表1.5 p q r 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 . \ 分析 在将公式化成或中公式时,应分以下几步: (1)先将公式化成全功能集中的公式. (2) 使用 或 使用双重否定律 或 使用德·摩根律 或 1.15 设p:矿样为铁; q:矿样为铜; r:矿样为锡. 设 , . 设 则F为真命题,并且 但,矿样不可能既是铜又是锡,于是q,r中必有假命题,所以因而必有 于是,必有P为真,q与r为假,即矿样为铁。 1.16 令p:今天是1号; q:明天是5号. 由于本题给出的推理都比较简单,因而可以直接判断推理的形式结构是否为重言式。 (1)推理的形式结构为 可以用多种方法判断上公式为重言式,其实,本推理满足假言推理定律,即 所以,推理正确。 (2)推理的形式结构为 可以用多种方法证明上公式不是重言式,其实,当p为假(即今天不是1号),q为线是上面公式的成假赋值,所以,推理的形式结构不是重方式,故,推理不正确。 (3)推理的形式结构为 可以用多种方法证明上面公式为重言式,其实,它满足拒取式推理定律,即 所以,推理正确。 (4)推理的形式结构为 可以用多种方法证明上公式不是重言式,01为上公式的成假赋值,所以,推理不正确。 分析 对于前提与结论都比较简单的推理,最好直接判推理的形式结构是否为重言式,来判断推理是否正确,若能观察出一个成假赋值,立刻可知,推理不正确。 1.17 (1) 证明 ① 前提引入 ② 前提引入 ③ ①②析取三段论 ④ 前提引入 ⑤ ④置换 ⑥ ②⑤析取三段论 (2) 证明 ① 前提引入 ② ①置换 ③q 前提引入 ④ ②③假言推理 ⑤ 前提引入 ⑥ ⑤置换 ⑦ ④⑥假言三段论 (3) 证明 ① 附加前提引入 ② 前提引入 ③q ①②假言推理 ④ ①③合取 或者 证明 ① 前提引入 ② ①置换 ③ ②置换 ④ ③置换 ⑤ ④置换 (4) 证明 ① 前提引入 ② ①置换 ③ ②化简 ④ 前提引入 ⑤ ⑥s ③⑤假言推理 ⑦ 前提引入 ⑧ ⑦置换 ⑨ ⑧化简 ⑩q ⑥⑨似言推理 ? 前提引入 ?p ⑩? 假言推理 ?r ④化简 ? ⑥⑩??合取 分析 由于 所以,当推理的结论也为蕴含式时,可以将结论的前件作为推理的前提,称为附加前提,并称使用附加前提的证明方法为附加前提证明法.(3)中第一个证明,即为附加前提证明法. 1.18 设p:他是理科生 q:他是文科生 r:他学好数学 前提 结论q 通过对前提和结论的观察,知道推理是正确的,下面用构造证明法给以证明。 证明 ① 前提引入 前提引入 ③ ①②拒取式 ④ 前提引入 ⑤ ③④拒邓式 ⑥q ⑤置理 1.19 本题可以用多种方法求解,根据要求回答问题,解本题最好的方法是真值表示或主析取范式法。这里采用主析取范式的主析取范式(过程略) 所以,成线,由④给也,成假赋值为000,001,011,由③给出,公式是非重言式的可满足式,由③给出。 1.20 答案 A:③; B:④; C:② 分析 解本题的方法不限于求主析取范式或主合取范式,也可以利用线: 求主析取范式 从上式可知,的主析取范式中含5个极小项。极小项角码的二进制表示为成线。由成真赋值立即可知成假赋值为000, 010,100,成假赋值的十进制的十进表示为极大项的角码,因而极大项为,故有3个极大项。 方法2:求主合取范式,分析类似主析取范式法。 方法3:真值表法 由真值表,求出成真赋值,将成真赋值转化成十进制数做为极小项的角码,这样就求出了全部极小项,也容易求出极大项。 1.21 答案 A:③; B:⑤; C:⑥ 分析 可用构造证明法解此题。 (1) ① 前提引入 ② 前提引入 ③ ①②析取三段论 ④ 前提引入 ⑤ ④置换 ⑥ ③⑤析取三段论 至此可知是(1)的逻辑结论。 (2) ① 前提引入 ② 前提引入 ③ ①②析取三段论 ④ 前提引入 ⑤ ④置换 ⑥ ⑤置换 至此可知是(2)的国逻辑结论。 (3) ① 前提引入 ② ①置换前提引入 ③ 前提引入 ④ ③置换 ⑤ ②④假言推理 ⑥ 前提引入 ⑦ ⑤⑥假言推理 至此可知是(3)的逻辑结论。 1.22 答案 A:④ 分析 在本题中,设A,B,C分别表示3个开关状态的命题变项,开关的扳键向上时,对应命题变项的线 本题没有给出个体域,因而使用全 总个体域. (1) 令是鸟 会飞翔. 命题符号化为 . (2)令为人. 爱吃糖 命题符号化为 或者 (3)令为人. 爱看小说. 命题符号化为 . (4) 为人. 爱看电视. 命题符号化为 . 分析 1°如果没指出要求什么样的个体域,就使用全总个休域,使用全总个体域时,往往要使用特性谓词。(1)-(4)中的都是特性谓词。 2° 初学者经常犯的错误是,将类似于(1)中的命题符号化为 即用合取联结词取代蕴含联结词,这是万万不可的。将(1)中命题叙述得更透彻些,是说“对于宇宙间的一切事物百言,如果它是鸟,则它会飞翔。”因而符号化应该使用联结词→而不能使用。若使用,使(1)中命题变成了“宇宙间的一切事物都是鸟并且都会飞翔。”这显然改变了原命题的意义。 3° (2)与(4)中两种符号化公式是等值的,请读者正确的使用量词否定等值式,证明(2),(4)中两公式各为等值的。 2.2 (1)d (a),(b),(c)中均符号化为 其中此命题在中均为线) 在中均符号化为 其中,此命题在(a)中为假命题,在(b)(c)中均为线)在中均符号化为 其中此命题在中均为假命题,在(c)中为线°命题的线° 有的命题在不同个体域中,符号化的形式不同,考虑命题 “人都呼吸”。 在个体域为人类集合时,应符号化为 这里,呼吸,没有引入特性谓词。 在个体域为全总个体域时,应符号化为 这里,为人,且为特性谓词。呼吸。 2.3 因题目中未给出个体域,因而应采用全总个体域。 (1) 令:是大学生,是文科生,是理科生,命题符号化为 (2)令是人,是化,喜欢,命题符 号化为 (3)令是人,犯错误,命题符号化为 或另一种等值的形式为 (4)令在北京工作,是北京人,命题符号化为 或 (5)令是金属,是液体,溶解在y中,命题符号化为 (6)令与y是对顶角,与y相等,命题符号化为 分析 (2),(5),(6)中要使用2无谓词,用它们来描述事物之间的关系。 2.4 (1)对所有的x,存在着y,使得,在中为真命题,在中为假命题。 (2)存在着对所有的y,都有,在中为真命题,在中为假命题。 (3)对所有x,存在着y,使得,在中均为假命题,而在中为线)存在着x,对所有的y,都有,在中都是假命题。 (5)对所有的x,存在着y,使得在中都是线)存在x,对所有的y,都有,在中为真命题,在中为假命题。 (7)对于所有的x和y,存在着z,使得,在中为真命题,在中为假命题。 2.5 (1)取解释为:个体域(实数集合),为有理数,能表示成分数,在下,的含义为 “对于叙何实数x而言,若x为有理数,则x能表示成分数”,简言之为“有理数都能表示成分数。”在此蕴含式中,当前件为真时,后件也为真,不会出现前件为真,后件为假的情况,所以在下,为真命题。 在在下,的含义为 “对于任何实数x,x既为有理数,又能表示成分数。” 取,则显然为假,所以,在下,为假命题. (2) 取解释为:个体域D=N(自然数集合), 为奇数, 为偶数,在下,的含义为 “存在自然数x,x发既为奇数,又为偶数。” 取,则为假,于是为真,这表明为真命题。 分析 本题说明 这里,表示A与B不等值,以后遇到,含义相同。 在一阶逻辑中,将命题符号化时,当引入特性谓词(如题中的之后,全称量词后往往使用联结词→而不使用,而存在量词后往往使用,而不使用→,如果用错了,会将真命题变成假命题,或者将假命题变成线 在解释R下各式分别化为 (1) (2) (3) (4) 易知,在解释R下,(1),(2)为假;,(3)(4)为线 给定解释为:个体域D=N(自然数集合),为奇数,为偶数。 (1)在解释下,公式被解释为 “如果所有的自然数不是奇数就是偶数,则所有自然数全为奇数,或所有自然数全为偶数。”因为蕴含式的前件为真,后件为假,所以线)在下,公式解释为 “如果存在着自然数为奇数,并且存在着自然为偶数,则存在着自然数既是奇数,又是偶数。” 由于蕴含式的前件为真,后件为假,后以真值为假。 分析 本题说明全称量词对析取不满足分配律,存在量词对合取不满足分配律。 2.8 令在A中,无自由出现的个体变项,所以A为闭式。 给定解释:个体域D=N(整数集合),为正数,为负数,,在下,A的含义为 “对于任意的整数x和y,如果x为正整数,y为负整数,则。” 这是真命题。 设解释:个体域D=R(R整数集合),为有理数,为无理数,,在下,A的含义为 “对于任意的实数x和y,如果x为有理数,y为元理数,则。” 这是假命题。 分析 闭式在任何解释下不是真就是假,不可能给出解释I, 使得闭式在I下真值不确定,这一点是闭式的一个重要特征。而非封闭的公式就没有这个特征。 2.9 取和,则和都是非土产的公式,在中,x, y都是自由出现的,在中,y是自出现的。 取解释I为,个体域D=N(N为自然数集合),为。在I下,为为假,所以在I下,真值不确定,即在I下的真值也是命题。 在I下,为当时,它为真;时为假,在I下的真值也不确定。 分析 非闭式与 闭式的显著区别是,前者可能在某些解释下,真值不确定,而后者对于任何解释真值都确定,即不是真就是假。 当然非闭式也可以是逻辑有效式(如),也可能为矛盾式(如,也可能不存在其值不确定的解释。 2.10 (1) (消去量词等值式) (德·摩根律) (消去量词等值式) (2) (消去量词等值式) (德·摩根律) (消去量词等值式) 2.11 (1) 令为人。 长着绿色头发。 本命题直接符号化验为 ] 而 (量词否定等值式) (德·摩根律) (蕴含等值式) 最后一步得到的公式满足要求(使用全称量词),将它翻译成自然语言,即为 “所有的人都不长绿色头发”。 可见得“没有人长着绿色头发。”与“所有人都不长绿色头发。”是同一命题的两种不同的叙述方法。 (2)令是北京人 去过香山。 命题直接符号化为 ] 而 (双重否定律) (理词否定等值式) (德·摩根律) (蕴含等值式) 最后得到的公式满足要求(只含全称量词),将它翻译成自然语言,即为 “并不是北京人都去过香山。” 可见,“有的北京人没过过香山。”与“并不是北京人都去过香山。”是同一命题不同的叙述方法。 2.12 (1) (2) (量词辖域收缩扩张等值式) (3) 分析 在有穷个体域内消去量词时,应将量词的辖域尽量缩小,例如,在(2)中,首先将量词辖域缩小了(因为中不含x,所以,可以缩小)。否则,演算是相当麻烦的。见下面的演算: 显然这个演算比原来的喾算麻烦多了。 2.13 在I下 (1) 所以,在下为假。 (2) 所以,此公式在I下也是假命题。 (3) (量词分配等值式) 所以,此公式在I下为线) (量词否定等值式) (约束变项换名规则) (量词辖域收缩扩张等值式) (2) 在以上演算中分别使用了德·摩根律、量词否定等值式、约束变项换名规则等。 分析 公式的前束范式是不唯一的。(1)中最后两步都是前束范式,其实 也是(1)中公式的前束范式。 2.15 (1) (2) 在以上演算中分别使用了自由变项换名规则和量词辖域收缩扩张等值式。 2.16 (1)②错。使用UI,UG,EI,EG规则应对前束范式,而①中公式下不是前束范式,所以,不能使用UI规则。 (2)。①中公式为,这时,,因而使用UI规则时,应得(或),故应有而不可能为 (3)②错。应对使用EG规则,其中c为特定的使A为真的个体常项,而不能为个体变项。 (4)②错。①中公式含个体变项x,不能使用EG规则。 (5)②错。①公式含两个个体常项,不能使用EG规则。 (6)⑤错。对①使用EI规则得,此c应使为真,此c不一定使为真。 分析 由于⑤的错误,可能由真前提,推出假结论。反例如下: 设个体域为自然数集合为偶数,为素数,能被3整除,能被4整数,显然此时, 与 均为线)中,③应为,它是真命题,而为假命题。对使用EI规则,得才为真。所以,对两个公式使用EI规则使用同一个个体常项是会犯错误的。 2.17 (1)证明 ① 前提引入 ② 前提引入 ③ ①② 假言推理 ④ ②EI ⑤ ④附加 ⑥ ③UI ⑦ ⑤⑥假言推理 ⑧ ⑦ EG (2)证明: ① 前提引入 ② ①EI ③ 前提引入 ④ ③UI ⑤ ②④假言推理 ⑥ ⑤化简 ⑦ ②⑥合取 ⑧ ⑦ EG 2.18 令是大熊猎。 产在中国。 欢欢 前提: 结论: 证明: ① 前提引入 ② 前提引入 ③ ①UI ④ ②③假言推理 2.19令为有理数。 为实数。 为整数。 前提: 结论: 证明: ① 前提引入 ② 前提引入 ③ ①② 假言推理 ④ ②EI ⑤ ④附加 ⑥ ③UI ⑦ ⑤⑥假言推理 ⑧ ⑦ EG (2)证明: ① 前提引入 ② ①EI ③ 前提引入 ④ ③UI ⑤ ②化简 ⑥ ④⑤假言推理 ⑦ ②化简 ⑧ ⑥与⑦合取 ⑨ ⑧EG 分析 在以上证明中,不能如下进行。 ① 前提引入 ② 前提引入 ③ ②UI ④ ①EI 至此,可能犯了错误,在③中取则为真,但为假,就是说,由UI规则得到的c不一定满足EI规则,但反之为线 答案 A:③; B:② 分析 (7)式为非闭式,在个体域为整数集Z时,的真值不能确定,当时为真,当时为假,所以,它不是命题,其余各式都是命题。(5)虽然不是闭式,但它为线 答案 A:②; B:④,⑤,⑨ C:⑦; D:⑧ 分析 注意约束变项和自由变项改名规则的使用。供选答案中,(1)的前束范式只有一个,就是②。而②的前束范式有3个,当然它们都是等值的。(3)的前束范式有2个,就是⑦和⑧。注意,在(3)式中,的辖域为,这就决定了它们的前束范式为 , (将自由出现的y改名为z) 所以,⑧也是(3)的前束范式。 2.22 答案 A:⑤。 分析 (1),(4)正确;可以构造证明。 (1)证明: ① 前提引入 ② ①EI ③ 前提引入 ④ ③UI ⑤ ②④假言推理 ⑥ ⑤EG 注意应先使用EI规则。 (4)证明: ① 前提引入 ② ①UI ③ 前提引入 ④ ②③拒取式 ⑤ ④UG (2),(3)推理不正确,只要举出反例即可. 在自然数集合中,令是偶数, 是素数,则为真命题,而为假命题,所以, 不是逻辑有效蕴含式,这说明(2)是推理不正确,读者可举反例说明(3)中推理也不正确. 2.23 答案 A: ② B:① C: ⑦ D:⑤ 第3章 习题解答 3.1 A:③; B:④; C:⑤; D:⑦;E:⑧ 3.2 A:③;B:①; C:⑤; D:⑥; E:⑦ 3.3 A:①;B:③; C:⑧; D:⑤; E:⑩ 分析 对于给定的集合或集合公式,比如说是A和B,判别B是否被A包含,可以有下述方法: 1° 若A和B是通过列元素的方式给出的,那么依次检查B中的每个元素是否在A中出现,如果都在A中出现,则否则不是。例如,3.3题给的答案中有{{1,2}}和{1},谁是的子集呢?前一个集合的元素是{1,2},要S中出现,但后一个集合的元素是1,不在S中出现,因此,{{1,2}} 2° 若A和B是通过用谓词概括元素性质的主试给出的,B中元素的性质为P,A中元素的性质为Q,那么, “如果P则Q”意味着 “只有P才Q”意味着 “除去P都不Q”意味着 “P且仅P则Q”意味着 例如,3.1题(1)是“如果P则Q”的形式,其中“计算机专业二年级学生”是性质P,“学《离散数学》课”是性质;题(2)是“P且仅P则Q”的形式,此外 “如果P就非Q”则意味着。 例如,3.1 题(3)和3.2题(3)都是这种形式。 3° 通过集合运算差别如果,,三个等式中有任何一个成立,则有。 4° 通过文氏图观察,如果代表B的区域落在代表A的区域内部,则。这后两种方法将在后面的解答中给出实例。 3.4 A:②; B:④; C:⑦; D:⑥;E:⑧ 3.5 A:②;B:④; C:⑤; D:⑥; E:⑨ 3.6 A:①;B:⑨; C:④; D:⑦; E:⑧ 3.7 A:④;B:⑨; C:①; D:⑧; E:① 分析 设只买1本、2本及3本书的学生集合分别为和,它们之间两两不交,由题意可知, 又知,所以, 然后列出下面的方程: 求得.因此,没有买书的人数是 75-(10+35+20)=10. 3.8 (1)和(4)为真,其余为假. 分析 这里可以应用集合运算的方法来差别集合之间的包含或相等关系.如题(3)中的条件意味着, ,这时不一定有S=T成立.而对于题(4),由条件~可推出 这是的充公必要条件,从而结论为真. 对于假命题都可以找到反例,如题(2)中令即可;而对于题(5),只要即可. 3.9 (2),(3)和(4)为线) 任何 (3) (4) (5) 且. 3.12 (1),(2)和(6)都是而(3),(4),(5)是A=B. 分析 对于用谓词给定的集合先尽量用列元素的方法表示,然后进行集合之间包含关系的判别.如果有的集合不能列元素,也要先对谓词表示尽可能化简.如题(3)中的A可化简为 题(5)中的A和B都可以化简为;题(6)中的 而对于题(4),不难看出A=B=R,是实数集合. 3.13 (1) (2) (3) (4)观察到故 (5) 观察到,故 3.14 (1) (2) (3) , (4) (5) 分析 在做集合运算前先要化简集合,然后再根据题目要求进行计算.这里的化简指的是元素,谓词表示和集合公式三种化简. 元素的化简——相同的元素只保留一个,去掉所有冗余的元素。 谓词表示的化简——去掉冗余的谓词,这在前边的题解中已经用到。 集合公工的化简——利用简单的集合公式代替相等的复杂公式。这种化简常涉及到集合间包含或相等关系的判别。 例如,题(4)中的化简后得,而题(5)中的化简为。 3.15 3.16 (1),(2),(3)和(6)为线)不为真。 分析 如果给出的是集合恒等式,可以用两种方法验证。一是分别对等式两边的集合画出文氏图,然后检查两个图中的阴影区域是否一致。二是利用集合恒等式的代入不断对等式两边的集合公式进行化简或者变形,直到两边相等或者一边是另一边的子集为止。例如,题(1)中的等式左边经恒等变形后可得到等式右边,即 类似地,对题(2)和(3)中的等式分别有 但对于等式(4),左边经变形后得 = 易见,但不一定有如令时,等式(4)不为线)的左边经化简后得,而不一定恒等于A-C。 3.17 (1)不为线)都为线)举反例如下:令 则且,但,与结论矛盾。 分析 (2)由于又由可得即成立。 (3)由于,故有 。 这里用到的充要条件为或或 (4)易见,当A=B成立时,必有A-B=B-A。反之,由A-B=B-A得 化简后得,即,同理,可证出,从而得到A=B。 3.18 由可知B=6。又由知,代入包含排斥原理得 从而有 3.19 令 是完全平方数}, 是完全立方数}, 从而有代入包含排斥原理得 =998910 第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中的 而题4.2中的 为得到题4.3中的R须求解方程,最终得到 求有三种方法,即集合表达式、关系矩阵和关系图的主法。下面由题4.2的关系分别加以说明。 1°集合表达式法 将的元素列出来,如图4.3所示。然后检查R的每个有序对,若,则从中的x到中的y画一个箭头。若中的x经过2步有向路径到达中的y,则。由图4.3可知 如果求,则将对应于G中的有序对的箭头画在左边,而将对应于F中的有序对的箭头画在右边。对应的三个集合分别为,然后,同样地寻找到的2步长的有向路径即可。 2° 矩阵方法 若M是R的关系矩阵,则的关系矩阵就是M·M,也可记作M2,在计算乘积时的相加不是普通加法,而是逻辑加,即0+0=0,0+1=1+0=1+1=1,根据已知条件得 中含有7个1,说明中含有7个有序对。 图4.3 图4.4 3°关系图方法 设G是R的关系图。为求的关系图,无将G的结点复制到中,然后依次检查G的每个结点。如果结点x到y有一条n步长的路径,就在中从x到y加一条有向边。当所有的结点检查完毕,就得到图。以题4.2为例。图4.4(1)表示R的关系图G。依次检查结点1,2,3,4。从1出发,沿环走2步仍回到1,所以,中有过1的环。从1出发,经1,1和1,4,2步可达4,所以,中有从1到4的边。结点1检查完毕。类似地检查其他3个结点,2步长的路径还有2→1→1,2→1→4,3→4→1,4→1→1,4→1→4。将这些路径对应的边也加到中,最终得到的关系图。这个图给在图4.4(2). 4.4 A:④; B:⑧; C:⑨; D:⑤; E:⑩ 分析 根据表4.1中关系图的特征来判定的性质,如表4.2所示。 表4.2 自反 反自反 对称 反对称 传递 √ √ √ √ √ √ √ √ √ √ 从表中可知和不是传递的,理上如下:在中有边3,1和1,2,但缺少边3,2.在中有边1,3和3,2,但缺少边1,2。在中有边1,2和2,1,但缺少过1的环。 4.5 A:①; B:③; C:⑧; D:⑨; E:⑤ 分析 等价关系和划分是两个不同的概念,有着不同的表示方法,等价关系是有序对的集合,而划分是子集的集合,切不可混淆起来,但是对于给定的集合A,A上的等价关系R和A的划分中一一对应的,这种对应的含义是 和y在的同一划分块里。 拘句话说,等价说系R的等价类就是划分的划分块,它们表示了对A中元素的同一种分类方式。 给定划分,求对应的等价关系R的方法和步骤说明如下: 1°设中含有两个以上元素的划分块有块,记作。若,,则求出。 2° 本题中的的划分块都是单元集,没有含有个以上元素的划分块,所以,含有两个划分块,故对应地等价关系含有两个等价类。中只有一个划分块包含了集合中的全体元素,这说明因此,这个划分块对应的关系就上的全域关系,从而得到也是上的全域关系。 4.6 A:③; B:⑩; C:⑤; D:⑩; E:⑤ 分析 画哈斯图的关键在于确定结点的层次和元素间的盖住关系,下面讨论一下画图的基本步骤和应该注意的问题。 画图的基本步骤是: 1° 确定偏序集中的极小元,并将这些极小元放在哈斯图的最底层,记为第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给出了最终得到的哈斯图。在整除关系的哈斯图中,盖住关系体现为最小的倍数或最小的公倍数关系。 如果偏序集是,那么哈斯图的结构将呈现出十分规则的形式。第0层是空集,第1层是所有的单元集,第2层是所有的2元子集,…,直到最高层的集合A。这里的盖住关系就体现为包含关系。 在画哈斯图时应该注意下面几个问题。 1°哈斯图中不应该出现三角形,如果出现三角形,一定是盖住关系没有找对。纠正的方法是重新考察这3个元素在偏序中的顺序中的顺序,然后将不满足盖住关系的那条边去掉。请看图 4.6(1)中的哈斯图。图中有两个三角形,即三角形abc和abd。根据结点位置可以看出满足如下的偏序关系: 从而得到和。这就说明c和d不盖住a,应该把ac边和ad边从图中去掉,从而得到正确的哈斯图,如图4.6(2)所示。 2° 哈斯图中不应该出现水平线段。根据哈斯图的层次结构,处在同一水平位置的结点是同一层的,它们没有顺序上的“大小”关系,是不可比的。出现这种错误的原因在于没有将“较大”的元素放在“较小”元素的上方。纠正时只要根据“大小”顺序将“较大”的元素放到更高的一层,将水平线° 哈斯图中应尽量减少线的交叉,以使得图形清晰、易读,也便于检查错误,图形中线的交叉多少主要取决于同一层结点的排列顺序,如果出现交叉过多,可以适当调正结点的排列顺序,注意变动结点时要同时移动连线。 最后谈谈怎样确定哈斯图中的极大元、极小元、最大元、最小元、最小上界和最大下界,具体的方法是: 1° 如果图中有孤立结点,那么这个结点既是极小元,也是极大元,并且图中既元最小元,也元最大元(除了图中只有唯一孤立结点的特殊情况)。 2° 除了孤立结点以外,其他的极小元是图中所有向下通路的终点,其他的极大元是图中所有向上通路的终点。 3° 图中唯一的极小元是最小元,唯一的极大元是最大元;否则最小元和最大元不存在。 4° 设B为偏序集的子集,若B中存在最大元,它就是B的最小上界;否则从A-B中选择那些向下可达B中每一个元素的结点,它们都是B的上界,其中的最小元是B的最小上界。类似地可以确定B的最大下界。 观察图4.5,1是所有向下通路的终点,是极小元,也是最小元,向上通路的终点有9,6,8,10和7,这些是极大元。由于极大元不是唯一的,所以,没有最在元。地于整个偏序集的最小上界和最大下界,就是它的最在元和最小元,因此,该偏序集没有最小上界,最大下界是1。 4.7 A:④; B:⑤; C:③; D:①; E:⑦ 4.8 A:②; B:①; C:④; D:②; E:⑨ 分析 给定函数,怎样判别它是否满足单射性呢?通常是根据函数的种类采取不同的方法。 1° 若 是实数区间上的连续函数,那么,可以通过函数的图像来判别它的单射性。如果的图像是严格单调上升(或下升)的,则是单射的。如果在的图像中间有极大或极小值,则不是单射的。 2° 若不是通常的初等函数。那么,就须检查在的对应关系中是否存在着多对一的形式,如果存在但,这就是二对一,即两个自变量对应于一个函数值,从而判定不是单射的。 下面考虑满射性的判别,满射性的判别可以归结为的值域的计算。如果,则是满射的,否则不是满射的。求的方法说明如下: 1° 若是实数区间上的初等函数,为了求首先要找到的单调区间。针对的每个单调区间求出的该区音的最小和最大值,从而确定在这个区间的局部值域。就是所有局部值域的并集。对于分段的初等函数也可以采用这种方法处理。 2° 若是用列元素的方法给出的,那么就是所有有序对的第二元素构成的集合。 本题中只有是定义于实数区间上的初等函数。易见,指数函数的图像是严格单调上升的,并且所有的函数值都大于0。从而知道是单射的,但不是满射的。对于,由 可知,它不是单射的。但,所以,它是满射的。既不是单射的,也不是满射的,因为且是单射的,但不是满射的。因为时,必有但 4.9 A:③; B:①; C:⑦; D:⑤; E:⑨ 分析 (1)先求出T的特征函数,它是从S到的函数。而中的函数是从到的函数,这就是说该函数应包含3个有序对,有序对的第一元素是,而第二元素应该从中选取(可以重复选取)。不难年出只有①满足要求。 (2)等价关系R对应的划分就是商集S/R。检查R的表达式,如果,那么x,y就在同一个等价类。不难看出S中的元素被划分成两个等价类:,因而对应的划分有2个划分块。 考虑自然映射它将S中的元素所在的等价类,即将a映到,将b映到,将c映到,将g写成集合表达式就是 通常的自然映射是满射的,但不一定是单射的,除非等价关系为恒等关系,这时每个等价类只含有一个元素,不同元素的等价类也不同,g就成为双射函数了。 4.11 (1) (2) (3) ] 4.12 对称性 4.13 4.14 图4.7 分析 根据闭包的计算公式 可以得到由关系图求闭包的方法. 设G是R的关系图,G的结点记为的关系图分别记作和. 为求,先将图G的结点和边拷贝到中缺少环的结点都加上环就得到了的关系图. 为求,也须将图G拷贝到,然后检查的每一对结点和.如果在和之间只存在一条单向的边,就在这两个结点间加上一条方向相反的边.当中所有的单向边都变成双向边以后就得到了的关系图. 最后拷虑.首先将图G拷贝到,然后从开始依次检查.在检查结点时,要找出从出发经过有限步(至少1步,至多n步)可达的所结点(包括自己在内)。如果从到这种结点之间缺少边,就把这条边加到中,当n个结点全部处理完毕,就得到的关系图。 以本题为例,依次检查结点从a出发可达四个结点,所以图中应该加上和的边。从b出发可达三个结点,所以,图中应该加上的边。从c出发可达c和d,在中应该加上边,即通过c的环,类似地分析可以知道,在中还应该加上过d的环。 4.15 若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,但是对于函数,则不允许这种一对多的对应。至于单射函数,不但不允许一对多,也不允许多对一,只能存在一对一的对应。为了判别一个关系是否为函数,就要检查关系的对应中是否存在一对多的情况。如本题中的(1)式,1,2和1,1同时在关系中出现,因此不是函数。又如(3)式,1,1和1,-1也同时在关系中出现,破坏了函数定义。 4.18 当时满足要求。 4.19 ,且 分析 注意合成的正确表示方法。表示和合成的方法有两种: 1°说明是从哪个集合到个集合的函数,然后给出的计算公式。 2° 给出的集合表达式。 本题中的结果都采用了第一种表示方法,先说明地果函数是从N到N的函数,然后分别给出函数值的计算公式。也可以彩用第二种方法,如 , 但是,如果写成就错了,因为是函数,是有序对的集合,与函数值是根本不同的两回事,不能混为一谈。 4.20 分析 首先由的双射性确定一定存在,然后通过的定义求出反函数的对应法则。设将对应到。根据的定义有 因而反函数的对应法则是对应到。 4.21 (1) 如下列出的对应关系 0 1 2 3 4 5 6 7 8… 1 2 3 4 0 5 6 7 8… 3 1 3 2 0 3 3 3 4… 从而得到 是满射的,但不是单射的。 (2) 4.22 (1) 其中 (2)令,且 分析 对于任意集合A,都可以构造从到的双射函数,任取A的子集的特征函数定义为 不同的子集的特征函数也不同,因此,令 是到的双射,在本题的实例中的是 4.23 (1) (2) 分析 给定集合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的双射函数。 例如,是实数区间。如图4.9所示,先将A,B区间分别标记在直角坐标系的x轴和y轴上,过(1,2)和(2,6)两点的直线方程将A中的每个数映到B中的每个数,因此,该直线方程所代表的一次函数就是从A到B的双射函数。由解析几何的知识可以得到双射函数 这种通过直线方程构造双射函数的方法对任意两个同类型的实数区间(同为闭区间、开区间或音开半闭的区间)都是适用的。但对半开半闭的区间要注意开端点与开端点对应,闭端点与闭端点对应。此外还要说明一点,对于某些特殊的实数区间可能选择其他严格单调的初等函数更方便,例如,,那么取即可。 3°A是一个无穷集合,B是自然数集N。 为构造从A到B的双射只须将A中的元素排成一个有序序列,且指定这个序列的初始元素,这就叫做把A“良序化”。比如说A良序化以后,是集合,那令 就是从A到B的双射。 例如,构造从整数集Z到自然数集N到自然数集N的双射。如下排列Z中元素,然后列出对应的自然数,即 观察这两个序列,不难找到对应法则。 显然f是从Z到N的双射。 最后要指出,并不是任何两个集合都可以构造双射的。比如说,含有元素不一样多的有穷集之间不存在双射。即使都是无穷集也不一定存在双射,如实数集R和自然数集N之间就不存在双射。这就涉及到集合“大小”的描述和度量方法,限于篇幅地此就不进行探入讨论了,有兴趣的读者可以阅读其他的《离散数学》书籍。 4.24 为N上的恒等关系,且有 与y的奇偶性相同。在N中的所有奇数构成一个等价类,所有的偶数构成另一个等价类。因此, ,即x除以3的余数与y除以3的余数相等。根据余数分别这0,1,2,可将N中的数分成3个等价类,因而 4.25 (1) 不是单射也不是满射。 。 (2) 不是单射也不是满射。 第5章 习题解答 5.1 A:③; B:⑥; C:⑧; D:⑩; E:⑨ 分析 S为n元集,那么有个元素.S上的一个二元运算就是函数.这样的函数有个.因此上的二元运算有个. 下面说明通过运算表判别二元运算性质及求特导元素的方法. 1 °交换律 若运算表中元素关于主对角线成对称分布,则该运算满足交换律. 2 °幂等律 设运算表表头元素的排列顺序为如果主对角线元素的排列也为 则该运算满足幂等律. 其他性质,如结合律或者涉及到两个运算表的分配律和吸收律,在运算表中没有明显的特征,只能针对所有可能的元素等来验证相关的算律是否成立. 3 ° 幺元设运算表表头元素的排列顺序为如果元素所在的行和列的元素排列顺序也是则为幺元. 4 ° 零元如果元素所在的行和列的元素都是,则是零元. 5 ° 幂等元.设运算表表头元素的排列顺序为如果主对角线上第个元素恰 为那么是幂等元.易见幺元和零元都是幂等元. 6 ° 可逆元素及其逆元.设为任意元素,如果所在的行和列都有幺元,并且这两个幺元关于主对角线成对称分布,比如说第行第列和第行第列的两个位置,那么与互为逆元.如果所在的行和列具有共同的幺元,则幺元一定在主对角线上,那么的逆元就是自己.如果所在的和地或者所在的列没有幺元,那么不是可逆元素.不难看出幺元一定是可逆元素,且;而零元不是可逆元素. 以本题为例,的运算表是对称分布的,因此,这三个运算是可交换的,而不是可交换的.再看幂等律.四个运算表表头元素排列都是,其中主对角线元素排列为的只有,所以, 遵从幂等律.下面考虑幺元.如果某元素所在的行和列元素的排列都是,该元素就是幺元.不难看出只有中的a满足这一要求,因此,a是的幺元,其他三个运算都不存在幺元.最后考虑零元.如果a所在的行和列元素都是a,那么a就是零元;同样的,若b所在的行和列元素都是b,那么b就是零元.检查这四个运算表,中的a满足要求,是零元,其他运算都没有零元.在的运算表中,尽管a和b的列都满足要求,但行不满足要求.因而中也没有零元. 5.2 A:①; B:③; C:⑤; D:⑦; E:⑩ 分析 对于用解析表达式定义的二元运算 °和 *,差别它们是否满足交换律,结合律,幂等律,分配律和吸收律的方法总结如下: 任取,根据 °运算的解析表达式验证等式是否成立.如果成立 °运算就满足交换律. 2 ° °运算的地合律 任取根据 °运算的解析表达式验证等式是否成立. 如果成立, °运算就是可结合的. 3 ° °运算的幂等律 任取x,根据 °运算的解析表达式验证等式是否成立.如果成立, °运算满足幂等律. 4 ° °运算对*运算的分配律 任取,根据 °和*运算的解析表达式验证等式和是否成立。如果成立,则°运算对*运算满足分配律。 5 ° °和*运算的吸收律 首先验证 °和*运算是可交换的。然后任取根据 °和 *运算的解析表达式验证等式和是否成立。如果成立,则°和 *运算满足吸收律。 设°是用解析表达式定义的A上的二元运算,求解对于该运算的特导元素可以采用下述方法: 1 ° 求幺元e。根据幺元定义,应满足等式。将等式中的和用关于°运算的解析表达式代入并将结果化简,然后由x的任意性来确定 2 °求零元根据零元定义,应该满足等式。将等式中的和用关于 °运算的解析表达式代入并将结果化简,然后由x的任意性确定 3 ° 求幂等元. 将等式中的用关于 °运算的解析表达式代入并化简单,然后求解该议程,所得到的解就是幂等元. 4 ° 求可逆元素的逆元. 任取,设x的逆元为y,则x与y应该满足等式将等式中的与用关于°运算的解析表达式代入,并将e用 °运算的幺元代入,然后化简等式.观察使得该等式成产的x应该满足的条件,然后将y用含有x的公式表示出来,从而得到x的逆元.这里特别要说明一点,如果°运算不存在幺元则所有有元素都是不可逆的. 以本题为例,具体的分析过程如下: 任取,由 可知一般情况下,所以运算不是可交换的. 任取,由 可知运算是可结合的. 设运算的幺元为则有 , , 代入关于运算的解析表达式得 从而得到 由于是任意有理数,要使得上述四个等式都成立,必有 所以,运算的幺元为. 对于任意的,设的逆元为,那么有 代入关于运算的解析表达式得 从而得到 解得 这说明对一切,只要都存在逆元. 最后补充说明一点.不难验证, 运算没有零元.而关于运算的幂等元是和,其中为任意有理数. 5.3 A:⑦; B:⑥; C:⑤; D:③; E:② 分析 怎样检验运算是否为S上的二元运算,或者说S是否关于运算封闭?主要是验证以下两个条件是否满足; 1°任何S中的元素都可以作为参与运算的元素. 2° 运算的结果仍旧是S中的元素. 如果给定了两个以上的运算,在讨论封闭性时要分别对每个运算讨论. 容易验证本题中的6个函数全是实数集R上的二元运算.它们的可交换性,结合性, 幺元和零元的判别结果如下. 交换 结合 幺元 零元 √ × √ √ √ √ √ × √ √ √ × 为0 × 为1 × × × × × 为0 × × × 5.4 A:②; B:⑤; C:⑦; D:⑧; E:⑧ 分析 对于给定的自然数 是V的子代数,因为有 这说明关于+和运算都是封闭的,满足子代数的定义.由于可以取任何自然数,这样的子代数有无数多个.其中当时, 是有穷集合.即有限的子代数,其余都是无限的子代数. 对于来说,它是奇整数的集合.而奇数加奇数等于偶数,因而关于加法不封闭.类似地, 关于加法也不封闭,因为,但.因而可以判定和都不是V的子代数,尽管和对于乘法是封闭的. 5.5 A:④; B:⑨; C:①; D:①; E:④ 分析 构成代数系统的要素有三个:集合,二元或一元运算及代数常数.如果是代数系统和的同态,那么必须满足以下条件: 1° 即是和的函数. 2° 对和上任意对应的二元运算和有 对和上任意对应的二元运算和有 3° 对和上任意对应的代数常数和有 以本题为例.因为只有一个二元运算,验证时只要检验条件1°,2°即可.具体的验证过程如下:都是到的映射, 且 所以和是V的自同态.但是和不是V的自同态.原因如下: , 故,破坏了同态映射的条件2°.而对于,它将正数映到负数,根本不是到的函数,破坏了条件1°,当然更谈不到同态了. 通过上面的分析已经知道了判别同态及其性质的基本方法.下面补公介绍一些典型同态映射的实例,以供读者参考. 1°是整数加群.令这里的a是给定的整数.那么有 是V的自同态. 当时,不是单同态,也不是满同态,其同态象为. 当时, 为自同态. 当时,为单自同态,其同态象为,其中 2°是模n整数加群,其中.可以证明是V的自同态.因为有 由于p有n种取值,这里定义了n个自同态. 例如,上有6个自同态,即.其中 这3个自同态中和是自同构,其他的既不是单同态,也不是满同态.的同态象为.和的同态象为的同态象为. 3° 设分别为整数加群和模n整数加群.容易证明是 满同态. 4° 设其中和分别代表实数集和非零实数集,+和·分别代表普能加法和乘法.是和的单同态,其同态象为,这里的是正实数集. 5° 设 是具有一个二元运算和代数系统. 和的积代数为令,那么是积代数到同态的,因为对任意有 容易看出是满同态.只有当B为单元集时为同构. 5.6 A:⑤; B:③; C:②; D:①; E:⑧ 5.7 (1)和(4)是代数系统. (2)不是,例如 (3)不是,例如 (5)不是,例如 5.8 (1)封闭,若是16的倍数,则也是16的倍数. (2)不封闭,例如2和5互质,3也和5互质,但2+3=5却不和5互质. (3)不封闭,3和5都是30的因子,但是3+5=8不是30的因子. (4)封闭 5.9 (1)可交换,不幂等.a是幺元,且和c互逆元. (2)不可交换,有幂等性,元幺元,当然不考虑逆元了. (3)可交换,有幂等性, 幺元是和c都没有逆元. 分析 这里补谈谈结合律的判定问题.在验证结合律是否成立时,等式中的可以取中的任何元素,共有27种可能的选法.这意味着必须要要验证27个等式,工作量很大.若中有幺元或零元存在,则等式显然成立.考虑到这个因素,在验证时可以不选取集合中的幺元和零元.下面以本题为例来判定结合律是否成立. (1)a是幺元.只须对b和 c进行验证.又由于*运算的可交换性,全是b或全是c情况可以忽略,因而需要验证的只有下面六种情况: 由以上验证可知*运算是可结合的. (2)通过观察发现,有每个元素都是右零元.因而必有, 这就证明了结合律是成立的. (3)c是零元,故只须对a和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,1 1,0 1,1 2,0 2,1 0,0 0,0 1,0 1,0 2,0 2,0 0,0 0,1 1,0 1,1 2,0 2,1 1,0 1,1 2,0 2,0 0,0 0,0 1,0 1,1 2,0 2,1 0,0 0,1 2,0 2,0 0,0 0,0 1,0 1,0 2,0 2,1 0,0 0,1 1,0 1,1 其中0,1为幺元. 运算表如表5.3所示. 1 2 5 10 * 1 2 5 10 x 1 2 5 10 1 1 1 1 1 2 1 1 1 1 5 5 1 2 5 10 1 2 5 10 1 2 5 10 2 2 10 10 5 10 5 10 10 10 10 10 1 2 5 10 10 5 2 1 5.12 (1)可交换,不可结合,无幺元,无可逆元素. (2)不可交换,不可结合,无幺元,无可逆元素. (3)可交换,可结合, 幺元是1,有. 5.13 结果如表5.4所示. 表5.4 * 0 1 2 3 4 0 1 2 3 4 0 0 0 0 0 0 1 2 3 4 0 2 4 1 3 0 3 1 4 2 0 4 3 2 1 零元 0 幺元 1 逆元 0元逆元. 5.14 其中 第6章 习题解答 6.1 A:⑨; B:⑨; C:④; D:⑥; E:③ 分析 对于给定的集合和运算判别它们是否构成代数系统的关键是检查集合对给定运算的封闭性,具体方法已在5.3节做过说明. 下面分别讨论对各种不同代数系纺的判别方法. 1°给定集合S和二元运算°,判定S, °是否构成关群、独导点和群. 根据定义,判别时要涉及到以下条件的验证: 条件1 S关于 °运算封闭: 条件2 °运算满足结合集 条件3 °运算有幺元, 条件4 ° 其中关群判定只涉及条件1和2;独导点判定涉及条件1、2、和3;而群的判定则涉及到所有的四个条件。 2 ° 给定集合S和二元运算 °和 *,判定S, °, *是否构成环,交换环,含幺环,整环,域.根据有关定义需要检验的条件有: 条件1 S, °S构成交换群, 条件2 S, * 构成关群, 条件 3 * 对 °运算的分配律, 条件4 * 对运算满足交换律, 条件5 * 运算有幺元, 条件6 * 运算不含零因子——消去律, 条件7 有(对*运算). 其中环的判定涉及条件1,2和3;交换环的判定涉及条件1,2,3和4;含幺环的判定涉及条件1,2,3和5;整环的判定涉及条件1-6;而域的判定则涉及全部7个条件. 3° 判定偏序集或代数系统是否构成格、分本配格、有补格和布尔格. 若为偏序集,首先验证和是否属于S.若满足条件则S为格,且构成代数系统.若是代数系统且°和*运算满足交换律、结合律和吸收律,则构成格。 在此基础上作为分配格的充分必要条件是不含有与图6.3所示的格同构的子格。而有补格和布尔格的判定只要根据定义进行即可。注意对于有限格,只要元素个数不是2的幂,则一定不是布尔格。但元素个数恰为的有限格中只有唯一的布尔格。 以本题为例具体的判定过程如下: 由可知对+运算不封闭,根本不构成代数系统。 (2)由可知对*运算不封闭,也不构成代数系统。 (3)关于运算封闭,构成代数系统。且关于模n加法满足交换群的定义,关于模n乘法*满足关群的定义,且*对有分配律。因而构成环。但当n=6时,有中含有零因子2和3,不是整环,也不是域。类似地分析可知,当n为合数时,不是域,但n为素数时构成域。 (4)是偏序集。对于小于等于关系,显然有,构成格。但不是有补格,2和3没有补元,也不是布尔代数。 (5)容易验证关于矩阵加法构成群。 6.2 A:②; B:③; C:⑦; D:⑩; E:⑨ 分析 此处的G实际上是关于模n加法构成群,但关于模n乘法只构成独导点,而不构成群,因为0没乘法逆元。是循环群。2是2阶元 ,1和3是4阶元。 如何求群G中元素的阶?如果,则是n的正因子。首先

  语篇分析理论视角下高考英语阅读理解的试题研究——以四川省高考英语2009-2013年为例.pdf

  新课改视角下江西省和广东省高考英语(2011-2013)阅读理解内容效度对比研究.pdf

  国开(广西)50753-中国传统文化概观-2019春形成性考核作业4(25分)-辅导资料.docx

  国开(广西)50753-中国传统文化概观-2019春形成性考核作业3(25分)-辅导资料.docx

  《习 近 平新时代中国特色社会主义思想第十讲-坚定不移贯彻新发展理念》.ppt

本文链接:http://scrinzoom.com/qianshufanshi/540.html