《离散数学第4章讲义-2》由会员分享，可在线阅读，更多相关《离散数学第4章讲义-2（125页珍藏版）》请在金锄头文库上搜索。
1、离散数学Discrete Mathematics上海金融学院信息管理学院上海金融学院信息管理学院 元如林元如林第 2 页第 2 页*上海金融学院信息管理学院 元如林第五章 数理逻辑（mathematical logic） 第 3 页第 3 页*上海金融学院信息管理学院 元如林逻辑学: 关于思维形式及其规律的科学形式逻辑: 研究思维形式结构及其规律和规则 数理逻辑: 用数学方法研究形式逻辑和数学基础 辩证逻辑: 研究辩证思维形式及其规律第 4 页第 4 页*上海金融学院信息管理学院 元如林思维: 人对客观世界的理性认识(或反映)，即人对事物的间接的、概括的映射过程，是在感性认识之后，对感性材料进
2、行比较、分析、综合、抽象、概括等去粗取精、去伪存真的活动。第 5 页第 5 页*上海金融学院信息管理学院 元如林思维的内容、思维的形式、思维形式的结构概念 思维的形式：思维形式的结构：判断 推理 S是P 所有S是M；所有M是P；所以，所有S是P；第 6 页第 6 页*上海金融学院信息管理学院 元如林思维的基本规律：同一律、矛盾律、排中律、充足理由律等认识客观现实的方法：下定义、划分、观察、实验、假说、论证第 7 页第 7 页*上海金融学院信息管理学院 元如林概念： 内涵、外延对象（属性、共同属性、特有属性）概念的种类、概念间的关系、概念的推演、划分、定义语言、文字 字 词第 8 页第 8 页*
3、上海金融学院信息管理学院 元如林判断：对思维对象有所肯定或有所否定的思想语句 命题直言判断：关系判断：联言判断：选言判断：假言判断：负判断： 模态判断 时态判断 第 9 页第 9 页*上海金融学院信息管理学院 元如林推理： 演绎推理 归纳推理 类比 假说演绎：直接推理、简单判断推理（三段论、关系推理）复合判断推理（联言推理、选言推理、假言推理、二难推理、模态推理等） 归纳：完全归纳推理、不完全归纳推理、科学归纳推理、求因果联系、提炼经验材料第 10 页第 10 页*上海金融学院信息管理学院 元如林推理： 演绎推理 归纳推理 类推 假说类推：根据同类的已知情况而推测其未知情况假说：对事物存在的原
4、因或规律作出有根据的假定说明第 11 页第 11 页*上海金融学院信息管理学院 元如林逻辑思维的规律：同一律：在正确的思维过程中，所运用的同一概念必须保 持同一意义。（保持思维的准确性）矛盾律：在同一时间、同一关系上，不能对同一对象作出 不同的判断。 （保持思维的一贯性）排中律：在同一时间、同一关系上，对关于同一事物的两 个矛盾论断，必须明确选择其一。 （保持思维的明确性）充足理由律：任何正确的思想，都应该有真实性已经在人 们的实践中被证实了的其它思想作根据 （保持思维的根据性 ）第 12 页第 12 页*上海金融学院信息管理学院 元如林论证：根据某个或某些判断的真实性，来判定另一 判断的真实
5、性的一种思维过程。 证明的种类：演绎证明、归纳证明、直接证明、间接证明（反证法） 反驳的方法：直接反驳、归纳反驳、归谬反驳 论证的规则： 论题：1、清楚明确；2、首尾一贯论据：1、已确知为真；2、其真实性不依靠论题来证明论证方式：必须遵守正确的推理规则第 13 页第 13 页*上海金融学院信息管理学院 元如林数理逻辑数理逻辑（mathematical logic） 是用数学方法研究人类推理过程的一门数学学科。 又称符号逻辑、现代逻辑。 其显著特征是符号化和形式化，即把逻辑所涉 及的“概念、判断、推理”用符号来表示，用公理体 系来刻划, 并基于符号串形式的演算来描述推理过 程的一般规律。 逻辑演
6、算四个分支： 公理集合论、证明论、模型论和递归论。第 14 页第 14 页*上海金融学院信息管理学院 元如林5.1 命题及联结词 一、命题（propositions or statements） 命题：能判断真假的陈述句。例如，“北京是中国的首都。” 命题 真（true） “长春是中国最大的城市。” 命题，假（false）“请关门!” 不是命题“你去哪里?” 不是命题。 第 15 页第 15 页*上海金融学院信息管理学院 元如林5.1 命题及联结词 一、命题（propositions or statements） 命题：能判断真假的陈述句。例如，“北京是中国的首都。” 命题 真（true） “
7、长春是中国最大的城市。” 命题，假（false）“请关门!” 不是命题“你去哪里?” 不是命题。 第 16 页第 16 页*上海金融学院信息管理学院 元如林命题的真值：命题的判断结果 如果一个命题是真的，就说它的真值是1；如果一个命题是假的，就说它的真值是0。 用1代表一个抽象的真命题， 用0代表一个抽象的假命题。 1、T、真、（true） 0、F、假、（false） 第 17 页第 17 页*上海金融学院信息管理学院 元如林命题的标示符: 用大写英文字母P，Q，P1， P2，表示命题。表示命题的符号称为命题的标示符。命题常元：当命题标示符标示一个具体命题时， 称为命题常元。（proposit
8、ion constants） 是命题命题变元：当命题标示符标示一组命题中的任一 个时，称为命题变元。 （proposition variable）不是命题第 18 页第 18 页*上海金融学院信息管理学院 元如林例1：分析下列自然语句哪些是命题1、今天我休息。是命题2、昨天下雨。3、雪是白色的。4、我是学生。5、6不是偶数。6、今天我休息。7、你好吗？8、请坐下。9、真好啊！不是命 题疑问句祈使句感叹句第 19 页第 19 页*上海金融学院信息管理学院 元如林例2：分析下列自然语句哪些是命题1、火星上有生命 。是命题2、1+1=10。3、雪是黑色的。4、这盘菜太咸。5、x1。6、我正在说谎。不
9、是命 题模糊逻辑与x有关悖论不是命 题是命题不是命 题不是命 题第 20 页第 20 页*上海金融学院信息管理学院 元如林二、联结词第 21 页第 21 页*上海金融学院信息管理学院 元如林定义5.1.1设P是一个命题，定义命题P ，称为P 的否定式，称符号为否定联结词并规定P 是真的当且仅当P是假的。例, P： 上海是一个城市。P：上海不是一个城市。“非” “不” “并非”（not all） ，1、否定（negation ）P 读作非P。p10 p10第 22 页第 22 页*上海金融学院信息管理学院 元如林定义5.1.2设P，Q是两个命题，命题 “P并且Q”称 为P，Q的合取，记以PQ，读
10、作P且Q。 规 定PQ是真的当且仅当P和Q都是真的。2、合取（ conjunction ）Q10P Q00P0110 010 1第 23 页第 23 页*上海金融学院信息管理学院 元如林例如，P：22=5，Q：雪是黑的，PQ：22=5并且雪是黑的。 例如，P：今天下雨，Q：今天刮风， P Q：今天下雨又刮风。 第 24 页第 24 页*上海金融学院信息管理学院 元如林虽然 ，但是。不仅 ，而且。既 ，也。 一面 ，一面。“与”“和”“并且”（and ）第 25 页第 25 页*上海金融学院信息管理学院 元如林定义5.1.3设P，Q是两个命题，命题 “P或者Q”称 为P，Q的析取，记以PQ，读作
11、P或Q。 规 定PQ是真的当且仅当P，Q中至少有一个 是真的。3、析取（disjunction）Q10P Q01P0110 011 1“或”（or ）第 26 页第 26 页*上海金融学院信息管理学院 元如林定义5.1.3例如，P：今天下雨，Q：今天刮风， PQ：今天下雨或者刮风。 例如，P：22=5，Q：雪是黑的，P Q：22=5或者雪是黑的。 第 27 页第 27 页*上海金融学院信息管理学院 元如林例如，P：小李爱唱歌。Q：小李爱跳舞。 PQ：小李爱唱歌或跳舞。例如，P：小李是北京人。Q：小李是上海人。 小李是北京人或上海人。 PQ： 可兼或不可兼或、异或小李是北京人或上海人。 (P Q
12、 ) 第 28 页第 28 页*上海金融学院信息管理学院 元如林定义5.1.4设P，Q是两个命题，命题 “如果P，则Q”称为P蕴含Q，记以PQ。 规定，PQ是假的当且仅当P是真的而Q是假的。4、蕴含（implication)Q10P Q11P0110 010 1P 称为前件，Q称为后件。第 29 页第 29 页*上海金融学院信息管理学院 元如林例如，P：f(x)是可微的，Q：f(x)是连续的，PQ： 若f(x)是可微的，则f(x)是连续的。 例如，P：22=5，Q：雪是黑的，P Q：若22=5，则雪是黑的。 第 30 页第 30 页*上海金融学院信息管理学院 元如林如果 ，则。 P Q （if
13、then）只要 ，就。 P Q因为 ，所以。 P Q只有 ，才。 Q P除非 ，才。 Q P除非 ，否则不。 Q P， P QP 是Q的充分条件： P QP 是Q的必要条件： Q P第 31 页第 31 页*上海金融学院信息管理学院 元如林例： P：我努力学习习。 Q：我会通过过考试试。 只要我努力学习习 ，我就会通过过考试试。 P Q 如果我努力学习习 ，我就会通过过考试试。 P Q 只有努力学习习 ，我才会通过过考试试。 Q P 除非努力学习习 ，我才会通过过考试试。 Q P除非努力学习习 ，否则我不会通过过考试试。Q P， P Q第 32 页第 32 页*上海金融学院信息管理学院 元如林
14、例：如果明天不下雨，我就去市图书馆。 P：明天不下雨。Q：我去市图书馆。 PQ：如果明天不下雨，我就去市图书馆。 P： 0 明天下雨。 Q： 1 我去市图书馆。P： 0 明天下雨。 Q： 0 我没有去市图书馆。P： 1 明天不下雨。 Q： 1 我去市图书馆。P： 1 明天不下雨。 Q： 0 我没有去市图书馆。第 33 页第 33 页*上海金融学院信息管理学院 元如林定义5.1.5设P，Q是两个命题，命题 “P当且仅当 Q”称为P等价Q，记以PQ。规定，PQ 是真的当且仅当P，Q或者都是真的，或者 都是假的。5、等价(two-way-implication)Q10P Q10P0110 010 1“充分必要”“当且仅当”“If and only if”iff第 34 页第 34 页*上海金融学院信息管理学院 元如林例如， P ： a2+b2=a2， Q： b=0， PQ： a2+b2=a2当且仅当b=0 。第 35 页第 35 页*上海金
