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