离散数学与命题逻辑课件 .ppt

绪论 课程介绍和要求 主要内容 教材说明 什么是离散数学？ 为什么要学习离散数学？ 怎样学习离散数学？ 课程要求与考试 教材 主教材： 1、郝林等编著. 离散数学. 北京: 科学出版社, 2012年5月 参考书目： 2、屈婉玲等编著.离散数学. 北京: 高等教育出版社，2008年3月 3、左孝凌等编著. 离散数学. 上海: 上海科学技术文献出版社, 2004年1月 第一部分 数理逻辑 问题 什么是数理逻辑？（符号化+推理规则） 经典数理逻辑和现代数理逻辑 主要内容 命题逻辑 谓词逻辑 推理与证明技术 第一讲 命题逻辑的基本概念 主要内容 命题与联结词 命题及其分类 联结词与复合命题 命题公式及其赋值 命题与真值 命题：判断结果惟一的陈述句 命题的真值：判断的结果 真值的取值范围：真与假 真命题与假命题 注意： 感叹句、祈使句、疑问句都不是命题 陈述句中的悖论，判断结果不惟一确定的不是命题 悖论 如果有一个句子B，如果承认B，则可以推出非B成立； 反之，如果承认非B，又可推出B成立。 例子： 1、我正在说假话。 2、罗素的理发师悖论。 3、克里特人伊壁孟德：所有的克里特人都是撒谎者。 悖论不是命题！ 悖论的共同特征： 论断者属于论断主体集。 命题概念 命题分类：简单命题（也称原子命题）与复合命题 简单命题符号化：命题常量 用小写英文字母 p, q, r, …, pi, qi, ri (i?1)表示简单命题 用“1”或“1”表示真，用“0”或“0”表示假 例如，令 p： 是有理数，（ p 的真值为0） q：2 + 5 = 7，（ q 的真值为1） 复合命题符号化：由常量和联结词组成的公式 合取联结词的实例 例2 将下列命题符号化. (1) 吴颖既用功又聪明. (2) 吴颖不仅用功而且聪明. (3) 吴颖虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 合取联结词的实例 解 令p:吴颖用功, q:吴颖聪明 (1) p?q (2) p?q (3) ?p?q (4) 设p:张辉是三好生, q:王丽是三好生 p?q (5) p:张辉与王丽是同学 (1)—(3) 说明描述合取式的灵活性与多样性 (4)—(5) 要求分清 “与” 所联结的成分 析取联结词的实例 例3 将下列命题符号化 (1) 2 或 4 是素数. (2) 2 或 3 是素数. (3) 4 或 6 是素数. (4) 小元元只能拿一个苹果或一个梨. (5) 王小红生于 1975 年或 1976 年. 析取联结词的实例 解 (1) 令p:2是素数, q:4是素数, p?q (2) 令p:2是素数, q:3是素数, p?q (3) 令p:4是素数, q:6是素数, p?q (4) 令p:小元元拿一个苹果, q:小元元拿一个梨 (p??q)?(?p?q) (5) p:王小红生于 1975 年, q:王小红生于1976 年, (p??q)?(?p?q) (1)—(3) 为相容或 (4)—(5) 为排斥或 合取和析取如何记忆？ 蕴涵联结词 定义1.4 设p, q为两个命题，复合命题“如果p, 则q”称作p与q的条件式，记作p?q，并称p是条件式的前件，q为条件式的后件，?称作条件联结词. 规定：p?q为假当且仅当p为真q为假. 蕴涵联结词的实例 例4 设 p：天冷，q：小王穿羽绒服，将下列命题符号化 (1) 只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服. (6) 除非小王穿羽绒服，否则天不冷. (7) 如果天不冷，则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候. 定义1.5 设 p, q为两个命题，复合命题“p当且仅当q”称作p与q的等价式，记作p?q，?称作等价（双条件）联结词. 规定p?q为真当且仅当p与q同时为真或同时为假. p?q 的逻辑关系：p与q互为充分必要条件 自学内容 课本P8—P9： 四种次重要联结词 本小节中p, q, r, … 均表示命题. 1.2 命题公式及其赋值 命题变项与合式公式 命题变项 合式公式 合式公式的层次 公式的赋值 公式赋值 公式类型 真值表 命题变项与合式公式 命题常项、命题变项（命题变元）：类比常量和变量。 常项与变项均用 p, q, r, …, pi, qi, ri, …, 等表示. 第二讲 命题逻辑的等值演算 上一讲主要内容回顾： 简单命题和复合命题、5个重要联结词； 命题