离散数学1.1-2.ppt

离散数学 张波 E-mail：zhangboajd@163.com 手机办公室：行政楼B212 主要内容 数理逻辑（又称符号逻辑） 集合论 代数结构 图论 组合分析初步 形式语言和自动机初步 数理逻辑部分 第1章 命题逻辑 第2章 一阶逻辑 第1章 命题逻辑 1.1 命题符号化及联结词 1.2 命题公式及分类 1.3 等值演算 1.4 对偶与范式 1.5 推理理论 1.1 命题符号化及联结词 命题与真值 原子命题 复合命题 命题常项 命题变项 联结词 命题与真值 命题: 判断结果惟一的陈述句 命题的真值: 判断的结果 真值的取值: 真与假 真命题: 真值为真的命题 假命题: 真值为假的命题 例 下列句子中那些是命题？ (1) 是无理数. (2) 2 + 5 ＝8. (3) x + 5 ＞ 3. (4) 你今天偷菜了吗？ (5) 这只兔子跑得真快呀！ (6) 诚湖内不许滑冰！ (7) 我正在说谎话. 命题的分类 1.简单命题(原子命题) 简单构成的命题 (不能分解成更简单的陈述句) 简单命题的真值是确定的，又称为命题常项或命题常元 2.复合命题 由简单命题与联结词按一定规则复合而成的命题 3.命题变项（命题变元） 真值不确定的陈述句，如:x+35 注意：命题变元不是命题！ 简单命题符号化 联结词与复合命题 1.否定式与否定联结词“?” 定义 设p为命题，复合命题 “非p”（或 “p的否定”）称 为p的否定式，记作?p，符号?称作否定联结词 ?p 为真当且仅当p为假 2.合取式与合取联结词“∧” 定义 设p,q为二命题,复合命题“p并且q”(或“p与q”)称 为p与q的合取式，记作p∧q，∧称作合取联结词，并规 定 p∧q为真当且仅当p与q同时为真 注意：描述合取式的灵活性与多样性 分清简单命题与复合命题 例 将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 例 令 r : 张辉是三好学生，s :王丽是三好学生 (4) r∧s. (5) 令 t : 张辉与王丽是同学，t 是简单命题 . 联结词与复合命题 定义 设 p,q为二命题，复合命题“p或q”称作p与q 的析取式，记作p∨q，∨称作析取联结词，并规 定p∨q为假当且仅当p与q同时为假. 例 （7）小王现在在宿舍或图书馆里. 令v :小王在宿舍,w:小王在图书馆 则 (7) 符号化为 v∨w 定义 设 p,q为二命题，复合命题 “如果p,则q” 称作p与q的蕴涵式，记作p?q，并称p是蕴涵式的前件，q为蕴涵式的后件. ?称作蕴涵联结词，并规定，p?q为假当且仅当 p 为真 q 为假. 注意：1. p与q不一定有内在联系 2. 前件p为假时， p?q为真 p?q 的逻辑关系： p为 q 的充分条件，q 为 p 的必要条件 “如果 p，则 q ” 的不同表述法很多： 若 p，就 q 只要 p，就 q p 仅当 q 只有 q 才 p 除非 q, 才 p 或 除非 q, 否则非 p， 常出现的错误：不分充分与必要条件 例 设 p:天冷，q:小王穿羽绒服， 将下列命题符号化 (1) 只要天冷，小王就穿羽绒服. (2) 因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服. (6) 除非小王穿羽绒服，否则天不冷. (7) 如果天不冷，则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候. 定义 设p，q为二命题，复合命题 “p当且仅当q”称作p与q的等价式，记作p?q，?称作等价联结词.并p?q规为真当且仅当p与q同时为真或同时为假. 说明: (1) p?q 的逻辑关系:p与q互为充分必要条件 (2) p?q为真当且仅当p与q同真或同假 (3) p ? q与(p ? q)?(q ? p)等值 例 求下列复合命题的真值 (1) 2 + 2 ＝ 4