左孝凌离散数学PPT课件.ppt

离散数学 DiscreteMathematics 第一部分数理逻辑 MathematicalLogic 逻辑 是研究推理的科学 公元前四世纪由希腊的哲学家亚里斯多德首创 作为一门独立科学 十七世纪 德国的莱布尼兹 Leibniz 给逻辑学引进了符号 又称为数理逻辑 或符号逻辑 逻辑可分为 1 形式逻辑 通过数学方法 数理逻辑2 辩证逻辑指引进一套符号体系的方法 辩证逻辑是研究反映客观世界辩证发展过程的人类思维的形态的 形式逻辑是研究思维的形式结构和规律的科学 它撇开具体的 个别的思维内容 从形式结构方面研究概念 判断和推理及其正确联系的规律 数理逻辑是用数学方法研究推理的形式结构和推理的规律的数学学科 它的创始人Leibniz 为了实现把推理变为演算的想法 把数学引入了形式逻辑 其后 又经多人努力 逐渐使得数理逻辑成为一门专门的学科 上个世纪30年代以后 数理逻辑进入一个崭新的发展阶段 逻辑学不仅与数学结合 还与计算机科学等密切关联 2020 3 25 第一章命题逻辑 PropositionalLogic 1 1命题及其表示方法 1 1 1命题 Proposition 1 1 2命题的表示方法1 1 3命题的分类 2020 3 25 1 1 1命题数理逻辑研究的中心问题是推理 inference 而推理的前提和结论都是表达判断的陈述句 因而表达判断的陈述句构成了推理的基本单位 基本概念命题 能够判断真假的陈述句 命题的真值 命题的判断结果 命题的真值只取两个值 真 用T true 或1表示 假 用F false 或0表示 真命题 判断为正确的命题 即真值为真的命题 假命题 判断为错误的命题 即真值为假的命题 因而又可以称命题是具有唯一真值的陈述句 判断命题的两个步骤 1 是否为陈述句 2 是否有确定的 唯一的真值 例 判断下列句子是否为命题 1 100是自然数 T 2 太阳从西方升起 F 3 3 3 8 F 4 Howdoyoudo 疑问句 不是命题 5 明年的十月一日是晴天 是命题 其真值到明年十月一日方可知道 6 x 3 9不是命题 7 我正在说谎 是悖论 8 1 101 110二进制中为真 十进制中为假 9 如果太阳从西方升起 那么2是奇数 T 10 国足能杀入2006世界杯当且仅当2 2 4 F 11 今天天气多好啊 感叹句 不是命题 12 请你关上门 祁使句 不是命题 13 别的星球上有生物 是命题 客观上能判断真假 说明 1 只有具有确定真值的陈述句才是命题 一切没有判断内容的句子 无所谓是非的句子 如感叹句 祁使句 疑问句等都不是命题 2 因为命题只有两种真值 所以 命题逻辑 又称 二值逻辑 3 具有确定真值 是指客观上的具有 与我们是否知道它的真值是两回事 如上例中的 5 和 13 1 1 2命题的表示方法在本书中 用大写英文字母A B P Q或带下标的字母P1 P2 P3 或数字 1 2 等表示命题 称之为命题标识符 例如 P 罗纳尔多是球星 Q 5是负数 P3 明天天气晴 2 太阳从西方升起 皆为符号化的命题 其真值依次为1 0 1或0 0 命题标识符又有命题常量 命题变元和原子变元之分 命题常量 表示确定命题的命题标识符 命题变元 命题标识符如仅是表示任意命题的位置标志 就称为命题变元 原子变元 当命题变元表示原子命题时 该变元称为原子变元 命题变元也用A B P Q P1 P2 P3 表示 1 1 3命题的分类 简单 原子命题 不能分解为更简单的陈述语句的命题 如上例中的命题 复合命题 由简单命题通过联结词联结而成的命题 联结词就是复合命题中的运算符 注意 1 一个符号 如P 它表示的是命题常量还是命题变元 一般由上下文来确定 2 命题变元可以表示任意命题 它不能确定真值 故命题变元不是命题 这与 变数x不是数 是一样的道理 小结 本节主要介绍了命题 命题的真值 原子命题 复合命题 命题标识符 命题常量 命题变元和原子变元的概念 重点理解和掌握命题 命题变元两个概念 作业 P8 1 13 第一章命题逻辑 PropositionalLogic 1 2逻辑联结词 LogicalConnectives 1 2 1否定联结词 Negation 1 2 2合取联结词 Conjunction 1 2 3析取联结词 Disjunction 1 2 4条件联结词 蕴涵联结词Conditional 1 2 5双条件联结 等值联结词Biconditional 14 在命题逻辑中 主要研究的是复合命题 而复合命题是由原子命题与逻辑联结词组合而成 联结词组是复合命题的重要组成部分 1 2 1否定联结词 定义1 2 1设P为一命题 P的否定是一个新的复合命题 称为P的否定式 记作 P 读作 非P 符号 称为否定联结词 P为真当且仅当P为假 说明 属于一元 unary 运算符 15 的定义也可用下表来说明 联结词 的定义真值表 16 例1 P 天津是一个城市 Q 3是偶数 于是 P 天津不是一个城市 Q 3不是偶数 例2 P 苏州处处清洁 Q 这些都是男同学 P 苏州不处处清洁 注意 不是处处不清洁 Q 这些不都是男同学 17 1 2 2合取联结词 Conjunction 定义1 2 2设P Q为二命题 复合命题 P并且Q 或 P与Q 称为P与Q的合取式 记作P Q 符号 称为合取联结词 P Q为真当且仅当P和Q同时为真 联结词 的定义真值表 18 说明 属于二元 binary 运算符 合取运算特点 只有参与运算的二命题全为真时 运算结果才为真 否则为假 自然语言中的表示 并且 意思的联结词 如 既 又 不但 而且 虽然 但是 一面 一面 和 与 等都可以符号化为 19 例3 将下列命题符号化 1 李平既聪明又用功 2 李平虽然聪明 但不用功 3 李平不但聪明 而且用功 4 李平不是不聪明 而是不用功 解 设P 李平聪明 Q 李平用功 则 1 P Q 2 P Q 3 P Q 4 P Q注意 不要见到 与 或 和 就使用联结词 例如 1 见课本P11例题6 2 李敏和李华是姐妹 3 李敏和张华是朋友 20 例4 试生成下列命题的合取 1 P 我们在XNA303 Q 今天是星期二 2 S 李平在吃饭 R 张明在吃饭 解 1 P Q 我们在XNA303且今天是星期二 2 S R 李平与张明在吃饭 21 1 2 3析取联结词 Disjunction 定义1 2 3设P Q为二命题 复合命题 P或Q 称为P与Q的析取式 记作P Q 符号 称为析取联结词 P Q为真当且仅当P与Q中至少有一个为真 联结词 的定义真值表 22 说明 属于二元 binary 运算符 析取运算特点 只有参与运算的二命题全为假时 运算结果才为假 否则为真 由析取联结词的定义可以看出 与汉语中的联结词 或 意义相近 但又不完全相同 在现代汉语中 联结词的 或 实际上有 可兼或 和 排斥或 之分 考察下面命题 1 小王爱打球或爱跑步 可兼或 设P 小王爱打球 Q 小王爱跑步 则上述命题可符号化为 P Q 23 2 林芳学过英语或法语 可兼或 设P 林芳学过英语 Q 林芳学过法语 则上述命题可符号化为 P Q 3 派小王或小李中的一人去开会 排斥或 设P 派小王去开会 Q 派小李去开会 则上述命题可符号化为 P Q P Q 4 人固有一死 或重于泰山或轻于鸿毛 排斥或 5 ab 0 即a 0或b 0 可兼或 由此可见 P Q 表示的是 可兼或 注意 当P和Q客观上不能同时发生时 P或Q 可以符号化为 P Q 例如 小王现在在宿舍或在图书馆 设P 小王现在在宿舍 Q 小王现在在图书馆 则上述命题可符号化为 P Q 25 1 2 4 条件联结词 蕴涵联结词Conditional 定义1 2 4设P Q为二命题 复合命题 如果P则Q 若P则Q 称为P与Q的条件命题 记作P Q P Q为假当且仅当P为真且Q为假 称符号 为条件联结词 并称P为前件 Q为后件 联结词 的定义真值表 26 注 1 P Q表示的基本逻辑关系是 Q是P的必要条件或P是Q的充分条件 因此复合命题 只要P就Q 因为P 所以Q P仅当Q 只有Q才P 等都可以符号化为P Q的形式 2 属于二元 binary 运算符 例5 将下列命题符号化 1 天不下雨 则草木枯黄 P 天下雨 Q 草木枯黄 则原命题可表示为 P Q 27 2 如果小明学日语 小华学英语 则小芳学德语 P 小明学日语Q 小华学英语R 小芳学德语 则原命题可表示为 P Q R 3 只要不下雨 我就骑自行车上班 P 天下雨 Q 我骑自行车上班 则原命题可表示为 P Q 4 只有不下雨 我才骑自行车上班 P 天下雨 Q 我骑自行车上班 则原命题可表示为 Q P 5 如果2 2 4 则太阳从东方升起 P Q T PQ如果2 2 4 则太阳从西方升起 P R F R如果2 24 则太阳从东方升起 P Q T 如果2 24 则太阳从西方升起 P R T 注意 1 与自然语言的不同 前件与后件可以没有任何内在联系 2 在数学中 若P则Q 往往表示前件P为真 则后件Q为真的推理关系 但数理逻辑中 当前件P为假时 P Q的真值为真 29 1 2 5双条件联结 等值联结词Biconditional 定义1 2 5设P Q为二命题 复合命题 P当且仅当Q 称为P与Q的双条件命题 记作PiffQ或P Q 符号 称为双条件 等值 联结词 P Q为真当且仅当P Q真值相同 联结词 的定义真值表 30 注 1 P仅当Q可译为P QP当Q可译为Q PP当且仅当Q译为P Q 2 属于二元 binary 运算符 3 双条件命题P Q所表达的逻辑关系是 P与Q互为充分必要条件 相当于 P Q Q P 只要P与Q的真值同为1或同为0 P Q的真值就为1 否则P Q的真值为0 双条件联结词连接的两个命题之间可以没有因果关系 例6 分析下列命题的真值 1 2 2 4当且仅当3是奇数 P Q P 2 2 4 Q 3是奇数 31 2 2 2 4当且仅当3不是奇数 P Q 3 2 24当且仅当3是奇数 P Q 4 2 24当且仅当3不是奇数 P Q 约定 1 运算次序优先级 2 相同的运算符按从左至右次序计算 否则要加上括号 3 最外层圆括号可省去 小结 本节介绍了五种联结词 重点是理解和掌握五种联结词的内涵及它们与自然语言中相应联结词的不同之处 32 作业 1 P8 3 5 2 预习 1 3 1 4思考题 1 何谓合式公式 2 复合命题符号化的基本步骤是什么 3 何谓真值表 4 两个命题公式等价的涵义是什么 5 两个等价的命题公式其真值表有何关系 33 第一章命题逻辑 PropositionalLogic 1 3命题公式与翻译 1 3 1命题公式1 3 2复合命题的符号化 翻译 1 3 1命题合式公式 Well formedformula wff 定义1 3 1 单个命题变元和命题常量称为原子公式 命题合式公式是由命题变元 命题常量 联结词和圆括号按一定的逻辑关系联结起来的符号串 我们以如下递归的形式来定义合式公式 34 定义1 3 2 1 原子公式是合式公式 wff 2 若A是合式公式 则 A 也是合式公式 3 若A B是合式公式 则 A B A B A B A B 也是合式公式 4 当且仅当有限次地应用 1 3 所得到的包含原子公式 联结词和括号的符号串是合式公式 注 1 合式公式也称为命题公式 并简称为公式 2 命题公式一般不是命题 仅当公式中的命题变元用确定的命题代入时 才得到一个命题 其真值依赖于代换变元的那些命题的真值 35 例1 指出 P P Q 是否是命题公式 wff 如果是 则具体说明 解 P是wff由 1 Q是wff由 1 P Q是wff由 3 P P Q 由 3 例2 P Q R S Q P P 等均为合式公式 而PQ S P W Q 等不是合式公式 36 1 3 2复合命题的符号化 翻译 有了命题演算的合式公式的概念 我们可以把自然语言中的有些语句 复合命题 翻译成数理逻辑中的符号形式 基本步骤如下 1 分析出各简单命题 将它们符号化 2 使用合适的联结词 把简单命题逐个的联结起来 组成复合命题的符号化表示 37 例3 1 我今天进城 除非下雨 1 3 7 2 仅当你走我将留下 3 假如上午不下雨 我去看电影 否则就在家里读书或看报 4 除非你努力 否则你将失败 P11例5 5 一个人起初说 占据空间的 有质量的而且不断变化的叫做物质 后来他改说 占据空间的有质量的叫做物质 而物质是不断变化的 问他前后主张的差异在什么地方 试以命题形式进行分析 1 3 6 38 例4 P10例题1小结 本节介了命题公式的概念及复合命题的符号化 重点是理解命题公式的递归定义 掌握复合命题的符号化方法 作业 P12 1 5 39 第一章命题逻辑 PropositionalLogic 1 4真值表与等价公式 1 4 1真值表 TruthTable 1 4 2等价公式 PropositionalEquivalences 1 4 1真值表前面在定义联结词时 曾经使用过真值表 下面给出真值表的定义 定义1 4 1 对公式的赋值或解释 设P1 P2 Pn是出现在公式A中的全部的命题变元 给P1 P2 Pn各指定一个真值 称为对A的一个赋值或解释 若指定的一组值使A的真值为真 假 称这组值为A的成真 假 赋值 40 比如 对公式 P Q R 赋值011 即令P 0 Q 1 R 1 为 P Q R的成真赋值 另一组赋值010为 P Q R的成假赋值 还有000 001 111 考虑 含有n个命题变元的公式共有多少组不同的赋值 定义1 4 2 真值表 在命题公式A中 对于命题变元的每一组赋值和由它们所确定的命题公式A的真值列成表 称做命题公式A的真值表 41 对公式A构造真值表的具体步骤为 1 找出公式中所有命题变元P1 P2 Pn 列出全部的2n组赋值 2 按从小到大的顺序列出对命题变元P1 P2 Pn 的全部2n组赋值 3 对应各组赋值计算出公式A的真值 并将其列在对应赋值的后面 42 例1 给出 P Q P Q 的真值表 43 例2 构造公式 P Q R的真值表 44 练习1 构造公式 P Q Q P真值表 45 练习2 构造公式 P Q Q真值表 46 1 4 2等价公式给定n个命题变元 按合式公式的形成规则可以形成无数多个命题公式 但这些无穷尽的命题公式中 有些具有相同的真值表 考虑 由n个命题变元能生成 种真值 表 不同的命题公式 47 1 4 2等价公式定义1 4 3 给定两个命题公式A和B 设P1 P2 Pn为出现于A和B中的所有原子变元 若给P1 P2 Pn任一组真值指派 A和B的真值都相同 则称A和B是等价的或逻辑相等 记作A B注 1 不是逻辑联结词 2 命题公式之间的逻辑相等关系具有 自反性 A A 对称性 若A B 则B A 传递性 若A B且B C 则A C 48 证明公式等价的方法 1 真值表法2 等值演算法1 真值表法例1 P Q P Q 见真值表例题1 例2 证明 P Q P Q Q P 49 例3 判断公式P Q R P Q R是否等价 50 由真值表可知 两个公式为等价式 2 等值演算法 EquivalentCaculation 利用P15表1 4 8 重要的等价式 补充 11 蕴涵等值式 P Q P Q12 等价等值式 P Q P Q Q P 13 假言易位 P Q Q P14 等价否定等值式 P Q P Q15 归谬论 P Q P Q P 51 其中P Q R等代表任意命题公式 这样上面的每一个公式都是一个模式 它可以代表无数多个同类型的命题公式 例如 P P T中 用 P Q 置换P 则得 P Q P Q T 用 P置换P 则得 P P T 等值演算中使用的一条重要规则 置换规则 定义1 4 4 子公式 如果X是wffA的一部分 且X本身也是wff 则称X是A的子公式 例如 P P Q 为Q P P Q 的子公式 52 定理1 4 1 置换定理Axiomofreplacement 设X是wffA的子wff 若X Y 则若将A中的X用Y来置换 所得公式B与A等价 即A B 证 因为对变元的任一指派 X与Y真值相同 所以Y取代X后 公式B与公式A对变元的任一指派真值也相同 所以A B 注 满足定理1 4 1的条件的置换称为等价置换 或等价代换 定义1 4 5 等值演算 根据已知的等价公式 推演出另外一些等价公式的过程称为等值演算 53 例1 证明Q P P Q Q P证 Q P P Q Q P P 吸收律 例2 证明P Q Q P Q证 P Q Q P Q Q Q P Q T P Q例3 证明 P Q Q P P Q R证 P Q Q P P Q Q R P Q Q R P Q Q R P Q R Q Q R P Q R 54 例4 验证P Q R P Q R证 右 P Q R P Q R P Q R P Q R P Q R 练 1 P Q P R P Q R 2 P Q P Q P Q P Q 55 等值演算在计算机硬件设计中 在开关理论和电子元器件中都占有重要地位 小结 本节介绍了真值表 公式等价 等值演算和等价置换等概念 给出了常用的重要等价公式 24个 重点掌握用真值表法验证公式的等价性和等值演算法推演两个公式等价 作业 P171c e 4a c 7d e 8 预习 1 5 1 6思考题 9 56 1 5 1命题公式的分类1 5 2重言式 Tautology 与矛盾式 contradictory 的性质1 5 3蕴含式 Implication 第一章命题逻辑 PropositionalLogic 1 5重言式与蕴含式 TautologyandImplication 57 1 5 1命题公式的分类复合命题 compoundpropositions 定义1 5 1设A为任一命题公式 1 若A在其各种赋值下的取值均为真 则称A是重言式或永真式 记为T或1 2 若A在其各种赋值下的取值均为假 则称A是矛盾式或永假式 记为F或0 3 若A不是矛盾式则称A为可满足式 satisfiable 注 由定义可知 重言式一定是可满足式 反之不真 58 第一章命题逻辑 PropositionalLogic 1 5重言式与蕴含式 TautologyandImplication 判别命题公式的类型有两种方法 真值表法和等值演算法 等值演算法是将所给命题公式通过等值演算化为最简单的形式 然后再进行判别 例1 判别下列命题公式的类型 1 Q P Q P 重言式 2 P P Q Q R 矛盾式 3 P Q P 可满足式 59 1 5 2重言式 Tautology 与矛盾式 contradictory 的性质定理1 5 1 任何两个重言式的合取或析取 仍然是一重言式 由幂等律立得 证明 设A和B为两个重言式 则不论A和B的分量指派任何真值 总有A为T B为T 故A B T A B T定理1 5 2 一个重言式 矛盾式 对同一分量都用任何合式公式置换 其结果仍为一重言式 矛盾式 证明 由于重言式 矛盾式 的真值与对变元的赋值无关 故对同一变元以任何合式公式置换后 重言式 矛盾式 的真值仍永为T F 60 定理1 5 3 A B是两个命题公式 A B的充要条件是A B为重言式 证明 若A B为重言式 则A B永为T 即A B的真值表相同 所以A B 反之 若A B 则A B真值表相同 所以A B永为T 所以A B为重言式 1 5 3蕴含式 Implication 定义1 5 2 当且仅当P Q是一个重言式时 我们称 P蕴含Q 并记作P Q 61 它们之间具有如下关系 P Q Q P由P21表1 5 1Q P P Q可以得出因此 要证明P Q有三种方法 1 真值表法 即列出P Q的真值表 观察其是否为永真 2 直接证法 假定前件P是真 推出后件Q是真 3 间接证法 假定后件是假 推出前件是假 即证 Q P 62 例 证明 Q P Q P1 法1 真值表2 法2 若 Q P Q 为真 则 Q P Q为真 所以Q为假 P为假 所以 P为真 3 法3 若 P为假 则P为真 再分二种情况 若Q为真 则 Q为假 从而 Q P Q 为假 若Q为假 则P Q为假 则 Q P Q 为假 根据 所以 Q P Q PP21表1 5 2给出了14个蕴含式 它们都可以用上述方法加以推证 63 等价式与蕴含式的关系 定理1 5 4 设P Q为任意两个命题公式 P Q的充要条件为P Q且Q P 证 若P Q 则P Q为永真式因为P Q P Q Q P 所以P Q Q P为永真式 从而P Q Q P 反之 若P Q Q P 则P Q Q P为永真式 所以 P Q Q P 为永真式 从而P Q为永真式 即P Q 64 蕴含的性质 设A B C为任意wff 1 若A B 且A为永真式 则B必为永真式 2 若A B B C 则A C 3 若A B A C 则A B C 4 若A B且C B 则A C B 证 1 因为A B A永为T 所以B必永为T 2 由I11 A B B C A C 所以若A B B C 则 A B B C 永为T 从而A C永为T 故A C 65 3 A B A C A B A C A B C A B C4 A B C B A B C B A C B A C B A C B 66 小结 本节介绍了命题公式的分类 重言式 矛盾式与蕴含式的概念及其性质 等价式与蕴涵式的关系 重点掌握 1 用等值演算法判别命题公式的类型 2 重言式 矛盾式与蕴涵式的性质 3 等价式与蕴涵式的关系 作业 P23 1 c d 2 a 9 预习 1 6思考题 1 为什么要引入联结词 2 什么是最小联结词组 67 第一章命题逻辑 PropositionalLogic 1 6其它联结词 OtherConnectives 1 6 1不可兼析取 排斥或 异或 exclusiveor 1 6 2与非联结词 Nand 1 6 3或非联结词 Nor 1 6 4条件否定联结词 Non conditional 1 6 5最小联结词组 Theminimalsetofconnectives 68 在第二节 1 2 中我们定义了五种基本的联结词 但在命题逻辑中 这些联结词还不能很广泛地直接表达命题之间的联系 例如 P异或Q 只能间接地表示为 P Q P Q 为此本节再给出逻辑设计中常用的另外四种联结词 1 6 1不可兼析取 排斥或 异或 exclusiveor 定义1 6 1 设P Q为二命题 复合命题 P Q之中恰有一个为真 称为P与Q的不可兼析取 记作PQ 符号 称为异或联结词 PQ为真当且仅当P和Q的真值不同 69 联结词 的定义真值表 定义了联结词 后 命题逻辑中的有些命题就可以符号化为非常简捷的形式 例 派小王或小李中的一人去开会 排斥或 设P 派小王去开会 Q 派小李去开会 则上述命题可符号化为 PQ 70 说明 属于二元 binary 运算符 联结词 的性质 设P Q R为命题公式 则有 1 PQ QP 交换律 2 PQ R P QR 结合律 3 P QR P Q P R 分配律 4 PQ P Q P Q 5 PQ P Q 6 PP F FP P TP P 71 定理1 6 1 设P Q R为命题公式 如果PQ R 则PR Q QR P 且PQR为一矛盾式 证 由PQ R得PR P PQ PP Q FQ QQR Q PQ FP PPQR RR F 72 1 6 2与非联结词 Nand 定义1 6 2设P Q为二命题 复合命题 P与Q的否定 称为P与Q的与非式 记作P Q 符号 称为与非联结词 P Q为真当且仅当P和Q不同时为真 联结词 的定义真值表 73 说明 1 由定义可知 P Q P Q 2 属于二元 binary 运算符 联结词 的性质 1 P P P P P 2 P Q P Q P Q P Q 3 P P Q Q P Q P Q P Q 74 1 6 3或非联结词 Nor 定义1 6 3设P Q为二命题 复合命题 P或Q的否定 称为P与Q的或非式 记作P Q 符号 称为或非联结词 P Q为真当且仅当P与Q同为假 联结词 的定义真值表 75 说明 1 由定义可知 P Q P Q 2 属于二元 binary 运算符 联结词 的性质 1 P P P P P 2 P Q P Q P Q P Q 3 P P Q Q P Q P Q P Q 76 1 6 4条件否定联结词 Non conditional 定义1 6 4设P Q为二命题 复合命题 PQ 称为命题P与Q的条件否定式 PQ为真当且仅当P为真且Q为假 联结词 的定义真值表 77 说明 1 由定义可知 PQ P Q 2 属于二元 binary 运算符 有了联结词后 合式公式的定义1 3 2可加入这四个联结词 1 6 5最小联结词组 Theminimalsetofconnectives 至此 我们一共定义了9个联结词 为了直接表达命题之间的联系 是否还需要定义其它联结词呢 回答是否定的 即含n个命题变元的所有个互不等价的命题公式 均可由这9个联结词直接表达 下面我们以含两个命题变元P Q的所有互等价的命题公式为例 来说明这一问题 78 由两个命题变元P Q所构成的互不等价的个命题公式如下 由上表可知 9个联结词足以直接表达命题之间的各种联系 二元运算中 9个联结词并不都是必要的 定义1 6 5 在一个联结词的集合中 如果一个联结词可由该集合中的其它联结词定义 则称此联结词为冗余联结词 否则称为独立联结词 不含冗余联结词的联结词组称为最小联结词组 说明 最小联结词组中的联结词构成的式子足以把一切命题公式等价的表达出来 对于9个联结词的集合 由于 1 P Q P Q Q P 2 P Q P Q 3 P Q P Q 4 P Q P Q 81 5 PQ P Q 6 P Q P Q 7 P Q P Q 8 PQ P Q 故任意命题公式都可由仅包含 或 的命题公式等价代换 即9个联结词的集合中至少有七个冗余联结词 又注意到联结词 和 不再有冗余联结词 故 或 为最小联结词组 但实际中为了使用方便 命题公式常常同时包含 82 例1 试证 是最小联结词组 证 P P P P PP Q P Q P Q P Q P Q P Q P Q P P Q Q P P Q Q 例2 试证 是最小联结词组证 P Q P Q P Q P Q P Q P Q小结 本节主要介绍了四种新的联结词及最小联结词组 作业 1 P29 1 2 4 83 2 预习 1 7思考题 1 何谓命题公式的 主 析 合 取范式 2 命题公式的 主 析 合 取范式唯一吗 3 为何要将命题公式化为与之等价的主析 合 取范式 4 如何将命题公式化为与之等价的主析 合 取范式 5 两个等价的命题公式其 主 析 合 取范式有何关系 84 第一章命题逻辑 PropositionalLogic 1 7对偶与范式 Dual NormalForm 1 7 1对偶式与对偶原理 DualisticFormula DualityPrinciple 1 7 2命题公式的析 合 取范式 TheDisjunctive ConjunctiveNormalFormsofaPropositionalFormula 1 7 3命题公式的主析 合 取范式 ThePrincipalDisjunctive ConjunctiveNormalFormofaPropositionalFormula 85 1 7 1对偶式与对偶原理 DualisticFormula DualityPrinciple 在第四节 1 4 中我们给出了命题定律 P15表1 4 8 其中多数等价公式都是成对出现的 每一对公式的不同之处是将 与 互换 我们把这样的公式称为是对偶的 定义1 7 1 设命题公式A仅含有联结词 在A中将 F T分别换以 T F得出公式A 则A 称为A的对偶公式 说明 A A 86 例1 P Q R P Q R P Q 1 P Q 0 由P Q P Q 和P Q P Q 可知 P Q P Q 87 关于对偶式我们有如下两个定理 定理1 7 1 设A A 是对偶式 P1 P2 Pn是出现于A和A 中的所有原子变元 则 1 A P1 P2 Pn A P1 P2 Pn 2 A P1 P2 Pn A P1 P2 Pn 证明 因为 P Q P Q P Q P Q所以 A P1 P2 Pn A P1 P2 Pn 同理 A P1 P2 Pn A P1 P2 Pn 88 第一章命题逻辑 PropositionalLogic 1 7对偶与范式 Dual NormalForm 定理1 7 2 对偶原理 设A B为两个仅含有联结词 的命题公式 若A B 则A B 证 设P1 P2 Pn是出现于A和B中的所有原子变元 因为A P1 P2 Pn B P1 P2 Pn 则A P1 P2 Pn B P1 P2 Pn 永真 故A P1 P2 Pn B P1 P2 Pn 永真 由定理1 7 1得 A P1 P2 Pn B P1 P2 Pn 因此A B 89 例1 因为 P P Q P由对偶原理 P P Q P例2 若A 1则A 1 即A 0 例3 设A为 P Q P P Q B为 P Q 且A B 则A B P Q 90 定理1 7 3 设A B为两个仅含有联结词 的命题公式 若A B 则B A 证 设P1 P2 Pn是出现于A和B中的所有原子变元 因为A P1 P2 Pn B P1 P2 Pn 则A P1 P2 Pn B P1 P2 Pn 永真 故 B P1 P2 Pn A P1 P2 Pn 永真 即B P1 P2 Pn A P1 P2 Pn 永真 以Pi代 Pi i 1 2 n得B P1 P2 Pn A P1 P2 Pn 永真 所以B A 91 1 7 2命题公式的析 合 取范式 TheDisjunctive ConjunctiveNormalFormsofaPropositionalFormula 从前面的讨论可知 存在大量互不相同的命题公式 实际上互为等价 因此 有必要引入命题公式的标准形式 使得相互等价的命题公式具有相同的标准形式 这无疑对判别两个命题公式是否等价以及判定命题公式的类型是一种好方法 同时对命题公式的简化和推证也是十分有益的 92 定义1 7 2 1 文字 命题变元及其否定统称为文字 如P P 2 简单析取式 仅有有限个文字组成的析取式 如 P P Q P P Q P P P Q R S 3 简单合取式 仅有有限个文字组成的合取式 如 P Q Q P P P Q P P p Q R 从定义不难看出 1 一个简单析取式是重言式当且仅当它同时含有某个命题变元及其否定式 2 一个简单合取式是矛盾式当且仅当它同时含有某个命题变元及其否定式 93 定义1 7 3 1 析取范式 一个命题公式称为析取范式 当且仅当它具有形式 A1 A2 An n大于等于1 其中Ai i 1 2 3 n 为简单合取式 如 P Q P Q P Q R Q P 2 合取范式 一个命题公式称为合取范式 当且仅当它具有形式 A1 A2 An n大于等于1 其中Ai i 1 2 3 n 为简单析取式 如 P Q P Q P Q R Q P 3 范式 析取范式与合取范式统称为范式 显然 任何合 析 取范式的对偶式是析 合 取范式 94 析取范式与合取范式的性质 1 一个析取范式是矛盾式 当且仅当它的每一个简单合取式都是矛盾式 2 一个合取范式是重言式 当且仅当它的每一个简单析取式都是重言式 定理1 7 4 范式存在定理 任一个命题公式都存在着与之等价的析取范式与合取范式 95 求命题公式的范式的基本步骤 1 将公式中的联结词化归成 及 2 将否定联结词消去或内移到各命题变元之前 利用下列等价式 A A A B A B A B A B 3 利用分配律 结合律将公式转化为合取范式或析取范式 C A B C A C B C A B C A C B 96 例1 求 P Q R P的析取范式与合取范式 例2 求 P Q R的析取范式与合取范式 例3 求 P Q P Q 的析取范式与合取范式 注意 1 单个命题变元既是简单合取式 又是简单析取式 公式P Q R既可以看成是合取范式 也可以看成是析取范式 2 一个命题公式的析 合 取范式不是唯一的 例1 求 P Q R P的析取范式与合取范式 解 原式 P Q R P P Q R P P R Q R P 析取范式 P P R Q R P Q R 析取范式 P Q P R P 合取范式 P Q R P 合取范式 例2 求 P Q R的析取范式与合取范式 解 原式 P Q R R P Q P Q R R P Q P Q R R P Q P Q R R P Q P R Q R R P Q 合取范式 P Q R P Q R R P Q P Q R R P R Q 析取范式 例3 求 P Q P Q 的析取范式与合取范式 解 P Q P Q P Q P Q P Q P Q P Q P Q P Q P Q P Q Q P 析取范式 P Q P Q 合取范式 100 1 7 3命题公式的主析 合 取范式 ThePrincipalDisjunctive ConjunctiveNormalFormofaPropositionalFormula 由于一个命题公式的析 合 取范式不是唯一 因而它们不能作为命题公式的规范形式 标准形式 为了使任意命题公式化为唯一的标准形式 下面引入主范式的概念 1 命题公式的主析取范式定义1 7 4 在含有n个命题变元的简单合取式中 若每个命题变元和它的否定不同时出现 而二者之一必出现且仅出现一次 称这样的简单合取式为小项 101 例如 三个命题变元P Q R 其小项共有8个 小项编码真值指派小项的真值 P Q Rm000 m00001 P Q Rm001 m10011 P Q Rm010 m20101 P Q Rm011 m30111P Q Rm100 m41001P Q Rm101 m51011P Q Rm110 m61101P Q Rm111 m71111 102 考虑 n个命题变元可产生多少个小 大 项 2n n个变元的小项 m0 P1 P2 Pnm1 P1 P2 Pn m2n 1 P1 P2 Pn小项的真值表 P33表1 7 1 表1 7 2 103 小项的性质 没有两个小项是等价的 且每个小项有且仅有一个成真赋值 若成真赋值所对应的二进制数转化为十进制数为i 就将所对应的小项记作mi 2 任意两个不同的小项的合取为矛盾式 3 全体小项的析取为永真式 定义1 7 5 设命题公式A中含有n个命题变元 如果A的析取范式中 所有的简单合取式都是小项 则称该析取范式为A的主析取范式 定理1 7 5 任何命题公式都存在着与之等价的主析取范式 并且是唯一的 104 主析取范式的求法定理1 7 6 在命题公式A的真值表中 真值为1的指派对应的小项的析取 即为A的主析取范式 例1 P34例题6例2 P35例题7一个命题公式A的主析取范式 还可以通过等值演算的方法求出 其推演步骤 1 将A化为析取范式 2 除去中所有永假的析取项 105 3 将中重复出现的简单合取式和相同变元都消去 4 若中某简单合取式B中不含命题变元Pi 添加 Pi Pi 然后应用分配律展开 即B B 1 B Pi Pi B Pi B Pi 例1 求 P Q R P的主析取范式 例2 求 P Q R的主析取范式 例3 求 P Q P Q 的主析取范式 106 第一章命题逻辑 PropositionalLogic 1 7对偶与范式 Dual NormalForm 例1 求 P Q R P的主析取范式 解 原式 P Q R P P Q R 析取范式 P Q Q R R P P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R 主析取范式 m7 m6 m5 m4 m2 m2 m4 m5 m6 m7 107 第一章命题逻辑 PropositionalLogic 1 7对偶与范式 Dual NormalForm 例2 求 P Q R的主析取范式 解 原式 P Q R R P R Q 析取范式 P Q R R P Q Q P P R Q P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R 主析取范式 m1 m3 m4 m7 108 例3 求 P Q P Q 的主析取范式 解 P Q P Q P Q Q P 主析取范式 m1 m2 109 2 命题公式的主合取范式定义1 7 6 在含有n个命题变元的简单析取式中 若每个命题变元和它的否定不同时出现 而二者之一必出现且仅出现一次 称这样的简单析取式为大项 110 例如 三个命题变元P Q R 其大项共有8个 大项编码真值指派大项的真值P Q RM000 M00000P Q RM001 M10010P Q RM010 M20100P Q RM011 M30110 P Q RM100 M41000 P Q RM101 M51010 P Q RM110 M61100 P Q RM111 M71110 111 n个变元的大项 M0 P1 P2 PnM1 P1 P2 Pn M2n 1 P1 P2 Pn 112 大项的性质 没有两个大项是等价的 且每个大项有且仅有一个成假赋值 若成假赋值所对应的二进制数转化为十进制数为i 就将所对应的大项记作Mi 2 任意两个不同的大项的析取为永真式 3 全体大项的合取为矛盾式 定义1 7 7 设命题公式A中含有n个命题变元 如果A的合取范式中 所有的简单析取式都是大项 则称该合取范式为A的主合取范式 定理1 7 6 任何命题公式都存在着与之等价的主合取范式 并且是唯一的 113 主合取范式的求法定理1 7 7 在命题公式A的真值表中 真值为0的指派对应的大项的合取 即为A的主合取范式 例1 P34例题6例2 P35例题7一个命题公式A的主合取范式 还可以通过等值演算的方法求出 其推演步骤 1 将A化为合取范式 2 除去中所有永真的合取项 114 3 将中重复出现的简单析取式和相同变元都消去 4 若中某简单析取式B中不含命题变元Pi 添加 Pi Pi 然后应用分配律展开 即B B 0 B Pi Pi B Pi B Pi 例1 求 P Q R P的主合取范式 例2 求 P Q R的主合取范式 例3 求 P Q P Q 的主合取范式 注 1 命题公式的主析 合 取范式唯一 2 两命题公式若有相同的主析 合 取范式 则二命题公式等价 115 例1 求 P Q R P的主合取范式 解 原式 P Q R P P Q R P 合取范式 P Q R R R P Q Q P Q R P Q R P Q R P Q R P Q R P Q R P Q R 主合取范式 M0 M1 M3 116 例2 求 P Q R的析取范式与合取范式 解 原式 P R Q R R P Q 合取范式 P R Q Q P P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R P Q R 主合取范式 M0 M2 M5 M6 117 例3 求 P Q P Q 的主合取范式 解 P Q P Q P Q P Q 主合取范式 M0 M3 118 3 主析取范式和主合取范式关系设Z为命题公式A的主析取范式中所有小项的足标集合 R为命题公式A的主合取范式中所有大项的足标集合 则R 0 1 2 2n 1 Z或Z 0 1 2 2n 1 R 故已知命题公式A的主析取范式 可求得其主合取范式 反之亦然 注意到小项与大项之间具有关系 mi Mi Mi mi 例 m5 P Q RM5 P Q R 设命题公式A中含n个命题变元 且设A的主析取范式中含k个小项mj1 mj2 mik 则 A的主析取范式中必含2n k个小项mi1 mi2 mi2n k 且 0 1 2 2n 1 j1 j2 jk i1 i2 i2n k 所以 119 A mi1 mi2 mi2n kA mi1 mi2 mi2n k mi1 mi2 mi2n k Mi1 Mi2 Mi2n k例如 设命题公式A m0 m1 m5 m7 则A M2 M3 M4 M6 120 第一章命题逻辑 PropositionalLogic 1 7对偶与范式 Dual NormalForm 4 主析 合 取范式的应用 1 求公式的成真 成假赋值 若公式A中含有n个命题变元 且A的主析取范式含s个小项 则A有s个成真赋值 有2n s个成假赋值 即主析取范式中的小项对应的编码是公式A的成真赋值 反之主合取范式中的大项对应的编码是公式A的成假赋值 121 2 判断公式的类型 设公式A中含有n个命题变元 则 1 A为重言式 A的主析取范式含全部2n个小项 2 A为矛盾式 A的主析取范式不含任何小项 记A的主析取范式为0 3 A为可满足式 A的主析取范式至少含一个小项 4 A为矛盾式 A的主合取范式含全部2n个大项 5 A为重言式 A的主合取范式不含任何大项 记A的主合取范式为1 6 A为可满足式 A的主合取范式中大项的个数一定小于2n 122 例 判断下列命题公式的类型 1 P Q R 2 P Q Q 3 P Q Q Q解 1 P Q R m1 m3 m4 m7为可满足式 123 3 判断两个命题是否等价 设公式A B中共含有n个命题变元 按n个命题变元求出A B的主析 合 取范式 若 则A B 否则A B不等价 例 试判断下列各组命题是否等价 1 P Q P R 与P Q R 2 P Q R 与P Q R 124 解 1 P Q P R P Q P R P Q R R P R Q Q P Q R P Q R P R Q P R Q M4 M5 M6P Q R P Q R P Q P R M4 M5 M6所以 P Q P R P Q R 125 解 2 P Q R P Q R P Q P R M4 M5 M6 m0 m1 m2 m3 m7P Q R P Q R M2 m0 m1 m3 m4 m5 m6 m7所以P Q R 与P Q R 不等价 126 5 解决实际问题 某科研所有三名青年高级工程师A B C 所里要选派他们中的1到2人出国进修 由于所里工作的需要 选派时必须满足以下条件 若A去 则C也可以去 若B去 则C不能去 若C不去 则A或B可以去问所里应如何选派他们 127 解 设P 派A去 Q 派B去 R 派C去 根据所要满足的条件 得命题公式为 P R Q R R P Q 求此公式的主析取范式 原式 P Q R P Q R P Q R 因此有三种选派方案 去 而 都不去 去 而 都不去 都去 而 不去 128 1 8 1常用的证明方法1 8 2真值表法 TruthTable 1 8 3直接证法 DirectProof 1 8 4间接证法 IndirectProof 第一章命题逻辑 Prop