第一章 命题逻辑(1.1-1.2).ppt

离散数学 李瑞红 软件学院 课程性质 离散数学（又称计算机数学）是理工各专业的专业必修课，是数学中涉及面非常广泛的一门学科。它不仅是计算机科学中重要的基础理论之一，是学习后续计算机专业课程不可缺少的数学工具，也是培养学生抽象思维能力和逻辑推理能力的核心课程。 课程目标 离散数学是以研究离散量的结构和相互之间的关系为主要目标，其研究对象一般为：有限或可数个元素（例如：自然数、整数、真假值、有限个结点等），而离散性也是计算机科学的显著特点。 与其他课程的关系 离散数学与计算机科学的其他课程，如：数据结构、操作系统、编译原理、算法分析、人工智能等有密切关系。它是这些课程的先导和基础课程。 教材与参考书 离散数学 上海科学技术文献出版社，1982，左孝凌等编著 离散数学 高等教育出版社，2008 屈婉玲等编著 课程内容 本课程根据大纲的内容和相关独立性可分为四大部分： 第一部分 数理逻辑 包括命题逻辑；谓词逻辑 第二部分 集合论 包括集合与关系；函数 第三部分 代数系统 包括代数结构；格与布尔代数 第四部分 图论 学习方法 本课程有两个特点： （1）[定义]、定理多 本课程内容=[定义]+定理+例题 （2）课外作业比较多 学习方法 为了学好这门课程，特提出三点要求： （1）弄懂[定义]、定理，弄懂例题，加深对[定义]、定理的理解； （2）在复习基础上，做好课外作业。同学之间可以讨论，但要弄懂弄通。 学习方法 最后，做两点说明： （1）考试内容以课堂上讲的内容为范围； （2）每次课后布置作业。希望大家认真完成。 第一篇 数理逻辑 逻辑学：研究思维形式及思维规律的科学。 辨证逻辑：研究事物发展的规律。 形式逻辑：对思维的形式结构和规律进行研究。 数理逻辑：是用数学的方法研究概念、判断和推理的科学，属于形式逻辑。 第一章 命题逻辑 1-1 命题及其表示法 1-2 联结词 1-3 命题公式与翻译 1-4 真值表与等价公式 1-5 重言式与蕴含式 1-6 其他联结词 1-7 对偶与范式 1-8 推理理论 第一章 命题逻辑 教学目的及要求： 深刻理解和掌握命题逻辑中基本概念和基本方法 教学内容： 命题及表示、联结词、命题公式与翻译、真值表与等价公式、重言式与蕴含式、对偶与范式、推理理论。 教学重点： 命题逻辑中的基本概念和基本推理方法。 教学难点：推理理论 §1.1 命题 [定义]1.1：具有确定真假值的陈述句叫命题。 该定义有两层含义： （1）命题是陈述句。其它的语句，如疑问句、祈使句、感叹句均不是命题； （2）这个陈述句表示的内容可以分辨真假，而且不是真就是假，不能不真也不假，也不能既真又假。 §1.1 命题 命题的真值 作为命题的陈述句所表示的判断结果称为命题的真值，真值只取两个值：真或假。凡是与事实相符的陈述句是真命题，而与事实不符合的陈述句是假命题。通常用1（或字母T）表示真，用0（或字母F）表示假。 §1.1 命题 例 判断下列语句是否为命题，并指出其真值。 （1）北京是中国的首都。 （2）5可以被2整除。 （3）2+2=5。 （4）请勿吸烟！ （5）乌鸦是黑色的吗？ （6）这个小男孩多勇敢啊！ （7）别的星球上有生物。 （8）我正在说谎。 §1.1 命题 注意： 一个语句本身是否能分辨真假与我们是否知道它的真假是两回事。也就是说，对于一个句子，有时我们可能无法判定它的真假，但它本身却是有真假的，那么这个语句是命题，否则就不是命题。 悖论不是命题。 §1.1 命题 命题的分类 原子命题：是指不能再分解为更简单命题的命题； 复合命题：若干个原子命题使用适当的联结词所组成的新命题。 例如“雪是白的”是原子命题；“昨天下雨，而且打雷”，“如果明天天晴我就去打球或者游泳”都是复合命题。 §1.1 命题 命题的表示法 在数理逻辑中，使用26个大写英文字母A、B、C…Z或用带下标的大写字母或用数字，如Ai，[12]等表示命题。表示命题的符号称为命题标识符。 例 P：今天下雨。 [12]：今天下雨。 §1.1 命题 [定义]1.2 一个命题标识符如表示确定的命题，称为命题常量；如果命题标识符只表示任意命题的位置标志，它不能确定真值，称为命题变元。 如果命题符号P代表命题常量则意味它是某个具体命题的符号化，如果P代表命题变元则意味着它可指代任何具体命题。命题变元不是命题。本书中如果没有特别指明，通常来说命题符号P等是命题变元，即可指代任何命题。 §1.2 联结词