The discipline that deals with the methods of reasoning

Presentation on theme: "The discipline that deals with the methods of reasoning"— Presentation transcript:

1 The discipline that deals with the methods of reasoning
逻辑与证明 The discipline that deals with the methods of reasoning

2 什么是逻辑，为什么学逻辑？ 逻辑是日常生活中的重要工具： 父子对话： 如果以p表示“做完作业”，q表示“玩游戏”： 子：爸爸，我要玩游戏
父：不做完作业不能玩 如果以p表示“做完作业”，q表示“玩游戏”： 常理： 数学： 良好的逻辑能力能够让你思路清晰，给人以信任感！

3 逻辑迷题 泥巴孩谜题 p：男孩的额头上有泥 q：女孩的额头上有泥 pq 为真
一个男孩和一个女孩玩耍回来，看不见自己的额头，父亲说“你们当中至少有一个人额头上有泥”。父亲问孩子“你知道你额头上有没有泥？” p：男孩的额头上有泥 q：女孩的额头上有泥 pq 为真

4 什么是逻辑，为什么学逻辑？ 逻辑是计算机科学的重要基础 程序验证： 霍尔的初始/终结断言，证明程序相对于给予他们的规定是正确的：
是什么功能？对所有的合法输入，都能保证正确吗？ 霍尔的初始/终结断言，证明程序相对于给予他们的规定是正确的： 初始断言：T 终结断言：abs=|x| if x<0 then abs:=-x else abs:=x

5 为阅读和构造证明而必须掌握的若干基本逻辑要素：形式化
命题、真值 连接符及其真值表 说明复合命题的组成、复合命题的真值； 命题表达式及其真值的确定：真值表； 异或、蕴涵、双蕴含 双蕴含可以举菜单的例子； 可能式、永真式、永假式； 逻辑等价

6 命题 命题指可以判断真假的陈述句 判断下列句子是否为命题   税收下降了 我的收入上升了 今天是星期五 你会说英语吗? 3-x=5
我们走吧! 任一足够大的偶数一定可以表示为两个素数之和。 他是个多好的人呀！ “我现在说的是假话。”  

7 命题变元 常用小写字母表示命题变元，如： p, q, r 命题变元的取值范围为： {T, F}
命题也可以表示为命题变元的形式，可以理解为该变元“已赋值” p: 今天是周五（p=F） q: 2+2=4 （q =T）

8 原子命题与复合命题 并非外面在下雨。 张挥与王丽都是三好学生。 张晓静不是江西人就是安徽人。 自然语言中的复合句与连词 复合命题 显然：
如果2+3=6，则是有理数。 是无理数当且仅当加拿大位于亚洲。 显然： 复合命题是否为真，取决于： 作为复合成分的子命题的真假 以及 连词的语义

9 否定连接词 ~p: 非p p ¬ p F T F T ¬ 的真值表 p所有可能的取值

10 合取连接词 “p 并且 q” 表示为 pq p q pq pq=T iff p 和 q 均为T F F F T T F T T F T

11 析取连接词 pq=F iff both p and q 均为F “p 或 q” 表示为 pq p q p q F F F T T F

12 若干例 今天周一，开学第一天 我们周一和周五有离散数学课 我们周一或者周四踢足球 但是，套餐的菜单上写着： 鸡腿饭或者叉烧饭，苹果或香蕉
异或连接符

13 蕴涵连接词 “如果 p 则 q” 可以表示为 pq p q pq F F F T T F T T T F

14 关于蕴含连接符的“吐槽” 如果1+1=3，我就是超人 老师说，考试得85分以上会得奖。我考了90分，但没有得到奖
命题为真，不保证结论为真 老师说，考试得85分以上会得奖。我考了90分，但没有得到奖 老师犯逻辑错误咯！ 老师说，考试得85分以上会得奖。我考了80分，但得奖了！ 老师犯糊涂了？ 老师说，考试得不到85分以上别想得奖。我考了80分，但得奖了！ 老师说，想得奖，仅当考试得85分以上

15 关于蕴含连接符的“吐槽” 老师说，想得奖，仅当考试得85分以上 老师说，想得奖，除非考试得85分以上 胡适先生说：这句话错了
“除非”就是“如果不” 吕叔湘先生说：过于严格了 “除非”往往被大众理解为“只有” 要想人不知，除非己莫为

16 双蕴含连接词 pq 为真：意味着 p 和 q 总是 有相同的真值。 p q p  q F F F T T F T T T F

17 教材、习题、编程 教材： 习题： 编程： [Rosen] 1.1;1.2 P11: 2,10,14,20(任选4小题),32(任选3小题)
None