《离散数学 第三章 一阶逻辑》由会员分享，可在线阅读，更多相关《离散数学 第三章 一阶逻辑（70页珍藏版）》请在金锄头文库上搜索。
1、第三章 一阶逻辑1一阶逻辑基本概念 一阶逻辑命题符号化 一阶逻辑公式、解释2谓词逻辑（一阶逻辑）的引入n著名的三段论论证：所有的人都将死去。苏格拉底是人。所以：苏格拉底将死去。n从人们的实践经验可知，这是一个有效的推 论。n但在命题逻辑中却无法判断它的正确性。n因为在命题逻辑中只能将推理中的三个简单 命题符号化为p, q, r，那么由p, q这两个命题 无论如何不可能得出r为有效结论。 33.1 一阶逻辑基本概念 个体词 谓词 量词 一阶逻辑中命题符号化 一阶逻辑公式与分类4基本概念个体词、谓词、量词 个体词（个体）: 所研究对象中可以独立存在的具 体或抽象的客体个体常项：具体的事务，用a,
2、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元谓词: 不含个体变项的谓词, 即命题常项
3、或 命 题变项 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中一些特定元
4、素的集合(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
5、下的涵义,并讨论真值 (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 注意不是闭式的公式在某些解
6、释下也可能是命题.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
7、个谓词公式，用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)383.2一阶逻辑等值演算等值式 基本等值式 量词否定等值式 量词辖域收缩与扩张等值式 量词分配等值式39等值式与基本等值式 在一阶逻辑中，有些命题可以有不同的符号化形式。例如：
8、没有不呼吸的人。取全总个体域时有下面两种不同的符号化形式：(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)
9、 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
10、(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) 043基本的等值式(续)量词否定等值式 设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)Bx(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx(BA(x)BxA(x) 关于存在量词的:x(A(x)B)xA(x)Bx(A(x)B)xA(x)Bx
11、(A(x)B)xA(x)Bx(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)(
12、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
13、) D 中特定函数f(x)为 ： f(2)=3， f(3)=2(d) D 中特定谓词G(x,y)为 ：G(2,2)=G(2,3)= G(3,2)=1G(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)不是前束范式，
14、定义 设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) （量词分配等值式 ） 另有一种形
