搜索

离散数学第5讲

gecimao 发表于 2019-06-27 15:03 | 查看: | 回复:

  离散数学第5讲。离散数学 第5讲 回顾上节课基本知识点 : 析取范式和合取范式的定义及相关的性质 定理; 定理; 求解公式范式的步骤和方法; 求解公式范式的步骤和方法; 极大项和极小项的概念以及它们之间的关 系。 主

  离散数学 第5讲 回顾上节课基本知识点 : 析取范式和合取范式的定义及相关的性质 定理; 定理; 求解公式范式的步骤和方法; 求解公式范式的步骤和方法; 极大项和极小项的概念以及它们之间的关 系。 主析取范式和主合取范式的定义; 主析取范式和主合取范式的定义; 用真值表求解主析取范式和主合取范式的 方法。 方法。 1 离散数学 第5讲 本讲基本知识点: 本讲基本知识点: 等值演算法求解主析取范式的方法和步骤: 等值演算法求解主析取范式的方法和步骤: 主析取范式的用途 关于主合取范式 联结词的完备集 2 第二章 命题逻辑等值演算 等值演算法求解主析取范式的方法和步骤: 等值演算法求解主析取范式的方法和步骤: (1)化为析取范式 ; )化为析取范式A; (2)对A中的简单合取项补入没有出现的 ) 中的简单合取项补入没有出现的 命题变元, 合取上 命题变元,即合取上(P ∨ ???P )式,然 后应用分配律展开; 后应用分配律展开; (3) 将析取式 中重复出现的合取项和相 ) 将析取式A中重复出现的合取项和相 同的变元合并; 同的变元合并; (4)除去析取范式中所有永假的合取项; )除去析取范式中所有永假的合取项; 3 第二章 命题逻辑等值演算 等值演算法求解主合取范式的方法和步骤: 等值演算法求解主合取范式的方法和步骤: (1)化为合取范式 ; )化为合取范式A; (2)对A中的简单析取项补入没有出现的 ) 中的简单析取项补入没有出现的 命题变元, 析取上 命题变元,即析取上(P ∧ ???P )式,然 后应用分配律展开; 后应用分配律展开; (3) 将合取式 中重复出现的析取项和相 ) 将合取式A中重复出现的析取项和相 同的变元合并; 同的变元合并; (4)除去合取范式中所有永真的合取项; )除去合取范式中所有永线 第二章 命题逻辑等值演算 说明:对于一个命题的主析取范式, 说明:对于一个命题的主析取范式,如将其 命题变元的个数及出现次序固定 出现次序固定后 命题变元的个数及出现次序固定后,则此 公式的主析取范式便是唯一的。 公式的主析取范式便是唯一的。 因此,给定两个公式, 因此,给定两个公式,由主析取范式可以方 便地看出两个公式是否等价。 便地看出两个公式是否等价。 5 第二章 命题逻辑等值演算 例:求(P∧Q)∨(???P ∧ R)∨(Q∧R)的主析取 ) ∧ 的主析取 范式。(等价演算法) 。(等价演算法 范式。(等价演算法) 解题思路: 解题思路: ?一共有三个原子变元; 一共有三个原子变元; 一共有三个原子变元 ?已经是析取范式的形式; 已经是析取范式的形式; 已经是析取范式的形式 ?只是每个简单合取项不是极小项,则应对合取 只是每个简单合取项不是极小项, 只是每个简单合取项不是极小项 则应对合取 项补入没有出现的命题变元, 项补入没有出现的命题变元,然后利用分配律 展开; 展开; ?消去永假的合取项; 消去永假的合取项; 消去永假的合取项 ?合并重复出现的合取项和相同的变元; 合并重复出现的合取项和相同的变元; 合并重复出现的合取项和相同的变元 6 第二章 命题逻辑等值演算 原式? 原式? (P∧Q∧(R∨ ???R)) ∨ ∨(???P∧(Q ∨ ???Q)∧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) ∧ ? m1∨ m3∨m6 ∨m7 (主析取范式) 主析取范式) 7 第二章 命题逻辑等值演算 例:求P → ((P → Q)∧ ?? (??Q∨ ???P))的主析取范 的主析取范 式. 等价演算法 思路: 一共有两个原子变元; 思路: 一共有两个原子变元; 含有联结词→,不是析取范式的形式。 不是析取范式的形式。 消去→ 先利用蕴含等值公式 P → Q ? ???P ∨ Q消去→ 消去 再化为析取范式 析取范式。 再化为析取范式。 8 第二章 命题逻辑等值演算 解:等价演算法 P → ((P → Q)∧ ?? (??Q∨ ???P)) ∧ ∨ 消去→及德摩根定律) ? ???P ∨ (( ???P ∨ Q)∧ (Q ∧ P)) (消去→及德摩根定律) ∧ 分配律) ? ???P ∨ (( ???P ∧ Q ∧ P) ∨ (Q∧ Q ∧ P))(分配律 ∧ 分配律 消去永假项和相同变元) ? ???P ∨ ( Q ∧ P) (消去永假项和相同变元) ?( ???P ∧(Q∨ ???Q) ) ∨ ( Q ∧ P) (在第一个合取项中 (Q∨ 补入变元Q 补入变元 ) ?( ???P ∧Q) ∨ ( ???P ∧ ???Q )∨ ( P∧ Q)(主析取范式) ∨ ∧ (主析取范式) ?m0 ∨m1 ∨m3 9 第二章 命题逻辑等值演算 的主析取/合取范式 例:求例2.7的主析取 合取范式。 求例 的主析取 合取范式。 接前 (p∧ ???q ∧? ??r )∨ (???p ∧ r) ∨(q ∧ r ) (析取 ∧ ∨ 析取 范式) 范式 (p∧? ??q ∧? ??r )∨ (???p ∧(q∨ ? ??q) ∧ r) ) ∨ (q ∧ ∨ ∨ ∧(p∨ ? ??p) ∧ 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) m1∨ m3∨m4∨ m7 (主析取范式 主析取范式) 主析取范式 10 第二章 命题逻辑等值演算 主析取范式的用途(主合取范式类似讨论) 主析取范式的用途(主合取范式类似讨论): 1、求公式的成真 成假赋值: 成假赋值: 、求公式的成真/成假赋值 若公式A中含有 个命题变项, 中含有n个命题变项 若公式 中含有 个命题变项,且A的主 的主 析取范式含s 个极小项, 析取范式含 个极小项,每一个极小项的 编码都是A的一个成真赋值 所以A有 个 的一个成真赋值, 编码都是 的一个成真赋值,所以 有s个 成真赋值,同理, 个成假赋值。 成线n-s个成假赋值。 个成假赋值 11 第二章 命题逻辑等值演算 例:(???p → q) →(? ??q ∨p) ?(??p ∨ q) ∨(? ??q ∨p) ( (???p ∧ ? ??q) ∨? ??q ∨p (???p ∧ ? ??q) ∨(???q ∧(p∨ ???p)) ∨(p ∧(q∨ ???q)) p ) m0∨m2∨ m3 ∨ ∨ M1 成真赋值: 、 、 成线 成假赋值: 成假赋值:01 12 第二章 命题逻辑等值演算 含有3个命题变项 例:已知公式A含有 个命题变项 已知公式 含有 个命题变项p,r,q,并且它的 , 成线,求A的主合取范式 成真赋值为 , , , 的主合取范式 和主析取范式。 和主析取范式。 因为主析取范式是由所有的取值为1的极小项 解:因为主析取范式是由所有的取值为 的极小项 析取构成, 析取构成,而成真赋值所对应的即为极小项的 编码,所以主析取范式为: 编码,所以主析取范式为: m0∨m3∨ m6 同理,主合取范式为: 同理,主合取范式为:M1 ∧ M2 ∧ M4 ∧ M5 ∧ M7 13 第二章 命题逻辑等值演算 2、判断公式的类型: 、判断公式的类型: 设公式A中含有 个命题变项, 中含有n个命题变项 设公式 中含有 个命题变项,则: 的主析取范式含全部2 (1)A为重言式 A的主析取范式含全部 n ) 为重言式 的主析取范式含全部 个极小项。 个极小项。 (2)A为矛盾式 A的主析取范式不含任何 ) 为矛盾式 的主析取范式不含任何 极小项, 的主析取范式为0。 极小项,记A的主析取范式为 。 的主析取范式为 (3)A为可满足式 A的主析取范式至少含 ) 为可满足式 的主析取范式至少含 一个极小项。 一个极小项。 14 第二章 命题逻辑等值演算 的主析取/合取范式 例:求例2.7的主析取 合取范式。 求例 的主析取 合取范式。 主析取范式) 接前 m1∨ m3∨m4∨ m7 (主析取范式 主析取范式 可知,该公式为可满足式。 可知,该公式为可满足式。 练习: 练习: 1、( ? ??p → q) →(q → ? ??p) 、 2、(p ∨ ? ??p ) → ((q∧ ? ??q) ∧ ? ??r) 、 ∧ 3、 ((p → q) ∧(q → r)) → (p → r) 、 15 第二章 命题逻辑等值演算 3、判断两个命题是否等值: 、判断两个命题是否等值: 设公式A、 中共含有 个命题变项, 中共含有n个命题变项 设公式 、B中共含有 个命题变项,按n个 个 命题变项求出A、 的主析取范式 的主析取范式A`、 。 命题变项求出 、 B的主析取范式 、 B`。 若A`=B` ,则A B,否则 、B不等值 。 ,否则A、 不等值 例题参见例2.11 例题参见例 练习: 、 练习:1、(p → q) ∧(p → r) 与 p →(q ∧ r) 2、 p →(q ∧ r) 与 p ∨(q → r) 、 16 第二章 命题逻辑等值演算 解:1、 (p → q) ∧(p → r) 、 (? ??p ∨ q) ∧(? ??p ∨ r) ? ??p ∨( q ∧ r) m0 ∨ m1 ∨ m2 ∨ m3∨m7 p →(q ∧ r) ? ??p ∨( q ∧ r) m0 ∨ m1 ∨ m2 ∨ m3∨m7 所以 (p → q) ∧(p → r) p →(q ∧ r) 17 第二章 命题逻辑等值演算 解: 2、 p →(q ∧ r) 、 ? ??p ∨( q ∧ r) m0 ∨ m1 ∨ m2 ∨ m3∨m7 p ∨(q → r) p ∨? ??q ∨ r m0 ∨ m1 ∨m3∨ m4 ∨ m5∨m6 ∨m7 不等值。 所以 (p → q) ∧(p → r) 与 p →(q ∧ r) 不等值。 18 第二章 命题逻辑等值演算 4、解决实际问题: 、解决实际问题: 某勘探队有3名队员, 有一天取得一块矿样, 人判断如下 人判断如下: 某勘探队有 名队员,有一天取得一块矿样, 3人判断如下: 名队员 甲说:这不是铁,也不是铜。 甲说:这不是铁,也不是铜。 乙说:这不是铁,是锡。 乙说:这不是铁,是锡。 丙说:这不是锡,是铁。 丙说:这不是锡,是铁。 经实验室鉴定发现,其中一人的两个判断全对, 经实验室鉴定发现,其中一人的两个判断全对,一人判对一 半,另一人全错。试根据以上情况,判断矿样的种类。 另一人全错。试根据以上情况,判断矿样的种类。 19 第二章 命题逻辑等值演算 矿样是铁。 矿样是铜 矿样是铜。 矿样是锡 矿样是锡。 解: 设 p:矿样是铁。q :矿样是铜。r :矿样是锡。 矿样是铁 根据题设知有六种情况: 根据题设知有六种情况: 甲正确,乙对一半,丙全错; ①甲正确,乙对一半,丙全错; 甲正确,乙全错,丙对一半; ②甲正确,乙全错,丙对一半; 甲对一半,乙正确,丙全错; ③甲对一半,乙正确,丙全错; 甲对一半,乙全错,丙正确; ④甲对一半,乙全错,丙正确; ⑤甲全错,乙正确,丙对一半; 甲全错,乙正确,丙对一半; 甲全错,乙对一半,丙正确。 ⑥甲全错,乙对一半,丙正确。 20 第二章 命题逻辑等值演算 以上六种情况对应公式分别为: 以上六种情况对应公式分别为: ①(???p∧???q) ∧((???p∧???r)∨(p∧r)) ∧(???p∧r) …① ∧ ∧ ∨ ∧ ∧ ① ② (???p∧???q) ∧(p∧???r)∧((p∧r)∨(???p∧? ??r)) …② ∧ ∧ ∧ ∧ ∨ ∧ ② ③ ((???p∧q)∨(p∧???q))∧(???p∧r)∧(???p∧r) ???p∧q ∧r… ③ ∧ ∨ ∧ ∧ ∧ ∧ ∧ ∧ ④ ((???p∧q)∨(p∧???q))∧(p∧???r)∧(p∧? ??r) p∧ ? ??q ∧ ??? ∧ ∨ ∧ ∧ ∧ ∧ ∧ ∧ r…④ ④ ⑤ (p∧q)∧(? ??p∧r)∧((p∧r)∨(???p∧? ??r))… ⑤ ∧ ∧ ∧ ∧ ∧ ∨ ∧ ⑥ (p∧q)∧ ((???p∧???r) ∨( p∧r) ) ∧ (p∧? ??r)… ⑥ ∧ ∧ ∧ ∧ ∧ 21 第二章 命题逻辑等值演算 判断经过为F, 解: 设 判断经过为 ,则: F ① ∨② ∨ ③ ∨ ④ ∨ ⑤ ∨ ⑥ (???p∧q ∧r) ∨(p∧ ? ??q ∧ ? ??r) =1 ∧ ∧ 但不能同时为铜又为锡,因而只能对应p∧ 但不能同时为铜又为锡,因而只能对应 ∧ ? ??q ∧ ? ??r,即 , 不是铜,也不是锡,而是铁。 不是铜,也不是锡,而是铁。 22 第二章 命题逻辑等值演算 关于主合取范式 1、由公式的主析取范式求主合取范式 、 设公式A中含有 个命题变项, 中含有n个命题变项 的主析取范式含s 设公式 中含有 个命题变项,且A的主析取范式含 个极 的主析取范式含 小项, 小项,即 A mi1 ∨ mi2 ∨ … ∨ mis,0≤ij≤ 2n-1,j=1,2, …,s. ≤ 没出现的极小项为m 没出现的极小项为 j1 , mj2 … ∨ mjk (k= 2n-s), 它们下标的 二进制表示为???A的成真赋值 因而???A的主析取范式为 的成真赋值, 二进制表示为 的成真赋值,因而 的主析取范式为 ???A= mj1 ∨ mj2 ∨ … ∨ mj k 23 第二章 命题逻辑等值演算 由否定律:定理 知 由否定律:定理2.4知 A ????A ? (??mj1 ∨ mj2 ∨ … ∨ mjk) ( ? ??mj1 ∧ ? ??mj2 ∧ … ∧ ? ??mjk 定理2.4知 定理 知 Mj1 ∧ Mj2 ∧ … ∧ Mj 例题参见2.13 例题参见 24 第二章 命题逻辑等值演算 2、重言式与矛盾式的主合取范式 、 设公式A中含有 个命题变项, 中含有n个命题变项 设公式 中含有 个命题变项,则: 的主合取范式含全部2 (1)A为矛盾式 A的主合取范式含全部 n ) 为矛盾式 的主合取范式含全部 个极大项。 个极大项。 (2)A为重言式 A的主合取范式不含任何 ) 为重言式 的主合取范式不含任何 极大项, 的主合取范式为1。 极大项,记A的主合取范式为 。 的主合取范式为 (3)A为可满足式 A的主合取范式中极大 ) 为可满足式 的主合取范式中极大 项的个数一定小于2n 。 项的个数一定小于 25 第二章 命题逻辑等值演算 重申: 重申: A B 当且仅当 A 、 B 含有相同的真值表或 A 、 B 有相同的主析 (合)取范式。 26 第二章 命题逻辑等值演算 2.3 联结词的完备集 定义2.6 称F:{0,1}n→{0,1}为n元真值 定义 : , , 为 元真值 函数。 函数。 定义2.7 :设S是一个联结词集合,如果任 是一个联结词集合, 定义 是一个联结词集合 元真值函数都可以由仅含S中的联结词 何n元真值函数都可以由仅含 中的联结词 元真值函数都可以由仅含 构成的公式表示, 则称S是联结词完备集 是联结词完备集。 构成的公式表示 , 则称 是联结词完备集 。 定理 2.6 S={ ?} ∨,∧,??是联结词的完备集。 ∧ ∨ 是联结词的完备集 27 第二章 命题逻辑等值演算 定理 2.6 S={ ?} ∨,∧,??是联结词的完备集。 ∧ ∨ 是联结词的完备集 以下联结词集都是完备集: 推论 以下联结词集都是完备集: , (1)S1={?}?,→,∨,∧,?? ) (2)S2={?}→,∨,∧,?? ) , (3)S3={?}∧,?? ) , (4)S4={?}∨,?? ) , (5)S5={?}→,?? ) , 28 第二章 命题逻辑等值演算——小结 命题逻辑等值演算——小结 本章基本知识点: 本章基本知识点: 24个重要等值式 个重要等值式 析取范式与合取范式及相关定理 极大项和极小项的概念 主合取范式、主析取范式, 主合取范式、主析取范式,二者的关系 必考题,一般运算较繁,应力求熟练) (必考题,一般运算较繁,应力求熟练) 联结词的完备集 29 第二章 命题逻辑等值演算——小结 命题逻辑等值演算——小结 本章考查要点: 一、本章考查要点: 24重要等值式 重要等值式 主合取范式、主析取范式, 主合取范式、主析取范式,二者的关系 必考题,一般运算较繁,应力求熟练) (必考题,一般运算较繁,应力求熟练) 典型例题: 二、典型例题: 1、已知命题公式为G=(?P∧Q)→R,则命题公式G 、 的析取范式是 ______. 2、与命题公式P→(Q→R)等值的公式是( ) (A)(P∨Q)→R (B)(P∧Q)→R (C)(P→Q)→R (D) P→(Q∨R) 30 第二章 命题逻辑等值演算——小结 命题逻辑等值演算——小结 3、设命题公式G??(P →Q),H ? P →(Q → ? P),则G 与H的关系是( ) A. G?H B. H→G C. H = G D. G = H 4、设A,B为任意命题公式,C为重言式,若A∧C?B ∧C,那么A?B是_________式(重言式、矛盾式或 可满足式)。 5、 命题公式(P→Q)∨P的主合取范式为______,主 析取范式为_______。 6、化简下式: (A∧B∧C)∨(?A∧B∧C) 31

本文链接:http://scmountainwx.net/diwufanshi/567.html
随机为您推荐歌词

联系我们 | 关于我们 | 网友投稿 | 版权声明 | 广告服务 | 站点统计 | 网站地图

版权声明:本站资源均来自互联网,如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

Copyright @ 2012-2013 织梦猫 版权所有  Powered by Dedecms 5.7
渝ICP备10013703号  

回顶部