Булеан как алгебра множеств

Алгеброй называется множество с операциями.

Например, натуральные числа с операциями сложения и умножения образуют алгебру натуральных чисел. Ес обозначают символом . Алгебра целых чисел может иметь три операции — сложение, умножение и вычитание: .

Более подробное обсуждение понятия алгебры и связанных с этим понятием вопросов будет сделано позже. Сейчас только заметим, что множество P(U) подмножеств множества U с теоретико-множественными операциями (пересечение, объединение и дополнение) образует алгебру, так как результаты применения этих операций к элементам из P(U) снова принадлежат P(U).

Обозначим эту алгебру множеств символом

< Р(М); п, и, >.

В этом символе точкой с запятой разделены множество-носитель алгебры Р(1Г) и операции алгебры: пересечение, объединение, дополнение.

Изучение алгебры (любой, не только алгебры множеств) — это изучение свойств ее операций.

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

Обычно такие тождества называются законами операций.

В тождествах (законах) алгебры могут участвовать и фиксированные, особые элементы.

В любом непустом множестве U всегда есть два подмножества — пустое и само множество U. Это значит, что в алгебре подмножеств универсального множества U особые элементы — это 0 и U.

Коммутативность, ассоциативность и другие законы теоретико-множественных операций

Обсудим лишь наиболее важные свойства теоретико-множественных операций, которые находят непосредственное применение в школьной математике.

Понятия законов операций встречаются уже в начальном курсе математики. Например, свойствами коммутативности и ассоциативности обладают сложение и умножение (для любых целых неотрицательных чисел а, Ь, с):

а + b = h + а;

а + (Ь + с) = (я + Л) + с;

а • b = b • а;

а ? (Ь ? с) = (а ? Ь) ? с.

В школьном курсе математики принято ассоциативный закон называть сочетательным свойством, а коммутативный — переместительным свойством. Ассоциативный, он же сочетательный, закон означает, что результат операции не зависит от образования ассоциаций (сочетаний); коммутативный закон, в свою очередь, утверждает, что результат операции не зависит от перемещений (коммутаций).

Операции над числами обладают и другими свойствами. Например, и сложение, и умножение обладают нейтральными элементами (для любого числа «):

а + 0 - а;

а 1 = а.

Пересечение и объединение множеств тоже обладают нейтральными элементами: универсальное множество U — нейтральный элемент для пересечения:

А гл U = А,

а пустое множество 0 — для объединения:

А и0 =А

(здесь А — любое множество из U). Число нуль обладает аннулирующим (говорят еще поглощающим) свойством при умножении (для любого числа а):

а • 0 = 0.

Таким же свойством обладает пустое множество 0 для операции пересечения (для любого множества Л):

А п 0 = 0.

Универсальное множество при объединении тоже поглощающий элемент (для каждого А из (/):

А и U = U.

Сложение и умножение чисел связаны распределительным свойством (для каждых чисел а, Ь, с):

(а + Ь) • с = а ? с + b ? с.

Этот закон называют еще дистрибутивным. Если отдать роль сложения объединению множеств, а роль умножения — пересечению, то получим по аналогии с числами дистрибутивный закон для объединения и пересечения:

(А и В) п С = (А п С) и (В сл С).

На диаграмме Эйлера темным цветом выделены левая и правая части этого равенства.

Вг>с

А А

(А и В) п С = (A n С) и n С)

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

(а ? Ь) + с = (а + Ь) • (Ь + с),

что не является числовым тождеством, т. е. выполняется не для всех чисел а, Ь, с.

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

(АпВ)иС=(АиС)МВи С).

Число нуль, нейтральный элемент для всех чисел, является нейтральным и для самого себя:

0 + 0 = 0.

Аналогичным свойством при умножении обладает единица:

11 = 1.

Такого рода свойство называют идемпотентностью'. В числовом множестве операция умножения имеет всего два идемпотентных элемента (нуль и единицу), а по сложению найдется единственный идемпотент — нуль.

В алгебре множеств ситуация с операциями пересечения и дополнения иная: все множества — идемпотенты:

А и А = А и А л А = А.

Взяв дополнение для множества два раза подряд (т. е. взяв дополнение дополнения), мы получим исходное множество:

А = А .

Это свойство называют законом двойного дополнения. Объединение взаимно дополняемых множеств равно универсальному множеству, а пересечение — пустому:

А гуА = 0, A u А = U.

Пересечение, объединение и дополнение связаны следующими тождествами (для любых множеств А, В):

АгуВ= АиВ ,

АиВ=АгуВ .

В честь автора эти тождества называются законами де Моргана . На рисунке воспроизведена иллюстрация второго закона де Моргана.

и и

Л-Л-П ЛпЛ-S

А и В= А п В

Заметим, что диаграммы Эйлера лишь иллюстрируют законы операций над множествами, но не могут заменить доказательство (геометрические фигуры — это лишь частные случаи множеств; свойство, которое выполняется в частном случае, вовсе не обязательно должно выполняться всегда).

Как же строго доказать перечисленные (и другие) свойства операций над множествами?

Проще всего опереться на свойства операций над предикатами, с помощью которых были определены теоретико-множественные операции.

1

От латинских слов: idem — «тот же самый» и potens — «сильный», «способный».

2

Августус де Морган (1806-1871) — шотландский математик, профессор математики Университетского колледжа в Лондоне (1828-1866), первый президент (1866) Лондонского математического общества. Законы де Моргана опубликованы в работе «Формальная логика или исчисление выводов необходимых и возможных» (1847).

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >