离散数学教案课件

1、第1章 命题逻辑数理逻辑：是用数学方法来研究推理的形式结构和推理规律 的数学学科。 数理逻辑近年来发展特别迅速，主要原因是这门学科对于数学其它分支如集合论、数论、代数、拓扑学等的发展有重大的影响，特别是对新近形成的计算机科学的发展起了推动作用。反过来，其他学科的发展也推动了数理逻辑的发展。本书介绍了数理逻辑的两个最基本、也是最重要的部分：命题逻辑和谓词逻辑。本章首先介绍命题逻辑。 命题逻辑是研究命题如何通过一些逻辑连接词构成更复杂的命题以及逻辑推理的方法。1.1 命题符号化与联结词数理逻辑研究的中心问题是推理。推理的前提和结论都是表达判断的陈述句。表达判断的陈述句构成了推理的基本单位。称能判断

2、真假的陈述句为命题。(判断结果惟一的陈述句)作为命题的陈述句所表达得的判断结果称为命题的真值。真值只取两个：真与假。真值为真的命题称为真命题。真值为假的命题称为假命题。命题又称为具有唯一真值的陈述句。注意: 感叹句、祈使句、疑问句都不是命题陈述句中的悖论以及判断结果不惟一确定的也不是命题 说明一、命题的概念2是素数。雪是黑色的。2+3=5 。明年10月1日是晴天。3能被2整除。这朵花多好看啊！明天下午有会吗？请关上门！x+y5。 地球外的星球上也有人 我正在说谎话.例1.1 判断下列句子是否为命题。 是，真命题是，假命题是，真命题是，真值客观存在是，假命题不是，感叹句不是，疑问句不是，祈使句不

3、是，真值不唯一是，真值客观存在 悖论二、命题的符号化用小写英文字母 p , q , r , pi , qi ,ri 表示命题用“1”表示真，用“0”表示假 命题符号化：用表示命题的符号放在该命题的前面。r：充分大的偶数等于两个素数之和。s：今天是星期二。p：4是素数。q：不能被分解成更简单句子的命题为简单命题或原子命题。（一）、简单命题简单命题的真值是唯一确定的，所以也称简单命题为命题常项或命题常元。称真值可以变化的简单陈述句为命题变项或命题变元 也用p,q,r,表示命题变项。当p,q,r,表示命题变项时，它们就成了取值0或1的变项，因而命题变项已不是命题。这样一来，p,q,r,既可以表示命题

4、常项，也可以表示命题变项。在使用中，需要由上下文确定它们表示的是常项还是变项。 由简单命题通过联结词联结而成的命题，称这样的命题为复合命题。 （二）、复合命题例1.2 （1）3不是偶数；（2）2是素数和偶数；（3）林芳学过英语或日语；（4）如果角A和角B是对顶角，则角A等于角B ；定义1.1（否定联结词） 设p为命题，复合命题“非p”(或“p的否定”)称为p的否定式,记作p，符号称作否定联结词，并规定p为真当且仅当p为假。 例如：p： 3是偶数。 p： 3不是偶数。（三）、联结词pp1001定义1.2（合取联结词） 设p ,q为二命题，复合命题“p并且q”(或“p与q”)称为p与q的合取式，记

5、作pq，称作合取联结词，并规定pq为真当且仅当p与q同时为真。使用合取联结词时要注意的两点：1）描述合取式的灵活性与多样性。自然语言中的“既又”、“不但而且”、“虽然但是”、“一面一面”等联结词都可以符号化为。2）分清简单命题与复合命题。不要见到“与”或“和”就使用联结词。 pqpq111100010000例1.3 将下列命题符号化李平既聪明又用功。李平虽然聪明，但不用功。李平不仅用功而且聪明。李平不是不聪明，而是不用功。p: 李平聪明。q:李平用功。(1)pq(2)pq(3)qp(4) （p） q解题要点：正确理解命题含义。找出原子命题并符号化。选择恰当的联结词。 定义1.3（析取联结词）

