可判定的问题

能够用一个能行过程确定任给一对象是否属于某类或具有某一性质的问题(参看判定问题)。以下是文献中常提到的一些可判定问题的例子。

1．命题逻辑是可判定的，即：存在一个能行过程能在有穷步内确定任何一个命题公式是否重言式(定理)，(例如，真值表方法就是一个这样的能行方法。)

2．只含一元谓词符号的一阶逻辑公式的可满足性和有效性都是可判定的。

3．形如x…xy…yα(α中无量词)的一阶逻辑公式(司寇伦范式)的可满足性是可判定的(但其有效性是不可判定的)。

4．形如x…xy…yα(α中无量词)的一阶逻辑公式(司寇伦范式)的有效性是可判定的(但其可满足性是不可判定的)。

5．常用的模态逻辑系统(如T，S，S)都是可判定的(参见模态逻辑)。

6．常用的时态逻辑的命题系统都是可判定的(参见时态逻辑)。

7．直觉主义的命题逻辑系统是可判定的(参见直觉主义逻辑)。

8．交换群(阿贝尔群)论是可判定的。

9．实数域理论是可判定的。

l0．初等几何是可判定的。

(参见判定问题和不可判定的问题。)