南京大学：《离散数学》课程教学资源（PPT课件讲稿）Lecture 01 命题逻辑（主讲：姚远）

1 命题逻辑

命题逻辑 1

本节提要 2 问题1：什么是命题逻辑？ 问题2：如何判断命题表达式的真假？ 问题3：如何判定命题可满足？

本节提要 2 问题1：什么是命题逻辑？ 问题2：如何判断命题表达式的真假？ 问题3：如何判定命题可满足？

引言 3 口编程语言中的布尔表达式 口程序分析时需要考虑布尔表达式的可满足性 ■(a>=5)&&(a<=10);pll!q 口搜索引擎中的布尔检索 口表达检索者的查询意图 ■(“Yuan Yao'”OR“姚远"”)AND“Computer Science?”AND(NOT “Female”) 口布尔运算符 a与，合取，Conjunction(AND)(,&,·) 口或，析取，Disjunction(OR)(v) 非，否定，Negation (NOT)(一，~，) 扣

引言  编程语言中的布尔表达式  程序分析时需要考虑布尔表达式的可满足性 ◼ (a >= 5) && (a <= 10) ; p || !q  搜索引擎中的布尔检索  表达检索者的查询意图 ◼ (“ Yuan Yao” OR “姚远”) AND “Computer Science” AND (NOT “Female” )  布尔运算符  与，合取，Conjunction (AND) (, &, · )  或，析取，Disjunction (OR) ()  非，否定，Negation (NOT) (, ~, -) 3

引言 4 口什么是逻辑？ 口在数学里，逻辑是指研究某个形式语言的有效推论 口推理和证明的思想过程 0 逻辑有什么作用？ 口用来做分析与论证 口逻辑引导人们通过推理获得事物的本质 口逻辑让描述变得严谨、无歧义

 什么是逻辑？  在数学里，逻辑是指研究某个形式语言的有效推论  推理和证明的思想过程  逻辑有什么作用？  用来做分析与论证  逻辑引导人们通过推理获得事物的本质  逻辑让描述变得严谨、 无歧义 4 引言

引言 口逻辑是日常生活中的重要工具： 口父子对话： ■子：爸爸，我要玩游戏 ■父：不做完作业不能玩 口如果以P表示“做完作业”，q表示“玩游戏”： ■常理：p→I ■数学：一p-→一q(等价命题：q→p)

引言  逻辑是日常生活中的重要工具：  父子对话： ◼ 子：爸爸，我要玩游戏 ◼ 父：不做完作业不能玩  如果以p表示“做完作业”，q表示“玩游戏”： ◼ 常理： p→q ◼ 数学： p→  q（等价命题：q→p） 5

命题 命题，(proposition)是无法严格定义的，一般可用 如下解释 “命题”主要是指一些字或者其它符号组 合成的一种形式，这种形式所表达的或者 为真或者为假。 罗素

命题  命题（proposition）是无法严格定义的，一般可用 如下解释

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

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

命题变元 口命题变元：代表命题的变量 口常用小写字母表示，如：p,q,r 口命题变元的取值范围为：{T,F} 口p:今天是周六(p=F) 口q:2+2=4(q=T) 口命题逻辑就是涉及命题的逻辑领域

 命题变元：代表命题的变量  常用小写字母表示，如：p, q, r  命题变元的取值范围为：{T, F}  p: 今天是周六（p=F）  q: 2+2=4 （q =T）  命题逻辑就是涉及命题的逻辑领域 命题变元

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

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

否定连接词 10 p/一p:非p -p F T F 一的真值表 p所有可能的取值

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