В математике булево кольцо R — это кольцо , для которого x2 = 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]