命题与逻辑联结词

1、专业基础课程专业基础课程vPowerPoint Template_Sub 逻辑学是一门非常古老的学科，到现在已经有了两千多年逻辑学是一门非常古老的学科，到现在已经有了两千多年的历史。古典逻辑学主要起源于古希腊学者亚里士多德的的历史。古典逻辑学主要起源于古希腊学者亚里士多德的逻辑学说，他的逻辑学说，他的工具论工具论是古代一部最完备的逻辑学著是古代一部最完备的逻辑学著作。作。古典逻辑学的基本特点是用自然语言描述对逻辑的研究，古典逻辑学的基本特点是用自然语言描述对逻辑的研究，而一旦超出这个范围，而一旦超出这个范围，引入数学的方法引入数学的方法来研究逻辑，就产来研究逻辑，就产生了远远优于古典逻辑学的生

2、了远远优于古典逻辑学的现代逻辑学现代逻辑学。 数理逻辑数理逻辑也称也称符号逻辑符号逻辑，是现代逻辑学研究的主体部分，是现代逻辑学研究的主体部分，是一门是一门运用数学方法研究思维规律的学科运用数学方法研究思维规律的学科。将推理变成数。将推理变成数学演算，是数理逻辑的指导思想，并且已经成为这门学科学演算，是数理逻辑的指导思想，并且已经成为这门学科的主要特征的主要特征 。数理逻辑是用形式化数理逻辑是用形式化(符号化符号化)方法来研究推理的科学。方法来研究推理的科学。孔子孔子是是孔仲尼孔仲尼孔子孔子是是人人 人人是是动物动物 vPowerPoint Template_Sub 侦探调查了罪案的四个证人。

3、从证人的话侦探得侦探调查了罪案的四个证人。从证人的话侦探得出的结论是：出的结论是：如果男管家说的是真话，那么厨师说的也是真话；如果男管家说的是真话，那么厨师说的也是真话；厨师和园丁说的不可能都是真话；厨师和园丁说的不可能都是真话；园丁和杂役不可能都在说谎园丁和杂役不可能都在说谎如果杂役说真话，那么厨师在说谎如果杂役说真话，那么厨师在说谎侦探能判断这四个证人分别是在说谎还是在说真侦探能判断这四个证人分别是在说谎还是在说真话吗？话吗？推理的例子推理的例子-5-第第9讲讲 命题与逻辑联结词命题与逻辑联结词vPowerPoint Template_Sub 1命题与逻辑联结词命题与逻辑联结词2逻辑等价式

4、和逻辑蕴涵式逻辑等价式和逻辑蕴涵式3范式范式4证明技术（补充）证明技术（补充）v命题与逻辑联结词命题与逻辑联结词离散数学离散数学第第9 9讲讲Textbook Page 56 to 62-7-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v内容提要内容提要命题的概念命题的概念断言与命题、命题真值表示断言与命题、命题真值表示原子命题和复合命题、命题常元、命题变元原子命题和复合命题、命题常元、命题变元逻辑联结词逻辑联结词 、 、 、 、 命题公式命题公式 公式的归纳定义公式的归纳定义真值表真值表自然语句的形式化自然语句的形式化-8-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v命题命题 (propo

5、sition(proposition或或statement) statement) 命题命题(proposition) ：表示判断的陈述句。表示判断的陈述句。或是真，或是假，但二者不能得兼（排中律）或是真，或是假，但二者不能得兼（排中律） 真、假常被称为真、假常被称为命题的真值命题的真值用大写的英文字母用大写的英文字母T或或“1”表示命题真值是表示命题真值是“真的真的” F或或“0”表示命题的真值是表示命题的真值是“假的假的” -9-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v命题举例命题举例例例4.1雪是白的。雪是白的。2+2=5。2是偶数且是偶数且3也是偶数。也是偶数。陈胜起义那天杭州下

