离散数学第三章一阶逻辑.ppt

第三章 一阶逻辑 1 一阶逻辑基本概念 一阶逻辑命题符号化 一阶逻辑公式、解释 2 谓词逻辑（一阶逻辑）的引入 n著名的三段论论证： 所有的人都将死去。 苏格拉底是人。 所以：苏格拉底将死去。 n从人们的实践经验可知，这是一个有效的推 论。 n但在命题逻辑中却无法判断它的正确性。 n因为在命题逻辑中只能将推理中的三个简单 命题符号化为p, q, r，那么由p, q这两个命题 无论如何不可能得出r为有效结论。 3 3.1 一阶逻辑基本概念 个体词 谓词 量词 一阶逻辑中命题符号化 一阶逻辑公式与分类 4 基本概念个体词、谓词、量词 个体词（个体）: 所研究对象中可以独立存在的具 体或抽象的客体 个体常项：具体的事务，用a, b, c表示 个体变项：抽象的事物，用x, y, z表示 个体域（论域）: 个体变项的取值范围 有限个体域，如a, b, c, 1, 2 无限个体域，如N, Z, R, 全总个体域: 宇宙间一切事物组成 如果事先没有给出个体域，都应以全总个体域 为个体域。 5 基本概念 (续) 谓词: 刻划个体词性质或相互之间关系的词 谓词常项：表示具体性质和关系的谓词， 用 F, G, H表示； 谓词变项：表示抽象或泛指的谓词， 也用F, G, H表示； 一元谓词: 表示事物的性质 多元谓词(n元谓词, n2): 表示事物之间的关系 如 L(x,y)：x与y有关系L，L(x,y)：xy， 0元谓词: 不含个体变项的谓词, 即命题常项或 命 题变项 6 实例 (1) 4是偶数 4是个体常项, “是偶数”是谓词常项, 符号化为: F(4) (2) 小王和小李同岁 小王, 小李是个体常项, 同岁是谓词常项. 记a:小王, b: 小李, G(x,y): x与y同岁, 符号化为: G(a,b) (3) x3，则3y，G(x,y)：x2, G(x): x1 代入得A=x(x2x1) 真命题 成假解释: 个体域N, F(x): x1, G(x): x2 代入得A=x(x1x2) 假命题 问: xF(x)xF(x) 有成真解释吗？ xF(x)xF(x) 有成假解释吗？ 29 解释 定义 解释I由下面4部分组成： (a) 非空个体域DI (b) DI中一些特定元素的集合 (c) DI上特定函数集合 (d) DI上特定谓词的集合 说明： 在解释的定义中引进了元语言符号, 如 等 被解释的公式A中的个体变项均取值于DI 若A中含个体常项ai，就解释成 30 解释 (续) 为第 i 个n元谓词. 例如， 表示第 2 个 3元 谓词，它可能以 形式出现在解释中， 公式A中若出现F2(x,y,z) 就解释成 为第 i 个n元函数. 例如， 表示第一个二元 函数, 它出现在解释中，可能是 =2xy等，一旦公式中出现f1(x,y) 就解释成 ,出现 g1(x,y) 就解释成 31 解释(续) 例4 给定解释I 如下: (a) 个体域 D=N (b) (c) (d) 谓词 说明下列公式在 I 下的涵义,并讨论真值 (1) xF(g(x,a),x) x(2x=x) 假命题 (2) xy(F(f(x,a),y)F(f(y,a),x) xy(x+2=yy+2=x) 假命题 32 例1(续) (3) xyzF(f(x,y),z) 两点说明: 5个小题都是闭式,在I下全是命题 (3)与(5)说明，量词顺序不能随意改变 (5) xyzF(f(y,z),x) xyz (y+z=x) 假命题 (4) xF(f(x,x),g(x,x) x(2x=x2) 真命题 xyz (x+y=z) 真命题 33 解释 (续) n 被解释的公式不一定全部包含解释中的4部分 . n 闭式在任何解释下都是命题， n 注意不是闭式的公式在某些解释下也可能是 命题. 34 公式的分类 永真式（逻辑有效式）：无成假赋值 矛盾式（永假式）：无成真赋值 可满足式：至少有一个成真赋值 几点说明： 永真式为可满足式，但反之不真 判断公式是否为可满足式不是易事(不同于命题逻辑 ) 某些特殊公式可以判断类型 35 代换实例(续) 例5 证明下面公式既不是永真式，也不是矛盾 式 (1) x(F(x) G(x) (2) x(F(x)G(x) (3) xy(F(x)G(y)H(x,y) 不难对每一个公式给出一个成假解释和一个成 真 解释, 从而证明它们既不是永真式，也不是矛 盾 式. 36 代换实例 定义 设A0是含命题变项p1, p2, ,pn的命题公式， A1,A2,An是n个谓词公式，用Ai处处代替A0中 的pi (1in) ，所得公式A称为A0的代换实例. 例如: F(x)G(x), xF(x)yG(y) 等都是pq的换实例 ， x(F(x)G(x) 等不是 pq 的代换实例. 定理 重言式的代换实例都是永真式，矛盾式的 代 换实例都是矛盾式. 37 代换实例(续) 例6 判断下面公式类型 (1) xF(x) (x y G(x,y) xF(x) (2) (x y G(x,y) xF(x) xF(x) 38 3.2一阶逻辑等值演算 等值式 基本等值式 量词否定等值式 量词辖域收缩与扩张等值式 量词分配等值式 39 等值式与基本等值式 在一阶逻辑中，有些命题可以有不同的符号化 形式。 例如：没有不呼吸的人。 取全总个体域时有下面两种不同的符号化形式： (1) x (F(x) G(x) (2) x (F(x)G(x) F(x)：x是人， G(x)： x要呼吸 40 等值式与基本等值式 基本等值式: 命题逻辑中16组基本等值式的代换实例 如，xF(x)yG(y) xF(x)yG(y) (xF(x)yG(y) xF(x)yG(y) 等 消去量词等值式 设D=a1,a2,an xA(x)A(a1)A(a2)A(an) xA(x)A(a1)A(a2)A(an) 定义 若AB为逻辑有效式，则称A与B是等值的， 记作 AB，并称AB为等值式. 41 实例 例 设个体域D=a,b,c, 消去下面公式中的量词: (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) 42 实例 解 (F(f(2)G(2, f(2)(F(f(3)G(3, f(3) 例给定解释I: (a) D=2,3, (b) (c) :x是奇数, : x=2 y=2, : x=y. 在I下求下列各式的真值: (1) x(F(f(x)G(x, f(x) (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 43 基本的等值式(续) 量词否定等值式 设A(x)是含x自由出现的公式 xA(x) x A(x) xA(x) x A(x) 44 基本等值式(续) 量词辖域收缩与扩张等值式 设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) 关于存在量词的: 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) 45 基本的等值式(续) 量词分配等值式 x(A(x)B(x)xA(x)xB(x) x(A(x)B(x)xA(x)xB(x) 注意：对无分配律，对无分配律 46 基本的等值式(续) 例 将下面命题用两种形式符号化 (1) 没有不犯错误的人 (2) 不是所有的人都爱看电影 解 (1) 令F(x)：x是人，G(x)：x犯错误. x(F(x)G(x) x(F(x)G(x) 请给出演算过程，并说明理由. (2) 令F(x)：x是人，G(x)：爱看电影. x(F(x)G(x) x(F(x)G(x) 给出演算过程，并说明理由. 47 等值演算的三条原则 置换规则：若AB, 则(B)(A) 换名规则: 将量词辖域中出现的某个约束变项的所有 出现及对应的指导变项，改成该量词辖域中未曾出 现过的个体变项符号，公式中其余部分不变，则所 得公式与原来的公式等值. 代替规则: 对某自由出现的个体变项用与原公式中所 有个体变项符号不同的符号去代替，则所得公式与 原来的公式等值. 48 换名规则与代替规则 例 (1) xF(x)y(G(x,y)H(y) zF(z)y(G(x,y)H(y) （换名规则 ） (2) x(F(x,y)y(G(x,y)H(x,z) x(F(x,u)y(G(x,y)H(x,z) ( 代替规 则 ) 49 例 给定解释I如下： (a) 个体域D=2,3 (b) D 中特定元素a=2 (c) D 中特定函数f(x)为 ： f(2)=3， f(3)=2 (d) D 中特定谓词G(x,y)为 ：G(2,2)=G(2,3)= G(3,2)=1 G(3,3)=0. L(2,2)=L(3,3)=1, L(2,3)=L(3,2)=0. F(x) 为： F(2)=0， F(3)=1。在I下求下列各式的 值 (1) x(F(x)G(x,a) ) (2) x(F(f(x)G(x, f(x) (3) x yL(x,y) (4) yxL(x,y) 50 前束范式 例如，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) 不是前束范式， 定义 设A为一个一阶逻辑公式, 若A具有如下形式 Q1x1Q2x2QkxkB, 则称A为前束范式, 其中Qi (1ik) 为或，B为不含量词的公式. 51 公式的前束范式 定理（前束范式存在定理）一阶逻辑中的任何公 式都存在与之等值的前束范式 注意: 公式的前束范式不惟一 求公式的前束范式的方法: 利用重要等值式、 置换规则、换名规则、代替规则进行等值演算. 52 公式的前束范式(续) 例 求下列公式的前束范式 (1) x(M(x)F(x) 解 x(M(x)F(x) x(M(x)F(x) （量词否定等值式 ） x(M(x)F(x) 两步结果都是前束范式，说明前束范式不惟 一. 53 例(续) (2) xF(x)xG(x) 解 xF(x)xG(x) xF(x)xG(x) （量词否定等值式 ） x(F(x)G(x) （量词分配等值式 ） 另有一种形式 xF(x)xG(x) xF(x)xG(x) （量词否定等值式 ） xF(x)yG(y) ( 换名规则 ) xy(F(x)G(y) ( 量词辖域扩张 ) 两种形式是等值的 54 例(续) (3) xF(x)xG(x) 解 xF(x)xG(x) xF(x)xG(x) （量词否定等值式 ） x(F(x)G(x) （为什么？） (4) xF(x)y(G(x,y)H(y) 解 xF(x)y(G(x,y)H(y) zF(z)y(G(x,y)H(y) （换名规则 ） zy(F(z)(G(x,y)H(y) （为什么？ ） 55 例(续) 或 xF(x)y(G(z,y)H(y) （代替规则 ） xy(F(x)(G(z,y)H(y) (5) x(F(x,y)y(G(x,y)H(x,z) 解 用换名规则, 也可用代替规则, 这里用代替规 则 x(F(x,y)y(G(x,y)H(x,z) x(F(x,u)y(G(x,y)H(x,z) xy(F(x,u)G(x,y)H(x,z) 注意：x与y不能颠倒 56 一阶逻辑推理理论 推理的形式结构 判断推理是否正确的方法 重要的推理定律 推理规则 构造证明 附加前提证明法 57 推理 推理的形式结构有两种： 第一种 A1A2AkB (*) 第二种 前提：A1，A2，Ak 结论： B 其中 A1,A2,Ak,B为一阶逻辑公式. 若(*)为永真式, 则称推理正确, 否则称推理 不正确. 58 重要的推理定律 第一组 命题逻辑推理定律代换实例 如 xF(x)yG(y)xF(x)为化简律代换实例. 第二组 由基本等值式生成 如 由 xA(x)xA(x) 生成 xA(x)xA(x), xA(x)xA(x), 第三组 xA(x)xB(x)x(A(x)B(x) x(A(x)B(x)xA(x)xB(x) 59 推理规则 (1)前提引入规则 (2)结论引入规则 (3)置换规则 (4)假言推理规则 (5)附加规则 (6)化简规则 (7)拒取式规则 (8)假言三段论规则 (9)析取三段论规则 (10)构造性二难推理规 则 (11)合取引入规则 60 推理规则(续) (12) 全称量词消去规则（简记为UI规则或UI） 两式成立的条件是： 在第一式中，取代x的y应为任意的不在A(x)中 约束出现的个体变项. 在第二式中，c为任意个体常项. 用y或c去取代A(x)中的自由出现的x时，一定 要 在x自由出现的一切地方进行取代.61 推理规则(续) (13) 全称量词引入规则（简记为UG规则或UG ） 该式成立的条件是： 无论A(y)中自由出现的个体变项y取何值， A(y) 应该均为真. 取代自由出现的y的x，也不能在A(y)中约束 出 现. 62 推理规则(续) (14) 存在量词引入规则（简记为EG规则或EG ） 该式成立的条件是： c是使A为真的特定个体常项. 取代c的x不能在A(c)中出现过. 63 推理规则(续) (15) 存在量词消去规则（简记为EI规则或EI） 该式成立的条件是： c是使A为真的特定的个体常项. c不在A(x)中出现. 若A(x)中除自由出现的x外，还有其他自由出 现 的个体变项，此规则不能使用. 64 构造推理证明 例1 证明苏格拉底三段论: “人都是要死的, 苏格 拉 底是人，所以苏格拉底是要死的.” 令 F(x): x是人, G(x): x是要死的, a: 苏格拉底 前提：x(F(x)G(x)，F(a) 结论：G(a) 证明： F(a) 前提引入 x(F(x)G(x) 前提引入 F(a)G(a) UI G(a) 假言推理 注意：使用UI时，用a取代x . 65 构造推理证明(续) 例2 乌鸦都不是白色的. 北京鸭是白色的. 因此