56858b1bb91d034

http://nhiro.org.s3.amazonaws.com/d/4/d4422251caa2a7bebe4edcda7e765948.jpg https://gyazo.com/d4422251caa2a7bebe4edcda7e765948

(OCR text)

今回のラスボス: 3SAT

35

N個の二値変数がある。これを連言標準形で組み

合わせた論理式が与えられる。

論理式を充足するように各変数の真偽値を定めよ

連言標準形とは:

m個の節がandで結ばれており、

各節の中はorで結ばれている形。

1: (x1 or x2 or x3) and (x3 or not(x1) or x4)

今回は各節の中の変数が

最大3個とする(3SAT)