6、雨。陈胜起义那天杭州下雨。大于大于2的偶数均可以分解为两个质数的和。的偶数均可以分解为两个质数的和。火星上有生物。火星上有生物。好痛快啊好痛快啊!您去看电影吗？您去看电影吗？X+Y0。我只给那些不给自己刮胡子的人刮胡子。我只给那些不给自己刮胡子的人刮胡子。我正在说谎。我正在说谎。-10-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v原子命题和复合命题原子命题和复合命题命题常元和变元命题常元和变元命题常元指一个命题常元指一个有确定真值有确定真值的固定命题的固定命题命题变元指一个命题变元指一个未确定真值未确定真值的任意命题，其值在的任意命题，其值在0,1上上变化变化 原子命题：原子命题：一个不能再

7、分解成更简单语句的命题一个不能再分解成更简单语句的命题原子命题是最简单的陈述句原子命题是最简单的陈述句 原子命题通常记为原子命题通常记为p、q、r等小写字母，等小写字母，f表示恒假命题，表示恒假命题，t表示恒真命题表示恒真命题 相对于原子命题的是相对于原子命题的是复合命题复合命题，它是由原子命题通过逻辑，它是由原子命题通过逻辑联结词进行适当的组合而成的联结词进行适当的组合而成的 复合命题的真值不仅依赖于这两个组成它的命题，而且复合命题的真值不仅依赖于这两个组成它的命题，而且还依赖于这个联结词的意义还依赖于这个联结词的意义 -11-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v举例举例p：明天刮

8、风；：明天刮风；q：明天下雨：明天下雨 利用联结词利用联结词“不不”、“或或”、“且且”等可分别等可分别构成新命题：构成新命题： “非非p”：明天不刮风明天不刮风“p或或q” ：明天要么刮风，要么下雨明天要么刮风，要么下雨“p并且并且q”：明天刮风下雨明天刮风下雨-12-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v常用常用5 5个逻辑联结词个逻辑联结词 否定词否定词(negation) ：P，“P不成立不成立”、“并非并非P”否定词是一元运算。否定词是一元运算。否定的是整个命题，并不否定的是整个命题，并不是否定命题中个别的词。是否定命题中个别的词。PP 0110真值表真值表“A A和和B B

9、都大于都大于0 0”的否定：的否定：“A A和和B B都不大于都不大于0 0”“A A和和B B不都大于不都大于0 0”“A A和和B B至少有一个不大于至少有一个不大于0 0”“A A和和B B至少有一个小于等于至少有一个小于等于0 0”“A大于大于0”的否定：的否定： “A不大于不大于0” “A小于等于小于等于0”-13-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v常用常用5 5个逻辑联结词个逻辑联结词合取词合取词(conjunction) ：pq， “p并且并且q”、“p和和q都成立都成立”合取词是二元运算合取词是二元运算只有当只有当p和和q均为真时，均为真时，pq才才是真的，否则，是

10、真的，否则，pq是假的是假的是可交换的是可交换的pqp q 000010100111p:今天是星今天是星期三期三；q:今天上离散数学课；今天上离散数学课；p q：今天是星期三并且上离散数学课；：今天是星期三并且上离散数学课；-14-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v常用常用5 5个逻辑联结词个逻辑联结词析取词析取词(disjunction) ：pq，“p成立或者成立或者q成立成立”、“p或或q”析取词是二元运算析取词是二元运算只有当只有当p和和q的真值均为假时，的真值均为假时， pq才是假的，否则，才是假的，否则， pq总是真的总是真的pqp q 000011101111p:我我上

11、上午上离散数学；午上离散数学；q:我我上上午上午上C 语言；语言；p q：我上午或者离散数：我上午或者离散数学，或者上学，或者上C 语言；语言；p:我我上上午三四节课上离散数学；午三四节课上离散数学；q:我我上上午三四节课上午三四节课上C语言；语言；p q：我：我上上午一二节课要么上午一二节课要么上离散数离散数上上学，要么上学，要么上C 语言语言(不会不会都上都上)；同或同或异或异或-15-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v常用常用5 5个逻辑联结词个逻辑联结词蕴涵词蕴涵词(implication) ：pq，“如如果果p，那么，那么q”、“p蕴涵蕴涵q”、“p是是q的充分条件的充分

