天津理工大学《离散数学》教学教案(第一章).pdf

天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 1 第第 1 章章 命题逻辑命题逻辑 学习目标 学习目标 1 理解命题 命题的真值 简单命题 复合命题 命题公式 真值表 等 价公式 重言式 矛盾式 蕴涵式 主 析取范式 主 合取范式等概念 2 深刻理解九种联结词 否定 合取析取条件双条件异或 与非或非 c条件否定 的定义 3 熟练掌握命题公式的翻译 命题公式的类型的判别及命题定律 4 熟练掌握命题公式的 主 析取范式 主 合取范式的求法 5 熟练掌握证明两个命题公式等价的真值表法 等值演算法和主范式方法 6 熟练掌握推理证明的直接证法和间接证法 主要内容 主要内容 1 命题及其表示 2 逻辑联结词 否定 合取 析取 条件 双条件 异或 与非 或非 c条件否定 3 命题公式与翻译 4 真值表与等价公式 5 命题公式的分类与蕴含式 6 最小功能完备联结词组 7 命题公式的范式 8 推理理论 重点 重点 1 五种逻辑联结词 否定 双条件条件析取合取 2 命题公式的主析取范式 主合取范式 3 推理证明的直接证法和间接证法 难点 难点 1 命题公式的主析取范式 主合取范式的求法 2 推理证明的间接证法 教学手段 教学手段 通过多个实例的精讲帮助同学理解重点和难点的内容 并通过大量的练习使 同学们巩固和掌握命题公式翻译的技巧 证明两个命题公式等价的方法 命题公 式的主析取范式 主合取范式的求法及推理证明的直接证法和间接证法 习题 习题 习题 1 1 2 习题 1 2 2 习题 1 3 2 习题 1 4 1 2 4 2 2 4 4 习题 1 5 1 2 2 4 3 6 8 习题 1 6 2 4 习题 1 7 2 4 6 1 8 习题 1 8 1 2 4 6 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 2 1 1 命题及其表示命题及其表示 1 1 1命题的基本概念命题的基本概念 数理逻辑研究的中心问题是推理 Inference 而推理就必然包含前提和结论 前提和 结论都是表达判断的陈述句 因而表达判断的陈述句就成为推理的基本要素 在数理逻辑中 将能够判断真假的陈述句称为命题 因此命题就成为推理的基本单位 定义定义 1 1 1 能够判断真假的陈述句称为命题 Proposition 命题的判断结果称为命题的 真值 常用 T True 或 1 表示真 F False 或 0 表示假 真值为真的命题称为真命题 真值为假的命题称为假命题 从上述的定义可知 判定一个句子是否为命题要分为两步 一是判定是否为陈述句 二 是能否判定真假 二者缺一不可 例例 1 1 1 判断下列句子是否为命题 1 北京是中国的首都 2 请勿吸烟 3 雪是黑的 4 明天开会吗 5 x y 5 6 我正在说谎 7 9 5 12 8 1 101 110 9 今天天气多好啊 10 别的星球上有生物 解解 在上述的十个句子中 2 9 为祈使句 4 为疑问句 5 6 虽然是陈述 句 但 5 没有确定的真值 其真假随 x y 取值的不同而有改变 6 是悖论 Paradox 即由真能推出假 由假也能推出真 因而 2 4 5 6 9 均不是命题 1 3 7 8 10 都是命题 其中 10 虽然现在无法判断真假 但随着科技的进步 是可以判定真假的 需要进一步指出的是 命题的真假只要求它有就可以 而不要求立即给出 如例 1 1 1 的 8 1 101 110 它的真假意义通常和上下文有关 当作为二进制的加法时 它是真命题 否则为假命题 还有的命题的真假不能马上给出 如例 1 1 1 的 10 但它确实有真假意 义 1 1 2 命题分类命题分类 根据命题的结构形式 命题分为原子命题和复合命题 定义定义 1 1 2 不能被分解为更简单的陈述语句的命题称为原子命题 Simple Proposition 由两个或两个以上原子命题组合而成的命题称为复合命题 Compound Proposition 例如 例 1 1 1 中的命题全部为原子命题 而命题 小王和小李都去公园 是复合命题 是由 小王去公园 与 小李去公园 两个原子命题组成的 1 1 3命题标识符命题标识符 定义定义 1 1 3 表示原子命题的符号称为命题标识符 Identifier 通常用大写字母 A B C P Q 等表示命题 如 P 今天下雨 命题标识符依据表示命题的情况 分为命题常元和命题变元 一个表示确定命题的标识 符称为命题常元 或命题常项 Propositional constant 没有指定具体内容的命题标识符称 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 3 为命题变元 或命题变项 Propositional Variable 命题变元的真值情况不确定 因而命题 变元不是命题 只有给命题变元 P 一具体的命题取代时 P 有了确定的真值 P 才成为命题 1 2 逻辑联结词逻辑联结词 本节主要介绍 5 种常用的逻辑联结词 Logical Connectives 分别是 非 否定联结 词 与 合取联结词 或 析取联结词 若 则 条件联结词 当且仅当 双条件联结词 通过这些联结词可以把多个原子命题复合成一个复合命题 1 2 1 否定联结词否定联结词 定义定义 1 2 1 设 P 为一命题 P 的否定 Negation 是一个新的命题 记为P 读作非 P 规定若 P 为 T 则P 为 F 若 P 为 F 则P 为 T P 的取值情况依赖于 P 的取值情况 真值情况见表 1 1 表表 1 1 P P 1 0 0 1 在自然语言中 常用 非 不 没有 无 并非 等来表示否定 例例 1 2 1 P 上海是中国的城市 P 上海不是中国的城市 P 是真命题 P 是假命题 Q 所有的海洋动物都是哺乳动物 Q 不是所有的海洋动物都是哺乳动物 Q 为假 命题 Q 为真命题 1 2 2 合取联结词合取联结词 定义定义 1 2 2 设 P Q 为两个命题 P 和 Q 的合取 Conjunction 是一个复合命题 记为 P Q 读作 P 与 Q 称为 P 与 Q 的合取式 规定 P 与 Q 同时为 T 时 P Q 为 T 其余 情况下 P Q 均为 F 联结词 的定义见表 1 2 表表 1 2 联结词 联结词 的定义 的定义 P QP Q 0 00 0 10 1 00 1 11 显然 P P 的真值永远是假 称为矛盾式 在自然语言中 常用 既 又 不但 而且 虽然 但是 一边 一边 等表示合取 例例 1 2 2 1 今天下雨又刮风 设 P 今天下雨 Q 今天刮风 则 1 可表示为 P Q 2 猫吃鱼且太阳从西方升起 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 4 设 P 猫吃鱼 Q 太阳从西方升起 则 2 可表示为 P Q 3 张三虽然聪明但不用功 P 张三聪明 Q 张三用功 则 3 可表示为 P Q 需要注意的是 在自然语言中 命题 2 是没有实际意义的 因为 P 与 Q 两个命题是 互不相干的 但在数理逻辑中是允许的 数理逻辑中只关注复合命题的真值情况 并不关心 原子命题之间是否存在着内在联系 1 2 3 析取联结词析取联结词 定义定义 1 2 3 设 P Q 为两个命题 P 和 Q 的析取 Disjunction 是一个复合命题 记为 P Q 读作 P 或 Q 称为 P 与 Q 的析取式 规定当且仅当 P 与 Q 同时为 F 时 P Q 为 F 否 则 P Q 均为 T 析取联结词 的定义见表 1 3 表表 1 3 联结词 联结词 的定义 的定义 P Q P Q 0 0 0 0 1 1 1 0 1 1 1 1 显然PP 的真值永远为真 称为永真式 析取联结词 与汉语中的 或 二者表达的意义不完全相同 汉语中的 或 可 表达 排斥或 也可以表达 可兼或 而从析取联结词的定义可看出 允许 P Q 同时为真 因而析取联结词 是可兼或 对于 排斥或 将在 1 6 中论述 例例 1 2 3 1 小王爱打球或跑步 2 他身高 1 8m 或 1 85m 1 为可兼或 2 为排斥或 设 P 小王爱打球 Q 小王爱跑步 则 1 可表示为 P Q 设 P 他身高 1 8 米 Q 他身高 1 85 米 则 2 可表示为 P Q P Q 1 2 4 条件联结词条件联结词 定义定义 1 2 4 设 P Q 为两个命题 P 和 Q 的条件 Conditional 命题是一个复合命题 记 为 P Q 读作若 P 则 Q 其中 P 称为条件的前件 Q 称为条件的后件 规定当且仅当前 件 P 为 T 后件 Q 为 F 时 P Q 为 F 否则 P Q 均为 T 条件联结词 的定义见表 1 4 表表 1 4 联结词 联结词 的定义 的定义 P Q P Q 0 0 1 0 1 1 1 0 0 1 1 1 在自然语言中 常会出现的语句如 只要 P 就 Q 因为 P 所以 Q P 仅当 Q 只 有 Q 才 P 除非 Q 才 P 等都可以表示为 P Q 的形式 例例 1 2 4 1 如果雪是黑色的 则太阳从西方升起 2 仅当天气好 我才去公园 对于 1 设 P 雪是黑色的 Q 太阳从西方升起 则 1 可表示为 P Q 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 5 2 设 R 天气好 S 我去公园 则 2 可表示为 S R 1 2 5 双条件联结词双条件联结词 定义定义 1 2 5 设 P Q 为两个命题 其复合命题 P Q 称为双条件 Biconditional 命题 P Q 读作 P 当且仅当 Q 规定当且仅当 P 与 Q 真值相同时 P Q 为 T 否则 P Q 均为 F 双条件联结词 的定义如表 1 5 所示 表表 1 5 P Q P Q 0 0 1 0 1 0 1 0 0 1 1 1 例例 1 2 5 1 雪是黑色的当且仅当 2 2 4 2 燕子北回 春天来了 1 设 P 雪是黑色的 Q 2 2 4 则 1 可表示为 P Q 其真值为 T 2 设 R 燕子北回 S 春天来了 则 2 可表示为 R S 其真值为 T 与前面的联结词一样 条件联结词和双条件联结词连接的两个命题之间可以没有任何 的因果联系 只要能确定复合命题的真值即可 1 3 命题公式与翻译命题公式与翻译 1 3 1 命题公式命题公式 上一节介绍了 5 种常用的逻辑联结词 利用这些逻辑联结词可将具体的命题表示成符 号化的形式 对于较为复杂的命题 需要由这 5 种逻辑联结词经过各种相互组合以得到其符 号化的形式 那么怎样的组合形式才是正确的 符合逻辑的表示形式呢 定义定义 1 3 1 1 单个的命题变元是命题公式 2 如果A是命题公式 那么A 也是命题公式 3 如果A B是命题公式 那么 A B A B A B 和 A B 也是命题公式 4 当且仅当能够有限次地应用 1 2 3 所得到的包含命题变元 联结词 和括号的符号串是命题公式 又称为合式公式 或简称为公式 上述定义是以递归的形式给出的 其中 1 称为基础 2 3 称为归纳 4 称为界限 由定义知 命题公式是没有真假的 仅当一个命题公式中的命题变元被赋以确定的命题 时 才得到一个命题 例如在公式QP 中 把命题 雪是白色的 赋给P 把命题 2 2 4 赋给Q 则公式QP 被解释为假命题 但若P的赋值不变 而把命题 2 2 4 赋给Q 则公式QP 被解释为真命题 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 6 定义中的符号A B不同于具体公式里的P Q R等符号 它可以用来表示任意的 命题公式 例例 1 3 1 QP RQP RQQP 等都是命题公式 而 QP QP RQP 等都不是命题公式 为了减少命题公式中使用括号的数量 规定 1 逻辑联结词的优先级别由高到低依 次为 2 具有相同级别的联结词 按出现的先后次序进行计算 括 号可以省略 3 命题公式的最外层括号可以省去 例例 1 3 2 RQP 也可以写成RQP RQP 也可写成RQP RQP 也可写成RQP 而 RQP 中的括号不能省去 定义定义 1 3 2 设P是命题公式Q的一部分 且P也是命题公式 则称P为Q的子公式 例如QP 及R都是公式RQP 的子公式 P QP 及RP 都是公式 PQPR 的子公式 1 3 2 命题的符号化命题的符号化 有了命题公式的概念之后 就可以把自然语言中的一些命题翻译成命题逻辑中的符号化 形式 把一个文字描述的命题相应地写成由命题标识符 逻辑联结词和圆括号表示的命题形 式称为命题的符号化或翻译 命题符号化的一般步骤 1 明确给定命题的含义 2 找出命题中的各原子命题 分 别符号化 3 使用合适的逻辑联结词 将原子命题分别连接起来 组成复合命题的符号化 形式 把命题符号化 是不管具体内容而突出思维形式的一种方法 注意在命题符号化时 要 正确地分析和理解自然语言命题 不能仅凭文字的字面意思进行翻译 例例 1 3 3 张三或李四都可以做这件事 设P 张三可以做这件事 Q 李四可以做这件事 则命题符号化为 QP 而不是QP 例例 1 3 4 1 只有你走 我才留下 这个命题的意义也可以理解为 如果我留下了 那么你一定走了 设P 你走 Q 我留下 则命题符号化为 PQ 与原命题类似的命题如 仅当你走我才留下 我留下仅当你走 当我留下你得走 注意 在一般的命题表述中 仅当 是必要条件 译成条件命题时其后的命题是后件 而 当 是充分条件 译成条件命题时其后的命题是前件 2 仅当天不下雨且我有时间 我才上街 设P 天下雨 Q 我有时间 R 我上街 命题符号化为 QPR 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 7 3 你将失败 除非你努力 这个命题的意义可以理解为 如果你不努力 那么你将失败 设P 你努力 Q 你失败 则命题符号化为 QP 含有 除非 的命题 非 是充分条件 译成条件命题时 非 是条件的前件 4 A中没有元素 A就是空集 设P A中有元素 Q A是空集 则命题符号化为 QP 5 张三与李四是表兄弟 此命题是一个原子命题 与 是表兄弟 表示两个对象之间的关系 张三是表兄 弟 及 李四是表兄弟 都不是命题 所以上述命题只能符号化为P的形式 其中P 张三与李四是表兄弟 例例 1 3 5 将下列命题符号化 1 如果明天早上下雨或下雪 则我不去学校 2 如果明天早上不下雨且不下雪 则我去学校 3 如果明天早上不是雨夹雪 则我去学校 4 当且仅当明天早上不下雨且不下雪时 我才去学校 设P 明天早上下雨 Q 明天早上下雪 R 我去学校 1 符号化为 PQR 2 符号化为 RQP 3 符号化为 RQP 4 符号化为 RQP 例例 1 3 6 将下列命题符号化 1 如果小王和小张都不去 则小李去 2 如果小王和小张不都去 则小李去 设P 小王去 Q 小张去 R 小李去 1 符号化为 RQP 2 符号化为 RQP 或RQP 例例 1 3 7 将下列命题符号化 1 说离散数学无用且枯燥无味是不对的 2 若天不下雨 我就上街 否则在家 对于 1 设P 离散数学是有用的 Q 离散数学是枯燥无味的 则命题符号化为 QP 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 8 对于 2 设P 天下雨 Q 我上街 R 我在家 则命题符号化为 RPQP 通过上述的例题可以看出 要正确地将自然语言中的联结词翻译成恰当的逻辑联结词 必须要正确地理解各原子命题之间的关系 1 4 真值表与等价公式真值表与等价公式 1 4 1 真值表真值表 定义定义 1 4 1 设 1 P 2 P n P是出现在命题公式A中的全部命题变元 给 1 P 2 P n P各指定一个真值 称为对公式A的一个赋值 或解释或真值指派 若指定的一组值使公式A的真值为 1 则这组值称为公式A的成真赋值 若指定的一组值使公式A的真值为 0 则这组值称为公式A的成假赋值 例如 对公式RQP 赋值 011 即令 1 1 0 RQP 则可得到公式的真 值为 1 若赋值 000 则公式真值为 0 因此 011 为公式的一个成真赋值 000 为公式的一 个成假赋值 除了上述的两种赋值外 公式的赋值还有 000 001 等 一般的结论是在 含有 n 个命题变元的命题公式中 共有 n 2种赋值 定义定义 1 4 2 将命题公式A在所有赋值下的取值情况列成表 称为公式A的真值表 Truth Table 构造真值表的基本步骤 1 找出公式中所有的命题变元 1 P 2 P n P 按二进制从小到大的顺序列出 n 2 种赋值 2 当公式较为复杂时 按照运算的顺序列出各个子公式的真值 3 计算整个命题公式的真值 例例 1 4 1 写出下列公式的真值表 并求其成真赋值和成假赋值 1 QP 2 QQP 3 QPQP 解解 1 的真值表见表 1 6 表表 1 6 QP 的真值表的真值表 P Q P QP 001 1 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 9 011 1 100 0 110 1 成真赋值为 00 01 11 成假赋值为 10 2 的真值表见表 1 7 表表 1 7 QQP 的真值表的真值表 P Q QP QP QQP 0 0 1 0 0 0 1 1 0 0 1 0 0 1 0 1 1 1 0 0 无成真赋值 成假赋值为 00 01 10 11 3 的真值表见表 1 8 表表 1 8 QPQP 的真值表的真值表 P Q QP QP QP QPQP 0 0 0 1 1 1 0 1 0 1 1 1 1 0 0 1 1 1 1 1 1 0 0 1 成真赋值为 00 01 10 11 无成假赋值 1 4 2 等价公式等价公式 定义定义 1 4 3 给定两个命题公式BA 设 1 P 2 P n P是出现在命题公式BA 中的 全部命题变元 若给 1 P 2 P n P任一组赋值 公式A和B的真值都对应相同 则称 公式A与B等价或逻辑相等 Equivalence 记作A B 需要注意的是 不是逻辑联结词 因而 A B 不是命题公式 只是表示两 个命题公式之间的一种等价关系 即若A B A和B没有本质上的区别 最多只是A和 B具有不同的形式而已 具有如下的性质 1 自反性 A A 2 对称性 若A B 则B A 3 传递性 若A B B C 则A C 给定 n 个命题变元 根据公式的形成规则 可以形成许多个形式各异的公式 但是有很 多形式不同的公式具有相同的真值表 因此引入公式等价的概念 其目的就是将复杂的公式 简化 下面介绍两种证明公式等价的方法 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 10 1 真值表法 真值表法 由公式等价的定义可知 利用真值表可以判断任何两个公式是否等价 例例 1 4 2 证明 PQQPQP 证明证明 命题公式QP 与 PQQP 的真值表见表 1 9 由表 1 9 可知 在任意赋值下QP 与 PQQP 两者的真值均对应相同 因此 PQQPQP 表表 1 9 QP 与与 PQQP 的真值表的真值表 P Q QP PQ PQQP QP 0 01 1 1 1 0 11 0 0 0 1 00 1 0 0 1 11 1 1 1 例例 1 4 3 判断公式QP 与QP 二者是否等价 证明证明 公式QP 与QP 的真值表见表 1 10 表表 1 10 QP 与与QP 的真值表的真值表 P QQP QP 0 01 1 0 11 0 1 00 1 1 11 1 可见真值表中的最后两列值不完全相同 因此公式QP 与QP 不等价 从理论上来讲 利用真值表法可以判断任何两个命题公式是否等价 但是真值表法并 不是一个非常好的方法 因为当公式中命题变元较多时 其计算量较大 例如当公式中有四 个变元时 需要列出 4 2 16 种赋值情况 计算较为繁杂 因此 通常采用其他的证明方法 这种证明方法是先用真值表法验证出一些等价公式 再用这些等价公式来推导出新的等价公 式 以此作为判断两个公式是否等价的基础 下面给出 12 组常用的等价公式 它们是进一 步推理的基础 牢记并熟练运用这些公式是学好数理逻辑的关键之一 1 双重否定律 A A 2 结 合 律 CBACBA CBACBA 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 11 CBACBA 3 交换律 ABBA ABBA ABBA 4 分配律 CABACBA CABACBA 5 幂等律 AAA AAA 6 吸收律 ABAA ABAA 7 德 摩根律 BABA BABA 8 同一律 ATAAFA 9 零律 FFATTA 10 否定律 FAATAA 11 条件等价式 ABABBA 12 双条件等价式 BAABBABA 上述 12 组公式均可以通过构造真值表法来证明 2 等值演算法 等值演算法 定理定理 1 4 1 代入规则 代入规则 在一个永真式A中 任何一个原子命题变元R出现的每一处用 另一个公式代入 所得的公式B仍为永真式 证明 因为永真式对于任何指派 其真值都是 1 与每个命题变元指派的真假无关 所 以 用一个命题公式代入到原子命题变元R出现的每一处 所得到的命题公式的真值仍为 1 例如 RR 是永真式 将原子命题变元R用QP 代入后得到的式子 QPQP 仍为永真式 定理定理 1 4 2 置换规则 置换规则 设X是命题公式A的一个子公式 若YX 如果将公式A 中的X用Y来置换 则所得到的公式B与公式A等价 即BA 证明 因为YX 所以在相应变元的任一种指派情况下 X与Y的真值相同 故 以Y取代X后 公式B与公式A在相应的指派情况下真值也必相同 因此BA 例如QPQP 利用SR 置换P 则QSRQSR 从定理可以看出 代入规则是对原子命题变元而言 而置换规则可对命题公式进行 代入必须处处代入 替换可以部分或全部替换 代入规则可以用来扩大永真式的个数 替换 规则可以增加等价式的个数 有了上述的 12 组等价公式及代入规则和置换规则后 就可以推演出更多的等价式 由 已知等价式推出另外一些等价式的过程称为等值演算 Equivalent Calculation 例例 1 4 4 证明下列公式等价 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 12 1 RQP RQP 2 QPQPQPQP 证明证明 1 RQP RQP RQP RQP RQP RQP 2 QQPPQPQPQP PPQPPQQQ 1 1 QPPQ QPQP QPQP 例例 1 4 5 某件事情是甲 乙 丙 丁 4 人中某一个人干的 询问 4 人后回答如下 1 甲说是丙干的 2 乙说我没干 3 丙说甲讲的不符合事实 4 丁说是甲干的 若其中 3 人说的是真话 一人说假话 问是谁干的 解解 设A 这件事是甲干的 B 这件事是乙干的 C 这件事是丙干的 D 这 件事是丁干的 4 个人所说的命题分别用P Q R S表示 则 1 2 3 4 分别符号化 为 PDCBA QB RC SDCBA 则 3 人说真话 一人说假话的命题K符号化为 K SRQPSRQPSRQPSRQP 其中SRQP DACBDCBA DACBDDACBC DACBBDCBA A DCB 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 13 同理 SRQPSRQPSRQP 0 所以 当K为真时 DCBA 为真 即这件事是甲干的 本题也可以从题干直接找出相互矛盾的两个命题作为解题的突破口 甲 丙两人所说 的话是相互矛盾的 必有一人说真话 一人说假话 而 4 个人中只有一人说假话 因此乙 丁两人必说真话 由此可断定这件事是甲干的 例例 1 4 6 在某次球赛中 3 位球迷甲 乙 丙对某球队的比赛结果进行猜测 甲说 该球队不会得第一名 是第二名 乙说 该球队不会得第二名 是第一名 丙说 该球队不 会得第二名 也不会是第三名 比赛结束后 结果证实甲 乙 丙 3 人中有一人猜的全对 有一人猜对一半 有一人猜的全错 试分析该球队究竟是第几名 解解 设P 该球队获得第一名 Q 该球队获得第二名 R 该球队获得第三名 则 P Q R中必然有一个真命题 两个假命题 设甲 乙 丙 3 人所说的命题分别用 1 A 2 A 3 A表示 则有 1 AQP 2 AQP 3 ARQ 设甲 乙 丙的判断全对分别用 1 B 1 C 1 D表示 甲 乙 丙的判断对一半分别用 2 B 2 C 2 D表示 甲 乙 丙的判断全错分别用 3 B 3 C 3 D表示 则有 1 BQP 2 BQPQPQP 由于该球队不可能既是第一名又是第二 名 所以0 QP 3 BQP 1 CQP 2 CQPQPQP QPC 3 1 DRQ 2 D RQRQ RQD 3 0 甲 乙 丙 3 人中有一人全对 有一人猜对一半 有一人全错的命题K符号化为 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 14 231321 DCBDCBK 312 DCB 132 DCB 213 DCB 123 DCB 其中 00 321 QPQPDCB 同理 312 DCB 0 0 132 DCB 312 BCDPQQRQR PQRPQQR 0 RQP 由于该球队不可能既是第一名 又是第三名 0 123 DCB 因此 若K为真 只有RQPDCB 231 为真 因而Q为真命题 RP 为假命题 即该球队获得第二名 甲的判断全对 乙的判断全错 丙的判断对一半 例例 1 4 7 A B C D 4 人进行百米竞赛 观众甲 乙 丙对比赛的结果进行预 测 甲 C第一 B第二 乙 C第二 D第三 丙 A第二 D第四 比赛结束后发现 甲 乙 丙每个人的预测结果都各对一半 试问实际名次如何 假如无并列者 解解 设 i A表示A第i名 i B表示B第i名 i C表示C第i名 i D表示D第i名 1 2 3 4i 则由题意有 TBCBC 2121 1 TDCDC 3232 2 TDADA 4242 3 因为真命题的合取仍为真命题 所以 1 2 3221 DCBC 3221 DCBC 3221 DCBC 3221 DCBC 3221 DCBC 3221 DCBC 4 3 4 322142 DCBCDA 322142 DCBCDA 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 15 322142 DCBCDA 322142 DCBCDA TDCBCDA 322142 因此 A第二 B第四 C第一 D第三 1 5 命题公式的分类与蕴含式命题公式的分类与蕴含式 1 5 1 命题公式的分类命题公式的分类 从前述的真值表中可以看到 有的命题公式无论对命题欧变元作何种赋值 其对应的 真值恒为T或恒为F 如例 1 4 1 的 2 3 而有的公式对应的真值则是有T有F 如 例 1 4 1 的 1 根据命题公式在不同赋值下的真值情况 可以对命题公式进行分类 定义定义 1 5 1 设A为一命题公式 对公式A所有可能的赋值 1 若A的真值永为T 则称公式A为重言式 Tautology 或永真式 2 若A的真值永为F 则称公式A为矛盾式 Contradictory 或永假式 3 若至少存在一种赋值使得A的真值为T 则称公式A为可满足式 Satisfiable 由定义可知 根据命题公式的真值情况 公式可分为两大类 即矛盾式和可满足式 重言式一定是可满足式 但反之不成立 用真值表法可以判定公式的类型 若真值表的最后一列全为 1 则公式为重言式 若最 后一列全为 0 则公式为矛盾式 若最后一列至少有一个 1 则公式为可满足式 在 1 4 的 例 1 4 1 中 1 为可满足式 2 为矛盾式 3 为重言式 用真值表法判断公式的类型 方法简单 但当变元较多时 计算量大 在后面的章节中还要介绍其他的方法 1 5 2 重言式与矛盾式的性质重言式与矛盾式的性质 定理定理 1 5 1 任何两个重言式的析取或合取 仍是一个重言式 证明 设A B为两个重言式 则无论对A与B的分量作何种指派 总有TA TB 故TBA TBA 定理定理 1 5 2 一个重言式 对同一分量用任何合式公式置换 所得公式仍为一重言式 证明 因为重言式的真值与分量的指派无关 所以对同一分量用任何合式公式置换后 重言式的真值仍永为真 例如 PP 为一重言式 用RQ 置换P 所得新公式 RQRQ 仍为 重言式 对于矛盾式 也有类似于定理 1 5 1 和定理 1 5 2 的结果 定理定理 1 5 3 设A B为两个命题公式 BA 当且仅当BA 为重言式 证明 若BA 则在A B所含命题变元的任何指派下 A与B的真值都相同 即BA 恒为真 若BA 为重言式 由重言式的定义知 在对A B所含命题变元的任何指派下 A 与B都有相同的真值 即BA 例例 1 5 1 证明 PQQPQP 为重言式 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 16 证明证明 由例 1 4 2 知 PQQPQP 故依据定理 1 5 3 有 PQQPQP 为重言式 1 5 3 蕴含式蕴含式 下面讨论BA 的重言式 定义定义 1 5 2 设A B为两个命题公式 若BA 为重言式 则称 A蕴含 Implication B 记作BA 注意 与 一样 都不是逻辑联结词 因而BA 也不是公式 BA 是 用来表示由条件A能够推导出结论B 或称为B可以由A逻辑推出 蕴含关系具有如下的性质 1 自反性 对任意的公式P 有PP 2 反对称性 对任意的公式P Q 若QP 且PQ 则有QP 3 传递性 对任意的公式P Q R 若QP RQ 则有RP 由于BA 不具有对称性 即BA 与AB 不等价 因此 对于BA 而言 AB 称为它的逆换式 BA 称为它的反换式 AB 称为它的逆反式 在上 述的 4 个公式中 BA AB AB BA 定理定理 1 5 4 BA 的充分必要条件是BA 且AB 证明 若BA 则BA 为重言式 而BA ABBA 故 ABBA 且均为重言式 即BA 且AB 反之 若BA 且AB 则ABBA 且均为重言式 于是 ABBA 为重言式 即BA 为重言式 故BA 由定义 1 5 2 知 要证明BA 只需证明BA 为重言式即可 因此 前面介绍的 真值表法和等值演算法均可应用 下面综合介绍证明BA 的各种方法 1 真值表法 真值表法 例例 1 5 2 证明ABA 证明证明 只需证明ABA 为重言式 真值表见表 1 11 表表 1 11 ABA 的真值表的真值表 A BBA ABA 0 00 1 0 10 1 1 00 1 1 11 1 2 等值演算法 等值演算法 例例 1 5 3 证明QQPP 证明证明 只需证明QQPP 为重言式 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 17 QQPP QQPP QQPP QPQP 1 即QQPP 3 分析法 分析法 分析法包括以下两种形式 1 假定前件A为真 推出后件B为真 则BA 2 假定后件B为假 推出前件A为假 则BA 理由是 1 若A为真 则B可能为真也可能为假 但由假设推出B为真 所以否定 了A为真 B为假的可能 只能是A为真 B也为真 所以BA 为重言式 即BA 对于 2 若后件B为假 则前件A可能为真也可能为假 若A为真 B为假 则BA 为假 若A为假 B为假 则BA 为真 而由假设推知A为假 因此否定了A为真 B 为假的可能 所以BA 为重言式 即BA 例例 1 5 4 证明 1 PQPQ 2 QQPP 证明证明 1 假设前件 QPQ 为真 则Q 为真 QP 为真 由此有Q为假 P为真 因此PQPQ 2 假设后件Q为假 若P为真 则QP 为假 有 QPP 为假 若P为假 则QP 为真 有 QPP 为假 综上 若后件Q为假 无论P为真还是假 前件 QPP 均为假 因此 QQPP 需要指出的是 在例 1 5 4 的 2 中 因为不知道P的真值情况 所以要分情况讨论 例例 1 5 5 分析下列论证的有效性 条件 香烟有利于健康 如果香烟有利于健康 那么医生就会把香烟作为药品开给病人 结论 医生把香烟作为药品开给病人 解解 设P 香烟有利于健康 Q 医生把香烟作为药品开给病人 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 18 上述推理符号化为 QQPP 其证明同例 1 5 4 的 2 因此上述论证是有效的 下面给出的蕴含式其正确性均可用上述的推理方法进行证明 1 PQP 2 QQP 3 QPP 4 QPP 5 QPQ 6 PQP 7 QQP 8 QQPP 9 PQPQ 10 QQPP 11 RPRQQP 12 RRQRPQP 13 SQRPSRQP 14 RPRQQP 1 6 其它逻辑联结词和最小功能完备联结词组其它逻辑联结词和最小功能完备联结词组 1 6 1 其它逻辑联结词其它逻辑联结词 前面介绍了 5 种常用的逻辑联结词 和 但是这 5 种联结词还不能 很广泛地直接用来表达命题间的联系 为此 下面再介绍 4 种联结词 1 不可兼析取 不可兼析取 排斥或排斥或 异或异或 exclusive or 定义定义 1 6 1 设P Q为两个命题公式 复合命题QP 称为P异或Q 规定QP 的真 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 19 值为T 当且仅当P与Q的真值不相同 否则QP 的真值为F 联结词 的定义见表 1 12 表表 1 12 联结词 联结词 的定义 的定义 P Q QP 000 011 101 110 从真值表中易见 QP QPQP 利用真值表法 易证 具有如下性质 1 QP PQ 2 QP R RQP 3 RPQPRQP 4 QP QP 5 FPP PPF PPT 6 若QP R 则QRP PRQ 且RQP 为一矛盾式 2 与非联结词与非联结词 Nand 定义义 1 6 2 设P Q为两个命题公式 复合命题QP 称为P和Q的 与非式 当 且仅当P与Q的真值都为T时 QP 的真值为F 否则QP 的真值为T 联结词 的定义见表 1 13 表表 1 13 联结词 联结词 的定义 的定义 P QQP 001 011 101 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 20 110 从真值表中易见 QP QP 联结词 具有如下性质 1 PPPPP 2 QPQPQPQP 3 QPQPQPQQPP 3 或非联结词 或非联结词 Nor 定义定义 1 6 3 设P Q为两个命题公式 复合命题QP 称为P和Q的 或非式 当 且仅当P与Q的真值都为F时 QP 的真值为T 否则QP 的真值为F 联结词 的定义见表 1 14 表表 1 14 联结词 联结词 的定义 的定义 P QQP 001 010 100 110 从真值表中易见 QP QP 联结词 具有如下性质 1 PPPPP 2 QPQPQPQPQP 3 QPQPQPQQPP 4 条件否定联结词 条件否定联结词 Non conditional c 定义定义 1 6 4 设P Q为两个命题公式 复合命题QP c 称为P和Q的 条件否定 当且仅当P的真值为T Q的真值为F时 QP c 的真值为T 否则QP c 的真 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 21 值为F 联结词 c 的定义见表 1 15 表表 1 15 联结词 联结词 c 的定义 的定义 P QQP c 000 010 101 110 从真值表中易见 QP c QP 1 6 2 最小功能完备联结词组最小功能完备联结词组 到目前为止 共定义了 9 个联结词 但这些联结词在表达命题时并不是缺一不可 因 为包含某些联结词的公式可以用含有另外一些联结词的公式来进行表示 如 PQQPQP QPQP QPQP QPQP 这说明 可以转化为 而 可转化为由 与 表示 而 与 又可以相互转化 对于另外的 4 个联结词 由于 QPQP QP QP QP QP QP c QP 这说明任意的一个命题公式最终都可以 转化为仅包含 或 的命题公式来等价地表示 定义定义 1 6 5 设G是一个联结词的集合 若任意一个命题公式都可用G中联结词构成的 公式来表示 则称G为功能完备联结词组 如果在G中去掉任何一个联结词后都不再具有 这种性质 则称G为最小功能完备联结词组 简称为最小联结词组 可以证明 等都是功能完备联结词组 而 及 均为最小功能完备联结词组 由联结词 及 的性质知 联结词 和 可分别用 或 表示 所以 及 也是最小功能完备联结词组 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 22 通常为了命题表示的简洁清楚 常用包含 的联结词组来表示命题 1 7 对偶与范式对偶与范式 1 7 1对偶式与对偶原理对偶式与对偶原理 1 对偶式 对偶式 定义定义 1 7 1 在只含有逻辑联结词 的命题公式A中 若把 与 互换 T与F 互换得到一个新的命题公式 A 则称 A是A的对偶式 Dualistic Formula 或称 A与A互 为对偶式 显然AA 例例 1 7 1 写出下列公式的对偶式 1 RQP 2 TQP 3 SQPQP 解解 上述公式的对偶式为 1 RQP 2 FQP 3 SQPQP 例例 1 7 2 求QP QP 的对偶式 解解 因为QP QP 所以QP 的对偶式为QPQP 同理 QP 的对偶式为QP 2 对偶原理 对偶原理 Duality Principle 一个仅含有逻辑联结词 的命题公式和它的对偶式之间具有如下等值关系 定理定理 1 7 1 设公式A为仅含有逻辑联结词 及命题变元 1 P 2 P n P的命 题公式 A是A的对偶式 则有 1 21 21nn PPPAPPPA 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 23 2 21 21nn PPPAPPPA 证明 由德 摩根定律 QPQP QPQP 故 21 21nn PPPAPPPA 同理 21 21nn PPPAPPPA 例例 1 7 3 设 RQPRQPA 证明 RQPARQPA 证明证明 因为 A P Q RPQR 所以 RQPRQPA 而 RQPRQPRQPA 所以 RQPARQPA 定理定理 1 7 2 对偶原理 对偶原理 若公式AB 则 BA 证明 设 1 P 2 P n P是出现在命题公式A B中所有的命题变元 因为AB 即 21n PPPA 21n PPPB 所以 21n PPPA 21n PPPB 由定理 1 7 1 得 21 21 nn PPPBPPPA 即 21 21 nn PPPBPPPA 为重言式 故 21 21 nn PPPBPPPA 也为重言式 即 BA 对偶定律表明 利用公式的对偶式可以扩大等价式的数量 也可以简化证明 例如 RPQPRQP 与 RPQPRQP 这两个等价公式 的两端互为对偶式 因而只需证明一个等价公式成立即可 1 7 2命题公式的范式命题公式的范式 从前面的讨论可知 存在大量互不相同的命题公式 实际上互为等价 因此 有必要引 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 24 入命题公式的标准形式 使得相互等价的命题公式具有相同的标准形式 这无疑对判别两个 命题公式是否等价以及判定命题公式的类型是一种好方法 同时对命题公式的简化和推证也 是十分有益的 1 简单析取式与简单合取式 简单析取式与简单合取式 定义定义 1 7 2 单个的命题变元及其否定形式称为文字 如P Q 等 定义定义 1 7 3 仅由有限个文字组成的析取式称为简单析取式 仅由有限个文字组成的合取 式称为简单合取式 例如QP RQP P Q等都是简单析取式 QP RQP P Q等都是简单合取式 一个文字既是简单析取式 又是简单合取式 定理定理 1 7 3 简单析取式是重言式当且仅当它同时含有某个命题变元及其否定形式 证明 设公式A为简单析取式 含有命题变元 n PPP 21 若A同时含有 i P及 i P 显然A为重言式 若A为重言式但不同时含有某个命题变元及其否定形式 不妨设 nii PPPPPA 121 若 i PPP 21 真值均为 0 而 ni PP 1 真值均 为 1 则A的真值为 0 这与A为重言式矛盾 对于简单合取式也有类似的性质 定理定理 1 7 4 简单合取式是矛盾式当且仅当它同时含有某个命题变元及其否定形式 证明同定理 1 7 3 2 析取范式与合取范式 析取范式与合取范式 定义定义 1 7 4 由有限个简单合取式组成的析取式称为析取范式 Disjunctive Normal Form 由有限个简单析取式组成的合取式称为合取范式 Conjunctive Normal Form 析取 范式与合取范式统称为范式 例如 RQPQP QP 等是析取范式 RQPQP QP 等是合取范式 对于单独的一个命题变元P或其否定P 既可以看成是析取范式 又可看成是合取范 式 当然既可以看成是简单析取式 又可以看成是简单合取式 至于QP 若把它看作为 简单合取式的析取 则它是析取范式 若把它看成是文字的析取 则它是合取范式 同理 QP QP 等既是析取范式 又是合取范式 定理定理 1 7 5 范式存在定理 任何一个命题公式都存在着与之等价的析取范式和合取范 式 从析取范式和合取范式的定义可知 范式中不存在除了 以外的其余逻辑联 结词 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 25 下面给出求公式范式的步骤 1 消去除 以外公式中出现的所有逻辑联结词 2 将否定联结词消去或内移到各命题变元之前 如 BABABA BABA BABA 3 利用分配律 结合律将公式转化为合取范式或析取范式 如 RPQPRQP RPQPRQP 例例 1 7 4 求RQP 的析取范式和合取范式 解解 RQP RQPRQPRQP 析取范式 RQRP 合取范式 例例 1 7 5 求 QPQP 的析取范式 解解 QPQP QPQPQPQP QPQPQPQP QQPQQPPPQPQP QPQP 上面所求的最后两个等价的公式都是原公式的析取范式 所以命题公式的析取范式不 唯一 例例 1 7 6 求 QPQP 的合取范式 解解 QPQP QPQPQPQP PQPQPQPQ PQPPQQPPQQPQ 天津理工大学本科 离散数学 教学教案天津理工大学本科 离散数学 教学教案 26 QPQP 上面所求的最后两个等价的公式都是原公式的合取范式 所以命题公式的合取范式不 唯一 3 范式的应用 范式的应用 利用范式判断命题公式类型的问题称为判定问题 定理定理 1 7 6 一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式 一个合取 范式是重言式当且仅当它的每个简单析取式都是重言式 例例 1 7 7 判断下列公式的类型 1 QQP 2 RPRQP 解解 1 QQP QQPQQP 由定理 1 7 6 可知 QQP 为矛盾式 2 RPRQP RPRQP RRQPPRQP 由定理 1 7 6 可知 RPRQP 为重言式 1 7 3命题公式的主析取范式和主合取范式命题公式的主析