离散数学教案课件.ppt

1、 1第第1 1章章 命题逻辑命题逻辑q 数理逻辑数理逻辑：是用数学方法来研究推理的形式结构和推理规律：是用数学方法来研究推理的形式结构和推理规律 的数学学科。的数学学科。数理逻辑近年来发展特别迅速，主要原因是这门学科对于数理逻辑近年来发展特别迅速，主要原因是这门学科对于数学其它分支如集合论、数论、代数、拓扑学等的发展有重数学其它分支如集合论、数论、代数、拓扑学等的发展有重大的影响，特别是对新近形成的计算机科学的发展起了推动大的影响，特别是对新近形成的计算机科学的发展起了推动作用。反过来，其他学科的发展也推动了数理逻辑的发展。作用。反过来，其他学科的发展也推动了数理逻辑的发展。q 本书介绍了数理

2、逻辑的两个最基本、也是最重要的部分：命本书介绍了数理逻辑的两个最基本、也是最重要的部分：命题逻辑和谓词逻辑。本章首先介绍命题逻辑。题逻辑和谓词逻辑。本章首先介绍命题逻辑。命题逻辑命题逻辑是研究命题如何通过一些逻辑连接词构成更复杂的是研究命题如何通过一些逻辑连接词构成更复杂的命题以及逻辑推理的方法。命题以及逻辑推理的方法。21.1 1.1 命题符号化与联结词命题符号化与联结词q数理逻辑研究的数理逻辑研究的中心问题中心问题是是推理推理。q推理的推理的前提前提和和结论结论都是都是表达判断表达判断的的陈述句陈述句。q表达判断的陈述句构成了推理的表达判断的陈述句构成了推理的基本单位基本单位。3q 称能判

3、断真假的陈述句为称能判断真假的陈述句为命题。命题。(判断结果惟一的陈述句)q 作为命题的陈述句所表达得的判断结果称为命题的作为命题的陈述句所表达得的判断结果称为命题的真值真值。q 真值只取两个：真值只取两个：真与假真与假。q 真值为真的命题称为真值为真的命题称为真命题真命题。q 真值为假的命题称为真值为假的命题称为假命题假命题。q 命题又称为具有唯一真值的陈述句。命题又称为具有唯一真值的陈述句。注意注意:感叹句、祈使句、疑问句都不是命题感叹句、祈使句、疑问句都不是命题陈述句中的悖论以及判断结果不惟一确定的也不是命题陈述句中的悖论以及判断结果不惟一确定的也不是命题 说说明明一、命题的概念一、命题

4、的概念 4(1)(1)2 2是素数。是素数。(2)(2)雪是黑色的。雪是黑色的。(3)(3)2+3=5 2+3=5。(4)(4)明年明年1010月月1 1日是晴天。日是晴天。(5)(5)3 3能被能被2 2整除。整除。(6)(6)这朵花多好看啊！这朵花多好看啊！(7)(7)明天下午有会吗？明天下午有会吗？(8)(8)请关上门！请关上门！(9)(9)x+yx+y5 5。(10)(10)地球外的星球上也有人地球外的星球上也有人(11)我正在说谎话.例例1.1.1 1 判断下列句子是否为命题。判断下列句子是否为命题。(1)(1)是，真命题是，真命题(2)(2)是，假命题是，假命题(3)是，真命题是，

5、真命题(4)(4)是，真值客观存在是，真值客观存在(5)是，假命题是，假命题(6)不是，感叹句不是，感叹句(7)不是，疑问句不是，疑问句(8)不是，祈使句不是，祈使句(9)不是，真值不唯一不是，真值不唯一(10)(10)是，是，真值客观存在真值客观存在(11)(11)悖论悖论 5二、命题的符号化二、命题的符号化q 用小写英文字母 p,q,r ,pi ,qi ,ri 表示命题q 用“1”表示真，用“0”表示假 q 命题符号化命题符号化：用表示命题的符号放在该命题的前面。：用表示命题的符号放在该命题的前面。r：充分大的偶数等于两个充分大的偶数等于两个素数之和。素数之和。s：今天是星期二。今天是星期

