TRUEガジェット
https://gyazo.com/e83e6c91ae1e343578ef742a66406b25
from SAT の色んなガジェット
TRUEガジェット
節同士が1変数のみ共有する + exactly 3 に縛ったときに定数を作れるおそらく最小のガジェット
三角形付加三角形の同じ値を取る変数$ f_1,f_2を 1 つの節$ Cに入れて束縛すると、同時に True を取れなくなって False が確定する
そして$ Cの残りの変数 $ tが True と確定する
$ f_1, f_2 と同じ値を取る三角形付加三角形の変数 $ f_3 も False が確定するので、三角形付加三角形の他の変数 $ x_1, x_2 が $ x_1 = \lnot{x}_2 の関係にあることがわかる
]https://gyazo.com/2a3cf4178557152302413293092c3ae6
グリッド上に描くとき、辺の長さが足りないため、辺の長さを 1 に縛ると レンガ状 や checker-grid 上には描けない
? 辺の長さを 1 に縛るとき、checker-grid 上の FALSE は存在するか？
正平面2上界1-in-3 SAT 版
https://gyazo.com/e83e6c91ae1e343578ef742a66406b25
三角形付加三角形による証明
https://scrapbox.io/files/665023fcc93ecf001d27eb7f.png
三角形付加三角形部分は三角形ガジェットによる証明に帰着できる
https://gyazo.com/122a3a41c694acb89166b673d676a796