12、条件” 从真值表可以看出，只有当前提为从真值表可以看出，只有当前提为真，而结论是假时，真，而结论是假时，pq才是假的才是假的 pqp q 001011100111逆命题：逆命题：qp；否命题：否命题：pq逆否命题：逆否命题：qp命题和逆否命题有相同命题和逆否命题有相同的真值的真值“如果今天是星期五，那么如果今天是星期五，那么2+3=62+3=6”：前提为假，蕴涵命题为真；前提为假，蕴涵命题为真；前提和结论之间可以没有关系，前提和结论之间可以没有关系，称为实质蕴涵称为实质蕴涵p:天晴；天晴； q:我爬山；我爬山；只要天晴，我就爬山：只要天晴，我就爬山： p q 只有天晴，我才爬山：只有天晴，我才

13、爬山： q p “只要下雨，我们队就能赢只要下雨，我们队就能赢”-16-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v常用常用5 5个逻辑联结词个逻辑联结词pqp q 001011100111pqp q 000011101111pqp q 000010100111PP 0110-17-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v常用常用5 5个逻辑联结词个逻辑联结词双向蕴涵词双向蕴涵词(two-way implication) ：p q，“p当且仅当当且仅当q”、“如果如果p，那么那么q；反之亦然；反之亦然”只有当只有当p和和q的真值相同时，的真值相同时，pq才才取真的真值取真的真值 pq与

14、与(pq)(qp)有完全相同有完全相同的真值。的真值。pqp q 001010100111“只有你健康，你才会感到快乐；只有你健康，你才会感到快乐；只有感觉快乐你才健康只有感觉快乐你才健康”-18-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v语句形式化举例语句形式化举例 我和他既是兄弟又是同学我和他既是兄弟又是同学 pq，其中：，其中：p：我和他是兄弟，：我和他是兄弟，q：我和他是同学：我和他是同学 我和他至少有一个要去外地我和他至少有一个要去外地pq，其中：，其中：p：我去外地，：我去外地，q：他去外地：他去外地 狗急跳墙狗急跳墙pq，其中：，其中： p：狗急了，：狗急了，q：狗跳墙：狗跳

15、墙 除非他来，否则我不同他和解除非他来，否则我不同他和解pq，(pq)(pq)，其中：，其中： p：他来，：他来，q：我同他和解：我同他和解-19-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v语句形式化举例语句形式化举例 如果我和他不都是傻子，那么我们俩都不会如果我和他不都是傻子，那么我们俩都不会去自讨没趣去自讨没趣（pq）（rs），其中：），其中： p：我是傻子；：我是傻子；q：他是傻子：他是傻子r：我会去自讨没趣；：我会去自讨没趣；s：他会去自讨没趣：他会去自讨没趣 若天气不下雨或不起雾，则航行比赛将举行若天气不下雨或不起雾，则航行比赛将举行而且救生表演将进行而且救生表演将进行 如果他没

16、来见你，那么他或者是生病了，或如果他没来见你，那么他或者是生病了，或者是不在本地者是不在本地v语句形式化步骤语句形式化步骤n要准确确定原子命题，并将其形式化要准确确定原子命题，并将其形式化n要选用恰当的联结词要选用恰当的联结词要善于识别自然语言中的联结词（有时它们被省略）要善于识别自然语言中的联结词（有时它们被省略）否定词的位置要放准确否定词的位置要放准确n必要时可以进行改述，但要保证表达意思一致必要时可以进行改述，但要保证表达意思一致(逻辑等价逻辑等价)n需要的括号不能省略需要的括号不能省略n要注意语句的形式化未必是唯一的要注意语句的形式化未必是唯一的-21-第第9讲讲 命题与逻辑联结词命题

17、与逻辑联结词v命题公式命题公式 (proposition formula) (proposition formula) 命题公式：命题公式：是一个表达式，它是由命题常元、是一个表达式，它是由命题常元、命题变元、联结词符号和圆括号所组成的一个命题变元、联结词符号和圆括号所组成的一个字符串字符串 归纳定义：归纳定义：命题常元和命题变元是命题公式，也称为原子公式或命题常元和命题变元是命题公式，也称为原子公式或原子原子如果如果A，B是命题公式，那么（是命题公式，那么（A）、（）、（AB）、）、（AB）、（）、（AB）、（）、（AB）也是命题公式）也是命题公式只有有限步引用条款（只有有限步引用条款（1）

