Jelaskan Unifikasi/Penyatuan dari Gelanggang Boolean

Unifikasi pada gelanggang Boolean adalah desidabilitas, yaitu, algoritma untuk menyelesaikan persamaan arbitrer pada gelanggang Boolean. Baik penyatuan dan pencocokan dalam hingga gelanggang Boolean bebas adalah kelengkapan-NP, dan keduanya NP-hard dalam kesajian-hingga ring Boolean. (faktanya, karena setiap masalah penyatuan f(X) = g(X) dalam gelanggang Boolean apabila ditulis sebagai masalah pencocokan f(' 'X) + g(X'') = 0, soalnya ekuivalen).

Unifikasi dalam gelanggang Boolean adalah satuan jika semua simbol fungsi yang tidak diinterpretasikan adalah nullari dan finiter jika tidak (yaitu jika simbol fungsi yang tidak muncul dalam tanda tangan gelanggang Boolean semuanya adalah konstanta, maka apabila unifikasi generalisasi umum, dan jika tidak, himpunan kelengkapan minimal unifikasi hingga).