6、设p，q为二命题，复合命题“p或q”称作p与q的析取式，记作pq，称作析取联结词，并规定pq为真当且仅当p与q中至少一个为真。 自然语言中的“或”具有二义性，用它联结的命题有时具有相容性，有时具有排斥性，对应的联结词分别称为相容或和排斥或(排异或)。 说明pqpq111101011000数理逻辑中，pq表示相容或，即允许p与q同时为真。说明例如：王燕学过英语或法语。 pq派小王或小李中的一人去开会。 (rs)(rs)自然语言中的“或”具有二义性，用它联结的命题有时具有相容性，有时具有排斥性，对应的联结词分别称为相容或和排斥或(排异或)。 例如 将下列命题符号化 张晓静爱唱歌或爱听音乐。张晓静只

7、能挑选202或203房间。张晓静是江西人或安徽人。设 p：张晓静爱唱歌，q：张晓静爱听音乐。相容或，符号化为 pq设t：张晓静挑选202房间，u：张晓静挑选203房间。排斥或，符号化为：(tu)(tu)设r：张晓静是江西人，s：张晓静是安徽人。排斥或，符号化为：(rs)(rs)定义1.4（蕴涵联结词） 设p，q为二命题，复合命题“如果p，则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件，称作蕴涵联结词,并规定pq为假当且仅当p为真q为假。 说明pq的逻辑关系表示q是p的必要条件。 q是p的必要条件有许多不同的叙述方式 只要p，就q 因为p，所以qp仅当q只有q才p除非

8、q才p除非q，否则非p pqp q111100011001例1.4 将下列命题符号化，并指出其真值 只要不下雨，我就骑自行车上班。只有不下雨，我才骑自行车上班。如果3+3=6，则太阳从东方升起。如果3+36，则太阳从东方升起。如果3+3=6，则太阳从西方升起。如果3+36，则太阳从西方升起。解：令p：天下雨。q：我骑自行车上班。 r: 3+3=6 。s：太阳从东方升起。t：太阳从西方升起。(1)pq ; (2)q p; (3) rs ; (4) rs ; (5) rt;定义1.5（等价联结词） 设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq， 称作等价联结词，并规定pq

9、为真当且仅当p与q同时为真或同时为假。pqp q111100010001例1.5 将下列命题符号化2+35当且仅当3是奇数。2+35当且仅当3不是奇数。2+35当且仅当3是奇数。2+35当且仅当3不是奇数。两圆A，B的面积相等当且仅当它们的半径相等。设 p ：2+35 ，q： 3是奇数。符号化为 pq，pq， pq，pq，设 p：两圆A，B的面积相等， q：两圆A，B的半径相等。符号化为 pq，真值为1。关于联结词的说明多次使用联结词集中的联结词，可以组成更为复杂的复合命题。 本书规定的联结词优先顺序为：( )， ，对于同一优先级的联结词，先出现者先运算。 习题：命题符号化(1)我和他既是兄弟

10、又是同学 p：我和他是兄弟，q：我和他是同学。故命题可符号化为： pq。(2)张三或李四都可以做这件事。 p：张三可以做这件事。 q：李四可以做这件事。故命题可符号化为：pq。 (3)仅当我有时间且天不下雨，我将去镇上。对于“仅当”，实质上是“当”的逆命题。“当A则B”是AB，而“仅当A则B”是BA。 p：我有时间。 q：天不下雨。 r：我将去镇上。故命题可符号化为：r(pq)。 (4)张刚总是在图书馆看书，除非图书馆不开门或张刚生病。 对于“除非”，只要记住，“除非”是条件。p：张刚在图书馆看书，q：图书馆不开门，r：张刚生病。 故命题可符号化为：(qr)p。 (5)风雨无阻，我去上学。可理解为“不管是否刮风、是否下雨，我都去上学”。 p：天刮风，q：天下雨，r：我去上学。故命题可符号化为：(pqr)(pqr)(pqr)(pqr)或(pqr)(pqr)(pqr)(pqr) 理解为“四种情况必居其一,而每种情况下我都去上学” 命题符号化的要点要准确确定原子命题，并将其形式化。要选用恰当的联结词，尤其要善于识别自然语言中的联结词（有时