离散数学文档第二章

第二章第二章 一阶逻辑一阶逻辑由上一章我们知道，命题逻辑可以形式化地描述一些自然语言中的逻辑思维，也能够用形式化的方法进行一些逻辑推理。但命题逻辑以原子命题作为最小的研究单位，不对原子命题的内部结构做深入研究。然而，这无论是在数学中还是在计算机科学中，都是不够的。例如，下列推理是人所共知的：所有的人都会呼吸所有的人都会呼吸,他是人他是人,所以他会呼吸所以他会呼吸.但是，命题演算却无法反映上述推理，因为前提和结论都只能表示为原子命题，例如表示为 p，q，r。在命题演算系统中,无法由前提 p, q 推出结论 r, 结论 r 也根本不是前提p，q 的逻辑结果。这三个命题中涉及两个概念，它们表示事物的性质：“是人” ， “会呼吸” ，我们称之为谓词谓词。它们还涉及两种主体：“所有的人” ， “他” ，我们称之为个体个体。前者表示一类个体的全部，这里使用了数量词“所有” ，我们称之为量词量词。只有当这些细节都被清楚地表示出来，同时建立起它们之间逻辑关系的形式描述，那么刻划类似上述本章引例的推理才是可能的。谓词演算及其形式系统正是以此为目的而建立的。一阶逻辑研究的基本内容是：原子命题的个体词、谓词和量词，研究它们的形式结构和逻辑关系、正确的推理形式和规则。2.12.1 一阶逻辑的基本概念一阶逻辑的基本概念2.1.12.1.1 个体词、谓词、量词个体词、谓词、量词2.1.1.1 个体词与谓词定义定义 2.1.12.1.1 在原子命题中，所描述的对象称为个体；用以描述个体的性质或个体间关系的部分，称为谓词。个体：原子命题中的主语部分；个体常元：表示特定的个体，以 a，b，c，(或带下标)表示;个体变元: 表示个体的变元，以 x，y，z，(或带下标)表示;个体域：个体变元的取值范围；谓词: 原子命题中的谓语(或表语)部分，常用大写字母 P，Q，R，(或带下标)表示;定义定义 2.1.22.1.2 一个原子命题的谓词形式为：谓词符号(个体常元 1，个体常元 2，)。例例 2.1.12.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.32.1.3 (1) 全称量词符，表示“对所有的，每一个，一切，对任何一个” 。全称量词的形式为x，x 称为指导变元；(2) 存在量词符，指代“ 存在一些，至少有一个，对于一些，某个” 。存在量词形式为x，x 为指导变元；说明：说明：(1) 个体域对命题的真值有影响;(2) 若非特别指明，个体变元的个体域总是 U；(5) 当个体域为 U 时，常需用一个特性谓词特性谓词 P(x)P(x)来限制个体变元 x 的取值范围。2.1.22.1.2 举例举例例例 2.1.22.1.2 设 D 为实数域，E(x,y)表示 D 上关系“x = y” ，L(x,y) 表示:x 0)例例 2.1.52.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.22.2 一阶逻辑合式公式及其解释一阶逻辑合式公式及其解释2.2.12.2.1 一阶逻辑合式一阶逻辑合式定义定义 2.2.12.2.1 项可以按如下方式递归定义而成:(1)个体变元和常元都是项;(2)若 f 是 n 元函数，且 t1，t2，tn是项，则 f(t1，t2，tn)也是项;(3)只有有限次经过使用(1)和(2)所得到的才是项。注:项起到一个个体的作用。定义定义 2.2.22.2.2 若 R(x1，x2，xn)是 n 元谓词，t1，t2，tn都是项，则称R(t1，t2，tn)为原子公式。定义定义 2.2.32.2.3 合式公式可由如下方式递归定义：(1)原子公式是合式公式；(2)若 A，B 是公式，则(A)，(AB)，(AB)，(AB)，(AB)都是合式公式；(3)若 A 为合式公式，x 为 A 中的个体变元，则xA，xA，!xA 都为合式公式；(4)仅由有限次(2)，(3)得到的才是合式公式。定义定义 2.2.42.2.4 在一个谓词公式 A 中，形如xB(x)、xB(x)的部分称为 A 的约束部分，B(x)为相应量词的辖域；在辖域中，x 的所有出现称为 x 的约束出现，x 称为约束变元。若 x 的出现不是约束出现，则称 x 为自由变元。注(1) : 若量词后有括号，则括号内的子公式就是该量词的辖域;(2) : 若量词后无括号，则与量词紧邻的子公式为该量词的辖域;(3) : 自由变元可以用个体域中的特定个体替代，而约束变元则不能用个体域中的特定个体替代。例例 2.2.12.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.22.2.2分别对个体域 D1=3，4，把 P(x)解释为“x 是质数” ，a=3,讨论 P(a)x P(x) 的真值。P(a)x P(x)1111)(ap定义定义. .6.6 若公式 A 在每一解释 I 下均真，那么称 A 为永真式。若公式 A 在每一解释 I 下均假，那么称 A 为矛盾式。若公式 A 存在成真解释，则称 A 为可满足式。说明：说明：对于一阶逻辑公式判断其类型至今没有一般的方法。定义定义. .7.7 设 A0是含命题变项 p1,p2,pn的命题公式，A1,A2,An是 n 个谓词公式，用Ai（1in）处处代替 pi所得公式 A 叫公式 A0的代换实例。 定理定理. .1.1 永真式的代换实例都是永真式；矛盾式的代换实例都是矛盾式。例例 2.2.32.2.3因为，所以是永真式)(qpp（1）)()()(yyGxxFxxF（2）)()()(yyGxFxF都是永真式。对于可满足式可满足式通过举例子的方法说明。例例 2.2.42.2.4是非矛盾式的可满足式。在自然数集中，),(),(yxyFxyxyFx及，两种解释一个使其为真一个使其为假。yxyxf：表示),(yxyxf：表示),(2.32.3 一阶逻辑等值式一阶逻辑等值式2.3.12.3.1 一阶逻辑等值式一阶逻辑等值式定义定义 2.3.12.3.1 设 A，B 是两个一阶逻辑公式，若 AB 是永真式，即在所有的解释下 A 和 B的真值对应相同，则称 A 与 B 是等值的，记作 AB，并称 AB 为逻辑恒等式。例例 2.3.12.3.1)()()(xxFxxFxxF说明：说明：由于永真式的代换实例是永真式，因而，由第一章的命题逻辑等值式可派生出许多一阶逻辑等值式。定理定理.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.3.2 量词否定等值式量词否定等值式（1）)()(xFxxxF（2）)()(xFxxxF定理定理 2.3.32.3.3 量词辖域扩张与收缩等值式当公式 B 中不含自由变元 x 时，第一组 (1)x A(x)Bx (A(x)B)(2)x A(x)Bx (A(x)B)(3)x A(x)Bx (A(x)B)(4)x A(x)Bx (A(x)B)第二组 (5)x(BA(x) Bx A(x)(6) x(A(x) B) x A(x)B(7) x(BA(x) Bx A(x)(8) x(A(x) B) x A(x)B定理定理 2.3.42.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.42.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.52.3.5（换名规则）（换名规则）设 A 是一个公式，将 A 中某量词辖域中的某约束变项约束变项及相应的指导变元，改成该量词辖域中未曾出现的某个个体变项，公式的其余部分不变，所得公式记为，则。AAA定理定理 2.3.62.3.6（代替规则）（代替规则）设 A 是一个公式，将 A 中自由出现的某变项自由出现的某变项，都改成该量词辖域中未曾出现的某个个体变项，公式的其余部分不变，所得公式记为，则。AAA2.3.22.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 zu (P(x,z)P(y,z)Q(x,y,u)（或xy zu (P(x,z)P(y,z)Q(x,y,u)）据以上讨论可知：定理定理 2.3.62.3.6（前束范式定理）（前束范