第一章逻辑与证明

离散数学

2证明介绍一些证明的一般方法用逻辑来分析正确和不正确的论证1.5推理规则从一系列命题推出一个结论的过程称为演绎推理考虑下面一系列命题。这个错误或者出现在模块17或者出现在模块81中。这个错误是一个数值计算错误。模块81没有数值计算错误。

假设这些句子为真，得出结论错误出现在模块17231.5.2命题逻辑的有效论证从一系列前提得出结论的方法称为演绎推理。前提：已知的命题系列结论：由假设得出的结论结论从前提导出结论为真任何论证过程都有形式：如果p1并且p2并且…并且pn,则q。论证有效在于形式不在于内容

4定义一个论证过程是一系列的命题，p1,p2,…,pn/∴qp1,p2,…,pn称为前提，命题q是结论如p1,p2,…,pn全为真，则q也必为真，那么论证有效；否则论证过程是无效的5例确定论证pq,p/∴q是否有效pqpqpqTT

TTTTFFTFFTTFTFFTFF注意：只要前提pq和p为真，结论q就为真。所以论证过程是有效的。6例：

用符号表示论证过程确定此论证过程是否有效如果论证过程是有效的，那么要pq和q同时为真，则p必为真。假设pq和q都为真，这在p为假q为真的时候是可能的；所以论证过程是无效的。

7例确定论证pq,q/∴p是否有效pqpqpqTT

TTTTFFTFFTTFTFFTFF注意：当前提pq和q为真，结论p可能为假。所以论证过程是无效的。81.5.3命题的推理规则假言推理/分离定律合取拒取附加化简假设３段论析取３段论下列论证里使用了那个推理规则若今天下雨，则我们今天将不野餐。若我们今天不野餐，则我们明天将野餐。因此，若今天下雨，则我们明天将野餐。解：设p：“今天下雨”，q:“我们今天将不野餐”r:“我们明天将野餐” p→q q→r

∴p→r假言三段论91.5.4用推理规则建立论证证明：前提：“今天下午没有出太阳并且今天比昨天冷q”“只有今天下午出太阳p，我们才去游泳r”“若我们不去游泳，则我们将去乘独木舟游览s”“若我们乘独木舟游览，则我们将在黄昏回家t”结论：“我们将在黄昏回家”解：pq前提

p

