离散数学课件 第二章.ppt

《离散数学课件 第二章.ppt》由会员分享，可在线阅读，更多相关《离散数学课件 第二章.ppt（74页珍藏版）》请在沃文网上搜索。

1、第二章第二章 一阶逻辑一阶逻辑 苏格拉底三段论苏格拉底三段论人人都是要死的都是要死的苏格拉底是人苏格拉底是人所以苏格拉底是要死的所以苏格拉底是要死的pqr第二章第二章 一阶逻辑一阶逻辑 第二章第二章 一阶逻辑一阶逻辑本章学习目标本章学习目标 命题逻辑中原子命题是最小的单位，不能命题逻辑中原子命题是最小的单位，不能够再进行分解，这给推理带来了很大局限性，够再进行分解，这给推理带来了很大局限性，本章引入一阶逻辑。学习关于一阶逻辑的相关本章引入一阶逻辑。学习关于一阶逻辑的相关概念和定理，解决实际问题。概念和定理，解决实际问题。第二章第二章 一阶逻辑一阶逻辑 第二章第二章 一阶逻辑一阶逻辑 2.1 一

2、阶逻辑基本概念一阶逻辑基本概念 2.2 一阶逻辑合式公式与解释一阶逻辑合式公式与解释 2.3 一阶逻辑等值式一阶逻辑等值式2.4 一阶逻辑推理理论一阶逻辑推理理论*第二章第二章 一阶逻辑一阶逻辑 2.1 一阶逻辑基本概念一阶逻辑基本概念 个体词个体词 谓词谓词 量词量词 一阶逻辑中命题符号化一阶逻辑中命题符号化 第二章第二章 一阶逻辑一阶逻辑 个体词（个体）:所研究对象中可以独立存在的具体或抽象的客体个体常项（元）：具体的事物，用a,b,c表示个体变项（元）：抽象的事物，用x,y,z表示个体域（论域）:个体变项的取值范围有限个体域，如a,b,c,1,2无限个体域，如N,Z,R,全总个体域:宇宙

3、间一切事物组成2.1 一阶逻辑基本概念一阶逻辑基本概念第二章第二章 一阶逻辑一阶逻辑 谓词:表示个体词性质或相互之间关系的词谓词常项：F(a)：a是人谓词变项：F(x)：x具有性质F一元谓词:表示事物的性质多元谓词(n元谓词,n2):表示事物之间的关系如L(x,y)：x与y有关系L，L(x,y)：xy，0元谓词:不含个体变项的谓词,即命题常项或命题变项2.1 一阶逻辑基本概念一阶逻辑基本概念第二章第二章 一阶逻辑一阶逻辑 2.1 一阶逻辑基本概念一阶逻辑基本概念例2.1 将下列命题在一阶逻辑中符号化，并讨论它们的真值：（1）只有4是素数，8才是素数。（2）如果2小于3，则8小于7。解（1）设谓

4、词G（x）：x是素数，a：4，b：8；（1）中的题符号化为谓词的蕴涵式：G（a）G（b）由于此蕴涵式的前件为假，所以（1）中的命题为真。（2）设谓词H（x，y）：x小于y，a：2，b：3，c：8，d：7（2）中的命题符号化为谓词的蕴涵式：H（a，b）H（c，d）由于此蕴涵式的前件为真，后件为假，所以（2）中的命题为假。第二章第二章 一阶逻辑一阶逻辑 量词:表示数量的词全称量词:表示任意的,所有的,一切的等如x 表示对个体域中所有的x存在量词:表示存在,有的,至少有一个等如x表示在个体域中存在x2.1 一阶逻辑基本概念一阶逻辑基本概念第二章第二章 一阶逻辑一阶逻辑 2.1 一阶逻辑基本概念一阶逻

5、辑基本概念解（a）令F（x）：x要死的；G（x）：x天生就近视。（1）在个体域D1中除人外，没有其他的事物，因而（1）可符号化为：x F（x）（2）在个体域D1中有些人是天生就近视，因而（2）可符号化为xG（x）例 2.2 在个体域分别限制为（a）和（b）条件时，将下面的命题符号化：（1）所有人都是要死的。（2）有的人天生就近视。其中：（a）个体域D1为人类集合。（b）个体域D2为全总个体域。全称量词存在量词第二章第二章 一阶逻辑一阶逻辑 2.1 一阶逻辑基本概念一阶逻辑基本概念例 2.2 在个体域分别限制为（a）和（b）条件时，将下面的命题符号化：（1）所有人都是要死的。（2）有的人天生就近

