《离散数学课件 第二章 谓词逻辑-1st》由会员分享，可在线阅读，更多相关《离散数学课件 第二章 谓词逻辑-1st（44页珍藏版）》请在金锄头文库上搜索。
1、1/44第二章 谓词逻辑大连理工大学软件学院陈志奎教授办公室： 综合楼411，Tel： 87571525 实验室：教学楼A318/A323，Tel：87571620/24 Mobile: 13478461921 Email: 2/44第二章谓词逻辑在命题逻辑中，命题被当作一个基本的，不可分割的单位，只研究由原子命题和联接词所组成的复合命题；因而无法研究命题的内部结构及命题之间内在的联系。本章介绍的谓词逻辑，对原子命题的成份、结构和原子命题间的共同特性等作了进一步分析。引入了个体词、谓词、量词、谓词公式等概念，在此基础上研究谓词公式间的等值关系和蕴含关系，并且对命题逻辑中的推理规则进行扩充和进
2、行谓词演绎。3/44主要内容谓词、个体、量词 合式谓词公式 自由变元和约束变元 含有量词的等价式和永真蕴含式 谓词逻辑中的推理理论 前束范式、斯柯林范式4/44谓词逻辑的引入在命题逻辑中，对下述论断无法判定正确性 “苏格拉底三段论”： 凡人都是要死的，P 苏格拉底是人，Q 所以苏格拉底是要死的。R (PQ)R 类似的还有很多，例如： 所有的人都要呼吸，李华是人，所以李华要呼吸。 所有的正整数都大于0，3是正整数，所以3大于0。5/442.1谓词演算本质上是把数学中的逻辑论证加以符号化。 在谓词演算中，原子命题被分解为谓词谓词和个体个体两部分。 个体：可以独立存在的事物 。老师，计算机，证书，道
3、德，智商等。 谓词：用来刻划个体的性质或个体之间关系的词称为谓词，刻划一个个体性质的词称为一元谓词；刻划n个个体之间关系的词称为n元谓词。6/44谓词和个体例： （1）李明是学生； （2）张亮比陈华高； （3）陈华坐在张亮与李明之间。个体：李明，张亮，陈华 谓词：是学生；比高；坐在和之间 一元谓词：是学生 二元谓词：比高 三元谓词：坐在和之间7/44谓词和个体（1）李明是学生； （2）张亮比陈华高； （3）陈华坐在张亮与李明之间。一般用大写的英文字母表示谓词大写的英文字母表示谓词，而用小写的英文字母表示个体小写的英文字母表示个体。 上述命题可分别表示为Q(a),P(b,c),R(c,b,a)一
4、般地，由n个个体和n元谓词所组成的命题可表示为F（a1,a2, ,an）,其中F表示n元谓词, a1,a2, ,an 分别表示n个个体。 注意：a1,a2, ,an的排列次序是重要的。8/44谓词和个体对于F（a1,a2, ,an），如果括号内的个体是抽象的可变化的，那么F（a1,a2, ,an）称为n元原子谓词公式或n元命题函数。注意：命题的n元谓词表示形式和n元命题函数不同。 a:张明。 命题函数：P(x) x是学生。 谓词表示形式:P(a) 张明是学生。9/44个体域 定义：任何个体的变化都有一个范围，这个变化范围称为个体域(或论域)。个体域可以是有限的，也可以是无限的。所有个体域的总和
5、叫作全总个体域。以某个个体域为变化范围的变元叫个体变元。 R(x)：x是大连理工大学软件学院的学生 如果x的讨论范围是大工软件学院某个班级的学生，则R(x)永真； 如果x的讨论范围是某个幼儿园里的小朋友，则R(x)永假 如果x的讨论范围是大连的所有市民，则R(x) 可能为真，也可能假。10/44谓词的阶在谓词中，如果个体变元是一些简单的事物，那么P为一阶谓词； 若个体变元中有一些是一阶谓词，那么P 为二阶谓词；二阶以上递推。12( ,)nP x xx11/44量词使用前面介绍的谓词和个体变元，还不足以描述自然界的所有命题。 例： 描述命题“所有的正整数都大于0”以及命题“有些正整数是素数”。量
6、词的引入：量词指在命题里表示数量的词。12/44全称量词符号“”表示命题：“对于个体域中所有个体x，谓词P(x)均为T”。其中“”叫作全称量词，读作“对于所有的x”。谓词P(x)称为全称量词的辖域或作用范围。例如：所有的人都是要死的令D(x)：x 是要死的。 则命题可表示为x D(x) 取个体域为全体人的集合，是真命题。 所有的正整数都是素数；令P(x)：x 是素数则命题可表示成x P(x) 取个体域为正整数集，是假命题。() ( )x P x ()x13/44存在量词符号“”表示命题：“在个体域中存在某些个体使谓词P(x) 为T”。其中“”叫作存在量词，读作“存在x”。谓词P(x)称为存在量
7、词的辖域或作用范围。例如：有些正整数是素数； 令 P(x)：x 是素数 则命题可表示成x P(x) 取个体域为正整数集，是真命题。() ( )x P x()x14/44量词量词本身不是一个独立的逻辑概念，可以用联结词取代。 设个体域是，谓词可以表示成以下形式：由量词确定的命题真值与个体域有关。 令 P(x)：x 是素数 则x P(x)，如果取个体域为素数集，为真；如果个体域为整数集，为假。, 12: ,nS Sa aa=12() ( )()()()nx A xA aA aA a12() ( )()()()nx A xA aA aA a15/44量词为了方便起见，个体域一律用全总个体域，每个个体
8、变元的真正变化范围则用一个特性谓词来刻划。注意：对于全称量词应使用单条件逻辑联结词；对于存在量词应使用逻辑联结词合取。 R(x): x是自然数；P(x): x大于0.()( ( )( )x R xP x()( ( )( )x R xP x16/44量词全称量词和存在量词不仅可以单独出现，还可以组合形式出现。 对于二元谓词P(x,y)，可能有以下几种量化的可能：()() ( , ),()() ( , ) ()() ( , ),()() ( , )()() ( , ),()() ( , )()() ( , ),()() ( , )xy P x yxy P x y xy P x yxy P x yy
9、x P x yyx P x yyx P x yyx P x y 17/44量词设A(x,y)表示x,y同姓， x的个体域是1班同学，y的个体域是2班同学。 ：1班任何一个同学与2班的所有同学同姓； ：2班任何一个同学与1班的所有同学同姓； ：对1班的任意一个同学，2班都有人跟他同姓； ：存在一个2班同学和1班的所有同学同姓。()() ( , )xy A x y()() ( , )yx A x y()() ( , )xy A x y()() ( , )yx A x y()() ( , )()() ( , )xy A x yyx A x y 18/44合式谓词公式若P为不能再分解的n元谓词变元，x
10、1 , x2 ,xn 是个体变元，则称P(x1 , x2 ,xn )为原子公式或原子谓词公式。当n=0时， P表示命题变元即原子命题公式。所以，命题逻辑实际上是谓词逻辑的特例。由原子谓词公式出发，通过命题联结词，可以组成复合谓词公式，叫分子谓词公式。19/44合式谓词公式定义： （1）原子谓词公式是合式的公式； （2）若A是合式的公式，则A也是合式的公式； （3）若A和B都是合式的公式，则A B, A B, A B,A B 也都是合式的公式； （4） 如果A是合式的公式，x是任意变元，且A中无或出现，则和都是合式的公式； （5）当且仅当有限次使用规则（1）（4）由逻辑联结词、圆括号构成的有意义
11、的字符串是合式的公式。()x()x() ( )x A x() ( )x A x20/44自由变元和约束变元在谓词公式中，如果有形如或者，则称它们是x的约束部分。每个量词后面的最短公式，称为量词的辖域。 约束变元：一个变元若出现在包含这个变元的量词(全称量词或存在量词)的辖域之内，则该变元称为约束变元，其出现称为约束出现。自由变元：变元的非约束出现叫作自由出现，该变元叫作自由变元。() ( )x A x () ( )x A x21/44自由变元和约束变元例：说明以下各式量词的辖域与变元的约束情况。(1) () ( , ) (2) ()( ( )() ( , )(3) ()()( ( , )( ,
12、 )()( ( , ) (4) ()( ( )() ( , )() ( , )( , )x P x y x P xy Q x yxy P x yQ y zx P x yx P xx Q x zy R x yQ x y 22/44自由变元和约束变元从约束变元的概念可知，谓词P(x)的量化，就是从变元x的整个个体域着眼，对性质P(x)所作的一个全称判断或特称判断。其结果是将谓词变成一个命题。因此，和可以看成消元运算。 对n元谓词P(x1 , x2 ,xn )量化后，假设有k个自由变元，则降为k元谓词。()x ()x() ( , , )x P x y z()()( ( , , )yx P x y z
13、23/44自由变元和约束变元一般情况下给定一个谓词公式A(x)，仅表明在该公式中只有一个自由变元，但并不限制在该公式中还存在若干约束变元。 以下各式都可以写成A(x)：(1) ()( ( )( , )(2) () ( )( ) (3) () ( )( )(4) () ( , )( )y P yQ x y x R xS x y S yS x y P x yQ x 24/44谓词公式的解释在命题逻辑中对一个公式的解释，是对每个命题变元进行取值指派，如果公式有n个变元，则有2n种解释。谓词公式的解释，涉及到命题变元、谓词变元、个体变元、符号函数25/44谓词公式的解释定义：设A的个体域是D，如果用一
14、组谓词常量、命题常量和A中的个体及函数符号（将它们简记为I）代换公式A中相应的变元，则该公式A转化成一个命题，可以确定其真值（记作P）。称I为公式A在D中的解释（或指派），称P为公式A关于解释I 的真值。 永真 永假 可满足26/44谓词公式的解释给定两个谓词公式A和B，D是它们共同的个体域，若AB在D中是永真式，则称遍及D有；若D是全总个体域，则称。若且，则称。 命题逻辑中的恒等式和永真蕴含式全部可以推广到谓词逻辑中。AB ABABBA AB1:( )( , )( )IP xQ x yP x101212:( ,.,)( ,.,)nnEP x xxP x xx27/44含有量词的等价式和永真蕴
15、含式量词转换律 例：设P(x)：x今天来上课。软件工程系08级21-23班全体同学。 ：所有同学今天都来上课了。 ：不是所有人今天都来上课了。 ：今天有人没有来上课。：有人今天来上课了。 ：没有人今天来上课。 ：所有的人今天都没有来上课。x()( ( )x P x()( ( )x P x ()( )xP x ()( ( )()( )x P xxP x ()( ( )x P x()( ( )x P x ()( )xP x()( ( )()( )x P xxP x 28/44量词转换律（其中（其中A(x)是任意的公式）是任意的公式）()( ( )()( )()( ( )()( )x A xxA xx A xxA x 证明证明设个体域设个体域,则则1,2,nEa aa=L12( )( ()().()nxA xA aA aA a 12()().()nA aA aA a
