三叉コピー - Summer498 の頭ん中

三叉コピー

3-bounded から 2-bounded にするには三叉コピーが欲しい

https://scrapbox.io/files/66527d73492002001cd7a05a.png

https://scrapbox.io/files/6652dd4b005b65001d4b52d1.png

$ (A\cdot B\cdot C)+(\overline A\cdot\overline B\cdot\overline C)

ABC が全て 1 になるか ABC が全て 0 になれば SAT

$ (A+\overline A)_{=\top}(A+\overline B)(A+\overline C)(B+\overline A)(B+\overline B)_{=\top}(B+\overline C)(C+\overline A)(C+\overline B)(C+\overline C)_{\top}

$ (A+\overline B)(B+\overline C)(C+\overline A)(C+\overline B)(B+\overline A)(A+\overline C)

$ (a+x)(\overline a+\overline x)(b+y)(\overline b+\overline y)(c+z)(\overline c+\overline z)$ (a+y)(b+z)(c+x)(c+y)(b+x)(a+z)

https://gyazo.com/56a3d81aa7fc103807aef0fca2315b89

https://scrapbox.io/files/6652dc3ddbc05f001d87f0f1.png

再帰的になっていて問題解決にはならない

試行錯誤の跡地

https://scrapbox.io/files/66534a38de67f8001c1a6dd2.png

https://scrapbox.io/files/6652e48d7f1f98001c575b32.png

https://scrapbox.io/files/6652f65b1d2436001d8a0820.png

https://scrapbox.io/files/6652f71a6bc5ce001c4f0afb.pngそんなわけない

https://scrapbox.io/files/6652f8395e171b001db18c97.png

https://scrapbox.io/files/6652f8c7378fc1001c5337a9.png

https://scrapbox.io/files/6652fa3c14d109001de58ec8.png

https://scrapbox.io/files/665308634c7361001c81ee00.png

https://scrapbox.io/files/6653179c1d5023001d6e9c23.png

https://scrapbox.io/files/665329e5863f70001c96b86b.png

https://gyazo.com/20e112c35ec79940972e7bcc378f115b

https://scrapbox.io/files/66532dcf06057b001d153aa4.png

1つ false が出るのは確定

情報量としては増えない事がわかる

https://scrapbox.io/files/66534424759500001ddd19f8.png

https://scrapbox.io/files/6653c50fd2766c001d5b840d.pngただし$ (a,b)=(1,1)のとき UnSAT

https://scrapbox.io/files/6653c5a0b725ae001c506bad.png

https://scrapbox.io/files/6653c75923e944001cc6509d.png

https://scrapbox.io/files/6653caf27e4258001cfe4139.png

https://scrapbox.io/files/6653cbb45decba001c94c1f3.png

https://scrapbox.io/files/6653cc460a4cb3001d69c114.png

https://scrapbox.io/files/6653e13a3bc7e1001c480c26.png

https://scrapbox.io/files/6653e363dd0b73001c43406f.png

https://scrapbox.io/files/66540303934c03001d9c0656.png

3 つ true にすると UnSAT になるガジェット

欲しい: 3 つとも同じ時のみ SAT のガジェット

https://scrapbox.io/files/665403c5cb394a001c576912.png

https://scrapbox.io/files/6654064c7a67ad001d188042.png

欲しい: イコール代入ガジェット

https://scrapbox.io/files/665406ea68f897001d3d8f37.png

→ 三角形ガジェット

https://scrapbox.io/files/665465f4d24aff001d224b1d.png

https://scrapbox.io/files/665468324a2288001d203a34.png

https://scrapbox.io/files/665469c65eab7a001dfb6bf2.png

https://scrapbox.io/files/665484b74b7828001c4ae0dc.png

https://scrapbox.io/files/66548705bb612c001d6e6734.png

https://scrapbox.io/files/665488c2134444001c7d1c97.png

https://scrapbox.io/files/6655737849f67f001df93f8b.png

https://scrapbox.io/files/6656e110ed9e31001ce0e658.png

https://scrapbox.io/files/6656e454bffabd001db87402.png

https://scrapbox.io/files/6657de59099042001c2ad569.png

ただの四角形ガジェット

https://scrapbox.io/files/66588d760223a3001dfe7f97.png

再帰的