真偽値の変数 , およびその否定 をリテラルという。リテラル, およびリテラルを論理和 で繋げた論理式を節という。さらに, 節, および節を論理積 で繋げた論理式を節形式という。例えば, , はリテラル, , , は節, , , , は節形式。 変数 からなる節形式 があるとき, 写像 を の割当という。どんな割当についても真となる節形式 は恒真であるという。また, が真となるような割当が存在するとき, 節形式 は充足可能であるという。例えば, 節形式 は恒真である。 節形式 は充足可能である。実際, , , という割当は を充足する。 しかし, 節形式 は充足可能でない。後ろの二つのリテラル…