谓词逻辑st课程学习.pptx

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

1、会计学1谓词谓词(wi c)逻辑逻辑 st 第一页，共45页。3.3.有些简单而正确的推理过程在命题演算里不能得到证明。例如著名有些简单而正确的推理过程在命题演算里不能得到证明。例如著名(zhmng)(zhmng)的苏格拉底三段论：的苏格拉底三段论：“所有的人都是要死的，所有的人都是要死的，苏格拉底是人，苏格拉底是人，所以苏格拉底是要死的。所以苏格拉底是要死的。”在命题逻辑中，三个原子命题分别用在命题逻辑中，三个原子命题分别用 P P，Q Q，R R表示，现在要证明表示，现在要证明P P Q QR R，即证明，即证明P P Q QR R是重言式，但这在命题逻辑中是不可能的。是重言式，但这在命题

2、逻辑中是不可能的。因此从推理的角度看，也有必要推广命题逻辑。因此从推理的角度看，也有必要推广命题逻辑。P P，Q Q，R R在内部结构上是有联系的，即在内部结构上是有联系的，即 R R的主语和谓语分别是的主语和谓语分别是 Q Q的主语和的主语和P P的谓语。的谓语。第2页/共45页第二页，共45页。类似的还有很多，例如类似的还有很多，例如(lr)：所有的人都要呼吸，李华是人，所以李华要呼吸。所有的人都要呼吸，李华是人，所以李华要呼吸。所有的正整数都大于所有的正整数都大于0，3是正整数，所以是正整数，所以3大于大于0。解决以上两个问题都需要将原子命题结构细分，一般主解决以上两个问题都需要将原子命

3、题结构细分，一般主要划分为主语和谓语。要划分为主语和谓语。本章介绍的谓词逻辑，本章介绍的谓词逻辑，对原子命题的成份、结构和原子命题间的共同特性等作对原子命题的成份、结构和原子命题间的共同特性等作了进一步分析。了进一步分析。引入了个体词、谓词、量词、谓词公式等概念，在此基引入了个体词、谓词、量词、谓词公式等概念，在此基础上研究谓词公式间的等值关系和蕴含关系，础上研究谓词公式间的等值关系和蕴含关系，并且对命题逻辑中的推理规则进行扩充和进行谓词演绎。并且对命题逻辑中的推理规则进行扩充和进行谓词演绎。第3页/共45页第三页，共45页。本章本章(bn zhn)内容内容n n谓词、个体、量词谓词、个体、量

4、词谓词、个体、量词谓词、个体、量词n n合式谓词公式合式谓词公式合式谓词公式合式谓词公式n n自由变元和约束变元自由变元和约束变元自由变元和约束变元自由变元和约束变元n n含有量词的等价式和永真蕴含式含有量词的等价式和永真蕴含式含有量词的等价式和永真蕴含式含有量词的等价式和永真蕴含式n n谓词逻辑中的推理理论谓词逻辑中的推理理论谓词逻辑中的推理理论谓词逻辑中的推理理论(l(l ln)ln)n n前束范式、斯柯林范式前束范式、斯柯林范式前束范式、斯柯林范式前束范式、斯柯林范式第4页/共45页第四页，共45页。5/445/44 2.1谓词演算谓词演算原子命题被分解原子命题被分解(fnji)为谓词和

5、个体两部分。为谓词和个体两部分。个体：可以独立存在的事物个体：可以独立存在的事物。它可以是一个具体。它可以是一个具体的事物，也可以是一个抽象的概念。的事物，也可以是一个抽象的概念。老师，计算机，证书，道德，智商等。老师，计算机，证书，道德，智商等。个体常元个体常元:表示具体的或确定的个体。表示具体的或确定的个体。a,b,c个体变元个体变元:表示抽象的或泛指的（或者说取值不确表示抽象的或泛指的（或者说取值不确定的）个体。定的）个体。x,y,z谓词：用来刻划单个个体的性质或两个以上个体谓词：用来刻划单个个体的性质或两个以上个体之间关系的词称为谓词。之间关系的词称为谓词。刻划一个个体性质的词称为一元

