Булево кольцо

В математике R булево кольцо — это кольцо , для которого x ² = x для всех x в R , то есть кольцо, состоящее только из идемпотентных элементов . Примером может служить кольцо целых чисел по модулю 2 .

Каждое булево кольцо порождает булеву алгебру , в которой умножение колец соответствует конъюнкции или встрече ∧ , а добавление колец — исключительной дизъюнкции или симметричной разности (не дизъюнкции ∨ , которое представляло бы собой полукольцо ). И наоборот, каждая булева алгебра порождает булево кольцо. Булевы кольца названы в честь основателя булевой алгебры Джорджа Буля .

Обозначения

Существует как минимум четыре различных и несовместимых системы обозначений булевых колец и алгебр:

• В коммутативной алгебре стандартными обозначениями являются использование x + y = ( x ∧ ¬ y ) ∨ (¬ x ∧ y ) для кольцевой суммы x и y и использование xy = x ∧ y для их произведения.
• В логике общепринятым обозначением является использование x ∧ y для соединения (так же, как кольцевое произведение) и использование x ∨ y для соединения, заданного в терминах кольцевой нотации (приведенной чуть выше) как x + y + xy .
• В теории множеств и логике также принято использовать x · y для соединения и x + y для соединения x ∨ y . Такое использование + отличается от использования в теории колец.
• Редким соглашением является использование xy для произведения и x ⊕ y для кольцевой суммы, чтобы избежать двусмысленности + .

Исторически термин «булевое кольцо» использовался для обозначения «булева кольца, возможно, без единицы», а «булева алгебра» использовался для обозначения булевого кольца с единицей. Существование тождества необходимо для того, чтобы рассматривать кольцо как алгебру над полем из двух элементов : в противном случае не может быть (унитального) кольцевого гомоморфизма поля из двух элементов в булево кольцо. (Это то же самое, что и старое использование терминов «кольцо» и «алгебра» в теории меры . )

Примеры

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

Связь

Диаграммы Венна для булевых операций соединения, дизъюнкции и дополнения.

Поскольку операция соединения ∨ в булевой алгебре часто записывается аддитивно, в этом контексте имеет смысл обозначать сложение колец символом ⊕ , который часто используется для обозначения исключающего или .

Учитывая булево кольцо R , для x и y в R мы можем определить

Икс ∧ у = ху ,

Икс ∨ y знак равно Икс ⊕ y ⊕ xy ,

¬ Икс знак равно 1 ⊕ Икс .

Затем эти операции удовлетворяют всем аксиомам встреч, объединений и дополнений в булевой алгебре . Таким образом, каждое булево кольцо становится булевой алгеброй. Аналогично, каждая булева алгебра становится булевым кольцом таким образом:

ху знак равно Икс ∧ у ,

Икс ⊕ у знак равно ( Икс ∨ у ) ∧ ¬( Икс ∧ у ).

Если таким образом булево кольцо перевести в булеву алгебру, а затем булеву алгебру перевести в кольцо, результатом будет исходное кольцо. Аналогичный результат справедлив, начиная с булевой алгебры.

Отображение между двумя булевыми кольцами является кольцевым гомоморфизмом тогда и только тогда, когда оно является гомоморфизмом соответствующих булевых алгебр. Более того, подмножество булева кольца является кольцевым идеалом (первичный идеал кольца, максимальный идеал кольца) тогда и только тогда, когда оно является идеалом порядка (идеалом простого порядка, идеалом максимального порядка) булевой алгебры. Фактор -кольцо булевого кольца по модулю кольцевого идеала соответствует фактор-алгебре соответствующей булевой алгебры по модулю соответствующего идеала порядка.

Свойства логических колец

Каждое булево кольцо R удовлетворяет условию x ⊕ x = 0 для всех x в R , поскольку мы знаем

Икс ⊕ Икс знак равно ( Икс ⊕ Икс ) ² = х ² ⊕ х ² ⊕ х ² ⊕ х ² знак равно х ⊕ х ⊕ х ⊕ х

и поскольку ( R , ⊕) — абелева группа, мы можем вычесть x ⊕ x из обеих частей этого уравнения, что дает x ⊕ x = 0 . Аналогичное доказательство показывает, что каждое булево кольцо коммутативно :

