第一章 命题逻辑基本概念.ppt

1、离 散 数 学 简 介,离散：反义词？,连续,与离散有关的课程 1、连续量离散化：如数值积分、微分 离散量连续化：如数值逼近,数值计算 计算方法,计算机存储数值按字节不连续,2、离散量之间关系、运算：离散数学,离散数学的特点：,顾名思义，内容又离又散，概念繁多。 离散数学的内容： 数理逻辑、集合论（关系、函数）、 代数结构、 图论,离散数学与计算机课程,培养抽象思维、缜密概括能力 现实问题抽象为数学模型概括为程序的机械操作 先行课程: 高等代数、数学分析 后继的课程：数据结构、数据库系统、操作系统、数字电路、编译原理、算法的分析与设计、人工智能、计算机网络等。,课程情况,课程开设一学期，教学总

2、学时数为64学时。 学分数为4学分。 本课程采用笔试考核方式， 根据教学大纲命题。,离散数学的教与学,1提问式教学为主 : 考勤、考查、（促进）考虑 2学习方法（三步曲） 具体（现实“记忆实例”） 抽象（性质、 定理） 具体（计算机实现） 3学习态度： 积极. “有用” “无用”？,教材、笔记和参考书,教材：详细、流式 笔记：结构、典型实例 参考书： 一般参考： 离散数学左孝凌等 上海科技出版社 离散数学李俊锋等 清华大学出版社 离散数学 贲可荣等 清华大学出版社 离散数学李盘林等 高教出版社 深入学习： 数理逻辑、集合论、 近式代数 、图论,引 入,思维形式结构：,逻辑？,思维的规律,逻辑学

3、：,思维规律、思维形式结构,思维：,概念判断推理,在表象、概念的基础上进行分析、综合、推理等认识活动的过程。,思维的表示：,语言、文字,形式化？,数学方法？,代数化、公式化,枚举、归纳、演绎 反证 统计推理 ,实验形式：公理化体系 语言形式：推理小说、算命 形式化+数学方法数理逻辑,推理方法：,第一章 命 题 逻 辑 基 本 概 念,数理逻辑是用数学方法研究思维规律的一门学科。 数学方法是指：用一套数学的符号系统来描述和处理思维的形式与规律。因此，数理逻辑又称为符号逻辑。 本章介绍数理逻辑中最基本的内容命题逻辑： 首先引入命题、命题公式等概念。然后，在此基础上研究命题公式间的等值关系和蕴含关系

4、，并给出推理规则，进行命题演绎。,1.1 命题与联结词 1.2 命题公式及其赋值,主要内容,三、命题符号化,1.1 命题与联结词,一、命题的概念,二、命题联结词,例1 判断下列语句是否是命题。 （1）空气是人生存所必需的。 （2）请不要喧哗! （3）南京是中国的首都。 （4）你吃饭了吗？ （5）明年春节是个大晴天。 （6）啊，真美呀！,解 语句（1）,（3）,（5）是陈述句，也是命题 。,一个命题总是具有一个值，称为“真值”。 “真值”只有“真”和“假”两种， 记作：T（true）、F(false) 或 1、0,命题：能分辨真假的陈述句。,一、命题的概念,语句（2）、（4）、(6)不是陈述句，

5、因此,不是命题 。,形式化： 命题用大或小写的字母p、q、或者带下标的字母来表示。本书采用小写字母,例2 判断下列陈述句是否是命题。 p：地球外的星球上也有人； q：小王是我的好朋友； r：101+1=110,解： p、q、r都是命题，因为其真值是确定的。 只是p的真值现在不能确定； q的真值由时间、人物等因素确定； r的真值靠上下文确定，二进制运算为真否则为假。,所谓悖论, 是指对于命题q，如果从q为真, 可以推导出q为假, 又从q为非真推导出q为真, 我们就说命题q是一个悖论。 显然如果从命题p可引出一个命题q, 而q是一个悖论, 那么p也是一个悖论。,一类特殊的陈述句 悖论,例：说谎悖论

6、 有一个人断言:“我正在说谎”。 我们要问: 这个人是在说谎还是在讲真话?,如果他在说谎，这表明他的断言“我正在说谎”是谎话，也就是说他在讲真话。即他说谎， 推出他是讲真话(即没有说谎)。,另一方面，如果他讲真话， 这表明他的断言“我正在说谎”是真话， 也就是说他正说谎话， 即他讲真话, 推出他在说谎(即没有讲真话)。,理发师悖论 一个村上，有一个理发师公开宣布“他给而且只给村子中所有的自己不替自己理发的人理发”。 现在要问: 谁给这个理发师理发? 如果理发师的头由别人给他理，也就是说理发师自己不替自己理发，那么按照规定，这位理发师应该给自己理发。 另一方面,如果理发师的头由自己理，那么按照规

