离散数学第1章-命题逻辑基本概念.ppt

Discrete Math. , Chen Chen 离散数学 Discrete Mathematics 第一部分 数 理 逻 辑 Part One Mathematics logic 逻辑学: 研究人的思维形式和规律的科学．由于研究的对象和方法各有侧重而又分为形式逻辑、辩证逻辑和数理逻辑． 数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科。这里所指的数学方法就是引进一套符号体系的方法。所以数理逻辑又称符号逻辑，它是从量的侧面来研究思维规律的。 现代数理逻辑可分为逻辑演算、证明论、公理集合论、递归论和模型论。 本部分仅介绍计算机科学领域中所必需的数理逻辑基础知识： 命题逻辑和谓词逻辑（一阶逻辑）。 * CHAPTER ONE * 第一章 命题逻辑基本概念 Chapter One Foundations of Proposition Logic 1.1 命题与联结词 1.2 命题公式及其赋值 命题与真值 命题符号化 联结词及其逻辑关系 复合命题 命题常项与变项 命题公式及其赋值 命题公式的类型 公式类型的判断方法 一 、命题 命题：能判断真假(非真即假)的陈述句。 命题的真值：命题的判断结果。 §1.1 命题与联结词 它只有两种可能：真或假，分别用1和0来表示。 真值为1的命题称为真命题；真值为0的命题称为假命题。 判断一个句子是否为命题： 首先判断它是否为陈述句;其次判断它是否有唯一的真值。 定义 一个命题若不能被分解成更简单的陈述句，则称为简单命题或原子命题； 若一个命题是由几个简单陈述句通过联结词联结而成的，则称为复合命题。 例 命题“因为32, 所以3?2.”的组成。 （1）?? 4是素数。 例 1.1 判断下列句子是否为命题 注：通常用小写字母p , q , r 等来表示命题。 （9）????我正在说假话。 （8）????这朵花真美丽啊！ （7）????请不要吸烟！ （6）?? π大于 吗？ （5）????2050年元旦是晴天。 （4）???火星上有水。 （3）? x 大于 y,其中x和y是任意的两个数。 （2）??? 是无理数 。 √ √ √ √ × × × × × 定义 1.1 设 p 为命题，复合命题“非 p ” (即 “p 的否定”)称为 p 的否定式，记为 ┐p 。 符号 ┐称为否定联结词。 规定：┐p 为真当且仅当 p 为假。 二．联结词与复合命题 则: (1) ┐p ； (2) ┐q . 例 符号化：（1）张伟不是三好学生;（2） 不是有理数 。 解：记 p：张伟是三好学生。 q： 是有理数。 例 1.2 将下列命题符号化。 (1) 是有理数是不对的.（2）2是偶素数. (3) 2或4是偶素数. (4) 如果2是素数，则3也是素数. (5) 2是素数当且仅当3是素数. 解：记 p： 是有理数. q：2是素数. r：2是偶数. s：3是素数. t：4是偶数. 则各语句表述为： 非p; (2) q与r; (3) p或t; (4)如果q,则s；(5) q当且仅当s . 定义1.2 设 p , q 为两个命题。复合命题“ p 与q” 即“p 并且q” 称为 p 与 q 的合取式，记为 p ∧ q。符号∧称为合取联结词。 规定： p ∧ q为真当且仅当 p 与q 同时为真。 注：自然语言中 “与”, “和”, “且”, “既.…又…”, “不仅…而且…”, “虽然…但是…”, “一面…一面…”等联结词都可以符号化为∧； 但并不是所有的“与”、“和”等都能用联结词∧替代。 (1)??? 吴颖既用功又聪明. (2)???吴颖不仅用功而且聪明. (3)????吴颖虽然聪明，但不用功. (4)??? 张辉和王丽都是三好学生. (5)??? 张辉和王丽是同学. 例1.3 将下列命题符号化 p∧q; p∧q; q∧┐p； r∧s。 (5) 是原子命题,符号化为t: 张辉和王丽是同学。 则符号化分别为： 解: (1)、(2)、(3)、(4)： 令p:吴颖用功；q:吴颖聪明， r: 张伟是三好学生；s: 王辉是三好学生. 定义1.3 设 p , q 为两个命题 , 复合命题 “ p 或 q ” 称为 p 与 q 的析取式, 记为 p∨q。符号∨称为析取联结词。 规定： p∨q 为假当且仅当 p 与 q 同时为假。 注: 自然语言中的 “或” 联结的两个命