离散数学ch2.pptVIP

第二章 谓词逻辑 命题逻辑的特点和局限性 命题是命题演算的基本单位 不再对简单命题进行分解 无法研究命题的内部结构及命题之间内在的联系 在推理方面存在局限性 著名的＂苏格拉底三段论＂ 凡人都是要死的. 苏格拉底是人. 所以苏格拉底是要死的. 若用P,Q,R表示上述三个命题 (P∧Q)?R表示上述推理, 但它不是有效推理. 无法判断＂苏格拉底三段论＂的正确性 其原因在于P,Q,R没有反映它们内在的联系. 需将简单命题做进一步的分析,分析出其中的个体词,谓词,量词等,研究它们的形式结构及逻辑关系,总结出正确的推理形式和规则. 这也就是谓词逻辑(一阶逻辑)所研究的内容 本章学习 谓词逻辑的基本概念 谓词逻辑合式公式及其解释 谓词逻辑等值式 谓词逻辑推理理论 2-1谓词的概念与表示 简单命题分解成客体(个体词、主词) 和谓词 客体: 可以是具体的事物,也可是抽象的概念 例, 李明,黑板,自然数,思想,定理等都是个体词 谓词:用来刻划客体的性质或客体之间关系的词语 例:在下面三个简单命题中: 3是无理数. 王宏是程序员. 小李比小王高2厘米． 客体：３, 王宏, 小李,小王 谓词: ＂…是无理数＂， ＂…是程序员＂，＂…比…高2厘米＂ ＂…是无理数＂， ＂…是程序员＂刻划个体的性质 ＂…比…高2厘米＂表示客体与客体之间的关系 与客体相关的概念 客体常元：表示具体的或特定的客体 用小写英文字母a,b,c,…表示 客体变元：表示抽象的或泛指的客体 用小写英文字母x,y,z,…表示 个体域(论域)：客体变元的取值范围 论域可为有限集，可为无限集 全总个体域 与谓词相关的概念 谓词常元：表示具体性质或关系的谓词 谓词变元：表示抽象的或泛指的谓词 用大写的英文字母表示 例: F: …比…高2厘米 3比2高2厘米 记作: F(3,2) 谓词填式： 谓词字母后填以个体所得的式子． 常称为谓词. 注 谓词中所含个体的数目称为该谓词的元数 一元谓词,二元谓词,…n元谓词 一元谓词刻划个体的性质，n元谓词刻划个体间的关系 0元谓词看成是命题 多元谓词个体填入的顺序有关 2-2命题函数与量词 简单命题函数: n元谓词P(x1,x2,…,xn)是以个体变元x1,x2,…,xn的个体域为定义域，以{0,1}为值域的n元函数. 复合命题函数 谓词与命题的关系 一般P(x1,x2,…,xn)不是命题 例:R(x):x是大学生. R(x)的真假与讨论范围密切相关 例:(P(x,y)∧P(y,z))→P(x,z) P(x,y)解释为:x小于y P(x,y)解释为:x是y的儿子 P(x,y)解释为:x距离y10米 量词 有些命题除了表示个体词和谓词外,还有表示数量的词,称为量词 例: 任何人都能做哪件事. 有些人活百岁以上. 量词的种类: 全称量词 用符号＂?＂ 对应日常语言中＂一切＂,＂所有的＂,＂任意的＂ ?x表示对个体域里的所有个体 存在量词 用符号＂?＂ 对应于日常语言中＂存在着＂,＂有一个＂,＂至少有一个＂ ?x表示存在个体域里的个体 带量词命题的符号化 例: (1)任何人都能做哪件事. (2)有些人活百岁以上. 解: D(x): x能做哪件事 G(x): x活百岁以上 假设个体域是人类的集合 (1)符号化为?xD(x) (2)符号化为?xG(x) 若个体域是全总个体域 需引进新的谓词 M(x):x是人. (1)符号化为?x(M(x)→D(x)) (2)符号化为?x(M(x)∧G(x)) 使用量词时的注意点 在不同的个体域中,命题符号化的形式不一样. 若事先没给出个体域,应以全总个体域为个体域. 当个体域是有限集时,如D={a1,a2,…,an},对任意谓词A(x),有: ?xA(x) ? A(a1)∧A(a2)∧…∧A(an) ?xA(x) ? A(a1)∨A(a2)∨…∨A(an) 多个量词同时出现时,不可随意颠倒它们的次序. ?x?yH(x,y) ?y?xH(x,y) H(x,y): x+y=5 例1:将下列命题符号化 1.凡是有理数都可写成分数 令谓词Q(x):x是有理数 F(x):x可写成分数 则命题符号化为：(?x)(Q(x)?F(x)) 2.教室里有同学在讲话 S(x):x在教室里 T(x):x在讲话， 则符号化为：(?x)(S(x)∧T(x)) 3.并非每个实数都是有理数. 令:R(x):x是实数. Q(x):x是有理数. 则命题可符号化为: ??x(R(x)→Q(x)) ?x(R(x)∧?Q(x)) 4.尽管有些人聪明,但不是所有人聪明. 令:M(x):x是人. P(x):x聪明. 则命题可符号化为: ?x(M(x)∧P(x))∧??x(M(x)→P(x)) 5.没有一个耗子比任何象重. 令H(x):x