离散数学第一章.pdf

命题与联结词命题公式及其赋值 离散数学 2016 02 2017 01 第 1 章命题逻辑的基本概念 陈寅计算机学院 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 参考书目 数理逻辑 A Mathematical Introduction to Logic Herbert B Enderton 沈复兴 陈磊 孙运传译 面向计算机科学的数理逻辑 第二版 陆钟万著 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 命题逻辑 第 1 章到第 3 章 命题逻辑 全称量词 存在量词 一阶逻辑 基本概念命题与连接词公式及赋值 等值演算等值式范式 完备集 可满足性问题 推理理论自然推理系统 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 本章的主要内容 1命题与联结词 命题 命题的符号化 2命题公式及其赋值 命题公式 公式的赋值和真值表 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 本章的主要内容 1命题与联结词 命题 命题的符号化 2命题公式及其赋值 命题公式 公式的赋值和真值表 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 本章的主要内容 1命题与联结词 命题 命题的符号化 2命题公式及其赋值 命题公式 公式的赋值和真值表 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 命题 命题 proposition 判断结果唯一的陈述句 命题的真值 判断的结果 真值的取值 真与假 真值为真的命题称为真命题 真值为假的命题称为假命题 感叹句 祈使句 疑问句都不是命题 陈述句中的悖论 判断结果不惟一确定的不是命题 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 命题 例子 4 是素数 5 是无理数 x y 其中 x 和 y 是任意两个数 火星上有水 2050 年元旦下大雪 大于 4 的偶数等于两个素数之和 大于 2 吗 请不要吸烟 这朵花真美丽啊 我正在说假话 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 命题 例子 4 是素数 是 假命题 5 是无理数 是 真命题 x y 其中 x 和 y 是任意两个数 否 真值不唯一 火星上有水 是 真假未知 2050 年元旦下大雪 是 真假未知 大于 4 的偶数等于两个素数之和 是 真假未知 大于 2 吗 否 疑问句 请不要吸烟 否 祈使句 这朵花真美丽啊 否 感叹句 我正在说假话 否 悖论 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 本章的主要内容 1命题与联结词 命题 命题的符号化 2命题公式及其赋值 命题公式 公式的赋值和真值表 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 命题的符号化 命题分类 不能被分解成更简单的命题称为简单命题或原子命题 由简单命题通过联结词联结而成的命题称为复合命题 1 2 是有理数 2 2 是素数 3 2 是偶数 4 3 是素数 5 4 是素数 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 命题的符号化 命题分类 不能被分解成更简单的命题称为简单命题或原子命题 由简单命题通过联结词联结而成的命题称为复合命题 1 2 是有理数是不对的 2 2 是偶素数 3 2 或 4 是素数 4 如果 2 是素数 则 3 也是素数 5 2 是素数当且仅当 3 也是素数 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 命题的符号化 简单命题 用小写字母表示简单命题 例如 p q r p1 p2 pi pn 1 pn 其中 i n 为正整数 用 1 表示真 0 表示假 1 p 2 是有理数 2 q 2 是素数 3 r 2 是偶数 4 s 3 是素数 5 t 4 是素数 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 命题的复合 例子 p 2 是有理数 q 2 是素数 r 2 是偶数 s 3 是素数 t 4 是素数 1 2 是有理数是不对的 2 2 是偶素数 3 2 或 4 是素数 4 如果 2 是素数 则 3 也是素数 5 2 是素数当且仅当 3 也是素数 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 命题的复合 例子 p 2 是有理数 q 2 是素数 r 2 是偶数 s 3 是素数 t 4 是素数 1 2 是有理数是不对的 非p 2 2 是偶素数q并且r 3 2 或 4 是素数q或者t 4 如果 2 是素数 则 3 也是素数如果q 则s 5 2 是素数当且仅当 3 也是素数q当且仅当s 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 联结词 否定 否定 negation 设 p 为命题 复合命题 非 p 或 p 的否定 称为 p 的 否定式 记作 p 符号 称作否定联结词 并规定 p 为真 当且仅当 p 为假 例如 p 2 是有理数 则 p 2 是有理数是不对的 p 2 不是有理数 p p 10 01 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 联结词 合取 合取 conjunction 设 p q 为两个命题 复合命题 p 并且 q 或 p 与 q 称为 p 与 q 的合取式 记作p q 称作合取联结词 并规 定 p q 为真当且仅当 p 与 q 同时为真 可以描述合取联结词的自然语言 既 又 不但 而且 虽然 但是 一面 一面 分清简单命题与复合命题 不要 见到 与 或 和 就使用合取 pqp q 111 100 010 000 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 合取 例子 将下列命题符号化 1 吴颖既用功又聪明 2 吴颖不仅用功而且聪明 3 吴颖虽然聪明 但不用功 4 张辉与王丽都是三好学生 5 张辉与王丽是同学 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 合取 例子 将下列命题符号化 1 吴颖既用功又聪明 2 吴颖不仅用功而且聪明 3 吴颖虽然聪明 但不用功 4 张辉与王丽都是三好学生 5 张辉与王丽是同学 p 吴颖用功 q 吴颖聪明 r 张辉是三好学生 s 王丽是三好学生 t 张辉与王丽是同学 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 合取 例子 将下列命题符号化 1 吴颖既用功又聪明 p q 2 吴颖不仅用功而且聪明 p q 3 吴颖虽然聪明 但不用功 q p 4 张辉与王丽都是三好学生 r s 5 张辉与王丽是同学 t p 吴颖用功 q 吴颖聪明 r 张辉是三好学生 s 王丽是三好学生 t 张辉与王丽是同学 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 联结词 析取 析取 disjunction 设 p q 为两个命题 复合命题 p 或 q 称作 p 与 q 的析 取式 记作p q 称作析取联结词 并规定 p q 为假当且 仅当 p 与 q 同时为假 自然语言中的 或 具有二义性 相容或 联结的命题具有相容性 排斥或 联结的命题具有排斥性 pqp q 111 101 011 000 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 析取 例子 将下列命题符号化 1 张晓静爱唱歌或爱听音乐 2 张晓静只能挑选 202 或 203 房间 3 张晓静是江西人或安徽人 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 析取 例子 将下列命题符号化 1 张晓静爱唱歌或爱听音乐 2 张晓静只能挑选 202 或 203 房间 3 张晓静是江西人或安徽人 简单命题的符号化 p 张晓静爱唱歌 q 张晓静爱听音乐 相容或 两个命题可以同时成立 符号化 p q 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 析取 例子 将下列命题符号化 1 张晓静爱唱歌或爱听音乐 2 张晓静只能挑选 202 或 203 房间 3 张晓静是江西人或安徽人 简单命题的符号化 r 张晓静挑选 202 房间 s 张晓静挑选 203 房间 排斥或 两个命题只能有一个成立 符号化 r s r s 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 析取 例子 将下列命题符号化 1 张晓静爱唱歌或爱听音乐 2 张晓静只能挑选 202 或 203 房间 3 张晓静是江西人或安徽人 简单命题的符号化 t 张晓静是江西人 u 张晓静是安徽人 排斥或 这两个简单命题本身具有排斥性 符号化 t u t u 或 t u 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 联结词 蕴涵 蕴涵 implication 设 p q 为两个命题 复合命题 如果 p 则 q 称作 p 与 q 的蕴涵式 记作p q 并称 p 是蕴涵式的前件 q 为蕴 涵式的后件 称作蕴涵联结词 规定 p q 为假当且 仅当 p 为真 q 为假 p q 的逻辑关系 q 为 p 的必要条件 p 和 q 之间可以没有任何内在联系 如果 p 则 q 有很多的表述方法 若 p 就 q 只要 p 就 q p 仅当 q 只有 q 才 p 除非 q 才 p pqp q 111 100 011 001 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 蕴涵 例子 1 设 p 天冷 q 小王穿羽绒服 将下列命题符号化 1 只要天冷 小王就穿羽绒服 2 因为天冷 所以小王穿羽绒服 3 若小王不穿羽绒服 则天不冷 4 只有天冷 小王才穿羽绒服 5 除非天冷 小王才穿羽绒服 6 除非小王穿羽绒服 否则天不冷 7 如果天不冷 则小王不穿羽绒服 8 小王穿羽绒服仅当天冷的时候 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 蕴涵 例子 1 设 p 天冷 q 小王穿羽绒服 将下列命题符号化 1 只要天冷 小王就穿羽绒服 p q 2 因为天冷 所以小王穿羽绒服 p q 3 若小王不穿羽绒服 则天不冷 p q 4 只有天冷 小王才穿羽绒服 q p 5 除非天冷 小王才穿羽绒服 q p 6 除非小王穿羽绒服 否则天不冷 p q 7 如果天不冷 则小王不穿羽绒服 q p 8 小王穿羽绒服仅当天冷的时候 q p 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 蕴涵 例子 2 设 p 3 3 6 q 雪是白的 将下列命题符号化 并指 出其真值 1 如果 3 3 6 则雪是白的 2 如果 3 3 6 则雪是白的 3 如果 3 3 6 则雪不是白的 4 如果 3 3 6 则雪不是白的 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 蕴涵 例子 2 设 p 3 3 6 q 雪是白的 将下列命题符号化 并指 出其真值 1 如果 3 3 6 则雪是白的 2 如果 3 3 6 则雪是白的 3 如果 3 3 6 则雪不是白的 4 如果 3 3 6 则雪不是白的 1 p q 真值为 1 2 p q 真值为 1 3 p q 真值为 0 4 p q 真值为 1 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 蕴涵 例子 3 设 a 是一个正整数 r a 能被 4 整除 s a 能被 2 整除 将下列命题符号化 并指出其真值 1 只要 a 能被 4 整除 则 a 一定能被 2 整除 2 a 能被 4 整除 仅当 a 能被 2 整除 3 除非 a 能被 2 整除 a 才能被 4 整除 4 除非 a 能被 2 整除 否则 a 不能被 4 整除 5 只有 a 能被 2 整除 a 才能被 4 整除 6 只有 a 能被 4 整除 a 才能被 2 整除 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 蕴涵 例子 3 设 a 是一个正整数 r a 能被 4 整除 s a 能被 2 整除 将下列命题符号化 并指出其真值 1 只要 a 能被 4 整除 则 a 一定能被 2 整除 2 a 能被 4 整除 仅当 a 能被 2 整除 3 除非 a 能被 2 整除 a 才能被 4 整除 4 除非 a 能被 2 整除 否则 a 不能被 4 整除 5 只有 a 能被 2 整除 a 才能被 4 整除 6 只有 a 能被 4 整除 a 才能被 2 整除 1 5 r s 真值为 1 6 s r 真值为未知 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 联结词 等价 等价 equivalent 设 p q 为两个命题 复合命题 p 当且仅当 q 称作 p 与 q 的等价式 记作p q 称作等价联结词 规定 p q 为真当且仅当 p 与 q 同时为真或同时为假 p q 的逻辑关系 q 为 p 的充分必要 条件 p q q p 与 p q 的逻辑关 系是完全一致的 pqp q 111 100 010 001 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 等价 例子 将下列命题符号化 并指出其真值 1 2 2 4 当且仅当 3 3 6 2 2 2 4 当且仅当 3 是偶数 3 2 2 4 当且仅当太阳从东方升起 4 2 2 4 当且仅当美国位于非洲 5 函数 f x 在 x0可导的充要条件是它在 x0连续 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 等价 例子 将下列命题符号化 并指出其真值 1 2 2 4 当且仅当 3 3 6 1 2 2 2 4 当且仅当 3 是偶数 0 3 2 2 4 当且仅当太阳从东方升起 1 4 2 2 4 当且仅当美国位于非洲 0 5 函数 f x 在 x0可导的充要条件是它在 x0连续 0 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 联结词集 构成一个联结词集 由上述联结词集中的一个联结词联结一个或两个原子 命题组成的复合命题是最简单的复合命题 称为基本的 复合命题 基本的复合命题的真值如下 pq pp qp qp qp q 0010011 0110110 1000100 1101111 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 复合命题 多次使用联结词可以组成更为复杂的复合命题 本书约定联结词的优先级为 可以在复合命题中使用成对出现的括号 和 来改 变优先顺序 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 复合命题 例子 令 p 北京比天津人口多 q 2 2 4 r 乌鸦是白色的 求下列复合命题的真值 1 p q p q r 2 q r p r 3 p r p r 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 复合命题 例子 令 p 北京比天津人口多 q 2 2 4 r 乌鸦是白色的 求下列复合命题的真值 1 p q p q r1 2 q r p r 1 3 p r p r 0 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 本章的主要内容 1命题与联结词 命题 命题的符号化 2命题公式及其赋值 命题公式 公式的赋值和真值表 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 本章的主要内容 1命题与联结词 命题 命题的符号化 2命题公式及其赋值 命题公式 公式的赋值和真值表 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 命题公式 简单命题是命题逻辑中最基本的研究单位 也称为命题 常项或命题常元 称真值可以变化的陈述句为命题变项或命题变元 常项和变项均可用 p q r pi qi ri 表示 将命题变项用联结词和圆括号按一定的逻辑关系联结 起来的符号串称为合式公式或命题公式或公式 以下的符号串是公式吗 p q p q r p q p q r 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 合式公式 合式公式 well formed formula wff 定义如下 1 单个命题变项是合式公式 并称为原子命题公式 2 若 A 是合式公式 则 A 也是合式公式 3 若 A 和 B 是合式公式 则 A B A B A B A B 也是合式公式 4 有限次地应用 1 3 形成的符号串是合式公式 上面的定义方式称为归纳定义或递归定义方式 定义中使用了 A B 等符号 用来表示任意的合式公 式 而不是某个具体的公式 A B 等符号被称作元语言符号 p q 等被称作对象语 言符号 这是两个不同层次的符号 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 合式公式 例子 1 p 2 p q 3 p q r 4 p q r 5 p q r s p 最外层的括号总是可以省略的 公式中不影响联结词的优先级的括号可以省去 例如 3 可以写成 p q r 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 公式的层次 1 若公式 A 是单个的命题变项 则称 A 为 0 层公式 2 称 A 是 n 1 n 0 层公式是指下面情况之一 a A B B 是 n 层公式 b A B C 其中 B C 分别为 i j 层 且 n max i j c A B C 其中 B C 分别为 i j 层 且 n max i j d A B C 其中 B C 分别为 i j 层 且 n max i j e A B C 其中 B C 分别为 i j 层 且 n max i j 3 若公式 A 的层次为 k 则称 A 是k 层公式 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 公式的层次 例子 1 p 2 p q 3 p q r 4 p q r 5 p q r s p 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 公式的层次 例子 1 p0 2 p q1 3 p q r2 4 p q r3 5 p q r s p 4 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 公式的层次 例子 p q r s p 0 1 2 3 4 q p rsp 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 本章的主要内容 1命题与联结词 命题 命题的符号化 2命题公式及其赋值 命题公式 公式的赋值和真值表 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 公式的解释 在命题公式中 由于有命题变项 因而真值是不确定的 如果将公式中出现的全部命题变项都解释成具体的命 题常项之后 公式就是真值确定的命题了 将命题变项解释成真命题 相当于指定它的真值为 1 解释成假命题 相当于指定它的真值为 0 考虑公式 p q r 将 p q r 分别指定为 1 p 2 是素数 q 3 是偶数 r 是无理数 2 p 2 是素数 q 3 是偶数 r 是有理数 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 公式的赋值 设 p1 p2 pn是出现在公式 A 中的全部命题变项 给 p1 p2 pn各指定一个真值 1 或 0 称为对 A 的一个赋值或解释 若指定的一组值使得 A 为 1 则称为 A 的成真赋值 若指定的一组值使得 A 为 0 则称为 A 的成假赋值 含有 n 个命题变项的公式有 2n个赋值 A 中出现的命题变项为 p1 p2 pn 则 A 的赋值 1 2 n是指 p1 1 p2 2 pn n 其中 i 为 0 或 1 i 1 2 n A 中出现的命题变项 字母序 为 p q r 则 A 的 赋值 1 2 n是指 p 1 q 2 r 3 其中 i为 0 或 1 i 1 2 n 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 公式的赋值 例子 p1 p2 p3 p1 p2 000 p1 0 p2 0 p3 0 是一个成真赋值 110 p1 1 p2 1 p3 0 是一个成真赋值 001 p1 0 p2 0 p3 1 是一个成假赋值 011 p1 0 p2 1 p3 1 是一个成假赋值 p q r 011 p 0 q 1 r 1 是一个成真赋值 100 p 1 q 0 r 0 是一个成假赋值 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 公式的真值表 将命题公式 A 在所有赋值下取值情况列成表 称为 A 的真 值表 公式的真值表可以用如下的方式构造 1 找出公式的所有命题变项 列出所有的赋值 2 按从低到高的顺序写出公式的各个层次 3 对应各个赋值计算出各层次的真值 直到最后计算出 公式的真值 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 真值表 例子 写出如下公式的真值表 并求出它们的成真和成假赋值 p q r p p q q p q q r 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 真值表 例子 p q r pqr p r p q p q r 0001101 0011001 0101111 0111010 1000101 1010001 1100101 1110001 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 真值表 例子 p p q q pq p qp pq q p p q q 0011001 0110001 1001001 1100001 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 真值表 例子 p q q r pqrp q p q p q q p q q r 0001000 0011000 0101000 0111000 1000100 1010100 1101000 1111000 陈寅2016 2017华南师范大学 命题与联结词命题公式及其赋值 重言式 永真式 可满足式 设 A 为任一命题公式 若 A 在它的各种赋值下取值均为真 则称 A 是重言 式或永真式 若 A 在它的各种赋值下取值均为假 则称 A 是矛盾 式或永假式 若 A 不是矛盾式 则称 A 是可满足式 A 是可满足式 当且仅当 A 至少