谓词逻辑 st 学习.pptx

《谓词逻辑 st 学习.pptx》由会员分享，可在线阅读，更多相关《谓词逻辑 st 学习.pptx（45页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、在命题逻辑中，我们把命题分解到原子命题为止，认为原子命题是不能再分解的，仅仅研究以原子命题为基本单位的复合命题之间的逻辑关系和推理。实际上，简单命题还可以进行分解:1.“王平是大学生”这一简单命题可以分解为主语(王平)和谓语(是大学生)，命题逻辑反映不出这一特点2.如下两个简单命题 “王平是大学生”“李明是大学生”有一个共同特点是大学生，这一共性在命题逻辑中也表示不出来。因此，有必要推广命题逻辑。第1页/共45页3.3.有些简单而正确的推理过程在命题演算里不能得到证明。例如著名的苏格拉底三段论：“所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。”在命题逻辑中，三个原子命题分别用P P，

2、Q Q，R R表示，现在要证明P P Q QR R，即证明P P Q QR R是重言式，但这在命题逻辑中是不可能的。因此从推理的角度看，也有必要推广命题逻辑。P，Q，R在内部结构上是有联系的，即R的主语和谓语分别是Q的主语和P的谓语。第2页/共45页类似的还有很多，例如：所有的人都要呼吸，李华是人，所以李华要呼吸。所有的正整数都大于0，3是正整数，所以3大于0。解决以上两个问题都需要将原子命题结构细分，一般主要划分为主语和谓语。本章介绍的谓词逻辑，对原子命题的成份、结构和原子命题间的共同特性等作了进一步分析。引入了个体词、谓词、量词、谓词公式等概念，在此基础上研究谓词公式间的等值关系和蕴含关系

3、，并且对命题逻辑中的推理规则进行扩充和进行谓词演绎。第3页/共45页本章内容谓词、个体、量词合式谓词公式自由变元和约束变元含有量词的等价式和永真蕴含式谓词逻辑中的推理理论前束范式、斯柯林范式第4页/共45页5/445/44 2.1谓词演算原子命题被分解为谓词和个体两部分。个体：可以独立存在的事物。它可以是一个具体的事物，也可以是一个抽象的概念。老师，计算机，证书，道德，智商等。个体常元:表示具体的或确定的个体。a,b,c个体变元:表示抽象的或泛指的（或者说取值不确定的）个体。x,y,z谓词：用来刻划单个个体的性质或两个以上个体之间关系的词称为谓词。刻划一个个体性质的词称为一元谓词；刻划n个个体

4、之间关系的词称为n元谓词。第5页/共45页6/446/44谓词和个体例：（1 1）李明是学生；（2 2）张亮比陈华高；（3 3）陈华坐在张亮与李明之间。个体：李明，张亮，陈华谓词：是学生；比高；坐在 和之间一元谓词：是学生二元谓词：比高三元谓词：坐在和之间特别地，当n=0n=0，称为零元谓词，即不带个体变元的谓词为零元谓词。零元谓词是命题，这样命题与谓词就得到了统一，因而可将命题看成特殊的谓词。第6页/共45页7/447/44谓词和个体（1 1）李明是学生；（2 2）张亮比陈华高；（3 3）陈华坐在张亮与李明之间。谓词(Predicate)常用P，Q，R，A，B等大写字母来表示，也常用英文单词

5、来表示，如GREAT：大于；BETWEEN：位于之间用小写的英文字母表示个体。上述命题可分别表示为Q(a),P(b,c),R(c,b,a)Q(a),P(b,c),R(c,b,a)一般地，由n n个个体和n n元谓词所组成的命题可表示为F F（a1,a2,ana1,a2,an）,其中F F表示n n元谓词,a1,a2,an,a1,a2,an 分别表示n n个个体。注意：a1,a2,ana1,a2,an的排列次序是重要的。第7页/共45页8/448/44谓词和个体对于F F（a1,a2,ana1,a2,an），如果括号内的个体是抽象的可变化的，那么F F（a1,a2,ana1,a2,an）称为n

6、n元原子谓词公式或n n元命题函数。命题的n n元谓词表示形式和n n元命题函数不同?a:a:张明。命题函数：P(x)xP(x)x是学生。谓词表示形式:P(a):P(a)张明是学生。(个体变元x,x,个体常元a)a)第8页/共45页9/449/44个体域个体域可以是有限的，也可以是无限的。所有个体域的总和叫作全总个体域全总个体域。以某个个体域为变化范围的变元叫个体变元。个体域的变换范围影响到谓词公式的真假R(x)：x是大连理工大学软件学院的学生如果x的讨论范围是大工软件学院某个班级的学生如果x的讨论范围是某个幼儿园里的小朋友如果x的讨论范围是大连的所有市民任何个体的变化都有一个范围，这个变化范