6、谓词；刻划一个个体性质的词称为一元谓词；刻划刻划n个个体之间关系的词称为个个体之间关系的词称为n元谓词。元谓词。第5页/共45页第五页，共45页。6/446/44谓词谓词(wi c)和个体和个体n n例：例：例：例：n n（1 1）李明是学生；）李明是学生；）李明是学生；）李明是学生；n n（2 2）张亮比陈华高；）张亮比陈华高；）张亮比陈华高；）张亮比陈华高；n n（3 3）陈华坐在张亮与李明之间。）陈华坐在张亮与李明之间。）陈华坐在张亮与李明之间。）陈华坐在张亮与李明之间。n n个体：李明，张亮，陈华个体：李明，张亮，陈华个体：李明，张亮，陈华个体：李明，张亮，陈华n n谓词谓词谓词谓词(

7、wi c)(wi c)：是学生；是学生；是学生；是学生；比比比比高；高；高；高；坐在坐在坐在坐在 和和和和之间之间之间之间n n一元谓词一元谓词一元谓词一元谓词(wi c)(wi c)：是学生是学生是学生是学生n n二元谓词二元谓词二元谓词二元谓词(wi c)(wi c)：比比比比高高高高n n三元谓词三元谓词三元谓词三元谓词(wi c)(wi c)：坐在坐在坐在坐在和和和和之间之间之间之间n n特别地，当特别地，当特别地，当特别地，当n=0n=0，称为零元谓词，称为零元谓词，称为零元谓词，称为零元谓词(wi c)(wi c)，即不，即不，即不，即不带个体变元的谓词带个体变元的谓词带个体变元的

8、谓词带个体变元的谓词(wi c)(wi c)为零元谓词为零元谓词为零元谓词为零元谓词(wi c)(wi c)。零元谓词零元谓词零元谓词零元谓词(wi c)(wi c)是命题，这样命题与谓词是命题，这样命题与谓词是命题，这样命题与谓词是命题，这样命题与谓词(wi(wi c)c)就得到了统一，因而可将命题看成特殊的谓就得到了统一，因而可将命题看成特殊的谓就得到了统一，因而可将命题看成特殊的谓就得到了统一，因而可将命题看成特殊的谓词词词词(wi c)(wi c)。第6页/共45页第六页，共45页。7/447/44谓词谓词(wi c)和个体和个体（1 1 1 1）李明是学生；）李明是学生；）李明是学生

9、；）李明是学生；（2 2 2 2）张亮比陈华高；）张亮比陈华高；）张亮比陈华高；）张亮比陈华高；（3 3 3 3）陈华坐在张亮与李明之间。）陈华坐在张亮与李明之间。）陈华坐在张亮与李明之间。）陈华坐在张亮与李明之间。谓词谓词谓词谓词(Predicate)(Predicate)(Predicate)(Predicate)常用常用常用常用P P P P，Q Q Q Q，R R R R，A A A A，B B B B等大写字母来表示，等大写字母来表示，等大写字母来表示，等大写字母来表示，也常用英文单词来表示，如也常用英文单词来表示，如也常用英文单词来表示，如也常用英文单词来表示，如GREATGREA

10、TGREATGREAT：大于；：大于；：大于；：大于；BETWEENBETWEENBETWEENBETWEEN：位：位：位：位于于于于(wiy)(wiy)(wiy)(wiy)之间之间之间之间用小写的英文字母表示个体。用小写的英文字母表示个体。用小写的英文字母表示个体。用小写的英文字母表示个体。上述命题可分别表示为上述命题可分别表示为上述命题可分别表示为上述命题可分别表示为Q(a),P(b,c),R(c,b,a)Q(a),P(b,c),R(c,b,a)Q(a),P(b,c),R(c,b,a)Q(a),P(b,c),R(c,b,a)一般地，由一般地，由一般地，由一般地，由n n n n个个体和个个

