离散数学-22-3命题逻辑等值演算

课 件 1 2.2 命题逻辑等值演算 2.2.1 等 值 式 与 等 值 演 算 等 值 式 与 基 本 等 值 式 真 值 表 法 与 等 值 演 算 法 2.2.2 联 结 词 完 备 集 真 值 函 数 联 结 词 完 备 集 与 非 联 结 词 和 或 非 联 结 词 课 件 2 等 值 式定 义 2.11 若 等 价 式 AB是 重 言 式 , 则 称 A与 B等 值 , 记 作AB, 并 称 AB是 等 值 式说 明 : (1) 是 元 语 言 符 号 , 不 要 混 同 于 和 =(2) A与 B等 值 当 且 仅 当 A与 B在 所 有 可 能 赋 值 下 的 真 值 都 相同 , 即 A与 B有 相 同 的 真 值 表(3) n个 命 题 变 项 的 真 值 表 共 有 个 , 故 每 个 命 题 公 式 都 有无 穷 多 个 等 值 的 命 题 公 式(4) 可 能 有 哑 元 出 现 . 在 B中 出 现 , 但 不 在 A中 出 现 的 命 题 变项 称 作 A的 哑 元 . 同 样 ,在 A中 出 现 , 但 不 在 B中 出 现 的 命 题 变项 称 作 B的 哑 元 . 哑 元 的 值 不 影 响 命 题 公 式 的 真 值 . n22 课 件 3 真 值 表 法例 1 判 断 (pq) 与 pq 是 否 等 值解结 论 : (pq) (pq) p q p q pq (pq) pq (pq)(pq) 0 0 1 1 0 1 1 1 0 1 1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 1 0 0 1 0 0 1 课 件 4 真 值 表 法 (续 )例 2 判 断 下 述 3个 公 式 之 间 的 等 值 关 系 : p(qr), (pq)r, (pq)r解 p q r p(qr) (pq)r (pq)r 0 0 0 1 0 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 0 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 p(qr)与 (pq)r等 值 , 但 与 (pq)r不 等 值 课 件 5 基 本 等 值 式双 重 否 定 律 AA幂 等 律 AAA, AAA交 换 律 ABBA, ABBA结 合 律 (AB)CA(BC) (AB)CA(BC)分 配 律 A(BC)(AB)(AC) A(BC) (AB)(AC)德 摩 根 律 (AB)AB (AB)AB吸 收 律 A(AB)A, A(AB)A 课 件 6 基 本 等 值 式 (续 )零 律 A11, A00 同 一 律 A0A, A1A排 中 律 AA1矛 盾 律 AA0蕴 涵 等 值 式 ABAB等 价 等 值 式 AB(AB)(BA)假 言 易 位 ABBA等 价 否 定 等 值 式 ABAB归 谬 论 (AB)(AB) A 课 件 7 等 值 演 算等 值 演 算 : 由 已 知 的 等 值 式 推 演 出 新 的 等 值 式 的 过 程置 换 规 则 : 若 AB, 则 (B)(A) 例 3 证 明 p(qr) (pq)r证 p(qr) p(qr) （ 蕴 涵 等 值 式 ） (pq)r （ 结 合 律 ） (pq)r （ 德 摩 根 律 ） (pq) r （ 蕴 涵 等 值 式 ） 课 件 8 实 例等 值 演 算 不 能 直 接 证 明 两 个 公 式 不 等 值 . 证 明 两 个 公 式 不等 值 的 基 本 思 想 是 找 到 一 个 赋 值 使 一 个 成 真 , 另 一 个 成 假 .例 4 证 明 : p(qr) (pq) r方 法 一 真 值 表 法 （ 见 例 2）方 法 二 观 察 法 . 容 易 看 出 000使 左 边 成 真 , 使 右 边 成 假 .方 法 三 先 用 等 值 演 算 化 简 公 式 , 再 观 察 . 课 件 9 实 例例 5 用 等 值 演 算 法 判 断 下 列 公 式 的 类 型(1) q(pq) 解 q(pq) q(pq) （ 蕴 涵 等 值 式 ） q(pq) （ 德 摩 根 律 ） p(qq) （ 交 换 律 ， 结 合 律 ） p0 （ 矛 盾 律 ） 0 （ 零 律 ）该 式 为 矛 盾 式 . 课 件 10 实 例 (续 )(2) (pq)(qp) 解 (pq)(qp) (pq)(qp) （ 蕴 涵 等 值 式 ） (pq)(pq) （ 交 换 律 ） 1该 式 为 重 言 式 . 课 件 11 实 例 (续 )(3) (pq)(pq)r) 解 (pq)(pq)r) (p(qq)r （ 分 配 律 ） p1r （ 排 中 律 ） pr （ 同 一 律 ）非 重 言 式 的 可 满 足 式 .如 101是 它 的 成 真 赋 值 ,000是 它 的成 假 赋 值 .总 结 :A为 矛 盾 式 当 且 仅 当 A0; A为 重 言 式 当 且 仅 当 A1说 明 :演 算 步 骤 不 惟 一 ,应 尽 量 使 演 算 短 些 课 件 12 真 值 函 数定 义 2.12 称 F:0,1n0,1为 n元 真 值 函 数n元 真 值 函 数 共 有 个每 一 个 命 题 公 式 对 应 于 一 个 真 值 函 数每 一 个 真 值 函 数 对 应 无 穷 多 个 命 题 公 式n221元 真 值 函 数 p 0 0 0 1 1 1 0 1 0 1 )1(3)1(2)1(1)1(0 FFFF 课 件 13 2元 真 值 函 数 p q 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 p q 0 0 1 1 1 1 1 1 1 1 0 1 0 0 0 0 1 1 1 1 1 0 0 0 1 1 0 0 1 1 1 1 0 1 0 1 0 1 0 1 )2(7)2(6)2(5)2(4)2(3)2(2)2(1)2(0 FFFFFFFF )2(15)2(14)2(13)2(12)2(11)2(10)2(9)2(8 FFFFFFFF 课 件 14 联 结 词 完 备 集定 义 2.13 设 S是 一 个 联 结 词 集 合 , 如 果 任 何 n(n1) 元 真 值函 数 都 可 以 由 仅 含 S中 的 联 结 词 构 成 的 公 式 表 示 ,则 称 S是联 结 词 完 备 集定 理 2.1 下 述 联 结 词 集 合 都 是 完 备 集 :(1) S1=, , , , (2) S2=, , , (3) S 3=, , (4) S4=, (5) S5=, (6) S6=, AB (AB)(BA)AB ABAB (AB) (AB)AB (AB)AB (A)B AB 课 件 15 复 合 联 结 词与 非 式 : pq(pq), 称 作 与 非 联 结 词或 非 式 : pq(pq), 称 作 或 非 联 结 词pq为 真 当 且 仅 当 p,q不 同 时 为 真pq为 真 当 且 仅 当 p,q不 同 时 为 假定 理 2.2 ,是 联 结 词 完 备 集证 p (pp) pp pq (pq) (pq) (pq)(pq)得 证 是 联 结 词 完 备 集 . 对 于 可 类 似 证 明 . 课 件 16 2.3 范式 2.3.1 析 取 范 式 与 合 取 范 式 简 单 析 取 式 与 简 单 合 取 式 析 取 范 式 与 合 取 范 式 2.3.2 主 析 取 范 式 与 主 合 取 范 式 极 小 项 与 极 大 项 主 析 取 范 式 与 主 合 取 范 式 主 范 式 的 用 途 课 件 17 简 单 析 取 式 与 简 单 合 取 式文 字 :命 题 变 项 及 其 否 定 的 统 称简 单 析 取 式 :有 限 个 文 字 构 成 的 析 取 式如 p, q, pq, pqr, 简 单 合 取 式 :有 限 个 文 字 构 成 的 合 取 式如 p, q, pq, pqr, 定 理 2.3 (1) 一 个 简 单 析 取 式 是 重 言 式 当 且 仅 当 它 同 时 含某 个 命 题 变 项 和 它 的 否 定(2) 一 个 简 单 合 取 式 是 矛 盾 式 当 且 仅 当 它 同 时 含 某 个 命 题变 项 和 它 的 否 定 课 件 18 析 取 范 式 与 合 取 范 式析 取 范 式 :由 有 限 个 简 单 合 取 式 组 成 的 析 取 式 A1A2Ar, 其 中 A1,A2,Ar是 简 单 合 取 式合 取 范 式 :由 有 限 个 简 单 析 取 式 组 成 的 合 取 式 A1A2Ar , 其 中 A1,A2,Ar是 简 单 析 取 式范 式 :析 取 范 式 与 合 取 范 式 的 统 称 定 理 2.4 (1) 一 个 析 取 范 式 是 矛 盾 式 当 且 仅 当 它 的 每 一 个简 单 合 取 式 都 是 矛 盾 式(2) 一 个 合 取 范 式 是 重 言 式 当 且 仅 当 它 的 每 一 个 简 单 析 取式 都 是 重 言 式 课 件 19 范 式 存 在 定 理定 理 2.5 任 何 命 题 公 式 都 存 在 着 与 之 等 值 的 析 取 范 式 与 合取 范 式 .证 求 公 式 A的 范 式 的 步 骤 ：(1) 消 去 A中 的 , ABAB AB(AB)(AB)(2) 否 定 联 结 词 的 内 移 或 消 去 A A (AB)AB (AB)AB 课 件 20 范 式 存 在 定 理 (续 )(3) 使 用 分 配 律 A(BC)(AB)(AC) 求 合 取 范 式 A(BC) (AB)(AC) 求 析 取 范 式例 1 求 (pq)r 的 析 取 范 式 与 合 取 范 式解 (pq)r (pq)r (pq)r 析 取 范 式 (pr)(qr) 合 取 范 式注 意 : 公 式 的 析 取 范 式 与 合 取 范 式 不 惟 一 . 课 件 21 极 小 项 与 极 大 项定 义 2.17 在 含 有 n个 命 题 变 项 的 简 单 合 取 式 (简 单 析 取 式 )中 ,若 每 个 命 题 变 项 均 以 文 字 的 形 式 出 现 且 仅 出 现 一 次 ，而 且 第 i(1in)个 文 字 (按 下 标 或 字 母 顺 序 排 列 )出 现 在 左起 第 i位 上 ,称 这 样 的 简 单 合 取 式 (简 单 析 取 式 )为 极 小 项(极 大 项 )说 明 :(1) n个 命 题 变 项 产 生 2n个 极 小 项 和 2n个 极 大 项(2) 2n个 极 小 项 (极 大 项 )均 互 不 等 值(3) 用 m i表 示 第 i个 极 小 项 ,其 中 i是 该 极 小 项 成 真 赋 值 的 十进 制 表 示 . 用 Mi表 示 第 i个 极 大 项 ,其 中 i是 该 极 大 项 成 假 赋值 的 十 进 制 表 示 , mi(Mi)称 为 极 小 项 (极 大 项 )的 名 称 . 课 件 22 极 小 项 与 极 大 项 (续 )定 理 2.6 设 m i 与 Mi是 由 同 一 组 命 题 变 项 形 成 的 极 小 项 和 极大 项 , 则 mi Mi , Mi mi 极 小 项 极 大 项 公 式 成 真 赋 值 名 称 公 式 成 假 赋 值 名 称 pq 0 0 m0 pq 0 0 M0 pq 0 1 m1 pq 0 1 M1 pq 1 0 m2 pq 1 0 M2 pq 1 1 m3 pq 1 1 M3 p,q形 成 的 极 小 项 与 极 大 项 课 件 23 主 析 取 范 式 与 主 合 取 范 式主 析 取 范 式 :由 极 小 项 构 成 的 析 取 范 式主 合 取 范 式 :由 极 大 项 构 成 的 合 取 范 式例 如 ， n=3, 命 题 变 项 为 p, q, r时 ， (pqr)(pqr) m1m3 是 主 析 取 范 式 (pqr)(pqr) M1M5 是 主 合 取 范 式定 理 2.7 任 何 命 题 公 式 都 存 在 着 与 之 等 值 的 主 析 取 范 式 和主 合 取 范 式 , 并 且 是 惟 一 的 . 课 件 24 求 主 析 取 范 式 的 步 骤设 公 式 A含 命 题 变 项 p1,p2,pn(1) 求 A的 析 取 范 式 A=B1 B2 Bs, 其 中 Bj是 简 单 合 取式 j=1,2, ,s (2) 若 某 个 Bj既 不 含 pi, 又 不 含 pi, 则 将 Bj展 开 成 Bj Bj(pipi) (Bjpi)(Bjpi)重 复 这 个 过 程 , 直 到 所 有 简 单 合 取 式 都 是 长 度 为 n的 极 小项 为 止(3) 消 去 重 复 出 现 的 极 小 项 , 即 用 m i代 替 mimi(4) 将 极 小 项 按 下 标 从 小 到 大 排 列 课 件 25 求 主 合 取 范 式 的 步 骤设 公 式 A含 命 题 变 项 p1,p2,pn(1) 求 A的 合 取 范 式 A=B1B2 Bs, 其 中 Bj是 简 单 析 取式 j=1,2, ,s (2) 若 某 个 Bj既 不 含 pi, 又 不 含 pi, 则 将 Bj展 开 成 Bj Bj(pipi) (Bjpi)(Bjpi)重 复 这 个 过 程 , 直 到 所 有 简 单 析 取 式 都 是 长 度 为 n的 极 大项 为 止(3) 消 去 重 复 出 现 的 极 大 项 , 即 用 M i代 替 MiMi(4) 将 极 大 项 按 下 标 从 小 到 大 排 列 课 件 26 实 例例 1(续 ) 求 (pq)r 的 主 析 取 范 式 与 主 合 取 范 式解 (1) (pq)r (pq)r pq (pq)1 同 一 律 (pq)(rr) 排 中 律 (pqr)(pqr) 分 配 律 m4m5 r (pp)(qq)r 同 一 律 , 排 中 律 (pqr)(pqr)(pqr)(pqr) m 0 m2 m4 m6 分 配 律得 (pq)r m0 m2 m4 m5 m6可 记 作 (0,2,4,5,6) 课 件 27 实 例 (续 )(2) (pq)r (pr)(qr) pr p0r 同 一 律 p(qq)r 矛 盾 律 (pqr)(pqr) 分 配 律 M1M3 qr (pp)qr 同 一 律 , 矛 盾 律 (pqr)(pqr) 分 配 律 M 3M7得 (pq)r M1M3M7可 记 作 (1,3,7) 课 件 28 快 速 求 法设 公 式 含 有 n个 命 题 变 项 , 则长 度 为 k的 简 单 合 取 式 可 展 开 成 2n-k个 极 小 项 的 析 取例 如 公 式 含 p,q,r q (pqr)(pqr)(pqr)(pqr) m2 m3 m6 m7长 度 为 k的 简 单 析 取 式 可 展 开 成 2n-k个 极 大 项 的 合 取例 如 pr (pqr)(pqr) M 1M3 课 件 29 实 例例 2 (1) 求 A (pq)(pqr)r的 主 析 取 范 式解 用 快 速 求 法(1) pq (pqr)(pqr) m2 m3 pqr m1 r (pqr)(pqr)(pqr)(pqr) m1 m3 m5 m7得 A m 1 m2 m3 m5 m7 (1,2,3,5,7) 课 件 30 实 例 (续 )(2) 求 B p(pqr)的 主 合 取 范 式解 p (pqr)(pqr)(pqr)(pqr) M4M5M6M7 pqr M1得 B M1M4M5M6M7 (1,4,5,6,7) 课 件 31 主 析 取 范 式 的 用 途(1) 求 公 式 的 成 真 赋 值 和 成 假 赋 值设 公 式 A含 n个 命 题 变 项 , A的 主 析 取 范 式 有 s个 极 小 项 , 则 A有 s个 成 真 赋 值 , 它 们 是 极 小 项 下 标 的 二 进 制 表 示 , 其 余 2n-s个 赋 值 都 是 成 假 赋 值 例 如 (pq)r m0 m2 m4 m5 m6 成 真 赋 值 : 000,010,100,101,110; 成 假 赋 值 : 001,011,111 课 件 32 主 析 取 范 式 的 用 途 (续 )(2) 判 断 公 式 的 类 型 设 A含 n个 命 题 变 项 ， 则 A为 重 言 式 当 且 仅 当 A的 主 析 取 范 式 含 2n个 极 小 项A为 矛 盾 式 当 且 仅 当 A的 主 析 取 范 式 不 含 任 何 极 小 项 ,记 作 0 A为 可 满 足 式 当 且 仅 当 A的 主 析 取 范 式 中 至 少 含 一 个 极 小 项 课 件 33 实 例例 3 用 主 析 取 范 式 判 断 公 式 的 类 型 :(1) A (pq)q (2) B p(pq) (3) C (pq)r解 (1) A ( pq)q ( pq)q 0 矛 盾 式(2) B p(pq) 1 m0m1m2m3 重 言 式(3) C (pq)r (pq)r (pqr)(pqr)(pqr) (pqr)(pqr)(pqr) m 0m1m3 m5m7 非 重 言 式 的 可 满 足 式 课 件 34 主 析 取 范 式 的 用 途 (续 )(3) 判 断 两 个 公 式 是 否 等 值例 4 用 主 析 取 范 式 判 断 下 面 2组 公 式 是 否 等 值 :(1) p与 (pq)(pq)解 p p(qq) (pq)(pq) m2m3 (pq)(pq) (pq)(pq) (pq)(pq) m 2m3故 p (pq)(pq) 课 件 35 实 例 (续 )(2) (pq)r 与 p(qr)解 (pq)r (pqr)(pqr) (pqr)(pqr)(pqr)(pqr) m1m3m5 m6m7 p(qr) (pq)(p r) (pqr)(pqr)(pqr)(pqr) m 5 m6m7故 (pq)r p(qr) 课 件 36 实 例例 5 某 单 位 要 从 A,B,C三 人 中 选 派 若 干 人 出 国 考 察 , 需 满足 下 述 条 件 :(1) 若 A去 , 则 C必 须 去 ;(2) 若 B去 , 则 C不 能 去 ;(3) A和 B必 须 去 一 人 且 只 能 去 一 人 .问 有 几 种 可 能 的 选 派 方 案 ?解 记 p:派 A去 , q:派 B去 , r:派 C去(1) pr, (2) qr, (3) (pq)(pq)求 下 式 的 成 真 赋 值 A=(pr)(qr)(pq)(pq) 课 件 37 实 例 (续 )求 A的 主 析 取 范 式 A=(pr)(qr)(pq)(pq) (pr)(qr)(pq)(pq) (pq)(pr)(rq)(rr) (pq)(pq) (pq)(pq)(pr)(pq) (rq)(pq)(pq)(pq) (pr)(pq)(rq)(pq) (pqr)(pqr)成 真 赋 值 :101,010结 论 : 方 案 1 派 A与 C去 , 方 案 2 派 B去 课 件 38 主 合 取 范 式由 主 析 取 范 式 求 主 合 取 范 式设没 有 出 现 的 极 小 项 是 siii mmmA 21 , 21 tjjj mmm 其 中 t=2n-s, tjjj mmmA 21 t ttjjj jjj jjj MMM mmm mmmA 21 21 21 )(于 是 课 件 39 主 合 取 范 式 (续 )例 6 求 A=(pqr)(pqr)(pqr)的 主 合 取 范 式解 A m1m3m7 M0M2M4M5M6矛 盾 式 的 主 合 取 范 式 含 全 部 2n个 极 大 项重 言 式 的 主 合 取 范 式 不 含 任 何 极 大 项 , 记 作 1