《逻辑与证明》PPT课件.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 FF TT FT T,pq,F FF T,所有可能的取值,pq=T iff p 和 q 均为T,析取连接词,“p 或 q”表示为 pq,p q,F FF TT FT T,p q,F TT T,所有可能的取值,pq=F iff both p and q 均为F,若干例,今天周一，开学第一天我们周一和周五有离散数学课我们周一或者周四踢足球,但是，套餐的菜单上写着：鸡腿饭或者叉烧饭，苹果或香蕉,异或连接符,蕴涵连接词,“如果 p 则 q”可以表示为 pq,p q,F FF TT FT T,pq,TTF T,关于蕴含连接符的“吐槽”,如果1+1=3，我就是超人命题为真，不保证结论为真老师说，考试得85分以上会得奖。我考了90分，但没有得到奖老师犯逻辑错误咯！老师说，考试得85分以上会得奖。我考了80分，但得奖了！老师犯糊涂了？老师说，考试得不到85分以上别想得奖。我考了80分，但得奖了！老师说，想得奖，仅当考试得85分以上,关于蕴含连接符的“吐槽”,老师说，想得奖，仅当考试得85分以上老师说，想得奖，除非考试得85分以上胡适先生说：这句话错了“除非”就是“如果不”吕叔湘先生说：过于严格了“除非”往往被大众理解为“只有”要想人不知，除非己莫为,双蕴含连接词,pq 为真：意味着 p 和 q 总是 有相同的真值。,p q,F FF TT FT T,p q,TFFT,教材、习题、编程,教材：Rosen 1.1;1.2习题：P11:2,10,14,20(任选4小题),32(任选3小题)P21:6,12(任选2小题),24,60编程：None,