11、体和个个体和个个体和n n n n元谓词所组成的命题可表示为元谓词所组成的命题可表示为元谓词所组成的命题可表示为元谓词所组成的命题可表示为F F F F（a1,a2,ana1,a2,ana1,a2,ana1,a2,an）,其中其中其中其中F F F F表示表示表示表示n n n n元谓词元谓词元谓词元谓词,a1,a2,a1,a2,a1,a2,a1,a2,an,an,an,an 分别表示分别表示分别表示分别表示n n n n个个体。个个体。个个体。个个体。注意：注意：注意：注意：a1,a2,ana1,a2,ana1,a2,ana1,a2,an的排列次序是重要的。的排列次序是重要的。的排列次序是重

12、要的。的排列次序是重要的。第7页/共45页第七页，共45页。8/448/44谓词谓词(wi c)和个体和个体n n对于对于对于对于F F（a1,a2,ana1,a2,an），如果括号内的个体是抽），如果括号内的个体是抽），如果括号内的个体是抽），如果括号内的个体是抽象的可变化的，那么象的可变化的，那么象的可变化的，那么象的可变化的，那么F F（a1,a2,ana1,a2,an）称为）称为）称为）称为n n元元元元原子原子原子原子(yunz(yunz)谓词公式或谓词公式或谓词公式或谓词公式或n n元命题函数。元命题函数。元命题函数。元命题函数。n n命题的命题的命题的命题的n n元谓词表示形式和

13、元谓词表示形式和元谓词表示形式和元谓词表示形式和n n元命题函数不同元命题函数不同元命题函数不同元命题函数不同?n na:a:张明。张明。张明。张明。n n命题函数：命题函数：命题函数：命题函数：P(x)xP(x)x是学生。是学生。是学生。是学生。n n谓词表示形式谓词表示形式谓词表示形式谓词表示形式:P(a):P(a)张明是学生。张明是学生。张明是学生。张明是学生。n n(个体变元个体变元个体变元个体变元x,x,个体常元个体常元个体常元个体常元a)a)第8页/共45页第八页，共45页。9/449/44个体个体(gt)域域个体域可以是有限的，也可以是无限的。所有个体域的总和叫作全总个体域。以某

14、个个体域为变化范围的变元叫个体变元。个体域的变换范围影响到谓词(wi c)公式的真假R(x)：x是大连理工大学软件学院的学生如果x的讨论范围是大工软件学院某个班级的学生如果x的讨论范围是某个幼儿园里的小朋友如果x的讨论范围是大连的所有市民任何(rnh)个体的变化都有一个范围，这个变化范围称为个体域(或论域)。永真永真永假永假可满足可满足第9页/共45页第九页，共45页。10/4410/44谓词谓词(wi c)的阶的阶n n在谓词在谓词在谓词在谓词 中，如果个体变元是一些简单中，如果个体变元是一些简单中，如果个体变元是一些简单中，如果个体变元是一些简单的事物的事物的事物的事物(shw)(shw)

15、，那么，那么，那么，那么P P为一阶谓词；为一阶谓词；为一阶谓词；为一阶谓词；n n若个体变元中有一些是一阶谓词，那么若个体变元中有一些是一阶谓词，那么若个体变元中有一些是一阶谓词，那么若个体变元中有一些是一阶谓词，那么P P为二阶谓词；为二阶谓词；为二阶谓词；为二阶谓词；二阶以上递推。二阶以上递推。二阶以上递推。二阶以上递推。本门课程仅研究(ynji)一阶谓词第10页/共45页第十页，共45页。11/4411/44量词量词(lingc)n n使用前面介绍的谓词和个体变使用前面介绍的谓词和个体变元，还不足以描述自然界的所元，还不足以描述自然界的所有命题。有命题。n n例：例：n n描述命题描述

16、命题“所有的正整数都大所有的正整数都大于于0”以及命题以及命题“有些正整数是有些正整数是素数素数(s sh)”。n n量词的引入：量词是指在命题量词的引入：量词是指在命题里表示数量的词。里表示数量的词。第11页/共45页第十一页，共45页。12/44全称全称(qun chn)量词量词n n符号符号符号符号“”“”表示命题：表示命题：表示命题：表示命题：“对于个体域中所有个体对于个体域中所有个体对于个体域中所有个体对于个体域中所有个体x x，谓词，谓词，谓词，谓词P(x)P(x)均为均为均为均为T”T”。其中。其中。其中。其中“”“”叫作全称量词，读叫作全称量词，读叫作全称量词，读叫作全称量词，

