离散数学(修改).pptVIP

CHAPTER 1 The Foundations: Logic, Sets, and Functions 问题的提出与解决 客体、谓词与量词 谓词公式 命题的符号化 等价式与蕴含式 令S(x)表示x是大学生，a:小张，b:小李。 则： S(a): 小张是大学生； S(b): 小李是大学生。 从符号S(a)、S(b)可看出“都是大学生”的共性。 问题的提出与解决 客体、谓词与量词 谓词公式 命题的符号化 等价式与蕴含式 客体与客体变元 谓词与命题函数 谓词的量化及量词 客体与客体变元 谓词与命题函数 谓词的量化及量词 定义：谓词用来描述个体的性质或个体间的关系，用大写字母后加括号表示，括号内为客体变元。如果括号内有n个客体变元，称该谓词为n元谓词。 用 P(x1,x2,…,xn)表示n元谓词。 例 如： S(x):表示x是大学生。 一元谓词 G(x,y)：表示 xy。 二元谓词 B(x,y,z)：表示x在y与z之间。 三元谓词 用 P(x1,x2,…,xn)表示n元谓词。 n元谓词也称简单命题函数，将若干个简单命题函数用逻辑联结词联结起来，构成的表达式，称之为复合命题函数。 简单命题函数与复合命题函数统称为命题函数。 例如 给定简单命题函数： A(x)：x身体好，B(x)：x学习好， C(x)：x工作好. 则：复合命题函数 ?A(x)→(?B(x)∧?C(x)) 表示如果x身体不好，则x的学习与工作都不会好 定义：在命题函数中命题变元的取值范围， 称之为论域，也称之为个体域。 例如： S(x):x是大学生，论域是:人类。 G(x,y)：xy， 论域是:实数。 定义：由所有客体构成的论域，称之为全总个体域。它是个“最大”的论域。 约定: 对于一个命题函数，如果没有给定论域，则假定该论域是全总个体域。 客体与客体变元 谓词与命题函数 谓词的量化及量词 问题的提出与解决 客体、谓词与量词 谓词公式 命题的符号化 等价式与蕴含式 谓词演算公式 量词的辖域 约束变元与自由变元 约束变元的改名 定义 谓词演算的合式公式递归定义如下： 1.原子谓词公式是合式公式。 2.如果A是合式公式，则?A也是合式公式。 3.如果A、B是合式公式，则(A∧B)、(A∨B)、(A→B)、(A?B)都是合式公式。 4.如果A是合式公式，x是Ａ中的任何客体变元，则?xＡ和?xＡ也是合式公式。 5.只有有限次应用规则(1)至(4)得到的才是合式公式。 谓词演算公式 量词的辖域 约束变元与自由变元 约束变元的改名 定义 在谓词公式中，量词的作用范围称之为量词的作用域，也叫量词的辖域。 谓词演算公式 量词的辖域 约束变元与自由变元 约束变元的改名 例如，下面公式： ?x(F(x,y)→?yP(y))∧Q(z) Ｆ(x,y)中的x在?x的辖域内，受?x约束，y不受?x约束。 P(y)中的y在?y的辖域内，受?y约束。 Q(z)中的z不受量词约束。 说明 (1)对约束变元用什么符号表示无关紧要。 就是说?xA(x)与?yA(y)是一样的。 (2)一个谓词公式如果无自由变元，它就表示一个命题。 例如： A(x)表示x是个大学生。?xA(x)或者?xA(x)就是个命题了，因为它们分别表示命题“有些人是大学生”和“所有人都是大学生”。 (3) 一个n元谓词P(x1,x2,…,xn)，若在前边添加k个量词，使其中的 k个客体变元变成约束变元，则此 n元谓词就变成了n-k元谓词。 例如P(x,y,z)表示x+y=z，论域是整数集。 ?x?yP(x,y,z)表示“？” （思考） 如果令 z=1，则?x?yP(x,y,1)就变成了命题 可见给z指定整数a后，?x?yP(x,y,a)就变成了一个命题。所以谓词公式?x?yP(x,y,z)就相当于只含有客体变元 z的一元谓词了。 谓词演算公式 量词的辖域 约束变元与自由变元 约束变元的改名