7、定， 理发师不能给自己理发。 也是一个悖论：理发师的头由别人来理, 不行；理发师的头由自己理，也不行。,原子（简单）命题 ：由简单陈述句形成的命题。,复合命题：由一个或几个原子命题(简单陈述句)通过联结词联接而构成的命题。,例3 p：雪不是白的（并非雪是白的） q：李明既是三好学生又是足球队员。 r：张平正在钓鱼或者正在睡觉。 s：如果明天天气晴朗，那么我们举行运动会。,二、命题联结词,原始陈述符号化符号化陈述,定义五种联结词（或称命题的五种运算）。,1. 否定“”,定义 设p是一个命题，复合命题“非p”(或“p的否定” ）称为p的否命题，记作“p” (读作“非p”)， 符号称作否定连接词 。

8、 规定：命题p取值为真时，命题p取值为假； 命题p取值为假时，命题p取值为真。,例4 设p：上海是一个城市； q：每个自然数都是偶数。 则有 p：上海不是一个城市; q：并非每个自然数都是偶数。,2合取“” 定义 设p和q是两个命题，复合命题“p并且q”(或“ p与q”) ，称为p与q的合取式，记作“p q” 、称作合取连接词。,规定： pq为真当且仅当命题p与q同时为真。,例5 设p：我们学习好。q：我们身体好。 则pq表示“我们学习好并且身体好。”,3. 析取“” 定义 设命题p和q为二命题，复合命题“p或q”称作p与q的析取式，记作pq， 称作析取连接词。 规定pq为假当且仅当p与q同时

9、为假。,由定义可知， pq取值为真当且仅当p和q至少有一个取值为真。,例6,将命题“他可能是100米或400米赛跑的冠军。”符号化。,解令 p：他可能是100米赛跑冠军； q：他可能是400米赛跑冠军。,则命题可表示为pq。,注意：这是一种可兼（相容性）或。 将命题“他可能是海军，也可能是空军。”符号化。 解令 p：他可能是海军； q：他可能是空军。 则命题可以表示为pq吗？,（pq）(pq),设p、q是两个命题，p异或q是一个复合命题，记作pq。,4. 蕴含（条件）“” 设p和q为二命题，复合命题“如果p，则q” 称为p与q的蕴含式，记作pq,并称p是蕴含式的前件，q为蕴含式的后件。 称作蕴

10、含连接词。 规定： pq为假当且仅当p为真q为假,当p为真: q为假时，pq为假； q为真时，pq为真， 当p为假: pq为真（善意推断）。（不论q为真还假）,例8 将命题“如果我得到这本小说，那么我今夜就读完它。”符号化。,解 令p：我得到这本小说； q：我今夜就读完它。 于是上述命题可表示为pr。,例9 如果用p表示“我有车”，q表示“我去接你”，那么pq表示命题“如果我有车，那么我去接你”。注意：当我有车时，若我去接了你，这时诺言pq真；若我没去接你，则诺言pq假。 当我没有车时，我无论去或不去接你均未食言，此时认定pq为真。 当p为假: pq为真，我们称为善意推断。,例“如果下雨，那么

11、我去接你”，这句话用p表示“天下雨”, q表示“我去接你”，那么pq表示命题就不确切了，因为这句话的潜台词是“如果不下雨，那么我就不去接你了”；而用p（pq）表示命题更确切。.,使用联接词，注意以下几点：,自然语言 只要p,就q 因为p,所以q p仅当q 只有q才p 除非q才p 除非q,否则非p,上述表面叙述不同，但都表达q是p的必要条件。用, 自然语言，“如果p,则q”，前件和后件具有某种内在联系 ，在数理逻辑中，p与q可以无联系。, 在数学和其它科学中，“如果p,则q”，往往表达的是前件为真，后件也为真的推理关系。但在数理逻辑中，作为一种规定，当p为假时，无论q是真还是假，p q均为真。,

12、5等价（双条件）“” 定义设p和q为二命题，复合命题“p当且仅当q”，称为p与q的等价式，记作“pq” ，“”称为等价连接词。 规定pq 为真当且仅当p与q 同时为真或同时为假,pq 的逻辑关系为p与q互为充分必要条件。,例10 非本仓库工作人员，一律不得入内。,解 令p：某人是仓库工作人员；q：某人可以进入仓库。,则上述命题可表示为pq。,例11 黄山比喜马拉雅山高，当且仅当3是素数 令p：黄山比喜马拉雅山高；q：3是素数 本例可符号化为pq,从汉语的语义看，p与q之间并无联系，但就联结词的定义来看，因为P的真值为假，q的真值为真，所以pq的真值为假。,对于上述五种联结词“、 、 、” ，应

13、注意到： 复合命题的真值只取决于构成它的各原子命题的真 值，而与这些原子命题的内容含义无关。,三、命题符号化,利用联结词可以把许多日常语句符号化。基本步骤如下：,（1）从语句中分析出各原子命题，将它们符号化； （2）使用合适的命题联结词，把原子命题逐个联结起来，组成复合命题的符号化表示。,联结词的优先顺序为： ( )、 “ ”、 “” 、“” 、 “” 、 “” 对于同一优先级的连接词，先出现者先运算。,命题符号化，无法表示“程度” P=“我一定去上学”， P是什么意思？,例12 将下列语句形式化。（1）我和他既是弟兄又是同学。（2）如果我和他都不是傻子，那么我们俩都不会去。,（1） p：我和

14、他是弟兄，q：我和他是同学； 命题表示为pq。 （2） p:我是傻子, q:他是傻子, r:我会去, s:他会去。 命题表示为（p q）(rs)或 p q(rs) 要善于确定原子命题，不要把一个概念硬拆成几个概念，或倒过来。,（3）我和你之间至少有一个要去海南岛。 （4）我和你之间有一个要去海南岛。,（3） p：我去海南岛，q：你去海南岛； 命题表示为pq。 （4） p：我去海南岛，q：你去海南岛； 命题表示为(pq)(pq)。 将语句形式化时，一定要注意形式化了的语句与原来的汉语语句有相同的语义。,（5）狗急跳墙。 （6）风雨无阻，我去上学。,（5） p：狗急了，q：狗跳墙，命题表示为 pq

15、。 （6） p：天刮风，q：天下雨，r：我去上学。命题表示为 (pqr) (pqr) (pqr) (pqr) 要善于识别自然语言中的联结词（有时它们被省略）。例如“狗急跳墙”一句，可理解为“如果狗急了，它就会跳墙”。“风雨无阻，我去上学”一句，可理解为“不管是否刮风、是否下雨我都去上学”。,（1）（pq） r；,例13 用符号形式表示下列命题 （1）如果明天早上下雨或下雪，那么我不去学校 （2）如果明天早上不下雨且不下雪，那么我去学校。 （3）如果明天早上不是雨夹雪，那么我去学校。 （4）只有当明天早上不下雨且不下雪时，我才去学校。,解 令p：明天早上下雨； q：明天早上下雪； r：我去学校。

16、,（2）（p q）r；,（3）(pq）r；,（4）r（p q）（必要）,否定词的位置要放准确。 注意充分必要条件的区别。,例14 将下列命题符号化 （1）派小王或小李出差； （2）我们不能既划船又跑步； （3） 如果你来了，那么他唱不唱歌将看你是否伴奏而定； （4） 如果李明是体育爱好者，但不是文艺爱好者，那么 李明不是文体爱好者；,（2） 令p：我们划船；q：我们跑步。 则命题可 表示为 (pq）,（3） 令p：你来了；q：他唱歌；r：你伴奏。 则命题可表示为 p（qr）,（4） 令p：李明是体育爱好者；q：李明是文艺爱好者。 则命题可表示为（p q）（p q）,（1） 令p：派小王出差；q

17、：派小李出差。 则 命题符号化为 pq,解： 令p：上午下雨；q：我去看电影；r：我在家读书。 则命题可表示为（p q）（pr）。,（5）假如上午不下雨，我去看电影，否则就在家里看书。,命题表示为（p q） （pr）为什么不行？,因为是善意推断，若下雨我不读书也是真，反之亦然。,以后我们可以证明（5）还可以等价的表示为： ( p q) (p r) 或（p （p q） （ p （pr）,练习1-1 1. 判断下列语句哪些是命题，若是命题，则指出其真值。 （1） 只有小孩才爱哭。 （2） X+6=Y （3） 银是白的。 （4） 起来吧，我的朋友。,( 是 假 ),( 不是 ),( 是 真 ),(

18、不是 ),2 将下列命题符号化 （1）我看见的既不是小张也不是老李。,解 令p：我看见的是小张；q：我看见的是老李。,则该命题可表示为pq,（2）如果晚上做完了作业并且没有其它的事，他就会看电视或听音乐。,解 令 p：他晚上做完了作业；q：他晚上有其它的事； r：他看电视； s：他听音乐。,则该命题可表示为（pq）（rs）,1.2 命题公式及其赋值,一 、 命题公式的概念,1. 命题常元 一个表示确定命题的小写字母。,2命题变元 一个没有指定具体内容的命题符号。也用小写字母表示。,一个命题变元当没有对其赋予内容时，它的真值不能确定，一旦用一个具体的命题代入，它的真值就确定了。,3. 命题公式 命题公式（或合式公式也简称公式）是由0、1和命题变元以及命题联结词按一定的规则产生的符号串。,定义（命题公式的递归定义。） （1） 0，1是命题公式； （2） 命题变元是命题公式； （3） 如果A是命题公式，则A是命题公式； （4） 如果A和B是命题公式，则（AB）， （AB）,(AB）,(A B）也是命题公式； 有限次地利用上述（1）（4）而产生的符号串是命题公式。,例1 下