TL;DR
命題論理式が与えられたとき、式に含まれる変数に真か偽を割り当てて、式全体を真にできる割り当てが存在するかどうか、という問題である。
仕組み
Wikipedia によると、論理式は、節（リテラルの論理和）の論理積からなる連言標準形（CNF）で与えることが多い。各節のリテラルが高々 3 つのものを 3-SAT と呼ぶ。任意の論理式の充足可能性問題は NP 完全であり、充足可能性問題を多項式時間で変形して、さまざまな NP 完全問題を作れる。
例
は、 を真、 を偽にすると真になるので、充足可能である。一方、 は、どう割り当てても偽になるので、充足不能である。
注意点
論理式の範囲を述語論理式に広げると、ゲーデルの不完全性定理により、充足可能性問題は決定不能になる。