7、围称为个体域个体域(或论域或论域)。永真永真永假永假可满足可满足第9页/共45页10/4410/44谓词的阶在谓词 中，如果个体变元是一些简单的事物，那么P为一阶谓词；若个体变元中有一些是一阶谓词，那么P为二阶谓词；二阶以上递推。本门课程仅研究一阶谓词第10页/共45页11/4411/44量词使用前面介绍的谓词和个体变元，还不足以描述自然界的所有命题。例：描述命题“所有的正整数都大于0”以及命题“有些正整数是素数”。量词的引入：量词是指在命题里表示数量的词。第11页/共45页12/44全称量词符号“”表示命题：“对于个体域中所有个体x，谓词P(x)均为T”。其中“”叫作全称量词，读作“对于所有

8、的x”。谓词P(x)称为全称量词的辖域或作用范围。例如：所有的人都是要死的 令D(x)：x 是要死的。则命题可表示为 x D(x)取个体域为全体人的集合，是真命题。所有的正整数都是素数；令 P(x)：x 是素数则命题可表示成 x P(x)取个体域为正整数集，是假命题。第12页/共45页13/4413/44存在量词符号“”表示命题：“在个体域中存在某些个体使谓词P(x)为T”其中“”叫作存在量词，读作“存在x”。谓词P(x)称为存在量词的辖域或作用范围。例如：有些正整数是素数；令 P(x)：x 是素数则命题可表示成 x P(x)取个体域为正整数集，是真命题。当一个一元谓词的个体域确定之后，经某个

9、量词的作用(叫量化)，将被转化为一个命题，可以确定其真值。第13页/共45页14/4414/44量词量词本身不是一个独立的逻辑概念，可以用 联结词取代。设个体域 ，谓词可以表示成以下形式：由量词确定的命题真值与个体域有关。令 P(x)：x 是素数则 x P(x)，如果取个体域为素数集，为真；如果个体域为整数集，为假。第14页/共45页15/4415/44量词为了方便起见，个体域一律用全总个体域，每个个体变元的真正变化范围则用一个特性谓词来刻划。注意：对于全称量词应使用单条件逻辑联结词；对于存在量词应使用逻辑联结词合取。R(x):x是自然数；P(x):x大于0.以后不加强调个体域均指全总个体域第

10、15页/共45页16/4416/44量词全称量词和存在量词不仅可以单独出现，还可以组合形式出现。对于二元谓词P(x,y)，可能有以下几种量化的可能：第16页/共45页17/4417/44组合量词的含义设A(x,y)表示x,y同姓，x的个体域是1班同学，y的个体域是2班同学。：1班任何一个同学与2班的所有同学同姓；：2班任何一个同学与1班的所有同学同姓；：对1班的任意一个同学，2班都有人跟他同姓；：存在一个2班同学和1班的所有同学同姓。翻译时从左向右量词出现的次序很重要，不能随便交换第17页/共45页18/4418/44合式谓词公式若P为不能再分解的n元谓词变元，x1,x2,xn是个体变元，则称

11、P(x1,x2,xn)为原子公式或原子谓词公式。当n=0时，P表示命题变元即原子命题公式。所以，命题逻辑实际上是谓词逻辑的特例。由原子谓词公式出发，通过命题联结词，可以组成复合谓词公式，叫分子谓词公式。第18页/共45页19/4419/44合式谓词公式定义：（1）原子谓词公式是合式的公式；（2）若A是合式的公式，则 A也是合式的公式；（3）若A和B都是合式的公式，则A B,A B,A B,A B 也都是合式的公式；（4）如果A是合式的公式，x是任意变元，且A中无 或 出现，则 和 都是合式的公式；（5）当且仅当有限次使用规则（1）（4）由逻辑联结词、圆括号构成的有意义的字符串是合式的公式。第1

12、9页/共45页20/4420/44自由变元和约束变元在谓词公式中，如果有形如 或者 ，则称它们是x的约束部分。每个量词后面的最短公式，称为量词的辖域。（量词的优先级高于任何联结词）约束变元：一个变元若出现在包含这个变元的量词(全称量词或存在量词)的辖域之内，则该变元称为约束变元，其出现称为约束出现。自由变元：变元的非约束出现叫作自由出现，该变元叫作自由变元。第20页/共45页21/4421/44自由变元和约束变元例：说明以下各式量词的辖域与变元的约束情况。第21页/共45页22/4422/44自由变元和约束变元从约束变元的概念可知，谓词P(x)的量化，就是从变元x的整个个体域着眼，对性质P(x

13、)所作的一个全称判断或特称判断。其结果是将谓词变成一个命题。因此，和 可以看成消元运算。（被量化以后没有自由变元了）对n元谓词P(x1,x2,xn)量化后，假设有k个自由变元，则降为k元谓词。二元谓词一元谓词第22页/共45页23/4423/44自由变元和约束变元一般情况下给定一个谓词公式A(x)，仅表明在该公式中只有一个自由变元，但并不限制在该公式中还存在若干约束变元。以下各式都可以写成A(x)：第23页/共45页24/4424/44谓词公式的解释在命题逻辑中对一个公式的解释，是对每个命题变元进行取值指派，如果公式有n个变元，则有2n种解释。谓词公式的解释，涉及到命题变元、谓词变元、个体变元

