Логическое кольцо

редактировать

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

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

Содержание

  • 1 Обозначения
  • 2 Примеры
  • 3 Связь с булевыми алгебрами
  • 4 Свойства булевых колец
  • 5 Унификация
  • 6 См. Также
  • 7 Примечания
  • 8 Ссылки
  • 9 Дополнительная литература
  • 10 Внешние ссылки

Обозначения

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

  • В коммутативной алгебре стандартное обозначение - использовать 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 мы можем определить

x ∧ y = xy,
x ∨ y = x ⊕ y ⊕ xy,
¬x = 1 ⊕ x.

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

xy = x ∧ y,
x ⊕ y = (x ∨ y) ∧ ¬ (x y).

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

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

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

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

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

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

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

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

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

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

Любая локализация RS - 1 {\ displaystyle RS ^ {- 1}}{\ displaystyle RS ^ {- 1}} логического кольца R с помощью набора S ⊆ R {\ displaystyle S \ substeq R}S \ substeq R - это логическое кольцо, поскольку каждый элемент в локализации идемпотентен.

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

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

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

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

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

Объединение

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

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

См. также

Примечания

Ссылки

Дополнительная литература

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

Последняя правка сделана 2021-05-13 14:35:45
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте