В математике булево кольцо R — это кольцо , для которого x 2 = x для всех x в R , то есть кольцо, состоящее только из идемпотентных элементов . [1] [2] [3] Примером является кольцо целых чисел по модулю 2 .
Каждое булево кольцо порождает булеву алгебру , в которой умножение колец соответствует конъюнкции или встрече ∧ , а добавление колец — исключительной дизъюнкции или симметричной разности (а не дизъюнкции ∨ , [4] которая образует полукольцо ). И наоборот, каждая булева алгебра порождает булево кольцо. Булевы кольца названы в честь основателя булевой алгебры Джорджа Буля .
Существует как минимум четыре различных и несовместимых системы обозначений булевых колец и алгебр:
Исторически термин «булевое кольцо» использовался для обозначения «булева кольца, возможно, без единицы», а «булева алгебра» использовался для обозначения булевого кольца с единицей. Существование тождества необходимо для того, чтобы рассматривать кольцо как алгебру над полем из двух элементов : в противном случае не может быть (унитального) кольцевого гомоморфизма поля из двух элементов в булево кольцо. (Это то же самое, что и старое использование терминов «кольцо» и «алгебра» в теории меры . [a] ) .
Одним из примеров булевого кольца является набор степеней любого множества X , где сложение в кольце представляет собой симметричную разность , а умножение — это пересечение . В качестве другого примера мы также можем рассмотреть набор всех конечных или коконитных подмножеств X , опять же с симметричной разницей и пересечением в качестве операций. В более общем смысле с помощью этих операций любое поле множеств представляет собой булево кольцо. По теореме Стоуна о представлении каждое булево кольцо изоморфно полю множеств (рассматриваемому как кольцо с этими операциями).
Поскольку операция соединения ∨ в булевой алгебре часто записывается аддитивно, в этом контексте имеет смысл обозначать сложение колец символом ⊕ , который часто используется для обозначения исключающего или .
Учитывая булево кольцо R , для x и y в R мы можем определить
Затем эти операции удовлетворяют всем аксиомам встреч, объединений и дополнений в булевой алгебре . Таким образом, каждое булево кольцо становится булевой алгеброй. Аналогично, каждая булева алгебра становится булевым кольцом таким образом:
Если таким образом булево кольцо перевести в булеву алгебру, а затем булеву алгебру перевести в кольцо, результатом будет исходное кольцо. Аналогичный результат справедлив, начиная с булевой алгебры.
Отображение между двумя булевыми кольцами является гомоморфизмом колец тогда и только тогда, когда оно является гомоморфизмом соответствующих булевых алгебр. Более того, подмножество булева кольца является кольцевым идеалом (первичный идеал кольца, максимальный идеал кольца) тогда и только тогда, когда оно является идеалом порядка (идеалом простого порядка, идеалом максимального порядка) булевой алгебры. Фактор -кольцо булевого кольца по модулю кольцевого идеала соответствует фактор-алгебре соответствующей булевой алгебры по модулю соответствующего идеала порядка.
Каждое булево кольцо R удовлетворяет условию x ⊕ x = 0 для всех x в R , поскольку мы знаем
и поскольку ( R , ⊕) — абелева группа, мы можем вычесть x ⊕ x из обеих частей этого уравнения, что дает x ⊕ x = 0 . Аналогичное доказательство показывает, что каждое булево кольцо коммутативно :
Свойство x ⊕ x = 0 показывает, что любое булево кольцо является ассоциативной алгеброй над полем F 2 с двумя элементами ровно одним способом. [ нужна цитата ] В частности, любое конечное булево кольцо имеет мощность , равную степени двойки . Не каждая ассоциативная алгебра с единицей над F 2 является булевым кольцом: рассмотрим, например, кольцо полиномов F 2 [ X ] .
Факторкольцо R / I любого булевого кольца R по модулю любого идеала I снова является булевым кольцом. Аналогично, любое подкольцо булева кольца является булевым кольцом.
Любая локализация RS −1 булевого кольца R множеством S ⊆ R является булевым кольцом, поскольку каждый элемент в локализации идемпотентен.
Максимальное кольцо частных Q ( R ) (в смысле Утуми и Ламбека ) булевого кольца R является булевым кольцом, поскольку всякий частичный эндоморфизм идемпотентен. [6]
Каждый простой идеал P в булевом кольце R является максимальным : факторкольцо R / P является областью целостности , а также булевым кольцом, поэтому оно изоморфно полю F 2 , что показывает максимальность P . Поскольку максимальные идеалы всегда просты, в булевых кольцах простые идеалы и максимальные идеалы совпадают.
Каждый конечно порожденный идеал булевого кольца является главным (действительно, ( x , y ) = ( x + y + xy ) ) . Более того, поскольку все элементы являются идемпотентами, булевы кольца являются коммутативными регулярными кольцами фон Неймана и, следовательно, абсолютно плоскими, что означает, что каждый модуль над ними плоский .
Унификация в булевых кольцах разрешима , [7] то есть существуют алгоритмы для решения произвольных уравнений над булевыми кольцами. И объединение, и сопоставление в конечно порожденных свободных булевых кольцах NP-полны , и оба NP-трудны в конечно определенных булевых кольцах. [8] (Фактически, поскольку любую проблему объединения f ( X ) = g ( X ) в булевом кольце можно переписать как задачу согласования f ( X ) + g ( X ) = 0 , эти проблемы эквивалентны.)
Унификация в булевых кольцах является унитарной, если все неинтерпретированные функциональные символы являются нулевыми и финитными в противном случае (т. е. если функциональные символы, не встречающиеся в сигнатуре булевых колец, все являются константами, то существует наиболее общий унификатор , а в противном случае — минимальный полный набор унификаторов). конечно). [9]