离散数学及应用.ppt

2020 4 23 1 离散数学 DiscreteMathematics 计算机科学与技术学院 SchoolofComputerScience Technology 魏雪丽 2020 4 23 计算机科学与技术学院 引言 一 离散数学与计算机计算机开辟了脑力劳动机械化和自动化的新纪元 计算机的诞生 人们就要为它进一步发展创建新的理论 就要寻找合适的数学工具 例 为了描述新开拓的应用领域中的各种数据的结构 就需要适宜的数学工具 2020 4 23 计算机科学与技术学院 引言 续 故计算机各分支领域中的理论问题 交错地使用着现代数学的各种不同的论题 因为计算机系统从本质上说是一种离散性的结构 它的许多性质可以在有限数学系统的框架中来理解 从中选出一些必要而且是基本的主干论题称为离散数学 因此 离散数学是随着计算机科学的发展而逐步建立的 它形成于七十年代初期 是一门新兴的工具性学科 2020 4 23 计算机科学与技术学院 引言 续 离散数学是现代数学的一个重要分支 是计算机科学与技术的理论基础 是计算机科学与技术专业的核心 骨干课程 它以研究离散量的结构和相互间的关系为主要目标 其研究对象一般是有限个或可数个元素 因此它充分描述了计算机科学离散性的特点 2020 4 23 计算机科学与技术学院 引言 续 二 该课程的主要内容 离散数学课程的主要内容可以分为四个部分 数理逻辑 包括命题逻辑和谓词逻辑 教材的第一 二章 集合论 包括集合 关系和函数 教材的第三 四章 代数系统 包括代数系统的一般概念 几类典型的代数系统和格 教材的第五 六章 图论 包括图的基本概念 几种特殊的图 教材的第七章 2020 4 23 计算机科学与技术学院 引言 续 三 学习该课程的目的 1 为学习计算机后继课程 如数据结构 编译理论 操作系统 数据库原理 形式语言及自动机 软件工程与方法学 计算机网络和人工智能 高级程序设计语言等 提供必要的数学基础 为阅读计算机文章作充分的数学准备 2020 4 23 计算机科学与技术学院 引言 续 数理逻辑 人工智能 数据库 形式语言及自动机 高级程序设计语言 集合论 信息结构与检索 数据结构 图论 可计算性理论 计算机网络 数据结构 代数结构 开关理论 逻辑设计和程序理论 语法分析 2 通过学习离散数学 可以培养和提高自己的抽象思维和逻辑推理能力 获得解决实际问题能力 为以后的软 硬件学习和研究开发工作 打下坚实的数学基础 2020 4 23 计算机科学与技术学院 引言 续 四 教学要求 通过该课程的学习 学生应当了解并掌握计算机科学中普遍采用的离散数学中的一些基本概念 基本思想 基本方法 五 自学要求 由于课时少 内容多且抽象 故要求课前预习 课后复习 认真完成习题 通过做课后习题 来加深对该课程中的一些基本概念的理解 逐步提高自己的抽象思维和逻辑推理能力 作业每星期一交 作为平时成绩 2020 4 23 计算机科学与技术学院 引言 续 六 参考教材 1 离散数学及其应用 魏雪丽等编著机械工业出版社2 离散数学 左孝凌等著上海科技文献出版社3 离散数学 理论 分析 题解 左孝凌等著上海科技文献出版社4 DiscreteMathematicsandItsApplications 英文版 美 KennethH Rosen著机械工业出版社 2020 4 23 计算机科学与技术学院 引言 续 七 考核方式 期末考试成绩占70 平时成绩占30 2020 4 23 计算机科学与技术学院 第一部分数理逻辑 MathematicalLogic 逻辑 是研究推理的科学 公元前四世纪由希腊的哲学家亚里斯多德首创 作为一门独立科学 十七世纪 德国的莱布尼兹 Leibniz 给逻辑学引进了符号 又称为数理逻辑 或符号逻辑 逻辑可分为 1 形式逻辑 通过数学方法 数理逻辑2 辩证逻辑指引进一套符号体系的方法 辩证逻辑是研究反映客观世界辩证发展过程的人类思维的形态的 2020 4 23 计算机科学与技术学院 第一部分数理逻辑 MathematicalLogic 形式逻辑是研究思维的形式结构和规律的科学 它撇开具体的 个别的思维内容 从形式结构方面研究概念 判断和推理及其正确联系的规律 数理逻辑是用数学方法研究推理的形式结构和推理的规律的数学学科 它的创始人Leibniz 为了实现把推理变为演算的想法 把数学引入了形式逻辑 其后 又经多人努力 逐渐使得数理逻辑成为一门专门的学科 上个世纪30年代以后 数理逻辑进入一个崭新的发展阶段 逻辑学不仅与数学结合 还与计算机科学等密切关联 2020 4 23 计算机科学与技术学院 第一部分数理逻辑 MathematicalLogic 1931年Godel不完全性定理的提出 以及递归函数可计算性的引入 促使了1936年Turing机的产生 十年后 第一台电子计算机问世 从广义上讲 数理逻辑包括四论 两演算 即集合论 模型论 递归论 证明论和命题演算 谓词演算 但现在提到数理逻辑 一般是指命题演算和谓词演算 本书课程只研究这两个演算 2020 4 23 计算机科学与技术学院 第一部分数理逻辑 MathematicalLogic 数理逻辑与计算机学 控制论 人工智能的相互渗透推动了其自身的发展 模糊逻辑 概率逻辑 归纳逻辑 时态逻辑等都是目前比较热门的研究领域 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 1命题及其表示方法 PropositionandItsExpression 1 2逻辑联结词 LogicalConnectives 1 3命题公式与翻译 PropositionalFormula ItsTranslation 1 4真值表与等价公式 TruthTablesandPrepositionalEquivalences 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 5重言式与蕴含式 TautologyandImplication 1 6其它联结词 OtherConnectives 1 7对偶与范式 Dual NormalForm 1 8推理理论 InferenceTheory 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 1命题及其表示方法1 1 1命题1 1 2命题的表示方法1 1 3命题的分类 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 1命题及其表示方法 1 1 1命题 Proposition 数理逻辑研究的中心问题是推理 inference 而推理的前提和结论都是表达判断的陈述句 因而表达判断的陈述句构成了推理的基本单位 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 1命题及其表示方法 基本概念命题 能够判断真假的陈述句 命题的真值 命题的判断结果 命题的真值只取两个值 真 用T true 或1表示 假 用F false 或0表示 真命题 判断为正确的命题 即真值为真的命题 假命题 判断为错误的命题 即真值为假的命题 2020 4 23 计算机科学与技术学院 因而又可以称命题是具有唯一真值的陈述句 判断命题的两个步骤 1 是否为陈述句 2 是否有确定的 唯一的真值 例 判断下列句子是否为命题 1 100是自然数 T 2 太阳从西方升起 F 第一章命题逻辑 PropositionalLogic 1 1命题及其表示方法 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 1命题及其表示方法 3 3 3 8 F 4 Howdoyoudo 疑问句 不是命题 5 明年的十月一日是晴天 是命题 其真值到明年十月一日方可知道 6 x 3 9不是命题 7 我正在说谎 是悖论 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 1命题及其表示方法 8 1 101 110二进制中为真 十进制中为假 9 如果太阳从西方升起 那么2是奇数 T 10 国足能杀入2006世界杯当且仅当2 2 4 F 11 今天天气多好啊 感叹句 不是命题 12 请你关上门 祁使句 不是命题 13 别的星球上有生物 是命题 客观上能判断真假 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 1命题及其表示方法 说明 1 只有具有确定真值的陈述句才是命题 一切没有判断内容的句子 无所谓是非的句子 如感叹句 祁使句 疑问句等都不是命题 2 因为命题只有两种真值 所以 命题逻辑 又称 二值逻辑 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 1命题及其表示方法 3 具有确定真值 是指客观上的具有 与我们是否知道它的真值是两回事 如上例中的 5 和 13 1 1 2命题的表示方法在本书中 用大写英文字母A B P Q或带下标的字母P1 P2 P3 或数字 1 2 等表示命题 称之为命题标识符 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 1命题及其表示方法 例如 P 罗纳尔多是球星 Q 5是负数 P3 明天天气晴 2 太阳从西方升起 皆为符号化的命题 其真值依次为1 0 1或0 0 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 1命题及其表示方法 命题标识符又有命题常量 命题变元和原子变元之分 命题常量 表示确定命题的命题标识符 命题变元 命题标识符如仅是表示任意命题的位置标志 就称为命题变元 原子变元 当命题变元表示原子命题时 该变元称为原子变元 命题变元也用A B P Q P1 P2 P3 表示 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 1命题及其表示方法 1 1 3命题的分类 简单 原子命题 不能分解为更简单的陈述语句的命题 如上例中的命题 复合命题 由简单命题通过联结词联结而成的命题 联结词就是复合命题中的运算符 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 1命题及其表示方法 注意 1 一个符号 如P 它表示的是命题常量还是命题变元 一般由上下文来确定 2 命题变元可以表示任意命题 它不能确定真值 故命题变元不是命题 这与 变数x不是数 是一样的道理 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 1命题及其表示方法 小结 本节主要介绍了命题 命题的真值 原子命题 复合命题 命题标识符 命题常量 命题变元和原子变元的概念 重点理解和掌握命题 命题变元 简单 原子 命题 复合命题四个概念 作业 P21 2 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 1 2 1否定联结词 Negation 1 2 2合取联结词 Conjunction 1 2 3析取联结词 Disjunction 1 2 4条件联结词 蕴涵联结词Conditional 1 2 5双条件联结 等值联结词Biconditional 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 在命题逻辑中 主要研究的是复合命题 而复合命题是由原子命题与逻辑联结词组合而成 联结词组是复合命题的重要组成部分 2020 4 23 计算机科学与技术学院 1 2 1否定联结词 定义1 2 1设P为一命题 P的否定是一个新的复合命题 称为P的否定式 记作 P 读作 非P 符号 称为否定联结词 P为真当且仅当P为假 说明 属于一元 unary 运算符 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 的定义也可用下表来说明 联结词 的定义真值表 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 例1 P 天津是一个城市 Q 3是偶数 于是 P 天津不是一个城市 Q 3不是偶数 例2 P 苏州处处清洁 Q 这些都是男同学 P 苏州不处处清洁 注意 不是处处不清洁 Q 这些不都是男同学 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 1 2 2合取联结词 Conjunction 定义1 2 2设P Q为二命题 复合命题 P并且Q 或 P与Q 称为P与Q的合取式 记作P Q 符号 称为合取联结词 P Q为真当且仅当P和Q同时为真 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 联结词 的定义真值表 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 说明 属于二元 binary 运算符 合取运算特点 只有参与运算的二命题全为真时 运算结果才为真 否则为假 自然语言中的表示 并且 意思的联结词 如 既 又 不但 而且 虽然 但是 一面 一面 和 与 等都可以符号化为 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 例3 将下列命题符号化 1 李平既聪明又用功 2 李平虽然聪明 但不用功 3 李平不但聪明 而且用功 4 李平不是不聪明 而是不用功 解 设P 李平聪明 Q 李平用功 则 1 P Q 2 P Q 3 P Q 4 P Q 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 注意 不要见到 与 或 和 就使用联结词 例如 1 李敏和李华是姐妹 2 李敏和张华是朋友 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 例4 试生成下列命题的合取 1 P 我们在6 503 Q 今天是星期二 2 S 李平在吃饭 R 张明在吃饭 解 1 P Q 我们在6 503且今天是星期二 2 S R 李平与张明在吃饭 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 1 2 3析取联结词 Disjunction 定义1 2 3设P Q为二命题 复合命题 P或Q 称为P与Q的析取式 记作P Q 符号 称为析取联结词 P Q为真当且仅当P与Q中至少有一个为真 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 联结词 的定义真值表 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 说明 属于二元 binary 运算符 析取运算特点 只有参与运算的二命题全为假时 运算结果才为假 否则为真 由析取联结词的定义可以看出 与汉语中的联结词 或 意义相近 但又不完全相同 在现代汉语中 联结词的 或 实际上有 可兼或 和 排斥或 之分 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 考察下面命题 1 小王爱打球或爱跑步 可兼或 设P 小王爱打球 Q 小王爱跑步 则上述命题可符号化为 P Q 2 林芳学过英语或法语 可兼或 设P 林芳学过英语 Q 林芳学过法语 则上述命题可符号化为 P Q 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 3 派小王或小李中的一人去开会 排斥或 设P 派小王去开会 Q 派小李去开会 则上述命题可符号化为 P Q P Q 4 人固有一死 或重于泰山或轻于鸿毛 排斥或 5 ab 0 即a 0或b 0 可兼或 由此可见 P Q 表示的是 可兼或 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 注意 当P和Q客观上不能同时发生时 P或Q 可以符号化为 P Q 例如 小王现在在宿舍或在图书馆 设P 小王现在在宿舍 Q 小王现在在图书馆 则上述命题可符号化为 P Q 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 1 2 4 条件联结词 蕴涵联结词Conditional 定义1 2 4设P Q为二命题 复合命题 如果P则Q 若P则Q 称为P与Q的条件命题 记作P Q P Q为假当且仅当P为真且Q为假 称符号 为条件联结词 并称P为前件 Q为后件 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 联结词 的定义真值表 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 注 1 P Q表示的基本逻辑关系是 Q是P的必要条件或P是Q的充分条件 因此复合命题 只要P就Q 因为P 所以Q P仅当Q 只有Q才P 等都可以符号化为P Q的形式 2 属于二元 binary 运算 2020 4 23 计算机科学与技术学院 第一章命题逻辑 ProPositionalLogic 1 2逻辑联结词 LogicalConnectives 例5 将下列命题符号化 1 天不下雨 则草木枯黄 P 天下雨 Q 草木枯黄 则原命题可表示为 P Q 2 如果小明学日语 小华学英语 则小芳学德语 P 小明学日语 Q 小华学英语 R 小芳学德语 则原命题可表示为 P Q R 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 3 只要不下雨 我就骑自行车上班 P 天下雨 Q 我骑自行车上班 则原命题可表示为 P Q 4 只有不下雨 我才骑自行车上班 P 天下雨 Q 我骑自行车上班 则原命题可表示为 Q P 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 5 如果2 2 4 则太阳从东方升起 P Q T PQ如果2 2 4 则太阳从西方升起 P R F R如果2 2 4 则太阳从东方升起 P Q T 如果2 2 4 则太阳从西方升起 P R T 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 注意 1 与自然语言的不同 前件与后件可以没有任何内在联系 2 在数学中 若P则Q 往往表示前件P为真 则后件Q为真的推理关系 但数理逻辑中 当前件P为假时 P Q的真值为真 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 1 2 5双条件联结 等值联结词Biconditional 定义1 2 5设P Q为二命题 复合命题 P当且仅当Q 称为P与Q的双条件命题 记作PiffQ或P Q 符号 称为双条件 等值 联结词 P Q为真当且仅当P Q真值相同 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 联结词 的定义真值表 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 注 1 P仅当Q可译为P QP当Q可译为Q PP当且仅当Q译为P Q 2 属于二元 binary 运算符 3 双条件命题P Q所表达的逻辑关系是 P与Q互为充分必要条件 相当于 P Q Q P 只要P与Q的真值同为1或同为0 P Q的真值就为1 否则P Q的真值为0 双条件联结词连接的两个命题之间可以没有因果关系 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 例6 分析下列命题的真值 1 2 2 4当且仅当3是奇数 P Q P 2 2 4 Q 3是奇数 2 2 2 4当且仅当3不是奇数 P Q 3 2 2 4当且仅当3是奇数 P Q 4 2 2 4当且仅当3不是奇数 P Q 2020 4 23 计算机科学与技术学院 第一章命题逻辑 ProPositionalLogic 1 2逻辑联结词 LogicalConnectives 约定 1 运算次序优先级 2 相同的运算符按从左至右次序计算 否则要加上括号 3 最外层圆括号可省去 小结 本节介绍了五种联结词 重点是理解和掌握五种联结词的内涵及它们与自然语言中相应联结词的不同之处 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 作业 1 P522 预习1 3 1 4思考题 1 何谓合式公式 2 复合命题符号化的基本步骤是什么 3 何谓真值表 4 两个命题公式等价的涵义是什么 5 两个等价的命题公式其真值表有何关系 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 3命题公式与翻译 1 3命题公式与翻译1 3 1命题公式1 3 2复合命题的符号化 翻译 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 3命题公式与翻译 PropositionalFormula ItsTranslation 1 3 1命题合式公式 Well formedformula wff 定义1 3 1 单个命题变元和命题常量称为原子公式 命题合式公式是由命题变元 命题常量 联结词和圆括号按一定的逻辑关系联结起来的符号串 我们以如下递归的形式来定义合式公式 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 3命题公式与翻译 定义1 3 2 1 原子公式是合式公式 wff 2 若A是合式公式 则 A 也是合式公式 3 若A B是合式公式 则 A B A B A B A B 也是合式公式 4 当且仅当有限次地应用 1 3 所得到的包含原子公式 联结词和括号的符号串是合式公式 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 3命题公式与翻译 注 1 合式公式也称为命题公式 并简称为公式 2 命题公式一般不是命题 仅当公式中的命题变元用确定的命题代入时 才得到一个命题 其真值依赖于代换变元的那些命题的真值 2020 4 23 计算机科学与技术学院 第一章命题逻辑 ProPositionalLogic 1 3命题公式与翻译 例1 指出 P P Q 是否是命题公式 wff 如果是 则具体说明 解 P是wff由 1 Q是wff由 1 P Q是wff由 2 P P Q 由 2 2020 4 23 计算机科学与技术学院 第一章命题逻辑 ProPositionalLogic 1 3命题公式与翻译 例2 P Q R S Q P P 等均为合式公式 而PQ S P W Q 等不是合式公式 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 3命题公式与翻译 1 3 2复合命题的符号化 翻译 有了命题演算的合式公式的概念 我们可以把自然语言中的有些语句 复合命题 翻译成数理逻辑中的符号形式 基本步骤如下 1 分析出各简单命题 将它们符号化 2 使用合适的联结词 把简单命题逐个的联结起来 组成复合命题的符号化表示 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 3命题公式与翻译 例3 1 我今天进城 除非下雨 2 仅当你走我将留下 3 假如上午不下雨 我去看电影 否则就在家里读书或看报 4 除非你努力 否则你将失败 5 一个人起初说 占据空间的 有质量的而且不断变化的叫做物质 后来他改说 占据空间的有质量的叫做物质 而物质是不断变化的 问他前后主张的差异在什么地方 试以命题形式进行分析 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 3命题公式与翻译 例4 P6例1 3 3 例1 3 4 5 例1 3 5小结 本节介了命题公式的概念及复合命题的符号化 重点是理解命题公式的递归定义 掌握复合命题的符号化方法 作业 P7 2 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 1 4 1真值表 TruthTable 1 4 2等价公式 ProPositionalEquivalences 1 4 1真值表前面在定义联结词时 曾经使用过真值表 下面给出真值表的定义 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 定义1 4 1 对公式的赋值或解释 设P1 P2 Pn是出现在公式A中的全部的命题变元 给P1 P2 Pn各指定一个真值 称为对A的一个赋值或解释 若指定的一组值使A的真值为真 假 称这组值为A的成真 假 赋值 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 例如 对公式 P Q R 赋值011 即令P 0 Q 1 R 1 为 P Q R的成真赋值 另一组赋值010为 P Q R的成假赋值 还有000 001 111 2020 4 23 计算机科学与技术学院 第一章命题逻辑 ProPositionalLogic 1 4真值表与等价公式 考虑 含有n个命题变元的公式共有多少组不同的赋值 定义1 4 2 真值表 在命题公式A中 对于命题变元的每一组赋值和由它们所确定的命题公式A的真值列成表 称做命题公式A的真值表 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 对公式A构造真值表的具体步骤为 1 找出公式中所有命题变元P1 P2 Pn 列出全部的2n组赋值 2 按从小到大的顺序列出对命题变元P1 P2 Pn 的全部2n组赋值 3 对应各组赋值计算出公式A的真值 并将其列在对应赋值的后面 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 例1 给出 P Q P Q 的真值表 2020 4 23 计算机科学与技术学院 第一章命题逻辑 ProPositionalLogic 1 4真值表与等价公式 例1 给出 P Q P Q 的真值表 2020 4 23 计算机科学与技术学院 第一章命题逻辑 ProPositionalLogic 1 4真值表与等价公式 例2 构造公式 P Q R的真值表 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 例2 构造公式 P Q R的真值表 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 练习1 构造公式 P Q Q P 真值表 2020 4 23 计算机科学与技术学院 第一章命题逻辑 ProPositionalLogic 1 4真值表与等价公式 练习1 构造公式 P Q Q P 真值表 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 练习2 构造公式 P Q Q真值表 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 练习2 构造公式 P Q Q真值表 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 1 4 2等价公式给定n个命题变元 按合式公式的形成规则可以形成无数多个命题公式 但这些无穷尽的命题公式中 有些具有相同的真值表 考虑 由n个命题变元能生成 种真值 表 不同的命题公式 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 定义1 4 3 给定两个命题公式A和B 设P1 P2 Pn为出现于A和B中的所有原子变元 若给P1 P2 Pn任一组真值指派 A和B的真值都相同 则称A和B是等价的或逻辑相等 记作A B 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 注 1 不是逻辑联结词 2 命题公式之间的逻辑相等关系具有 自反性 A A 对称性 若A B 则B A 传递性 若A B且B C 则A C 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 证明公式等价的方法 1 真值表法2 等值演算法1 真值表法例1 P Q P Q 见真值表例题1 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 例2 证明 P Q P Q Q P 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 例2 证明 P Q P Q Q P 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 例3 判断公式P Q R P Q R是否等价 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 例3 判断公式P Q R P Q R是否等价 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 由真值表可知 两个公式为等价式 2 等值演算法 EquivalentCalculation 等值演算中使用的一条重要规则 置换规则定义1 4 4 子公式 如果X是wffA的一部分 且X本身也是wff 则称X是A的子公式 例如 P P Q 为Q P P Q 的子公式 2020 4 23 计算机科学与技术学院 第一章命题逻辑 ProPositionalLogic 1 4真值表与等价公式 定理1 4 1 置换定理AxiomofrePlacement 设X是wffA的子wff 若X Y 则若将A中的X用Y来置换 所得公式B与A等价 即A B 证 因为对变元的任一指派 X与Y真值相同 所以Y取代X后 公式B与公式A对变元的任一指派真值也相同 所以A B 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 注 满足定理1 4 1的条件的置换称为等价置换 或等价代换 定义1 4 5 等值演算 根据已知的等价公式 推演出另外一些等价公式的过程称为等值演算 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 常用的等价式 1 双重否定律 P P2 结合律 P Q R P Q R P Q R P Q R P Q R P Q R 3 交换律 P Q Q PP Q Q PP Q Q P4 分配律 P Q R P Q P R P Q R P Q P R 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 常用的等价式 5 幂等律 P P PP P P6 吸收律 P P Q PP P Q P7 德 摩根律 P Q P Q P Q P Q8 同一律 P F PP T P9 零律 P T TP F F 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 常用的等价式 10 否定律 P P TP P F11 蕴涵等值式 P Q P Q12 等价等值式 P Q P Q Q P 13 假言易位 P Q Q P14 等价否定等值式 P Q P Q15 归谬论 P Q P Q P 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 其中P Q R等代表任意命题公式 这样上面的每一个公式都是一个模式 它可以代表无数多个同类型的命题公式 例如 P P T中 用 P Q 置换P 则得 P Q P Q T 用 P置换P 则得 P P T 2020 4 23 计算机科学与技术学院 第一章命题逻辑 ProPositionalLogic 1 4真值表与等价公式 例1 证明Q P P Q Q P证 Q P P Q Q P P 吸收律 例2 证明P Q Q P Q证 P Q Q P Q Q Q P Q T P Q 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 例3 证明 P Q Q R P Q R证 P Q Q R P Q Q R P Q Q R P Q Q R P Q R Q Q R P Q R 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 例4 验证P Q R P Q R证 右 P Q R P Q R P Q R P Q R P Q R 练 1 P Q P R P Q R 2 P Q P Q P Q P Q 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 等值演算在计算机硬件设计中 在开关理论和电子元器件中都占有重要地位 小结 本节介绍了真值表 公式等价 等值演算和等价置换等概念 给出了常用的重要等价公式 26个 重点掌握用真值表法验证公式的等价性和等值演算法推演两个公式等价 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 作业 Pg 13 1 2 4 2 2 4 4 6 3 预习 1 5 1 6思考题 Pg 13 5 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 5重言式与蕴含式 TautologyandImplication 1 5 1命题公式的分类1 5 2重言式 Tautology 与矛盾式 contradictory 的性质1 5 3蕴含式 ImPlication 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 5重言式与蕴含式 TautologyandImplication 1 5 1命题公式的分类复合命题 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 5重言式与蕴含式 TautologyandImplication 定义1 5 1设A为任一命题公式 1 若A在其各种赋值下的取值均为真 则称A是重言式或永真式 记为T或1 2 若A在其各种赋值下的取值均为假 则称A是矛盾式或永假式 记为F或0 3 若A不是矛盾式则称A为可满足式 satisfiable 注 由定义可知 重言式一定是可满足式 反之不真 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 5重言式与蕴含式 TautologyandImplication 判别命题公式的类型有两种方法 真值表法和等值演算法 等值演算法是将所给命题公式通过等值演算化为最简单的形式 然后再进行判别 例1 判别下列命题公式的类型 1 Q P Q P 重言式 2 P P Q Q R 矛盾式 3 P Q P 可满足式 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 5重言式与蕴含式 TautologyandImplication 1 5 2重言式 Tautology 与矛盾式 contradictory 的性质定理1 5 1 任何两个重言式的合取或析取 仍然是一重言式 由幂等律立得 证明 设A和B为两个重言式 则不论A和B的分量指派任何真值 总有A为T B为T 故A B T A B T 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 5重言式与蕴含式 TautologyandImplication 定理1 5 2 一个重言式 矛盾式 对同一分量都用任何合式公式置换 其结果仍为一重言式 矛盾式 证明 由于重言式 矛盾式 的真值与对变元的赋值无关 故对同一变元以任何合式公式置换后 重言式 矛盾式 的真值仍永为T F 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 5重言式与蕴含式 TautologyandImplication 定理1 5 3 A B是两个命题公式 A B的充要条件是A B为重言式 证明 若A B为重言式 则A B永为T 即A B的真值表相同 所以A B 反之 若A B 则A B真值表相同 所以A B永为T 所以A B为重言式 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 5重言式与蕴含式 TautologyandImplication 它们之间具有如下关系 P Q Q PQ P P Q 1 5 3蕴含式 ImPlication 定义1 5 2 当且仅当P Q是一个重言式时 我们称 P蕴含Q 并记作P Q 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 5重言式与蕴含式 TautologyandImplication 因此 要证明P Q有三种方法 1 真值表法 即列出P Q的真值表 观察其是否永为真 2 等值演算法 通过证明P Q 1来证P Q3 分析法 直接分析法 假定前件P是真 推出后件Q是真 间接分析法 假定后件是假 推出前件是假 即证 Q P 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 5重言式与蕴含式 TautologyandImplication 例 证明 Q P Q P1 法1 真值表 略 2 法2 Q P Q P Q P Q P Q P Q P P Q P Q 1即 Q P Q P 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 5重言式与蕴含式 TautologyandImplication 3 直接分析法 若 Q P Q 为真 则 Q P Q为真 所以Q为假 P为假 所以 P为真 间接分析法 若 P为假 则P为真 再分二种情况 若Q为真 则 Q为假 从而 Q P Q 为假 若Q为假 则P Q为假 则 Q P Q 为假 根据 所以 Q P Q P 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 5重言式与蕴含式 TautologyandImplication 下面常用的14个蕴含式 都可以用上述方法加以推证 1 P Q P2 P Q Q3 P P Q4 P P Q5 Q P Q6 P Q P7 P Q Q8 P P Q Q9 Q P Q P10 P P Q Q11 P Q Q R P R12 P Q P R Q R R13 P Q R S P R Q S 14 P Q Q R P R 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 5重言式与蕴含式 TautologyandImplication 等价式与蕴含式的关系 定理1 5 4 设P Q为任意两个命题公式 P Q的充要条件为P Q且Q P 证 若P Q 则P Q为永真式因为P Q P Q Q P 所以P Q Q P为永真式 从而P Q Q P 反之 若P Q Q P 则P Q Q P为永真式 所以 P Q Q P 为永真式 从而P Q为永真式 即P Q 2020 4 23 计算机科学与技术学院 第一章命题逻辑 PropositionalLogic 1 5重言式与蕴含式 TautologyandImplication 蕴含的性质 设A B C为任意wff 1 若A B 且A为永真式 则B必为永真式 2 若A B B C 则A C 3 若A B A C 则A B C 4 若A B且C B 则A C B 证 1 因为A B A永为T 所以B必永为T 2 由I11 A B B C A C 所以若A B B C 则 A B B C 永为T