6、视。（b）在个体域D2中除人外，还有其他的事物，因而在将（1）、（2）符号化时，必须考虑先将人分离出来，令M（x）：x是人。在D2中，（1）、（2）可分别描述如下：（1）对于宇宙间的一切事物，如果事物是人，则他是要死的。（2）在宇宙间存在着天生就近视的人。将（1）、（2）分别符号化为：（1）x（M（x）F（x）（2）x（M（x）G（x）在个体域D1、D2中命题（1）、（2）都是真命题。特性谓词第二章第二章 一阶逻辑一阶逻辑 2.1 一阶逻辑基本概念一阶逻辑基本概念例2.3在个体域分别限制为（a）和（b）条件时，将下面的命题符号化：（1）对任意的x，都有x2-5x+6=（x-2）（x-3）（2）

7、存在x，使得x+1=0。其中：（a）个体域D1为自然数集合。（b）个体域D2为实数集合。第二章第二章 一阶逻辑一阶逻辑 2.1 一阶逻辑基本概念一阶逻辑基本概念解（a）令F（x）：x2-5x+6=（x-2）（x-3）；G（x）：x+1=0。（1）可符号化为：xF(x)（2）可符号化为：xG（x）在个体域D1中命题（1）为真命题，命题（2）为假命题。例2.3在个体域分别限制为（a）和（b）条件时，将下面的命题符号化：（1）对任意的x，都有x2-5x+6=（x-2）（x-3）（2）存在x，使得x+1=0。其中：（a）个体域D1为自然数集合。（b）个体域D2为实数集合。第二章第二章 一阶逻辑一阶逻辑

8、 2.1 一阶逻辑基本概念一阶逻辑基本概念解（b）在个体域D2中（1）、（2）符号化分别为（1）xF（x）（2）xG（x）在个体域D2中命题（1）、（2）都是真命题。例2.3在个体域分别限制为（a）和（b）条件时，将下面的命题符号化：（1）对任意的x，都有x2-5x+6=（x-2）（x-3）（2）存在x，使得x+1=0。其中：（a）个体域D1为自然数集合。（b）个体域D2为实数集合。第二章第二章 一阶逻辑一阶逻辑 2.1 一一阶阶逻逻辑辑基基本本概概念念例2.4将下列命题符号化，并指出真值情况。（1）没有人登上过月球。（2）所有人的头发未必都是黑色的。解个体域为全总个体域，令M（x）：x是人。

9、（1）令F（x）：x登上过月球。命题（1）符号化为：x（M（x）F（x）设a是1969年登上月球完成阿波罗计划的一名美国人，则M（a）F（a）为真，故命题（1）为假。（2）令H（x）：x的头发是黑色的。命题（2）可符号化为：x（M（x）H（x）还有没有另一种表示呢？我们知道有的人头发是褐色的，所以x（M（x）H（x）为假，故命题（2）为真。第二章第二章 一阶逻辑一阶逻辑 2.1 一阶逻辑基本概念一阶逻辑基本概念例2.5 在一阶逻辑中将下列命题符号化。计算机系的学生都要学离散数学。解 取个体域为全总个体域。令C（x）：x是计算机系的学生，G（x）：x要学离散数学;则命题（2）可符号化为：x（C（

10、x）G（x）第二章第二章 一阶逻辑一阶逻辑 2.1 一阶逻辑基本概念一阶逻辑基本概念例2.6 将下列命题符号化。（1）尽管有人聪明，但并非所有人都聪明。（2）这只大红书柜摆满了那些古书。解 （1）令C（x）：x聪明；M（x）：x是人。则命题（1）可符号化为x（M（x）C（x）x（M（x）C（x）（2）令F（x，y）：x摆满了y；R（x）：x是大红书柜；Q（x）:x是古书；a：这只；b：那些。则命题（2）可符号化为R（a）Q（b）F（a，b）第二章第二章 一阶逻辑一阶逻辑 2.1 一阶逻辑基本概念一阶逻辑基本概念练习 将下列命题符号化。（1）猫比老鼠跑得快。（2）有的猫比所有老鼠跑得快。（3）并

