基本内容
若用,…表示真值确定的简单命题,则称,…为命题常项,命题常项的真值是确定不变的,不是为1,就是为0。
若用,…泛指简单的陈述句,则称,…为命题变项,此时,…是变量,它们的取值为1或0。
定义1.6
(1)单个命题常项或变项是合式公式;
(2)如果A是合式公式,则也是合式公式;
(3)如果A,B是合式公式,则,,,也是合式公式;
(4)只有有限次地应用(1)~(3)组成的符号串才是合式公式。
为方便起见,规定,等的外层括号可以省去。
根据定义,,,等都是命题公式,但等都不是命题公式。
所谓元语言,是用来说明对象语言的语言,而对象语言是指用来描述所研究的对象(指数理逻辑)的语言。
相关知识
为了使一阶逻辑中命题符号化更准确和规范,以便正确进行谓词演算和推理,引进一阶逻辑中合式公式的概念.nn在形式化中,将使用以下四类符号。nn(1)常量符号:,当论域D给出时,它可以是D中的某个元素;nn(2)变量符号:,当论域D给出时,它可以是D中的任何一个元素;nn(3)函数符号::,当论域D给出时,n元函数符号可以是到的任意一个映射;nn(4)谓词符号:,当论域D给出时,n元谓词符号可以是到{1,0}的任意一个谓词。nn定义1一阶逻辑中的项(item),被递归定义如下:nn(1)常量符号是项;nn(2)变量符号是项;nn(3)若是n元函数符号,是项,则是项;nn(4)只有有限次地使用(1)、(2)、(3)所生成的符号串才是项。nn例如a,b,x,y是项,,是项,也是项。nn定义2设是n元谓词,是项,则称为原子公式,或简称原子。
约束变量和自由变量
在一个谓词公式中.变量的出现是约束的(bound),当且仅当它出现在使用这个变量的量词作用范围(称为作用域)之内;变量的出现是自由的(free),当且仅当它的出现不是约束的;至少有一次约束出现的变量称为约束变量(bound variable),至少有一次自由出现的变量称为自由变量(free variable)。
为了避免公式中有些变量既可以约束出现,又可自由出现的情形,我们可采用以下两条规则。nn改名规则:将谓词公式中出现的约束变量改为另一个约束变量,这种改名必须在量词作用域内各处以及该量词符号中进行,并且改成的新约束变量要有别于改名区域中的所有其他变量。
基本分类
设G是一个谓词公式,nn(1)如果存在解释,使在下为真(简称满足),则称是可满足的;nn(2)如果所有解释均不满足,(简称弄假),则称为恒假的,或不可满足的;nn(3)如果的所有解释都满足,则称为恒真的。nn如果一阶逻辑中的恒真(恒假)公式,要求所有解释均满足(弄假)该公式,而解释依赖一个非空个体集合D,又集合D可以是无穷集合,而集合D的“数目”也可以有无穷多个,因此,所谓公式的“所有”解释,实际上是很难考虑的,这就使得一阶逻辑中公式的恒真、恒假性的判定异常困难。Church和Turing分别于1936年独立地证明了:对于一阶逻辑,判定问题是不可解的,即不存在一个统一的算法A,该算法与谓词公式无关,使得对一阶逻辑中的任何谓词公式G,A能够在有限步内判定公式G的类型。nn但是,一阶逻辑是半可判定的,即如果谓词公式G是恒真的,有算法在有限步内检验出G的恒真性。


















