一个赋值必须满足整个公式
对于(p∨q)∧(¬p∨r)，p真、r真且q任意就是满足赋值。分别给每个子句找到互不相容的赋值并不够：相同变量在整个公式中必须保持同一个值。与之不同，永真性要求每个赋值都成立，而SAT只要求至少一个。
公式给定后，代入赋值并按照联结词计算即可核验。在有限命题输入上，穷举全部赋值总会结束，因此SAT可判定；“求解可能很慢”和“根本不存在总能回答的算法”是不同性质。
核验、归约与NP完全性
按公式编码长度计，满足赋值的长度和核验时间均有多项式上界，所以SAT属于NP。Cook–Levin定理的另一个方向是，任意NP判定问题都可经多项式时间转换成SAT实例，而且原问题为“是”恰好对应生成公式可满足。两个条件合起来才是NP完全性。
构造证明可先把验证计算表示成布尔电路，再为电路中的门设置变量，用子句约束它们忠实执行门运算，并要求输出为真。辅助变量记录中间值；它们使局部约束可以组合起来，而不是提前知道原问题的答案。
一般最坏情形与实际实例
NP完全不等于已证明每个SAT实例都要指数时间，也不表示现实求解器毫无用途。它说明若一般SAT存在多项式时间算法，就会有P=NP；截至所引课程资料，这仍是未解决的问题。性能还取决于编码、约束结构及求解策略。
2-SAT和命题霍恩公式具有可多项式求解的结构；一般3-SAT已经NP完全。软件验证等应用还需核对编码是否忠实：求得满足模型说明编码约束有解，不能自动保证模型之外的需求也成立。