14、、符号函数真值表法不可行第24页/共45页25/4425/44谓词公式的解释定义：设A的个体域是D，如果用一组谓词常量、命题常量和A中的个体及函数符号（将它们简记为I）代换公式A中相应的变元，则该公式A转化成一个命题，可以确定其真值（记作P）。称I为公式A在D中的解释（或指派）称P为公式A关于解释I的真值。永真永假可满足 第25页/共45页26/4426/44谓词公式的解释给定两个谓词公式A和B，D是它们共同的个体域，若AB在D中是永真式，则称遍及D有 ；若D是全总个体域，则称 若 且 ，则称 。命题逻辑中的恒等式和永真蕴含式全部可以推广到谓词逻辑中。第26页/共45页27/4427/44含有

15、量词的等价式和永真蕴含式量词转换律例：设P(x)：x今天来上课。软件工程系08级18-20班全体同学。：所有同学今天都来上课了。：不是所有人今天都来上课了。：今天有人没有来上课。：有人今天来上课了。：没有人今天来上课。：所有的人今天都没有来上课。谓词逻辑区别于命题逻辑所特有的等价式与蕴涵式第27页/共45页28/44量词转换律（其中（其中A(x)是任意的公式）是任意的公式）证明证明 设个体域设个体域 ,则则第28页/共45页29/4429/44量词辖域扩张及收缩律证明：仅对第一个式子证明，其余类推。P不含自由变元第29页/共45页30/4430/44量词分配律全称量词对满足分配律，存在量词对满

16、足分配律。证明：仅证明第一个式子。第30页/共45页31/4431/44量词分配律全称量词对，存在量词对 不满足分配律。例：个体域是人的集合。A(x)：x是女人。B(x)：x是男人。为真；为假。为假.为真。仅满足：为正确理解上面第二式。设A(x):x会用左手拿筷子吃饭B(x):x会用右手拿筷子吃饭第31页/共45页32/4432/44重要等价式和永真蕴含式第32页/共45页33/4433/44重要等价式和永真蕴含式第33页/共45页34/4434/44重要等价式和永真蕴含式17，18 谓词逻辑中特有的蕴涵式第34页/共45页35/4435/44量词交换式第35页/共45页36/4436/44记

17、忆规律第36页/共45页37/4437/442.2 谓词逻辑中的推理规则谓词公式的翻译推理规则第37页/共45页38/4438/44谓词公式的翻译任何整数都是实数。P(x)：x是整数；Q(x)：x是实数。符号化为：没有不犯错误的人。P(x)：x是人；Q(x)：x犯错误。符号化为：或符号化为：第38页/共45页39/4439/44谓词公式的翻译有一个大于10的偶数。P(x)：x10；Q(x)：x是偶数。符号化为：每个学生都要锻炼身体。P(x)：x是学生；Q(x)：x锻炼身体。符号化为：不能符号化为：第39页/共45页40/4440/44有的狮子不爱喝咖啡。P(x)：x是狮子；Q(x)：x爱喝咖啡

18、。符号化为：不能符号化为：谓词公式的翻译第40页/共45页41/4441/44谓词公式的翻译不管黑猫白猫，抓住老鼠就是好猫。P(x)：x是黑猫。Q(x)：x是白猫。R(x)：x是抓住老鼠的猫。G(x)：x是好猫。符号化为：有些人对某些食物过敏。A(x)：x是人。B(x)：x是食物。C(x,y)：x对y过敏。符号化为：第41页/共45页42/4442/44谓词公式的翻译一切人不是一样高。P(x)：x是人。Q(x,y)：x与y一样高。R(x,y)：x与y是不一样。符号化为：不是一切人都一样高。符号化为：或：第42页/共45页43/4443/44谓词公式的翻译符号化：没有只爱江山不爱美人的英雄Hero(x)：x是英雄Love(x,y)：x爱y符号化为：或第43页/共45页作业P39 ：1（1），（3）2（1）3课件下载：password：aaaaa11111第44页/共45页感谢您的观看！第45页/共45页