合式公式

合式公式

符号串
命题公式是由命题常项、命题变项、联结词、括号等组成的符号串,但不是由这些符号任意组成的符号串都是命题公式。因此,必须给出命题公式的严格定义。今后我们将合式公式称为命题公式,或简称为公式。在公式的定义中,引进了A,B等符号,它们代表任意的命题公式,称它们为元语言符号。[1]例用定义说明是公式。
  • 中文名:合式公式
  • 外文名:well-formed formula
  • 别名:谓词公式
  • 要求:给出命题公式的严格定义
  • 组成:命题常项、命题变项
  • 简称:公式
  • 定义:按一定规则构成的表达式

基本内容

若用,…表示真值确定的简单命题,则称,…为命题常项,命题常项的真值是确定不变的,不是为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的恒真性。

相关词条

相关搜索

其它词条