3CNF論理式
全ての節が3つのリテラルを持つ
連言標準形
の論理式
ex.
$ (x_1\lor \overline{x_2}\lor\overline{x_3})\land(x_3\lor\overline{x_5} \lor x_6)\land(x_3\lor\overline{x_6}\lor x_4)\land(x_4\lor x_5\lor x_6)