6、二。是无理数2p：4 4是素数。是素数。q：q 不能被分解成更简单句子的命题为不能被分解成更简单句子的命题为简单命题简单命题或或原子命题原子命题。（一）、简单命题（一）、简单命题 6p简单命题的真值是唯一确定的，所以也称简单命题简单命题的真值是唯一确定的，所以也称简单命题为为命题常项命题常项或或命题常元命题常元。p称真值可以变化的简单陈述句为称真值可以变化的简单陈述句为命题变项命题变项或或命题变命题变元元 也用也用p,q,r,表示命题变项。表示命题变项。p当当p,q,r,表示命题变项时，它们就成了取值表示命题变项时，它们就成了取值0或或1的的变项，因而变项，因而命题变项已不是命题命题变项已不是

7、命题。p这样一来，这样一来，p,q,r,既可以表示命题常项，也可以表既可以表示命题常项，也可以表示命题变项。在使用中，需要由上下文确定它们表示命题变项。在使用中，需要由上下文确定它们表示的是常项还是变项。示的是常项还是变项。7 由简单命题通过联结词联结而成的命题，称这样由简单命题通过联结词联结而成的命题，称这样的命题为的命题为复合命题复合命题。（二）、复合命题（二）、复合命题例例1.2（1）3不是偶数；不是偶数；（2）2是素数和偶数；是素数和偶数；（3）林芳学过英语或日语；）林芳学过英语或日语；（4）如果角）如果角A和角和角B是对顶角，则角是对顶角，则角A等于角等于角B；8q 定义定义1.11

8、.1（否定联结词）（否定联结词）设设p为命题，复合命题为命题，复合命题“非非p”(”(或或“p的否定的否定”)”)称为称为p的的否否定式定式,记作记作p，符号符号称作称作否定联结词否定联结词，并规定，并规定p为真为真当且仅当当且仅当p为假为假。例如例如：p：3是偶数是偶数。p：3不是偶数不是偶数。（三）、联结词（三）、联结词pp1001 9q 定义定义1.21.2（合取联结词）（合取联结词）设设p,q为二命题，复合命题为二命题，复合命题“p并且并且q”(或或“p与与q”)称为称为p与与q的的合取式合取式，记作，记作pq，称作称作合取联结词合取联结词，并规定，并规定pq为真当且仅当为真当且仅当p

9、与与q同时为真。同时为真。使用合取联结词时要注意的两点：使用合取联结词时要注意的两点：1 1）描述合取式的灵活性与多样性。）描述合取式的灵活性与多样性。自然语言中的自然语言中的“既既又又”、“不但不但而且而且”、“虽然虽然但是但是”、“一面一面一面一面”等联结词都等联结词都可以符号化为可以符号化为。2 2）分清简单命题与复合命题。）分清简单命题与复合命题。不要见到不要见到“与与”或或“和和”就使用联结词就使用联结词。pqpq1 11 11 11 10 00 00 01 10 00 000 0 10例1.3 将下列命题符号化将下列命题符号化(1)(1)李平既聪明又用功。李平既聪明又用功。(2)(

10、2)李平虽然聪明，但不用功。李平虽然聪明，但不用功。(3)(3)李平不仅用功而且聪明。李平不仅用功而且聪明。(4)(4)李平不是不聪明，而是不用功。李平不是不聪明，而是不用功。p:p:李平聪明。李平聪明。q:q:李平李平用功。用功。(1)pq(1)pq(2)pq(2)pq(3)qp(3)qp(4)(4)（p）q解题要点：解题要点：正确理解命题含义。正确理解命题含义。找出原子命题并符号化。找出原子命题并符号化。选择恰当的联结词。选择恰当的联结词。11q定义定义1.31.3（析取联结词析取联结词）设设p p，q q为二命题，复合命题为二命题，复合命题“p p或或q q”称作称作p p与与q q的的

11、析析取式取式，记作，记作p pq q，称作称作析取联结词析取联结词，并规定，并规定p pq q为真当且仅当为真当且仅当p p与与q q中至少一个为真。中至少一个为真。自然语言中的自然语言中的“或或”具有二义性，用它联结的命具有二义性，用它联结的命题有时具有相容性，有时具有排斥性，对应的联题有时具有相容性，有时具有排斥性，对应的联结词分别称为结词分别称为相容或相容或和排斥或排斥或(排异或排异或)。说说明明pqpq1 11 11 11 10 01 10 01 11 10 000 0 12数理逻辑中，数理逻辑中，pqpq表示相容或，即允许表示相容或，即允许p p与与q q同时为真。同时为真。说说明明

