Логическое кольцо - Boolean ring

В математике , А булево кольцо R является кольцом , для которого х 2 = х для всех х в 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 мы можем определить

х ∧ у = ху ,
х ∨ у = х ⊕ у ⊕ ху ,
¬ х = 1 ⊕ х .

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

ху = х ∧ у ,
х ⊕ у = ( х ∨ у ) ∧ ¬ ( х ∧ у ).

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

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

Свойства булевых колец

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

x ⊕ x = ( x ⊕ x ) 2 = x 2 ⊕ x 2 ⊕ x 2 ⊕ x 2 = x ⊕ x ⊕ x ⊕ x

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

x ⊕ y = ( x ⊕ y ) 2 = x 2 ⊕ xy ⊕ yx ⊕ y 2 = x ⊕ xy ⊕ yx ⊕ y

и это дает xy ⊕ yx = 0, что означает xy = yx (используя первое свойство выше).

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

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

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

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

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

Булевы кольца - это регулярные кольца фон Неймана .

Булевы кольца абсолютно плоские: это означает, что каждый модуль над ними плоский .

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

Объединение

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

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

Смотрите также

Примечания

использованная литература

дальнейшее чтение

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