第4章 离散数学(精品·公开课件).ppt

离散数学 前言 离散数学是现代数学的一个重要分支，是学习计算机科学与技术的重要基础课之一。本课程以数理逻辑、集合论、代数结构、图论的四大部分为主干教学内容,并辅以组合论、数论基础、形式语言与自动机初步等内容。包括： 前言 第一部分 数 理 逻 辑 逻辑学: 研究人的思维形式和规律的科学．由于研究的对象和方法各有侧重而又分为形式逻辑、辩证逻辑和数理逻辑． 数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科。这里所指的数学方法就是引进一套符号体系的方法。所以数理逻辑又称符号逻辑，它是从量的侧面来研究思维规律的。 现代数理逻辑可分为逻辑演算、证明论、公理集合论、递归论和模型论。 本部分仅介绍计算机科学领域中所必需的数理逻辑基础知识。 p?q 的逻辑关系： p为 q 的充分条件，q 为 p 的必要条件 “如果 p，则 q ” 的不同表述法很多： 若 p，就 q 只要 p，就 q p 仅当 q 只有 q 才 p 除非 q, 才 p 或 除非 q, 否则非 p， 例 求下列复合命题的真值 (1) 2 + 2 ＝ 4 当且仅当 3 + 3 ＝ 6. (2) 2 + 2 ＝ 4 当且仅当 3 是偶数. (3) 2 + 2 ＝ 4 当且仅当 太阳从东方升起. (4) 2 + 2 ＝ 4 当且仅当 美国位于非洲. (5) 2 + 2 ≠ 4 当且仅当3不是奇数. （6）两圆面积相等当且仅当它们的半径相等. 命题常项：简单命题,真值确定的陈述句 命题变项：真值不确定的陈述句 命题公式(合式公式)：由命题常项、命题变项、命题联结词及圆括号等组成的字符串。 是否任何字符串都是命题呢？A?B，?A，B? 定义 合式公式 (命题公式, 公式) 递归定义如下： (1) 单个命题常项或变项 p,q,r,…,pi ,qi ,ri ,…,0,1是合式公式 (2) 若A是合式公式，则 (?A)也是合式公式 (3) 若A, B是合式公式，则(A?B), (A?B), (A?B), (A?B)也是合式公式 (4) 只有有限次地应用(1)~(3)形成的符号串才是合式公式 真值表 真值表: 公式A在所有赋值下的取值情况列成的表 （1）列出所有命题变项，列出所有可能赋值 （2）按从低到高的顺序写出各层次； （3）对应每个赋值，计算命题公式各层次的值，直到命 题公式的值 例 给出公式的真值表 A= (q?p) ?q?p 的真值表 3 条件命题的衍生命题 基本概念——个体词、谓词、量词 个体词（个体）: 所研究对象中可以独立存在的具体或抽象的客体，它可以是一个具体的事物，也可以是一个抽象的概念. 表示主语的词（名词或代词）：苏格拉底，2，黑板，自然数，思想，定理. 个体常项：具体的或特定的个体词， 用a, b, c表示 个体变项：抽象的或泛指的个体词， 用x, y, z表示 个体域: 个体变项的取值范围 有限个体域，如{a, b, c}, {1, 2} 无限个体域，如N, Z, R, … 全总个体域: 宇宙间一切事物组成 基本概念 (续) 谓词: 表示个体词的性质或相互之间关系的词 ???? 谓词常项：表示具体性质或关系的谓词 F: …是人，F(a)：a是人 G： …是自然数， F(2)：2是自然数 ???? 谓词变项：表示抽象的或泛指的谓词 F: …具有性质F，F(x)：x具有性质F 元数：谓词中所包含的个体词数 ???? 一元谓词: 表示事物的性质 多元谓词(n元谓词, n?2): 表示个体词之间的关系 如 L(x,y)： x与y有关系L， L(x,y)： x比y高2厘米 注意：多元谓词中，个体变项的顺序不能随意改动 5 公式的类型 定义 设A为一个命题公式 (1) 若A无成假赋值，则称A为重言式(也称永真式) (2) 若A无成真赋值，则称A为矛盾式(也称永假式) (3) 若A不是矛盾式，则称A为可满足式 注意：重言式是可满足式，但反之不真. 例1.13 用真值表证明(p∨q)∧┐p→q为重言式。 逻辑等价式 定义1.3 当命题公式A?B为永真式时，称A逻