命题逻辑与谓词逻辑.ppt

《命题逻辑与谓词逻辑.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第二章逻辑推理2.1命题逻辑1．命题定义2-1命题：具有真假意义的语句。定义2-2原子命题：如果一个命题不能被进一步分解成更为简单的命题，则该命题就称为原子命题。2．连接词～：称为“非”或“否定”。∨：称为“析取”，P∨Q读作“P或Q”。∧：称为“合取”，P∧Q读作“P与Q”。→：称为“条件”。P→Q。：称为“双条件”。PQ,“P当且仅当Q”。连接词优先级：～，∧，∨，→，3．合式公式定义2-3合式公式（Well-FormedFormula，WFF）①孤立的命题变元或逻辑常量（T，F）是合式公式；②如果A是一个合式公式，则～A也是一个合式公式；③如果A、

2、B是合式公式，则A∨B，A∧B，A→B，AB也都是合式公式；④当且仅当有限次使用规则①～③后得到的公式才是合式公式。永真式（或重言式）：给定一个公式，如果对于所有的真值指派，它的值都为真（T），则称该公式为永真式（或重言式）；永假式（或称该公式为不可满足的）：如对于所有的真值指派，它的值都为假（F），则称该公式为永假式（或称该公式为不可满足的）。非永假的公式称为可满足的公式。4．等价和永真蕴涵定义2-4等价：设A，B是两个命题公式，P1，P2，…，Pn是出现在A、B中的所有命题变元。如果对于这n个变元的任何一个真值指派的集合，A和B的真值都相等，则称公式A等

3、价于公式B，记作AB。“等价”又可定义为：AB当且仅当AB是一个永真式。定义2-5永真蕴涵：命题公式A永真蕴涵命题公式B，当且仅当A→B是一个永真式，记作AB，读作“A永真蕴涵B”，简称“A蕴涵B”。2.2谓词逻辑1．谓词与个体原子命题被分解为谓词和个体两部分。个体是指可以单独存在的事物，它可以是一个抽象的概念，也可以是一个具体的东西。谓词是用来刻画个体性质或个体间关系的词。如：POET(libai)POET(dufu)GREAT(libai,dufu)一般用大写字母表示谓词，小写字母表示个体。元数:谓词中包含的个体数目称为谓词的。一元谓词:与一个个体

4、相连的谓词，如POET(x)；多元谓词:与多个个体相连的谓词叫，如GREAT(x,y)(二元谓词)。个体域:任何个体的变化都有范围。谓词变元命名式:一个n元谓词常被表示成P(x1,x2,…,xn)。2．量词全称量词:“(x)P(x)”表示命题“对个体域中所有的个体x，谓词P(x)均为T”。存在量词:“(x)Q(x)”表示命题“在个体域中存在某个个体使谓词Q(x)为T”。其中“”叫存在量词。设x的取值范围是{甲，乙，丙}三人，y的取值范围是{bora,jetta,santana}三种车型。(x)(y)LIKE(x,y)表示甲、乙、丙三人都喜爱{bora

5、,jetta,santana}中的某一种车型；(x)(y)LIKE(x,y)表示甲、乙、丙三人都喜爱{bora,jetta,santana}三种车型。3．合式谓词公式原子公式:若P为不能再分解的n元谓词变元，x1,x2,…,xn是个体变元，则称P(x1,x2,…,xn)为原子公式或原子谓词公式。当n= 0时，P表示命题变元或原子命题公式。所以命题逻辑是谓词逻辑的特例定义2-6谓词合式公式（简称公式）的定义如下：①原子公式是合式公式；②若A是合式公式，则～A也是合式公式；③若A和B都是合式公式，则(A∧B)，(A∨B)，(A→B)，(AB)也都是合式公式；

6、④若A是合式公式，x是任意变元，且A中无(x)或(x)出现，则(x)A或(x)A也都是合式公式；⑤当且仅当有限次使用规则①～④得到的公式是合式公式。4．量词的辖域与变元的约束约束变元,自由变元。公式约束变元自由变元(x)P(x,y)xy(x)Q(y)无y(x)(P(x)→(y)Q(x,y))x,y(y)P(x)∧Q(x)yx5．谓词公式的解释谓词公式中的谓词变元、命题变元和自由个体变元，个体常量和函数的一种指派就是一个解释。在每一种解释下，谓词公式都具有一种真值（T或F）。定义2-7设D为谓词公式P的个体域，若对P中的个体常量、函数和谓词按照

7、如下规定赋值：（a）为每个个体常量指派D中的一个元素；（b）为每个n元函数指派一个从Dn到D的映射，其中Dn= {(x1,x2,…,xn) 

8、x1,x2,…,xnD}（c）为每个n元谓词指派一个从Dn到{F，T}的映射；则称这些指派为公式P在D上的一个解释I。例2-1给定公式B= (x)(y)P(x,y)和个体域D1= {1，2}。求：公式B的解释及在该解释下B的真值。解：x,y都可以取D1中的任何值，于是可有以下几种情况：P(1,1)，P(1,2)，P(2,1)，P(2,2)。对这4个公式，每一个都可以指派真假（T，F）两个值，则共有24=16个不同的

9、组合，构成16个不同的解释。P(1,1