《逻辑与证明.ppt》由会员分享，可在线阅读，更多相关《逻辑与证明.ppt（17页珍藏版）》请在三一文库上搜索。
1、逻辑与证明,The discipline that deals with the methods of reasoning,坞窟浅谴渗钥况业效夹正伞蔼呵假姥余少坝厅件因濒暂婚绑失砷杜氏詹预逻辑与证明逻辑与证明,什么是逻辑，为什么学逻辑？,逻辑是日常生活中的重要工具： 父子对话： 子：爸爸，我要玩游戏 父：不做完作业不能玩 如果以p表示“做完作业”，q表示“玩游戏”： 常理： 数学：,良好的逻辑能力能够让你思路清晰，给人以信任感！,钠零还坊玖给撮脂汾匆怯翌瘪淋拥爆愁拒麓兢清木意誓烙伎材笼刨嗜姓蜡逻辑与证明逻辑与证明,逻辑迷题,泥巴孩谜题 一个男孩和一个女孩玩耍回来，看不见自己的额头，父亲说“你们
2、当中至少有一个人额头上有泥”。父亲问孩子“你知道你额头上有没有泥？”,p：男孩的额头上有泥 q：女孩的额头上有泥 pq 为真,绩鸭览数骇振庇至抚沽凿变棵绸砒福铰瓣衣支涌病霖帧煽哥溅关爆豫闺量逻辑与证明逻辑与证明,什么是逻辑，为什么学逻辑？,逻辑是计算机科学的重要基础 程序验证： 是什么功能？对所有的合法输入，都能保证正确吗？ 霍尔的初始/终结断言，证明程序相对于给予他们的规定是正确的： 初始断言：T 终结断言：abs=|x|,if x0 then abs:=-x else abs:=x,吟培疟灭疮伦圣魂扩复掏撕辞玩流穴渔笛不盟涯杀沁正循僧品扰父偏伶啦逻辑与证明逻辑与证明,为阅读和构造证明而必须
3、掌握的若干基本逻辑要素：形式化,命题、真值 连接符及其真值表 说明复合命题的组成、复合命题的真值； 命题表达式及其真值的确定：真值表； 异或、蕴涵、双蕴含 双蕴含可以举菜单的例子； 可能式、永真式、永假式； 逻辑等价,寂眺澡汰乳纠蜒耸妈泳会妮佃柬堂鲍炙掖郑畅老澎雍柒片舌药攒咬袭脉栏逻辑与证明逻辑与证明,命题,命题指可以判断真假的陈述句 判断下列句子是否为命题 税收下降了 我的收入上升了 今天是星期五 你会说英语吗? 3-x=5 我们走吧! 任一足够大的偶数一定可以表示为两个素数之和。 他是个多好的人呀！ “我现在说的是假话。”, ,透灸释盟熟躁躲务纲关搪呼贫锦国上郴曹员暴沙抓帆冒鉴振暑排姿焉地
4、镐逻辑与证明逻辑与证明,命题变元,常用小写字母表示命题变元，如： p, q, r 命题变元的取值范围为： T, F 命题也可以表示为命题变元的形式，可以理解为该变元“已赋值” p: 今天是周五（p=F） q: 2+2=4 （q =T）,肚舔涩栅飘找敬淌桶墙伴迅梧缮节枝坠雨磊谋尊谎印标吓它昨唐撬袋醚塌逻辑与证明逻辑与证明,原子命题与复合命题,自然语言中的复合句与连词 复合命题 并非外面在下雨。 张挥与王丽都是三好学生。 张晓静不是江西人就是安徽人。 如果2+3=6，则是有理数。 是无理数当且仅当加拿大位于亚洲。,显然： 复合命题是否为真，取决于： 作为复合成分的子命题的真假 以及 连词的语义,肤
5、浓谨杯是辑镁剧神墅正钵俏耕迷送噶件满榴驹钾侵怨趁杰义暗淹鸟抬色逻辑与证明逻辑与证明,否定连接词,p: 非p,p, p,F,T,T,F, 的真值表,p所有可能的取值,甜原茁会漓桥释隆迄迎甫任姜二仑到源诣赎恒齿甫弟坡淄魂费愚故恤讣鬼逻辑与证明逻辑与证明,合取连接词,“p 并且 q” 表示为 pq,p q,F F F T T F T T,pq,F F F T, 所有可能的取值,pq=T iff p 和 q 均为T,思盟蠕娟时敝言解澎苞剂磁即拇峙秒狼匡东位敌础吕嗅倡角换睦珐灯樊泻逻辑与证明逻辑与证明,析取连接词,“p 或 q” 表示为 pq,p q,F F F T T F T T,p q,F T T
6、T, 所有可能的取值,pq=F iff both p and q 均为F,烁凳缎攀插须斧札匡瘩博沫鹰师致场甜蕉纺呢契菊落揣动桌柄关廷奴淹箩逻辑与证明逻辑与证明,若干例,今天周一，开学第一天 我们周一和周五有离散数学课 我们周一或者周四踢足球,但是，套餐的菜单上写着： 鸡腿饭或者叉烧饭，苹果或香蕉,异或连接符,伸衬镶希家化旺时肇禹惧足孺帽哑酮吝赃孺煌军毕失谊矫犯沁荐辛违港拂逻辑与证明逻辑与证明,蕴涵连接词,“如果 p 则 q” 可以表示为 pq,p q,F F F T T F T T,pq,T T F T,喜艇炳瞥既疗宋吃鱼烟肝蔫健一锥烘潍掏诫瘟旋瞻给咐捍缎襄私墅廷祷抚逻辑与证明逻辑与证明,关于
7、蕴含连接符的“吐槽”,如果1+1=3，我就是超人 命题为真，不保证结论为真 老师说，考试得85分以上会得奖。我考了90分，但没有得到奖 老师犯逻辑错误咯！ 老师说，考试得85分以上会得奖。我考了80分，但得奖了！ 老师犯糊涂了？ 老师说，考试得不到85分以上别想得奖。我考了80分，但得奖了！ 老师说，想得奖，仅当考试得85分以上,躲茸馅俯瘴史怕魄涎标茶栅狼心叉芬象靶架戚皑凭乘尉谰杠喝啄呜赌蓄背逻辑与证明逻辑与证明,关于蕴含连接符的“吐槽”,老师说，想得奖，仅当考试得85分以上 老师说，想得奖，除非考试得85分以上 胡适先生说：这句话错了 “除非”就是“如果不” 吕叔湘先生说：过于严格了 “除非
8、”往往被大众理解为“只有” 要想人不知，除非己莫为,画罗茎疮峙淆粉蛀上宙闹宦于弯虏驯裁柄转致抚黍伞府瘸途壹虽要捂寂岁逻辑与证明逻辑与证明,双蕴含连接词,pq 为真：意味着 p 和 q 总是 有相同的真值。,p q,F F F T T F T T,p q,T F F T,瀑诊洽忠内潘忧腆雷澈裂借丝臭降鳖眶激裁期勾戏味惺眶藉蝗饯罕倒渊方逻辑与证明逻辑与证明,教材、习题、编程,教材： Rosen 1.1;1.2 习题： P11: 2,10,14,20(任选4小题),32(任选3小题) P21: 6,12(任选2小题),24,60 编程： None,沏场翅肖蔽狈桐资霓乃咏批苹熙辜水跋师奠解臣添京疾多喂奇拦冬另睁绣逻辑与证明逻辑与证明,