离散数学-31-2一阶逻辑

《离散数学-31-2一阶逻辑》由会员分享，可在线阅读，更多相关《离散数学-31-2一阶逻辑（38页珍藏版）》请在装配图网上搜索。

1、课 件 1 第 3章 一 阶 逻 辑 课 件 2 第 3章 一 阶 逻 辑 3.1 一 阶 逻 辑 基 本 概 念 3.2 一 阶 逻 辑 等 值 演 算 课 件 3 3.1 一 阶 逻 辑 基 本 概 念 3.1.1 命 题 逻 辑 的 局 限 性 3.1.2 个 体 词 、 谓 词 与 量 词 个 体 常 项 、 个 体 变 项 、 个 体 域 、 全 总 个 体 域 谓 词 常 项 、 谓 词 变 项 全 称 量 词 、 存 在 量 词 3.1.3 一 阶 逻 辑 命 题 符 号 化 课 件 4 3.1 一 阶 逻 辑 基 本 概 念 (续 ) 3.1.4 一 阶 逻 辑 公 式 与 分

2、 类 一 阶 语 言 L （ 字 母 表 、 项 、 原 子 公 式 、 合 式公 式 ） 辖 域 和 指 导 变 元 、 约 束 出 现 和 自 由 出 现 闭 式 一 阶 语 言 L 的 解 释 永 真 式 、 矛 盾 式 、 可 满 足 式 代 换 实 例 课 件 5 命 题 逻 辑 的 局 限 性 苏 格 拉 底 三 段 论 （ 1） 所 有 的 人 都 是 要 死 的 。 P （ 2） 苏 格 拉 底 是 人 。 Q （ 3） 苏 格 拉 底 是 要 死 的 。 R 应 当 有 ： PQR 但 当 P,Q取 1， 而 R取 0时 ， 真 值 为 0 课 件 6 个 体 词 与 个 体

3、 域个 体 词 : 所 研 究 对 象 中 可 以 独 立 存 在 的 具 体 或 抽 象 的 客 体 个 体 常 项 : 表 示 具 体 事 物 的 个 体 词 , 用 a, b, c等 表 示 个 体 变 项 : 表 示 抽 象 事 物 的 个 体 词 , 用 x, y, z等 表 示 个 体 域 : 个 体 变 项 的 取 值 范 围 全 总 个 体 域 : 宇 宙 间 一 切 事 物例 如 “ 若 x是 偶 数 , 则 x能 被 2整 除 .” x、 偶 数 和 2是 个 体 词 , 偶 数 和 2是 个 体 常 项 , x是 个 体 变 项 个 体 域 可 以 是 自 然 数 集 N

4、, 整 数 集 Z, 也 可 以 是 全 总 个 体 域 课 件 7 谓 词谓 词 : 表 示 个 体 词 性 质 或 相 互 之 间 关 系 的 词 谓 词 常 项 : 表 示 具 体 性 质 或 相 互 之 间 关 系 的 谓 词 谓 词 变 项 : 表 示 抽 象 性 质 或 相 互 之 间 关 系 的 谓 词 谓 词 用 F,G,H,P等 表 示 n元 谓 词 P(x1, x2, xn): 含 n个 命 题 变 项 的 谓 词 , 是 定 义 在个 体 域 上 , 值 域 为 0,1的 n元 函 数 一 元 谓 词 : 表 示 事 物 的 性 质 多 元 谓 词 (n2): 表 示 事

5、 物 之 间 的 关 系 0元 谓 词 : 不 含 个 体 变 项 的 谓 词 ,即 命 题 常 项 或 命 题 变 项 课 件 8 实 例例 1 (1) 4是 偶 数 4是 个 体 常 项 , “ 是 偶 数 ” 是 谓 词 常 项 , 符 号 化 为 : F(4) (2) 小 王 和 小 李 同 岁 小 王 , 小 李 是 个 体 常 项 , 同 岁 是 谓 词 常 项 . 记 a:小 王 , b: 小 李 , G(x,y): x与 y同 岁 , 符 号 化 为 : G(a,b)(3) x y x,y是 命 题 变 项 , 3， 则 3y, G(x,y): x10, G(x): x0 真

6、命 题 课 件 21 解 释定 义 3.7 设 一 阶 语 言 L 的 个 体 常 项 集 ai| i1, 函 数 符 号 集fi| i1, 谓 词 符 号 集 Fi| i1, L 的 解 释 I由 下 面 4部 分 组 成 :(1) 非 空 个 体 域 DI(2) 对 每 一 个 个 体 常 项 ai, DI, 称 作 ai在 I中 的 解 释(3) 对 每 一 个 函 数 符 号 fi, 设 其 为 m元 的 , 是 DI上 的 m元 函数 , 称 作 fi在 I中 的 解 释(4) 对 每 一 个 谓 词 符 号 F i, 设 其 为 n元 的 , 是 一 个 n元 谓 词 , 称 作

