第一章-命题逻辑.pptVIP

离散数学 陈夫华，fuhua1205@ 一般性参考： 《离散数学》，左孝凌等，上海科学技术出版社 《数学家的逻辑》，哈密尔顿，商务印书馆 《元数学导论》， S．C．克林，科学出版社 离散和连续 离散和连续的区别和联系 　离散与连续 “离散”与“连续”是数量关系中一对极为深刻的矛盾，它们之间的对立与统一是数学发展的重要动力之一．“离散”是连续的否定，即“不连续”；“连续”则是指事物、数量的一种属性，这种属性使它们容易被分割或者结合，并且不会因此而丧失它们原有的本性。例如，实数是连续的，整数则是离散的；马铃薯是离散的，而马铃薯羹则是连续的。 离散化 离散数学是计算机专业的一门重要基础课。它所研究的对象是离散数量关系和离散结构数学模型． 由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系， 因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。??? 离散化举例 人体是一个连续的系统，在计算机模拟人体组织构造的时候，需要将连续的化归为一个离散的问题． 你还能举出哪些离散化的例子？ 　离散数学应用领域及学习意义 ?离散数学课程主要介绍离散数学的各个分支的基本概念、基本理论和基本方法。这些概念、理论以及方法大量地应用在数字电路、编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、人工智能、计算机网络等专业课程中；同时，该课程十分有益于学生概括抽象能力、逻辑思维能力、归纳构造能力的提高，十分有益于学生严谨、完整、规范的科学态度的培养。 离散数学五大分支 一、数理逻辑 二、集合论 三、数论 四、代数结构 五、图论 数理逻辑的研究内容 逻辑（Logics）研究的是有效的推理方法，数理逻辑（Mathematical Logics）就是用数学化（符号化）的手段，研究有效的推理方法 什么是有效的推理方法? a 如果推理前提真，则推理结论真 b 由相同的推理前提进行正确的推理，所得的推理结论是一致的 数理逻辑的研究目的 数理逻辑的研究目的：研究形式的真和形式有效的推理，用形式手段尽可能地刻画人们对形式的真和形式有效的推理的朴素理解。 数理逻辑的主要内容 命题逻辑、谓词逻辑 模型论、证明论、递归论、公理化集合论 第一章 命题逻辑1-1 命题及其表示法 定义1：命题是一个具有确定真值的陈述语句 注：真值表示真假的性质，其可能的取值只有“真”和“假”，通常有T或者１表示真，F或者０表示假。 例子：你吃过饭了吗? 　　　　严禁吸烟！ 　　　　5是一个整数 3是偶数 x+y=4 我正在说谎 1-1 命题及其表示法 定义2：原子命题是不能再分解为更简单命题的命题 例子：苏格拉底是哲学家 德国和法国都是欧洲国家 注：１ 原子命题的界定不宜绝对化 3 原子命题常用大写字母A，B，…，P，Q，…或带下标的大写字母来表示 1-1 命题及其表示法 定义3：由原子命题、联结词或标点符号的复合构成的命题称复合命题 例子： 昨天下雨，今天也在下雨 定义4：表示命题的符号称为命题标识符 定义5：一个命题标识符如果表示确定的命题，称为命题常元；如果命题标识符可以表示某类命题中的任何一个，称为命题变元 1-2 命题的联结词 作用：规范日常语言中联结词（如“与”、“或”等）在命题逻辑中的意义和用法，这里联结词可以看作是作用于命题之上的运算符 定义1：设P为一命题，P的否定是一个新的命题，记为┐P。若P为T， ┐P为F；若┐P为T，P为F 例子：P：上海不是一个大城市 ┐P：？ 1-2 命题的联结词 定义2：两个命题P和Q的合取是一个复合命题，记作P∧Q。当且仅当P、Q同时为T时，P∧Q为T，其他情况下P∧Q均为F 例子：P：地球是球形的 Q: 牛顿是物理学家 P∧Q: 地球是球形的并且牛顿是物理学家 1-2 命题的联结词 注：1 ∧是汉语中“与”、“和”、“并”的翻译，但不能绝对化，例如“老张与小李是师徒” 2 合取在一起的两个命题不一定有实质的联系，也不一定是一致的，甚至可以将互为否定的命题合取在一起（该注释对其他逻辑联结词也适用） 定义3：两个命题P和Q的析取是一个复合命题，记作P?Q。当且仅当P、Q同时为F时，P?Q的真值为F；否则P?Q的真值为T 1-2 命题的联结词 例子： P：机器有故障 Q：开关有故障