Presentation is loading. Please wait.

Presentation is loading. Please wait.

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

Similar presentations


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节 课后习题: 见课程网站或者微信群


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

Similar presentations


Ads by Google