11、不是所有的猫比老鼠跑得快。（4）不存在跑得同样快的两只猫。解 设个体域为全总个体域。令C（x）：x是猫；M（y）：y是老鼠；Q（x，y）：x比y跑得快；L（x，y）：x和y跑得同样快。这4个命题分别符号化为：（1）x y（C（x）M（y）Q（x，y）；（2）x（C（x）y（M（y）Q（x，y）；（3）x y（C（x）M（y）Q（x，y）；（4）x y（C（x）C（y）L（x，y）。第二章第二章 一阶逻辑一阶逻辑 2.2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释定义字母表包含下述符号：(1)个体常项：a,b,c,ai,bi,ci,i1(2)个体变项：x,y,z,xi,yi,zi,i1(3)函

12、数符号：f,g,h,fi,gi,hi,i1(4)谓词符号：F,G,H,Fi,Gi,Hi,i1(5)量词符号：,(6)联结词符号：,(7)括号与逗号：(,),，第二章第二章 一阶逻辑一阶逻辑 2.2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释定义项的定义如下：(1)个体常项和个体变项是项.(2)若(x1,x2,xn)是任意的n元函数，t1,t2,tn是任意的n个项，则(t1,t2,tn)是项.(3)所有的项都是有限次使用(1),(2)得到的.个体常项、变项是项，由它们构成的n元函数和复合函数还是项第二章第二章 一阶逻辑一阶逻辑 2.2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释定 义 设 R