r→p r→s s→t10rst1.5.5消解11121.5.7量词化句子推理规则全称例化全称一般化存在例化存在一般化例1.5.25给出如下假设：每个人都喜欢Microsoft或者Apple。Lynn不喜欢Microsoft，说明由假设可得出结论，Lynn喜欢Apple。设P(x)表示命题函数“x喜欢Microsoft”，Q(x)表示命题函数“x喜欢Apple”。第一个前提是x(P(x)∨Q(x))。通过全称例化，得到P(Lynn)∨Q(Lynn)。第二个前提是┐P(Lynn)。析取三段论推理规则得出Q(Lynn)，代表命题“Lynn喜欢Apple”。这样，得出了遵从假设的结论。1314本节复习1.什么是数学系统？2.什么是公理？3.什么是定义？4.什么是未定义项5.什么是定理？6.什么是证明？7.什么是引理？8.什么是直接证明？9.“偶数”的形式化定义是什么？10.“奇数”的形式化定义是什么？11.什么是反证法？12.什么是间接证明？13.什么是逆否证明？14.什么是分情况证明？15.什么是存在性证明？16.什么是演绎推理？17.什么是论证过程中的假设？18.什么是论证过程中的前提？19.什么是论证过程中的结论？20.什么是有效的论证？21.什么是无效的论证？22.说明假言推理规则。练习35用符号表示下面的论证过程，并说明论证过程是否有效。设p:我努力学习。q:我的成绩是A。r:我发财了。如果我努力学习，则我的成绩是A或者我发财了。我的成绩不是A并且没有发财。————————————————我不努力学习。15p→(q∨r)¬q¬r_________¬ppqrq∨rp→(q∨r)¬q¬r¬pTTTTTFTFTFTTTFFFTFFFTFFF16p呢→鹊(q歉∨r京)¬q¬r__捕__竿__刊__雄_¬p注意屑到：岁当p迎→卖(q麦∨r弹)，¬q，¬r三个杀命题杂都为T的时效候，¬p也为T，因姓此本已论证帐有效慎。171.汤6证明张导论数学拒系统公理定义未定济义项定理愿、引袍理、敬推论董、证皇明论证嘉一个创定理裹为真陈的过有程称患为证明18欧几铅里德捞几何公理例：城给定报两个环不同退的点务，存糕在惟泊一的民一条例直线泪通过净这两赛个点厦。定义例：工如果x是正校数或解零，堆则实峰数x的绝保对值|x|定义府为x，其联他情翁况定竿义成-x。19欧几违里德阅几何日中的容定理克例如果士一个芝三角蛋形的灭两条军边相派等，勺则这台两条冲边相主对的赤角相秒等。如果持四边页形的撇对角带线互盐相平裕分，过则四坟边形轧为平心行四餐边形欧几盈里德爆几何调中的训推论扒例如果执一个机三角缓形是狭等边妨的，帝则它遣是等予角的塘。201.野6.骨5直接耻证明惰法构造版一个亿条件斜语句pq的直帜接证戒明假设p为真应用居推理粥规则内构造推出q也一亏定为素真定义纷：整大数n为偶群数，阳如果亦存在乐一个典整数k使得n=究2k蛇;整数n为奇乏数，半如果化存在薪一个踩整数k使得n=殃2k超+1直接纺证明摧方法者举例例：滔如果m和n都是条完全扮平方勿数，法那么mn也是傍一个蚕完全膨平方拉数。（若顶有一仔个整限数b使得a=饿b2,则整清数a是一浊个完健全平糊方数哪）证明跑：根替据完耍全平炕方数逢的定复义，氧可知存在s,汤t，使气得m=搜s2,课n舰=t2mn真=s2t2=(储st壶)2所以mn是一虾个完仆全平抚方数2122例假设d、d1、d2和x是任挠意实病数if饥d篮=m尿in指(d酬1,反d2撑)茧an到d闹x牌≤dth宰en窑x搁≤d飘1睁an镇d柔x哲≤d轿2证明饼：根据mi盏n的定筹义可旨以推描出d≤d1并且d≤d2。依x≤d并且d≤d1，可趣以根戴据前租面的赛定理辣（例1.贱5.并5的第字二个纸定理骄）推赏出x≤d1。由测于x≤d并且d≤d2，可处以根阴据前情面的熟同一堆个定歉理推拣出x≤d2。因脑此，x≤d1并且x≤d2。231.赠6.摇6反证法反证谊法有开时称筛为间伴接证律明，逝它使惜用矛斗盾来瓦证明淹命题强。通常药用被紫否定焰了的合结论申作为侮前提姓，推出锹矛盾终，从未而证区明原舍命题餐为真24反证死法的尘正确贼性通过结命题p→q和(p^¬q)扔→胖(r^¬r)的等奴价性秘来说评明反案证法帜的正搞确性顺。例给出塞定理穗“若3n妄+2是奇想数，沾则n是奇恼数”属的证胳明若用馆直接瓦法证扔明，限设3n肢+2是奇胖数，竖则存打在k使得3n醉+2滚=2悉k+胃1—陷—能否环从中承得出n是奇肿数的叹结论村？反正厦法：第一步：屠假设疏条件孔语句瓶结论披是假牙，即床“3n米+2是奇抱数，n不是亦奇数随”，闯那么n是偶狸数。挤即：n=帅2k捐+1烛,第二步：睛根据郊上面终的假辈设，溜则3n吼+2财=3改(2酬k)喘+2主=6桂k+蜡2=梯2(心3k益+1帖),也就叛是得盗出3n剑+2是偶案数，川这与稼原命槽题的部假设喊“3n童+2危”是奇楚数”触矛盾所以脚原来兄的条楼件语钓句为碌真，痒定理注得证梁。2526例用反探证法录证明娱下面雅的陈垃述：对于论所有湖的实梨数x和y，如x+融y≥室2，则x嫁≥1或y炎≥1证:设结畅论为议假,x般<1兵,y辰<1街,则x+洽y<遣1+葛1=客2我们摇得出勉矛盾pan先dno层tp,其中p:怠x陵+y施≥2例：汉用反手证法封证明最句子送：对于考所有检的整机数m，若m2为奇猪数，鹿则m为奇埋数。证明祸：首耕先将m看作隆任意楼的整茎数。纠原命园的逆艺否命帽题为秤：“若m为不椒是奇吐数，座则m2不是顶奇数折。”等价束于：若m为偶箩数，随则m2为偶抄数。因此陵假定m为偶吓数，彼则m＝2k，其棍中k为某致个整组数。孙于是m2＝（2k）2＝2·（2k2）。查由于m2可以翠写成2×某个葛整数贴的形尚式（财整数赠为2k2），员所以m2为偶兔数。叹证毕钻。27空证醒明如果槽能证骂明p为假藏，就岂得到p刊→近q为真精，这桐种证贷明方椅法叫边空证泰明例，微证明p(德0)为真芽，其最中p(益n)表示扭“若n>态1,则n2>n件”,论域鸟是所彼有整木数解：唱命题p(辽0)是条券件语竹句“志若0>弯1,则02>0”。因为杰前提0>炭1所假公，所旺以p(爬0)自动午为真注：哑在这席里，胖条件绑语句筒的结谨论为娘假，煮与条离件语闯句的唇真值遇无关铲，因献为前标提为热假的狠条件鲜保证如了每条件盗语句粘为真28平凡五证明在条素件语帮句p尊→艺q中，真如果狂知道尾结论q为真呼，那待么就躺能得乐出条问件语举句为班真。店这种变证明血方法亏为平窜凡证赌明例,设p(粉n)表示扑“若a、b是满辉足a≥b的正驱整数队，则an≥bn”,其中酿论域当是所棒有整严数。诸证明纸命题p(摧0)为真犬。解：肠命题p(起0)是“亡若a、b是满搭足a挎≥b的正撞整数织，则a0≥b0”因为a0=b0=1，即乱条件泊语句慈的结罗论为谁真，所以验条件昌语句p(质0)为真29利用断等价烟关系焦证明p当且晃仅当qpq≡(pq)∧(qp)例1.培5.砍15证明衣对于计所有快的整番数n，n为奇遵数当且兼仅当n－1为偶朝数。30利用态等价算关系械证明例1.陆5.奸15证明客对于痕所有填的整匪数n，n为奇猪数当学且仅看当n－1为偶受数。证明猴：如果n为奇顷数，裕则n－1为偶去数。若n为奇耐数，米则n＝2k＋1，其员中k为某药个整亚数。毕于是n－1＝(2柿k＋1)－1＝2k，凤所以n－1为偶和数。下面葡证明嫁“如果n－1为偶缝数，提则n为奇哥数”。如果n－1为偶牺数，概则n－1＝2k，其吊中k为某艘个整似数。乡丰于是n＝2k＋1所以n为奇滥数。龟证毕拜。31反例暂证明赠法反驳x熟P(货x)只需昌在论森域内捡找到意一个x，使P(饿x)为假衣。例1.少5.奖19命题截“n芽(2n+1稍)是素崭数”为旋假。反例宪为n＝3时，23＝9，不啄是素狐数321.棉7证明灿方法狡和策醉略穷举病证明分情独况证峰明存在宣性证轧明唯一奋性证糕明证明绣策略331.看7.套2穷举士证明有些蔬定理砍可以饥通过盏有关卵的小荣数量上例子爸测验社来证班明——穷举指证明例，糖当n是一姑个正名整数软，且n老≤4时，(n排+1贤)3≥3n解：墓用穷仆举证疲明对于n=幻玉1,踩(齿n+相1)3=23=8温,而31=3，即(n脉+1柱)3≥3n对于n=秤2，(n普+1香)3=33=2悟7,而32=9，即(n骨+1葵)3≥3n对于n=屑3,保(铲n+百1)3=43=6弓4,而33=2端7，即(n藏+1冲)3≥3n对于n=造4,既(及n+办1)3=53=1洒25笼,而34=8缠1，即(n含+1向)3≥3n对于叶论域架中的养每个n，都吸有(n交+1迎)3≥3n34分情必况的业证明拥法例如涉，前微提“x是一傅个实涛数”先可以都被分修成两燃种情集况：(a绣)作x是一协个非议负实残数(b弟)狠x是一痰个负着实数宽。例1.算5.户14证明古对每稻个实唇数x，x≤|x酷|。证明显：当x≥0时，血根据毁绝对什值的钓定义溪，|x常|＝x，于峰是|x宽|≥x。当x<映0时，凯根据季绝对适值的和定义李，|x共|＝－x，因浩为|x简|＝－x>缎0，0>县x，所富以|x须|>趟x。两种改情况达下都既有|x川|≥x，所虫以命至题成渔立。351.叙7.崇3存在产性证链明需在涝论域毁中找拌到一笨个x使P(击x)为真希即可专。例1.温5.陡17令a和b为实琴数且a<绸b。证葵明存拒在实串数x满足a<岗x<茧b。证明回只泥需找碍到一样个实功数x满足a<昏x<匠b即可徒。实均数x＝显然久满足a<姿x<傅b。36372.饶4数学裙归纳膊法Sn表示n个正蛮整数皱的和Sn=捎1病+窝2毅+识⋯+n3839前n个自针然数态之和塔为n(元n+尘1)未/2证明鹅：对n进行砍归纳瞒。当n=站1时，烘有S(彻1)予=1骗=1剂×(盯1+钻1)来/2，故券命题即成立福。假设吴前n个自始然数泰之和S(咐n)为n(泡n+黄1)王/2。接着维证前n+草1个自乡丰然数愚之和S(罚n+鹿1)秀=(核n+瞧1)帖(n股+2绕)/偷2。根据S(察n)的定厅义，军有S(幸n+嗽1)驶=S乳(n流)+盯n+殊1，又由育假设S(矩n)颜=欧n(微n+辆1)啦/2，于刚是可道以推蚀得S(稀n+密1)霞=n肚(n窝+1盖)/标2+挡n+咳1=或(n辛+2柱)(征n+菠1)蜘/2，命兵题得装证。40数学湾归纳誉法原哭理设对勇于每航个正密整数n，我察们有便一个稻陈述s(巡寿n)，假径设s(蛛1)为真；如对亚于所不有的i，s(闻i)为真摩，s(耐i+娱1)也为筹真。则对秋于所呼有正居数n，s(吩n)为真会。41定义纹：n的阶败乘定作义即如影果n≥陈1，n！等欣于所田有1到n之间窃的整辞数的闯乘积铸。特别割是将0！定四义为142例2.帮4.骆3使用悠归纳枯法证兵明n!≥涌2n-揭1对所卸有n≥拼143如果秀要验概证命壁题S(n0),S(n0＋1)，…为真则必通须把基本节步变成S(n0)为真归纳乔步变为对任体意的n≥n0，如简果S(n)为真叫，则S(n+丹1)为真迫。44例2.肺4.横5用归水纳法停证明5n-1能被4整除居。基本凭步：n=圣1时显叫然为焰真归纳宣步：设5n-1可被4整除5n+胡1-1籍=5·5n-1箱=(营5n-1她)+盒4·5n可被4整除所以对于n=介1,观2…,祝5n-1能被4整除45对任肺意的酷自然榴数x和n，xn-1能被x-厨1除尽证明啄：对n进行雁归纳萍。基本异步：当n=物1时，寻定理辣显然弃成立规。归纳掉步：假设n-劈燕1时定摘理仍知然成刚立，守即假范设对摸任意环自然誉数x，xn-洞1-1能被x-诱1除尽绸。接下桂来要梅证明姻的就攀是xn-1能被x-枯1除尽饥。证明设思路慨就是愈用xn-治1-1来表隔达xn-1。根据动归纳伏假设xn-困1-1能被x-五1除尽因，则活：xn-1晃=x千(xn-词1-1判)胃