离散数学(DiscreteMathematics2.2一阶逻辑合式公式及解释2026/3/15
2026/3/15 1 离散数学(Discrete Mathematics) 2.2一阶逻辑合式公式及解释
字母表定义字母表包含下述符号：(1) 个体常项 a,b, c, ..., a, bi, Ci, ., i≥1(2) 个体变项: x,y, z, ... X,yi, zi .. i≥1(3)函数符号：f,g, h, ..,f,gi, h,.,i≥1(4)谓词符号:F,G,H, ..., F, G, H,..,i≥1(5)量词符号：V,3(6) 联结词符号： ,^,V,→,(7)括号与逗号：（)，，2026/3/15计算机科学与工程系2
2026/3/15 计算机科学与工程系 2 字母表 定义 字母表包含下述符号： (1) 个体常项：a, b, c, ., ai , bi , ci , ., i 1 (2) 个体变项：x, y, z, ., xi , yi , zi , ., i 1 (3) 函数符号：f, g, h, ., f i , gi , hi , ., i 1 (4) 谓词符号：F, G, H, ., Fi , Gi , Hi , ., i 1 (5) 量词符号：, (6) 联结词符号：, , , →, (7) 括号与逗号：(, ),
项定义 项的定义如下：(1)个体常项和个体变项是项(2)若p(x1,X2,……, xn)是任意的n元函数，ti,t2.…,fn是任意的n个项，则p(t,t2，…,t)是项.(3)所有的项都是有限次使用(1),(2)得到的.个体常项、变项是项，由它们构成的n元函数和复合函数还是项2026/3/15计算机科学与工程系3
2026/3/15 计算机科学与工程系 3 项 定义 项的定义如下： (1) 个体常项和个体变项是项. (2) 若(x1 , x2 , ., xn )是任意的n元函数，t 1 ,t 2 ,.,tn 是任意的n个项，则(t 1 , t 2 , ., tn ) 是项. (3) 所有的项都是有限次使用 (1), (2) 得到的. 个体常项、变项是项，由它们构成的n元函数和复 合函数还是项
原子公式定义设R(x1,X2,…, xn)是任意的n元谓词，ti,f2… tn是任意的n个项，则称R(tj,t2，…,t,)是原子公式.原子公式是由项组成的n元谓词例如，F(xy),F(f(x1,x2),g(x3xx)等均为原子公式2026/3/15计算机科学与工程系4
2026/3/15 计算机科学与工程系 4 原子公式 定义 设R(x1 , x2 , ., xn )是任意的n元谓词，t 1 ,t 2 ,., tn 是任意的n个项，则称R(t 1 , t 2 , ., tn )是原子公式. 原子公式是由项组成的n元谓词. 例如，F(x,y), F(f(x1 ,x2 ),g(x3 ,x4 ))等均为原子公式
第二章谓词逻辑（PredicateLogic）定义2.4谓词演算的合式公式，可由下述各条组成：（1）原子公式是合式公式。（2）若A是合式公式，则(A)也是合式公式。(3）若A，B是合式公式，则(A ^B)，(AV B),(A→B)，(A台B)也是合式公式。（4）若A是合式公式，x是A中出现的任何变元则(Vx)A和(3x)A也是合式公式。(5)只有有限次应用(1)~(4)得到的公式是合式公式2026/3/15计算机科学与工程系5
2026/3/15 计算机科学与工程系 5 第二章 谓词逻辑（Predicate Logic） 定义2.4谓词演算的合式公式,可由下述各条组成: （1）原子公式是合式公式。 （2）若A是合式公式，则(A)也是合式公式。 （3）若A，B是合式公式，则(A ∧ B)，(A ∨ B)， (A → B)，(A B)也是合式公式。 （4）若A是合式公式，x是A中出现的任何变元, 则(x)A和 (x)A也是合式公式。 (5)只有有限次应用(1)~(4)得到的公式是合式公式