离散数学对偶和范式课件.ppt

《离散数学对偶和范式课件.ppt》由会员分享，可在线阅读，更多相关《离散数学对偶和范式课件.ppt（35页珍藏版）》请在装配图网上搜索。

1、1 1.5 对 偶 与 范 式 对 偶 式 与 对 偶 原 理 析 取 范 式 与 合 取 范 式 主 析 取 范 式 与 主 合 取 范 式 2 对 偶 式 和 对 偶 原 理定 义 在 仅 含 有 联 结 词 , , 的 命 题 公 式 A中 ， 将 换 成 , 换 成 ， 若 A中 含 有 0或 1， 就 将 0换 成 1， 1换 成 0， 所 得 命 题 公式 称 为 A的 对 偶 式 ， 记 为 A*.从 定 义 不 难 看 出 ， (A*)* 还 原 成 A显 然 ， A也 是 A*的 对 偶 式 。 可 见 A与 A*互 为对 偶 式 。 3 对 偶 式 和 对 偶 原 理定 理

2、 设 A和 A*互 为 对 偶 式 ， p1,p2,pn是 出 现 在 A和A*中 的 全 部 命 题 变 项 ， 将 A和 A*写 成 n元 函 数 形 式 ，则 (1) A(p1,p2,pn) A* ( p1, p2, pn) (2) A( p1, p2, pn) A* (p1,p2,pn) n (1)表 明 ， 公 式 A的 否 定 等 价 于 其 命 题 变 元 否 定 的对 偶 式 ； (2)表 明 ， 命 题 变 元 否 定 的 公 式 等 价 于 对偶 式 之 否 定 。 4 对 偶 式 和 对 偶 原 理定 理 （ 对 偶 原 理 ） 设 A， B为 两 个 命 题 公 式 ，

3、若 A B， 则 A* B*.有 了 等 值 式 、 代 入 规 则 、 替 换 规 则 和 对 偶定 理 ， 便 可 以 得 到 更 多 的 永 真 式 ， 证 明更 多 的 等 值 式 ， 使 化 简 命 题 公 式 更 为 方便 。 5 判 定 问 题真 值 表等 值 演 算范 式 6 析 取 范 式 与 合 取 范 式 文 字 :命 题 变 项 及 其 否 定 的 总 称如 p, q简 单 析 取 式 :有 限 个 文 字 构 成 的 析 取 式如 p, q, pq, pqr, 简 单 合 取 式 :有 限 个 文 字 构 成 的 合 取 式如 p, q, pq, pqr, 注 意 ：

4、 一 个 命 题 变 元 或 其 否 定 既 可 以 是 简 单 合 取式 ， 也 可 是 简 单 析 取 式 ， 如 p， q等 。 7 析 取 范 式 与 合 取 范 式 n 定 理 ： 简 单 合 取 式 为 永 假 式 的 充 要 条 件 是 ： 它同 时 含 有 某 个 命 题 变 元 及 其 否 定 。n 定 理 ： 简 单 析 取 式 为 永 真 式 的 充 要 条 件 是 ： 它同 时 含 有 某 个 命 题 变 元 及 其 否 定 。 8 析 取 范 式 与 合 取 范 式 简 单 析 取 式 :有 限 个 文 字 构 成 的 析 取 式如 p, q, pq, pqr, 简

5、单 合 取 式 :有 限 个 文 字 构 成 的 合 取 式如 p, q, pq, pqr, 析 取 范 式 :由 有 限 个 简 单 合 取 式 组 成 的 析 取 式 A1A2Ar, 其 中 A1,A2,Ar是 简 单 合 取 式合 取 范 式 :由 有 限 个 简 单 析 取 式 组 成 的 合 取 式 A 1A2Ar , 其 中 A1,A2,Ar是 简 单 析 取 式 9 析 取 范 式 与 合 取 范 式 (续 )范 式 :析 取 范 式 与 合 取 范 式 的 总 称 公 式 A的 析 取 范 式 : 与 A等 值 的 析 取 范 式公 式 A的 合 取 范 式 : 与 A等 值

