离散数学教材（国防科大版）

【实例简介】
国防科大版的离散数学教材，北航计算机学院离散数学老师推荐的教材
内客提 本书系统地介绍了离散数学各分支的基本内容。全书共分十四章,主要包活;集合论数理卫 辑、图论原始璁归面数、程序正骑性验证代数构及其在计算机科学中的应用。它可作为计算机 软件专业和硬秤专业的“离救数学课程的教材,供一学年教学之用,它也可供队事计算机工作的科 研人员、工程技术人员及其他有关人员参考。 离/数 王兵山王知同食每白编 任编辑式莱5 资下教时:李 装换 国防科技大学出版社出暖发行 潮离省新华书店经销 国防科大学钍漸印副!印装 开本:787X102116即张:LE5字数:451于字 35年6月第1版199年9只第6次印刚甲数:380c-:43000 SsBN781024-350-8 TP·68定价:20.00元 本书刻有印刷装订质量冋题清直接与印刚厂家联系解决 言 随着计算机技术的发展,计算机的应用也日益广泛。除了般的科学计算之外,它还 深入到了组织管理、情报检索和社会的公共服务事业等各个方面。同跖,计算机的理论也 日臻完善,逐渐产生并形成了犯立的计算机科学。因为计算机科学以研究计算机领域中的 些普遍规律为其主要任务,所以需要大量的代数学作为工具由于它所用的数学多具 有“离散性"和“能行性”这两大特点,故称之为“离散数学”离散数学的内容一直随着计 算机科学的发展而不断地扩充与更新到目前为止,它包括的主要内容:集合论、数理逻 辑抽象代数图论可计算性理论自动机理论组合学和离散概率论等等 离散数学对计算机技术和计算机科学的发展,一直起着重大作用。在计算机产生之 前,图灵在研究可计算性时于1936年提出了一个抽象机模型,即著名的图灵机,并证明了 存在能存储程序的通用图灵机,这为1946年间世的第一台电子计算机奠定了理论基础 在计算机发展的初期,利用布尔代数理论研究开关电路从而建立了一门完整的数字逻辑 理论对计算机的逻辑设计起了很大作用、在近期,利用自动机韭论研究形式语言和编译, 利用谓词演算研究程序理论利用代数绪构研究编码理论,利用自动机和遍归函数研究可 计算性问题。此外在计算机科学中普遍采用了离散数学中的基本概念基本思想和方法 例如,集合论的概念和方法,抽象代数的概念和方法在计算机科学的各个领域中,到处都 能碰到。所有这些都使离散数学在计算机科学中的地位和作用越来越重要,成了必不可少 的理沦工具。这就难怪有入把离散数学叫做“计算机数学”了 本书是作者为在国防科技大学让算机系讲授离散数学课程而编写的,这次付印做了 修改和补充。叮以作为理工科院校计算机软件专业和壇件专业的教材,供一学年教学之 用 般说来,阅读本书不需要具备高等数学知识,但希望读者具有一定的逻辑思维能 力,且经过·定的数学训练。由于离散数学是一门数学,因此本书力求叙述严格证明与摧 导的逻辑性强,思路清楚,使学生通过本课程的学习后能得到严格的逻辑推理与抽象思维 能力的训练 全书共分十四章。前三章叙述朴索集合论的基本内容。第四章至第六章是数理逻辑, 与其它离散数学教材不同的是,本书引入了比较严格的自然推理系统,以及在人工智能中 应用广泛的艾尔布朗定理。第七章是图论力求使定义和定理的叙述严格而明确。第八章 详细讨论了原始递归函数的性质,引进了递归函数即能行可计算函数的概念。第儿章讨 论数理逻辑和集合论在计箅机科学中的重要应用——程序正确性验证。第十章至第十四 章是代数结构及其在计算机科学中的应用,除了群和环的基本性质之外,还详细讨论了有 狠域,因为有限域理论是编码理论的基础。 本书习题数量较多.其中大部分是基本的,只要熟悉了教材的基本内容即可做出。但 也有少数习题难度较大,需要一定的技巧才能做出供学习成绩好的学生选{ 武汉大学曾光昌教授,中山大学麦卓文老师,国防科技大学宫德荣付教授审阅了全部 书稿,并提出了修改意见,在此谨致谢意。 由于我们水平不高加之时间仓促,错误疏漏之处一定不少,还望广大读者批评指正 编者 1984年11月 且录 第一章集合 §1￥集合及其表示 1.2集合的运算 唱●。电罩咖电电●唱曲咖血 氵1.3自然数和归纳法…… 中曾■ 14 §1.4笛卡儿乘积,……r…… '"s!20 第二章二元关系 §2.1关系………………………………………………”………………24 §2,2关系矩阵与关系图 ■■■冒■号『■冒■■『■■冒■■■看■■T晶■■ ■冒■晶■■■画 逆关系 3日 §24关系的合成 r…:…--…-…--*"…r…33 82.5关系的闭包 ,……………∵"…"!”3 §2.6相容关系… ss,41 §2.了等价关系…………… 45 2.8序关系………………,…,…,…w…………………………………………50 第三章函数 33.1部分函数 罩聊「■■画■4■ ·日g品日口中品amb日m即日t §3.2函数的合成………… 52 §3.3逆函数… …………65 §3,4特征函数 罩·◆日咖·◆·◆p司喜●咖■■血自■··■□啬■·郾日郾島—即聊■画 ↓聊■鼻■着島卩■郾■■晶■罪■■ 67 §3.5基数…… 69 §36基数算术… …………74 第四章命题理辑 氵.1命题和联结词 …………*…75 §42合式公式…… 78 843等价和蕴含… 甲·■會會P會早合鲁看音血曲鲁P■『■噜血自會 ……………………………82 §4,4范式和判定问题…… k山↓画mb山看bL 第五章词远辑 §5.1变元、谓词和量词 卜■↓■矗↓『■■↓d↓■↓d↓中■d↓↓↓ 92 §5.2合式公式……… 99 §5.3水真式 …………………102 §5.4永真式的判定……………………………………………………………106 第六章自然推理系統 §6.1白然推理系统……… 冒? I09 §6.2形式推理关系的简化让明 中■!P鲁會會自噜自鲁早即鲁早幽■鲁鲁早命_■■ …………115 第七章图论 §7.1图的基本概念… 山■晶画画■ h■■ 19 §7.2子图和图的运算 §7.3路径、回路和连通性 127 R7.4欧拉图和哈密顿图 …………………133 §7.5图的矩阵表示… ↓■忌 晶d↓冒晶 136 §7,6树、有向树和有序树 …140 87.7二部图 ■■郾■ ↓↓↓m最4 ↓鼻山↓ §7.8平面图…… 圈■ 口m…4" 5 §7.9网络流… 日■■■ ……………………]54 第八章原始递归函数 §8.1原始递归亟数的定义…… 159 §82常用函数的原始归性……………………………………162 §8.3康托尔缃码和哥德尔编码 a…2169 §8.4原始递归谓词……… m177 §8.5部分递归函数的概含………………………………………………………382 86阿克曼函数……………………………………………………………185 第九章序正确性验证 9.1流图程序4… 94 §9.2霍尔的程序逻辑……………………………,………,”…200 §9.3终土推断规圳 卩自會會■■■唱P■俨肀■曾自凵■■P■譬啬唱■平自自■■中■■■ …………"L…205 第十章代数结构 810.1代数运算 甲早『中鲁4中即P口中早鲁鲁司即■唱冒身自鲁餐早鲁 209 §10.2代数结构……… ●日·◆.··血4·阜4b中自甲鄂4 §10.3同态与同构… 由4·4甲···●B4自44·自◆自BB4甲自4、·■ 2:2 §1.4同余关系 …!……216 10.5商代数和积代数 . 21B 第十一章半群独异点和群 §11.1半群和独异点… 俨冒卜■■■■■■■■冒昏昏■■督口■4■看冒■晶■晋晶■看冒画 222 §11.2群的基本性质… …225 附录初等数论中的某些结果…………………………………………………………"228 §11.3子群和群的同态……"…*……………………*………"…………"…"……230 §11.4变拯群与循环秤……… 壘d也d西垂■↓看 …232 §11,5不变子群、商群和群同态定理…………… 體甲■■俨『會昌■自【■鲁■■■■·會■『昏d■■■昏■凸■昏■曾备■ 236 第十二章环和域 812.1具有两个二元运算的代数结构 242 §12.2有限域……………………………m……………………………249 附录域上多项式的最高公因式………………………………………254 §12.3有限域的结构……… 2b5 §12.4有限域的表示………… …26l 第十三章格与布尔代效 §13.1格及其性质 ■■■自■ ■罪■■@■■角 2G4 §13.2格是一种代数…………*…""………,……………267 §133特殊格 ψ■↓■■壘讠■4■;■●■↓ψ■↓b■d●山d駟bpb ………"…271 §13,4布尔代数………………………………"………………… 274 §13.5有限布称代数的曜一性…………“………………280 §13,6自由布尔代数……………… 4=a=“·看单b日B··中4面甲 282 第十四章代数结构在计算机设计中的应用 §14.1剩余算术在计算机设计中的应用…………,……… ■卓b 288 §14.2动态存贮器的置换联结…………"……………291 参考书目 甲會D■b·鲁■看甲命唱甲 ……………"…∵…”296 符号表 …………………-…………"……………………279 蒙引………………………………………………-…*……-……………399 第一章集合 集合是现代数学中最重要的基本概念之 众所周知,在任何一种数学理论中,不可能对其中每个概念都严格定义比如说它 的第个概念就无法定义,因为已没有能用于定义这个概念的更原始的概念了我们称这 种不能严格定义的概念为该数学理论的原始概念,而称其余的概念为它的派生概念如在 欧氏几何学中,“点”和“线是原始概念,而“二角形”和“圆”则为派生概念在这里我们把 集合”就作为不能严格定义的原始概念 本章主要介绍集合及其表示,巢合的运算,自然数和归纳法。 §1.1集合及其表示 閃为集合是不能严格定义的原始概念、所以对亡就只能绺予直观描述。所谓集合乃 是由某些可以可相区分的任意对象如数、变量、函数符号、字母、数竽、图、语句、程序或 事件等等汇集在一起所组成的一个整体。所涉及的各个对象统称为元素。组成一个集 合的各个对象,称为这个集合的元素或成员 例1以下是一些集合的例子 1)中国人的集合; 2)中国的山与河的集合 3)1000以内的素数的集合; 4)方程x2+x+1=0的实根的集合 5)自然数〔即非负整数)的集合: )直线y=2x-5上的点的集合。 在组成集合的对象中,也允许有集合,即允许把集合作为其它集合的元素。 例2在以下集合的元素中,有的就是集合: 1)例1中列举的集合的集合↓ 2)由u和自然数的集合一起所组成的集合 对例2的1),集合的每个元素部是集合;对例2的2)集合的一些元素是集合,另 些素不是集合。 通常,我们用大写拉丁字母ABC,…表示集合,用小写拉丁字母a,b,c…表示元亲 用以一字母表示固定集合 Q有理数的集合 N—自然数的集合; 整数的集合; R-实数的集合 一复数的集合 E,—偶自然数的集合; O4—奇自然数的集合; Nn小于m的当然数的集合; —正整数的集合 负整数的集合 R+一…正实数的集合 负实数的集合。 设n为任意…个对象,A为任意一个集合,则在a和A之间有且仅有以下两种情况之 出现 (1)a为A的元素,记为“∈A"或“A3a”,并称为“a属于A”或“A含有a” (2)a不为A的元索记为aA”或“Aa”,有时也记为“a∈A或“Aa”,并称为“a 不属于A或“A不含有a” 当∈Aa2∈A,…G∈A时,常简写作a,a,…a∈A 定义1.1.!设A为任意一个集合,用(4表示A含有的元素的个数 i若(A)=自则称A为空集 i)若a(A)为自然数,则称A为有限集; i)若n(A)为无穷大则称A为无限集 iv)若n(A)≠0,则称A为非空集。 显然,空集是不含有任何元素的有限集,常用符号表示。 在例1所列举的集合中,1)、2和3)都是非空有限集(即为有限集,且不为空集的集 合),4)为空集而5)和6)都是无限集。 在上而列举的誉用的重要集合中,只有N,为有限集其余的都是无限集 定义1.1.2设A,B为任意两个集合 若对每个a∈A皆有∈B,则称A为B的子集或B包含A,也称占为A的母集记 为AC历或圹=A i)若ACB且乐=A则称A和B相等,记为A=B;否则,称A和B不相等,并记为A≠ ⅲ)若AB且A≠B,则称A为B的真于策或b真包含A,记为ACB或BA 由此可知,两个集合相等,仅指它们所含有的元素完全相同所以,我们要想确定一个 集合只需要确定:哪元素属于这个集合哪些元素不属于这个集合。至于这些元素用 什么方法描述或指定,并无关紧要。因此我们可以用种种不同的方法描述一个集合。营 用的方法有以下四种: 1)列举法 依照任意一种次序,不重复地列举出集合的全部元素并用一对花括号括起来。例如 【实例截图】
【核心代码】