离散数学文档第二章.doc

第二章 一阶逻辑 由上一章我们知道，命题逻辑可以形式化地描述一些自然语言中的逻辑思维，也能够用形式化的方法进行一些逻辑推理。但命题逻辑以原子命题作为最小的研究单位，不对原子命题的内部结构做深入研究。然而，这无论是在数学中还是在计算机科学中，都是不够的。例如，下列推理是人所共知的：所有的人都会呼吸,他是人,所以他会呼吸.但是，命题演算却无法反映上述推理，因为前提和结论都只能表示为原子命题，例如表示为p，q，r。在命题演算系统中,无法由前提p, q推出结论r, 结论r也根本不是前提p，q的逻辑结果。 这三个命题中涉及两个概念，它们表示事物的性质：“是人”，“会呼吸”，我们称之为谓词。它们还涉及两种主体：“所有的人”，“他”，我们称之为个体。前者表示一类个体的全部，这里使用了数量词“所有”，我们称之为量词。只有当这些细节都被清楚地表示出来，同时建立起它们之间逻辑关系的形式描述，那么刻划类似上述本章引例的推理才是可能的。谓词演算及其形式系统正是以此为目的而建立的。一阶逻辑研究的基本内容是：原子命题的个体词、谓词和量词，研究它们的形式结构和逻辑关系、正确的推理形式和规则。2.1一阶逻辑的基本概念2.1.1 个体词、谓词、量词2.1.1.1个体词与谓词定义2.1.1 在原子命题中，所描述的对象称为个体；用以描述个体的性质或个体间关系的部分，称为谓词。个体：原子命题中的主语部分；个体常元：表示特定的个体，以a，b，c，(或带下标)表示;个体变元: 表示个体的变元，以x，y，z，(或带下标)表示;个体域：个体变元的取值范围；谓词: 原子命题中的谓语(或表语)部分，常用大写字母P，Q，R，(或带下标)表示;定义2.1.2 一个原子命题的谓词形式为： 谓词符号(个体常元1，个体常元2，)。例2.1.1 张明是位大学生。设S(x)：x是大学生，c：张明，则原句的谓词形式为S(c)。我坐在张三和李四中间。设S(x,y,z)：x坐在y和z之间，i：我，z：张三，l：李四，则原句的谓词形式为S(i，z，l)。谓词常项：表示特定的谓词，以F,G,H(或带下标)表示;谓词变项: 表示不确定的谓词，以F,G,H(或带下标)表示;2.1.1.2量词在自然语言表示的命题中，经常要对某个个体域的整体进行描述，诸如“对于每一个”，“所有的”，“存在某一个”，“至少有一个”等。为了表示这些，引入了量词的概念。定义2.1.3 (1) 全称量词符，表示“对所有的，每一个，一切，对任何一个”。全称量词的形式为x，x称为指导变元；(2) 存在量词符，指代“ 存在一些，至少有一个，对于一些，某个”。存在量词形式为x，x为指导变元；说明：(1) 个体域对命题的真值有影响;(2) 若非特别指明，个体变元的个体域总是U；(5) 当个体域为U时，常需用一个特性谓词P(x)来限制个体变元x的取值范围。2.1.2 举例例2.1.2 设D为实数域，E(x,y)表示D上关系“x = y”，L(x,y) 表示:x y那么 （1）x L(0,x2+1) 真。 （2）$xE(x2-2x-1,0) 真。 （3）$xE(x2+x+1,0) 假。 （4）$xE(x2,y)当y取非负实数时真，否则假。例2.1.3 设个体域是人类，试将下列语句符号化。(1) 所有的人都呼吸;(2)有的人用左手写字;例2.1.4将下列语句用谓词公式形式化： （1）没有不犯错误的人。 F(x)：“x犯错误”，M(x)：“x是人”，它符号化为$x(M(x)F(x) 或 x(M(x)F(x) （2）凡是实数，或者大于零，或者等于零，或者小于零。 R (x)：“x是实数”，它符号化为 x(R(x)x0)例2.1.5 试将下列命题进行谓词量化:（1）有人勇敢，但不是所有的人都勇敢。 用B(x)表示“x勇敢”，它符号化为$xB(x) x B(x) （2）人人都不相互依靠，但互相帮助。 用R(x,y)表示“x依靠y”，H(x,y)表示“x帮助y”，它符号化为 xyR(x,y) xyH(x,y)2.2一阶逻辑合式公式及其解释2.2.1一阶逻辑合式定义2.2.1 项可以按如下方式递归定义而成:(1) 个体变元和常元都是项;(2) 若f是n元函数，且t1，t2，tn是项，则f(t1，t2，tn)也是项;(3) 只有有限次经过使用(1)和(2)所得到的才是项。注:项起到一个个体的作用。定义2.2.2 若R(x1，x2，xn)是n元谓词，t1，t2，tn都是项，则称R(t1，t2，tn)为原子公式。定义2.2.3 合式公式可由如下方式递归定义：(1) 原子公式是合式公式；(2) 若A，B是公式，则(A)，(AB)，(AB)，(AB)，(AB)都是合式公式；(3) 若A为合式公式，x为A中的个体变元，则xA，xA，!xA都为合式公式；(4) 仅由有限次(2)，(3)得到的才是合式公式。定义2.2.4 在一个谓词公式A中，形如xB(x)、xB(x)的部分称为A的约束部分，B(x)为相应量词的辖域；在辖域中，x的所有出现称为x的约束出现，x称为约束变元。若x的出现不是约束出现，则称x为自由变元。注(1) : 若量词后有括号，则括号内的子公式就是该量词的辖域; (2) : 若量词后无括号，则与量词紧邻的子公式为该量词的辖域; (3) : 自由变元可以用个体域中的特定个体替代，而约束变元则不能用个体域中的特定个体替代。例2.2.1指出下是中的指导变元、量词的辖域、个体变项的自由出现和约束出现(1) x(P(x)yQ(x，y) (2) xH(x)L(x，y) (3) xy(P(x，y)Q(y，z)xR(x，y)定义. 称一个无自由出现的个体变项的公式为闭式。注: 闭式都是命题，一般说来，n元谓词没有确定的意义，将公式中的变项指定为常项后才是命题。2.2.2 一阶逻辑公式的解释与分类定义.一个一阶逻辑公式的解释由以下部分组成(1)非空个体域D;(2) D中一部分特定元素；(3) D上一部分特定函数；(5) D上一部分特定谓词。例2.2.2分别对个体域D1=3，4，把P(x)解释为“x是质数”，a=3,讨论 P(a)$x P(x) 的真值。P(a)$x P(x)定义.6若公式A在每一解释I下均真，那么称A为永真式。若公式A在每一解释I下均假，那么称A为矛盾式。若公式A存在成真解释，则称A为可满足式。说明：对于一阶逻辑公式判断其类型至今没有一般的方法。定义.7设A0是含命题变项p1,p2,pn的命题公式，A1,A2,An是n个谓词公式，用Ai（1in）处处代替pi所得公式A叫公式A0的代换实例。定理.1永真式的代换实例都是永真式；矛盾式的代换实例都是矛盾式。例2.2.3因为，所以 （1） （2）都是永真式。对于可满足式通过举例子的方法说明。例2.2.4是非矛盾式的可满足式。在自然数集中，及，两种解释一个使其为真一个使其为假。2.3一阶逻辑等值式2.3.1一阶逻辑等值式定义2.3.1 设A，B是两个一阶逻辑公式，若AB是永真式，即在所有的解释下A和B的真值对应相同，则称A与B 是等值的，记作AB，并称AB为逻辑恒等式。例2.3.1说明：由于永真式的代换实例是永真式，因而，由第一章的命题逻辑等值式可派生出许多一阶逻辑等值式。定理.3.1（消去量词等值式）有限个体域中消去量词的两个等价式：若D=a，b，c，则 (1)xA(x)A(a)A(b)A(c); (2)xA(x)A(a)A(b)A(c);定理.3.2量词否定等值式 （1） （2）定理2.3.3量词辖域扩张与收缩等值式当公式B中不含自由变元x时， 第一组 (1)x A(x)Bx (A(x)B) (2)x A(x)Bx (A(x)B)(3)$x A(x)B$x (A(x)B)(4)$x A(x)B$x (A(x)B)第二组 (5)x(BA(x) Bx A(x) (6) x(A(x) B) $x A(x)B(7) $x(BA(x) B$x A(x) (8) $ x(A(x) B) x A(x)B定理2.3.4量词分配等值式(1)x (A(x)B(x) x A(x)x B(x) (2)$x (A(x)B(x) $xA(x)$x B(x)说明：(1)x A(x)x B(x)x (A(x)B(x)(2)$x (A(x)B(x)$x A(x)$x B(x)定理2.3.4（1）x yA(x,y) y x A(x,y) (2)$x $ y A(x,y) $y $ x A(x,y)定理2.3.5（换名规则）设A是一个公式，将A中某量词辖域中的某约束变项及相应的指导变元，改成该量词辖域中未曾出现的某个个体变项，公式的其余部分不变，所得公式记为，则。 定理2.3.6（代替规则）设A是一个公式，将A中自由出现的某变项，都改成该量词辖域中未曾出现的某个个体变项，公式的其余部分不变，所得公式记为，则。2.3.2前束范式定义2.3.2 ：公式A称为公式A的前束范式，如果AA，且A形如Q1x1QnxnB ,.其中Q1，Qn为量词 或 $，B中无量词。 对任何谓词公式均可作出其前束范式，因为我们总可以利用各组逻辑等价式将量词逐个移至公式的前部，其步骤是: (1)首先将公式中联结词, 消除。 (2)其次将否定词 深入到各原子公式之前。 (3)真式将量词逐个移至公式前部。 例如： xA(x)x B(x)xA(x)yB(y)x(A(x)yB(y)xy (A(x)B(y) 例2.3.1 求以下两式的前束范式： （1）xA(x)$x B(x)（2）xy ($z(P(x,z)P(y,z)$z Q(x,y,z)解（1）xA(x)$x B(x)xA(x)$x B(x) $xA(x)$x B(x)$x(A(x)B(x) （2）xy ($z(P(x,z)P(y,z)$z Q(x,y,z) xy ($z(P(x,z)P(y,z)$z Q(x,y,z)xy (z(P(x,z)P(y,z)$z Q(x,y,z)xy (z(P(x,z)P(y,z)$u Q(x,y,u)xy z$u (P(x,z)P(y,z)Q(x,y,u) （或xy z$u (P(x,z)P(y,z)Q(x,y,u)） 据以上讨论可知：定理2.3.6（前束范式定理） 对任意谓词公式都存在与之等值的前束范式.2.4一阶逻辑的推理理论谓词演算是命题演算的深化，因此除了在谓词演算系统中可以使用命题演算系统中的推理规则外，还有它自己独有的推理规则。2.4.1、四个与量词有关的推理规则 (1)全称量词消去规则（UI规则）形式：xA(x)A(c)，其中c为不在A(x)出现过的个体常项； xA(x) A(y)，其中y不在A(x)中约束出现;说明：使用时要全部替代。(2) 全称量词引入规则(UG规则)形式: A(y) xA(x)应用条件: 前提A(y)对于y的任意取值都成立；y不在A(x)中约束出现；(3)存在量词消去规则(EI规则)形式: xA（x） A（c），其中c使A(x)真;应用条件: c不在A(x)出现; 若A(x)中除x外还有其他自由变元时，不能应用本规则； (4)存在量词引入规则(EG规则)形式: A(c) xA(x)，其中c是个体常项；应用条件: 取代c的变元x不在A(c)中出现；注: （1）要正确地使用这四种规则，常常带有各种限制，稍不注意就出错。（2）EI规则与UI规则的作用顺序要特别注意;例2.4.1指出下列