Satisfiability Problem(SAT)について - Qiita

リテラル リテラル...論理変数($x_1$)またはその否定($\bar{x_1}$)のこと 節 節...リテラルの論理和のこと 問題の例 $f = (x_1 ∨ x_2 ∨ \bar{x_3}) ∧ (\bar{x_1} ∨x_3) ∧ (\bar{x_2} ∨ x_3)$に対して$f$が真となるような$x_1, x_2, x_3$の真偽値の組み合わせは存在するか? 存在する例 $x_1 = 1, x_2 = 1, x_3 = 1$の場合満たされる 理由 第一節$(x_1 ∨ x_2 ∨ \bar{x_3})$,第二節$(\bar{x_1} ∨x_3)$,第三節$(\bar{x_2} ∨ x_3)$に注目する 第一節について,これは$1∨ 1∨ 0$となるので第一節は真 第二節について,これは$0 ∨ 1$となるので第二節は真 第三節について,これは$0∨ 1$となるので第三節は真 した