6、的 合 取 范 式说 明 ： 单 个 文 字 既 是 简 单 析 取 式 ， 又 是 简 单 合 取 式形 如 pqr, pqr 的 公 式 既 是 析 取 范 式 ，又 是 合 取 范 式 (为 什 么 ?) 10 命 题 公 式 的 范 式 定 理 任 何 命 题 公 式 都 存 在 着 与 之 等 值 的 析 取 范 式与 合 取 范 式 .求 公 式 A的 范 式 的 步 骤 ： (1) 消 去 A中 的 , （ 若 存 在 ） （ 消 去 公 式 中 除、 和 以 外 公 式 中 出 现 的 所 有 联 结 词 ） (2) 否 定 联 结 词 的 内 移 或 消 去 （ 使 用 (P

7、)P和 德 摩 根 律 ） (3) 使 用 分 配 律 对 分 配 （ 析 取 范 式 ） 对 分 配 （ 合 取 范 式 ）公 式 的 范 式 存 在 ， 但 不 惟 一 ， 这 是 它 的 局 限 性 11 求 公 式 的 范 式 举 例 例 求 下 列 公 式 的 析 取 范 式 与 合 取 范 式(1) A=(pq)r解 (pq)r (pq)r （ 消 去 ） pqr （ 结 合 律 ）这 既 是 A的 析 取 范 式 （ 由 3个 简 单 合 取 式 组 成 的 析取 式 ） ， 又 是 A的 合 取 范 式 （ 由 一 个 简 单 析 取 式组 成 的 合 取 式 ） 12 求 公

8、 式 的 范 式 举 例 (续 )(2) B=(pq)r解 (pq)r (pq)r （ 消 去 第 一 个 ） (pq)r （ 消 去 第 二 个 ） (pq)r （ 否 定 号 内 移 德 摩 根 律 ）这 一 步 已 为 析 取 范 式 （ 两 个 简 单 合 取 式 构 成 ）继 续 ： (pq)r (pr)(qr) （ 对 分 配 律 ）这 一 步 得 到 合 取 范 式 （ 由 两 个 简 单 析 取 式 构 成 ） 13 极 小 项 与 极 大 项 定 义 在 含 有 n个 命 题 变 项 的 简 单 合 取 式 (简 单 析 取 式 )中 ，若 每 个 命 题 变 项 均 以 文

9、 字 的 形 式 在 其 中 出 现 且 仅 出 现 一次 ， 而 且 第 i（ 1in） 个 文 字 出 现 在 左 起 第 i位 上 ， 称 这 样的 简 单 合 取 式 （ 简 单 析 取 式 ） 为 极 小 项 （ 极 大 项 ） .n 例 如 ， 两 个 命 题 变 元 p和 q， 其 构 成 的 小 项 有 pq，pq， pq和 pq； 而 三 个 命 题 变 元 p、 q和 r， 其 构成 的 小 项 有 pqr， pqr， pqr， pqr，pqr ， pqr， pqr， pqr。 14 极 小 项 与 极 大 项 定 义 在 含 有 n个 命 题 变 项 的 简 单 合 取

10、式 (简 单 析 取 式 )中 ，若 每 个 命 题 变 项 均 以 文 字 的 形 式 在 其 中 出 现 且 仅 出 现 一次 ， 而 且 第 i（ 1in） 个 文 字 出 现 在 左 起 第 i位 上 ， 称 这 样的 简 单 合 取 式 （ 简 单 析 取 式 ） 为 极 小 项 （ 极 大 项 ） .例 如 ， 由 两 个 命 题 变 元 p和 q， 构 成 大 项 有 pq， pq，pq， pq； 三 个 命 题 变 元 p， q和 r， 构 成 pqr，pqr， pqr， pqr， pqr， pqr，pqr， pqr。 15 极 小 项 与 极 大 项 说 明 ： n个 命 题

