可满足性

通常指一阶逻辑公式的一种性质。一个原子公式F(x，…，x)是可满足的，如果有一个个体域D，对F(x，…，x)中的自由个体变元x，…，x指定D中的元素a，…，a，对F指定D中元素间的一个n元关系F，使得F(a，…，a)是一个真命题。对于一个不是原子的公式A，A是可满足的，如果有一个个体域D，对A中的每个自由个体变元指定一个D中的个体为值，对A中每个n元谓词符号，指定D中的一个n元关系，并对A中的联结词和量词给以解释(如全称量词是指对D中的每一元素，存在量词是指有一个D中元素)，使得这样解释后得到的是一个真命题。例如，公式F(x，y)是可满足的，如取自然数集合为个体域，对x，y分别指定3，5为值，对F指定为关系＜，“3＜5”是一真命题。个体域D和使公式A成真的对A中符号的一个解释，称为A的一个模型。一般地是对一阶语言L定义模型，如果是L的一个模型，A是L的一个公式，满足A，记作A，就说公式A是可满足的。一阶语言L的一个公式集合Γ称为可满足的。如果有一个L的一个模型，满足Γ中的每一公式，即对每一A∈Γ，都有A。模型满足公式集合Γ，记作：Γ。

可满足性与协调性有深刻的联系。凡是可满足的公式集合都是协调的。另一方面，凡是协调的公式集也都是可满足的，这就是一阶逻辑的完全性。