12、例如例如：王燕学过英语或法语王燕学过英语或法语。pqpq派小王或小李中的一人去开会。派小王或小李中的一人去开会。(rs)(rsrs)(rs)自然语言中的自然语言中的“或或”具有二义性，用它联结的命题具有二义性，用它联结的命题有时具有相容性，有时具有排斥性，对应的联结词有时具有相容性，有时具有排斥性，对应的联结词分别称为相容或分别称为相容或和排斥或排斥或(排异或排异或)。13例如例如 将下列命题符号化将下列命题符号化 (1)(1)张晓静爱唱歌或爱听音乐。张晓静爱唱歌或爱听音乐。(2)(2)张晓静只能挑选张晓静只能挑选202202或或203203房间。房间。(3)(3)张晓静是江西人或安徽人。张晓

13、静是江西人或安徽人。(1)(1)设设 p p：张晓静爱唱歌，张晓静爱唱歌，q q：张晓静爱听音乐。张晓静爱听音乐。相容或，符号化为相容或，符号化为 p pq q(2)(2)设设t t：张晓静挑选张晓静挑选202202房间，房间，u u：张晓静挑选张晓静挑选203203房间。房间。排斥或，符号化为：排斥或，符号化为：(t tu u)()(t tu u)(3)(3)设设r r：张晓静是江西人，张晓静是江西人，s s：张晓静是安徽人。张晓静是安徽人。排斥或，符号化为：排斥或，符号化为：(rs)(rs)rs)(rs)14q定义定义1.41.4（蕴涵联结词）（蕴涵联结词）设设p p，q q为二命题，复合

14、命题为二命题，复合命题“如果如果p p，则则q q”称作称作p p与与q q的的蕴涵式蕴涵式，记作，记作p pq q，并称并称p p是蕴涵式的是蕴涵式的前件前件，q q为蕴涵式的为蕴涵式的后件后件，称作称作蕴涵联结词蕴涵联结词,并规定并规定p pq q为假当且仅当为假当且仅当p p为真为真q q为假为假。说说明明q pq的逻辑关系表示的逻辑关系表示q是是p的必要条件。的必要条件。q q是是p的必要条件有许多不同的叙述方式的必要条件有许多不同的叙述方式 只要只要p，就就q 因为因为p，所以所以q p仅当仅当q只有只有q才才p除非除非q才才p除非除非q，否则非否则非p pqp q1 11 11 1

15、1 10 00 00 01 11 10 001 1 15例例1.41.4 将下列命题符号化，并指出其真值将下列命题符号化，并指出其真值 (1)(1)只要不下雨，我就骑自行车上班。只要不下雨，我就骑自行车上班。(2)(2)只有不下雨，我才骑自行车上班。只有不下雨，我才骑自行车上班。(3)(3)如果如果3+33+3=6=6，则太阳从东方升起。，则太阳从东方升起。(4)(4)如果如果3+363+36，则太阳从东方升起。，则太阳从东方升起。(5)(5)如果如果3+33+3=6=6，则太阳从西方升起。，则太阳从西方升起。(6)(6)如果如果3+363+36，则太阳从西方升起。，则太阳从西方升起。解：令解

16、：令p：天天下雨下雨。q：我骑自行车上班我骑自行车上班。r:3+3=6。s：太阳从东方升起。：太阳从东方升起。t：太阳从西方升起。：太阳从西方升起。(1)pq;(2)q p;(3)rs;(4)rs;(5)rt;16q定义定义1.51.5（等价联结词）（等价联结词）设设p p，q q为二命题，复合命题为二命题，复合命题“p p当且仅当当且仅当q q”称作称作p p与与q q的的等价式等价式，记作，记作p pq q，称作称作等价联结词等价联结词，并规定并规定p pq q为真当且仅当为真当且仅当p p与与q q同时为真或同时为同时为真或同时为假假。pqp q1 11 11 11 10 00 00 0

