[Список тем] [Вступление к этой теме] Страницы темы: [1] [2] [3] [4] [5] [6] [7] [8]

Тождества алгебры множеств

С помощью операций объединения, пересечения и дополнения из множеств можно составлять различные алгебраические выражения. Обозначим через J(X, У, Z) некоторое алгебраическое выражение, составленное из множеств X, Y и Z и представляющее собой некоторое множество. Пусть R(X, Y, Z)-другое алгебраическое выражение, составленное из тех же множеств. Если оба алгебраических выражения представляют собой одно и то же множество, то их можно приравнять друг к другу, получая алгебраическое тождество вида
J(X, У, Z) = R(X, Y, Z).      (31)
Такие тождества бывают очень полезны при преобразованиях алгебраических выражений над множествами, и некоторые из них мы рассмотрим в настоящем разделе.

  1. На рис. 7,а приведены диаграммы Эйлера-Венна для выражений (X Y )Z и (X Z) (Y Z). Из этих диаграмм видно, что оба выражения определяют одно и то же множество, так что в алгебре множеств имеет место тождество
    (X Y) Z= (X Z) (Y Z),      (32)
    аналогичное дистрибутивному закону (а+b)с=ас+bс в обычной алгебре.

  2. В обычной алгебре мы не можем заменить в дистрибутивном законе действие сложения умножением, а действие умножения сложением, так как это приводит к абсурдному выражению (аb)+с=(a+с) (b+с). Иначе обстоит дело в алгебре множеств.
    На рис. 7,б приведены диаграммы Эйлера - Венна для алгебраических выражений (X Y) Z и (X Z) (Y Z) . Оба эти выражения дают одно и то же множество, так что имеет место тождество
    (X Y) Z = (X Z) (Y Z).      (33)

  3. Легко убедиться, что если YX, то
    X Y=Y, X Y=X.      (34)
    Действительно, все элементы множества Y являются в то же время и элементами множества X. Значит, пересечение этих множеств, т. е. общая часть множеств Х и Y,

      а.)

      б)

    Рис. 7. Геометрическая иллюстрация тождеств
    (X Y )Z= (X Z) (Y Z) (а) и (X Y) Z = (X Z) (Y Z) (б)

    совпадает с Y. В объединение множеств Х и Y множество Y не внесет ни одного элемента, который уже не входил бы в него, будучи элементом множества X. Следовательно, Х Y совпадает с X.

  4. Полагая в (34) Y=X и учитывая, что Х Х, находим
    X X=X, X X=X      (35)
    Установление тождеств алгебры множеств с помощью диаграммы Эйлера-Венна в ряде случаев оказывается неудобным. Имеется более общий способ установления тождественности двух алгебраических .выражений.
    Пусть, как и прежде, через J(X, У, Z) и R(X, Y, Z) обозначены два алгебраических выражения, получившихся путем применения операций объединения, пересечения и дополнения к множествам X, Y и Z. Для того чтобы доказать, что J = R, достаточно показать, что JR и чтоRJ . В свою очередь, чтобы показать, что , нужно убедиться, что из x следует x . Аналогично, чтобы показать, что , нужно убедиться, что из xJ следует хR . Воспользуемся этим методом, чтобы доказать еще несколько тождеств.

  5. Докажем тождество
    (X Y) = X Y.      (36)
    Предположим, что x (X Y), т. е. что х (Х Y). Это значит, что х Х и х Y, т. е. x X и x Y. Следовательно, x (X Y). Предположим теперь, что у (X Y), т.е. y X и y Y. Это значит, что у Х и yY, т.е. что y (Х Y). Следовательно, у (X Y).

  6. Тождество
    (X Y) = X Y.      (37)
    докажем, приведя обе его части к одинаковому виду. Выполняя операцию дополнения над обеими частями (37), получим (X Y)= ( X Y) Левая часть этого выражения дает XY . То же самое получим, преобразовывая правую часть по правилу (36).
    В литературе тождества (36) и (37) обычно называются тождествами де-Моргана.

[Список тем] [Вступление к этой теме] Страницы темы: [1] [2] [3] [4] [5] [6] [7] [8]