17、读作作作作“对于所有的对于所有的对于所有的对于所有的x”x”。谓词。谓词。谓词。谓词P(x)P(x)称为全称量词的辖域或称为全称量词的辖域或称为全称量词的辖域或称为全称量词的辖域或作用范围作用范围作用范围作用范围(fnwi)(fnwi)。n n例如：例如：例如：例如：n n所有的人都是要死的所有的人都是要死的所有的人都是要死的所有的人都是要死的n n 令令令令D(x)D(x)：x x 是要死的。是要死的。是要死的。是要死的。n n则命题可表示为则命题可表示为则命题可表示为则命题可表示为 x D(x)x D(x)n n取个体域为全体人的集合，是真命题。取个体域为全体人的集合，是真命题。取个体域为

18、全体人的集合，是真命题。取个体域为全体人的集合，是真命题。n n所有的正整数都是素数；所有的正整数都是素数；所有的正整数都是素数；所有的正整数都是素数；n n令令令令 P(x)P(x)：x x 是素数是素数是素数是素数n n则命题可表示成则命题可表示成则命题可表示成则命题可表示成 x P(x)x P(x)n n取个体域为正整数集，是假命题。取个体域为正整数集，是假命题。取个体域为正整数集，是假命题。取个体域为正整数集，是假命题。第12页/共45页第十二页，共45页。13/4413/44存在存在(cnzi)量词量词n n符号符号符号符号“”“”表示命题表示命题表示命题表示命题(mng t)(mn

19、g t)：“在个体在个体在个体在个体域中存在某些个体使谓词域中存在某些个体使谓词域中存在某些个体使谓词域中存在某些个体使谓词P(x)P(x)为为为为T”T”其中其中其中其中“”叫作存在量词，读作叫作存在量词，读作叫作存在量词，读作叫作存在量词，读作“存在存在存在存在x”x”。谓词。谓词。谓词。谓词P(x)P(x)称称称称为存在量词的辖域或作用范围。为存在量词的辖域或作用范围。为存在量词的辖域或作用范围。为存在量词的辖域或作用范围。n n例如：例如：例如：例如：n n有些正整数是素数；有些正整数是素数；有些正整数是素数；有些正整数是素数；n n令令令令 P(x)P(x)：x x 是素数是素数是素

20、数是素数n n则命题则命题则命题则命题(mng t)(mng t)可表示成可表示成可表示成可表示成 x P(x)x P(x)n n取个体域为正整数集，是真命题取个体域为正整数集，是真命题取个体域为正整数集，是真命题取个体域为正整数集，是真命题(mng t)(mng t)。当一个一元谓词的个体域确定当一个一元谓词的个体域确定(qudng)之后，经某个量词的作用之后，经某个量词的作用(叫量化叫量化)，将被转化为一个命题，可以确定，将被转化为一个命题，可以确定(qudng)其真值。其真值。第13页/共45页第十三页，共45页。14/4414/44量词量词(lingc)n n量词本身不是一个独立的逻辑

21、概念，可以量词本身不是一个独立的逻辑概念，可以(ky)用用 联结词取代。联结词取代。n n设个体域设个体域 ，谓词可谓词可以以(ky)表示成以下形式：表示成以下形式：n n由量词确定的命题真值与个体域有关。由量词确定的命题真值与个体域有关。n n令令 P(x)：x 是素数是素数n n则则 x P(x)，如果取个体域为素数集，为真；，如果取个体域为素数集，为真；如果个体域为整数集，为假。如果个体域为整数集，为假。第14页/共45页第十四页，共45页。15/4415/44量词量词(lingc)n n为了方便起见，个体域一律用全总个体域，每个个体为了方便起见，个体域一律用全总个体域，每个个体为了方便

