Доказательство тождеств в алгебре множеств.

= {M; }, где М , алгебра множеств. (а готическое рукописное).

объекты операции

В алгебре множеств рассматриваются основные тождества и свойства этих тождеств. Рассматриваются уравнения двух типов

1) U(A, B, C…) = B(A, B, C…) множества заданы подмножествами А, В, С…

2) U(А, В, С…) = 0

Докажем эти тождества. Существует 3 метода доказательства тождеств:

1. геометрический,

2. аналитический (с использованием понятия эвристики),

3. аналитический (с использованием основных свойств теоретико-множественных операций).

Рассмотрим геометрический метод доказательства для первого тождества на примере:

U(A, B, C…) = B(A, B, C…)

Картинки аудентичны (доподлинно одинаковы по построению)

Преимущество геометрического метода: наглядность.

Недостаток: при большом количестве множеств, участвующих в построении (более 5), теряется наглядность данного метода.

Аналитический метод исправляет недостаток геометрического метода, но сам он не наглядный.

U(A, B, C…) = B(A, B, C…)

=

D F

1) (А = В) = А В и В

2) (А В) = ( х) [х А х В] условия равенства двух множеств

3) (В А) = ( х) [х В х А]

(D = F) = D F и F

(D F) = ( х) [х D х F]

x D = x A (B C) =

D

по свойству теоретико-множественных операций переходим к более простому виду записи:

= x A и x A (B C) = x A и [x В или x С] =

Сейчас мы должны перейти к методам эвристики. Эвристический путь сокращает перебор решений. При эвристическом пути рассуждать необходимо после рассмотрения левой части доказываемого множества (рассмотрение до уровня разложения на элементы отношения принадлежности и простейшие логические союзы (и, или)) перейти к рассмотрению таким же образом правой части.

= (x A и x В) или (x A и x С).

= [x (A В)] или [x (A С)] = x [(A В) (A С)]

F

Взяв х – произвольный элемент во множестве D, мы обнаружили его во множестве F.

Аналогичным образом докажем: ( х) [х F х D] = F D и получим конечный результат: (D = F) = D F и F .

Рассмотрим 3-й метод для второго вида тождеств:

(A, B, C, …)=0;

А\[(А В) (А\В)] =

По свойству дистрибутивности исходное тождество можно переписать следующим образом:

А\{[А (А\В)] [В (А\В)]} = А\{А (А В)} = А\А =

А А В

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