1、1一阶逻辑(谓词逻辑）2内容要点：谓词和个体谓词和个体量词量词一阶逻辑公式一阶逻辑公式置换规则置换规则一阶逻辑等值式一阶逻辑等值式一阶逻辑前束范式一阶逻辑前束范式推理理论推理理论CH4CH4CH4CH4CH4CH4CH5CH5CH5CH5CH5CH5CH5CH53例例：凡偶数都能被：凡偶数都能被2整除，整除，6是偶数。是偶数。所以，所以，6能被能被2整除整除将它们命题符号化：将它们命题符号化：p：凡偶数都能被：凡偶数都能被2整除整除 q：6是偶数是偶数 r：6能被能被2整除整除则推理的形式结构符号化为：则推理的形式结构符号化为：(p q)r由于上式不是重言式，由于上式不是重言式，所以不能由它判
2、断推所以不能由它判断推理的正确性。为了克理的正确性。为了克服命题逻辑的局限性，服命题逻辑的局限性，就应该将简单命题再就应该将简单命题再细分，分析出个体词、细分，分析出个体词、谓词和量词，以期达谓词和量词，以期达到表达出个体与总体到表达出个体与总体的内在联系和数量关的内在联系和数量关系，这就是谓词逻辑。系，这就是谓词逻辑。引引 言言4第五讲第五讲 一阶逻辑一阶逻辑主要内容一、谓词的概念与表示法二、命题函数与量词三、特性谓词的使用四、一阶逻辑合式公式的翻译及解释五、变元的约束5(1)(1)是自然数。是自然数。(2)(2)21世纪末，人类将住在月球。世纪末，人类将住在月球。(3)x+y=y+x(4)
3、只有只有x能被能被2整除，整除，x才能被才能被4整除。整除。x,y的取值范围：复数域的取值范围：复数域a的取值范围：整数域的取值范围：整数域是指所研究对象中可以是指所研究对象中可以独立存在的具体的或抽独立存在的具体的或抽象的客体。象的客体。表示具体或特定的客体表示具体或特定的客体的个体词称作的个体词称作个体常项个体常项；常用常用a,b,c,表示。表示。表示抽象或泛指的客体表示抽象或泛指的客体的个体词称作的个体词称作个体变项个体变项；常用常用x,y,z,表示。表示。个体变项的取值范围为个体变项的取值范围为个个体域体域，个体域可以是有穷，个体域可以是有穷集合，也可以是无穷集合。集合，也可以是无穷集
4、合。全总个体域全总个体域：由宇宙间一切事物组成的域为：由宇宙间一切事物组成的域为全总个体域全总个体域。一、谓词的概念及表示法一、谓词的概念及表示法-个体词个体词6(1)(1)是自然数。是自然数。(2)(2)21世纪末，人类将住在月球。世纪末，人类将住在月球。(3)x 与与 y 具有关系具有关系L(4)只有只有x能被能被2整除，整除，x才能被才能被4整除。整除。谓词：谓词：用来刻划个体用来刻划个体词性质及个体词之间词性质及个体词之间相互关系的词相互关系的词 表示具体性质表示具体性质或关系的谓词或关系的谓词称为称为谓词常项谓词常项谓词变项谓词变项：表示：表示抽抽象的或泛指的象的或泛指的性质性质或关
5、系的谓词或关系的谓词两者都用大写两者都用大写英文字母表示英文字母表示一、谓词的概念及表示法一、谓词的概念及表示法-谓词谓词前面例子中的1元谓词F(x)，G(x)，2元谓词H(x,y)，L(x,y)等都是原子公式。前面例子中的1元谓词F(x)，G(x)，2元谓词H(x,y)，L(x,y)等都是原子公式。施行后的结果不同。(3)DI上特定函数集合fin|i,n 1.在P(x)，P(x,y)等前加上x或x，称变元x被存在量化或全称量化。谓词变项：表示抽象的或泛指的性质或关系的谓词b:4;f(x,y)=x+y;F(x,y):x=y一、谓词的概念及表示法b:5;f(x,y)=x-y;F(x,y):xy定
6、义2 复合命题函数：由一个或几个简单命题函数及逻辑联结词组合的表达式。(2)令F(x)：x是无理数，G(y)：y是有理数，L(x,y)：xy6是偶数。R(x):x住在中国如果事先没有给出个体域，都应以全总个体域为个体域。是指所研究对象中可以独立存在的具体的或抽象的客体。7 谓词命名式谓词命名式 是谓词与个体常元和个体变元结合的表现形式，是谓词与个体常元和个体变元结合的表现形式，有时简称谓词有时简称谓词。规定：小写字母表示个体变元，大写字母表示谓词。规定：小写字母表示个体变元，大写字母表示谓词。例例 “张明是位大学生张明是位大学生”这是命题，作为谓词逻辑的对象，这是命题，作为谓词逻辑的对象，“张
7、明张明”是是个体个体，“是位大是位大学生学生”是是谓词谓词，它刻划了，它刻划了“张明张明”的性质。的性质。设设 P P：是位大学生：是位大学生 a a：张明：张明则则“张明是位大学生张明是位大学生”可表示为可表示为P(a)P(a)，或者写成或者写成P(a)P(a)：张明是位大学生。：张明是位大学生。一、谓词的概念及表示法一、谓词的概念及表示法8一般的一般的用用F(a)表示个体常项表示个体常项a具有性质具有性质F（F是谓词常项或是谓词常项或谓词变项），谓词变项），用用F(x)表示个体变项表示个体变项x具有性质具有性质F。而用而用F(a,b)表示个体常项表示个体常项a,b具有关系具有关系F，用用F
8、(x,y)表示个体变项表示个体变项x,y具有关系具有关系F。一、谓词的概念及表示法一、谓词的概念及表示法9定义定义：一个大写英文字母后边有括号，括号内是若干个客体变元，用以表示客体的属性或者客体之间的关系，称之为谓词。如果括号内有n个客体客体变元变元，称该谓词为n元谓词。例如 S(x):表示x是大学生。一元谓词 G(x,y)：表示 xy。二元谓词 B(x,y,z)：表示x在y与z之间。三元谓词一般地 P(x1,x2,xn)是n元谓词。一、谓词的概念及表示法一、谓词的概念及表示法100元谓词元谓词：有时将不带个体变项的谓词称为：有时将不带个体变项的谓词称为0元谓元谓词，例如到的词，例如到的F(a
9、)，H(a,b)，P(a1,a2,an)等都等都是是0元谓词，当元谓词，当F,H,P为谓词常项时，为谓词常项时，0元谓词为元谓词为命题命题。这样，。这样，命题逻辑中的命题均可表示成命题逻辑中的命题均可表示成0元谓元谓词词，因而可以将命题看成是特殊的谓词。，因而可以将命题看成是特殊的谓词。注意：注意：命题的谓词形式中的个体出现的次序影响命题的谓词形式中的个体出现的次序影响命题的真值，不是随意变动，否则真值会有变化。命题的真值，不是随意变动，否则真值会有变化。一、谓词的概念及表示法一、谓词的概念及表示法11将下列命题用将下列命题用0元谓词符号化，并讨论它们的真值。元谓词符号化，并讨论它们的真值。(
10、1)2是素数且是偶数是素数且是偶数(2)如果如果2大于大于3，则，则2大于大于4 解：(1)设一元谓词F(x)：x是素数；一元谓词G(x)：x是偶数；a：2。则(1)中命题符号化为0元谓词的合取式：F(a)G(a)。(2)设二元谓词L(x,y)：x大于y；a：2；b：3；c：4.命题符号化为L(a,b)L(a,c)一、谓词的概念及表示法一、谓词的概念及表示法12二、命题函数与量词二、命题函数与量词定义定义1 1 简单命题函数：简单命题函数：由一个谓词、一些个体变元组成的表达式。n元谓词P(x1,xn)是n个个体变元的命题函数。是以个体域为定义域，0，1为值域的n元命题函数。定义定义2 2 复合
11、命题函数：复合命题函数：由一个或几个简单命题函数及逻辑联结词组合的表达式。命题逻辑联结词的意义在谓词逻辑中可看作相同解命题逻辑联结词的意义在谓词逻辑中可看作相同解释。命题函数不是命题，取值与个体域也有关。释。命题函数不是命题，取值与个体域也有关。13例如例如S(x)S(x)：x x是大学生，是大学生，x x的个体域为某单位职工；的个体域为某单位职工；那么那么S(x)S(x)可表示：可表示：某单位职工都是大学生，也可表示某单位有一某单位职工都是大学生，也可表示某单位有一些职工是大学生。些职工是大学生。利用利用n n元谓词和它的论域概念，有时还是不能元谓词和它的论域概念，有时还是不能用符号来很准确
12、地表达某些命题。为了避免理解上用符号来很准确地表达某些命题。为了避免理解上的歧义，需要引入用以刻划的歧义，需要引入用以刻划“所有的所有的”、“存在一存在一些些”等表示不同数量的词，即量词，其定义如下：等表示不同数量的词，即量词，其定义如下：量词量词14量词定义量词定义量词量词表示数量的词表示数量的词 全称量词全称量词 x:对个体域中所有的对个体域中所有的x 如如,xF(x)表示个体域中所有的表示个体域中所有的x具有性质具有性质F x yG(x,y)表示个体域中所有的表示个体域中所有的x和和y有关系有关系G 存在量词存在量词 x:个体域中有一个个体域中有一个x 如如,xF(x)表示个体域中有一个
13、表示个体域中有一个x具有性质具有性质F x yG(x,y)表示个体域中存在一个表示个体域中存在一个x使得对每使得对每一个一个y,x和和y有关系有关系G15 在P(x)，P(x,y)等前加上x或x，称变元x被存在量化或全称量化。将谓词将谓词F(x)F(x)变成命题有两种方法变成命题有两种方法a.将x取定值 例：F(x)：x是质数，那么F(4)是命题（假）b.将谓词量化 例：1).xF(x)F(x)：任意的x是质数 2).y(yy+1)3).y(yy。(2)21世纪末，人类将住在月球。施行后的结果不同。xyG(x,y)表示个体域中存在一个x使得对每一个y,x和y有关系Gp：凡偶数都能被2整除用F(
14、x,y)表示个体变项x,y具有关系F。xyG(x,y)表示个体域中所有的x和y有关系G24实例实例3例例3 在一阶逻辑中将下面命题符号化在一阶逻辑中将下面命题符号化 (1)正数都大于负数正数都大于负数 (2)有的无理数大于有的有理数有的无理数大于有的有理数解解 注意：题目中没给个体域，一律用全总个体域注意：题目中没给个体域，一律用全总个体域 (1)令令F(x)：x为正数，为正数，G(y)：y为负数为负数,L(x,y)：xy x(F(x)y(G(y)L(x,y)或者或者 x y(F(x)G(y)L(x,y)(2)令令F(x)：x是无理数，是无理数，G(y)：y是有理数，是有理数，L(x,y)：x
15、y x(F(x)y(G(y)L(x,y)或者或者 x y(F(x)G(y)L(x,y)25原子公式：原子公式：不出现命题联结词和量词的谓词命名式，P(X1,X2Xn)称为谓词演算的原子公式。前面例子中的前面例子中的1元谓词元谓词F(x)，G(x)，2元谓词元谓词H(x,y)，L(x,y)等都是原子公式。等都是原子公式。四、一阶逻辑公式翻译及解释四、一阶逻辑公式翻译及解释26定义定义4 合式公式合式公式定义如下：定义如下：(1)原子公式是合式公式.(2)若A是合式公式，则(A)也是合式公式(3)若A,B是合式公式，则(AB),(AB),(AB),(AB)也是合式公式(4)若A是合式公式，则xA,
16、xA也是合式公式(5)只有有限次地应用(1)(4)形成的符号串才是合式公式.合式公式简称公式公式 如如,F(x),F(x)G(x,y),x(F(x)G(x)等都是合式公式等都是合式公式谓词公式谓词公式27定义 一个解释 I 由下列4部分组成：(1)非空个体域DI。(2)DI中一些特定元素的集合a1,a2,ai,.(3)DI上特定函数集合fin|i,n 1.(4)DI上特定谓词的集合Fin|i,n 1.所谓一个解释不外乎指定个体域、个体域中一些特定的元素、特定的函数和谓词等。谓词公式的解释谓词公式的解释28解释解释(举例举例)F(f(a,a),b)解释解释1：个体域是全体自然数个体域是全体自然数
17、;a:2;b:4;f(x,y)=x+y;F(x,y):x=y 原公式解释成原公式解释成:“2+2=4”。解释解释2：个体域是全体实数个体域是全体实数;a:3;b:5;f(x,y)=x-y;F(x,y):xy 原公式解释成原公式解释成:“3-35”。29(1)量词的辖域量词的辖域定义定义:量词的辖域量词的辖域是邻接量词之后的最小子公式，是邻接量词之后的最小子公式，故除非辖域是个原子公式，否则应在该子公式的两故除非辖域是个原子公式，否则应在该子公式的两端有括号。端有括号。例：例：XP(X)Q(X)XP(X)Q(X)X X的辖域是的辖域是P(X)P(X)X(P(X,Y)Q(XX(P(X,Y)Q(X，
18、Y)Y)P(Y,Z)P(Y,Z)X X的辖域是的辖域是P(XP(X，Y)Q(XY)Q(X，Y)Y)变元的约束变元的约束30定义：定义：在量词在量词 X X，X X辖域内变元辖域内变元X X的一切出现叫的一切出现叫约约束出现束出现，称这样的，称这样的X X为为约束变元；约束变元；变元的非约束出变元的非约束出现称为现称为自由出现自由出现,称这样的变元为称这样的变元为自由变元自由变元。例：例：指出下列谓词公式中的自由变元和约束变元，指出下列谓词公式中的自由变元和约束变元，并指明量词的辖域。并指明量词的辖域。X(P(X)R(X)XP(X)Q(X)解：表达式中的X(P(X)R(X)中X的辖域是 P(X)
19、R(X),其中的X是约束出现，Q(X)中的X是自由变元。变元的约束变元的约束31 注意：注意：在一个公式中，一个变元既可以约束出在一个公式中，一个变元既可以约束出现，又可以自由出现。为避免混淆可采用下面两个现，又可以自由出现。为避免混淆可采用下面两个规则：规则：约束约束出现出现改名规则，将量词辖域中某个约束出现改名规则，将量词辖域中某个约束出现的个体变元及相应指导变元，改成本辖域中未曾出的个体变元及相应指导变元，改成本辖域中未曾出现过的个体变元，其余不变。现过的个体变元，其余不变。例例 x F(x)G(x,y)(换名规则换名规则,将约束出现将约束出现 zF(z)G(x,y)的的x改成改成z)约
20、束变元改名规则约束变元改名规则32 对自由变元改名称为自由变元代入规则，对自由变元改名称为自由变元代入规则，对某自由出现的个体变元可用个体常元或用与原对某自由出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，子公式中所有个体变元不同的个体变元去代入，且处处代入。且处处代入。例例 x F(x)x F(x)G(x,y)(G(x,y)(代替规则代替规则,将自由出现将自由出现 x x F(x)G(z,y)F(x)G(z,y)的的x x改成改成z)z)自由变元代入规则自由变元代入规则33改名规则与代入规则的共同点都是不能改变约束关系，而不同点是：施行的对象不同。改名是对约束变元
21、施行，代入是对自由变元施行。施行的范围不同。改名可以只对公式中一个量词及其辖域内施行，即只对公式的一个子公式施行；而代入必须对整个公式同一个自由变元的所有自由出现同时施行，即必须对整个公式施行。34 施行后的结果不同。改名后，公式含义不变，因为约束变元只改名为另一个个体变元，约束关系不改变。约束变元不能改名为个体常元；代入，不仅可用另一个个体变元进行代入，并且也可用个体常元去代入，从而使公式由具有普遍意义变为仅对该个体常元有意义，即公式的含义改变了。35闭公式定义：定义：设设A是任意的公式，若是任意的公式，若A中不含自由出现的个中不含自由出现的个体变项，则称体变项，则称A为为封闭的公式封闭的公式，简称，简称闭式闭式。例如，例如，x(F(x)G(x)，x y(F(x)G(x,y)都都是闭式，而是闭式，而 x(F(x)G(x,y)，z y L(x,y,z)都都不是闭式。不是闭式。要想使含有要想使含有r(r1)个自由出现个体变项的公式变个自由出现个体变项的公式变成闭式，至少要加上成闭式，至少要加上r个量词个量词