11、 变 项 产 生 2n个 极 小 项 和 2n个 极 大 项 2n个 极 小 项 （ 极 大 项 ） 均 互 不 等 值 用 mi表 示 第 i个 极 小 项 ， 其 中 i是 该 极 小 项 成 真 赋 值 的 十进 制 表 示 . （ 将 命 题 变 元 按 字 典 序 排 列 ， 并 且 把 命 题 变元 与 1对 应 ， 命 题 变 元 的 否 定 与 0对 应 ， 则 可 对 2n个 小 项依 二 进 制 数 编 码 ） 用 Mi表 示 第 i个 极 大 项 ， 其 中 i是 该 极 大 项 成 假 赋 值 的 十进 制 表 示 。 （ 将 n个 命 题 变 元 排 序 ， 并 且

12、把 命 题 变 元 与 对 应 ， 命 题 变 元 的 否 定 与 对 应 ， 则 可 对 2 n个 大 项 按二 进 制 数 编 码 ） mi(Mi)称 为 极 小 项 (极 大 项 )的 名 称 . mi与 Mi的 关 系 : mi Mi , Mi mi 16 极 小 项 与 极 大 项 (续 )由 p, q两 个 命 题 变 项 形 成 的 极 小 项 与 极 大 项 公 式 成 真 赋 值 名 称 公 式 成 假 赋 值 名 称 p q p q p q p q 0 0 0 1 1 0 1 1 m0m1m2m 3 p q p q p q p q 0 0 0 1 1 0 1 1 M0M1M

13、2M3 极 小 项 极 大 项 17 由 p, q, r三 个 命 题 变 项 形 成 的 极 小 项 与 极 大 项 极 小 项 极 大 项 公 式 成 真赋 值 名 称 公 式 成 假赋 值 名 称 p q rp q rp q rp q rp q rp q rp q rp q r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 m0m1m2m 3m4m5m6m7 p q r p q r p q r p q r p q r p q r p q r p q r 0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1 M0M1M2M3M

14、4M5M6M7 小 项 的 性 质 ：n (a) 没 有 两 个 小 项 是 等 价 的 ， 即 是 说 各 小 项 的 真值 表 都 是 不 同 的 ；n (b)任 意 两 个 不 同 的 小 项 的 合 取 式 是 永 假 的 ：mi mj ， ij。n (c)所 有 小 项 之 析 取 为 永 真 ： mi 。n (d)每 个 小 项 只 有 一 个 解 释 为 真 ， 且 其 真 值 1位 于主 对 角 线 上 。 181 ni 大 项 的 性 质 ：n (a) 没 有 两 个 大 项 是 等 价 的 。n (b) 任 何 两 个 不 同 大 项 之 析 取 是 永 真 的 ， 即Mi

15、 Mj ， ij。n (c) 所 有 大 项 之 合 取 为 永 假 ， 即 Mi 。n (d) 每 个 大 项 只 有 一 个 解 释 为 假 ， 且 其 真 值 0位 于主 对 角 线 上 。 191 ni 20 主 析 取 范 式 与 主 合 取 范 式 主 析 取 范 式 : 由 极 小 项 构 成 的 析 取 范 式主 合 取 范 式 : 由 极 大 项 构 成 的 合 取 范 式例 如 ， n=3, 命 题 变 项 为 p, q, r时 ， (pqr)(pqr) m1m3 是 主 析 取 范 式 (pqr)(pqr) M1M5 是 主 合 取 范 式 A的 主 析 取 范 式 :

