离散数学课件第2章).ppt

《离散数学》教案 计算机科学与技术学院 课程学时：64 主 讲：宋 成 第二章：谓词逻辑 §2.1谓词的概念与表示 §2.2命题函数与量词 §2.3谓词公式与翻译 §2.4变元的约束 §2.5谓词演算的等价式和蕴含式 §2.6前束范式 §2.7谓词演算的推理理论 第二章：谓词逻辑 §2.1 谓词的概念与表示 在研究命题逻辑中，原子命题是命题演算中的最基小单位，不在对原子命题进行分解，这样会产生两大缺点 不能研究命题的结构、成分和内部的逻辑特征； 也不能表达两个原子命题所具有的共同特征，甚至在命题逻辑中无法处理一些简单又常见的过程。 例：苏格拉底论证是正确的，但是不能用命题逻辑的推理规则推导出来。 “所有的人都是要死的” A “苏格拉底是人” B “所以苏格拉底是要死的” C 第二章：谓词逻辑 1、客体（个体） 考察下面的三个原子命题： ⑴ 李玲是优秀共产党员。 ⑵ 张华比李红高。 ⑶ 小高坐在小王和小刘的中间。 上述命题中的李玲、张华、李红、小高、小王、小刘等就是客体。所以可以这样说，客体是指所研究对象中可以独立存在的具体的或抽象的个体。它可以是独立存在的人或物体，也可以是抽象的概念，如“马列主义”，“资本主义”等。客体常用小写英文字母或小写英文字母带下标表示，叫做客体标识符。 第二章：谓词逻辑 表示具体或特定客体的标识符称作客体体常元，一般用小写英文字母a、b、c、…或这些英文字母带下标表示。例如：李玲、张华、李红、小高、小王、小刘可如下表示： a：李玲 b：张华 c：李红 d：小高 e：小王 f：小刘 a,b,c,d,e,f都是客体常元。 将表示任意客体或泛指某类客体的标识符称为客体变元，常表示为x、y、z、…等或这些英文字母带下标。 客体变元的变化范围称为客体域或论域。客体域可以是有穷集合，也可以是无穷集合，包含任意客体的客体域称为全总客体域，它是由宇宙间一切对象组成的集合。 第二章：谓词逻辑 2、谓词 在上面的三个原子命题中，⑴可以分解成为客体“李玲”和“…是优秀共产党员”两部分。“…是优秀共产党员”是用来描述个体“李玲”的性质的；⑵可以分解成为客体 “张华”、“李红”和“…比…高”两部分。“…比…高”是用来描述客体“张华”和“李红”的身高关系的；⑶可以分解成为客体“小高”、“小王”、“小刘”和“…坐在…和…的中间”两部分。“…坐在…和…的中间”是用来描述客体“小高”、“小王”、“小刘”的位置关系的。 【定义】用以刻划客体性质或关系的即是谓词。谓词常用大写英文字母表示，叫做谓词标识符。 例如可以用F，G，H表示上面三个命题中谓词： F：…是优秀共产党员。 G：…比…高。 H：…坐在…和…的中间。 第二章：谓词逻辑 把与一个客体相关联的谓词叫做一元谓词。F是一元谓词；把与两个客体相关联的谓词叫做二元谓词。G是二元谓词；把与三个客体相关联的谓词叫做三元谓词。H是三元谓词；…。一般的，把与n个客体相关联的谓词叫做n元谓词。 设F是一元谓词，a是客体常元，用F(a)表示客体常元a具有性质F；设G是二元谓词，a,b是客体常元，用G(a,b)表示客体常元a和b具有关系G；… 于是上面三个命题就表示为： F(a)：李玲是优秀共产党员。 G(b,c)：张华比李红高。 H(d,e,f)：小高坐在小王和小刘的中间。 将谓词字母后面填上相关联的客体常元所得的式子叫做谓词填式。F(a)，G(b,c)，H(d,e,f)都是谓词填式。谓词填式表示的是命题。 第二章：谓词逻辑 §2.2谓词函数与量词 1、命题函数 客体在谓词表达式中可以是任意名词。 【例】C：总是要死的。 j: