《谓词逻辑基本概念最全资料课件.ppt》由会员分享，可在线阅读，更多相关《谓词逻辑基本概念最全资料课件.ppt（36页珍藏版）》请在三一办公上搜索。
1、1,一阶逻辑(谓词逻辑）,2,内容要点：,置换规则,3,例：凡偶数都能被2整除，6是偶数。所以，6能被2整除将它们命题符号化：p：凡偶数都能被2整除 q：6是偶数 r：6能被2整除则推理的形式结构符号化为：(p q)r,由于上式不是重言式，所以不能由它判断推理的正确性。为了克服命题逻辑的局限性，就应该将简单命题再细分，分析出个体词、谓词和量词，以期达到表达出个体与总体的内在联系和数量关系，这就是谓词逻辑。,引 言,4,第五讲 一阶逻辑,主要内容一、谓词的概念与表示法二、命题函数与量词三、特性谓词的使用四、一阶逻辑合式公式的翻译及解释五、变元的约束,5,(1)是自然数。(2)21世纪末，人类将住
2、在月球。(3)x+y=y+x(4)只有x能被2整除，x才能被4整除。,x,y的取值范围：复数域a的取值范围：整数域,是指所研究对象中可以独立存在的具体的或抽象的客体。,表示具体或特定的客体的个体词称作个体常项；常用a,b,c,表示。,表示抽象或泛指的客体的个体词称作个体变项；常用x,y,z,表示。,全总个体域：由宇宙间一切事物组成的域为全总个体域。,一、谓词的概念及表示法-个体词,6,(1)是自然数。(2)21世纪末，人类将住在月球。(3)x 与 y 具有关系L(4)只有x能被2整除，x才能被4整除。,谓词：用来刻划个体词性质及个体词之间相互关系的词,一、谓词的概念及表示法-谓词,前面例子中的
3、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定义2 复合命题函数：由一个或几个简单命题函数及逻辑联结词组合的表达式。(2)令F(x)：x是无理数，G(y)：y是有理数，L(x,y)
4、：xy6是偶数。R(x):x住在中国如果事先没有给出个体域，都应以全总个体域为个体域。是指所研究对象中可以独立存在的具体的或抽象的客体。,7,谓词命名式 是谓词与个体常元和个体变元结合的表现形式，有时简称谓词。规定：小写字母表示个体变元，大写字母表示谓词。例“张明是位大学生”这是命题，作为谓词逻辑的对象，“张明”是个体，“是位大学生”是谓词，它刻划了“张明”的性质。设 P：是位大学生 a：张明则“张明是位大学生”可表示为P(a)，或者写成P(a)：张明是位大学生。,一、谓词的概念及表示法,8,一般的用F(a)表示个体常项a具有性质F（F是谓词常项或谓词变项），用F(x)表示个体变项x具有性质F
5、。而用F(a,b)表示个体常项a,b具有关系F，用F(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元谓词。,一、谓词的概念及表示法,10,0元谓词：有时将不带个体变项的谓词称为0元谓词，例如到的F(a)，H(a,b)，P(a1,a2,an)等都是0元谓词，当F,
6、H,P为谓词常项时，0元谓词为命题。这样，命题逻辑中的命题均可表示成0元谓词，因而可以将命题看成是特殊的谓词。,注意：命题的谓词形式中的个体出现的次序影响命题的真值，不是随意变动，否则真值会有变化。,一、谓词的概念及表示法,11,将下列命题用0元谓词符号化，并讨论它们的真值。(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,二、
7、命题函数与量词,定义1 简单命题函数：由一个谓词、一些个体变元组成的表达式。n元谓词P(x1,xn)是n个个体变元的命题函数。是以个体域为定义域，0，1为值域的n元命题函数。,定义2 复合命题函数：由一个或几个简单命题函数及逻辑联结词组合的表达式。命题逻辑联结词的意义在谓词逻辑中可看作相同解释。命题函数不是命题，取值与个体域也有关。,13,例如S(x)：x是大学生，x的个体域为某单位职工；那么S(x)可表示：某单位职工都是大学生，也可表示某单位有一些职工是大学生。利用n元谓词和它的论域概念，有时还是不能用符号来很准确地表达某些命题。为了避免理解上的歧义，需要引入用以刻划“所有的”、“存在一些”
8、等表示不同数量的词，即量词，其定义如下：,量词,14,量词定义,量词表示数量的词 全称量词 x:对个体域中所有的x 如,xF(x)表示个体域中所有的x具有性质F xyG(x,y)表示个体域中所有的x和y有关系G 存在量词 x:个体域中有一个x 如,xF(x)表示个体域中有一个x具有性质F xyG(x,y)表示个体域中存在一个x使得对每一个y,x和y有关系G,15,在P(x)，P(x,y)等前加上x或x，称变元x被存在量化或全称量化。,将谓词F(x)变成命题有两种方法a.将x取定值 例：F(x)：x是质数，那么F(4)是命题（假）b.将谓词量化 例：1).xF(x)F(x)：任意的x是质数 2)
9、.y(yy+1)3).y(yy+1),量词作用,16,特别注意：一个谓词中所有个体变元都量化了，该谓词才能变成命题。这如同数学中的函数f(x)，的值是不确定的，但 可确定其值。,量词作用,17,(1)分析命题中表示性质和关系的谓词，分别符号化为一元和n（n 2）元谓词。(2)根据命题的实际意义选用或。(3)在不同的个体域中，命题符号化的形式可能不一样。如果事先没有给出个体域，都应以全总个体域为个体域。(4)多个量词同时出现时，不能随意颠倒它们的顺序，颠倒后会改变原命题的含义。,量词使用注意事项,18,(5)当个体域为有限集时，如D=a1,a2,an，由量词的意义可以看出，对于任意的谓词A(x)
10、，都有 x A(x)A(a1)A(a2)A(an)x A(x)A(a1)A(a2)A(an)这实际上是将谓词逻辑中命题公式转化为命题逻辑中的命题公式问题。,量词使用注意事项,19,三、特性谓词的使用,特性谓词：用P(x)来限制个体变元的取值范围。如在全总个体域（全总论域）中，用M(x)表示x是人；用R(x)表示x是实数等。,20,1.设个体域为D=0,1,2,10,将下列命题符号化：(1)D中所有元素都是整数；(2)D中有的元素是偶数；(3)D中所有的偶数都能被2整除；(4)D中有的偶数是4的倍数。,举例,xF(x),其中F(x)：x是整数,xG(x),其中G(x)：x是偶数,x(G(x)H(
11、x),其中G(x):x是偶数;H(x):x能被2整除,x(G(x)R(x),其中G(x):x是偶数;R(x):x是4的倍数,21,2.设个体域为D=x|x为人，将下列命题符号化：(1)人都生活在地球上；(2)有的人长着黑头发；(3)中国人都用筷子吃饭；(4)有的中国人不住在中国；,xF(x),其中F(x)：x生活在地球上,xG(x),其中G(x)：x长着黑头发,x(H(x)I(x),其中H(x):x是中国人；I(x)：x用筷子吃饭,x(H(x)R(x),其中H(x):x是中国人；R(x):x住在中国,举例,22,3.用量词、谓词来表述命题。(1)凡是人都是要死的。(2)某些实数是有理数。,x(
12、F(x)H(x),其中F(x):x是人；H(x):是要死的；,x(G(x)Q(x),其中G(x):x是实数；H(x):是有理数；,举例,23,特性谓词加入规则,（1）对全称量词，特性量词作为蕴含前件加入。（2）对存在量词，特性量词作为合取项加入。,p：凡偶数都能被2整除四、一阶逻辑公式翻译及解释G(x,y)：表示 xy。(2)21世纪末，人类将住在月球。施行后的结果不同。xyG(x,y)表示个体域中存在一个x使得对每一个y,x和y有关系Gp：凡偶数都能被2整除用F(x,y)表示个体变项x,y具有关系F。xyG(x,y)表示个体域中所有的x和y有关系G,24,实例3,例3 在一阶逻辑中将下面命题
13、符号化(1)正数都大于负数(2)有的无理数大于有的有理数,解 注意：题目中没给个体域，一律用全总个体域(1)令F(x)：x为正数，G(y)：y为负数,L(x,y)：xy,x(F(x)y(G(y)L(x,y)或者 xy(F(x)G(y)L(x,y),(2)令F(x)：x是无理数，G(y)：y是有理数，L(x,y)：xy,x(F(x)y(G(y)L(x,y)或者 xy(F(x)G(y)L(x,y),25,原子公式：不出现命题联结词和量词的谓词命名式，P(X1,X2Xn)称为谓词演算的原子公式。前面例子中的1元谓词F(x)，G(x)，2元谓词H(x,y)，L(x,y)等都是原子公式。,四、一阶逻辑公
14、式翻译及解释,26,定义4 合式公式定义如下：(1)原子公式是合式公式.(2)若A是合式公式，则(A)也是合式公式(3)若A,B是合式公式，则(AB),(AB),(AB),(AB)也是合式公式(4)若A是合式公式，则xA,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
15、1.所谓一个解释不外乎指定个体域、个体域中一些特定的元素、特定的函数和谓词等。,谓词公式的解释,28,解释(举例),F(f(a,a),b)解释1：个体域是全体自然数;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)X的辖域是P(X)X(P(X,Y)Q(X，Y)P(Y,Z)X的辖域是P(X，Y)Q(X，
16、Y),变元的约束,30,定义：在量词X，X辖域内变元X的一切出现叫约束出现，称这样的X为约束变元；变元的非约束出现称为自由出现,称这样的变元为自由变元。,例：指出下列谓词公式中的自由变元和约束变元，并指明量词的辖域。X(P(X)R(X)XP(X)Q(X)解：表达式中的X(P(X)R(X)中X的辖域是 P(X)R(X),其中的X是约束出现，Q(X)中的X是自由变元。,变元的约束,31,注意：在一个公式中，一个变元既可以约束出现，又可以自由出现。为避免混淆可采用下面两个规则：约束出现改名规则，将量词辖域中某个约束出现的个体变元及相应指导变元，改成本辖域中未曾出现过的个体变元，其余不变。例 x F(
17、x)G(x,y)(换名规则,将约束出现 zF(z)G(x,y)的x改成z),约束变元改名规则,32,对自由变元改名称为自由变元代入规则，对某自由出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且处处代入。例 x F(x)G(x,y)(代替规则,将自由出现 x F(x)G(z,y)的x改成z),自由变元代入规则,33,改名规则与代入规则的共同点都是不能改变约束关系，而不同点是：施行的对象不同。改名是对约束变元施行，代入是对自由变元施行。施行的范围不同。改名可以只对公式中一个量词及其辖域内施行，即只对公式的一个子公式施行；而代入必须对整个公式同一个自由变元的所有自由出现同时施行，即必须对整个公式施行。,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个量词,