22、起见，个体域一律用全总个体域，每个个体为了方便起见，个体域一律用全总个体域，每个个体变元的真正变化范围则用一个变元的真正变化范围则用一个变元的真正变化范围则用一个变元的真正变化范围则用一个(y(y )特性谓词来刻划。特性谓词来刻划。特性谓词来刻划。特性谓词来刻划。n n注意：对于全称量词应使用单条件逻辑联结词；对于注意：对于全称量词应使用单条件逻辑联结词；对于注意：对于全称量词应使用单条件逻辑联结词；对于注意：对于全称量词应使用单条件逻辑联结词；对于存在量词应使用逻辑联结词合取。存在量词应使用逻辑联结词合取。存在量词应使用逻辑联结词合取。存在量词应使用逻辑联结词合取。n nR(x):xR(x)

23、:x是自然数；是自然数；是自然数；是自然数；P(x):xP(x):x大于大于大于大于0.0.以后不加强(jiqing)调个体域均指全总个体域第15页/共45页第十五页，共45页。16/4416/44量词量词(lingc)n n全称量词和存在量词不仅可以全称量词和存在量词不仅可以单独出现，还可以组合形式出单独出现，还可以组合形式出现。现。n n对于二元谓词对于二元谓词(wi c)P(x,y)，可能有以下几种量化的可能：可能有以下几种量化的可能：第16页/共45页第十六页，共45页。17/4417/44组合组合(zh)量词的含义量词的含义设A(x,y)表示x,y同姓，x的个体域是1班同学(tng

24、xu)，y的个体域是2班同学(tng xu)。：1班任何一个同学(tng xu)与2班的所有同学(tng xu)同姓；：2班任何一个同学(tng xu)与1班的所有同学(tng xu)同姓；：对1班的任意一个同学(tng xu)，2班都有人跟他同姓；：存在一个2班同学(tng xu)和1班的所有同学(tng xu)同姓。翻译(fny)时从左向右量词出现的次序很重要，不能随便交换量词出现的次序很重要，不能随便交换第17页/共45页第十七页，共45页。18/4418/44合式合式(h sh)谓词公式谓词公式n n若若若若P P为为为为不不不不能能能能再再再再分分分分解解解解的的的的n n元元元元谓

25、谓谓谓词词词词变变变变元元元元，x1,x1,x2,xnx2,xn是是是是个个个个体体体体变变变变元元元元，则则则则称称称称P(x1,P(x1,x2,xn)x2,xn)为为为为原原原原子子子子公公公公式式式式或或或或原原原原子子子子谓谓谓谓词词词词公公公公式式式式。当当当当n=0n=0时时时时，P P表表表表示示示示命命命命题题题题变变变变元元元元即即即即原原原原子子子子命命命命题题题题公公公公式式式式。所以所以所以所以(su(su y y)，命题逻辑实际上是谓词逻辑的特例。，命题逻辑实际上是谓词逻辑的特例。，命题逻辑实际上是谓词逻辑的特例。，命题逻辑实际上是谓词逻辑的特例。n n由由由由原原原

26、原子子子子谓谓谓谓词词词词公公公公式式式式出出出出发发发发，通通通通过过过过命命命命题题题题联联联联结结结结词词词词，可可可可以以以以组组组组成成成成复合谓词公式，叫分子谓词公式。复合谓词公式，叫分子谓词公式。复合谓词公式，叫分子谓词公式。复合谓词公式，叫分子谓词公式。第18页/共45页第十八页，共45页。19/4419/44合式合式(h sh)谓词公式谓词公式n n定义：定义：n n（1）原子谓词公式是合式的公式；）原子谓词公式是合式的公式；n n（2）若）若A是合式的公式，则是合式的公式，则 A也也是合式的公式；是合式的公式；n n（3）若）若A和和B都是合式的公式，则都是合式的公式，则A

27、 B,A B,A B,A B 也都也都是合式的公式；是合式的公式；n n（4）如果如果A是合式的公式，是合式的公式，x是任是任意变元，且意变元，且A中无中无 或或 出现，出现，则则 和和 都是合式的公都是合式的公式；式；n n（5）当且仅当有限次使用规则）当且仅当有限次使用规则（1）（）（4）由逻辑）由逻辑(lu j)联结联结词、圆括号构成的有意义的字符词、圆括号构成的有意义的字符串是合式的公式。串是合式的公式。第19页/共45页第十九页，共45页。20/4420/44自由自由(zyu)变元和约束变元变元和约束变元n n在谓词公式中，如果有形如在谓词公式中，如果有形如 或者或者 ，则称它们是，

28、则称它们是x的的约束部分。约束部分。n n每个量词后面的最短公式，称每个量词后面的最短公式，称为量词的辖域。（量词的优先为量词的辖域。（量词的优先级高于任何联结词）级高于任何联结词）n n约束变元：一个变元若出现在约束变元：一个变元若出现在包含这个变元的量词包含这个变元的量词(全称量词全称量词或存在或存在(cnzi)量词量词)的辖域之的辖域之内，则该变元称为约束变元，内，则该变元称为约束变元，其出现称为约束出现。其出现称为约束出现。n n自由变元：变元的非约束出现自由变元：变元的非约束出现叫作自由出现，该变元叫作自叫作自由出现，该变元叫作自由变元。由变元。第20页/共45页第二十页，共45页。

29、21/4421/44自由自由(zyu)变元和约束变元变元和约束变元n n例：说明以下各式量词的辖域例：说明以下各式量词的辖域与变元的约束与变元的约束(yush)情况。情况。第21页/共45页第二十一页，共45页。22/4422/44自由自由(zyu)变元和约束变元变元和约束变元n n从约束变元的概念可知，谓词从约束变元的概念可知，谓词P(x)的量化，就是从变元的量化，就是从变元x的整的整个个体域着眼，对性质个个体域着眼，对性质P(x)所所作的一个全称判断或特称判断。作的一个全称判断或特称判断。其结果是将谓词变成一个命题。其结果是将谓词变成一个命题。n n 因此，因此，和和 可以看成消可以看成消

30、元运算元运算(yn sun)。n n （被量化以后没有自由变元了）（被量化以后没有自由变元了）n n对对n元谓词元谓词P(x1,x2,xn)量化量化后，假设有后，假设有k个自由变元，则个自由变元，则降为降为k元谓词。元谓词。二元谓词(wi c)一元谓词第22页/共45页第二十二页，共45页。23/4423/44自由自由(zyu)变元和约束变元变元和约束变元n n一般情况下给定一个谓词公式一般情况下给定一个谓词公式一般情况下给定一个谓词公式一般情况下给定一个谓词公式A(x)A(x)，仅表明在该公，仅表明在该公，仅表明在该公，仅表明在该公式中只有一个自由变元，但并不限制在该公式中还式中只有一个自由

31、变元，但并不限制在该公式中还式中只有一个自由变元，但并不限制在该公式中还式中只有一个自由变元，但并不限制在该公式中还存在若干约束变元。存在若干约束变元。存在若干约束变元。存在若干约束变元。n n以下以下以下以下(y(y xi)xi)各式都可以写成各式都可以写成各式都可以写成各式都可以写成A(x)A(x)：第23页/共45页第二十三页，共45页。24/4424/44谓词公式谓词公式(gngsh)的解释的解释n n在命题逻辑中对一个公式在命题逻辑中对一个公式(gngsh)的解释，是对每个命的解释，是对每个命题变元进行取值指派，如果公题变元进行取值指派，如果公式式(gngsh)有有n个变元，则有个变

32、元，则有2n种解释。种解释。n n谓词公式谓词公式(gngsh)的解释，涉的解释，涉及到命题变元、谓词变元、个及到命题变元、谓词变元、个体变元、符号函数体变元、符号函数真值表法不可行(kxng)第24页/共45页第二十四页，共45页。25/4425/44谓词公式谓词公式(gngsh)的解释的解释n n定义：设定义：设A的个体域是的个体域是D，如果，如果用一组谓词常量、命题常量和用一组谓词常量、命题常量和A中的个体及函数符号（将它中的个体及函数符号（将它们简记为们简记为I）代换公式）代换公式A中相应中相应(xingyng)的变元，则该公式的变元，则该公式A转化成一个命题，可以确定转化成一个命题，

33、可以确定其真值（记作其真值（记作P）。）。n n称称I为公式为公式A在在D中的解释（或中的解释（或指派）指派）n n称称P为公式为公式A关于解释关于解释I的真值。的真值。n n永真永真n n永假永假n n可满足可满足 第25页/共45页第二十五页，共45页。26/4426/44谓词谓词(wi c)公式的解释公式的解释n n给定两个谓词公式给定两个谓词公式A和和B，D是是它们共同的个体域，若它们共同的个体域，若AB在在D中是永真式，则称遍及中是永真式，则称遍及D有有 ；n n若若D是全总个体域，则称是全总个体域，则称 n n若若 且且 ，则称，则称 。n n命题逻辑中的恒等式和永真蕴命题逻辑中的

34、恒等式和永真蕴含式全部可以含式全部可以(ky)推广到谓推广到谓词逻辑中。词逻辑中。第26页/共45页第二十六页，共45页。27/4427/44含有含有(hn yu)量词的等价式和永真蕴含式量词的等价式和永真蕴含式量词转换量词转换(zhunhun)律律例：设例：设P(x)：x今天来上课。今天来上课。软件工程系软件工程系08级级18-20班全体同学。班全体同学。：所有同学今天都来上课了。：所有同学今天都来上课了。：不是所有人今天都来上课了。：不是所有人今天都来上课了。：今天有人没有来上课。：今天有人没有来上课。：有人今天来上课了。：有人今天来上课了。：没有人今天来上课。：没有人今天来上课。：所有的

35、人今天都没有来上课。：所有的人今天都没有来上课。谓词逻辑区别于命题逻辑所特有的等价(dngji)式与蕴涵式第27页/共45页第二十七页，共45页。28/44量词量词(lingc)转换律转换律（其中（其中A(x)是任意的公式）是任意的公式）证明证明 设个体域设个体域 ,则则第28页/共45页第二十八页，共45页。29/4429/44量词量词(lingc)辖域扩张及收缩律辖域扩张及收缩律证明：仅对第一个式子证明，其余证明：仅对第一个式子证明，其余证明：仅对第一个式子证明，其余证明：仅对第一个式子证明，其余(qy)(qy)类推。类推。类推。类推。P不含自由(zyu)变元第29页/共45页第二十九页，

36、共45页。30/4430/44量词量词(lingc)分配律分配律n n全称量词全称量词(lingc)对对满足分配满足分配律，存在量词律，存在量词(lingc)对对满足满足分配律。分配律。n n证明：仅证明第一个式子。证明：仅证明第一个式子。第30页/共45页第三十页，共45页。31/4431/44量词量词(lingc)分配律分配律n n全称量词对全称量词对全称量词对全称量词对，存在量词对，存在量词对，存在量词对，存在量词对 不满足分配律。不满足分配律。不满足分配律。不满足分配律。n n例：个体域是人的集合。例：个体域是人的集合。例：个体域是人的集合。例：个体域是人的集合。n n A(x)A(x

37、)：x x是女人。是女人。是女人。是女人。B(x)B(x)：x x是男人。是男人。是男人。是男人。n n 为真；为真；为真；为真；为假。为假。为假。为假。n n 为假为假为假为假.为真。为真。为真。为真。n n仅满足：仅满足：仅满足：仅满足：n n为正确理解上面第二式。设为正确理解上面第二式。设为正确理解上面第二式。设为正确理解上面第二式。设n nA(x):xA(x):x会用左手拿筷子吃饭会用左手拿筷子吃饭会用左手拿筷子吃饭会用左手拿筷子吃饭(ch fn)(ch fn)n nB(x):xB(x):x会用右手拿筷子吃饭会用右手拿筷子吃饭会用右手拿筷子吃饭会用右手拿筷子吃饭(ch fn)(ch f

38、n)第31页/共45页第三十一页，共45页。32/4432/44重要重要(zhngyo)等价式和永真蕴含式等价式和永真蕴含式第32页/共45页第三十二页，共45页。33/4433/44重要等价重要等价(dngji)式和永真蕴含式式和永真蕴含式第33页/共45页第三十三页，共45页。34/4434/44重要等价重要等价(dngji)式和永真蕴含式式和永真蕴含式17，18 谓词逻辑谓词逻辑(lu j)中特有的蕴涵式中特有的蕴涵式第34页/共45页第三十四页，共45页。35/4435/44量词量词(lingc)交换式交换式第35页/共45页第三十五页，共45页。36/4436/44记忆记忆(jy)规

39、律规律第36页/共45页第三十六页，共45页。37/4437/442.2 谓词逻辑谓词逻辑(lu j)中的推理规则中的推理规则n n谓词公式谓词公式(gngsh)的翻译的翻译n n推理规则推理规则第37页/共45页第三十七页，共45页。38/4438/44谓词公式谓词公式(gngsh)的翻译的翻译 任何整数都是实数任何整数都是实数(shsh)(shsh)。P(x)P(x)：x x是整数；是整数；Q(x)Q(x)：x x是实数是实数(shsh)(shsh)。符号化为：符号化为：没有不犯错误的人。没有不犯错误的人。P(x)P(x)：x x是人；是人；Q(x)Q(x)：x x犯错误。犯错误。符号化为

40、：符号化为：或符号化为：或符号化为：第38页/共45页第三十八页，共45页。39/4439/44谓词公式谓词公式(gngsh)的翻译的翻译 有一个大于有一个大于1010的偶数的偶数(u sh)u sh)。P(x)P(x)：x10 x10；Q(x)Q(x)：x x是偶数是偶数(u sh)u sh)。符号化为：符号化为：每个学生都要锻炼身体。每个学生都要锻炼身体。P(x)P(x)：x x是学生；是学生；Q(x)Q(x)：x x锻炼身体。锻炼身体。符号化为：符号化为：不能符号化为：不能符号化为：第39页/共45页第三十九页，共45页。40/4440/44 有的狮子有的狮子(sh zi)(sh zi)

