离散数学─逻辑和证明 南京大学计算机科学与技术系

Presentation on theme: "离散数学─逻辑和证明 南京大学计算机科学与技术系"— Presentation transcript:

1 离散数学─逻辑和证明 南京大学计算机科学与技术系
命题逻辑 离散数学─逻辑和证明 南京大学计算机科学与技术系

2 内容提要 引言 逻辑运算符 命题表达式 命题的真值表 逻辑等价

3 引言－编程语言中的布尔表达式 Java程序设计语言中的布尔运算符 举例 程序验证需要考察有关不变式
&&, || , ! 举例 (a >= 5) && (a <= 10) p || !q 程序验证需要考察有关不变式 条件/循环语句 程序分析时需要考虑布尔表达式的可满足性 if x<0 then abs:=-x else abs:=x

4 引言－搜索引擎中的布尔检索 布尔逻辑检索 布尔运算符 利用布尔逻辑运算符进行检索项的逻辑组配，用以表达检索者的查询。
(“ San Zhang ” OR “张三") AND "Software Engineering" …… NOT “Ontology”// 有的使用“-”替代 “NOT” 布尔运算符 与，合取，Conjunction (AND) (, &, · ) 或，析取，Disjunction (OR) () 非，否定，Negation (NOT) (, ~, -)

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

6 引言－日常生活中的逻辑 父子对话 如果以p表示“做完作业”，q表示“玩游戏” 子：爸爸，我要玩游戏
父：不做完作业不能玩游戏 （除非…, 否则不允许…. ） 如果以p表示“做完作业”，q表示“玩游戏” 常理： pq 数学： p  q（等价命题：qp）

7 引言－日常生活中的推理 老张宴请好友，他和老钱先到目的地，等了好久小刘还没到。老张说道：“哎，该来的还没有来。” 问题：
如何理解“该来的还没有来”。 老钱如何进行推理：他该不该来？

8 Knowledge Representation and Reasoning, KR&R
引言－合理表述的重要性 不合理表述的后果会很严重 该来的没来 老钱走了 不该走的走了 留下的人也走了 知识表示与推理 Knowledge Representation and Reasoning, KR&R

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

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

11 原子命题与复合命题 复合命题 并非外面在下雨。 张挥与王丽都是三好学生。 张晓静不是江西人就是安徽人。 如果2+3=6，则是有理数。
复合命题是否为真，取决于： 作为复合成分的子命题的真假 逻辑运算符（联接词）的语义 复合命题 并非外面在下雨。 张挥与王丽都是三好学生。 张晓静不是江西人就是安徽人。 如果2+3=6，则是有理数。 是无理数当且仅当加拿大位于亚洲。

12 否定（运算符，联接词） ¬p: “非p” ¬ p的真值表 p ¬ p 1 1 p所有可能的取值

13 合取（运算符，联接词） pq：“p 并且 q” p q pq pq=1 iff p和q均为1 0 0 0 1 1 0 1 1 1
1 (p,q) 所有可能的取值

14 析取（运算符，联接词） pq=0 iff p和q均为0 pq：“p 或 q” p q p q 1

15 蕴含（运算符，联接词） pq：“若 p ，则 q” （条件语句） p称为假设，q称为结论 pq =0 iff p为1而q为0 p q
1

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

17 关于蕴含 pq：“若 p ，则 q” （条件语句） “想得奖，仅当/只有考试得85分以上”
“得奖”  “考试得85分以上” 考不到85分以上，甭想得奖 不能玩游戏，除非做完作业（  p, 除非 c） 没有做完作业，就不能玩（ c   p ）

18 双蕴含（运算符，联接词） pq ：“p当且仅当 q ”（双条件语句） p q p  q 0 0 0 1 1 0 1 1 1
1 pq =1 iff p和q有相同的真值

19 命题表达式（命题逻辑公式） 命题变元是命题表达式； 若p是命题表达式，则（¬ p）也是；
若p和q是命题表达式，则(pq), (pq), (p  q), (pq)也是； 只有有限次应用上述规则形成的符号串才是命题表达式。 (pq)(qr), p(qr)是命题公式（省略了外层括号）。 pqr以及 pq都不是命题公式。 pq r， ¬ pq ， (¬ p)q是命题公式 运算符的优先级： ¬， ， ， ，

20 将自然语言翻译成命题表达式 只有你主修计算机科学或不是新生, 才可以从校园网访问因特网. a: 你可以从校园网访问因特网
c: 你主修计算机科学 f: 你是新生 a  (c  ¬f)；

21 将自然语言翻译成命题表达式（续） 除非你满16周岁, 否则只要你身高不足4英尺就不能乘滑行游乐车. q: 你能乘滑行游乐车
r: 你身高不足4英尺 s: 你满16周岁 s  (r ¬q) (¬sr) ¬q

22 将自然语言翻译成命题表达式（续） 套餐的菜单上写着： 鸡腿饭或者叉烧饭，苹果或香蕉

23 命题表达式的真值表 (¬pq)¬r p q r ¬ p ¬pq ¬r (¬pq)¬r 0 0 0 0 0 1 0 1 0
该命题表达式的所有指派 1 1 1 1 一种“成假”指派

24 命题表达式的真值表 (pq)  ((pq)(qp)) (pq)  ((pq)(qp)) 0 0 0 1 1 0 1 1
1 1 1 1 1

25 永真式、矛盾式与可能式 可能式：既不是永真式又不是矛盾式。比如： ¬p
永真式（重言式）：总是真的，无论其中出现的命题变元如何取值。比如：p¬p 矛盾式：总是假的，无论其中出现的命题变元如何取值。比如： p¬p 可能式：既不是永真式又不是矛盾式。比如： ¬p p ¬ p 1 p¬p p¬p

26 逻辑等价 p和q逻辑等价：在所有可能情况下p和q都有相同的真值。 也就是说，pq是永真式。 记法：p  q
pq  (pq)(qp) T  p¬p F  p¬p

27 命题逻辑公式（定义为一个形式语言）

28

29 作业 教材内容：[Rosen] 1.1，1.2，1.3节 课后习题： 见课程网站或者微信群