《面向计算机的数理逻辑（ch3）ppt培训课件》由会员分享，可在线阅读，更多相关《面向计算机的数理逻辑（ch3）ppt培训课件（97页珍藏版）》请在金锄头文库上搜索。
1、1,面向计算机的数理逻辑,主讲：李伟刚 西北工业大学软件与微电子学院,2,第三章 谓词逻辑,3,3.1 我们需要更丰富的语言,命题逻辑通过三个角度来展开研究 证明论（自然演绎演算） 句法（公式的树状性质） 语义（公式的实际含义） 这是基于：判断语句，即关于现实世界论述的每个赋值或模式都能给出真值。,4,我们知道，命题演算的基本研究单位是原子命题，在命题演算中，原子命题是不能再分割的了。这对研究命题间的关系是比较合适的。但是，在进一步研究时就会发现，仅仅命题演算对我们是很不够的并且也不充分，比如：三段论在命题演算系统中是无法完成的。例如： 所有的科学是有用的数理逻辑是科学所以，数理逻辑是有用的
2、又例如：凡人必死张三是人故张三必死,5,上述两个例子用命题逻辑描述不充分的主要原因就是在于这种推理中需要对原子命题作进一步分解，在上述两个例子中，每个例子三个命题间，具有必然的内在逻辑关系，只有对这种内存逻辑联系深入研究后，才能解决形式逻辑中的一些推理问题。谓词演算正是为了这样的目的，换言之也就是对原子命题进行进一步的分解。,6,在谓词演算中，将原子命题分解为谓词与个体两部分，在上例中，“数理逻辑是科学”即主语“数理逻辑”与谓语“是科学”，“张三是人”中的“张三”是主语，“是人” 为谓语。换言之在数理逻辑中将主语称为个体，将谓语称为谓词。所谓个体是可以独立存在的物体。它可以是抽象的，也可以是具
3、体的，如：鲜花，代表团，自行车，自然数，唯物主义等等都是个体。谓词是用来刻划个体的性质或关系。如“3整除6”这里3与6是个体，关系“整除”是谓词。一个谓词可以与某个个体相联，此种谓词称为一元谓词。上例中张三，3，6等也可以是抽象的，比如x，y，称为变元/变量。由个体组成的集合称为个体域（或论述域），以某个个体域I为变域的变元叫做个体变元。,7,一个单独的谓词是没有含义的，如：“是大学生“，这个谓词必须跟随一定数量的个体后才有明确的含义，最重要的是能分别其真假。个体谓词中的次序有时也是很重要的，如“上海位于南京与杭州之间”，此命题为真，其中“上海”、“南京”、“杭州”三个个体间次序不能随便颠倒，
4、如果写成“杭州位于南京和上海之间”，则此时命为假。所以，由谓词以及跟随它的若干个有一定次序的个体便可构成一个完整的命题。,8,下面我们一般用大写字母A，BE表示谓词，用小写字母a，b，cz表示个体（或个体变元），这样x，y间具有关系B可记作B（x，y），x，y，z具有关系C，记作C（x，y，z），上述是二元谓词和三元谓词，当然也可以表示为n元谓词就是有n个个体变元的谓词，并约定0元谓词是命题。n元谓词当然需要赋于n个个体变元才有意义，我们把谓词后填以个体称为谓词填式。有了谓词的概念后我们可以将一些日常用语及命题更深刻地刻划出来，下面我们以几个例子说明：,9,例1：王强是大学生李华也是大学生。解
5、：F表示是大学生， F（x）表示x是大学生。a表示“王强”，b表示“李华”，则此式可表示为：F（a）F （b）,例2：我国领导人访问美国 。解：F（x，y）表示x访问y，a表示我国领导人，b表示美国，则此式可表示为：F（a，b）,10,例3：大楼建成了。解：F（x）表示“x建成了”，G（x）表示“x是大的”， H（x）表示“x是楼”， 则此式可表示为：F（a）G （a）H（a）,例4：这个人正在看那本红皮面的书。解：F（x，y）表示“x正在看y”，G（x）表 示“x是人”，H（y）表示“y是红皮面的”，U （y）表示“y是书”，a表示“这个”，b表示“那 本”，则此式可表示为：F（a，b）G
6、（a）H（b）U（b）,11,一般地讲，对日常的语句，我们可给出一个大体的准则，根据这些准则可写出其逻辑表达式来。名词：专用名词（如王强，美国等）为个体通用名词（如楼房，人等）一般可为个体代名词：人称代词（如：你，我，他），指示代词（如这个，那个）为个体不定代词（如任何，每个，有些，一些等）为量词形容词：一般为谓词数词： 一般为量词动词： 一般为谓词副词： 与所修饰的动词合并为一谓词，不再分解前置词：与其它有关字合并为一，本身不独立表示连接词：一般为命题联结词以上准则只供参考，在具体应用时常常也有许多例外,12,3.2 作为形式语言的谓词逻辑,在谓词逻辑中，将句子表达的复杂事实编码为逻辑公式很
7、重要 编码一旦完成，我们的主要目标成为：对那些公式中表达的相关信息进行符号地（ ）或语义地（）推导。,13,3.2.1 量词,在数学上或日常生活中经常碰到“对一切”、“所有的”、“存在一个”、“至少有一个“等的概念，我们学过的命题逻辑是无法表达清楚的。一个谓词演算中的表达不一定是确定的，个体域中不同的个体代入后可得到不同的真假值。如我们考察下面两个式子（它们均以整数作为其个体域）：（1）（x+1）2=x2+2 x+1（2）X+6=5对于（1）我们发现任何整数代入后等式总是正确，但是对（2）分析则不然，它只存在一个整数即（-1）代入后使得等式成立。又如：“q或者大于0，或者等于0，或者小于0”，
8、当然该句可写成：q0q=0q0a=0a（x，0），=（x，0），（x，0）=（x，0） （x，0）,21,3.2.2 函词（函数）为了说明命题函词（函数）的概念，下面先举例解释命题与谓词的关系。例：H为谓词“能够到达山顶”。L表示个体名称李四。T表示个体名称老虎。C表示个体名称汽车。那么H（L），H（T），H（C）等分别表示各种不同的命题，但它们都有一个共同的形式，即H（X）。当X取L，T，C时就表示了，“李四能够到达山顶”，“老虎能够到达到山顶”，“汽车能够到达山顶”。,22,同理，若L（x，y）表示“x小于y”，那么L（2，3）表示了一个真命题：“2小于3”。而L（5，1）表示一个假命题：
9、“5小于1”。又如A（x，y，z）表示一个关系“x+y=z”。则A（3，2，5）表示了真命题“3+2=5”。而A（1，2，4）表示了一个假命题“1+2=4”。总之从上述三个例子可以看到H（x），L（x，y），A（x，y，z）本身不是一个命题，只有当x，y，z等取特定的个体时，才确定了一个命题。即给出如下定义：,23,定义：由一个谓词及一些个体变元组成的表达式称为命题函词（函数）。根据这个定义可以看到，n元谓词是有n个个体变元函词（函数），当n=0时称为0元函词，它本身就是一个命题，记为a，b，c。通常称它为常量。故命题是n元谓词的一个特殊情况。由一个或n个简单函词（函数）以及逻辑联结词组合而成
10、的表达式称为复合命题函词（函数）。逻辑联结词，。例如：R（x）表示“x是大学生”，如果x的讨论范围为某大学班级里的学生，则R（x）是永真式。如果x的讨论范围为某中学班级里的学生，则R（x）是永假式。,24,3.2.3 自由变元与约束变元在阐述自由变元与约束变元之前首先要给出谓词演算公式的概念。 定义：由命题变元和谓词填式利用真值联结词和量词如下构成的式子称为谓词演算公式（简称公式）。（1）命题变元是公式；（2）填以个体变元的谓词变元填式是公式；（3） 如果A是公式，则A也是公式；（4）如果A和B是公式，则（AB），（AB），（AB），（A B）也是公式；（5）如果A是公式，x是个体变元则 x
11、(A),x(A）也都是公式；（6）公式仅限于此。,25,定义：一个公式中如果其中有一部分公式形式如: x (A)或x(A)，则凡在这部分中的变元x的一切出现都叫做在此公式中的约束出现，而变元x叫做此公式中的约束变元。,例如： x（P（x）F（x）中的变元x的二次出现均是约束出现。,26,定义：一公式中如果其中有一部分公式内变元x 不呈约束出现，则称x在此公式中自由出现， 而此变元x称此公式的自由变元。,例如： x（P（x）F（x）Q(y)中的变元y是自由出现，所以y是自由变元。每个量词都有个辖域，除原子公式外，量词的辖域既是出现在它后面的括号内的公式。,通过语法分析树也可以判定自由出现和约束出现（详见教材）。 请分析：（ x(P(x)Q(x) (P(x)Q(y),27,关于约束变元与自由变元我们再举一些例子：例1： x （P（x）yR（x，y）此公式变元x，y均为约束出现，无自由出现。例2：uP（x，z）此公式中变元x,z为自由出现。例3： x P（x）Q（x）此公式中变元x即约束出现，又自由出现。例子中，我们要作一些说明，我们认为在一个公式中允许一个变元即自由出现又为约束出现。但为了避免概念上的混肴起见，我们有时通过改名规则，使得一个变元在一个公式中只有一种形式出现，（即或者自由出现或者约束出现）。这样就避免了二义性。,
