数理逻辑与 1.1-2 .ppt

离散数学 主讲：任光明 电话邮箱：Ren_guang_ming@163.com Q q一、什么是离散数学？ 离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。 二、为什么要学习离散数学？ 由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系， 因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型； 又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。 离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域， 从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。 三、离散数学从哪里来？ 离散数学是传统的逻辑学，集合论（包括函数），数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数（包括代数系统，群、环、域等），布尔代数，计算模型（语言与自动机）等汇集起来的一门综合学科。离散数学的应用遍及现代科学技术的诸多领域。 四、学好离散数学有什么好处？ 离散数学课程主要介绍离散数学的各个分支的基本概念、基本理论和基本方法。这些概念、理论以及方法大量地应用在数字电路、编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、人工智能、计算机网络等专业课程中； 同时，该课程所提供的训练十分有益于学生概括抽象能力、逻辑思维能力、归纳构造能力的提高，十分有益于学生严谨、完整、规范的科学态度的培养。 主要内容 数理逻辑 集合论 代数结构 图论 组合分析初步 形式语言和自动机初步 教材与教学参考书 教材： 耿素云、屈婉玲、张立昂，离散数学（第三版），清华大学出版社, 2004. 教学参考书： 屈婉玲、耿素云、张立昂，离散数学题解（修订版），清华大学出版社，2004. 数理逻辑部分 第1章 命题逻辑 第2章 一阶逻辑 第1章 命题逻辑 1.1 命题符号化及联结词 1.2 命题公式及分类 1.3 等值演算 1.4 对偶与范试 1.5 推理理论 1.1 命题符号化及联结词 命题与真值 原子命题 复合命题 命题常项 命题变项 联结词 命题与真值 命题: 判断结果惟一的陈述句 命题的真值: 判断的结果 真值的取值: 真与假 真命题: 真值为真的命题 假命题: 真值为假的命题 注意: 感叹句、祈使句、疑问句都不是命题 陈述句中的悖论以及判断结果不惟一确定的也不是 命题 例 下列句子中那些是命题？ (1) 是无理数. (2) 2 + 5 ＝8. (3) x + 5 ＞ 3. (4) 你有铅笔吗？ (5) 这只兔子跑得真快呀！ (6) 请不要讲话！ (7) 我正在说谎话. 命题的分类 简单命题(原子命题)： 简单陈述句构成的命题 复合命题： 由简单命题与联结词按一定规则复合 而成的命题 简单命题符号化 联结词与复合命题 1.否定式与否定联结词“?” 定义 设p为命题，复合命题 “非p”（或 “p的否定”）称 为p的否定式，记作?p，符号?称作否定联结词，并规 定?p 为真当且仅当p为假 2.合取式与合取联结词“∧” 定义 设p,q为二命题,复合命题“p并且q”(或“p与q”)称 为p与q的合取式，记作p∧q，∧称作合取联结词，并规 定 p∧q为真当且仅当p与q同时为真 注意：描述合取式的灵活性与多样性 分清简单命题与复合命题 例 将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 解 令 p：王晓用功，q：王晓聪明，则 (1) p∧q (2) p∧q (3) p∧?q. 例 (续) 令 r : 张辉是三好学生，s :王丽是三好学生 (4) r∧s. (5) 令 t : 张辉与王丽是同学，t 是简单命题 . 联结词与复合命题(续) 定义 设 p,q为二命题，复合命题“p或q”称作p与q 的析取式，记作p∨q，∨称作析取联结词，并规 定p∨q为假当且仅当p与q同时为假. 解 令 p:2是素数, q:3是