Введение

В математике, булево кольцо R — это кольцо, для которого 1 = x² = x для всех x из R, то есть кольцо, состоящее только из идемпотентных элементов. Примером является кольцо целых чисел по модулю 2. Каждое булево кольцо порождает булеву алгебру, где умножение в кольце соответствует конъюнкции или пересечению ∧, а сложение в кольце — исключающему ИЛИ или симметрической разности (а не дизъюнкции ∨, которая образовала бы полукольцо). Обратно, каждая булева алгебра порождает булево кольцо. Булевы кольца названы в честь основателя булевой алгебры, Джорджа Буля.

Примеры

Одним из примеров булевого кольца является множество степеней любого множества X, где сложение в кольце — это симметрическая разность, а умножение — пересечение. В качестве другого примера можно также рассмотреть множество всех конечных или коконечных подмножеств X, с симметрической разностью и пересечением в качестве операций. В более общем случае, любое поле множеств с этими операциями является булевым кольцом. По теореме представления Стоуна, каждое булево кольцо изоморфно полю множеств, рассматриваемому как кольцо с этими операциями.

Объединение

Объединение в булевых кольцах является разрешимой задачей, то есть существуют алгоритмы для решения произвольных уравнений над булевыми кольцами. И объединение, и сопоставление в конечно порожденных свободных булевых кольцах являются NP-полными, и оба являются NP-трудными в конечно представленных булевых кольцах. (В действительности, поскольку любую задачу унификации вида 1=f(X) = g(X) в булевом кольце можно переписать как задачу сопоставления 1=f(X) + g(X) = 0, эти задачи эквивалентны.) Объединение в булевых кольцах является унитарным, если все неинтерпретированные символы функций являются нулевыми, и конечным в противном случае (то есть, если символы функций, не входящие в сигнатуру булевых колец, являются константами, то существует наиболее общий унификатор, а в противном случае минимальное полное множество унификаторов конечно).