Икс ⊕ у знак равно ( Икс ⊕ у ) ² = х ² ⊕ ху ⊕ ух ⊕ у ² = x ⊕ xy ⊕ yx ⊕ y, и это дает xy ⊕ yx = 0 , что означает xy = yx (с использованием первого свойства выше).

Свойство x ⊕ x = 0 показывает, что любое булево кольцо является ассоциативной алгеброй над полем F ₂ с двумя элементами ровно одним способом. В частности, любое конечное булево кольцо имеет равную степени мощность, двойки . Не каждая ассоциативная алгебра с единицей над F ₂ является булевым кольцом: рассмотрим, например, кольцо полиномов F ₂ [ X ] .

Факторкольцо R / I любого булевого кольца R по модулю любого идеала I снова является булевым кольцом. Аналогично, любое подкольцо булева кольца является булевым кольцом.

Любая локализация РС ⁻¹ булевого кольца R множеством S ⊆ R является булевым кольцом, поскольку каждый элемент в локализации идемпотентен.

Максимальное кольцо частных Q ( R ) (в смысле Утуми и Ламбека ) булевого кольца R является булевым кольцом, поскольку всякий частичный эндоморфизм идемпотентен.

Каждый простой идеал P в булевом кольце R является максимальным : факторкольцо R / P является областью целостности , а также булевым кольцом, поэтому оно изоморфно полю F 2 _, что показывает максимальность P . Поскольку максимальные идеалы всегда просты, в булевых кольцах простые идеалы и максимальные идеалы совпадают.

Каждый конечно порожденный идеал булевого кольца является главным (действительно, ( x , y ) = ( x + y + xy ) ) . Более того, поскольку все элементы являются идемпотентами, булевы кольца являются коммутативными регулярными кольцами фон Неймана и, следовательно, абсолютно плоскими, что означает, что каждый модуль над ними плоский .

Объединение

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

Унификация в булевых кольцах является унитарной, если все неинтерпретированные функциональные символы являются нулевыми и финитными в противном случае (т. е. если функциональные символы, не встречающиеся в сигнатуре булевых колец, все являются константами, то существует наиболее общий унификатор , а в противном случае — минимальный полный набор унификаторов). конечно).

См. также

• Нормальная форма кольцевой суммы

Ссылки

• Атья, Майкл Фрэнсис ; Макдональд, И.Г. (1969), Введение в коммутативную алгебру , Westview Press, ISBN  978-0-201-40751-8
• Буде, А.; Жуанно, Ж.-П. ; Шмидт-Шаус, М. (1989). «Объединение булевых колец и абелевых групп». Журнал символических вычислений . 8 (5): 449–477. дои : 10.1016/s0747-7171(89)80054-9 .
• Брейнерд, Б.; Ламбек, Дж. (1959). «О кольце частных булева кольца» . Канадский математический бюллетень . 2 : 25–29. дои : 10.4153/CMB-1959-006-x .
• Фрэли, Джон Б. (1976), Первый курс абстрактной алгебры (2-е изд.), Аддисон-Уэсли , ISBN  978-0-201-01984-1
• Херштейн, Индиана (1975), Темы алгебры (2-е изд.), John Wiley & Sons
• Кандри-Роди, Абделила; Капур, Дипак; Нарендран, Палиат (1985). «Теоретико-идеальный подход к проблемам слов и проблемам объединения над конечно представленными коммутативными алгебрами». Техники и приложения переписывания . Конспекты лекций по информатике. Том. 202. С. 345–364. дои : 10.1007/3-540-15976-2_17 . ISBN  978-3-540-15976-6 .
• Коппельберг, Сабина (1989). Справочник по булевым алгебрам, вып. 1 . Амстердам: Северная Голландия. ISBN  0-444-70261-Х .
• Мартин, У.; Нипков, Т. (1986). «Объединение в булевых кольцах». В Йорге Х. Зикманне (ред.). Учеб. 8-й КАДЕ . ЛНКС. Том. 230. Спрингер. стр. 506–513. дои : 10.1007/3-540-16780-3_115 . ISBN  978-3-540-16780-8 .
• Маккой, Нил Х. (1968), Введение в современную алгебру (пересмотренная редакция), Аллин и Бэкон , LCCN   68015225
• Рябухин, Ю. М. (2001) [1994], «Булево кольцо» , Энциклопедия математики , EMS Press

Внешние ссылки

• Джон Армстронг, Булевы кольца