离散-1-1-命题逻辑.ppt

离 散 数 学 林昌龙 华侨大学计算机学院 1 教材与参考资料 n教材： n 离散数学 刘玉珍、刘咏梅编，武汉大学出版社 n参考资料： n离散数学耿素云、屈婉玲、张立昂编，清华大学出版社 n离散数学朱一清编著，电子工业出版社 nDiscrete Mathematical Structures Bernard Kolman, Fobert C. Busby and Sharon Ross 著 Prentice Hall出版社 2 目的、意义和要求 nIEEE (Institute of Electrical and Electronics Engineers) 美国电气和电子工程师协会 nACM (Association for Computing Machinery ) 美国计算机协会 nComputing curricula 2001 computer science 3 目的、意义和要求 n研究内容：离散量的结构及其相互间的关系。 n意义：计算机科学的理论基础。 n目的：打基础 n必备的数学知识 n培养抽象思维能力、逻辑推理能力 n教学要求： n内容：1-7 章、8-10简介、11章 n作业：按时交、课后复习（概念、定理） 4 离散数学的构成 数理逻辑 集 合 论 图 论 代数系统 命题逻辑 谓词逻辑 集合 关系 图的基本概念 几个特殊图 代数系统的基本概念 特殊代数系统 离散数学 函数 图的连通性 代数系统的同态与同构 5 主要内容： n1.1 命题符号化 n基本概念 n命题联接词 n1.2 合式公式 n命题语言的字母表 n合式公式可归纳定义 n公式的代入实例 6 第一篇 数理逻辑 第一章 命题逻辑 n数理逻辑是用数学方法研究形式推理的一门学科 n命题逻辑是数理逻辑的基本组成部分之一 n推理的基本要素是命题 n把命题作为基本单位来分析 n在计算机科学中的应用：软件、硬件设计 符号化 研究公式间的关系 推导、演算 7 1.1 命题符号化 1. 基本概念 n命题：具有唯一真/假值的陈述句。 T/1真 F/0假 （1）命题必须是一个完整的句子，包括用数学式子代表的语句。 （2）所给的语句具有真假意义。 一般只有陈述句才具有真假意义 祈使句、疑问句、感叹句不具有真假意义 （3）能判断出真假。 将来某个时候能判断出真假也行 两者必居其一且只居其一 二值逻辑 8 1.1 命题符号化 1. 基本概念 n命题：具有唯一真/假值的陈述句。 T/1真 F/0假 例： 中国的首都在北京。 雪是白色的。 1 + 1 = 10 建国大业里面有很多大腕。 贾君鹏，你妈妈喊你回家吃饭。 立正！ 你喜欢网络游戏吗？ 今天的天气真热！ 9 1.1 命题符号化 1. 基本概念 n命题：具有唯一真/假值的陈述句。 T/1真 F/0假 例： 哥德巴赫猜想是正确的。 牛鬼蛇神是存在的。 x + y 3 我正在说谎。 本命题是假的。 10 1.1 命题符号化 1. 基本概念 n命题：具有唯一真/假值的陈述句。 T/1真 F/0假 n简单命题：若命题是一个简单的陈述句。 n复合命题：由简单命题通过“非”、“或”、“与”、“蕴含”、“等值” 等命题联结词而组成。 例：李红既学英语又学日语。 你只有刻苦学习，才能取得好成绩。 11 n否定词（）：P为真当且仅当P的真值为假。 例： P : 中国的首都在北京。 P: 中国的首都不在北京。 1.1 命题符号化 2.联接词 是不是简单命题？ PP 01 10 n合取: PQ为真当且仅当P和Q的真值均为真。 例：P: 李红学英语。 Q: 李红学日语。 PQ: 李红学英语并且学日语。 相当于汉语的 “与”、“并且” P QPQ 0 00 0 10 1 00 1 11 与自然语言不同：凡是命题均可联接。 12 1.1 命题符号化 2.联接词 n合取的概念与自然语言中的“与”意义相似，但并不完全相 同。例如 nP：我们去看电影。 nQ：房间里有十张桌子。 n上述命题的合取为 nPQ：我们去看电影与房间里有十张桌子。 n在自然语言中，上述命题是没有意义的，因为P与Q没有 内在联系，但作为数理逻辑中P和Q的合取PQ来说，它 仍可成为一个新的命题，只要按照定义，在P、Q分别取 真值后，PQ的真值也必确定。 13 1.1 命题符号化 2.联接词 n命题联结词“合取”甚至可以将两个互为否定的 命题联结在一起。这时，其真值永为F。 P：今天下雨。 Q：今天不下雨。（此时Q既是P） PQ：今天下雨与今天不下雨。 PQ的真值为F。 n命题联结词“合取”也可以将若干个命题联结在 一起。 n“合取”是一个二元运算。 14 1.1 命题符号化 2.联接词 n注意，并非所有的“和”、“与”、“并且”均 可用“”表示。例如“李华和张南是表兄 弟。”“王丽与王萍是堂姐妹”“他打开箱子 并且取出一件衣服来。”这三句中的“和” 、“与”、“并且”就不能用“”表示。 n练习：P：一个世纪是一百年。 Q：4是偶数。 写出PQ并确定其真值。 15 1.1 命题符号化 2.联接词 n析取: PQ为假当且仅当P和Q的真值均为假。 例：P: 李红学英语。 Q: 李红学日语。 PQ: 李红学英语或者学日语。 相当于 汉语中 两者可 同时为 真的“或 ” P QPQ 0 00 0 11 1 01 1 11 n并非所有的“或”可用“”表示。例如，“我向东行或向西行。”该语句中 的“或”称为“排斥或”，因为事实上一个人不会既向东行，又向西行。 n析取“”指的是“可兼或”。例如，他可能是100米或400米赛跑的冠军。 这里 nP：他可能是100米赛跑的冠军。 nQ：他可能是400米赛跑的冠军。 nPQ：他可能是100米或400米赛跑的冠军。 16 1.1 命题符号化 2.联接词 n 还有一些汉语中的“或”字实际上不是命 题联结词。例如，他昨天做了二十或三十道 习题。这里的“或”字只表示了习题的近似数 目，不能用联结词“”表达。 n练习：P：雪是黑的。 Q：4是偶数。 写出PQ并确定其真值。 17 1.1 命题符号化 2.联接词 n蕴涵: PQ为假当且仅当P为真、Q为假。 例：P: 天晴。 Q: 我骑自行车上班。 PQ: 如果天晴，则我骑自行车上班。 P QPQ 0 01 0 11 1 00 1 11 n例1 如果某动物为哺乳动物，则它必胎生。 n例2 如果我得到这本小说，那么我今夜就读完它。 n例3 如果雪是黑的，那么太阳从西方出。 n上述三个例子都可用条件命题PQ表达。 n在例1中，P：某动物为哺乳动物，Q：它必胎生。P的真值为T，Q的真值为T ，PQ的真值为T。 n在例2中，P：我得到这本小说，Q：我今夜就读完它。P的真值为T，Q的真 值为T，PQ的真值为T。如果P的真值为T，Q的真值为F，PQ的真值为F 。如果P的真值为F，Q的真值为T，PQ的真值为T。 n在例3中，P：雪是黑的，Q：太阳从西方出。P的真值为F，Q的真值为F， PQ的真值为T。 18 1.1 命题符号化 2.联接词 n在自然语言中，“如果”与“那么”之间常常是有因果联系 的，否则就没有意义，但对条件命题PQ来说，只要P、Q 能够分别确定真值，PQ即成为命题。此外，自然语言中 对“如果、则”这样的语句，当前提为假时，结论不管真 假，这个语句的意义，往往无法判断。而在条件命题中， 规定为“善意的推定”，即前提为F时，条件命题的真值都取 为T。 在数学上和有些逻辑学的书籍中，“若P则Q”亦可叫 作P蕴含Q，而本书在条件命题中将避免使用“蕴含” 一词，因为在以后将另外定义“蕴含”这个概念。 命题联结词“”亦可记作“ ”。 19 1.1 命题符号化 2.联接词 n蕴涵 nP Q P QPQ 0 01 0 11 1 00 1 11 nP是Q的充分条件。 nQ当P。 nQ是P的必要条件。 nP仅当Q。 nP除非Q。 n只有Q，才P。 20 1.1 命题符号化 2.联接词 n等价: PQ为真当且仅当P和Q的真值相同。 例：P: 两个圆的面积相等。 Q: 两个圆的半径相等。 PQ: 两个圆的面积相等当且仅当两个圆的半径相等。 P QPQ 0 01 0 10 1 00 1 11 n“P当且仅当Q”有两层含义： （1）P当Q； （2）P仅当Q n等价联结词又可以称为双蕴含连接词 n例 当且仅当你走，我留下。 P：你走，Q：我留下。 命题可以表示为：P Q 21 1.1 命题符号化 2.联接词 分析找出 简单命题 用大写字母 表示简单命题 用联接词联接 命题符号 例：符号化命题：如果我上街并且我不累，我就去书店看看。 简单命题：我上街 我累 我去书店看看 解 令 P: 我上街 Q: 我累 R: 我去书店看看 则可符号化为：（PQ)R 22 1.2 合式公式(1) 1. 命题语言的字母表 ： n命题常元：T, F (或 0，1) n命题变元：P1, P2, , Pn n联接词：， n辅助符号：（， ） *：上的符号串，包括空串 2. 命题逻辑的合式公式可归纳定义如下： 命题常元或命题变元是合式公式； 若A,B是合式公式,则(A),(AB),(AB),(AB)和(AB)都是合式公式； 有限次地使用,所得到的符号串才是合式公式。 例：(（PQ)P)R n子公式、真子公式 23 1.2 合式公式(2) 3. 公式的代入实例： 所得到的公式称为A的代入实例。 例