一阶逻辑等值演算与推理课件(离散数学)

1、第五章 一阶逻辑等值演算与推理1本章主要内容本章主要内容5.1一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则5.2一阶逻辑前束范式一阶逻辑前束范式5.3一阶逻辑的推理理论一阶逻辑的推理理论25.1一阶逻辑等值式与置换规则一阶逻辑等值式与置换规则n等值式的概念等值式的概念n基本等值式基本等值式n等值演算与置换规则等值演算与置换规则3所有的学生都上课了，这是错的。所有的学生都上课了，这是错的。 令令 F(x): x是学生是学生, G(x): x上课了。上课了。 )()(x xG Gx xF Fx x 这句话相当于这句话相当于“有些学生没有上课有些学生没有上课”。 )()(x xG Gx xF F

2、x x 4一、等值式的概念一、等值式的概念 定义：定义：若若AB为永真式，则称为永真式，则称A与与B是等是等值的，记作值的，记作 AB，并称，并称AB为等值式。为等值式。其中其中A、B是一阶逻辑中任意的两个合式公是一阶逻辑中任意的两个合式公式。式。5二、基本等值式二、基本等值式n命题逻辑中命题逻辑中1616组基本等值式的代换实例组基本等值式的代换实例例：例： xF(x)yG(y) xF(x)yG(y) ( xF(x)yG(y) xF(x)yG(y) 即命题逻辑中的基本等值式在谓词逻即命题逻辑中的基本等值式在谓词逻辑中均适用。辑中均适用。6二、基本等值式二、基本等值式n有限个体域中，消去量词等值

3、式有限个体域中，消去量词等值式 设个体域为设个体域为D=a1,a2,an xA(x) A(a1) A(a2) A(an) xA(x) A(a1) A(a2) A(an)7二、基本等值式二、基本等值式n量词否定等值式量词否定等值式“并不是所有的人都是黄皮肤。并不是所有的人都是黄皮肤。” 这句话相当于这句话相当于“有的人不是黄皮肤。有的人不是黄皮肤。”)(x xxAxA)(x xA Ax x )()(x xA Ax xx xx xA A )()(x xA Ax xx xx xA A 8二、基本等值式二、基本等值式n量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式 设设A(x)是含是含x自由出现的公

4、式，自由出现的公式，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) 9二、基本等值式二、基本等值式 关于存在量词关于存在量词: 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)10二、基本等值式二、基本等值式n量词分配等值式量词分配等值式 x(A(x) B(x)xA(x)xB(x) x(A(x) B(x)xA(x)xB(x)注意：注意： 对对 无分配律，无分配律， 对对 无分配律

5、无分配律11三、等值演算与置换规则三、等值演算与置换规则 置换规则：置换规则：设设 (A)是含有公式是含有公式A的公式，的公式，用公式用公式B置换置换 (A)中所有的中所有的A后得到新的公后得到新的公式式 (B)，若若AB, 则则 (B)(A) 等值演算的基础：等值演算的基础：（1 1）一阶逻辑的基本等值式；）一阶逻辑的基本等值式；（2 2）置换规则、换名规则、代替规则。）置换规则、换名规则、代替规则。12例题例题 例例1：下面的命题都有两种不同的符号化形：下面的命题都有两种不同的符号化形式，写出其中的一种，然后通过等值演算式，写出其中的一种，然后通过等值演算得到另一种。得到另一种。 (1)

6、没有不犯错误的人没有不犯错误的人 (2) 不是所有的人都爱看电影不是所有的人都爱看电影13(1) 没有不犯错误的人没有不犯错误的人令令F(x)：x是人，是人，G(x)：x犯错误犯错误蕴涵等值式的代入实例蕴涵等值式的代入实例摩根律的代入实例摩根律的代入实例德德量词否定等值式量词否定等值式)()()()()()()()(x xG Gx xF Fx xx xG Gx xF Fx xx xG Gx xF Fx xx xG Gx xF Fx x )()(x xG Gx xF Fx x 例题例题14(2) 不是所有的人都爱看电影不是所有的人都爱看电影令令F(x)：x是人，是人，G(x)：爱看电影：爱看电影

7、)()(x xG Gx xF Fx x 摩根律的代入实例摩根律的代入实例德德量词否定等值式量词否定等值式蕴涵等值式的代入实例蕴涵等值式的代入实例 )()()()()()()()(x xG Gx xF Fx xx xG Gx xF Fx xx xG Gx xF Fx xx xG Gx xF Fx x例题例题15 例例2：设个体域：设个体域D=a,b,c，在，在D中消去下列中消去下列公式中的量词。公式中的量词。)()(1y yy yG Gx xF Fx x ）（)()()()()()()()()()()()()()()()()()()()()()()()(c cG Gb bG Ga aG Gc c

8、F Fb bF Fa aF Fc cG Gb bG Ga aG Gc cF Fc cG Gb bG Ga aG Gb bF Fc cG Gb bG Ga aG Ga aF Fc cG Gb bG Ga aG Gx xF Fx xy yy yG Gx xF Fx x 两次使用两次使用“消去等值消去等值式式”例题例题16)()()()()()()()()()(c cG Gb bG Ga aG Gc cF Fb bF Fa aF Fy yy yG Gx xx xF Fy yy yG Gx xF Fx x 量词辖域收缩与扩张等值式量词辖域收缩与扩张等值式解法二：解法二：小结：采用不同的演算过程同样可以

9、达到消去量词小结：采用不同的演算过程同样可以达到消去量词的目的，但是如何演算才更简单呢？结论是的目的，但是如何演算才更简单呢？结论是将量词将量词辖域尽可能的缩小，然后再消量词。辖域尽可能的缩小，然后再消量词。例题例题17)()(2y yG Gx xF Fy yx x ）（)()()()()()(cGbGaGcFbFaF )()()()()()(c cG Gx xF Fb bG Gx xF Fa aG Gx xF Fx x )()()()()()()()()()()()()()()()()()(c cG Gc cF Fb bG Gc cF Fa aG Gc cF Fc cG Gb bF Fb b

10、G Gb bF Fa aG Gb bF Fc cG Ga aF Fb bG Ga aF Fa aG Ga aF F )()()()(y yyGyGx xxFxFy yG Gx xF Fy yx x 方法方法2：例题例题18),(),(yxGyxFyx ),(),(),(),(b bx xG Gb bx xF Fa ax xG Ga ax xF Fx x ),(),(),(),(),(),(),(),(b bb bG Gb bb bF Fa ab bG Ga ab bF Fb ba aG Gb ba aF Fa aa aG Ga aa aF F (3)当个体域当个体域D=a,b提问：如果先消去全

11、称量词，后消去存在提问：如果先消去全称量词，后消去存在量词，结果会怎样？量词，结果会怎样？例题例题19u该题量词的辖域已经不能再缩小了，所以演算该题量词的辖域已经不能再缩小了，所以演算过程无法再简化，演算结果也不易化的更简单。过程无法再简化，演算结果也不易化的更简单。),(),(yxGyxFyx ),(),(),(),(ybGybFyyaGxaFy ),(),(),(),(),(),(),(),(bbGbbFabGabFbaGbaFaaGaaF u 两种消去顺序得到的结果相同。两种消去顺序得到的结果相同。例题例题20 例例3 3 给定解释给定解释I I 如下如下: : (a) 个体域个体域 D

12、=2，3 (b) (c) (d) 谓词如下页所示谓词如下页所示2 a2) 3(3) 2()( ffxf，为为：例题例题21 在在 I 下求下列各式的真值。下求下列各式的真值。. 1) 3(, 0) 2()(0) 2 , 3(L) 3 , 2(L) 2 , 2(L:),(L0.) 3 , 3(1,) 2 , 3() 3 , 2() 2 , 2(:),( FFxFyxGGGGyxG为为：为为为为例题例题22),()4(),()3()(,()()2(),()()1(yxxLyyxyLxxfxGxfFxaxGxFx 计算过程见教材计算过程见教材例题例题23例例4：证明下面的谓词公式是永真式。：证明下面

13、的谓词公式是永真式。为为任任意意公公式式、其其中中）（）（BAxBxABAxxxFxxF)()(2)()(1 证明谓词公式是永真式不能像命题公式那证明谓词公式是永真式不能像命题公式那样使用真值表。常用的方法是等值演算。样使用真值表。常用的方法是等值演算。例题例题24)()()()()()()()(1x xF Fx xF Fx xx xxFxFx xF Fx xx xxFxFx xxFxFx xxFxFx xxFxF ）（经过等值演算可知该公式是永真式。经过等值演算可知该公式是永真式。例题例题251)()()()()()()()(2 xBxBxBxBA Ax xxBxBB Bx xA Ax xx

14、BxBB BA Ax xxBxBA AB BA Ax xxBxBA Ax xB BA Ax xxBxBxAxAB BA Ax xxBxBxAxAB BA Ax x）（例题例题26兔子比乌龟跑得快。兔子比乌龟跑得快。令：令：F(x):x是兔子是兔子 G(y):y是乌龟是乌龟 L(x,y):x比比y跑得快跑得快),()()(yxLyGyxFx 命题符号化为：命题符号化为：),()()(yxLyGxFyx 另外一种等值的符号化形式为：另外一种等值的符号化形式为：275.2 前束范式前束范式 定义：定义：设设A为一个一阶逻辑公式为一个一阶逻辑公式, 若若A具有如具有如下形式下形式Q1x1Q2x2Qkx

15、kB, 则称则称A为为前束范式前束范式, 其中其中Qi (1 i k)为为 或或 ，B为不含量词的公式。为不含量词的公式。例：例： x y(F(x)(G(y) H(x,y) x (F(x) G(x)x(F(x) G(x)不是前束范式。不是前束范式。B前束前束范式范式B285.2 前束范式前束范式(1) x(M(x) F(x)解：解： x(M(x) F(x) x( M(x)F(x) （量词否定等值式）（量词否定等值式） x(M(x)F(x)两步结果都是原公式的前束范式。两步结果都是原公式的前束范式。 例例1：求下列公式的前束范式：求下列公式的前束范式 295.2 前束范式前束范式(2) xF(x

16、)xG(x)解：解： xF(x)xG(x) xF(x)x G(x) （量词否定等值式）（量词否定等值式） x(F(x)G(x) （量词分配等值式）（量词分配等值式）另有一种形式如下：另有一种形式如下：305.2 前束范式前束范式 xF(x)xG(x) xF(x)x G(x) xF(x)y G(y) ( 换名规则换名规则 ) x(F(x)y G(y) ) ( 量词辖域扩张量词辖域扩张 ) x y(F(x)G(y) ( 量词辖域扩张量词辖域扩张 )315.2 前束范式前束范式(3) xF(x)xG(x) 解解 xF(x)xG(x) xF(x)x G(x) x(F(x)G(x) 或或 x y(F(x

17、)G(y)325.2 前束范式前束范式 (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) (换名规则换名规则) z y(F(z)(G(x,y)H(y)或或 xF(x)y(G(t,y)H(y) (代替规则代替规则) x y (F(x)(G(t,y)H(y)335.2 前束范式前束范式(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) x y(F(x,u)G(x

18、,y) H(x,z)注意：注意： x与与 y不能颠倒不能颠倒 (换名规则换名规则)345.2 前束范式前束范式（6）),()(),(321122211x xx xx xH Hx xx xG Gx xx xx xF Fx x ),()(),(),()(),(),()(),(),()(),(345241521345524121345522411321122211xxxHxGxxFxxxxxxHxxGxxFxxxxxHxxGxxxFxxxxHxxGxxxFx 355.2 前束范式前束范式 例题小结：例题小结：n公式的前束范式不惟一；公式的前束范式不惟一；n求公式的前束范式的方法求公式的前束范式的方法

19、: : 利用基本等值利用基本等值式、置换规则、换名规则、代替规则进行式、置换规则、换名规则、代替规则进行等值演算。等值演算。 定理定理：一阶逻辑中的任何公式都存在与之：一阶逻辑中的任何公式都存在与之等值的前束范式。等值的前束范式。365.3一阶逻辑的推理理论一阶逻辑的推理理论n推理的形式结构推理的形式结构n重要的推理定律重要的推理定律n推理规则推理规则n构造证明（附加前提证明法）构造证明（附加前提证明法） 37一、推理的形式结构一、推理的形式结构 推理的形式结构推理的形式结构有两种：有两种： 第一种第一种 A1 A2 AkB (*) 第二种第二种 前提：前提：A1，A2，Ak 结论：结论： B

20、 其中其中 A1,A2,Ak,B为一阶逻辑公式为一阶逻辑公式. 若若(*)为永真式为永真式, 则称则称推理正确推理正确, 否则称否则称推理不正确推理不正确38一、推理的形式结构一、推理的形式结构 判断推理是否正确的方法：判断推理是否正确的方法：n等值演算法等值演算法，应用这种方法时采用第一种，应用这种方法时采用第一种形式结构；形式结构；n构造证明法构造证明法，采用第二种形式结构。，采用第二种形式结构。39二、重要的推理定律二、重要的推理定律 第一组第一组 命题逻辑推理定律代换实例命题逻辑推理定律代换实例 如：如： xF(x)yG(y)xF(x) 化简律代换实例化简律代换实例. 第二组第二组 由

21、基本等值式生成的推理定律由基本等值式生成的推理定律如：由如：由 xA(x)x A(x) 生成生成 xA(x)x A(x), x A(x)xA(x), 40二、重要的推理定律二、重要的推理定律 第三组第三组 xA(x)xB(x)x(A(x) B(x) x(A(x) B(x)xA(x)xB(x) )()()()()()()()(x xx xB Bx xx xA Ax xB Bx xA Ax xx xx xB Bx xx xA Ax xB Bx xA Ax x 41三、推理规则三、推理规则(1)前提引入规则前提引入规则 (2)结论引入规则结论引入规则(3)置换规则置换规则 (4)假言推理规则假言推理

22、规则(5)附加规则附加规则 (6)化简规则化简规则(7)拒取式规则拒取式规则 (8)假言三段论规则假言三段论规则(9)析取三段论规则析取三段论规则 (10)构造性二难推理规则构造性二难推理规则(11)合取引入规则合取引入规则 42(12) 全称量词消去规则（记为全称量词消去规则（记为UI）)()(2)()(1c cA Ax xx xA Ay yA Ax xx xA A ）（或或）（注意：下面的规则只能用于前束范式。注意：下面的规则只能用于前束范式。n在在(1)式中，式中，y应为任意的应为任意的不在不在A(x)中约束出现中约束出现的个的个体变项。体变项。n在第二式中，在第二式中，c为任意的未在为

23、任意的未在A(x)中出现过的个体中出现过的个体常项。常项。n用用y或或c去取代去取代A(x)中的自由出现的中的自由出现的x时，一定要在时，一定要在x自由出现的一切地方进行取代。自由出现的一切地方进行取代。43(13) 全称量词引入规则（记为全称量词引入规则（记为UG）)()(xxAyA n无论无论A(y)中自由出现的个体变项中自由出现的个体变项y取何值，取何值，A(y)应应该均为真。该均为真。 nx不约束出现在不约束出现在A(y)中。中。),()(y yx xx xF Fy yA A y yx xy yx xF FD D :),(：实实数数域域；例例：个个体体域域若对若对A(y) 应用应用UG

24、规则时，用在规则时，用在A(y) 中约束中约束出现的出现的x代替代替y，则得到，则得到),(xxxFx 44(14) 存在量词消去规则（记为存在量词消去规则（记为EI）)()(cAxxA nc是个体域中使是个体域中使A为真的某个确定的个体，且为真的某个确定的个体，且c不不在在A(x)中出现。中出现。n若若A(x)中除自由出现的中除自由出现的x外，外，还有其他自由出现的还有其他自由出现的个体变项，此规则不能使用。个体变项，此规则不能使用。对公式对公式 能否用能否用EI规则？规则？ x xG Gy yF Fx x 提问：提问：45三、推理规则三、推理规则y yx xy yx xF FD D :),

25、(：实实数数域域；例例：个个体体域域),()1(y yx xy yF Fx x 前提引入前提引入),()2(y yz zy yF F (1)UI规则规则),()3(c cz zF F(2)EI规则规则),()4(cxxF (3)UG规则规则吗吗？能能推推出出有有效效结结论论由由前前提提),(),(cxxFyxyFx 46(15) 存在量词引入规则（记为存在量词引入规则（记为EG）)()(xxAcA 该式成立的条件是：该式成立的条件是：nc是使是使A为真的特定个体常项为真的特定个体常项.n取代取代c的的x不能在不能在A(c)中出现过中出现过.47四、构造推理证明四、构造推理证明一阶逻辑自然推理系

26、统一阶逻辑自然推理系统F1.字母表，即一阶语言的字母表。字母表，即一阶语言的字母表。2.合式公式。合式公式。3.推理规则推理规则 构造推理证明的方法：直接法，附加前提引构造推理证明的方法：直接法，附加前提引入法和归谬法。入法和归谬法。48四、构造推理证明四、构造推理证明 例例1：在自然推理系统中，指出下面各证明：在自然推理系统中，指出下面各证明序列中的错误。序列中的错误。（1） 前提引入前提引入 EI规则规则)()(x xx xG Gx xF F )()(c cG Gc cF F（2） 前提引入前提引入 EI规则规则)()(y yy yG Gx xx xF F )()(b bG Ga aF F

27、49四、构造推理证明四、构造推理证明（3） 前提引入前提引入 EG规则规则)()(y yG Gy yF F)()(x xG Gx xF Fx x （4） 前提引入前提引入 EG规则规则)()(b bG Ga aF F )()(x xG Gx xF Fx x （5） 前提引入前提引入 UG规则规则)()(c cG Gc cF F)()(x xG Gx xF Fx x 50四、构造推理证明四、构造推理证明 例例2： 证明苏格拉底三段论证明苏格拉底三段论: “人都是要死的人都是要死的, 苏格拉底是人，所以苏格拉底是要死的。苏格拉底是人，所以苏格拉底是要死的。” 令：令：F(x): x是人是人, G(

28、x): x是要死的是要死的, a: 苏格拉底苏格拉底 前提：前提： x(F(x)G(x)，F(a) 结论：结论：G(a)51四、构造推理证明四、构造推理证明证明：证明： F(a) 前提引入前提引入 x(F(x)G(x) 前提引入前提引入 F(a)G(a) UI G(a) 假言推理假言推理注意：使用注意：使用UI时，用时，用a取代取代x。52四、构造推理证明四、构造推理证明 例例3：乌鸦都不是白色的。：乌鸦都不是白色的。 北京鸭是白色的。北京鸭是白色的。 因此，北京鸭不是乌鸦。因此，北京鸭不是乌鸦。 令：令：F(x): x是乌鸦是乌鸦, G(x): x是北京鸭是北京鸭, H(x): x是白色的是白色的 前提：前提： x(F(x)H(x)， x(G(x)H(x) 结论：结论： x(G(x)F(x)53四、构造推理证明四、构造推理证明证明：证明： x(F(x)H(x) 前提引入前提引入 F(y)H(y) UI