第二章一阶逻辑【教学目的】1.深刻理解个体、谓词、量词的概念。2.深刻理解原子、公式、解释的概念。3.掌握用解释的方法证明等价式和蕴涵式。4.熟练掌握谓词演算的形式推理方法。【教学重点】：个体、谓词、量词的概念；用解释的方法证明等价式和蕴涵式；谓词演算的形式推理方法【教学难点】：解释的方法证明等价式和蕴涵式；谓词演算的形式推理方法【教学方法】：讲授【时数】：理论课6学时【教学内容】2.1一阶逻辑基本概念在一阶逻辑中，简单命题被分解成个体词和谓词两部分。所谓个体词是指可以独立存在的客体，而调词是用来刻画个体词的性质或个体词之间关系的词。表示具体的或特定的个体的词称为个体常项，一般用小写的英文字母a，b,c，表示。表示抽象的，或泛指的个体的词称为个体变项，常用小写英文字母x，y，z，表示。个体变项的取值范围称为个体域（或论域）。称表示具体性质或关系的谓词为谓词常项，用大写英文字母F，G,H，表示；而表示抽象的或泛指的谓词称为谓词变项。，也用大写英文字母F，G，H，·表示。个体变项x具有性质F，记作F（x）。个体变项x，y具有关系L，记作L(x，y)，下文中常称这种个体变项和谓词的联合体F(x）、L（x,y）等为谓词。在谓词中包含的个体词数称为元数。含n（n>=1）个个体词的谓词称为n元谓词。一元谓词是表示个体词性质的。n(n>=2)元谓词是表示个体词之间关系的。一般说来，用P(xi,X2，",x)表示n元谓词，它是以个体变项的个体域为定义域，以[0，1)为值域的n元函数，在这里Ⅱ个个体变项的顺序不能随意改动。有时将不带个体变项的谓词称为0元谓词。命题逻辑中的简单命题都可以用0元谓词表示，因而可将命题看成谓词的特殊情况。命题逻辑中的联结词在一阶逻辑中均可应用。例2.1将下列命题用0元谓词符号化（1）2是素数且是偶数以上给出的两个命题中，除了有个体词和谓词外，还有表示数量的词，称表示数量的词为量词。量词有两种：1.全称量词对应日常语言中的“一切”，“所有的”，“任意的”等词，用符号“”表示。Vx表示对个体域里的所有个体。xF（x）表示个体域里的所有个体都有性质F。2.存在量词对应日常生活中的“存在着”，“有一个”，“至少有一个”等词，用符号“3”表示。3x表示存在个体域里的个体。日xF(x)表示存在着个体域中的个体具有性质F。在使用量词时，应注意以下6点：（1）在不同的个体域中，命题符号化的形式可能不一样；(2）女如果事先没有给出个体域，都应以全总个体域为个体域：(3）在引入特征谓词后，使用全称量词与存在量词符号化的形式是不同的：
第二章 一阶逻辑 【教学目的】： 1.深刻理解个体、谓词、量词的概念。 2.深刻理解原子、公式、解释的概念。 3.掌握用解释的方法证明等价式和蕴涵式。 4.熟练掌握谓词演算的形式推理方法。 【教学重点】：个体、谓词、量词的概念；用解释的方法证明等价式和蕴涵式；谓词演算的 形式推理方法 【教学难点】：解释的方法证明等价式和蕴涵式；谓词演算的形式推理方法 【教学方法】：讲授 【时数】：理论课 6 学时 【教学内容】： 2.1 一阶逻辑基本概念 在一阶逻辑中，简单命题被分解成个体词和谓词两部分。所谓个体词是指可以独立存在 的客体，而谓词是用来刻画个体词的性质或个体词之间关系的词。 表示具体的或特定的个体的词称为个体常项，一般用小写的英文字母 a,b,c,.表示。 表示抽象的，或泛指的个体的词称为个体变项，常用小写英文字母 x,y,z,.表示。个体变 项的取值范围称为个体域（或论域）。 称表示具体性质或关系的谓词为谓词常项，用大写英文字母 F,G,H,.表示；而表示抽 象的或泛指的谓词称为谓词变项。，也用大写英文字母 F,G,H,.表示。个体变项 x 具有性质 F，记作 F（x）。个体变项 x,y 具有关系 L，记作 L(x,y)，下文中常称这种个体变项和谓词 的联合体 F(x)、L（x,y）等为谓词。 在谓词中包含的个体词数称为元数。含 n（n>=1）个个体词的谓词称为 n 元谓词。一元 谓词是表示个体词性质的。n(n>=2)元谓词是表示个体词之间关系的。一般说 来，用 P(x1,x2,.,xn)表示 n 元谓词，它是以个体变项的个体域为定义域，以{0，1}为值域的 n 元 函数，在这里 n 个个体变项的顺序不能随意改动。有时将不带个体变项的谓词称为 0 元谓 词。命题逻辑中的简单命题都可以用 0 元谓词表示，因而可将命题看成谓词的特殊情况。命 题逻辑中的联结词在一阶逻辑中均可应用。 例 2.1 将下列命题用 0 元谓词符号化 （1）2 是素数且是偶数 以上给出的两个命题中，除了有个体词和谓词外，还有表示数量的词，称表示数量的词 为量词。量词有两种： 1. 全称量词 对应日常语言中的“一切”,“所有的”,“任意的”等词，用符号“” 表示。x 表示对个体域里的所有个体。xF(x)表示个体域里的所有个体都有性质 F。 2. 存在量词 对应日常生活中的“存在着”，“有一个”，“至少有一个”等词，用符号 “”表示。x 表示存在个体域里的个体。xF(x)表示存在着个体域中的个体具有 性质 F。 在使用量词时，应注意以下 6 点： （1） 在不同的个体域中，命题符号化的形式可能不一样； （2） 如果事先没有给出个体域，都应以全总个体域为个体域； （3） 在引入特征谓词后，使用 全称量词与存在量词符号化的形式是不同的；
(4)个体域和谓词的含义确定之后，n元谓词要转化为命题至少需要n个谓词：(5)当个体域为有限集时，如D={ai，az,"，an)，由量词的定义可以看出，对于任意的谓词A（x），都有AVxA(x)A(ai)A(az)*A(a.):②xA(x)A(a) VA(az)V...VA(a.);这实际上是将一阶逻辑中命题公式转化为命题逻辑中的命题公式问题。(6）多个量词同时出现时，不能随意颠倒它们的顺序，颠倒后会改变原命题的含义。例2.2在一阶逻辑中将下面命题符号化例2.3将下列命题符号化例2.4在一阶逻辑中将下面命题符号化例2.5在一阶逻辑中将下面命题符号化2.2一阶逻辑合式公式及解释本书中使用的字母表定义2.1字母表如下：(1)个体常项：a,b,c,.,ai,bi,c,….,i>=l（2）个体变项：x,y,z,",Xi,yi,zi,",i>=l;(3）函数符号：f,g,h,,fi,g,hi,"",i>=l;(4)谓词符号：F,G,H,",Fi,G,H，",i>=l(5）量词符号：V，3；（6）连接词符：（7）括号和逗号：（，），“。定义2.2项的递归定义如下：（1）个体常项和变项是项；（2）若Φ（x,X2，…x）是任意n元函数，t，t2，…，t是项，则Φ（x,x2,，x）也是项；（3）只有有限次地使用（1、（2）生成的符号串才是项。Φ这里表示任意的函数，可以看成表示函数的模式，或称为元语言符号。所谓元语言是用来描述对象语言的语言，而对象语言是用来描述研究对象的语言。定义2.3设R(xi,Xz,*,x）是任意的n元谓词，ti,t2，""，t，是项，则称R(ti,tz,""，t)为原子公式。定义中R是元语言符号。定义2.4合式公式的定义如下：(1)原子公式是合式公式：(2）若A是合式公式，则（A）也是合式公式：(3)若A、B是合式公式，则（A^B）、（AVB）（A-→B）（A+→B）也是合式公式：(4)若A是合式公式，则VxA、3xA也是合式公式；(5）只有有限次地应用（1）～（4）构成的符号串才是合式公式。定义2.5在合式公式VxA和xA中，称x为指导变项，称A为相应量词辖域。在辖域中，X的所有出现称为约束出现（即x受相应量词指导变项的约束），A中不是约束出现的其他变项的出现称为自由出现。例2.6指出下列各合式公式中的指导变项、量词的辖域、个体变项的自由出现和约定出现。(1)(2)(3)
（4） 个体域和谓词的含义确定之后，n 元谓词要转化为命题至少需要 n 个谓词； （5） 当个体域为有限集时，如 D={a1,a2,.,an}，由量词的定义可以看出，对于任意的 谓词 A（x）,都有 A ①xA(x)A(a1)∧A(a2)∧.∧A(an)； ②xA(x)A(a1)∨A(a2)∨.∨A(an)； 这实际上是将一阶逻辑中命题公式转化为命题逻辑中的命题公式问题。 （6） 多个量词同时出现时，不能随意颠倒它们的顺序，颠倒后会改变原命题的含义。 例 2.2 在一阶逻辑中将下面命题符号化 例 2.3 将下列命题符号化 例 2.4 在一阶逻辑中将下面命题符号化 例 2.5 在一阶逻辑中将下面命题符号化 2.2 一阶逻辑合式公式及解释 本书中使用的字母表 定义 2.1 字母表如下： （1）个体常项：a,b,c,.,ai,bi,ci,.,i>=1； （2）个体变项：x,y,z,.,xi,yi,zi,.,i>=1； (3) 函数符号：f,g,h,.,fi,gi,hi,.,i>=1； (4) 谓词符号：F,G,H,.,Fi,Gi,Hi,.,i>=1； (5) 量词符号：，； （6）连接词符： （7）括号和逗号：（，），‘。 定义 2.2 项的递归定义如下： （1） 个体常项和变项是项； （2） 若φ(x1,x2,.,xn)是任意 n 元函数，t1,t2,.,tn 是项，则φ(x1,x2,.,xn)也是项； （3） 只有有限次地使用（1）、（2）生成的符号串才是项。 φ这里表示任意的函数，可以看成表示函数的模式，或称为元语言符号。所谓元语言是 用来描述对象语言的语言，而对象语言是用来描述研究对象的语言。 定义 2.3 设 R(x1,x2,.,xn)是任意的 n 元谓词，t1,t2,.,tn 是项，则称 R(t1,t2,.,tn)为原 子公式。 定义中 R 是元语言符号。 定义 2.4 合式公式的定义如下： （1） 原子公式是合式公式； （2） 若 A 是合式公式，则（┓A）也是合式公式； （3） 若 A、B 是合式公式，则（A∧B）、（A∨B）（A→B）（A←→B）也是合式公式； （4） 若 A 是合式公式，则xA、xA 也是合式公式； （5） 只有有限次地应用（1）～（4）构成的符号串才是合式公式。 定义 2.5 在合式公式xA 和xA 中，称 x 为指导变项，称 A 为相应量词辖域。在辖域中，x 的所有出现称为约束出现（即 x 受相应量词指导变项的约束），A 中不是约束出现的其他变 项的出现称为自由出现。 例 2.6 指出下列各合式公式中的指导变项、量词的辖域、个体变项的自由出现和约定出现。 （1） （2） （3）
定义2.6设A为任一公式，若A中无自由出现的个体变项，则称A是封闭的，则称A是封闭的合式公式，简称闭式。换名规则将量词辖域中某个约束出现的个体变项及对应的指导变项，改成公式中未曾出现过的个体变项符号。公式中其余部分不变代替规则对某自由出现的个体变项用与原公式中所有变项符号不同的变项符号去代替，且处处代替。定义2.7一个解释I由下面4部分组成（1）非空个体域D；(2）D中一部分特定元素；(3)D上一些特定的函数；(4)D上一些特定的谓词在使用一个解释I解释一个公式A时，将A中的个体常项用I中特定常项代替，函数和谓词用I中的特定函数和谓词代替。例2.7给定解释I如下：在解释I下，求下列各式的真值。例2.8给定解释N如下：在解释N下，下面哪些公式为真？哪些公式为假？定义2.8设A为一公式（谓词公式），如果A在任何解释下都是真的，则称A为逻辑有效式（或称永真式）：如果A在任何解释下都是假的，则称A是矛盾式（或称永假式）：若至少存在一个解释使A为真，则称A是可满足式。定义2.9设A是命题变项pi,P2，",pa的命题公式，Ai，Az，,A是n个谓词公式，用A（1K<=i<=n）处处代换pi，所得公式A称为Ao的代换实例。例2.9判断下列公式中哪些是逻辑有效式？哪些是矛盾式？2.3一阶逻辑等值式定义2.10设A、B若A<->B为逻辑有效式，则称A与B是等值的，记作A台B，称AB为等值式。定理2.1量词否定等值式(1)(2)其中，A（x）是任意的公式。定理2.2量词辖域收缩与扩张等值式定理2.3量词分配等值式例2.10证明定理2.4下面两等值式成立：定义2.11设A为一谓词公式，如果A具有如下形式：Q1x1Q2x2-QkxkB,则称A是前束范式。其中每个Qi（1<=i<=k）为，B为不含量词的谓词公式。例2.11求下列公式的前束范式
定义 2.6 设 A 为任一公式，若 A 中无自由出现的个体变项，则称 A 是封闭的，则称 A 是封 闭的合式公式，简称闭式。 换名规则 将量词辖域中某个约束出现的个体变项及对应的指导变项，改成公式中未曾出 现过的个体变项符号。公式中其余部分不变。 代替规则 对某自由出现的个体变项用与原公式中所有变项符号不同的变项符号去代替， 且处处代替。 定义 2.7 一个解释 I 由下面 4 部分组成 （1） 非空个体域 D; （2） D 中一部分特定元素； （3） D 上一些特定的函数； （4） D 上一些特定的谓词 在使用一个解释 I 解释一个公式 A 时，将 A 中的个体常项用 I 中特定常项代替，函数 和谓词用 I 中的特定函数和谓词代替。 例 2.7 给定解释 I 如下： 在解释 I 下，求下列各式的真值。 例 2.8 给定解释 N 如下： 在解释 N 下，下面哪些公式为真？哪些公式为假？ 定义 2.8 设 A 为一公式（谓词公式），如果 A 在任何解释下都是真的，则称 A 为逻辑有效式 （或称永真式）；如果 A 在任何解释下都是假的，则称 A 是矛盾式（或称永假式）；若至少存 在一个解释使 A 为真，则称 A 是可满足式。 定义 2.9 设 A0 是命题变项 p1,p2,.,pn 的命题公式，A1,A2,.,An 是 n 个谓词公式，用 Ai （1<=i<=n）处处代换 pi，所得公式 A 称为 A0 的代换实例。 例 2.9 判断下列公式中哪些是逻辑有效式？哪些是矛盾式？ 2.3 一阶逻辑等值式 定义 2.10 设 A、B 若 A<->B 为逻辑有效式，则称 A 与 B 是等值的，记作 AB，称 AB 为 等值式。 定理 2.1 量词否定等值式 （1） （2） 其中，A（x）是任意的公式。 定理 2.2 量词辖域收缩与扩张等值式 定理 2.3 量词分配等值式 例 2.10 证明 定理 2.4 下面两等值式成立： 定义 2.11 设 A 为一谓词公式，如果 A 具有如下形式： Q1x1Q2x2.QkxkB, 则称 A 是前束范式。其中每个 Qi(1<=i<=k)为，B 为不含量词的谓词公式。 例 2.11 求下列公式的前束范式