2.2 一阶逻辑谓词公式及解释
简单命题函数+ 逻辑联结词?谓词表达式
问题：怎样的谓词表达式才能成为谓词公式，并能进行逻辑演算？
2006-3-16电子工程学院，离散数学1
2.2.1 合式公式与翻译
定义2.4在形式化中，我们将使用如下7种符号：1.个体常项：用小写英文字母a，b，c，…表示，当个体域D给出时，它可以是D中某个元素。
2.个体变项：用小写英文字母x，y，z，…表示，当个体域D给出时，D中任意元素可代入个体变项。
3.函数符号：用小写英文字母f，g，…表示，当个体域D给出时，n元函数符号f(x1，…，xn)可以是Dn到D的任意一个映射。
4.谓词符号：用大写英文字母F，G，H，…表示，当个体域D给出时，n元谓词符号F(x1，…，xn)可以是Dn上的任意一个谓词。
2006-3-16
电子工程学院，离散数学
2
2.2.1 合式公式与翻译
5.量词符号：?，?
6.联结词符号：?，∧，∨，→，?7.括号和逗号：（、）、，
定义2.5谓词逻辑中的项，被递归定义为：1.个体常项是项；2.个体变项是项；
3.若?(x1, …, xn)是n元函数，t1, …, tn是项，则?(t1, …, tn)也是项；
4.所有项都是有限次使用1、2、3、生成的符号串才是项。
2006-3-16
电子工程学院，离散数学
3
2.2.1 合式公式与翻译——说明
1.有了项的定义，函数的概念就可用来表示个体常项和个体变项。如：P(x)：x是教授，f(x)：x的父亲，a：张三，那么P(f(a))则表示：“张三的父亲是教授”2.函数的使用给谓词表示带来很大的方便。如：用谓词表示命题：对任意的整数x，x2 –1=(x+1)(x-1)是恒等式。
令：I(x)：x是整数，f(x)=x2 –1，g(x)= (x+1)(x-1)，E(x,y)：x=y，则该命题可表示为：?x(I(x)→E(f(x), g(x)))
2006-3-16
电子工程学院，离散数学
4
2.2.1 合式公式与翻译
定义2.6若R(x1,…, xn)是n元谓词符号，t1,…,tn是项，则R(t1,…, tn)是原子（谓词）公式。
定义2.7谓词演算的合式公式，被递归定义如下：1.原子公式是合式公式；
2.若A，B是公式，则(?A)，(A ∨B)，( A ∧B)，(A→B)，(A?B)也是合式公式；
3.若A是公式，x是A中的自由变项，则?xA，?xA也是合式公式；
4.只有有限次地使用1～3构成的符号串才也是合式公式。
2006-3-16
电子工程学院，离散数学
5
离散数学 第五讲
