逻辑与证明.ppt

逻辑与证明,The discipline that deals with the methods of reasoning,什么是逻辑，为什么学逻辑？,逻辑是日常生活中的重要工具： 父子对话： 子：爸爸，我要玩游戏 父：不做完作业不能玩 如果以p表示“做完作业”，q表示“玩游戏”： 常理： 数学：,良好的逻辑能力能够让你思路清晰，给人以信任感！,逻辑迷题,泥巴孩谜题 一个男孩和一个女孩玩耍回来，看不见自己的额头，父亲说“你们当中至少有一个人额头上有泥”。父亲问孩子“你知道你额头上有没有泥？”,p：男孩的额头上有泥 q：女孩的额头上有泥 pq 为真,什么是逻辑，为什么学逻辑？,逻辑是计算机科学的重要基础 程序验证： 是什么功能？对所有的合法输入，都能保证正确吗？ 霍尔的初始/终结断言，证明程序相对于给予他们的规定是正确的： 初始断言：T 终结断言：abs=|x|,if x0 then abs:=-x else abs:=x,为阅读和构造证明而必须掌握的若干基本逻辑要素：形式化,命题、真值 连接符及其真值表 说明复合命题的组成、复合命题的真值； 命题表达式及其真值的确定：真值表； 异或、蕴涵、双蕴含 双蕴含可以举菜单的例子； 可能式、永真式、永假式； 逻辑等价,命题,命题指可以判断真假的陈述句 判断下列句子是否为命题 税收下降了 我的收入上升了 今天是星期五 你会说英语吗? 3-x=5 我们走吧! 任一足够大的偶数一定可以表示为两个素数之和。 他是个多好的人呀！ “我现在说的是假话。”, ,命题变元,常用小写字母表示命题变元，如： p, q, r 命题变元的取值范围为： T, F 命题也可以表示为命题变元的形式，可以理解为该变元“已赋值” p: 今天是周五（p=F） q: 2+2=4 （q =T）,原子命题与复合命题,自然语言中的复合句与连词 复合命题 并非外面在下雨。 张挥与王丽都是三好学生。 张晓静不是江西人就是安徽人。 如果2+3=6，则是有理数。 是无理数当且仅当加拿大位于亚洲。,显然： 复合命题是否为真，取决于： 作为复合成分的子命题的真假 以及 连词的语义,否定连接词,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 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,关于蕴含连接符的“吐槽”,如果1+1=3，我就是超人 命题为真，不保证结论为真 老师说，考试得85分以上会得奖。我考了90分，但没有得到奖 老师犯逻辑错误咯！ 老师说，考试得85分以上会得奖。我考了80分，但得奖了！ 老师犯糊涂了？ 老师说，考试得不到85分以上别想得奖。我考了80分，但得奖了！ 老师说，想得奖，仅当考试得85分以上,关于蕴含连接符的“吐槽”,老师说，想得奖，仅当考试得85分以上 老师说，想得奖，除非考试得85分以上 胡适先生说：这句话错了 “除非”就是“如果不” 吕叔湘先生说：过于严格了 “除非”往往被大众理解为“只有” 要想人不知，除非己莫为,双蕴含连接词,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,