《离散数学 第2版 教学课件 ppt 作者 王元元 离散第9讲 命题与逻辑联结词》由会员分享，可在线阅读，更多相关《离散数学 第2版 教学课件 ppt 作者 王元元 离散第9讲 命题与逻辑联结词（28页珍藏版）》请在金锄头文库上搜索。
1、,计算机专业基础课程,授课人：王元元 单位：计算机理论教研室,指挥自动化学院计算机系,PowerPoint Template_Sub,逻辑学是一门非常古老的学科，到现在已经有了两千多年的历史。古典逻辑学主要起源于古希腊学者亚里士多德的逻辑学说，他创作的工具论一书是古代一部最完备的逻辑学著作 古典逻辑学的基本特点是用自然语言描述对逻辑的研究，而一旦超出这个范围，引入数学的方法来研究逻辑，就产生了远远优于古典逻辑学的现代逻辑学 数理逻辑也称符号逻辑，是现代逻辑学研究的主体部分，是一门运用数学方法研究思维规律的边缘性学科。将推理变成数学演算，这是数理逻辑的指导思想，并且已经成为这门学科的主要特征 数
2、理逻辑是用形式化(符号化)方法来研究推理的科学,PowerPoint Template_Sub,侦探调查了罪案的四个证人。从证人的话侦探得出的结论是： 如果男管家说的是真话，那么厨师说的也是真话； 厨师和园丁说的不可能都是真话； 园丁和杂役不可能都在说谎 如果杂役说真话，那么厨师在说谎 侦探能判断这四个证人分别是在说谎还是在说真话吗？,推理的例子,-4-,第9讲 命题与逻辑联结词,PowerPoint Template_Sub,命题与逻辑联结词,逻辑等价式和逻辑蕴涵式,范式,证明技术（补充）,命题与逻辑联结词,离散数学第9讲,Page 27 to 33,-6-,第9讲 命题与逻辑联结词,内容提
3、要,命题的概念 断言与命题、命题真值表示 原子命题和复合命题、命题常元、命题变元 逻辑联结词 、 、 、 、 命题公式 公式的归纳定义 指派 自然语句的形式化,-7-,第9讲 命题与逻辑联结词,命题 (proposition或statement),断言(affirmation)：是一个表示判断的陈述句，它是命题的前身 命题：是一句有确定真假值的断言 或是真，或是假，但二者不能得兼（排中律） 真、假常被称为命题的真值,用大写的英文字母T或“1”表示命题真值是“真的” F或“0”表示命题的真值是“假的”,-8-,第9讲 命题与逻辑联结词,命题举例,雪是白的 半径为1的圆的面积为2 2是偶数且3也是
4、偶数 陈胜起义那天杭州下雨 大于2的偶数均可以分解为两个质数的和 数学多美啊! X+Y=4 “我正在说谎。” 我只给那些不给自己刮胡子的人刮胡子,-9-,第9讲 命题与逻辑联结词,原子命题和复合命题,命题常元和变元 命题变元是指一个未确定真值的任意命题，其值在0，1上变化 命题常元是指一个有确定真值的固定命题 原子命题：一个不能再分解成更简单语句的命题 原子命题是最简单的陈述句 原子命题通常记为p、q、r等小写字母，f表示恒假命题，t表示恒真命题 相对于原子命题的是复合命题，它是由原子命题通过逻辑联结词进行适当的组合而成的 复合命题的真值不仅依赖于这两个组成它的命题，而且还依赖于这个联结词的意
5、义,-10-,第9讲 命题与逻辑联结词,举例,p：明天下雪；q：明天下雨 利用联结词“不”、“或”、“且”等可分别构成新命题： “非p”：明天不下雪 “p或q” ：明天要么下雪，要么下雨 “p并且q”：明天下雨雪,-11-,第9讲 命题与逻辑联结词,常用5个逻辑联结词,否定词(negation) ：P，“P不成立”、“并非P” 否定词是一元运算。 否定的是整个命题，并不是否定命题中个别的词。,真值表,“A和B都大于0”的否定： “A和B都不大于0” “A和B不都大于0” “A和B至少有一个不大于0” “A和B至少有一个小于等于0”,“A大于0”的否定： “A不大于0” “A小于等于0”,-12
6、-,第9讲 命题与逻辑联结词,常用5个逻辑联结词,合取词(conjunction) ：pq， “p并且q”、“p和q都成立” 合取词是二元运算 只有当p和q均为真时，pq才是真的，否则，pq是假的 是可交换的,p:今天是星期三； q:今天上离散数学课； p q：今天是星期三并且上离散数学课；,-13-,第9讲 命题与逻辑联结词,常用5个逻辑联结词,析取词(disjunction) ：pq，“p成立或者q成立”、“p或q” 析取词是二元运算 只有当p和q的真值均为假时， pq才是假的，否则， pq总是真的,p:我上午上离散数学； q:我上午上操作系统； p q：我上午或者上离散数学，或者上操作系
7、统；,p:我上午一二节课上离散数学； q:我上午一二节课上操作系统； p q：我上午一二节课要么上离散数学，要么上操作系统(不会上两门)；,同或,异或,-14-,第9讲 命题与逻辑联结词,常用5个逻辑联结词,蕴涵词(implication) ：pq，“如果p，那么q”、“p蕴涵q”、“p是q的充分条件” 从真值表可以看出，只有当前提为真，而结论是假时，pq才是假的,逆命题：qp； 否命题：pq 逆否命题：qp 命题和逆否命题有相同的真值,“如果今天是星期三，那么2+3=6”： 前提为假，蕴涵命题为真； 前提和结论之间可以没有关系，称为实质蕴涵,p:天晴； q:我爬山； 只要天晴，我就爬山： p
8、 q 只有天晴，我才爬山： q p,“只要下雨，我们队就能赢”,-15-,第9讲 命题与逻辑联结词,常用5个逻辑联结词,-16-,第9讲 命题与逻辑联结词,常用5个逻辑联结词,双向蕴涵词(two-way implication) ：p q，“p当且仅当q”、“如果p，那么q；反之亦然” 只有当p和q的真值相同时，pq才取真的真值 pq与(pq)(qp)有完全相同的真值。,“只有你健康，你才会感到快乐；只有感觉快乐你才健康”,-17-,第9讲 命题与逻辑联结词,命题公式 (proposition formula),命题公式：是一个表达式，它是由命题常元、命题变元、联结词符号和圆括号所组成的一个字
9、符串 归纳定义： 命题常元和命题变元是命题公式，也称为原子公式或原子 如果A，B是命题公式，那么（A）、（AB）、（AB）、（AB）、（AB）也是命题公式 只有有限步引用条款（1）、（2）所组成的符号串是命题公式,-18-,第9讲 命题与逻辑联结词,简写约定,为了减少圆括号的使用，我们约定： 省掉最外面的括号 联结词的结合能力强弱为、（、）、 结合能力平等的联结词从左到右运算 (p) (q (r q) s) p q (r q s),-19-,第9讲 命题与逻辑联结词,指派(assignment),设公式A含有n个命题变元p1， p2 ， pn记为A(p1, pn ) 给定这n个变元任意一组确定
10、的值（每一变元都有取真或假两种可能），公式A得到一个确定的值（1或0），我们称这一组确定的值为公式A的一组完全指派 常用表示指派，若在某一指派下A取真的真值，则称弄真A，记为 (A)=1, 反之称弄假A，记为 (A)=0,-20-,第9讲 命题与逻辑联结词,复合命题公式的真值表,首先确定在公式中出现的命题变元的个数。 写出公式A的所有指派，一个指派为一行，若有n个命题变元，则有2n组指派，也就是说真值表有2n+1行。 确定公式中联结词的个数，写出单个联结词的真值，一般讲，一个联结词对应着一列。,(pq)r)p 的真值表,-21-,第9讲 命题与逻辑联结词,指派举例,使公式A: (pq)r)p为
11、真的指派,(A)=1,1. (pq)r)=1， (p)=1，,2. (pq)r)=0， (p)=0 (r)=0, (r)=1,1.1. (q)=1,1.1.1. (r)=0,1.1.2. (r)=1,1.2. (q)=0,1.2.1. (r)=0,2.1. (q)=0,2.2. (q)=1,(1,1,0),(1,1,1),(1,0,0),(0,0,1),(0,1,1),-22-,第9讲 命题与逻辑联结词,语句形式化举例,设p：a是偶数 q：a是奇数 r：a是质数 s：a=2，如何理解下述命题公式 pq pr s p （r s） rs q （qs）r r （q s） r q s,-23-,第9讲
12、 命题与逻辑联结词,语句形式化举例,我和他既是兄弟又是同学 pq，其中： p：我和他是兄弟，q：我和他是同学 我和他至少有一个要去外地 pq，其中： p：我去外地，q：他去外地 狗急跳墙 pq，其中： p：狗急了，q：狗跳墙 除非他来，否则我不同他和解 pq，(pq)(pq)，其中： p：他来，q：我同他和解,-24-,第9讲 命题与逻辑联结词,语句形式化举例,如果你和他不都是傻子，那么你们俩都不会去自讨没趣 （pq）（rs），其中： p：你是傻子；q：他是傻子 r：你会去自讨没趣；s：他会去自讨没趣 若天气不下雨或不起雾，则航行比赛将举行而且救生表演将进行 如果他没来见你，那么他或者是生病了
13、，或者是不在本地,-25-,第9讲 命题与逻辑联结词,推理的例子,侦探调查了罪案的四个证人。从证人的话侦探得出的结论是： 如果男管家说的是真话，那么厨师说的也是真话； 厨师和园丁说的不可能都是真话； 园丁和杂役不可能都在说谎 如果杂役说真话，那么厨师在说谎,p、q、r、s：分别表示男管家、厨师、园丁、杂役说的是真话,1、pq 2、qr 3、rs 4、sq,哪些指派使这四个命题公式同时为真？,-26-,第9讲 命题与逻辑联结词,推理的例子,一个探险者被几个吃人者抓住了。 有两种吃人者：总是说谎的和永不说谎的。 除非探险者能判断出一位指定的吃人者是说谎者还是说真话者，否则就要被吃人者烤了吃。 探险
14、者只被允许问这位吃人者一个问题。 “ 你是说真话者？”、“你是说谎者？”,p：你是说真话的人,构造一个公式S，让吃人者回答,pp,-27-,第9讲 命题与逻辑联结词,推理的例子,边远村庄的每个人要么总说真话，要么总说谎。 对旅游者的问题，村民要么回答“是”，要么回答“不”。 假定你在这一地区旅游，走到了一个岔路口，一条岔路口通向你想去的遗址，另一条岔路口通向丛林深处。 此时恰有一村民在岔路口，问村民什么样的一个问题就能决定走哪条路呢？,p：你是说真话的人；q：应该向右走 构造一个公式S，让村民回答,pq,-28-,第9讲 命题与逻辑联结词,本讲小结,主要内容 命题的概念：什么是命题、命题的真值 五个主要的逻辑联结词 命题公式的概念、命题公式的真值表 语句的形式化 作业 P44. 1 (3) (5) (7) (9) (11) (13) (15) 2 (2)(4)(8) 3 (1)(2),
