Алгебраические системы - Мальцев А.И.
Скачать (прямая ссылка):
Если A ^ В, то разность В \ А называется дополнением множества А в множестве В и обозначается через допвА. В случае, когда множество В заранее известно, вместо допвЛ кратко пишут А' и говорят просто о дополнении множества А. Так, если основным множеством В служит множество N всех натуральных чисел, то дополнением совокупности четных чисел является совокупность нечетных чисел, дополнением совокупности чисел, каждое из которых делится на какое-либо нечетное число, большее единицы, является совокупность степеней двойки 2°, 21, 22, 23, ...
Только что определенные операции объединения, пере- * сечения множеств и взятия дополнения множества допускают очень наглядное графическое истолкование. В качестве основного множества берем совокупность точек плоскости. Пусть А — круг на этой плоскости (см. рис. 1), т. е. множество точек, лежащих внутри и на заданной окружности. Тогда А' будет множеством точек, лежащих вне упомянутой окружности (на рис. 1 — заштрихованная область). ОТНОШЕНИЯ И ОТОБРАЖЕНИЯ-
13
Рассмотрим теперь два круга А, В. На рис. 2 изображено объединение множеств A U В (заштрихованная область), а на рис. 3 изображено множество А [\В (дважды заштрихованная область). На рис. 4 заштрихованная область представляет разность А \ В множеств А, В.
Арифметические действия сложения и умножения натуральных чисел суть операции, производимые над парами чисел,, или, как говорят, бинарные операции. Теоретико-множественные операции объединения и пересечения могут
служить хорошим примером бинарных операций, производимых над множествами, т. е. над объектами еще более простой логической природы, чем натуральные числа. Операции возведения числа в квадрат и взятия дополнения множества суть операции, производимые над одним объектом. Такие операции называются унарными.
Фиксируем какое-нибудь множество U и обозначим через 11 совокупность всех подмножеств множества U. Над элементами совокупности U можно производить операции пересечения, объединения и взятия дополнения
Рис. 1.
Рис. 2.
Рис. 3.
Рис. 4. 14
0Ё1ЦЙЕ понятна
[Гл. 1
(в основном множестве U). Совокупность U замкну-т а относительно перечисленных операций в том смысле, что, производя эти операции над элементами совокупности U, мы будем в результате получать элементы, принадлежащие II. Система, состоящая из совокупности U и операций Ui Пі '» называется алгеброй Буля подмножеств множества U.
В арифметике действия сложения и умножения связаны известными законами ассоциативности, коммутативности, дистрибутивности. Аналогичным законам и ряду других подчинены и операции объединения, пересечения и дополнения в алгебрах Буля. Мы выпишем здесь основные из этих законов, так как взятые в абстрактной форме (см. п. 5.2) они играют большую роль во многих разделах алгебры и логики:
Б1) х[]х = х\
Б2) х\)у = у\)х\
БЗ) {x\]y)\]z = x\]{y\} z);
Б4) snfoUz) = (snsf)U(snz);
Б5) {х'У = x\
Б6) (x\j y)' = x'(]y';
Б7) x[j(y[\y') = x.
В истинности этих тождеств легко убедиться и путем простых рассуждений, и графически. Например, из рис. 5
непосредственно видно, что для любых множеств х, у, z левая и правая части тождества Б4 изображаются одной и той же заштрихованной частью плоскости.
Равенства Б1, . . ., Б 7 суть тождества. Поэтому, подставляя в них вместо х, у, z выражения ж', у', z', получим снова тождества. Эти новые тождества можно преобразовать при помощи тождеств как старых, так и новых и т. д.
В результате из тождеств Б1 — Б7 мы получим ряд тождеств, называемых формальными следствиями данных. Этот процесс выведения из данных
Рис. 5. ОТТЇОБІЕІЇЙЙ Й ОТОЙРАЖЕЯЙЯ
15
тождеств новых во всех деталях будет проанализирован далее в п. 11.2 этой книги, а здесь мы покажем лишь, что из тождеств Б1 — Б7 чисто формально вытекают следующие тождества, в которых х" ~ (х')':
Бої) xf]x = x;
Б„2) хГ\у = у()х;
Б03) (xf)y)f]z = x[](yf\zy,
Б04) x[j(y[]z) = (x[jy)[](x[}z);
В()5) X — х\
Б06) (хг\у)' = х'\)у'; Б07) Х{\(у[)у') = х.
Все они получаются сходными приемами. Выведем из Б1 — Б7, например, лишь тождество Б06. Заменяя в Б6 х, у на х', у', получим (х' Uj/')' — х" П у" • Это равенство ввиду тождества Б5 можно представить в форме (х'[}у'У — х(]у- Беря дополнения от обеих частей и применяя снова тождество Б5, получим требуемое соотношение Б 06.
Тождества Б01 — Б07 с чисто внешней стороны получаются из х тождеств Б1 — Б7 взаимной переменной ролей знаков U и П и потому называются двойственными этим тождествам.
Наряду с операцией вычитания множеств иногда рассматривается операция разностного сложения, обозначаемая символом 0 и определяемая формулой
хфу = (х\у)[](у\х). (1)
Графически разностная сумма х 0 у изображена на рис. 6, откуда ясно видно, что
(Х©У)®У = Х-
Поэтому, если ввести новую операцию вычитания (разностного) 0 с помощью формулы
xG У =^ х@ у, 16
ОБЩИЕ ПОНЯТИЯ
[Гл. I
то обе операции будут связаны друг с другом обычным арифметическим законом
x@y = z<&>y = zQx,
где знак <=> употреблен как символ слова «равносильно». Вместе с тем легко проверить, что для операций ©, П имеет место и обычный закон дистрибутивности