18、、（）、（2）所组成的符号串是）所组成的符号串是命题公式命题公式参见教材参见教材P60例例4.8中的正例与反例中的正例与反例 -22-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v简写约定简写约定为了减少圆括号的使用，我们为了减少圆括号的使用，我们约定约定：省掉最外面的括号省掉最外面的括号联结词的结合能力强弱为联结词的结合能力强弱为、（、（、）、）、结合能力平等的联结词从左到右运算结合能力平等的联结词从左到右运算(p) (q (r q) s)p q (r q s)-23-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v语句形式化举例语句形式化举例设设p：a是偶数是偶数 q：a是奇数是奇数 r：a

19、是质数是质数 s：a=2，如何，如何理解下述命题公式理解下述命题公式pq pr s p （r s）rs q（qs）r r （q s）r q s-24-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v指派指派(assignment) (assignment) 设公式设公式A含有含有n个命题变元个命题变元p1， p2 ， pn记为记为A(p1, pn ) 给定这给定这n个变元任意一组确定的值个变元任意一组确定的值（每一变元都（每一变元都有取真或假两种可能），公式有取真或假两种可能），公式A得到一个确定的得到一个确定的值（值（1或或0），我们称这一组确定的值为公式），我们称这一组确定的值为公式A的的一

20、组一组指派指派 常用常用 表示指派，若在某一指派表示指派，若在某一指派 下下A取真的真值，取真的真值，则称则称 弄真弄真A，记为，记为 (A)=1, 反之称反之称 弄假弄假A，记，记为为 (A)=0 -25-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v复合命题公式的真值表复合命题公式的真值表 首先确定在公式中出现的首先确定在公式中出现的命题变元的个数。命题变元的个数。写出公式写出公式A的的所有指派所有指派，一个指派为一行，若有，一个指派为一行，若有n个命题变个命题变元，则有元，则有2n组指派，也就是说真值表有组指派，也就是说真值表有2n+1行。行。确定公式中确定公式中联结词的个数联结词的个数

21、，写出单个联结词的真值，一般讲，写出单个联结词的真值，一般讲，一个联结词对应着一列。一个联结词对应着一列。 例例4.9 (p (qr)的真值表的真值表 (pq)r)p的真值表的真值表 pqrpqr(pq)r(pq)r)p00001100010001010011001100011000111101000011011111111011-26-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v指派举例指派举例使公式使公式A: (pq)r)p为真的指派为真的指派 (A)=11. (pq)r)=1， (p)=1， 2. (pq)r)=0， (p)=0 (r)=0, ( (r r)=1)=11.1. (q)=

22、11.1.1. (r)=01.1.2. (r)=11.2. (q q)=01.2.1. (r)=02.1. (q)=02.2. (q)=1(1,1,0)(1,1,1)(1,0,0)(0,0,1)(0,1,1)-27-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v推理的例子推理的例子 侦探调查了罪案的四个证人。从证人的话侦探得侦探调查了罪案的四个证人。从证人的话侦探得出的结论是：出的结论是：如果男管家说的是真话，那么厨师说的也是真话；如果男管家说的是真话，那么厨师说的也是真话；厨师和园丁说的不可能都是真话；厨师和园丁说的不可能都是真话；园丁和杂役不可能都在说谎园丁和杂役不可能都在说谎如果杂役说真话，那么厨师在说谎如果杂役说真话，那么厨师在说谎p p、q q、r r、s s：分别表示男管家、厨师、园丁、杂：分别表示男管家、厨师、园丁、杂役说的是真话役说的是真话1、pq2、qr3、rs4、sq哪些指派使这四个命题哪些指派使这四个命题公式同时为真？公式同时为真？-28-第第9讲讲 命题与逻辑联结词命题与逻辑联结词v本讲小结本讲小结主要内容主要内容命题的概念：命题的概念：什么是命题、命题的真值什么是命题、命题的真值五个主要的五个主要的逻辑联结词逻辑联结词命题公式的概念、命题公式的命题公式的概念、