离散数学及其应用解析

所需积分/C币:50 2015-12-03 16:59:28 1.94MB PDF

离散数学应用解析 课后习题 相当于一本习题集 题目答案
内容简介 本书就离散数学的两大部分—效理逻辑集合论及二元关系、图论、代数系统纷出了大量具有代表性的 习题及其解答。对一些典型的习题还给出了多种不同的解法,其目的在于师宽读者的思路 本书可作为大专院校离散数学课程的辅导读物,也可供广大从事计算机研究和应用的工程技术人员颇 读 丛书名高等学校教材 书名:高散微学及其应用习題解析 著者:爆彦小丰 黄任解辑:张属葛 特约辑:袁英 印刷章:北京牛山世兴印刷厂 装订新三河市斯還奖订厂 出版发行:电子工业出版社出版没行UHL:h:wwW.pba.c四m 北京咔降淀区万寿路3信箝邮编10005发行邴电话6821470 经销:各地新华书店经钠 开本:77×1091/16印张:65字数:164千字 版次:9年4月第!19年4月第!次印群 印数:1 800册 书号:75033559 TP·21 定价;9,0元 兀购买电子工业出鹹社的图书,如有缺頁、捌頁、就頁者,本社发行鄣负脅调换 版权所有“即必究 前 言 高散数学是高等院校计算机专业的核心课程,但初学者往往由于对寓散数学中某些概念 和定理理解得不够透彻,从而对一些习题无从下手。本书正是为了适应离散数半教学和自学 的这一需要可编写的。 高散敔学主要包括集合论及元关系数理逻辑、团论、代数系统这阿个部分,本书作为 离散数学及其应用》的配套教材,也相应地分为五章,其中第 三章由傅彦編写,第四五 章由顾小卡编写 本书共选编了283个习题,每题包含若于小题,其中集合论部分30个,数理逻辑部分28 个,二元关系部分58个,图论部分81个,代数系统部分86个。对于书中的习题,一般只给出 了一种解法,但对于一些典型的习题,我们也给出了多种解法,其目的在于使读者拓宽思路掌 握更多的技巧。 在编写本书的过程中,电子科技大学的刘乃琦教授和吴跃教授给作者以极大的帮助提出 了许多宝贵的意见,在此向他们表示衷心的感谢。 作者是在多年教学积的基础上编写本书的但由于水平有限,错误和不当之处在所难 免。恳切希望广大读者提出宝贵意见。 作着 195年8月 目录 篡一章集食论 血啁中◆是p号唱卓p血自b日日日早D自自唱D聊自日日自聊·自自·自自會日目自自會曾甲曾"·曾曾"· 器1.1集合及其表示… 甲:D·『聊■■■曾■自·昏·省曾曾P唱曾冒曾古晶晶 §12集合与元素的关系 ●●■●■■■■1着聊咖自自音■■口會■‘會暑曾 ……(2) 13集合的运算… (4) 第二章理辑 ………………(8) 521命题逻辑 甲血即日■即口啁■●日●·D■ 了·■■■■b §21.1命题 2.2命题的真值表… (10) 晷2.13公式及其性质" 1昏西晶L白·即■ ………(13) 器214范式 凸郾■■■■—咱自ψ 215推理理论……(16) §22谓词逻辑…………………………………"(20 22.1谓词与量词 ■省■■冒■■■ ■■■口■■冒pp·曾自血口曾晋鲁?冒山如 (20 §222谓词公式 223公式的解释与基本性质………… ,(23) 晷224谓词演算与推理 第三章二元关系 ●。●■嵋■■■■←■·■自卜ψdb■■■■↓■●ψ■dψb■■■画■■?■會冒■甲■「■ (31) 832二元关系及其表示 T鲁口鲁■日!■ …………(31) 器33关系的性质 ■■■噜自鲁唱·唱,自1曾·鲁·餐司 ……:(34 §34等价关系… 动p 聊◆山·■■·■↓b ■·哥■郾■■■■■■【自自·■自即■● …(41) 53.5次序关系 ■b■凸b凸■画■■■晶■■■■■鲁■■昏■■鲁鲁■鲁噜■■『曾■P■鲁鲁l唱q早曾?甲冒鲁■b …………(45) 836函数(映射) …………….4(49) 第四章图论…………………………………………………(53) 4.1图的结构 ……………………………(3) §4.2通路、回路与连通性 ………………"……(55) §4.3图的矩阵表示 血血■■命 …"……………………(59) 卖44欧拉图与汉密尔顿图 (62) 弱45树… 平管号◆音■即日■一自自·曾日■·· …………………(67 §4.6偶图与平面图 a吾b吾吾日日品4·品卩q日目器 …(73) 第五章代数系統 噌↓■西b■■■喜卩看咱■■着■■4 …(79) §5.1代数系统及其基本性质 D自自自·日日日●4吾·咱自冒即··P自日日日日自音■自自會号 852同态与同构 甲■■■■■甲 ■口昏督h吾b吾曾量口晋甲■■ ■【·白·自口 83 s5.3半群与独异 (86) 85.4群论 (88) 555格与布尔代数 ◆日日■甲↓■十 第一章集合论 §1.1集合及其表示 1.给出下列集合 (1)小于10的非负整数全体。 (2)1至2网的全体素数(质数) (3)小于100的12的整倍数。 解(1)设A为小于10的非负整数全体 则:A={0,1321334354678,9} (2)设B为1至20间的全体意数〔质数)。 则;B={2,3,5,7,11,13,17,19} (3)设C为小于100的12整倍数。 则:C-{12+24,36,48,60,7284,96; 2.选择合适的论域和谓词,写出下列集合 (1)从0到100的整数。 (2)奇数的全体。 (3)5的数。 (4)所有一元二次方程的解組成的集合。 (5)能被100整除的整数集合。 (6)直角坐标系中,单位元(不包括单位國周的点集 解(1)A={!∈并且(0≤x≤100)}。 (2)O={x|(距∈I)并且(x=2+1》}。 (3)B={x〔∈D)#且(x=5) (4)D={x|(x∈C)并且(a∈』并且(bEⅠ)拌且(c∈D并且(ax2十bx+c=0)} (5)E={x|〔∈I)并且(x=100)} (6)F={xy(x,y∈R并且(x2+y2<1》} 3.用列举元素法写出下列集合 (1){x|(x∈D并且(2<x<10)} (2){x|2是十进制的数宇符号}。 (3){x|x是P进制的数字符号},P=2,8,12。 (4)(x|(x=2)或(x=5)} (5)F=(x,y)(x,y∈D并且(0≤x≤2)并且(-2≤y≤1)} (6){xz是 the Peoples republic of china中的英文字母} 解(1)x|(x∈并且(2<x<10)}={345,6,7,89 (2){x|x是十进制的数字符号}={0,123+45,6,78,}。 (3){x!x是二进制的数字符号}={01} x|x是八进制的数字符号}={01234567} x|x是十二进制的数字号}={0,1,2,3,4,5,6,7,8,9,10,13}e (4)〈x|(x=2)或(x=5)}={25} 5)F={(x,y)(x,y∈功并且(0≤x≤2)并且(-2≤y≤1)}={0,-2),〈0,-1}, 0,0),(0,1},1,-2),1,一1),1,0》,<1,1),2,-2),〈2+-1),〈2,0 6){xx是 the People' s Republic of China中的英文字母} {a3bc,e,∫h,i,"屮户 4,设全集为I下列哪些集合是相等的? 1)A=【x|x是数或奇数}。 (2)B={x1(3y)(y∈并且(x=2y))}。 (3)={1,2,3}。 4》D=101,-12,-2,3,-34,-4,}。 (5)E=(2crEI) (6)F={3,3,2,1,2}。 7)G-{x|x2-6x2-7x-6=0} 8)H={x:x3-6x2+11x-6=0 解其中 A=DE B=E C=F=F。 12集合与元素的关系 1.找出下列集合之间的关系。 (1}A={x(x∈I并且(1<x<5)}。(2)B={23}。 3)C={x|x2-5x+6=0)} (4)D={2,3H}。 (5)E={2}。 (6)F={x|(x=2)或(x=3)或(x=4)或(x=5) (7)G={2x|(1≤z≤3)} (8)H={x(x∈D)并且(x2+x+1=0)} 佩 HCECBCACF: B∈ D, HCECGI HCC:HCD 2.设S={N,Q,R},问下列命題是杏正确。 (1)2∈N,N∈S,则2∈S (2)NCQ,QES则NCS。 (3)NCQ,QCR,则NcR 解(1},(2}是错误的:(3)是正确的。 3.求下列集合的基数和每个集合的幂集 (1){1,2,3}。 (2){1,{2,3}}。 (3){{1{2,3}}。 (4){{2},{2,1,1}。(2,1,2,1}} (5){(西2}{2}}。 (6)[a,(a}} (7){φ,a,{}}。 解(1)基数为3幂集为:{φ,1}:(2},(3},{1,2},{1,3}{23}{1,2,3}} (2)若数为2,赛集为:{,{1},{2,3}}{1{23}。 3)基数为1,幂集为:{,{1,{23}k (4)基数为1,幂梨为:{中,{1,2}}〕 5)基数为2幂集为:{φ,{{,2}},2}},{φ2};{2}}。 (6)数为2,篝集为;{@,{a},{a}},{a,a}} 〔7)基数为3幂集为:{{a}{$},{{b}},{a},{}},a},,{}}}。 4.设A=φ,B={a求P(A),P(PA)),P(P(P(A),P(B)P(P(B)),P〔P〔P(B)))。 解P(A)={},P(P(A》)={,{}},P(P(P(A))={,{},{},{φ,{)}, P(B){,{a}},P(P(B))=,},ta}{,{a}}}P(P(P(B)){,{}, 1}},{{a}}},{,!a}},师,}}{,},埂,锺。{a}}:{{}{,{a} {a},{φ,a}}},{{φ},{{a},{φ,{φ},{a}},{φ,{a},{,{a}}},{φ}, a}φ,{a}}},{φ,{s},{,{a}},{中,{},{{a} 5.A,BC是集合若A∈B且B∈C有可能A∈C吗?常有A∈C吗?举例说明 解设A={a},B={a}},C={{a},{a} 则由A∈B且B∈C,有A∈C。但由A∈B且B∈C,不一定常有A∈C 设A-{a},B={{a}},C={{la}}。 则有A∈B且B∈C,但A∈C。 6,简要说明:{2}与!{2}}的区别,举出它们的元素与于集。 解{2}是以元亲为元意的集合,元为2子集有,{2} {{2}}是以集合为元系的集合,元素为{2};子集有,《{2}}。 7.筒要说明:φ与{}的区别,举出它们的元与子集。 解φ是无任何元素的集合。子集有φ 如}是以集合为元素的集合,元素为中于集有¢,{。 8.有可能有ACC且A∈C吗?论证你的断言 佩AcC且A∈C不一定成立。 如A={a},C-{a,{ar},则AcC且AEC同时成立 但若A={a},C=({a},则AC恒A∈C。 9.确定下列命题是否为真。 (2)Φ∈。 4)∈{业} (5)亟s{{9}}。(6)∈{{φ}}。(7){φ}s{φ}。(8){φ}∈{}}。 (9){φ}{φ,{φ}}。(10){φ}∈{φ,{}(11){{}}s{φ,{如}}。 12){{@}}∈{,{@}。(13){ais{{a}}。(14){a}∈{a}。 (15){a}s{,a}},(16){a}∈{a,{a}}。 解(1),〔3),(4),(5),(8},9},〔10),〔11),〔14),(15〕,(16)是真耷,其余是假命题 10.证明:若abc和d是任意客体,则{{a},{a,b}}={{c},{c,d}当且仅当a=c,b=d 证明若{},{a:b}}={c},{c,d}},则由集合的定义有ta}={c},{ab}={cd} 由{a}={c}知a=c,{a6}={c;以}={a,d,有b=d。 1⊥.设A:BC是集合,证明或反吸下列断言 (1)A∈BAR∈C→A∈C。 (2)A在BAB∈C>A6C。 (3)A∈BABC→>A∈Ca 4) ACBABEC→A∈C。 5)a∈ AMACE→∈B 解(1)结论不一定成立。 (a)若A={a},B={b},C={语b}},则有A妊BAB∈C,但AC 若A={a},B={b},C={{a},{b}},则有A6 BABEC→A∈Ca 3 (2)结论不-定成立。 (a)若A={a},B={b},C={{a}},则有A∈BAB∈C,但A∈C (b)若A={a}B={b},={ch,则有ABAB∈C→A∈C。 (3)结论不一定成立。 a)若A=(a},B={4}}C=(a}},则有A∈BABC,但A∈C b)若A={a},B={la}},C={c},则有A∈B∧BC→A套C (4)转论不一定成立。 (a)若A={a},B={a,b},C={th},则有 ACBABEC但A∈C b)若A={a},B={ab},C={c},则有 ACBAB(C→A〔C 〔5)纳论成立。 由ACB知:对任意x∈A,有北∈B。因为a∈A,所以a∈B §1.3集合的运算 1设全集U={1,2,3,4,5}。A=(14}B={1,2,5},C={2,4}确定下面的集合 (1)A∩B。(2)(A∩BUC。(3)(A∩BU(A∩C)(4)AUB 5)A∩B。(6)B∩C (?BC。 8)2U2C。 解(1)A∩B=({4})。 (2)(A∩B)∪C={1,35} (3)(A∩B)U(A∩C)={1,4}。(4AUB=(3}。 A∩B={ (6)B∩C=1 (7)BUC={1,3,4,53 (8)2U2={φ{1},{2}{4},4}{2,4}}。 2.设A={ 丿升且(x<5》},B={x|(x∈E)并且(x<7)}求AUB,A∩B 解A={xc(x∈N)并且(x<5》={0,12,3,4}, B={x|(x∈E+)并且(x<7)}={2,46} A∪B=(0,1,2,34+6},A∩B={2 3设A={x|x是book中的字母},B={x|x是 black中的字母}求AUB,AnB。 解A=(x|x是bk中的字得}=tb,,k} B={a!x是back中的字母}={bya+E,k} AUB={abrC,k*0),A自B={b}。 4.给定自鬆数桌合N的下列子集: A={1,2,7,8}; 丑={i|E2<50} C={lG可被3整除)并且0≤≤30)}D={训(计2并且(∈)并且(1≤≤6)}。 求下列集合 (1)AU〔BUC∪D)) (2)A∩(B∩nD))。 C3)B-(AUC) (4)(AhB)∩D 解A={1,27,8}B={0,1,2,3,4,5,6,7 C={0,3,69,1215182124y27,30},D={2,4,8,16,32;64} (1)A∪(RU(CUD))={0,,2,3,435:647,8,9,12151618,21,24,27,30,32 64} (2)A∩(B∩(门D))=中 3)B-(AUC)={4,5}。 4)〔A∩B)∩D=《4}。 5.求下列集合的结果。 (1)I-N。(2)UN。(3)I-(I-N)。4)kUQ。(5)R-一Q 解(1)【-N={-1,-2,-3, (2)rUN=, 3)I-(亠N)=I-I=N。 (4)RUQ=R (5)R一Q=S(S是无理效的集合)。 6.设A=(3,4}B=(4,3H∩sC={34}∩;D={x(x2-7x+12=0)并且(x∈R)}; 已={中34};F={4,生,3}G={4,,3,3}。问上述集合中哪些是相等的?郧些是不相等的? 解A=F=DAB=C↓E=G 7.当A≠时:若只有:(1)AUB=AUC,是否一定有B=C (2)A∩B=A∩C,是否一定有B=C (3)(AUB=AUC)并且(A∩B=A∩C),是否一定有B=C? 解《1)不一定成立。当AB,A=C,但B≠C时,则有AUB=AUC,但B≠C 2)不一定成立。当AB,A≤C,但B≠C时,则有A∩B=A∩C,但B≠C 3)结论成立 证明B=BU(B∩A)=BU(A∩B)=BU(A∩C)=(BUA)∩(BUC (AUBn(BUC)=(AUC)n(BUC)=(ANB)UC=(AnCUC=C. 8.设A,B,C均为矿的子集,问下列命题谁对?谁错? 1) ACBHAUB=B(2)ACB台AUB=A。 (3)ACB白A∩B=A。 4)ACBA∩B=B。(5)ACB冷AU(B-A)=B。〔6)BCA台A-B∩R=A 解(1),(3),(5)正确;(2),(4),(6)错误 9设A,B为任意集合,证 (1)ACB→P(AP(B)。 (2)P(A)cP(B)→A三B。 (3)P(A)=P(BA=B。 证明(1)设A∈B。 对任意x∈P(A)有xsA,又A∈B,所以rcB即有x∈P(B)。所以 PCCP(By (2)设P(A)三P(B) 对任意x∈A,有{x}∈PA,又P(A)三P(B),所以{x}∈PB)即有x∈B 所以AcB 〔3)“→设PA)=P(B)。 则有P(A)P(B并且P(B)P(A)。由题(2知P(A)≌PB)→ASB。 同样可证P(B二P(A)→BA。所以A=B。 ←。设A=B。则有ASB并且B≌A。由题1知AcB→P(A)sPB)。 阿样可BsA→P(B)cPA)。所以P(A)=P(B)。 10.对下列各集族C求∪S,∩S SecS∈C (1)C={}。 (2)C={{a}{},{a3b}}

...展开详情
img
SF999555

关注 私信 TA的资源

上传资源赚积分,得勋章
最新资源