离散数学课程教学课件.pdf

离散数学与Je他课程的关系 基础数学的延伸 算法与数据结构 的理论基础 概率统计、算法 设计与分析的理 论基础 其他专业课程的 描述和建模工具算法设计 与分析算法与数 据结构编译技术 网络技术 软件工程 人工智能概率 统计离散 数学高等 代数数学 分析4系统建模关系 关系数据库-刀元关系 图的连通性-等价关系 集合的聚类划分等价关系 流程的拓扑排序-偏序关系 计划评审技术PERT 偏序关系 问题类复杂度的归约偏序关系5系统建模图 通信网络-无向图 In t ern et上的超链接-有向图 社会网络（群体之间影响）有向图 依赖网络（食物链）-有向图 基于Pet ri网的工作流模型-有向图 有源网络的最大流问题-有向图 计算机文件系统-树 决策决策树 多处理机调度图的着色6系统建模代数系统 计算机硬件设计的基础-布尔代数 编码系统-群码 数据仓库OLAP分析-物化视图的格结构多维数据立方体包含刀个维属性，1个度量属性在聚类操作中，需要物化的聚类层子方体构成一个格 结构软件形式化方法用进程代数描述并发系统基本元素是进程进程之间顺序、并发、通信都表示成运算77离散数学课程教学目标 具有良好的知识结构，为学习其他课程打下基础：知识获 取能力 掌握离散数学的语言，能对实际问题给出清晰的描述（建 模）：基本应用能力 掌握离散数学的分析方法，针对实际问题设计解决方案并 加以实施：工程实践能力 培养思维严谨性，提升抽象思考和严格推理能力：研究能 力 了解现代数学思想和学科进展，培养创新意识8能力培养体系创 新 能 力综 合 能 力 实 践 匕 目匕科研训练（科研项目）奖励基金竞赛（ACM竞赛、电子设计竞赛）实验室课题毕业论文实验课程（实验教学）理论课程（课堂教学）力9面向不同培养类型的离散数学定位型养求位数散学基 及他业 时排 类培要定人离数的础 涉算专课学安科学型基础理论和核心技术研究 原始创新学术研究少熟练掌握形式描述、变换、推理和证明方法熟练掌握离散系统的描述 与分析方法了解实际离散系统的建模数据结构与算法,数据库系 统原理，操作系统,编译原 理,软件工程,人工智能,数 字逻辑，计算机网络，建议学时72-1 08工程型基本理论与原理的综合 应用（创新性应用）IT企事业较多熟悉形式描述、变换、推理和证明方法熟练掌握离散系统的描 述与分析方法了解实际离散系统建模数据结构与算法，数据 库系统原理，操作系统,编译原理，软件工程，数 字逻辑，计算机网络，建议学时72-90应用型计算机应用人才应用领域信息化人才多简要了解形式描述、变换、推理和证明方法掌握离散系统描述与分析方 法熟悉常用实际离散系统模型 数据结构与算法,数据库与 信息管理技术,计算机网络 与互联网，建议学时5 1-7210离散数学知识框架（科学型）形式I集合计算初等 系统I基数I理论I数论应可选知 用识单元证明技术应推荐知 用识单元特殊 高级代数 的图 计数结构核心知 识单元11离散数学知识框架（工程型）形式 系统高级 计数初等 数论应 用可选知 识单元证明技术推荐知 识单元特殊代数的图结构应 用核心知 识单元12离散数学知识框架（应用型）基本I代数系初等 计数统简介I数论应 用可选知 识单元应 推荐知用 识单元特殊 证明 的图 技术核心知 识单元13离散数学中的学科方法什么是计算机科学中的数学方法 以数学为工具进行计算机科学与技术研究的方法 用数学语言表达事物的状态、关系和过程，经推导形 成解释和判断 特点是：高度抽象、高度精确、具有普遍意义主要的数学方法描述方法：模型分析方法：变换、数量化等证明方法：演绎推理、公理化方法、构造性方法等14能力培养目标计算机科学技术人才需要的能力结构 获取知识能力：自学能力、信息获取、表达能力 应用知识能力：对事物的整体的系统的认知能力、理 论分析能力、实践能力 创新能力：创造性思维能力、创新实验能力、科技开 发能力、科学研究能力、对新知识新技术的敏感性离散数学的能力培养目标 获取知识能力 系统的认知能力、一定的理论分析能力 初步的创造性思维和科学研究的训练15一个应用型方向的教学计划应用实例特殊的图基本计数基本逻辑应用概念 工具 方法基础知识单元：5个学时：5416特点定位于应用型人才的培养教学内容及其安排 以离散数学的基本概念、描述方法为主 引入较多的离散数学在计算机科学技术中的应 用实例 介绍一些基本的证明技术 教学方式以课堂讲授为主，辅以习题及网上教 学 习题及考核要求以概念题、计算题、应用题为 主，辅以少量简单的证明题17示例1试题证明或推翻下列命题：“设平面上有100个点，其中任意两点间的距离至少是L则最多有300对点距离恰好是参考答案命题成立建模：无向图&匕及，俄100个点的集合，两个点 相邻当且仅当距离恰好为1.性质证明：每个顶点度数d(06,根据握手定理2m=d(v)6 x 100=600 7 7人V G K/m 30018第1章数学语言与证明方法 1.1常用的数学符号 1.2集合及其运算 1.3证明方法概述191.1 常用的数学符号 1.1.1集合符号 1.1.2运算符号 1.1.3逻辑符号201.1.1集合符号集合是数学中最基本的概念，没有严格的定义理解成某些个体组成的整体，常用4 B,所表示元素：集合中的个体 不力（xM于/）：/（不属于力）包含（子集）不包含 相等 不相等 真包含（真子集:不是/的元素:X不是/的元素/1方即A中的每个元素都是B的元素A B即合B不包含集合A/=月即/旦夕且方）/u6即/=旭/w B211.1.1集合符号续x Ei A x 是：A 的 yG 素x A x不是A的兀素A B-A是B的子集，或 A包含于 B(B 包含 A)/H B-A不是B的子集，或ZuB-A是B的真子集A=B-A与B有相同的元素A U B-A并 BnU Aj 一 一41，/24一，力之并 i=lA A B-A交 BnP)A i 一 一 41，/2，一，力之交Z=1A-B-B对A的相对补Z6-A与B的对称差P(Z)-A的哥集。-空集B不包含 AN-自然数集(含0)N+-非0自然数集Z-整数集Q-有理数集Q*-非零有理数集，即 Q-0R-实数集R 非零实数集，即 R 0C-复数集(1)Nc Zc Qc Rc C(2)N u Z u Q u Ru C 221.1.2运算符号nEq.-,之和,即 a.+ai 1 7 2 7 7 n 1 2 nz=100a j 之和，即 Q +Q 2+,一i=1nna.-之积,即 a a ai 1?2 7 y n 1 2 ni=l00n a.-一 之积,即 1 2 一i=la|b-整除，如 3|9、a|b-。不能整除 仇如3建a=b(mod n)-与被除余数相同，如 4=7(mod 3)max(*)或max a,b-为中的大者min(a，)或 min a,b-为中的小者231.1.2运算符号(续)g c d(a,b)-与力的最大公约数，如 g c d(6,8)=2Icm(a,b)-a 与 b 的最小公倍数，如 1cm(10,14)=70|x|-x 的绝对值，如|-2.5|=2.5XI-大于等于 X的最小整数，如-2.2 1=2,0.7 =1,上限函数_xj-小于等于 x的最大整数，如-2.2 _|=-3,0.7 =0,下限函数|A|-有穷集合 A中的元素个数241.1.3逻辑符号 命题与真值 联结词(-A,V,V,f n)命题公式(重言式，矛盾式,可满足式)重要等值式 重要推理规则 个体,个体域与谓词全称量词与存在量词25Ll.3逻辑符号_命题:具有确定真值的陈述句，如：2+2=4;3是偶数;命题的符号化：用p,q,t等表示命题，如p:2+2=4;q:3是偶数；真与假的符号化:用1表示真,用0表示假 真命题:真值为真的命题 假命题:真值为假的命题例如，p:2+2=4,q 3是偶数它们都是命题，是真命题，q是假命题.26联结词（续）否定联结词否定式p:非P（，的否定）P为真当且仅当，为假 合取联结词人合取式卬并且q（，与g）,g为真当且仅当，与g同时为真 析取联结词V析取式pv g：，或gpv g为假当且仅当P与g同时为假27联结词（续）排斥或联结词V排斥或p V q：p并且非q,或者q并且非Pp V 9为真当且仅当P与9中一个为真，另一个为假 蕴涵联结词-蕴涵式pfq:如果P,则qpfq为假当且仅当，为真q为假 等价联结词一等价式pq：p当且仅当qp-q为真当且仅当，与q同时为真或同时为假28实例:设/）：2是偶数,：1+1=3,则2的真值为1N的真值为0PA夕的真值为0 FA夕的真值为0 pv夕的真值为1 pv 的真值为1P必夕的真值为1 p W-1夕的真值为0夕的真值为0夕的真值为1PA1夕的真值为1 FA10的真值为0 pv夕的真值为0“V-1夕的真值为1T V夕的真值为0“0的真值为129实例（续）pfq的真值为0pf-ig的真值为-Pfq的真值为-Ip3-iq的真值为1又设r：今天是星期一，s:明天是星期二明天是星期三r-s的真值为1七的真值为不定30命题公式 基本复合命题：设p,q为命题，称 pfq,po q为基本复合命题。命题变项:取值为。或1的变元，也用等表示.命题公式:用联结词和圆括号把命题和命题变项按照一定 规则连接起来的符号串，常用等表示.例如，么=(-1PAq)f(rvp)公式的赋值:对公式中每一个命题变项给定一个值(0或1).公式的成真赋值:使公式为真的赋值.公式的成假赋值:使公式为假的赋值.例如，p=l,q=l,r=工是港的成真赋值，p=0lq=1,r=0是么的成假赋值.31重言式,矛盾式与可满足式 重言式（永真式）:无成假赋值的命题公式 矛盾式（永假式）:无成真赋值的命题公式 可满足式：不是矛盾式的命题公式例如，A=（-I0AQ）（八3是可满足式，但不是重言式,B=（0a4）v（-1PA4）v（A-q）v（-1p/-q）是重言式,C=-1PAsV。（人一14）是矛盾式.AnR蕴涵式/一展重言式的简记.Ao B.等价式力63是重言式的简记,称/与8等值，/o任爱等值式.32基本等值式 双重否定律 第等律 交换律 结合律 分配律 德摩根律-1-Jo/A/AAAvBo Bv A,A/BB B AAr B iA-B(AfB)a(1i而 o 1434重要推理规则（推理定律）附加律 化简律 假言推理 拒取式 析取三段论 假言三段论 等价三段论 构造性二难A n(小/百 n A(AtB)aA n B(4aB=A(小/8 a18 n A(A.B)八 gC)n 4。(AB)八n 20(/.而(j aA(A/0 n(A/0破坏性二难（力.而a（3。a（风n（小/035谓词与量洞 个体域:个体变项的取值范围.个体词：个体域中的一个元素.全称量词V:全称量词的符号化形式 Vx:对个体域中的每一个x 存在量词三：存在量词的符号化形式 3 x:在个体域中存在x 谓词：表示个体词性质或相互之间关系的词 P(X)：X具有性质P VxP(x):个体域中每个x具有性质P 3 xP(x):个体域中存在x具有性质P361.2集合及其运算 1-2.1集合及其表示法 1.2.2集合之间的包含（子集）与相等 1-2.3集合的嘉集 1-2.4集合运算，）1-2.5基本集合恒等式及其应用371.2.1集合及其表示法康托尔，G.Cant o r）：是德国数学家，集合论的创始者。1845年3月3日生于圣彼得堡，1918年1月6日病逝于哈雷。他处理了数学上最棘手的对象-无穷集合。康托尔悖论：据康托尔集合理论，任何性质都可以决定一 个集合，这样所有的集合又可以组成一个集合，即“所有集 合的集合”（大全集）显然,此集合应该是最大的集合了,因此其基数也应是最大的，然而其子集的集合的基数按“康托尔定理”又必然是更大的，那么，“所有集合的集 合”就不成其为“所有集合的集合”，这就是“康托尔悖 论”。对这一悖论，康托尔并没有感到害怕，因为通过反证 法恰恰证明没有“所有集合的集合”或者说“最大的集合 当然也没有“最大的基数”。38罗素悖论：伯特兰罗素是二十世纪英国哲学家、数学家、逻辑学家、历史学家。“罗素悖论”的通俗形式是“理发师悖论”：一 个理发师声称他只给不为自己理发的人理发。那 么问题来了，这个理发师是否给自己理发？如果 他不给自己理发，那么按照他的声称，他应该给 自己理发。如果他给自己理发，那么他便具有“不为自己理发”性质的，也就是他不为自己理发O391.2.1集合及其表示法 集合是数学中最基本的概念，没有严格的定义理解成某些个体组成的整体，常用4 B,保表示 元素：集合中的个体 丫/（%属于力）：X是/的元素 丫任/5不属于/）：x不是的元素 无穷集:元素个数无限的集合 有穷集（有限集）：元素个数有限的集合.Ml：/中元素个数 阮集:4个元素的集合，k 040集合的表示法 列举法：列出集合中的全体元素，元素之间用逗号分开，然后 用 括号括起来如 A=a,b,c,d,N=0,1,2,D=北京,地球，宇宙 描述法：用谓词P(x)表示x具有性质P,用旧产但表示x具有性质 P的全体元素组成的集合。如N=*|不是自然数)说明：(1)集合中的元素各不相同.如，1,2,3 =1,1,2,3)(2)集合中的元素没有次序.如，口，2,3=3,1,2=1,3,1,2,2(3)有时两种方法都适用，可根据需要选用.41常用集合 自然数集2仪|x为自然数=0,1,2,整数集Z=x|x为整数=.,-2,-1,0,1,2,正整数集Z+=x|x E ZAx0=1,2,3,.)有理数集Q=x|x为有理数 非零有理数集Q*=x|xQ/xwO 实数集R=x|x为实数 非零实数集 R*=x|xR/xwO 复数集C=x|x为复数 区间当=x|x 6 R A a x b 区间,。)=x|x 6 R A a x Vx(xgA f XgB)A B Bx(xeA a XB)A-B=x|xgRa|x|1,C=x|xgRax2=1,D=-lzlz性质(1)4(2)/cBaBcC/cC43空集与全集定义1.4空集0:不含任何元素的集合例如，x|t20atgR=0定理L 1 空集是任何集合的子集证 用归谬法.假设不然，则存在集合4 使得0 0 4即存在X,且力,矛盾.推论空集是惟一的.证假设存在01和02，则0叵。2且。叵02，因此。1=。2定义L 5全集月：如果限定所讨论的集合都是月的子集.441.2.3集合的赛集赛集)：力的所有子集组成的集合，即(/)=X I XA 例如，设/=当4。/的0元子集：0力的 1 元子集：a,，c力的2元子集：%5，多。,“。力的3元子集：P3)=0,%。,a,6.a,c,b,c,a,b,c 定理1.2如果|力|=小 贝P(Z)|=2证 I P(Z)1=C+c”1 z i n n n=(1+1)=2451.2.4集合的运算 并 AjB=x|xeA v xgB 交 AcB=x|xeA a xgB 相对补 A-B=x|xeA a xB y 对称差 4 8=(4B)u(B4)=(4uB)(4c 8)绝对补=E-A=X|xA 例如 设=0工，9,4=0J,2,3,8=1,3,5,7,9,贝J AjB=0,123,5,7,9,4c B=1,3,A-B=0,2,48=0,2,5,7,9,-A=%5,6,7,8,9,B=0,2,4,6,8 说明：1.只使用圆括号2.运算顺序：优先级别为括号，(2)和赛集，(3)其他.同级别的按从左到右运算46实例例1设层 X I是北京某大学学生,4片q碇月的子集，A=x *是北京人,B=x 不是走读生,华 x I X是数学系学生，大 x I是喜欢听音乐的学生.试描述下列各集合中学生的特征：(/uZ)c C=x|”是北京人或喜欢听音乐，但不是数学系学生*|不是夕卜地走读生(A-B)n D=*I x是北京住校生，并且喜欢听音乐Dc B=x|x是不喜欢听音乐的住校生47文氏图表示ABA48例：用公式表示下图阴影部分的集合上左=(B n o-A上右=(AnBAC)U(A 右=40(BcUC)49例：某班有25个学生，其中14人会打篮球，12人会打排球，6 个会打篮球和排球，5人会打篮球和网球，还有两个会打这三 种球，已知7个会打网球的人中有4人会打排球，求不会打球的 人数.R=E-AUBUC|A|=14|B|=12|C|=7|AABnC|=2|AAB|=6|AAC|=5|BnC|=4会打网球|R|=25-(|A|+|B|+|C|-|AAB|-|AAC|-|BnC|+|AnBnC|)=550集合运算（续）并和交运算可以推广到有穷个集合上nU a.=x I X Gy41vxey42v.vxe 4wi=l np|z=A1r 42.r 4n=x|xGy41AX Gy42A.Axey4wi=l并和交运算还可以推广到可数无穷个集合上00J a.=x 3i(Z=1,2V.)xAti=l00pl a.=4c 242c=x|Vi(i=12)xeAt51实例例2 设4.=0,1/),以=(0,i),1=1,2,，则U 4=曲 1)1=1nn01加)i 二 lnU 氏=(0，)i 二 ln2”(0,1)i=looi 二 loorvi 二 loou万i 二 looi 二 l”0,1)”0i=(o,+00)”(0,1)52实例:例3设=x|x是北京某大学一年级学生,A,B,C,D是E的子 集：A=x|x是北京人 B=x|x是走读生C=x|x是数学系学生 D=x|x是喜欢听音乐试描述下列各集合中学生的特征：(1)(/uD)c C=x|x是北京人或喜欢听音乐，但不是数学系学生531.2.5基本集合恒等式及其应用1.哥等律 AjA=A,ArA=A2.交换律 4cB=BM3.结合律 CAdB)uC=4u(BdC)(4cB)cC=4c(BcC)4.分配律 4u(BcC)=(4uB)cCAuC)4c(BuC)=CAcB)d(4cC)5.德摩根律绝寸形式(BdC)=8cG(BcC)=BdC相对形式 4-(BuC)=(4-B)c(4-C)4-(8cC)=(4-B)d(4-C)54基本集合恒等式（续）6.吸收律7.零律8.同一律9,排中律10.矛盾律11.余补律12.双重否定律13.补交转换律4u(4cB)=Af 4c(4uB)=AAuE=E,4c0=0Au0=Af A(E=AAj-A=E4c 4=0O=E,=0=AA-B=4c 855基本集合恒等式(续)14.关于对称差的恒等式(1)交换律 4B=B4(2)结合律(4B)C=4(BC)(3)c对的分配律4c(B C)=(4cB)(4cC)(4)40=4,46 A(5)44=0,4 A=E注意:u对没有分配律,反例如下：/=a,c,B=b,c,d,C=g4,8,cd仇e=,仇c,e(NdC)=a,b,c,研a,b,c,d,e=e,两者不等56证明集合包含或相等方法一：根据定义，通过逻辑等值演算证明方法二：利用已知集合等式或包含式，通过集合演算证明 例3证明：(1)AjB=KjA(交换律)证 Vx xwAuB=xeAvxeB=xrB/xrA（并的定义）（逻辑演算的交换律）（并的定义）57例3（续）（2）/D（质。=（/u面（分配律）证/x xeAj（Br yC）o xeAv（xB/xe C）（并，交的定义）o（tg AvxeS）a（tg Avxe C）（逻辑演算的分配律）。年（小j而c（/u。（并，交的定义）(3)AjE=E(零律)证 Vx xeAjE=xe AvxeE=xe Ayl o l0 x e E（并的定义）（全集名的定义）（逻辑演算的零律）（全集名的定义）58例3（续）(4)AcE=A(同一律)证 X/x jtg AcyEo tg A/xEO T G a1xe A（交的定义）（全集演勺定义）（逻辑演算的同一律）59口实例例4证明（吸收律）证利用例3证明的4条等式证明A4)o XAn XoBo XwP(B)（化简律）(已知4qB)64口实例例8证明4B=4 uB-4 cB.证 4 B=(4c8)d(4cB)=(4u2/1)c(4dB)c(2Bu24)c(2BuB)=(4d8)c(Bd4)=(4 u8)c(4 cB)=AB65补：集合的计算机表示用全集元素的一个任意排序存放元素以表示集合 的方法。假设全集E是有限的，首先为E的元素规定一个顺 序，ija1,a2，,am于是可以用长度为n的位串表示 E的子集，如果可属于A,则位串中第位是1,如果 aj不属于A,则位串中第位是0。66实例令全集E=1,2,3,4,5,6,7,8,9,10),即小=1。表示E 中所有奇数组成的子集、所有偶数组成的子集和不 超过5的整数组成的子集的位串是什么？解：E中所有奇数组成的子集为1,3,5,7,9,所以位 串为 1010101010.超过5的整数组成的子集为1,2,3,4,5,所以位串为 1111100000o67实例令全集 E=1,2,3,4,5,6,7,8,9,10),子集1,2,3,4,5 和13 5,7,9的位串分别是1111100000和 1010101010,用位串找出它们的并集和交集。解：它们的并集为：1111100000 V1010101010=1111101010交集为：1111100000 A 1010101010=101010000068计算机解题:#include stdio.h11#include conio.h11unsigned long b_s(int E,int mjnt A,int n)一unsigned long bs=0ul;int ij;for(i=0;i=O;j-)if(j!=m-1)k*=2ul;if(Ai=EU)bs=bs|k;printf(,bs=%otk=%otni,bsJk);break;)return bs;)main()(int E=1,2,3,4,5,6,7,8,930,A尸1,2,3,4,5,B=135,7,9;printf(fiA 的位串=%onf,b_s(E0,A,5);printf-B 的位串=%otn,6_s(E,10,B,5);printf(A和 B 的交集的位串二%orT,b_s(E/0,A,5)&b_s(E/0,B,5);printf(A和 B 的并集的位串二%on,b_s(E,10A5)|b_s(E40,B,5);getch();)69#include stdio.h#include conio.h#define N 10void getBitString(int Ezint Azint nzchar bs)int ij;for(i=0;iN;i+)bsi=,0,;for(j=O;jn;j+)if(Ei=Aj)bsi=,li;break;bsN=,0,;void operationl(char bslzchar bs2Aint nfchar bs)int i;for(i=0;iN;i+)if(bsli=i0i&abs2i=i0l)bsi=l01;else bsi=,l,;bsN=i0i;7Uvoid output(int Ezint nzchar bs)int i;printf(结果:for(i=0;iN;i+)if(bsi=,l,)printf(“)；main()intE=lz23,4/5z6z7z8z9/10zA=l/23,4z5zB=lz3,5z7/9;char bslN+lz bs2N+lzbsN+l;getBitString(EzAA5Absl);printf(A 的位串二%)srT,bs1);getBitString(EzBA5zbs2);printf(”B 的位串二%sn”,bs2);operation l(bslzbs2ANzbs);口皿七(幺和3的并的位,=%)5|1由5)；output(EzNzbs);getch();711.3证明方法概述 1.3.1逻辑推理的形式结构 1.3.2公理、定理和证明 1.3.3证明方法 1.3.4数学归纳法72L3.1逻辑推理的形式结构逻辑推理是从前提推出结论的思维过程逻辑推理的形式结构 4乂2必k-B(*)当(*)为重言式时，记作4A(*)并称推理有效或推理正确，又称B是A2，4k的有效(或 逻辑)结论；否则称推理不正确.4BAB(1)001(2)011(3)100(4)111,(2),(4)推理正确(3)推理不正确中制 的逻辑结论，但不 是正确结论;(2)和(4)中5既 是逻辑结论，又是正确结论.73例1.12判断下面两个推理是否正确(1)若今天是1号，则明天是3号；今天是1号，所以明天是3号。(2)若今天是1号，则明天是2号；明天是2号，所以今天是1号令：P:今天是1号q：明天是2号r:明天是3号(1)推理的形式结构为：(p-r)Ap-r(p-r)Apr对于P泮的4组赋值00,01,10,11,上式均为真，故为重言式(2)推理的形式结构为：(p-q)Aq-p(pq)Aq 7 p对于p,q的4组赋值00,01,10,11,上式取值为1,0,1,1,故为可满足式74推理定律(p f q)p n q(p f-np(夕 p(夕 9)0 Pp=p 7 q（假言推理定律）（拒取式推理定律）（析取三段论推理定律）（化简律推理定律）（附加律推理定律）751.3.2公理、定理和证明 公理：公认为真的命题。如：两点决定一条通过它们的直线。定理：可以被证明为真的命题，定理是所属学科 的一些重要的结论或一些重要的猜想，当它得到 证明以后，也就成为定理了。引理：也是被证明为真的命题，但引理往往是为 证明某条定理而引用的辅助性的真命题，其作用 有一定的局限性。推论：从某条定理直接推导出来的真命题。76实例、2”定理 a+aq+aq+=-，其中|夕|11-0为了证明上述定理，先 证下面引理：2 a(l-qn+1)弓理：a+aq+aq+aq=-，其中 夕 w 11-0由上述定理可以得出下 面推论：2 11+q+q+=-，其中|夕|4/rB为假为假或B为真n 4-8为真例3 若4-B=4,则4cB=0证用归谬法，假设4cBw0,则存在x,使得XeAt B=XgAaXeB=Xg1-BaXgB o Xg4aX BaXgB n x BaXgB,(4-B=4)矛盾82归谬法(续)例4证明正是无理数证假设41是有理数,存在正整数外孙使得4i=mln,不妨设为既约分数.于是,m2=2n2旭2是偶数，从而m是偶数.设m=2A,得(2A)2=22,/=2。2,这又得到也 是偶数,与旭/”为既约分数矛盾.间接证明法是归谬法的特殊形式:寸n834、穷举法(分情况证明法)推理4f号 其中4=A1vA2v.vAk.做法 证明B,人-号，B均为真理由 A1vA2Ak-Bo-i(/Itv/42Vb k)=(-|42八,八o(-i42vB)i/Iq/B)(4一B)/(42-B)84实例例5 证明:max(a,max(dzc)=max(max(azd)zc)证情况u=max(b,c)max(d,u)u=max(d,b)max(c)a b cccbca c bbbbbb a cccacb c acaaac a bbbbbc b C=ab但BwC,故命题为假.881.3.4数学归纳法命题形式：Vx(XGNAXn0)A P(x)1、命题的提出一一归纳与猜想例如，观察l=lx(l+l)/21+2=3=2x(2+1)/21+2+3=6=3x(3+1)/21+2+3+4=10=4x(4+1)/2猜想 对所有“21,1+2+.+n=n(n+l)/2892、数学归纳法的推理规则良序性：良序性是数学归纳法的基础。所谓良序性 是指设A=N,则A中元素关于小于等于关系均有最 小元。如N的最小元为0。推理形式结构应为：(P(n0)AVn(nn0)(P(n)-P(n+1)-Vn(nn0)P(n)若能证明 P(o)与 V(io)(P(a)-P(n+2)均为真，则必有Vn(nMo)P()为真903、数学归纳法的原理(工)归纳基础证P(o)为真(2)归纳步骤 vn ENAnnQr 有P(n)fP(+1)为真.则称GN AnnQr P(x)为真”说明：(1)实际证明中，从工开始的情况较多，但有时可能从。或 大于1的某自然数 o开始证明。(2)实际操作中，常称P()fP(fi+l)中的前件为归纳假 设。(3)以上归纳法原理常称为第一数学归纳原理。后面还要 介绍第二数学归纳法原理。914、数学归纳法的步骤(1)归纳基础证P(l)(或P(n。)为真(2)归纳步骤(或nW。),假设P(n)为真，证 P(+l)为真.例8 证明：对所有1+2+.+n=n(n+l)/2证 归纳基础,当=工时,工=工义(1+1)/2,结论成立.归纳步骤,假设对结论成立，则有1+2+.+n+(n+l)=n(n+l)/2+(n+l)(归纳假设)=(n+l)(n+2)/2得证当+工时结论也成立.92数学归纳法的步骤（续）注意：归纳基础与归纳步骤两者缺一不可反例 1 命题 Vnl,21+22+2n=2n+1证假设结论成立，则21+22+2n+2n+1=2n+1+2n+1对+1结论成立，故命题成立.事实上：当n=1时，左边二21,右边二2293数学归纳法的步骤（续）反例2观察2T-1是否被n整除n2，t-1整除n2t-1整除33Y10511N47N111023Y515Y122047N631N134095Y763Y148191N8127N1516383N9255N1632767N94反例2（续）n2，t-1整除n2，t-1整除1765535Y211048575N18131071N222097151N19262143Y234194303Y20524287N248388607N由上表可能会提出下述命题命题设相3,n是素数的充分必要条件是21：1被整除.但此命题不真.561=3xllxl7B 而256。工能被561整除.95例9任何大于等于2的整数均可表成素数的乘积 证归纳基础：对于2,结论显然成立.归纳步骤：假设对所有的2V左刀）结论成立，要 证结论对加1也成立.若刃+1是素数，则结论成立；否则 n+=ab,bn0)(P(n0)A P(n0+l)A.AP(n)P(+1)-Vn(nn0)P(n)第二数学归纳法的原理：(1)归纳基础证为真(2)归纳步骤 Vn ENAnnQr 有PS。)A P(n0+l)A.A P(n)-P(n+t)为真.贝ij称AnnQr P(x)为真 第二数学归纳法的步骤：(1)归纳基础证为真(2)归纳步骤 Vn(n)(或nW。),假设P(o)，P(n0+l)，.P()为真，证P(+1)为真.97注释归纳基础 证尸（力。），/（4+1）,，尸（刀1）为真,刀（）刀1.例10可用4分和5分邮票组成4分邮资，/?12.证归纳基础.12=3 x4,13=2x4+5,14=2x5+4,15=3 x5,得证对r12,13,14,15时结论成立.归纳步骤.设应15,假设对12,13,，刀结论成立，由12。-3 和归纳假设，”-3分邮资可用4分和5分邮票组 成，再加一张4分邮票即可得到加1分邮资，得证结论对+1 也成立.98作业1 P3 01.41.71.8 1-11(3)1.121.1399作业2 P3 1 1.15 1.19(4)1.29 1.3 0 1.3 1 1.3 4 1.3 9100