16、与 A等 值 的 主 析 取 范 式 A的 主 合 取 范 式 : 与 A等 值 的 主 合 取 范 式 . 21 主 析 取 范 式 与 主 合 取 范 式 (续 )定 理 任 何 命 题 公 式 都 存 在 着 与 之 等 值 的 主 析 取 范式 和 主 合 取 范 式 , 并 且 是 惟 一 的 . 用 等 值 演 算 法 求 公 式 的 主 范 式 的 步 骤 ： (1) 先 求 析 取 范 式 （ 合 取 范 式 ） (2) 将 不 是 极 小 项 （ 极 大 项 ） 的 简 单 合 取 式 （ 简 单 析 取 式 ） 化 成 与 之 等 值 的 若 干 个 极 小 项 的 析 取

17、 （ 极 大 项 的 合 取 ） ， 需 要 利 用 同 一 律 （ 零 律 ） 、 排 中 律 （ 矛 盾 律 ） 、 分 配 律 、 幂 等 律 等 . (3) 极 小 项 （ 极 大 项 ） 用 名 称 m i（ Mi） 表 示 ， 并按 角 标 从 小 到 大 顺 序 排 序 . 22 主 析 取 范 式 与 主 合 取 范 式 (续 )用 等 值 演 算 法 求 公 式 的 主 范 式 的 步 骤 ： (1) 先 求 析 取 范 式 (2) 删 除 析 取 范 式 中 所 有 为 永 假 的 简 单 合 取 式 (3)用 等 幂 律 化 简 简 单 合 取 式 中 同 一 命 题 变

18、 元 的 重复 出 现 为 一 次 出 现 ， 如 p pp。 (4) 用 同 一 律 补 进 简 单 合 取 式 中 未 出 现 的 所 有 命 题变 元 ， 如 q， 则 pp （ q q)， 并 用 分 配 律 展开 之 ， 将 相 同 的 简 单 合 取 式 的 多 次 出 现 化 为 一 次出 现 ， 这 样 得 到 了 给 定 公 式 的 主 析 取 范 式 。 从 A的 主 析 取 范 式 求 其 主 合 取 范式 的 步 骤n (a) 求 出 A的 主 析 取 范 式 中 设 有 包 含 的 小项 。(b) 求 出 与 (a)中 小 项 的 下 标 相 同 的 大 项 。(c)

19、 做 (b)中 大 项 之 合 取 ， 即 为 A的 主 合 取 范式 。例 如 ， (pq)qm1m3， 则(pq)qM0M2。 23 24 求 公 式 的 主 范 式例 求 公 式 A=(pq)r的 主 析 取 范 式 与 主 合 取 范 式 . (1) 求 主 析 取 范 式 (pq)r (pq)r , （ 析 取 范 式 ） (pq) (pq)(rr) (pqr)(pqr) m 6m7 , 25 求 公 式 的 主 范 式 (续 ) r (pp)(qq)r (pqr)(pqr)(pqr)(pqr) m1m3m5m7 , 代 入 并 排 序 ， 得 (pq)r m1m3m5 m6m7（

20、主 析 取 范 式 ） 26 求 公 式 的 主 范 式 (续 ) (2) 求 A的 主 合 取 范 式 (pq)r (pr)(qr) , （ 合 取 范 式 ） pr p(qq)r (pqr)(pqr) M 0M2, 27 求 公 式 的 主 范 式 (续 ) qr (pp)qr (pqr)(pqr) M0M4 , 代 入 并 排 序 ， 得 (pq)r M0M2M4 （ 主 合 取 范 式 ） 28 主 范 式 的 用 途 与 真 值 表 相 同 (1) 求 公 式 的 成 真 赋 值 和 成 假 赋 值 例 如 (pq)r m1m3m5 m6m7， 其 成 真 赋 值 为 001, 01