7、Fi在 I中 的 解 释 ia ifiF 课 件 22 实 例例 8 给 定 解 释 I 如 下 : (a) 个 体 域 D=N (b) (c) (d) 谓 词说 明 下 列 公 式 在 I 下 的 含 义 , 并 讨 论 其 真 值 (1) xF(g(x,a),x)2a xyyxgyxyxf ),(,),( yxyxF :),( x(2x=x) 假 命 题(2) xy(F(f(x,a),y)F(f(y,a),x)xy(x+2=yy+2=x) 假 命 题 课 件 23 实 例 (续 )(3) xyzF(f(x,y),z)(5) F(f(x,a), g(x,a)(4) xF(f(x,x),g(x

8、,x)x(2x=x2) 真 命 题xyz (x+y=z) 真 命 题(6) x (F(x,y)F(f(x,a), f(y,a)x (x=yx+2=y+2) 真 命 题x+2=2x 不 是 命 题 课 件 24 闭 式 的 性 质定 理 3.1 闭 式 在 任 何 解 释 下 都 变 成 命 题 .例 8 (1)(4)都 是 闭 式 , 在 I下 全 是 命 题 .(5)和 (6)不 是 闭 式 , 在 I下 (5)不 是 命 题 , (6)是 命 题 课 件 25 一 阶 逻 辑 公 式 的 分 类永 真 式 (逻 辑 有 效 式 ): 无 成 假 解 释矛 盾 式 (永 假 式 ): 无 成

9、 真 解 释可 满 足 式 : 至 少 有 一 个 成 真 解 释在 一 阶 逻 辑 中 , 公 式 的 可 满 足 性 (永 真 性 ,永 假 性 )是 不 可判 定 的 ,即 不 存 在 算 法 能 在 有 限 步 内 判 断 任 给 的 公 式 是 否是 可 满 足 式 (永 真 式 ,矛 盾 式 ) 课 件 26 代 换 实 例定 义 3.9 设 A0是 含 命 题 变 项 p1, p2, ,pn的 命 题 公 式 , A1,A2, An是 n个 谓 词 公 式 , 用 Ai处 处 代 替 A0中 的 pi(1in), 所 得 公 式A称 为 A0的 代 换 实 例 .例 如 F(x)

10、G(x), xF(x)yG(y) 等 都 是 pq的 代 换 实 例 定 理 3.2 重 言 式 的 代 换 实 例 都 是 永 真 式 ， 矛 盾 式 的 代 换 实例 都 是 矛 盾 式 . 课 件 27 实 例例 9 判 断 下 列 公 式 的 类 型 :(1) x(F(x)G(x)非 永 真 式 的 可 满 足 式(2) (xF(x)(xF(x) 这 是 pp 的 代 换 实 例 , pp是 重 言 式 , 取 解 释 I1, D1=R, :x是 整 数 , :x是 有 理 数 , 真 命 题)(xF )(xG 永 真 式(3) (xF(x)yG(y) yG(y)这 是 (pq)q的

11、代 换 实 例 , (pq)q是 矛 盾 式 矛 盾 式取 解 释 I2, D2=R, :x是 整 数 , :x是 自 然 数 , 假 命 题)(xF )(xG 课 件 28 3.2 一 阶 逻 辑 等 值 演 算 3.2.1 一 阶 逻 辑 等 值 式 与 置 换 规 则 基 本 等 值 式 置 换 规 则 、 换 名 规 则 、 代 替 规 则 3.2.2 一 阶 逻 辑 前 束 范 式 课 件 29 等 值 式定 义 3.10 若 AB是 永 真 式 , 则 称 A与 B是 等 值 的 , 记 作 AB, 并 称 AB为 等 值 式基 本 等 值 式命 题 逻 辑 中 基 本 等 值 式

12、 的 代 换 实 例如 ， xF(x)yG(y) xF(x)yG(y) (xF(x)yG(y) xF(x)yG(y) 等 消 去 量 词 等 值 式 设 D=a 1,a2,an xA(x)A(a1)A(a2)A(an) xA(x)A(a1)A(a2)A(an) 课 件 30 基 本 等 值 式 (续 )量 词 辖 域 收 缩 与 扩 张 等 值 式 设 A(x)是 含 x自 由 出 现 的 公 式 ， B中 不 含 x的 出 现关 于 全 称 量 词 的 ： x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x)BxA(x) 关 于 存 在 量

13、 词 的 : x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(A(x)B)xA(x)B x(BA(x)BxA(x) 课 件 31 基 本 等 值 式 (续 )量 词 否 定 等 值 式设 A(x)是 含 x自 由 出 现 的 公 式 xA(x) x A(x) xA(x)x A(x)量 词 分 配 等 值 式 x(A(x)B(x)xA(x)xB(x) x(A(x)B(x)xA(x)xB(x)注 意 ： 对 无 分 配 律 ， 对 无 分 配 律 课 件 32 置 换 规 则 、 换 名 规 则 、 代 替 规 则置 换 规 则 设 (A)是 含 公 式 A的 公 式 , (B)是

14、 用 公 式 B取代 (A)中 的 所 有 A得 到 的 公 式 , 则 (A)(B)换 名 规 则 将 公 式 A中 某 量 词 的 指 导 变 元 及 其 在 辖 域 内 的所 有 约 束 出 现 改 成 该 量 词 辖 域 内 未 曾 出 现 的 某 个 个 体 变项 , 其 余 部 分 不 变 , 记 所 得 公 式 为 A, 则 AA 代 替 规 则 将 公 式 A中 某 个 自 由 出 现 的 个 体 变 项 的 所 有 自由 出 现 改 成 A中 未 曾 出 现 的 某 个 个 体 变 项 , 其 余 部 分 不 变 , 记 所 得 公 式 为 A, 则 AA 课 件 33 实

15、例例 1 消 去 公 式 中 既 约 束 出 现 、 又 自 由 出 现 的 个 体 变 项(1) xF(x,y,z) yG(x,y,z) uF(u,y,z) yG(x,y,z) 换 名 规 则 uF(u,y,z) vG(x,v,z) 换 名 规 则或 者 xF(x,u,z) yG(x,y,z) 代 替 规 则 xF(x,u,z) yG(v,y,z) 代 替 规 则(2) x(F(x,y) yG(x,y,z) x(F(x,y) tG(x,t,z) 换 名 规 则或 者 x(F(x,t) yG(x,y,z) 代 替 规 则 课 件 34 实 例例 2 设 个 体 域 D=a,b,c, 消 去 下

16、 面 公 式 中 的 量 词 :(1) x(F(x)G(x) (F(a)G(a)(F(b)G(b)(F(c)G(c)(2) x(F(x)yG(y) xF(x)yG(y) 量 词 辖 域 收 缩(F(a)F(b)F(c)(G(a)G(b)G(c) x(F(x,a)F(x,b)F(x,c)(3) xyF(x,y) (F(a,a)F(a,b)F(a,c)(F(b,a)F(b,b)F(b,c) (F(c,a)F(c,b)F(c,c) 课 件 35 实 例解 (F(f(2)G(2, f(2)(F(f(3)G(3, f(3)例 3 给 定 解 释 I: (a) D=2,3, (b) (c) :x是 奇 数

17、 , : x=2 y=2, : x=y.在 I下 求 下 列 各 式 的 真 值 :(1) x(F(f(x)G(x, f(x) ,2)3(,3)2(: fff),( yxG ),( yxL)(xF(2) xyL(x,y) (11)(01) 1解 yL(2,y)yL(3,y) (L(2,2)L(2,3)(L(3,2)L(3,3) (10)(01) 0 课 件 36 实 例例 4 证 明 下 列 等 值 式 : x(M(x)F(x) x(M(x) F(x)证 左 边 x (M(x)F(x) 量 词 否 定 等 值 式 x(M(x)F(x) x(M(x) F(x) 课 件 37 前 束 范 式定 义

18、 3.11 设 A为 一 个 一 阶 逻 辑 公 式 , 若 A具 有 如 下 形 式 Q1x1Q2x2Qkxk B则 称 A为 前 束 范 式 , 其 中 Qi 为 或 , 1ik, B为 不 含 量 词 的公 式 .例 如 xy(F(x)(G(y)H(x,y) x(F(x)G(x)是 前 束 范 式 x(F(x)y(G(y)H(x,y) x(F(x)G(x)不 是 前 束 范 式 课 件 38 公 式 的 前 束 范 式定 理 3.3(前 束 范 式 存 在 定 理 ) 一 阶 逻 辑 中 的 任 何 公 式 都 存在 与 之 等 值 的 前 束 范 式例 5 求 公 式 的 前 束 范 式(1) xF(x)xG(x)解 xF(x)xG(x) 量 词 否 定 等 值 式 x(F(x)G(x) 量 词 分 配 等 值 式解 2 xF(x)yG(y) 换 名 规 则 xF(x)yG(y) 量 词 否 定 等 值 式 x(F(x)yG(y) 量 词 辖 域 扩 张 xy(F(x)G(y) 量 词 辖 域 扩 张