离散命题逻辑.ppt

. -吴扬扬制- 离 散 数 学 林昌龙 华侨大学计算机学院 教材与参考资料 教材： 《 离散数学 》刘玉珍、刘咏梅编，武汉大学出版社 参考资料： 《离散数学》耿素云、屈婉玲、张立昂编，清华大学出版社 《离散数学》朱一清编著，电子工业出版社 《Discrete Mathematical Structures》 Bernard Kolman, Fobert C. Busby and Sharon Ross 著 　 Prentice Hall出版社 目的、意义和要求 IEEE (Institute of Electrical and Electronics Engineers) 美国电气和电子工程师协会 ACM (Association for Computing Machinery ) 美国计算机协会 Computing curricula 2001 computer science 目的、意义和要求 研究内容：离散量的结构及其相互间的关系。 意义：计算机科学的理论基础。 目的：打基础 必备的数学知识 培养抽象思维能力、逻辑推理能力 教学要求： 内容：1-7 章、8-10简介、11章 作业：按时交、课后复习（概念、定理） 离散数学的构成 数理逻辑 主要内容： §1.1 命题符号化 基本概念 命题联接词 §1.2 合式公式 命题语言的字母表 合式公式可归纳定义 公式的代入实例 第一篇 数理逻辑第一章 命题逻辑 数理逻辑是用数学方法研究形式推理的一门学科 命题逻辑是数理逻辑的基本组成部分之一 推理的基本要素是命题 把命题作为基本单位来分析 §1.1 命题符号化 1. 基本概念 命题：具有唯一真/假值的陈述句。 T/1—真 F/0—假 §1.1 命题符号化 1. 基本概念 命题：具有唯一真/假值的陈述句。 T/1—真 F/0—假 §1.1 命题符号化 1. 基本概念 命题：具有唯一真/假值的陈述句。 T/1—真 F/0—假 §1.1 命题符号化 1. 基本概念 命题：具有唯一真/假值的陈述句。 T/1—真 F/0—假 §1.1 命题符号化 2.联接词 否定词（┐）：┐P为真当且仅当P的真值为假。 例： P : 中国的首都在北京。 ┐P: 中国的首都不在北京。 §1.1 命题符号化 2.联接词 合取的概念与自然语言中的“与”意义相似，但并不完全相同。例如 P：我们去看电影。 Q：房间里有十张桌子。 上述命题的合取为 P∧Q：我们去看电影与房间里有十张桌子。 在自然语言中，上述命题是没有意义的，因为P与Q没有内在联系，但作为数理逻辑中P和Q的合取P∧Q来说，它仍可成为一个新的命题，只要按照定义，在P、Q分别取真值后，P∧Q的真值也必确定。 §1.1 命题符号化 2.联接词 命题联结词“合取”甚至可以将两个互为否定的命题联结在一起。这时，其真值永为F。 P：今天下雨。 Q：今天不下雨。（此时Q既是┐P） P∧Q：今天下雨与今天不下雨。 P∧Q的真值为F。 命题联结词“合取”也可以将若干个命题联结在一起。 “合取”是一个二元运算。 §1.1 命题符号化 2.联接词 注意，并非所有的“和”、“与”、“并且”均可用“∧”表示。例如“李华和张南是表兄弟。”“王丽与王萍是堂姐妹”“他打开箱子并且取出一件衣服来。”这三句中的“和”、“与”、“并且”就不能用“∧”表示。 练习：P：一个世纪是一百年。 Q：4是偶数。 写出P∧Q并确定其真值。 §1.1 命题符号化 2.联接词 并非所有的“或”可用“∨”表示。例如，“我向东行或向西行。”该语句中的“或”称为“排斥或”，因为事实上一个人不会既向东行，又向西行。 析取“∨”指的是“可兼或”。例如，他可能是100米或400米赛跑的冠军。这里 P：他可能是100米赛跑的冠军。 Q：他可能是400米赛跑的冠军。 P∨Q：他可能是100米或400米赛跑的冠军。 §1.1 命题符号化 2.联接词 还有一些汉语中的“或”字实际上不是命题联结词。例如，他昨天做了二十或三十道习题。这里的“或”字只表示了习题的近似数目，不能用联结词“∨”表达。 练习：P：雪是黑的。 Q：4是偶数。 写出P∨Q并确定其真值。 §1.1 命题符号化 2.联接词 例1 如果某动物为哺乳动物，则它必胎生。 例2 如果我得到这本小说，那么我今夜就读完它。