离散数学(杨圣洪版)-第2章-复习总结.ppt

离散数学 第2章 复习总结 1. 基本概念 1、谓词 用W表示“要喝水”，用H表示“喜欢帅哥”。 这些表示谓语部分的大写字母，称为“谓词”。 2、个体常元 如a表示“刘翔”，c表示“姚明”， 表示具体个体的小写字母，称为“个体常元”或个体常量，用字母表中靠前的字母表示常量。 3、个体变元 “某某要喝水”表示为W(x)，x泛指所有的人，这些小字字母称为“个体变元”。 4、全称量词 符号“?”，表示“所有”，称为全称量词。 5、存在量词 符号“?”，表示“存在，有些、有部分”等的含义。 6、谓词公式 将单个谓词公式如W(x)，带量词的谓词如?zM(z)，统称为“谓词公式”。 例题 例5 表示“所有人都要变老的，杨圣洪是人，所以杨圣洪也会变老的”。 解：个体域为全总个体域，即对个体变元的取值不做任何限。 H(x)表示对象x是人类， O(x)表示对象x变老， c表示个体常元“杨圣洪”，则 H(c)表示个体常元杨圣洪是人类， O(c)表示个体常元杨圣洪要变老，原句表示 (?x(H(x)?O(x))?H(c))?O(c)。 1. 基本概念 7、项的定义：个体常元与变元及其函数式为项。 (1)个体常元和个体变元是项。 (2)若?(x1,x2,…, xn)是n元函数,t1,t2,…tn是n个项,则?(t1,t2,…, tn)是项。 (3)有限次使用(2)得到的表达式是项。 8、原子公式： 设R(x1,x2,…,xn)是n元谓词，t1,t2,…,tn是项，则R(t1,t2,…, tn)是原子公式。 9、合式谓词公式： (1)原子公式是合式公式； (2)若A是合式公式，则(?A)也是合式公式； (3)若A,B合式，则A?B, A?B, A?B , A?B 合式 (4)若A合式，则?xA、? xA合式 (5)有限次使用(2)~(4)得到的式子是合式。 1. 基本概念 10、量词的指导变元与辖域，变元的约束出现、自由出现 (1) 量词指导变元：?xA和?xA中的x (2) 量词辖域：?xA和?xA中的A为量词?/?辖域 (3) 变元的约束出现：指导变元的每次出现(称约束变元)。 (4) 变元的自由出现：不是约束出现的变元(称自由变元) 。 11、闭公式： 不含自由变元的谓词公式 。 12、谓词公式的类型 永真式(逻辑有效式): 在任何解释下均为真； 永假式(矛盾式): 在任何解释下均为假； 可满足式: 至少存在一种解释下为真； 例题 例题 分析?x?y(P(x,y)?Q(y,z))??xP(x,y)作用域与变元约束情况 解：?x、?y的作用域是(P(x,y)?Q(y,z))， ?x的作用域是P(x,y)。 将与自由变元同名约束变元y?r， 将与前一个同名约束变元x?s，则原公式 ?x?r(P(x,r)?Q(r,z))??sP(s,y) 改名规则：一般仅对约束变元改名, 后出现者约束变元也要改名。 1. 基本概念 13、代换实例： 设A0是含命题变元p1,p2,...,pn的命题公式，A1,A2,...,An是n个谓词公式(其中个体常元/变元/函数/谓词公式都未确定含义)，将A0中pi的每次出现都换成Ai，所得公式A称为A0的代换实例。 2. 谓词公式真值 方法：个体常元的值、个体变元的值域、确定函数、谓词公式的含义。 例题 例题：?x?y (F(x)?F(y)?G(x,y)?H(f(x,y),g(x,y)) f(x,y),g(x,y)是函数变元，一元谓词公式F(x),二元谓词G与H。 x与y的个体域：全总个体域。 F(x):x是实数 G(x,y):x?y H(x,y):xy f(x,y)=x2+y2 g(x,y)=2xy 这时整个公式的含义： 对于任意的x和y，若x与y是实数且x?y，那么x2+y2 2xy ，其真值为1. 3. 谓词公式等值演算 定义1 设A、B是两个合法的谓词公式,如果在任何解释下两个公式的真值都相等，则称A与B等值记为A?B。 定义2 设A、B是两个合法谓词公式，如果在任何解释下，A?B为永真式，则A与B等值，记为A?B。 3. 谓词公式等值演算 1、?xA(x) ?A(a1)?A(a2)?… ?A(an) 个体域为有限 ?xA(x) ?A(a1)?A(a2) ?… ?A(