17、1 10 00 001 1 17例例1.5 1.5 将下列命题符号化将下列命题符号化(1)(1)2+32+35 5当且仅当当且仅当3 3是奇数。是奇数。(2)(2)2+32+35 5当且仅当当且仅当3 3不是奇数。不是奇数。(3)(3)2+352+35当且仅当当且仅当3 3是奇数。是奇数。(4)(4)2+352+35当且仅当当且仅当3 3不是奇数。不是奇数。(5)(5)两圆两圆A A，B B的面积相等当且仅当它们的半径相等。的面积相等当且仅当它们的半径相等。设设 p p ：2+35，q q：3是奇数是奇数。符号化为符号化为 p pq q，p pq q，pq，pq，设设 p p：两圆两圆A A，

18、B B的面积相等的面积相等，q q：两圆两圆A A，B B的半径相等的半径相等。符号化为符号化为 p pq q，真值为真值为1 1。18关于联结词的说明关于联结词的说明q 多次使用联结词集中的联结词，可以组成更为复杂的复多次使用联结词集中的联结词，可以组成更为复杂的复合命题。合命题。q 本书规定的联结词优先顺序为：本书规定的联结词优先顺序为：()()，对于同一优先级的联结词，先出现者先运算。，对于同一优先级的联结词，先出现者先运算。19习题：命题符号化习题：命题符号化(1)(1)我和他既是兄弟又是同学我和他既是兄弟又是同学 p p：我和他是兄弟，我和他是兄弟，q q：我和他是同学。我和他是同学

19、。故命题可符号化为：故命题可符号化为：pqpq。(2)(2)张三或李四都可以做这件事。张三或李四都可以做这件事。p p：张三可以做这件事。张三可以做这件事。q q：李四可以做这件事。李四可以做这件事。故命题可符号化为：故命题可符号化为：pqpq。(3)(3)仅当我有时间且天不下雨，我将去镇上。仅当我有时间且天不下雨，我将去镇上。对于对于“仅当仅当”，实质上是，实质上是“当当”的逆命题。的逆命题。“当当A A则则B”B”是是ABAB，而而“仅当仅当A A则则B”B”是是BABA。p p：我有时间。我有时间。q q：天不下雨。天不下雨。r r：我将去镇上。我将去镇上。故命题可符号化为：故命题可符号

20、化为：r(pqr(pq)。20(4)(4)张刚总是在图书馆看书，除非图书馆不开门或张刚生病。张刚总是在图书馆看书，除非图书馆不开门或张刚生病。对于对于“除非除非”，只要记住，只要记住，“除非除非”是条件。是条件。p p：张刚在图书馆看书，张刚在图书馆看书，q q：图书馆不开门，图书馆不开门，r r：张刚生病。张刚生病。故命题可符号化为：故命题可符号化为：(qr)pqr)p。(5)(5)风雨无阻，我去上学。风雨无阻，我去上学。可理解为可理解为“不管是否刮风、是否下雨，我都去上学不管是否刮风、是否下雨，我都去上学”。p p：天刮风，天刮风，q q：天下雨，天下雨，r r：我去上学。我去上学。故命题

21、可符号化为：故命题可符号化为：(pqr)(pqr)(pqr)(pqrpqr)(pqr)(pqr)(pqr)或或(pqr)(pqr)(pqr)(pqrpqr)(pqr)(pqr)(pqr)理解为理解为“四种情况必居其一四种情况必居其一,而每种情况下我都去上学而每种情况下我都去上学”21命题符号化的要点命题符号化的要点q要准确确定原子命题，并将其形式化要准确确定原子命题，并将其形式化。q要选用恰当的联结词，尤其要善于识别自然语言要选用恰当的联结词，尤其要善于识别自然语言中的联结词（有时它们被省略）中的联结词（有时它们被省略）。q否定词的位置要放准确。否定词的位置要放准确。q需要的括号不能省略，而可以省略的括号，在需需要的括号不能省略，而可以省略的括号，在需要提高公式可读性时亦可不省略要提高公式可读性时亦可不省略。q要注意的是要注意的是,语句的形式化未必是唯一的。语句的形式化未必是唯一的。22q 一、命题的概念一、命题的概念q 二、命题的符号化二、命题的符号化 （一）简单命题（一）简单命题 （二）复合命题（二）复合命题 （三）联结词（三）联结词 否定、合取、析取、蕴含、等价联结词否定、合取、析取、蕴含、等价联结词小结小结 23练习：练习：q P P：31-3231-32q 1.1(10-151.1(10-15）若是命题，将他们符号化。）若是命题，将他们符号化。q 1.51.5