离散数学9讲.pptVIP

离散数学 第9讲 回顾上节课重要知识点： 一阶逻辑的定义； 一阶逻辑中命题的符号化问题。 离散数学 第9讲 本讲基本知识点： 4.2 一阶逻辑公式及解释 第四章 一阶逻辑基本概念 4.2 一阶逻辑公式及解释 定义4.1 一阶语言￡的字母表定义如下： （1）个体常项：a , b , c ,…, ai , bi , ci…，i ≥1. （2）个体变项：x , y , z ,…, xi , yi , zi…，i ≥1. （3）函数符号：f , g , h ,…, fi , gi , hi…，i ≥1. （4）谓词符号：F , G , H,…,Fi , Gi , Hi…，i ≥1. （5）量词符号： ? ， ? . （6）联结词符号： ?，∧，∨，?，?. （7）括号与逗号： （，），，. 第四章 一阶逻辑基本概念 定义4.2 一阶语言￡的项的定义如下： （1）个体常项和个体变项是项 （2）若φ(x1 , x2 ,… xn ) 是任意的n元函数， t1 , t2 ,… tn 是任意的n个项，则φ(t1 , t2 ,… tn )是项。 （3）所有的项都是有限次使用（1），（2）得到的。 定义4.3 若R(x1 , x2 ,… xn )是￡的任意n元谓词， t1 , t2 ,… tn 是￡的任意的n个项，则称R(t1 , t2 ,… tn ) ￡的原子公式。 第四章 一阶逻辑基本概念 定义4.4 ￡的合式公式/谓词公式/公式定义如下： （1）原子公式是合式公式。 （2）若A 是合式公式，则(?A)也是合式公式。 （3）若A，B是合式公式，则(A ∧ B)，(A ∨ B)，(A ? B)，(A ? B)也是合式公式。 （4）若A是合式公式，则?x A , ?x B，也是合式公式。 (5)只有有限次应用(1)~(4)构成的符号串才是合式公式(谓词公式)。 第四章 一阶逻辑基本概念 定义4.5 在公式?x A和?x B中，称x为指导变元，A为相应量词的辖域。 在?x 和?x的辖域中，x的所有出现都称为约束出现，A中不是约束出现的其它变项均称为是自由出现的。 例： 1、?x( H(x,y)??y(W(y) ∧ L(x,y,z))) 2、 ?x( H(x)?W(y)) ? ?y( F(x) ∧L(x,y,z)) 练习:习题四第8题. 第四章 一阶逻辑基本概念 8、（1） ?x(F(x)? G(x,y)) x是指导变元，量词?的辖域A= (F(x)? G(x,y)), 在A 内，x是约束出现两次，y是自由出现一次。 （2）?x F(x,y) ? ? y G(x,y) x是指导变元，量词?的辖域A= F(x,y), 在A 内，x是约束出现一次，y是自由出现一次;同时，y也是指导变元，量词? 的辖域B= G(x,y), 在B 内，y是约束出现一次，x是自由出现一次 （3）?x ? y (F(x,y) ∧ G(y,z)) ∨ ? x H(x,y,z) x、y是指导变元，对应量词?、 ?的辖域为 (F(x,y) ∧ G(y,z)) , 其中x是约束出现一次，y是约束出现两次,z是自由出现一次;后一个x也是指导变元，量词? 的辖域为 G(x,y), 其中x是约束出现一次，y、z是自由出现一次. 第四章 一阶逻辑基本概念 本书约定 A (x1 , x2 ,… xn )是表示含x1 , x2 ,… xn自由出现的公式。 △x1 A(x1 , x2 ,… xn )是表示含x2 ,… xn自由出现的公式,记作A1 (x2 , x3 , … xn )。类似的， △x2 △x1 A(x1 , x2 ,… xn )可记作A2 (x3 , x4 , … xn )。 △xn-1 △xn-2 … △x1 A(x1 , x2 ,… xn )可记作An (xn )。 其中△表示任意的量词（ ? 或 ? ）。 第四章 一阶逻辑基本概念 定义4.6 设A 是任意的公式，若A中不含自由出现的个体变项，则称A为封闭的公式，简称为闭式。 合式公式的解释:指将公式中的变项（项的变项、谓词的变项等）用指定的常项代替，使所的公式具备一定的意义（有时就变成了命题）。 例4.7。 第四章 一阶逻辑基本概念 定义4.7 ￡的解释 ￡的一个解释I由下列4部分组成： (1)非空个体域DI。 (2)DI中一些特定元素的集合{a1,a2,…ai,…}. (3)DI上特定函数集合{fin|i,n ≥ 1}. (4)DI上特定谓词的集合{Fin|i,n ≥ 1}. 所谓一个解释不外乎指定个体域、个体域中一些特定的元素、特定的函数和谓词等。 第四章 一阶逻辑基本概念 参见例4.8 练习：给定解释I如下： (1)DI={2,3}； (2)DI中的特定元素a=2； (3)DI上的