《逻辑与证明》PPT课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,逻辑与证明,The discipline that deals with the methods of reasoning,什么是逻辑，为什么学逻辑？,逻辑是日常生活中的重要工具：,父子对话：,子：爸爸，我要玩游戏,父：不做完作业不能玩,如果以,p,表示“做完作业”，,q,表示“玩游戏”：,常理：,数学：,良好的逻辑能力能够让你思路清晰，给人以信任感！,逻辑迷题,泥巴孩谜题,一个男孩和一个女孩玩耍回来，看不见自己的额头，父亲说“你们当中至少有一个人额头上有泥”。父亲问孩子“你知道你额头上有没有泥？”,p,：男孩的额头上有泥,q,：女孩的额头上有泥,p,q,为真,什么是逻辑，为什么学逻辑？,逻辑是计算机科学的重要基础,程序验证：,是什么功能？对所有的合法输入，都能保证正确吗？,霍尔的初始,/,终结断言，证明程序相对于给予他们的规定是正确的：,初始断言：,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,”,表示为,p,q,p q,F F,F T,T F,T T,p,q,F,F,F,T,所有可能的取值,p,q,=T,iff,p,和,q,均为,T,析取连接词,“,p,或,q,”,表示为,p,q,p q,F F,F T,T F,T T,p,q,F,T,T,T,所有可能的取值,p,q=,F,iff both,p,and,q,均为,F,若干例,今天周一，开学第一天,我们周一和周五有离散数学课,我们周一或者周四踢足球,但是，套餐的菜单上写着：,鸡腿饭或者叉烧饭，苹果或香蕉,异或连接符,蕴涵连接词,“,如果,p,则,q,”,可以表示为,p,q,p q,F F,F T,T F,T T,p,q,T,T,F,T,关于蕴含连接符的“吐槽”,如果,1+1=3,，我就是超人,命题为真，不保证结论为真,老师说，考试得,85,分以上会得奖。我考了,90,分，但没有得到奖,老师犯逻辑错误咯！,老师说，考试得,85,分以上会得奖。我考了,80,分，但得奖了！,老师犯糊涂了？,老师说，考试得不到,85,分以上别想得奖。我考了,80,分，但得奖了！,老师说，想得奖，仅当考试得,85,分以上,关于蕴含连接符的“吐槽”,老师说，想得奖，仅当考试得,85,分以上,老师说，想得奖，除非考试得,85,分以上,胡适先生说：这句话错了,“除非”就是“如果不”,吕叔湘先生说：过于严格了,“除非”往往被大众理解为“只有”,要想人不知，除非己莫为,双蕴含连接词,p,q,为真：意味着,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,