Дискретна математика для програмістів

лекция

1.6 Доведення тотожностей

Основний метод доведення тотожностей в алгебрі множин ґрунтується на згаданому раніше факті: А = В тоді і тільки тоді, коли А В і В А. Доведемо, наприклад, тотожність 3а) А (В С) = (А В) (А С).

Доведемо спочатку, що А (В С) (А В) (А С). Для цього візьмемо будь-яке x А (В С), тоді за означенням операцій та маємо x А або (x В і x С). За законом дистрибутивності "або" відносно "і" (x А або x В) і (x А або x С), тобто x А В і x А С. Це рівносильно x ( А В) (А С), що й треба було довести.

Доведемо тепер, що (А В) (А С) А (В С). Для цього візьмемо будь-яке x (А В) (А С). Звідси (x А або x В) і (x А або x С). Це рівносильно x А або (x В і x С), тобто x А (В С), що й потрібно було довести.

Таким чином, А (В С) = (А В) (А С).

Із властивості асоціативності операції обєднання множин випливає, що обєднання кількох множин можна виконати, послідовно обєднуючи їх, причому порядок входження множин не впливає на результат: А (В С) = (А В) С = А В С. Отже, обєднання сукупності множин можна подати співвідношенням: . Аналогічно на n множин узагальнюється операція перетину: .

Використовуючи узагальнення операцій обєднання та перерізу на n множин, можна узагальнити також інші співвідношення, наприклад закон де Моргана, який в узагальненому вигляді записується так: і .

Приклад. Показати, що .

Розвязання. Доведемо цю властивість асоціативності, скориставшись діаграмами Венна:

Як бачимо , що й треба було довести.

Делись добром ;)