《谓词逻辑的基本概念课件》由会员分享，可在线阅读，更多相关《谓词逻辑的基本概念课件（48页珍藏版）》请在金锄头文库上搜索。
1、第四章 谓词逻辑的基本概念l在命题逻辑中，是把简单命题作为基在命题逻辑中，是把简单命题作为基本单元或说作为原子来看待的，不再本单元或说作为原子来看待的，不再对简单命题的内部结构进行分析对简单命题的内部结构进行分析l谓词逻辑引入谓词和量词对简单命题谓词逻辑引入谓词和量词对简单命题做了进一步剖析。做了进一步剖析。l约定以小写字母表示约定以小写字母表示命题、函数命题、函数，而，而以大写字母来表示以大写字母来表示谓词谓词l所介绍的内容限于一阶谓词逻辑或称所介绍的内容限于一阶谓词逻辑或称狭谓词逻辑狭谓词逻辑4.1 谓词和个体词4ll 谓词的描述性定义l例例 张三是学生李四是学生张三是学生李四是学生1.1
2、.在命题逻辑里，这是两个不同的命题，在命题逻辑里，这是两个不同的命题， 只能分别以两个不同的符号表示只能分别以两个不同的符号表示2.2.然而然而它们都有主词和谓词它们都有主词和谓词。主词。主词“张三张三”、“李四李四”不同不同谓词谓词“是学生是学生”是是相同相同的的若以大写符号若以大写符号P P表示表示“是学生是学生”，便可把，便可把这两个命题分别写成这两个命题分别写成P(P(张三张三) ) 和和P(P(李四李四) )3.3.自然一般地可引入变量自然一般地可引入变量x x来表示主词，来表示主词，于是符号于是符号P(xP(x) )就表示就表示“x x是学生是学生”通常通常把把P(xP(x) )称
3、作谓词称作谓词一元谓词描述性定义：一元谓词描述性定义：在一个命题里，在一个命题里，如果主词只有一个，这时表示该主词如果主词只有一个，这时表示该主词性质或属性的词便称作谓词这是一性质或属性的词便称作谓词这是一元元( (目目) )谓词，以谓词，以P(x)P(x)，Q(x)Q(x)，表示表示多元谓词描述性定义：多元谓词描述性定义：在一个命题里，在一个命题里，如果主词多于一个，那么表示这几个如果主词多于一个，那么表示这几个主词间的关系的词称作谓词这是多主词间的关系的词称作谓词这是多元谓词，以元谓词，以P(xP(x，y)y)，Q(xQ(x，y)y)，R(xR(x，y y，z)z)，表示表示n如如“张三和
4、李四是兄弟张三和李四是兄弟”其中其中“是兄弟是兄弟”是是谓词谓词“5 5大于大于3”3”其中其中“大于大于”是谓词是谓词“张三比李四高张三比李四高”其中其中“比比高高”是谓是谓词词“天津位于北京的东南天津位于北京的东南”其中其中“位于位于东南东南”是谓词是谓词“A A在在B B上上”其中其中“在在上上”是谓词是谓词4.1.2 4.1.2 个体词个体词 l个体词个体词( (主词主词) ): :个体常项、个体变项个体常项、个体变项l谓词谓词: :谓词常项、谓词变项谓词常项、谓词变项l个体词的变化范围个体词的变化范围：个体域：个体域( (论域论域) )。约定谓词逻。约定谓词逻辑的个体域除明确指明外，
5、都认为是包括一切事辑的个体域除明确指明外，都认为是包括一切事物的一个最广的集合以物的一个最广的集合以D D表示表示l谓词的变化范围谓词的变化范围: :不做特别声明时，指一切关系不做特别声明时，指一切关系或一切性质的集合或一切性质的集合l同一谓词在不同论域下的描述形式可能不同，所同一谓词在不同论域下的描述形式可能不同，所取的真假值也可能不同取的真假值也可能不同4.1.3 4.1.3 谓词的抽象定义谓词的抽象定义 l将谓词视作为一个个体的性质或多个个体间的将谓词视作为一个个体的性质或多个个体间的关系还可进一步关系还可进一步抽象地定义抽象地定义: :谓词是给定的个体域到集合谓词是给定的个体域到集合T
6、 T，F F上的一个上的一个映射映射l还需说明，一般地说谓词还需说明，一般地说谓词P(X)P(X)，Q(xQ(x，y)y)是命是命题形式而不是命题题形式而不是命题不可能直接确定取真还是不可能直接确定取真还是取假，仅当谓词变项取定为某个谓词常项，并取假，仅当谓词变项取定为某个谓词常项，并且个体词取定为个体常项时，命题形式才化为且个体词取定为个体常项时，命题形式才化为命题命题4.1.4 4.1.4 谓词逻辑与命题逻辑谓词逻辑与命题逻辑l可认为谓词逻辑是命题逻辑的推广可认为谓词逻辑是命题逻辑的推广因为任一命因为任一命题都可通过引入具有相应含义的谓词题都可通过引入具有相应含义的谓词( (个体词视为个体
7、词视为常项常项) )来表示，或认为一个命题是没有个体变元的来表示，或认为一个命题是没有个体变元的零元谓词零元谓词l命题逻辑中的很多概念。规则都可推广到谓词逻命题逻辑中的很多概念。规则都可推广到谓词逻辑中延用，如辑中延用，如联结词可照搬到谓词逻辑联结词可照搬到谓词逻辑，无需再，无需再做说明，有的等值式推理式也可移植到谓词逻辑做说明，有的等值式推理式也可移植到谓词逻辑4.2 4.2 函数和量词函数和量词4.2.1 4.2.1 函数函数l约定函数符号用小写字母表示，如约定函数符号用小写字母表示，如f f，g g，fatherfather，l函数可以嵌入在谓词中，但不能单独使用函数可以嵌入在谓词中，但
8、不能单独使用如如函数函数father(x)father(x)表示表示x x的父亲，若谓词的父亲，若谓词P(x)P(x)表表示示x x是教师，则是教师，则P(father(x)P(father(x)就表示就表示x x的父亲是的父亲是教师当教师当x x的取值确定后，的取值确定后，P(father(x)P(father(x)的值或的值或为真或为假为真或为假又如又如“张三的父亲和母亲是夫妻张三的父亲和母亲是夫妻”可描述成可描述成MARRIED(father(MARRIED(father(张三张三) )，mother(mother(张三张三)其中谓其中谓词词MARRIED(xMARRIED(x，y)y)
9、表示表示x x和和y y是夫妻，而是夫妻，而father(x)father(x)，mother(x)mother(x)是函数是函数4.2.2 4.2.2 量词量词全称量词全称量词l例例子子：“凡凡事事物物都都是是运运动动的的”。这这命命题题中中的的“凡凡” ” 是是表表示示个个体体变变元元数数量量的的词词，“凡凡”的的等等义义词词有有“所所有有的的”、“切切的的”、“任任个个”、“每每一一个个”，它是全称量词。，它是全称量词。l符符号号: :( ( x x) )读读作作所所有有的的x x或或任任一一x x，一一切切x x而而 就就称为全称量词，它所约束的个体是称为全称量词，它所约束的个体是x
10、xl定定义义：命命题题( ( x x)P(x)P(x)当当且且仅仅当当对对论论域域中中的的所所有有x x来来说说，P(x)P(x)均均为为真真时时方方为为真真这这就就是是全全称称量量词词的的定义定义( ( x x)P(x)P(x)也写为也写为( ( x x)(P(x)(P(x)注意注意( ( x x)(P(x)(P(x) Q(x)Q(x) ( ( x x)P(x)P(x) Q(x)Q(x)量词的运算优先级高于逻辑联结词量词的运算优先级高于逻辑联结词l性性质质: :( ( x x)P(x)P(x)F F成成立立，当当且且仅仅当当有有一一个个x x0 0 D D ，使，使P(xP(x0 0 D D
11、) )F F存在量词存在量词例例子子：“有有的的事事物物是是动动物物”。这这命命题题中中“有有的的”就就是是表表示示个个体体变变元元数数量量的的词词，“有有的的”的的等等义义词词有有“存存在在一个一个”、“有一个有一个”、“有些有些”它是存在量词。它是存在量词。符符号号: :( ( x x) )读读作作至至少少有有一一个个x x或或存存在在个个x x或或有有某某些些x x而而 就就是是对对个个体体词词起起约约束束作作用用的的存存在在量量词词，所所约约束束的变元是的变元是x.x.l定定义义：命命题题( ( x x)Q(x)Q(x)当当且且仅仅当当在在论论域域中中至至少少有有一一个个x x0 0，
12、Q(xQ(x0 0) )为为真真时时方方为为真真这这就就是是存存在在量量词词的的定定义义( ( x x)Q(x)Q(x)也写为也写为( ( x x)(Q(x)(Q(x)注意注意( ( x x)(P(x)(P(x) Q(x)Q(x) ( ( x x)P(x)P(x) Q(x)Q(x)l性性质质: :( ( x x)Q(x)Q(x)F F当当且且仅仅当当对对所所有有的的x x D D都都有有Q(x)Q(x)F F4.2.2 4.2.2 约束变元和自由变元约束变元和自由变元1. 约束变元与自由变元约束变元与自由变元l在一个含有量词的命题形式里，区分个体词在一个含有量词的命题形式里，区分个体词受量词的
13、约束还是不受量词的约束是重要的受量词的约束还是不受量词的约束是重要的l若若P(x)P(x)表示表示x x是有理数，这时的变元是有理数，这时的变元x x不受任不受任何量词约束，便称是何量词约束，便称是自由的自由的而而( ( x)P(x)x)P(x)中中的的两处出现的两处出现的变元变元x x都受量词都受量词 的约束，便称的约束，便称作作约束变元约束变元，受约束的变元也称被量词量化，受约束的变元也称被量词量化了的变元了的变元l例：命题形式例：命题形式( ( x)P(x)x)P(x) Q(y)Q(y)中，变元中，变元x x是约是约束的，而变元束的，而变元y y是自由的是自由的2. 2. 量词的辖域量词
14、的辖域l量词所约束的命题范围称为量词的辖域如量词所约束的命题范围称为量词的辖域如3. 3. 变元易名规则变元易名规则( ( x x)P(x)= )P(x)= ( ( y y)P(y)P(y)4.3 4.3 合式公式合式公式l目的：目的：像命题逻辑一样，需限定所讨论的命题形像命题逻辑一样，需限定所讨论的命题形式的范围，由于谓词逻辑里引入了个体词、量词，式的范围，由于谓词逻辑里引入了个体词、量词，从而带来了复杂性从而带来了复杂性l一阶而不是高阶谓词逻辑：一阶而不是高阶谓词逻辑：限定量词仅作用于个限定量词仅作用于个体变元，不允许量词作用于命题变项和谓词变项，体变元，不允许量词作用于命题变项和谓词变项
15、，也不讨论谓词的谓词也不讨论谓词的谓词不考虑下述公式不考虑下述公式( p)(Q(x)p)量词作用于命题量词作用于命题p( Q)(Q(x) P(x)量词作用于谓词量词作用于谓词Q(x)合式公式新定义合式公式新定义基本基本( (纳入谓词纳入谓词( (函数可嵌入函数可嵌入)：(1)(1)命题常项、命题命题常项、命题变项和变项和原子谓词公式原子谓词公式( (不含联结词的谓词不含联结词的谓词) )都是合都是合式公式式公式( (函数嵌入？函数嵌入？) )联结词：联结词：(2)(2)如果如果A A是合式公式，则是合式公式，则A A也是合式公式也是合式公式联结词：联结词：(3)(3)如果如果A A，B B是合
16、式公式，而无变元是合式公式，而无变元x x在在A A，B B的一个中是约束的而在另一个中是自由的，则的一个中是约束的而在另一个中是自由的，则(AB)(AB)，(AB)(AB)，(A(AB)B)，(A (A B)B)也是合式公也是合式公式式( (最外层括号可省略最外层括号可省略) )量词：量词：(4)(4)如果如果A A是合式公式，而是合式公式，而x x在在A A中是自由变元，中是自由变元，则则( ( x)Ax)A，( ( x)Ax)A也是合式公式也是合式公式协调：协调：(5)(5)只有有限次应用以上只有有限次应用以上4 4条构成的符号串才条构成的符号串才是合式公式是合式公式判断一个公式是否为合
17、式公式判断一个公式是否为合式公式合式公式：合式公式： p, p, P(x,y)P(x,y)Q(y), (Q(y), ( x)(A(x)x)(A(x)B(x),B(x),( ( x)(A(x)x)(A(x)( ( y)B(x,y)y)B(x,y)非合式公式：非合式公式：( ( x)F(x)G(x),x)F(x)G(x),违反第三条违反第三条( ( x)(x)( x)F(x),x)F(x),违反第四条违反第四条( ( x)P(y)x)P(y)违反第四条违反第四条4.4 4.4 自然语句的形式化自然语句的形式化使用谓词逻辑描述以自然语句表达的问题，使用谓词逻辑描述以自然语句表达的问题，首先要将问题分
18、解成一些原子谓词，引入谓首先要将问题分解成一些原子谓词，引入谓词符号，进而使用量词、函数、联结词来构词符号，进而使用量词、函数、联结词来构成合式公式。成合式公式。一、四个典型例子4.4.1 “所有的有理数都是实数”的形式化l若以若以P(x)P(x)表示表示x x是有理数，是有理数，Q(x)Q(x)表示表示x x是实数，是实数，这句话的形式描述应为这句话的形式描述应为( ( x)(P(x)x)(P(x)Q(x)Q(x)l“所有的所有的都是都是”，这类语句的形式描，这类语句的形式描述只能使用述只能使用而不能使用而不能使用. 当当P(x)P(x)与与Q(x)Q(x)为为此例中的谓词常项时，上式真值与
19、论域无关。此例中的谓词常项时，上式真值与论域无关。4.4.2 “有的实数是有理数”的形式化l以以P(x)P(x)表表x x是有理数，是有理数，Q(x)Q(x)表示表示x x是实数，这句是实数，这句话的形式描述应为话的形式描述应为( ( x)(P(x)Q(x)x)(P(x)Q(x)l这类语句的形式描述只能使用这类语句的形式描述只能使用而不能使用而不能使用. .按通常认识，按通常认识，其真值与论域有关。其真值与论域有关。设论域设论域D D1 1=e=e，张三，桌子，张三，桌子 ，则上述命题为假。仅当则上述命题为假。仅当D D1 1中有有理数时上述命题方为真中有有理数时上述命题方为真4.4.3 “没
20、有无理数是有理数”的形式化l若以若以A(x)A(x)表示表示x是无理数，是无理数， B(x)B(x)表示表示x是有理是有理数，这句话的形式描述为数，这句话的形式描述为 ( ( x)(A(x)B(x) (x)(A(x)B(x) (比照比照4.4.2)4.4.2)l由摩根律，上式等价于由摩根律，上式等价于( (比照比照4.4.1)4.4.1)证明证明( (注意论域相同注意论域相同) ) ( ( x)(A(x)B(xx)(A(x)B(x)= = ( ( x)(x)( A(x)A(x)B(xB(x)= = ( ( x)(A(x)x)(A(x)B(xB(x)= (= ( x)(B(x)x)(B(x)A(
21、xA(x)4.4.4 “有的实数不是有理数”的形式化l若以若以A(x)A(x)表示表示x x是实数，是实数，B(x)B(x)表示表示x x是有理数，是有理数，那么这句话可形式描述为那么这句话可形式描述为二、二、4.4.5 4.4.5 自然数集的三条公理的形式描述自然数集的三条公理的形式描述l论域是自然数集论域是自然数集，来形式化语句，来形式化语句(1)(1)对每个数，有且仅有一个相继后元，对每个数，有且仅有一个相继后元，(2)(2)没有这样的数，没有这样的数，O O是其相继后元是其相继后元(3)(3)对除对除O O而外的数，有且仅有一个相继前元而外的数，有且仅有一个相继前元( (可将可将这三句
22、话作为建立自然数集合的公理这三句话作为建立自然数集合的公理) )l准备工作准备工作: :引入谓词引入谓词E(x,y)E(x,y)表示表示x xy y，引入函数引入函数f(x)f(x)表示个体表示个体x x的相继后元，即的相继后元，即f(x)=x+1f(x)=x+1引入函引入函数数g(x)g(x)表示个体表示个体x x的相继前元，即的相继前元，即g(x)g(x)x-1.x-1.n对语句对语句1 1需注意需注意存在性和唯一性的描述存在性和唯一性的描述: :即对每个即对每个x x都存在都存在y y，y y是是x x的相继后元的相继后元; ;且对且对任一任一z z，如果它也是，如果它也是x x的相继后
23、元，那么的相继后元，那么y y，z z必相等必相等l语句语句2 2的描述是简单的，可写成的描述是简单的，可写成对语句对语句3 3需注意的是对需注意的是对“除除0 0而外而外”的描的描述，可理解为如果述，可理解为如果x x00则则的形式，的形式，于是语句于是语句3 3可描述为可描述为三、三、4.4.6 4.4.6 三例不等三例不等四、三个有趣的例子四、三个有趣的例子4.4.7 4.4.7 积木世界的形式描述积木世界的形式描述如图所示三块积木如图所示三块积木A A，B B，C C放在桌子上放在桌子上相对位置可如下描述：相对位置可如下描述：ON(CON(C，A) A) 表示表示C C在在A A上，上
24、，ONTABLE(A) ONTABLE(A) 表示表示A A在桌子上在桌子上ONTABLE(B) ONTABLE(B) 表示表示B B在桌子上，在桌子上，CLEAR(C) CLEAR(C) 表示表示C C上无积木块上无积木块CLEAR(B) CLEAR(B) 表示表示B B上无积木块上无积木块表示，对任一表示，对任一x x，如果，如果x x上无积木，那么没有上无积木，那么没有y y在在x x上，这表明了谓词上，这表明了谓词CLEARCLEAR，ONON的关系的关系4.4.8 4.4.8 一段话的形式描述一段话的形式描述l“张三在计算机系工作，李四是计算机系的领张三在计算机系工作，李四是计算机系
25、的领导人员如果导人员如果y y在计算机系工作，而在计算机系工作，而z z是计算机是计算机系的领导，那么系的领导，那么z z是是y y的上级的上级”这段话的形式描这段话的形式描述为述为WORKS-IN(WORKS-IN(计算机系，张三计算机系，张三) )MANAGER(MANAGER(计算机系，李四计算机系，李四) )4.4.9 4.4.9 “函数函数f(x)f(x)在在aa，bb上的点上的点x x。处连续。处连续”的形式描的形式描述述五、五、4.4.10 4.4.10 对谓词变元多次量化的分析对谓词变元多次量化的分析设设P(xP(x，y)y)是二元谓词，对两个变元的量化可得是二元谓词，对两个变
26、元的量化可得4 4种形式种形式(1)注意注意 x x和和 y y可交换可交换(2)注意注意 x x和和 y y不可交换，不可交换，且且y y是是x x的函数的函数(3)注意注意 x x和和 y y不可交换不可交换(4)注意注意 x x和和 y y可交换可交换自然语言形式化小结l这一节介绍了一些具体语句的形式化，都这一节介绍了一些具体语句的形式化，都具有一般性，特别是对具有一般性，特别是对“所有的所有的都是都是”，“有的有的是是”的形式描述是的形式描述是最基本的格式最基本的格式4.5 4.5 有限域下公式有限域下公式 的表示法的表示法l今将论域限定为有限集，为方便又不失一般性，今将论域限定为有限
27、集，为方便又不失一般性，用用1，2，k来代表，这时来重新认识一下来代表，这时来重新认识一下全称量词和存在量词全称量词和存在量词4.5.1 4.5.1 论域为有限域时的公式表示法论域为有限域时的公式表示法l全称量词是合取词的推广全称量词是合取词的推广有限域下，就化成有限域下，就化成了由合取词描述的命题逻辑的公式了由合取词描述的命题逻辑的公式在任意域在任意域下，全称量词的作用下，全称量词的作用“相当于相当于”无限个合取词的无限个合取词的作用作用l同样，同样，存在量词乃是析取词的推广存在量词乃是析取词的推广有限域下有限域下就化成了由析取词描述的命题逻辑的公式就化成了由析取词描述的命题逻辑的公式在在任
28、意域下，存在量词的作用任意域下，存在量词的作用“相当于相当于”无限个析无限个析取词的作用取词的作用l在无穷集在无穷集11，2 2，k k，上上都是没有定义的，不是合式公式因此一都是没有定义的，不是合式公式因此一般地说，谓词逻辑的公式不能转换为命题般地说，谓词逻辑的公式不能转换为命题逻辑公式逻辑公式4.5.2 4.5.2 在域在域11，22上多次量化公式上多次量化公式注意上式右侧含意：注意上式右侧含意：x x是是y y的函数的函数4.5.3 4.5.3 域域11，22上谓词公式的解释上谓词公式的解释l在已知的论域下，需对公式中所含的在已知的论域下，需对公式中所含的命题变命题变项、自由个体变项、谓
29、词变项以及函数项、自由个体变项、谓词变项以及函数给出给出一个具体的设定才构成该公式的一个具体的设定才构成该公式的一个解释一个解释I I，在在I I下该公式有确定的真值。下面在论域下该公式有确定的真值。下面在论域11，22上讨论。上讨论。例例1 1：需设定谓词变项：需设定谓词变项例例2 2：需设定谓词变项：需设定谓词变项例例3 3：需设定谓词变项、函数、自由：需设定谓词变项、函数、自由个体变项个体变项l不不难难看看出出，在在般般的的论论域域D D上上，一一个个谓谓词词公公式式解解释释的的个个数数是是无无限限的的，而而且且每每个个解解释释本本身身需需设设定定的的内内容容也也可可理理解解为为是是无无
30、限限的的，包包括括对对P(1)P(1)，P(2),P(2),，f(1)f(1)，f(2)f(2)，的设定，的设定，4.6 4.6 公式的普遍有效性和判定问题公式的普遍有效性和判定问题l谓词逻辑公式也可分为三类，一是普遍有谓词逻辑公式也可分为三类，一是普遍有效公式、一是可满足公式、一是不可满足效公式、一是可满足公式、一是不可满足公式公式论域确定之后，论域确定之后，判别一个公式的普判别一个公式的普遍有效性问题就是判定问题遍有效性问题就是判定问题4.6.1 4.6.1 普遍有效的公式普遍有效的公式l1.1.对一个谓词公式来说，如果在它的任一解释对一个谓词公式来说，如果在它的任一解释I I下真值都为真
31、，便称作下真值都为真，便称作普遍有效的普遍有效的l2. 2. 对一个谓词公式来说，如果在它的某对一个谓词公式来说，如果在它的某个解释个解释I I下真值为真，便称作下真值为真，便称作可满足的可满足的l3. 3. 对一个谓词公式来说，如果在它的任对一个谓词公式来说，如果在它的任一解释一解释I I下真值均为假，便称作下真值均为假，便称作不可满足不可满足的的l在某个含在某个含k k个元素的个元素的k k个体域上普遍有效个体域上普遍有效( (或可满足或可满足) )，则在，则在k k个体域中任一个体上也普遍有效个体域中任一个体上也普遍有效( (或可满或可满足足) )l如果某公式在如果某公式在k k个体域上
32、普遍有效，则在个体域上普遍有效，则在k k一一1 1个体个体域上也普遍有效，域上也普遍有效，l如果某公式在如果某公式在k k个体域上可满足，则在个体域上可满足，则在k+1k+1个体域个体域上也可满足上也可满足4.4.有限域上公式普遍有效性的几个结论有限域上公式普遍有效性的几个结论4.6.2 4.6.2 判定问题判定问题5. 5. 谓词逻辑的判定问题谓词逻辑的判定问题 指的是任一公式的指的是任一公式的普遍有效性的判定问题若说谓词逻辑是可普遍有效性的判定问题若说谓词逻辑是可判定的，就要求给出一个能行的方法，使得判定的，就要求给出一个能行的方法，使得对任一谓词公式都能判断是否是普遍有效的对任一谓词公式都能判断是否是普遍有效的。(1)(1)一阶谓词逻辑是不可判定的对任一谓词公一阶谓词逻辑是不可判定的对任一谓词公式而言，没有能行方法判明它是否是普遍有效式而言，没有能行方法判明它是否是普遍有效的的(2)(2)一阶谓词逻辑的某些子类是可判定的一阶谓词逻辑的某些子类是可判定的只含有一元谓词变项的公式是可判定的只含有一元谓词变项的公式是可判定的以下公式以下公式 若若P P中无量词和其他自由变项时也是可判定的中无量词和其他自由变项时也是可判定的个体域有穷时的谓词公式是可判定的个体域有穷时的谓词公式是可判定的6. 6. 谓词逻辑判定问题的几个结论谓词逻辑判定问题的几个结论
