第五章一阶逻辑等值演算与推理.ppt
《第五章一阶逻辑等值演算与推理.ppt》由会员分享,可在线阅读,更多相关《第五章一阶逻辑等值演算与推理.ppt(60页珍藏版)》请在三一文库上搜索。
1、第五章 一阶逻辑等值演算与推理 离 散 数 学 厦门理工学院 本章说明 q 本章的主要内容 一阶逻辑等值式与基本等值式 置换规则、换名规则、代替规则 前束范式 一阶逻辑推理理论 q 本章与其他各章的关系 本章先行基础是前四章 本章是集合论各章的先行基础 本章主要内容 5.1 一阶逻辑等值式与置换规则 5.2 一阶逻辑前束范式 5.3 一阶逻辑的推理理论 5.1 一阶逻辑等值式与置换规则 q 在一阶逻辑中,有些命题可以有不同的符号化形式。 q 例如:没有不犯错误的人 令 M(x):x是人。 F(x):x犯错误。 则将上述命题的符号化有以下两种正确形式: (1) x(M(x)F(x) (2) x(
2、M(x)F(x) q我们称(1)和(2)是等值的。 说 明 等值式的定义 定义5.1 设A,B是一阶逻辑中任意两个公式,若 AB是永 真式,则称A与B是等值的。(这里A,B是谓词公式) 记做AB,称 AB 是等值式。 例如: q 判断公式A与B是否等值,等价于判断公式 AB是否为永真式。 q 谓词逻辑中关于联结词的等值式与命题逻 辑中相关等值式类似。 说 明 一阶逻辑中的一些基本而重要等值式 q 代换实例 q 消去量词等值式 q 量词否定等值式 q 量词辖域收缩与扩张等值式 q 量词分配等值式 代换实例 q 由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永 真式,因而第二章的16组等值式(P
3、17)模式给出的代换 实例都是一阶逻辑的等值式的模式。 q 例如: (1)xF(x) xF(x)(双重否定律) (2)F(x)G(y) F(x)G(y) (蕴涵等值式) (3)x(F(x)G(y) zH(z) (x(F(x)G(y)zH(z) (蕴涵等值式) 消去量词等值式 设个体域为有限集D=a1,a2,an,则有 (1)xA(x) A(a1)A(a2)A(an) (2)xA(x) A(a1)A(a2)A(an) (5.1) 量词否定等值式 设A(x)是任意的含自由出现个体变项x的公式,则 (1)xA(x) xA(x) (2)xA(x) xA(x) 说明 q “并不是所有的x都有性质A”与“
4、存在x没有 性质A”是一回事。 q ”不存在有性质A的x”与”所有X都没有性质 A”是一回事。 (5.2) 量词辖域收缩与扩张等值式 设A(x)是任意的含自由出现个体变项x的公式,B中不含x 的出现,则 (1) 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) (2) 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) (5.3) (5.4) 证明: xA(x)B x(A(x)B) xA(x)B xA(x)B xA(x)B x(A(x) B) x
5、(A(x)B) 量词分配等值式 设A(x),B(x)是任意的含自由出现个体变项x的公式,则 (1)x(A(x)B(x) xA(x)xB(x) (2)x(A(x)B(x) xA(x) xB(x) (5.5) q 例如,“联欢会上所有人既唱歌又跳舞”和“联欢会上所 有人唱歌且所有人跳舞” ,这两个语句意义相同。故有 (1)式。 q 由(1)式推导(2)式 x(A(x)B(x) xA(x)xB(x) x(A(x)B(x) xA(x)xB(x) x(A(x)B(x) (xA(x)xB(x) x(A(x)B(x) xA(x) xB(x) 一阶逻辑等值演算的三条原则 q 置换规则:设(A)是含公式A的公式
6、,(B)是用公式B取 代(A)中所有的A之后的公式,若AB,则(A)(B) 。 q 换名规则:设A为一公式,将A中某量词辖域中某约束变项 的所有出现及相应的指导变元改成该量词辖域中未曾出现 过的某个体变项符号,公式的其余部分不变,设所得公式 为A,则AA。 q 代替规则:设A为一公式,将A中某个自由出现的个体变项 的所有出现用A中未曾出现过的个体变项符号代替,A中其 余部分不变,设所得公式为A,则AA。 说明 q 一阶逻辑中的置换规则与命题逻辑中的置换 规则形式上完全相同,只是在这里A,B是一 阶逻辑公式。 例5.1 例5.1 将下面公式化成与之等值的公式,使其没有既是约束 出现又是自由出现的
7、个体变项。 (1)xF(x,y,z)yG(x,y,z) (2)x(F(x,y) yG(x,y,z) (1)xF(x,y,z) yG(x,y,z) tF(t,y,z)yG(x,y,z)(换名规则) tF(t,y,z)wG(x,w,z)(换名规则) 或xF(x,y,z)yG(x,y,z) xF(x,t,z)yG(x,y,z)(代替规则) xF(x,t,z)yG(w,y,z)(代替规则) 解答 例5.1的解答 (2)x(F(x,y)yG(x,y,z) x(F(x,t)yG(x,y,z)(代替规则) 或x(F(x,y)yG(x,y,z) x(F(x,y)tG(x,t,z)(换名规则) 解答 例5.2
8、例5.2 证明 (1) x(A(x)B(x) xA(x)xB(x) (2) x(A(x)B(x) xA(x)xB(x) 其中A(x),B(x)为含x自由出现的公式。 只要证明在某个解释下两边的式子不等值。 取解释I:个体域为自然数集合N; (1)取F(x):x是奇数,代替A(x); 取G(x):x是偶数,代替B(x)。 则x(F(x)G(x)为真命题, 而xF(x) xG(x)为假命题。 两边不等值。 证明 例5.2 (2)x(A(x)B(x) xA(x)xB(x) x(F(x)G(x):有些x既是奇数又是偶数为假命题; 而xF(x)xG(x):有些x是奇数并且有些x是偶数为真 命题。 两边不
9、等值。 证明 说明 q 全称量词“”对“”无分配律。 q 存在量词“”对“”无分配律。 q 当B(x)换成没有x出现的B时,则有 x(A(x)B) xA(x)B x(A(x)B) xA(x)B 例5.3消去量词 例5.3 设个体域为Da,b,c,将下面各公式的量词消去: (1) x(F(x)G(x) (2) x(F(x) yG(y) (方法) (3) xyF(x,y) 说明 q 如果不用公式(5.3)将量词的辖域缩小,演算过程较 长。注意,此时yG(y)是与x无关的公式B。 解答(1)x(F(x)G(x) (F(a)G(a) (F(b)G(b) (F(c)G(c) (2)x(F(x) yG(y
10、) xF(x)yG(y) (公式5.3) (F(a)F(b)F(c)(G(a)G(b)G(c) 例5.3消去量词 (3) xyF(x,y) x(F(x,a)F(x,b)F(x,c) (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) 在演算中先消去存在量词也可以,得到结果是等值的。 xyF(x,y) yF(a,y) yF(b,y) yF(c,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) 例5.4 在解释I下求下列各式的值: (1)x(F(x)G(x
11、,a) (2)x(F(f(x)G(x,f(x) (3)xyL(x,y) (4)yxL(x,y) 例5.4 给定解释I如下: (a)个体域 D2,3 (b)D中特定元素: (c)D上的特定函数(x)为: (d)D的特定谓词 例5.4的解答 (1) x(F(x)G(x,a) (F(2)G(2,2) (F(3)G(3,2) (01) (11) 0 (2) x(F(f(x)G(x,f(x) (F(f(2)G(2,f(2) (F(f(3)G(3,f(3) (F(3)G(2,3) (F(2)G(3,2) (11) (01) 1 例5.4的解答 (3) xyL(x,y) (L(2,2)L(2,3) (L(3
12、,2)L(3,3) (10) (01) 1 (4) yxL(x,y) y(L(2,y)L(3,y) (L(2,2)L(3,2) (L(2,3)L(3,3) (10) (01) 0 说明 q 由(3),(4)的结果进一步可以说明量词的次 序不能随意颠倒。 例5.5 例5.5 证明下列等值式。 (1)x(M(x)F(x) x(M(x)F(x) (2)x(F(x)G(x) x(F(x)G(x) (3)xy(F(x)G(y)H(x,y) xy(F(x)G(y)H(x,y) (4)xy(F(x)G(y)L(x,y) xy(F(x)G(y)L(x,y) 例5.5的证明 (1) x(M(x)F(x) x(M
13、(x)F(x) x(M(x)F(x) x(M(x)F(x) x(M(x)F(x) x(M(x)F(x) (2) x(F(x)G(x) x(F(x)G(x) x(F(x)G(x) x(F(x)G(x) x(F(x)G(x) x(F(x)G(x) 例5.5的证明 (3) xy(F(x)G(y)H(x,y) xy(F(x)G(y)H(x,y) xy(F(x)G(y)H(x,y) x(y(F(x)G(y)H(x,y) xy(F(x)G(y)H(x,y) xy(F(x)G(y)H(x,y) 例5.5的证明 (4) xy(F(x)G(y)L(x,y) xy(F(x)G(y)L(x,y) xy(F(x)G(
14、y)L(x,y) x (y(F(x)G(y)L(x,y) xy(F(x)G(y)L(x,y) xy(F(x)G(y)L(x,y) xy(F(x)G(y)L(x,y) 5.2 一阶逻辑前束范式 定义5.2 设A为一个一阶逻辑公式,若A具有如下形式 Q1x1Q2x2 QkxkB 则称A为前束范式,其中Qi(1ik)为或,B为不含量 词的公式。 q 前束范式的例子: xy(F(x)G(y)H(x,y) xyz(F(x)G(y)H(z)L(x,y,z) q 不是前束范式的例子: x(F(x)y(G(y)H(x,y) x(F(x)y(G(y)H(x,y) 前束范式存在定理 定理5.1 一阶逻辑中的任何公
15、式都存在与之等值的前束范式。 说明 q 求前束范式的过程,就是制造量词辖域可以扩大的 条件,进行量词辖域扩大。 q 任何公式的前束范式都是存在的,但一般说来,并 不唯一。 q 利用一阶逻辑等值式以及三条变换规则(置换规则 、换名规则(约束出现)、代替规则(自由出现) )就可以求出与公式等值的前束范式,或所谓公式 的前束范式。 (1)利用量词转化公式,把否定深入到指导变元的后面。 xA(x) xA(x) xA(x) xA(x) (2)利用xA(x)B x(A(x)B)和xA(x)Bx(A(x)B) 把量词移到全式的最前面,这样便得到前束范式。 例5.6 求公式的前束范式 (1) xF(x)xG(
16、x) xF(x)yG(y) (换名规则) xF(x)yG(y) (5.2)第二式) x(F(x)yG(y) (5.3)第二式) xy(F(x)G(y) (5.3)第二式) ( yx(F(x)G(y) ) 或者 xF(x)xG(x) xF(x)xG(x) (5.2)第二式) x(F(x)G(x) (5.5)第一式) 例5.6 求公式的前束范式 (2) xF(x)xG(x) xF(x)xG(x) (5.2)第二式) xF(x)yG(y) (换名规则) x(F(x)yG(y) (5.3)第一式) xy(F(x)G(y) (5.3)第一式) 说明 q 有(1)可知公式的前束范式是不唯一的。 例5.7
17、求前束范式 (1)xF(x) xG(x) yF(y) xG(x) yx(F(y)G(x) (2) xF(x) xG(x) yF(y) xG(x) yx(F(y)G(x) (3) xF(x) xG(x) yF(y) xG(x) yx(F(y)G(x) (4) xF(x) yG(y) xy(F(x)G(y) 例5.8 求公式的前束范式 (1)xF(x,y)yG(x,y) tF(t,y)wG(x,w) (换名规则) tw(F(t,y)G(x,w) (5.3),(5.4) 或者 xF(x,y)yG(x,y) xF(x,t)yG(w,y) (代替规则) xy(F(x,t)G(w,y) (5.3),(5.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第五 一阶 逻辑 等值 演算 推理
链接地址:https://www.31doc.com/p-2560904.html