1-1、2命题、联结词.ppt

离散数学DiscreteMathematics 第一篇数理逻辑 逻缉学是一门研究思维形式及思维规律的科学 逻辑规律就是客观事物在人的主观意识中的反映 思维的形式结构包括了概念 判断和推理之间的结构和联系 研究推理有很多方法 用数学方法来研究推理的规律称为数理逻辑 即通过引入表意符号研究推理 因此 数理逻辑又名符号逻辑 现代数理逻辑可分为证明论 模型论 递归函数论 公理化集合论等 这里介绍的是数理逻辑最基本的内容 命题逻辑和谓词逻辑 命题逻辑 也称命题演算 记为Ls 它与谓词逻辑构成数理逻辑的基础 而命题逻辑又是谓词逻辑的基础 学习 命题逻辑 这一章的要求 一 学习目的与要求本章目的是介绍命题逻辑的基本概念 掌握利用命题逻辑表示自然语言 描述概念 判断和推理 建立初步的语言形式化方法 二 知识点1 命题的概念 表示方法 联结词的逻辑意义 2 命题公式的递归定义 自然语言翻译成命题公式3 真值表的构造 命题公式等价的概念 4 重言式与蕴涵式的定义 逻辑意义 逻辑等价与逻辑蕴涵的意义和证明方法 常用的逻辑等价公式和逻辑蕴涵公式 5 命题公式的对偶式 合取范式 析取范式 主合取范式 主析取范式 逻辑小项 逻辑大项 任给公式化为析取范式 任给公式化为主析取范式 任给公式化为合取范式 任给公式化为主合取范式 6 命题逻辑的推理理论 主要的推理方法 真值表法 直接证明法 间接证明法 常用推理规则 P规则 T规则 CP规则 7 命题逻辑的应用示例 三 要求1 识记命题表示方法 真值判断 命题公式的递归定义 2 领会联结词真值确定 翻译 命题公式的等价性和蕴涵性证明 任给公式化为析取范式 任给公式化为主析取范式 任给公式化为合取范式 任给公式化为主合取范式 3 简单应用命题逻辑推理规则 第一章命题逻辑 1 1命题及其表示法要求 深刻理解命题 真值 原子命题 复合命题 命题标识符 命题常量 命题变元 原子变元等概念 1 1命题及其表示法一 命题1 定义能表达判断的陈述句称作命题 Proposition 命题 具有确定值例 判断下列语句是否为命题 1 地球外存在智慧生物 2 1 1 10 3 离散数学是现代数学的一个重要分支 4 你今年暑假去旅行吗 疑问句 5 克里特岛人说 克里特岛人都是说谎话者 悖论 陈述句 述说一件事情的句子 句末用句号 祈使句 要求或者希望别人做什么事或者不做什么事时用的句子 句末用句号或感叹号 疑问句 提出问题的句子 句末用问号 感叹句 带有浓厚感情的句子 句末用感叹号 悖 相反 悖论 自相矛盾的陈述 2 真值 命题所表达的判断结果称为命题的真值 真值只有 真 和 假 两种 记作True 真 和False 假 分别用符号T和F表示 由于命题只有两种真值 所以称这种逻辑为二值逻辑 命题的真值是具有客观性质的 而不是由人的主观决定的 真值是否唯一确定 与是否知道无关 再看下面的语句中 哪些语句是命题 如果是命题 指出它的真值 1 能整除7的正整数只有1和7本身 2 对于每一个正整数n存在一个大于n的素数 3 煤是白的 4 雪是黑的 5 我学英语 或者我学日语 6 在宇宙中地球是唯一有生命的球体 7 1 101 110 8 买两张星期六的电影票 9 全体立正 10 明天是否开会 11 天气多好啊 12 我正在说谎 3 和 4 是命题 真值为F 1 2 是命题 真值为T 祈使句 疑问句 感叹句等都不能作为命题 悖论无真值 也不能作为命题 语句 8 12 都不是命题 6 是命题 有确定真值 只是目前还不知道 7 不是命题 在二进制中为T 在十进制中为F 可根据上下文确定其真假 5 是命题 3 分类命题有两种类型 原子命题和复合命题 1 原子命题 不能分解为更简单的陈述句 2 复合 分子 命题 由联结词 标点符号和原子命题复合构成的命题 前面例子中的 1 2 3 4 6 是原子命题 5 是复合命题 三 命题的表示法1 命题标识符 表示命题的符号称为命题标识符 在数理逻辑中 使用大写字母 或带下标的大写字母 或用方括号括起的数字表示命题 例 P 今天下雨 今天下雨 是一个命题 P是命题标识符 A1 今天下雨 12 今天下雨 A1 12 也是命题标识符 2 命题常量 一个命题标识符如表示确定的命题 就称为命题常量 3 命题变元 如果命题标识符只表示任意命题的位置标志 就称为命题变元 命题变元可以表示任意命题 所以它不能确定真值 故命题变元不是命题 当命题变元用一个特定命题取代时 才能确定真值 这称为对命题变元进行指派 4 原子变元 当命题变元表示原子命题时 该变元称为原子变元 四 小结学习本节要掌握下列概念 命题能表达判断的语句 并具有确定真值的陈述句 真值一个命题总具有一个 值 称为真值 真值只有真和假两种 分别记为T和F 原子命题不能分解为更简单的陈述句 称为原子命题 复合命题由联结词 标点符号和原子命题复合构成的命题 称为复合命题 复合命题亦称分子命题 命题标识符表示命题的符号 命题常量一个命题标识符表示确定的命题 该标识符称作命题常量 命题变元题标识符如仅是表示任意命题的位置标志 就成为命题变元 原子变元当命题变元表示原子命题时 该变元称原子变元 1 2联结词 要求 熟练掌握命题的联结词及其真值表 在数理逻辑中 复合命题是由原子命题与逻辑联结词组合而成 命题的连接方式叫做命题联结词或命题运算符 联结词是复合命题中的重要组成部分 为了便于书写和进行推演 必须对联结词作出明确规定并符号化 我们主要讨论下述五种联结词 亦称真值联结词 逻辑联结词或逻辑运算符 借助它们组成复合命题 1 否定 Negation 一元联结词 1 定义定义1 2 1设P为一命题 P的否定是一个新的命题 记作 P 若P为T P为F 若P为F P为T 联结词 表示命题的否定 称为否定联结词或否定词 读作 非 或 not 否定联结词有时亦可记作 2 真值表表1 2 1 命题P与其否定 P的关系如表1 2 1所示 否定 的意义仅是修改了命题的内容 它是一个一元运算 我们仍把它看作为联结词 自然语言中的 不 无 没有 等词在命题演算中常与 非 相当 例 P 今天下雨 P 今天不下雨 P 今天无雨 P 今天没有下雨 P 上海是一个大城市 P 上海不是一个大城市 P 上海是一个不大的城市 练习 P 一个世纪是一百年 写出 P 2 合取 Conjunction 二元联结词 1 定义定义1 2 2两个命题P和Q的合取是一个复合命题 记作P Q 当且仅当P Q同时为T时 P Q为T 在其他情况下 P Q的真值都是F 联结词 称为合取词 读作 和 或 and 2 真值表联结词 的定义如表1 2 2所示 表1 2 2 表1 2 2中给出复合命题P Q为T当且仅当P Q同时为T 与 和 有相同意义的汉字还有 与 以及 并且 而且 等 例 P 今天下雨 Q 明天下雨 上述命题的合取为P Q 今天下雨而且明天下雨 P Q 今天与明天都下雨 P Q 这两天都下雨 显然只有当 今天下雨 与 明天下雨 都是真时 这两天都下雨 才是真的 合取的概念与自然语言中的 与 意义相似 但并不完全相同 例如P 我们去看电影 Q 房间里有十张桌子 上述命题的合取为P Q 我们去看电影与房间里有十张桌子 在自然语言中 上述命题是没有意义的 因为P与Q没有内在联系 但作为数理逻辑中P和Q的合取P Q来说 它仍可成为一个新的命题 只要按照定义 在P Q分别取真值后 P Q的真值也必确定 例如 P 1 1 2Q 地球是行星 P Q 1 1 2与地球是行星 P Q的真值为T P 1 1 2Q 地球是恒星 P Q 1 1 2与地球是恒星 P Q的真值为F P 1 1 3Q 地球是行星 P Q 1 1 3与地球是行星 P Q的真值为F P 1 1 3Q 地球是恒星 P Q 1 1 3与地球是恒星 P Q的真值为F 命题联结词 合取 甚至可以将两个互为否定的命题联结在一起 这时 其真值永为F P 今天下雨 Q 今天不下雨 此时Q既是 P P Q 今天下雨与今天不下雨 P Q的真值为F 命题联结词 合取 也可以将若干个命题联结在一起 合取 是一个二元运算 注意 并非所有的 和 与 并且 均可用 表示 例如 李华和张南是表兄弟 王丽与王萍是堂姐妹 他打开箱子并且取出一件衣服来 这三句中的 和 与 并且 就不能用 表示 练习 P 一个世纪是一百年 Q 4是偶数 写出P Q并确定其真值 3 析取 Disjunction 二元联结词 1 定义定义1 2 3两个命题P和Q的析取是一个复合命题 记作P Q 当且仅当P Q同时为F时 P Q为F 否则P Q的真值为T 联结词 称为析取词 读作 或 或 or 2 真值表联结词 的定义如表1 2 3所示 表1 2 3 表1 2 3中给出复合命题P Q为F当且仅当P Q同时为F 例 P 灯泡坏了 Q 开关坏了 上述命题的析取为P Q 灯泡坏了或开关坏了 并非所有的 或 可用 表示 例如 我向东行或向西行 该语句中的 或 称为 排斥或 因为事实上一个人不会既向东行 又向西行 析取 指的是 可兼或 例如 他可能是100米或400米赛跑的冠军 这里P 他可能是100米赛跑的冠军 Q 他可能是400米赛跑的冠军 P Q 他可能是100米或400米赛跑的冠军 还有一些汉语中的 或 字实际上不是命题联结词 例如 他昨天做了二十或三十道习题 这里的 或 字只表示了习题的近似数目 不能用联结词 表达 练习 P 雪是黑的 Q 4是偶数 写出P Q并确定其真值 4 条件 Condition 二元联结词 1 定义定义1 2 4给定两个命题P和Q 其条件命题是一个复合命题 记作P Q 读作 如果P 那么Q 或 若P则Q 当且仅当P的真值为T Q的真值为为F时 P Q的真值为F 否则P Q的真值为T 我们称P为前件 Q为后件 2 真值表联结词 的定义如表1 2 4所示 表1 2 4 例1如果某动物为哺乳动物 则它必胎生 例2如果我得到这本小说 那么我今夜就读完它 例3如果雪是黑的 那么太阳从西方出 上述三个例子都可用条件命题P Q表达 在例1中 P 某动物为哺乳动物 Q 它必胎生 例1表示为P Q 在例2中 P 我得到这本小说 Q 我今夜就读完它 P的真值为T Q的真值为T P Q的真值为T 如果P的真值为T Q的真值为F P Q的真值为F 如果P的真值为F Q的真值为T P Q的真值为T 如果P的真值为F Q的真值为F P Q的真值为T 在例3中 P 雪是黑的 Q 太阳从西方出 P的真值为F Q的真值为F P Q的真值为T 在自然语言中 如果 与 那么 之间常常是有因果联系的 否则就没有意义 但对条件命题P Q来说 只要P Q能够分别确定真值 P Q即成为命题 此外 自然语言中对 如果 则 这样的语句 当前提为假时 结论不管真假 这个语句的意义 往往无法判断 而在条件命题中 规定为 善意的推定 即前提为F时 条件命题的真值都取为T 在数学上和有些逻辑学的书籍中 若P则Q 亦可叫作蕴含Q 而本书在条件命题中将避免使用 蕴含 一词 因为在以后将另外定义 蕴含 这个概念 命题联结词 亦可记作 2 真值表联结词 的定义可如表1 2 5所示 5 双条件 DoubleCondition 二元联结词 1 定义定义1 2 5给定两个命题P和Q 其复合命题PQ称作双条件命题 读作 P当且仅当Q 当P和Q的真值相同时 PQ的真值为T 否则PQ的真值为F 表1 2 5 例1两个三角形全等 当且仅当它们的三组对应边相等 例2燕子飞回南方 春天来了 例32 2 4当且仅当雪是白的 上面三个例子都可用双条件命题PQ来表示 与前面的联结词一样 双条件命题也可以不顾其因果联系 而只根据联结词定义确定真值 双条件联结词亦可记作 或 iff 它亦是二元运算 应强调指出的是 复合命题的真值只取决于各原子命题的真值 而与它们的内容 含义无关 与原子命题之间是否有关系无关 理解和掌握这一点是至关重要的 小结 本节给出了如下五种联结词的定义 否定设P为一命题 P的否定是一个新的命题 记作 P 若P为T P为F 若P为F P为T 合取两个命题P和