41、不爱喝咖啡。不爱喝咖啡。P(x)P(x)：x x是狮子是狮子(sh zi)(sh zi)；Q(x)Q(x)：x x爱喝咖啡。爱喝咖啡。符号化为：符号化为：不能符号化为：不能符号化为：谓词谓词(wi c)公式的翻译公式的翻译第40页/共45页第四十页，共45页。41/4441/44谓词公式谓词公式(gngsh)的翻译的翻译 不管黑猫白猫，抓住老鼠就是不管黑猫白猫，抓住老鼠就是(jish)(jish)好好猫。猫。P(x)P(x)：x x是黑猫。是黑猫。Q(x)Q(x)：x x是白猫。是白猫。R(x)R(x)：x x是抓住老鼠的猫。是抓住老鼠的猫。G(x)G(x)：x x是好猫。是好猫。符号化为：符

42、号化为：有些人对某些食物过敏。有些人对某些食物过敏。A(x)A(x)：x x是人。是人。B(x)B(x)：x x是食物。是食物。C(x,y)C(x,y)：x x对对y y过敏。过敏。符号化为：符号化为：第41页/共45页第四十一页，共45页。42/4442/44谓词公式谓词公式(gngsh)的翻译的翻译一切(yqi)人不是一样高。P(x)：x是人。Q(x,y)：x与y一样高。R(x,y)：x与y是不一样。符号化为：不是一切(yqi)人都一样高。符号化为：或：第42页/共45页第四十二页，共45页。43/4443/44谓词谓词(wi c)公式的翻译公式的翻译符号化：没有(mi yu)只爱江山不爱美人的英雄Hero(x)：x是英雄(yngxing)Love(x,y)：x爱y符号化为：或第43页/共45页第四十三页，共45页。作业作业(zuy)n nP39 ：n n1（1），（），（3）n n2（1）n n3课件下载课件下载(xi zi)：password：aaaaa11111第44页/共45页第四十四页，共45页。感谢您的观看感谢您的观看(gunkn)！第45页/共45页第四十五页，共45页。