13、(x1,x2,xn)是 任 意 的 n元 谓 词，t1,t2,tn是任意的n个项，则称R(t1,t2,tn)是原子公式.原子公式是由项组成的n元谓词.例如，F(x,y),F(f(x1,x2),g(x3,x4)等均为原子公式第二章第二章 一阶逻辑一阶逻辑 2.2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释定义合式公式（简称公式）定义如下：(1)原子公式是合式公式.(2)若A是合式公式，则(A)也是合式公式(3)若A,B是合式公式，则(AB),(AB),(AB),(AB)也是合式公式(4)若A是合式公式，则xA,xA也是合式公式(5)只有有限次地应用(1)(4)形成的符号串是合式公式.第二章第二

14、章 一阶逻辑一阶逻辑 2.2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释定义在公式xA和xA中，称x为指导变元，A为相应量词的辖域.在x和x的辖域中，x的所有出现都称为约束出现，A中不是约束出现的其他变项均称为是自由出现的.例如,在公式x(F(x,y)G(x,z)中,A=(F(x,y)G(x,z)为x的辖域，x为指导变元,A中x的两次出现均为约束出现，y与z均为自由出现.闭式:不含自由出现的个体变项的公式.第二章第二章 一阶逻辑一阶逻辑 2.2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释例2.7 指出下列各式量词的辖域及变项的约束情况：（1）x（P（x）y R（x，y）（2）x（F（x）G

15、（y）y（H（x）M（x，y，z）（1）x（P（x）y R（x，y）对于x的辖域是（P（x）y R（x，y），y的辖域是R（x，y），x，y均是约束出现的。（2）x（F（x）G（y）y（H（x）M（x，y，z）对于x的辖域是（F（x）G（y），其中x是约束出现的，而y是自由出现的。对y的辖域是（H（x）M（x，y，z），其中y是约束出现的，而x，z是自由出现的。在整个公式中，x约束出现一次，自由出现两次，y约束出现一次，自由出现一次，z仅自由出现一次。第二章第二章 一阶逻辑一阶逻辑 2.2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释换名规则：将量词辖域中出现的某个约束出现的个体变项及对应的指

16、导变项，改成另一个辖域中未曾出现过的个体变项符号，公式中其余部分不变例2.8 对公式x（P（x）R（x，y）Q（x，y）进行换名。解 对约束变项 x 换名为 t 后为t（P（t）R（t，y）Q（x，y）第二章第二章 一阶逻辑一阶逻辑 2.2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释对公式中的自由变项也可以更改，这种更改称作代替。自由变项的代替规则是：（1）对于谓词公式中的自由变项，可以代替，此时需要对公式中出现该自由变项的每一处进行代替。（2）用以代替的变项与原公式中所有变项的名称都不能相同。第二章第二章 一阶逻辑一阶逻辑 2.2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释例2.9 对公

17、式x（F（x）G（x，y）y H（y）代替。解 对y实施代替，经过代入后原公式为x（F（x）G（x，t）y H（y）另外，量词作用域中的约束变项，当论域的元素是有限时，个体变项的所有可能的取代是可以枚举的。设论域元素为a1，a2，an，则 x A（x）A（a1）A（a2）A（an）x A（x）A（a1）A（a2）A（an）。第二章第二章 一阶逻辑一阶逻辑 2.2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释定义解释I由下面4部分组成：(a)非空个体域DI(b)DI中一些特定元素等(c)DI上一些特定函数等(d)DI上一些特定谓词等说明：被解释的公式A中的个体变项均取值于DI若A中含个体常项a、

18、函数f、谓词F,就分别解释成、第二章第二章 一阶逻辑一阶逻辑 2.2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释被解释的公式不一定全部包含解释中的4部分.闭式在任何解释下都是命题，注意不是闭式的公式在某些解释下也可能是命题.第二章第二章 一阶逻辑一阶逻辑 2.2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释永真式（逻辑有效式）：无成假赋值矛盾式（永假式）：无成真赋值可满足式：至少有一个成真赋值几点说明：永真式为可满足式，但反之不真谓词公式的可满足性（永真性,永假性)是不可判定的利用代换实例可判某些公式的类型 第二章第二章 一阶逻辑一阶逻辑 2.2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释

19、定义设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 的代换实例.定理重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式.第二章第二章 一阶逻辑一阶逻辑 2.2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释例2.10 指出下面公式在解释I下的真值。（1）G=x（P（f（x）Q（x，f（a）；（2）H=x（P（x）Q（x，a）。给出如下的解释I：D=2，3；a：2；f（2）=3、f（3）=2；P（2）

20、=0、P（3）=1；Q（2，2）=1、Q（2，3）=1、Q（3，2）=0、Q（3，3）=1；第二章第二章 一阶逻辑一阶逻辑 2.2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释解（1）G=x（P（f（x）Q（x，f（a）；D=2，3；a=2；f（2）=3、f（3）=2；P（2）=0、P（3）=1；Q（2，2）=1、Q（2，3）=1、Q（3，2）=0、Q（3，3）=1；G（P（f（2）Q（2，f（2）（P（f（3）Q（3，f（2）（P（3）Q（2，3）（P（2）Q（3，3）（11）（01）1第二章第二章 一阶逻辑一阶逻辑 2.2 一阶逻辑合式公式及解释一阶逻辑合式公式及解释解 （2）H=x（P（

21、x）Q（x，a）D=2，3；a=2；f（2）=3、f（3）=2；P（2）=0、P（3）=1；Q（2，2）=1、Q（2，3）=1、Q（3，2）=0、Q（3，3）=1；H （P（2）Q（2，2）P（3）Q（3，2）0110 0第二章第二章 一阶逻辑一阶逻辑 2.3 一阶逻辑等值式一阶逻辑等值式等值式基本等值式量词否定等值式量词辖域收缩与扩张等值式量词分配等值式前束范式 第二章第二章 一阶逻辑一阶逻辑 2.3 一阶逻辑等值式一阶逻辑等值式定义 若AB为逻辑有效式，则称A与B是等值的，记作 AB，并称AB为等值式.基本等值式:命题逻辑中16组基本等值式的代换实例如，xF(x)yG(y)xF(x)yG(

22、y)(xF(x)yG(y)xF(x)yG(y)等消去量词等值式设D=a1,a2,anxA(x)A(a1)A(a2)A(an)xA(x)A(a1)A(a2)A(an)第二章第二章 一阶逻辑一阶逻辑 2.3 一阶逻辑等值式一阶逻辑等值式定理 1 设A（x）是谓词公式，有关量词否定的两个等价公式：（1）x A（x）xA（x）（2）x A（x）xA（x）证明 （1）设个体域是有限的为：D=a1，a2，an，则有:x A（x）（A（a1）A（a2）A（an）A（a1）A（a2）A（an）xA（x）第二章第二章 一阶逻辑一阶逻辑 2.3 一阶逻辑等值式一阶逻辑等值式定理 1 设A（x）是谓词公式，有关量词

23、否定的两个等价公式：（1）x A（x）xA（x）（2）x A（x）xA（x）证明 （2）设个体域是有限的为：D=a1，a2，an，则有 x A（x）（A（a1）A（a2）A（an）A（a1）A（a2）A（an）xA（x）第二章第二章 一阶逻辑一阶逻辑 2.3 一阶逻辑等值式一阶逻辑等值式定理2 设A（x）是任意的含自由出现个体变项x的公式，B是不含x出现的公式，则有（1）x（A（x）B）x A（x）B（2）x（A（x）B）x A（x）B（3）x（A（x）B）x A（x）B（4）x（BA（x）B x A（x）（5）x（A（x）B）x A（x）B（6）x（A（x）B）x A（x）B（7）x（A（x

24、）B）x A（x）B（8）x（BA（x）Bx A（x）辖域收缩与扩张第二章第二章 一阶逻辑一阶逻辑 2.3 一阶逻辑等值式一阶逻辑等值式证明 （1）设D是个体域，I为任意解释，即用确定的命题及确定的个体代替出现在x（A（x）B）和x A（x）B中的命题变项和个体变项，于是得到两个命题，若对x（A（x）B）代替之后所得命题的真值为真，此时必有A（x）B的真值为真；因而A（x）真值为真或B的真值为真，若B的真值为真，则x A（x）B的真值为真；若B的真值为假，则必有对D中任意x都使得A（x）的真值为真，所以x（A（x）B）为真，从而x A（x）B为真。若对x（A（x）B）代替之后所得命题的真值为假

25、，则A（x）和B的真值必为假，因此x A（x）B的真值为假；所以x（A（x）B）为假，有x A（x）B为假。第二章第二章 一阶逻辑一阶逻辑 2.3 一阶逻辑等值式一阶逻辑等值式证明（2）、（5）和（6）证明与（1）类似，证明过程略。（3）x（A（x）B）x（A（x）B）x A（x）B x A（x）B x A（x）B（4）、（7）、（8）证明与（3）类似，证明过程略。第二章第二章 一阶逻辑一阶逻辑 2.3 一阶逻辑等值式一阶逻辑等值式定理3 设A（x）、B（x）是任意包含自由出现个体变项x的公式,则有：（1）x（A（x）B（x）x A（x）x B（x）（2）x（A（x）B（x）x A（x）x B

26、（x）另一种呢？（a）x（A（x）B（x）？xA（x）xB（x）（b）x（A（x）B（x）？xA（x）xB（x）量词分配等值式第二章第二章 一阶逻辑一阶逻辑 2.3 一阶逻辑等值式一阶逻辑等值式证明 （1）x（A（x）B（x）x A（x）x B（x）设D是任一个体域，若x（A（x）B（x）的真值为真，则对任意aD，有A（a）和B（a）同时为真，即x A（x）为真、x B（x）为真，从而x A（x）x B（x）为真。若x（A（x）B（x）的真值为假，则对任意aD，有A（a）和B（a）不能同时为真，即x A（x）和 x B（x）的真值不能同时为真，从而x A（x）x B（x）的真值为假。综上所述

27、x（A（x）B（x）x A（x）x B（x）第二章第二章 一阶逻辑一阶逻辑 2.3 一阶逻辑等值式一阶逻辑等值式证明 （2）x（A（x）B（x）x A（x）x B（x）设D是任一个体域，若x（A（x）B（x）的真值为真,则存在aD，使得A（a）B（a）为真，即A（a）为真或B（a）为真，即x A（x）为真或x B（x）为真，从而x A（x）x B（x）为真。若x（A（x）B（x）的真值为假，则对任意aD，使得A（a）B（a）为假，此时，A（a）为假，B（a）为假，从而x A（x）x B（x）的真值为假。综上所述 x（A（x）B（x）x A（x）x B（x）第二章第二章 一阶逻辑一阶逻辑 2.3

28、 一阶逻辑等值式一阶逻辑等值式例2.11 证明下列各等值式（1）x（A（x）B（x）x（A（x）B（x）（2）x（A（x）B（x）x（A（x）B（x）证明 （1）x（A（x）B（x）x（A（x）B（x）x（A（x）B（x）x（A（x）B（x）第二章第二章 一阶逻辑一阶逻辑 2.3 一阶逻辑等值式一阶逻辑等值式例2.11 证明下列各等值式（1）x（A（x）B（x）x（A（x）B（x）（2）x（A（x）B（x）x（A（x）B（x）证明（2）x（A（x）B（x）x（A（x）B（x）x（A（x）B（x）x（A（x）B（x）第二章第二章 一阶逻辑一阶逻辑 2.3 一阶逻辑等值式一阶逻辑等值式例如，xy(

29、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为不含量词的公式.（一个谓词公式，如果量词均在全式的开头，且辖域延伸到公式的末尾）第二章第二章 一阶逻辑一阶逻辑 2.3 一阶逻辑等值式一阶逻辑等值式定理 对任意一个谓词公式都可以化为与它等价的前束范式。证明 首先利用等价公式将谓词公式中的联结词，去掉。其次利用量词的转化律将量词前面的否定深入到谓词前面，在利用改名和代入规则以及量词辖域扩张的公式将

30、量词移到全式的最前面，这样便得到前束范式。第二章第二章 一阶逻辑一阶逻辑 2.3 一阶逻辑等值式一阶逻辑等值式例求下列谓词公式的前束范式。（1）xy（zA（x，z）A（x，z）tB（x，y，t）解（1）xy（zA（x，z）A（x，z）tB（x，y，t）xy（zA（x，z）A（x，z）tB（x，y，t）xy（zA（x，z）A（x，z）tB（x，y，t）（量词转化）xy（wA（x，w）A（x，z）tB（u，v，t）（改名及代入规则）xywt（A（x，w）A（x，z）B（u，v，t）（量词辖域扩张）第二章第二章 一阶逻辑一阶逻辑 2.3 一阶逻辑等值式一阶逻辑等值式例求下列谓词公式的前束范式。（2）

31、x（yP（x，y）xy（Q（x，y）y（P（y，x）Q（x，y）解（2）x（yP（x，y）xy（Q（x，y）y（P（y，x）Q（x，y）x（yP（x，y）xy（Q（x，y）y（P（y，x）Q（x，y）x（yP（x，y）xy（Q（x，y）y（P（y，x）Q（x，y）（量词转化、德摩根定律）第二章第二章 一阶逻辑一阶逻辑 2.3 一阶逻辑等值式一阶逻辑等值式x（yP（x，y）xy（Q（x，y）z（P（z，x）Q（x，z）（改名原则）x（yP（x，y）xyz（Q（x，y）（P（z，x）Q（x，z）（量词辖域扩张）x（yP（x，y）uvz（Q（u，v）（P（z，u）Q（u，z）（改名原则）xyuvz（

32、P（x，y）（Q（u，v）（P（z，u）Q（u，z）（量词辖域扩张）第二章第二章 一阶逻辑一阶逻辑 2.4 一阶逻辑推理理论一阶逻辑推理的形式结构:（G1G2Gn）H若上式是逻辑有效式，则称推理正确,H是G1,G2,Gn 的逻辑结论，记作:（G1G2Gn）H第二章第二章 一阶逻辑一阶逻辑 2.4 一阶逻辑推理理论定理 下列蕴涵式成立（1）x A（x）x B（x）x（A（x）B（x）（2）x（A（x）B（x）x A（x）x B（x）（3）x（A（x）B（x）x A（x）x B（x）（4）x（A（x）B（x）x A（x）x B（x）（5）x A（x）x B（x）x（A（x）B（x）第二章第二章 一

33、阶逻辑一阶逻辑 2.4 一阶逻辑推理理论证明:（1）x A（x）x B（x）x（A（x）B（x）设x A（x）x B（x）在任意解释下的真值为真，即对个体域中的每一个x，都能使A（x）的真值为真或者对个体域中的每一个x都能使B（x）的真值为真，无论哪种情况，对于个体域中的每一个x都能使A（x）B（x）的真值为真。因此，蕴涵式x A（x）x B（x）x（A（x）B（x）成立。第二章第二章 一阶逻辑一阶逻辑 2.4 一阶逻辑推理理论证明:（2）x（A（x）B（x）x A（x）x B（x）设个体域为D，在解释I下 x（A（x）B（x）的真值为真，即存在aD使得A（a）B（a）为真，从而A（a）为真，

34、B（a）为真，故有x A（x）、x B（x）均为真，所以，蕴涵式x（A（x）B（x）x A（x）x B（x）成立。第二章第二章 一阶逻辑一阶逻辑 2.4 一阶逻辑推理理论证明:（3）x（A（x）B（x）x A（x）x B（x）设个体域为D，在解释I下x A（x）x B（x）的真值为假,即存在aD使得A（a）B（a）为假，所以蕴涵式x（A（x）B（x）x A（x）x B（x）成立。换一种证明方式呢？第二章第二章 一阶逻辑一阶逻辑 2.4 一阶逻辑推理理论证明:（4）x（A（x）B（x）x A（x）x B（x）x（A（x）B（x）x（A（x）B（x）x（A（x）B（x）x（A（x）B（x）（x A

35、（x）x B（x）（已证明的蕴含式2）x A（x）x B（x）x A（x）x B（x）x A（x）x B（x）x A（x）x B（x）第二章第二章 一阶逻辑一阶逻辑 2.4 一阶逻辑推理理论证明:（5）x A（x）x B（x）x（A（x）B（x）x A（x）x B（x）x A（x）x B（x）x（A（x）B（x）x（A（x）B（x）第二章第二章 一阶逻辑一阶逻辑 2.4 一阶逻辑推理理论1 全称量词消去规则(简称UI规则)全称指定规则（简称US规则）这条规有下面两种形式：(1)x P（x）P（y）(2)x P（x）P（c）其中，P是谓词，x在P（x）中自由出现；（1）中y为任意不在P（x）中约

36、束出现的个体变项；（2）中c为个体域中的任意一个个体常元。第二章第二章 一阶逻辑一阶逻辑 2.4 一阶逻辑推理理论2全称量词引入规则（简称UG规则）全称推广规则 P（y）x P（x）y在P（y）中自由出现;取代y的x不能在P(y)中约束出现。第二章第二章 一阶逻辑一阶逻辑 2.4 一阶逻辑推理理论3存在量词引入规则（简称EG规则）存在推广规则P（c）x P（x）其中，c为个体域中的个体常元，这个规则比较明显，对于某些个体c，若P（c）成立，则个体域中必有x P（x）。取代c的x不能在P(c)中出现过;第二章第二章 一阶逻辑一阶逻辑 2.4 一阶逻辑推理理论4存在量词消去规则（简称EI规则）存在

37、推广规则（简称EG规则）x P（x）P（c）其中，c为个体域中的个体常元，这个规则比较明显，对于某些个体c，若P（c）成立，则个体域中必有x P（x）。c不曾在P(x)中出现过；P(x)中除x外，没有其他自由出现的个体变项。第二章第二章 一阶逻辑一阶逻辑 2.4 一阶逻辑推理理论例 证明 x（M（x）D（x）M（s）D（s）这是著名的苏格拉底三段论的论证。其中 M（x）：x是一个人。D（x）：x是要死的。s：苏格拉底。证明 （1）x（M（x）D（x）P （2）M（s）D（s）UI（1）（3）M（s）P （4）D（s）T（2）（3）I第二章第二章 一阶逻辑一阶逻辑 2.4 一阶逻辑推理理论例 判

38、断下列的推理过程是否正确。（1）x y G（x，y）P （2）y G（z，y）UI（1）（3）G（z，c）EI（2）（4）x G（x，c）UG（3）（5）y x G（x，y）EG（4）第二章第二章 一阶逻辑一阶逻辑 2.4 一阶逻辑推理理论解 这个推理过程是错误的，因为从它可以得出结论：x y G（x，y）y x G（x，y）从前面的学习中我们知道这个式子不成立。它的推导错误出现在第（3）步。x y G（x，y）的含义是：对于任意的一个x，存在着与它对应的y，使得G（x，y）成立。但是，对y G（z，y）利用ES规则消去存在变量后得到G（z，c）的含义却是：对于任意个体z，有同一个体c，使得G

39、（z，c）成立。显然，G（z，c）不是y G（z，y）的有效结论。因此，使用ES规则x P（x）P（c）消去存在量词的条件是:P（x）中除x外没有其他自由出现的个体变项。第二章第二章 一阶逻辑一阶逻辑 2.4 一阶逻辑推理理论例证明：x（C（x）（W（x）R（x）xC（x）Q（x）xR（x）xQ（x）证明（1）xC（x）P（2）C（y）EI（1）（3）x（C（x）（W（x）R（x）P（4）C（y）（W（y）R（y）UI（3）（5）W（y）R（y）T（2）（4）I（6）R（y）T（5）I（7）xR（x）EG（6）（8）Q（x）P（9）xQ（x）EG（8）（10）xR（x）xQ（x）T（7）（9）

40、I 第二章第二章 一阶逻辑一阶逻辑 2.4 一阶逻辑推理理论例 证明：x（A（x）B（x）x A（x）x B（x）证明 （1）x（A（x）B（x）P （2）A（y）B（y）UI（1）（3）x（A（x）B（x）EG（2）（4）x A（x）x B（x）T（3）E第二章第二章 一阶逻辑一阶逻辑 2.4 一阶逻辑推理理论例 给定前提：x（P（x）y（Q（y）R（x，y）x（P（x）y（S（y）R（x，y）证明下列结论：x（Q（x）S（x）第二章第二章 一阶逻辑一阶逻辑 2.4 一阶逻辑推理理论例 证明：（1）x（P（x）y（Q（y）R（x，y）P（2）P（a）y（Q（y）R（a，y）EI（1）（3）P

41、（a）T（2）（4）x（P（x）y（S（y）R（x，y）P（5）P（a）y（S（y）R（a，y）UI（4）（6）y（S（y）R（a，y）T（3）（5）Ix（P（x）y（Q（y）R（x，y）x（P（x）y（S（y）R（x，y）结论：x（Q（x）S（x）第二章第二章 一阶逻辑一阶逻辑 2.4 一阶逻辑推理理论例 证明：（7）y（Q（y）R（a，y）T（2）I（8）S（z）R（a，z）UI（6）（9）Q（z）R（a，z）UI（7）（10）R（a，z）S（z）T（8）E（11）Q（z）S（z）T（9）（10）I（12）x（Q（x）S（x）UG（11）x（P（x）y（Q（y）R（x，y）x（P（x）y（

42、S（y）R（x，y）结论：x（Q（x）S（x）第二章第二章 一阶逻辑一阶逻辑 2.4 一阶逻辑推理理论例2.18 符号化下面的命题“所有的有理数都是实数，所有的无 理数也是实数，任何虚数都不是实数，所以任何虚数既不是有理 数也不是无理数”，并推证其结论。证明 设：P（x）：x是有理数。Q（x）：x是无理数。R（x）：x是实数。S（x）：x是虚数。本题符号化为：x（P（x）R（x），x（Q（x）R（x），x（S（x）R（x）x（S（x）P（x）Q（x）第二章第二章 一阶逻辑一阶逻辑 2.4 一阶逻辑推理理论x（P（x）R（x），x（Q（x）R（x），x（S（x）R（x）x（S（x）P（x）Q（x

43、）（1）x（S（x）R（x）P（2）S（y）R（y）UI（1）（3）x（P（x）R（x）P（4）P（y）R（y）UI（3）（5）R（y）P（y）T（4）E（6）x（Q（x）R（x）P（7）Q（y）R（y）UI（6）（8）R（y）Q（y）T（7）E第二章第二章 一阶逻辑一阶逻辑 2.4 一阶逻辑推理理论x（P（x）R（x），x（Q（x）R（x），x（S（x）R（x）x（S（x）P（x）R（x）（9）S（y）P（y）T（2）（5）I（10）S（y）Q（y）T（2）（8）I（11）（S（y）P（y）（S（y）Q（y）T（9）（10）I（12）（S（y）P（y）（S（y）Q（y）T（11）E（13）S（y）（P（y）Q（y）T（12）E（14）S（y）（P（y）Q（y）T（13）E（15）x（S（x）P（x）Q（x）UG（14）第二章第二章 一阶逻辑一阶逻辑 本章小结 本章是命题逻辑的深入和扩展，通过了解命题逻辑的局限性引入了谓词、量词、个体域、个体等概念；在此基础上定义了谓词公式及对公式的解释、公式的等价、蕴涵和前束范式等内容；然后利用谓词的等价式、蕴涵式、一阶逻辑的推理理论、全称量词消去规则、全称量词引入规则、存在量词消去规则和存在量词引入规则等进行逻辑推理。第二章第二章 一阶逻辑一阶逻辑 作业作业2.32.5(2)2.62.72.102.122.132.142.15