四川大学离散数学第一章.pdf

主要内容主要内容 1 1 命题与逻辑联结词 1 2 命题公式与其赋值 1 3 命题公式的等价 1 4 联结词的完备集 1 5 命题公式的范式表示 1 6 命题公式的蕴涵 1 7 命题逻辑的推理方法 1 6 命题公式的蕴涵1 6 命题公式的蕴涵 1 定义 设A和B是两个合适公式 如果在任何解释下A取值1 时B也取值1 则称为公式公式A 永真永真 蕴涵蕴涵公式公式B 记为 A B 例 证明 P Q Q R P R 方法 列出真值表 根据定义确定 1 6 命题公式的蕴涵1 6 命题公式的蕴涵 定理定理11 设A和B是两个命题公式 则A B当且仅当 A B是永真式 证明 证明 已知A B 根据定义 任何使公式A取值1的解释 B取值 1 则在此解释下有A B为1 在任何解释下公式A取值为0 则 条件命题A B为1 所以A B为永真式 反之 如果A B是永真式 则任何使公式A取值1的解释也必 定使B取值1 根据蕴涵关系的定义应有A B 蕴涵关系 和条件联结词 是完全不同的符号 蕴涵关系 和条件联结词 是完全不同的符号 是 是命题联结词命题联结词 A B是一个条件命题公式 是一个条件命题公式 是 是公式间关系符公式间关系符 A B不是一个命题公式 仅表示不是一个命题公式 仅表示A B间的蕴涵关系 间的蕴涵关系 1 6 命题公式的蕴涵1 6 命题公式的蕴涵 例例20 用等值演算法证明下面蕴含式 用等值演算法证明下面蕴含式P Q P Q 成立 成立 证明 分析 由定理 要证明P Q P Q 即证明 P Q P Q T P Q P Q P Q P Q P Q P Q P T T 由定理知 P Q P Q 成立 1 6 命题公式的蕴涵1 6 命题公式的蕴涵 2 基本蕴涵式 蕴涵定律 I I1 1 P Q P P Q Q I P Q P P Q Q I2 2 P Q P P Q Q P Q P P Q Q 解释 解释 利用P Q的真值表 P Q不成立只有一种情况 前件 即P成立 同样 P Q不成立只有一种情况 后件即Q不成 立 I I3 3 P P Q Q P Q I P P Q Q P Q I4 4 P P Q Q P Q P P Q Q P Q 解释 解释 类似I1 I2 自己思考 扩充法则扩充法则 简化法则简化法则 1 6 命题公式的蕴涵1 6 命题公式的蕴涵 I I5 5 P P P Q Q P Q Q 假言推论假言推论 I I6 6 Q Q P Q P P Q P 拒取式 否定式假言推论 拒取式 否定式假言推论 解释 解释 类似I1 I2 自己思考 I I7 7 P P Q Q P P Q Q 析取三段论析取三段论 I I8 8 P P Q Q I P P Q Q I9 9 P Q Q R P R P Q Q R P R 假言三段论假言三段论 解释 解释 假如我是川大的学生 则我拥有川大的学籍 假如我拥 有川大的学籍 则我有川大的学生证 所以 假如我是川 大的学生 则我有川大的学生证 1 6 命题公式的蕴涵1 6 命题公式的蕴涵 I I10 10 P Q P R Q R R P Q P R Q R R 二难推论二难推论 解释 解释 和假言推论联系起来思考 I I11 11 P Q R S P R Q S P Q R S P R Q S 解释 解释 假如我是川大的学生 则我拥有川大的学籍 同时 假 如小华是川大的学生 则小华拥有川大的学籍 所以 假如我 和小华都是川大的学生 则我和小华都拥有川大的学籍 1 6 命题公式的蕴涵1 6 命题公式的蕴涵 I I11 11 P Q Q R P R P Q Q R P R等价三段论等价三段论 I I12 12 P Q P R Q R P Q P R Q R归结原理归结原理 解释 等价转化 P Q P R Q R 解释 等价转化 P Q P R Q R 1 6 命题公式的蕴涵1 6 命题公式的蕴涵 3 蕴涵式的性质 自反性 A A 自反性 A A 反对称性 如果A B B A iff A B 反对称性 如果A B B A iff A B A B 且A为永真式 则B必为永真式 A B 且A为永真式 则B必为永真式 1 6 命题公式的蕴涵1 6 命题公式的蕴涵 传递性 如果A B B C 则A C 传递性 如果A B B C 则A C 证明 由已知条件A B 且B C 根据定理11 A B B C 是永真式 再由假言三段论 应有 A B B C A C 再根据性质3 A C也必是永真式 即A C 1 6 命题公式的蕴涵1 6 命题公式的蕴涵 如A B A C 如A B A C iffiff A B CA B C 证明 由A B 且 A C 得到A B和A C都是永真式 于是 A B A C 也是永真式 但是 A B A C A B A C A B C A B C 所以A B C 是永真式 即A B C 从证明过程看 性质5反过来也对 即由 A B C可以得到A B 且 A C 1 6 命题公式的蕴涵1 6 命题公式的蕴涵 如A B C B 则A C B A B C 如A B C B 则A C B A B CiffiffA B CA B C 该性质是推理演绎中CP规则的基础该性质是推理演绎中CP规则的基础 A B A BiffiffA B 是矛盾式A B 是矛盾式 该性质是反证法的基础该性质是反证法的基础 1 6 命题公式的蕴涵1 6 命题公式的蕴涵 1 6 命题公式的蕴涵1 6 命题公式的蕴涵 定理定理12 A B当且仅当 B A 证明 留作练习 证明 留作练习 例题 考虑以下语句 并将其前提和结论符号化 1 前提 例题 考虑以下语句 并将其前提和结论符号化 1 前提 1 如果明天天晴 我们准备外出旅游 P Q 2 明天的确天晴 P 结论 结论 我们外出旅游 Q 上述例子可描述为 P Q P Q 假言推论 2 前提 2 前提 1 如果一个人是单身汉 则他不幸福 P Q 2 如果一个人不幸福 则他死得早 Q R 结论 结论 单身汉死得早 P R 上述例子可描述为 P Q Q R P R 假言三段论 1 6 命题公式的蕴涵1 6 命题公式的蕴涵 3 3 某女子在某日晚归家途中被杀害 据多方调查确证 凶手必 为王某或陈某 但后又查证 作案之晚王某在工厂值夜班 没有外出 根据上述案情可得前提如下 前提 前提 1 凶手为王某或陈某 P Q 2 如果王某是凶手 则他在作案当晚必外出 P R 3 王某案发之晚并未外出 R 结论 结论 陈某是凶手 Q 则上述例子可描述为 P R R P 拒取式 P Q P Q 析取三段论 1 6 命题公式的蕴涵1 6 命题公式的蕴涵 4 前提 4 前提 1 如果某同学为省二级以上运动员 则他将被大学录取 P R 2 如果某同学高考总分在560分以上 则将被大学录取 Q R 3 某同学高考总分在560分以上或者是省二级运动员 P Q 结论 结论 该同学被大学录取 R 则上述例子可描述为 P Q P R Q R R 二难推论 1 6 命题公式的蕴涵1 6 命题公式的蕴涵 习题一 15 1 3 18 19 1 4 习题一 15 1 3 18 19 1 4 作业作业 主要内容主要内容 1 1 命题与逻辑联结词 1 2 命题公式与其赋值 1 3 命题公式的等价 1 4 联结词的完备集 1 5 命题公式的范式表示 1 6 命题公式的蕴涵 1 7 命题逻辑的推理方法 1 7 命题逻辑的推理方法1 7 命题逻辑的推理方法 命题演算的一个主要任务在于提供一种正确的思维规 律 即 命题演算的一个主要任务在于提供一种正确的思维规 律 即推理规则推理规则 应用此规则从一些前提中推导出一个结论 来 这种推导过程称为 应用此规则从一些前提中推导出一个结论 来 这种推导过程称为演绎演绎或或形式证明形式证明 1 几个定义 设A B为命题公式 若A B 则称B是A的有效结论有效结论或 逻辑结果逻辑结果 一般地 设A1 A2 Am B是命题公式 如果 A1 A2 Am B 则B是A1 A2 Am的有效结论 逻辑结果 有效结论 逻辑结果 或称由A1 A2 Am推出结论B 有效论证 在更一般意义上 我们有下述定义 定义1 20定义1 20设G是由一组命题公式组成的集合 如果存在命题 公式的有限序列 A1 A2 An B 使得每个Ai要么是G中的某个公式 要么是前面的某些公 式Aj j i 的有效结论 并且An就是B 则称公式B是G的逻辑 结果 有效结论 或者称由G演绎出结论B来 理解为 公式集合理解为 公式集合G中前提和由某些前提得到的中间结论 结论中前提和由某些前提得到的中间结论 结论B 1 7 命题逻辑的推理方法1 7 命题逻辑的推理方法 我们有下述结论 我们有下述结论 公式B是公式集合G A公式B是公式集合G A1 1 A A2 2 A An n 的逻辑结果 当且仅当A 的逻辑结果 当且仅当A1 1 A A2 2 A An n B为永真公式 B为永真公式 1 7 命题逻辑的推理方法1 7 命题逻辑的推理方法 定义说明 定义说明 1 若A1 A2 An B 则A1 A2 An从推 出B 这样的推理是正确的 但是 1 若A1 A2 An B 则A1 A2 An从推 出B 这样的推理是正确的 但是 推理正确不等于结论为 真 正确 真实 推理正确不等于结论为 真 正确 真实 结论的真假还取决于前提A1 A2 An的真假 前提为真时 结论B为真 前提为假时 B可 能真也可能假 这就是定义中说B是A1 A2 An的 结论的真假还取决于前提A1 A2 An的真假 前提为真时 结论B为真 前提为假时 B可 能真也可能假 这就是定义中说B是A1 A2 An的有 效结论 有 效结论而而不是说正确结论不是说正确结论的原因 的原因 1 7 命题逻辑的推理方法1 7 命题逻辑的推理方法 2 由此可见 2 由此可见 推理的有效性是一回事 推理的有效性是一回事 前提与结论 的真实与否是另一回事 前提与结论 的真实与否是另一回事 所谓所谓推理有效 推理有效 指的是它的结论 是在它的前提下 指的是它的结论 是在它的前提下合乎逻辑合乎逻辑的结果 的结果 也即 并不要求前提或 结论一定为真或为假 而 也即 并不要求前提或 结论一定为真或为假 而如果它的前提都为真 那么所得 的结论也必然为真 如果它的前提都为真 那么所得 的结论也必然为真 1 7 命题逻辑的推理方法1 7 命题逻辑的推理方法 1 7 命题逻辑的推理方法1 7 命题逻辑的推理方法 2 推理规则 1 蕴涵式 见表 标注蕴涵式 见表 标注I 2 恒等式 见表 标注恒等式 见表 标注E 3 P规则 称为前提引用规则 规则 称为前提引用规则 在推导的过程中 可随时 引入前提集合中的任意一个前提 标注 在推导的过程中 可随时 引入前提集合中的任意一个前提 标注P 4 T规则 逻辑结果引用规则 规则 逻辑结果引用规则 在推导的过程中 利用基 本等价式和蕴涵式 由证明过程中某些中间公式变换出新 的公式 若依据的是等价式 规则标明为 在推导的过程中 利用基 本等价式和蕴涵式 由证明过程中某些中间公式变换出新 的公式 若依据的是等价式 规则标明为T E 若依据的 是蕴涵式 规则标明为 若依据的 是蕴涵式 规则标明为T I 5 CP规则 附加前提规则 规则 附加前提规则 如果要推导的结果是形如如果要推导的结果是形如 B C的公式 则把的公式 则把B作为附加前提 与给定的前提一起推 导出 作为附加前提 与给定的前提一起推 导出C 即G1 G2 Gn B C 当且仅当 G1 G2 Gn B C 6 合取引入规则 合取引入规则 A B A B 1 7 命题逻辑的推理方法命题逻辑的推理方法 1 7 命题逻辑的推理方法1 7 命题逻辑的推理方法 例21 前提 P Q R Q R 结论 P 证明 R P R Q P Q T I5 P Q P P T I6 1 7 命题逻辑的推理方法1 7 命题逻辑的推理方法 3 证明方法 推理方法 1 真值表法 1 真值表法 根据前提A1 A2 An和结论B 构造条件式 A1 A2 An B的真值表 若它为永真式 则结论B是 有效的 2 2 演绎法演绎法 演绎法是从前提 假设 出发 依据公认的推理规则推理规则 推 导出一个结论来 1 1 直接法直接法 2 2 利用CP规则利用CP规则 3 3 间接证明法间接证明法 反证法 反证法 1 7 命题逻辑的推理方法1 7 命题逻辑的推理方法 直接证明法直接证明法 A1 A2 An B形式命题 从前提出发 利 用已知的基本等价式和蕴涵式构造中间命题 直至导出 最后结论 例22例22求证S R是前提 P Q P R Q S 的有效结论 构 造性二难推论 证 步骤公式依据 注释 P Q P P Q T E1 E2 Q S P P S T I9 S P T E23 P R P S R T I9 S R T E2 E1 故 P Q P R Q S S R 1 7 命题逻辑的推理方法1 7 命题逻辑的推理方法 1 7 命题逻辑的推理方法1 7 命题逻辑的推理方法 CP规则推理法规则推理法 A1 A2 An B C形式命题的证明 通常将B 作为附加前提附加前提加入已知前提中 将证明转化为 A1 A2 An B C 以蕴涵式的性质7为基础 例23例23 证明R S可以从前提 P Q S R P Q 推出 证 证 R P 附加前提 R P P P T I8 P Q S P Q S T I5 Q P S T I5 R S CP 1 7 命题逻辑的推理方法1 7 命题逻辑的推理方法 1 7 命题逻辑的推理方法1 7 命题逻辑的推理方法 反证法反证法 归谬法归谬法 A1 A2 An B形式命题 把 B作为附加前提 将证明转化为A1 A2 An B F F R R 矛盾律 矛盾律 1 7 命题逻辑的推理方法1 7 命题逻辑的推理方法 例24 例24 证明 P Q P Q 证明 将 P Q 作为附加前提 P Q P 附加前提 P T I1 P Q P P T I1 F T E19 1 7 命题逻辑的推理方法1 7 命题逻辑的推理方法 例例25 应用题 应用题 证明以下推理是正确的 如果小张和小王去看电影 则小李也去看电影 小赵不去看电影或小张去看电影 小王去看电影 所以 当小赵去看电影时 小李也去 解 设P 小张去看电影 Q 小王去看电影 R 小李去看电影 S 小赵去看电影 前提 P Q R S P Q 结论 S R 1 7 命题逻辑的推理方法1 7 命题逻辑的推理方法 现用CP规则法证明 S P 附加前提 S P P P T I7 P Q R P Q P P Q T I R T I5 S R CP 4 消解原理 归结推理法 归结推理法 利用规则推理有很大的随意性 不易机械执行 归结 推理法是仅有一条推理规则的机械推理法 容易以程序实 现 是定理机器证明的重要方法 是反证法的特殊情况 根据基本蕴涵式I8 析取三段论 即P P Q Q 和基本蕴涵式I13 归结原理 P Q P R Q R 1 7 命题逻辑的推理方法1 7 命题逻辑的推理方法 1 7 命题逻辑的推理方法1 7 命题逻辑的推理方法 设设C1 L C1 C2 L C2 是两个子句 有互补对 是两个子句 有互补对L 和 和 L 则新子句 则新子句 C3 C1 C2 C1 C2 称作称作C1和和C2的的消解式消解式 归结式 归结式 例如 设C1 P Q R C2 P S C1和C2消解式 C3 Q S 为了证明为了证明 A1 A2 An BA1 A2 An B 根据根据反证法反证法 即需证明 即需证明 A1 A2 An B R RA1 A2 An B R R 利用消解规则进行推理 其过程为 1 从 A1 A2 An B 出发从 A1 A2 An B 出发 2 2 将A将A1 1 A A2 2 A An n B转化成 B转化成合取范式合取范式 如 P P R P Q P R 的形式 3 将合取范式中的 如 P P R P Q P R 的形式 3 将合取范式中的所有子句所有子句 析取式析取式 构成子句集合S 如 构成子句集合S 如 S P P R P Q P R S P P R P Q P R 4 4 对S使用消解规则对S使用消解规则 对S的对S的子句子句作归结 即消除互补式 互反对 如子句P R 与 P Q作归结 得归结式R Q并将这归结式仍放S中 重复这一 过程 5 作归结 即消除互补式 互反对 如子句P R 与 P Q作归结 得归结式R Q并将这归结式仍放S中 重复这一 过程 5 直至归结出矛盾式直至归结出矛盾式 称为空子句 记为 称为空子句 记为 因此 其消解过程就是对S的子句求消解式的过程 因此 其消解过程就是对S的子句求消解式的过程 消解式消解式C C3 3 C C1 1 C C2 2 C C1 1 C C2 2 仅三种情况 C 仅三种情况 C1 1 A B C A B C2 2 A D 则 A B A D B D C A D 则 A B A D B D C1 1 A C A C2 2 A B 则 A A B B C A B 则 A A B B C1 1 A C A C2 2 A 则 A A F A 则 A A F 1 7 命题逻辑的推理方法1 7 命题逻辑的推理方法 1 7 命题逻辑的推理方法1 7 命题逻辑的推理方法 例 用消解法证明P Q S R P Q R S 解 首先把结论否定 R S 后加入前提中 构造由前提组成 的合取式 并化为合取范式 P Q S R P Q R S P Q S R P Q R S P Q S R P Q R S 得到子句集 P Q S R P Q R S 消解序列 1 7 命题逻辑的推理方法1 7 命题逻辑的推理方法 消解序列 P Q S P QP P ST 消除Q和 Q S P P T 消除S和 S R P P R T 消除P和 P R P T 消除R和 R 例26例26 如果公司的利润高 那么公司有个好经理或它是一 个好企业及大体上是个好的经营年份 现在的情况是 公司的利润高 不是一个好的经营年份 要证明 公司 有个好经理 解 设A 公司的利润高 B 公司有个好经理 C 公司是个好企业 D 大体上是个好的经营年份 解 设A 公司的利润高 B 公司有个好经