21、1, 101, 110, 111， 其 余 的 赋 值 000, 010, 100为 成 假 赋 值 . 类 似 地 ， 由 主 合 取 范 式 也 可 立 即 求 出 成 假 赋 值 和 成 真 赋 值 . 29 主 范 式 的 用 途 (续 ) (2) 判 断 公 式 的 类 型 设 A含 n个 命 题 变 项 ， 则 A为 重 言 式 A的 主 析 取 范 式 含 2n个 极 小 项 A的 主 合 取 范 式 为 1.A为 矛 盾 式 A的 主 析 取 范 式 为 0 A的 主 合 析 取 范 式 含 2n个 极 大 项A为 非 重 言 式 的 可 满 足 式A的 主 析 取 范 式 中

22、 至 少 含 一 个 且 不 含 全 部 极 小 项A的 主 合 取 范 式 中 至 少 含 一 个 且 不 含 全 部 极 大 项 30 主 范 式 的 用 途 (续 )例 用 主 析 取 范 式 判 断 下 述 两 个 公 式 是 否 等 值 ： p(qr) 与 (pq)r p(qr) 与 (pq)r解 p(qr) = m0m1m2m3 m4m5 m7 (pq)r = m0m1m2m3 m4m5 m7 (pq)r = m1m3 m4m5 m7显 见 ， 中 的 两 公 式 等 值 ， 而 的 不 等 值 . (3) 判 断 两 个 公 式 是 否 等 值说 明 ： 由 公 式 A的 主 析

23、 取 范 式 确 定 它 的 主 合 取 范 式 ， 反 之 亦 然 . 用 公 式 A的 真 值 表 求 A的 主 范 式 . 31 主 范 式 的 用 途 (续 ) 例 某 公 司 要 从 赵 、 钱 、 孙 、 李 、 周 五 名 新 毕业 的 大 学 生 中 选 派 一 些 人 出 国 学 习 . 选 派 必 须满 足 以 下 条 件 ： (1)若 赵 去 ， 钱 也 去 ； (2)李 、 周 两 人 中 至 少 有 一 人 去 ； (3)钱 、 孙 两 人 中 有 一 人 去 且 仅 去 一 人 ； (4)孙 、 李 两 人 同 去 或 同 不 去 ； (5)若 周 去 ， 则 赵

24、、 钱 也 去 . 试 用 主 析 取 范 式 法 分 析 该 公 司 如 何 选 派 他 们 出国 ？ 32 例 (续 )解 此 类 问 题 的 步 骤 为 ： 将 简 单 命 题 符 号 化 写 出 各 复 合 命 题 写 出 由 中 复 合 命 题 组 成 的 合 取 式 求 中 所 得 公 式 的 主 析 取 范 式 33 例 (续 )解 设 p： 派 赵 去 ， q： 派 钱 去 ， r： 派 孙 去 ， s： 派 李 去 ， u： 派 周 去 . (1) (pq) (2) (su) (3) (qr)(qr) (4) (rs)(rs) (5) (u(pq) (1) (5)构 成 的

25、合 取 式 为 A=(pq)(su)(qr)(qr) (rs)(rs)(u(pq) 34 例 (续 ) A (pqrsu)(pqrsu)结 论 ： 由 可 知 ， A的 成 真 赋 值 为 00110与 11001，因 而 派 孙 、 李 去 （ 赵 、 钱 、 周 不 去 ） 或 派 赵 、 钱 、周 去 （ 孙 、 李 不 去 ） . A的 演 算 过 程 如 下 : A (pq)(qr)(qr)(su)(u(pq) (rs)(rs) （ 交 换 律 )B 1= (pq)(qr)(qr) (pqr)(pqr)(qr) （ 分 配 律 ） 35 例 (续 )B2= (su)(u(pq) (su)(pqs)(pqu) （ 分 配 律 ）B1B2 (pqrsu)(pqrsu) (qrsu)(pqrs)(pqru)再 令 B3 = (rs)(rs)得 A B1B2B3 (pqrsu)(pqrsu)注 意 ： 在 以 上 演 算 中 多 次 用 矛 盾 律要 求 ： 自 己 演 算 一 遍