Логічні операції над множинами та їх властивості. Тотожні перетворення виразів 


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

Логічні операції над множинами та їх властивості. Тотожні перетворення виразів



Множину можна також визначити за допомогою операцій над іншими множинами. Нехай маємо дві множини А і В.

Об’єднання (сума) А È В є множина всіх елементів, що належать А та В.

Наприклад, {1, 2, 3} È {2, 3, 4} = {1, 2, 3, 4}.

Для наочного зображення співвідношень між множинами будь-якого універсума U використовують круги Ейлера. Зазвичай універсум подають множиною точок прямокутника, а його підмножини зображають у вигляді кругів або інших простих областей усередині цього прямокутника. Об’єднання зображується таким чином (рис. 1.2.1):

Рис. 1.2.1. Об’єднання (сума) А È В

Перетин (добуток) А Ç В є множиною всіх елементів, що належать одночасно як А, так і В (рис. 1.2.2).

Наприклад, {1, 2, 3} Ç {2, 3, 4} = {2, 3}.

Рис. 1.2.2. Перетин (добуток) А Ç В

Множини, які не мають спільних елементів, називаються різночленними або неперетинаючими А Ç В = Æ (рис. 2.3).

Рис. 1.2.3. Перетин (добуток) А Ç В= Æ

Різниця А \ В (чи А - В) є множиною, котра складається з усіх елементів А, що не входять у В (рис. 1.2.4).

Наприклад, {1, 2, 3} \ {2, 3, 4} = {1}.

Рис. 1.2.4. Різниця А \ В

Її можна розглядати як відносне доповнення В до А. Якщо А Ì В, то множина U\A називається абсолютним доповненням (або просто доповненням) множини A і позначається через . Вона містить усі елементи універсума U, крім елементів множини А (рис. 1.2.5).

Рис. 1.2.5. Доповнення

Доповнення А визначається запереченням властивості P(x), за допомогою якої визначається А. Очевидно, А \ В = А Ç (рис. 1.2.6).

Рис. 1.2.6. Різниця А \ В = А Ç , при А Ì В

Диз’юктивна сума (симетрична різниця) А+В (чи АÅВ) є множиною всіх елементів, що належать або А або В (але не обом одразу) (рис. 1.2.7).

Наприклад, {1, 2, 3} + {2, 3, 4} = {1, 4}.

Рис. 1.2.7. Сума А + В

Диз’юктивну суму одержуємо об’єднанням елементів множин, за винятком тих, які трапляються двічі.

Властивості операцій над множинами.

Комутативний закон для об’єднання і перетину множин

А È В= В È А;

А Ç В= В Ç А.

Асоціативний закон для об’єднання та перетину множин

А È È С)=(А È В) È С;

А Ç Ç С)=(А Ç В) Ç С.

Дистрибутивний закон для об’єднання і перетину множин

А È Ç С)=(А È В) Ç(А È С);

А Ç È С)=(А Ç В) È(А Ç С).

Властивості пустої множини та універсума відносно об’єднання

А ÈÆ = А;

А È = U;

А È U = U;

=U.

Властивості пустої множини та універсума відносно перетину

А Ç U = A;

А Ç = Æ;

А ÈÆ = А;

= Æ.

Закон ідемпотентності для об’єднання і перетину множин

А È А = А;

А Ç А = А.

Закон поглинання

А È Ç В) = А;

А Ç È В) = А.

Теорема де Моргана

;

.

Наступні властивості:

1) Якщо А È В = U і А Ç В = Æ, то В= ;

2) = U \ А;

3) =А;

4) А \ В=А Ç В;

5) А+В =(А Ç ) È ( Ç В);

6) А+В =В+А;

7) А+В+С =А +(В+С);

8) А+ Æ = Æ +А = А;

9) А Ì В, тоді й тільки тоді, якщо А Ç В=А, або А È В=В, або А Ç = Æ;

10) А=В, тоді та тільки тоді, якщо (А Ç ) È ( Ç В)= Æ.

Ми розглядали операції над множинами і їх властивості (закони операцій). Усі ці закони можна довести. Є різні способи доведення.

1. Доведення цих тотожностей за допомогою відношення належності

Приклад. Довести дистрибутивний закон А È (В ÇС)=(А È В) Ç(А È С).

Доведення

Уважатимемо, що x Î А È Ç С), тоді x Î А або x Î Ç С). Якщо x Î А, то x належить об’єднанню з А з будь-якою множиною, тобто x Î А È В і x Î А È С; із цього слідує, що x є елементом перетину множин А È В і А È С, тобто x Î È В) Ç(А È С).

Якщо x Î В Ç С, то x Î В і x Î С, а значить, x Î А È В і x Î А È С, тобто x є елементом перетину тих же множин. Таким чином, доведено, що

А È Ç С)Ì(А È В) Ç(А È С).

Аналогічно доводимо і відношення

А È Ç С)É(А È В) Ç(А È С).

Згідно з визначенням рівності множин маємо потрібну тотожність

А È Ç С)=(А È В) Ç(А È С).

2. Доведення тотожностей за допомогою кругів Ейлера

Приклад.Довести дистрибутивний закон А Ç È С)=(А Ç В) È(А Ç С) за допомогою кругів Ейлера.

Доведення. Проілюструємо за допомогою кругів Ейлера спочатку ліву частину тотожності, виконавши спочатку об’єднання множин В і С, а потім перетин з А. Потім побудуємо діаграму для правої частини тотожності (рис. 1.2.8).

Рис. 1.2.8. Доведення тотожності А Ç È С)=(А Ç В) È(А Ç С) за допомогою кругів Ейлера

Як бачимо, діаграми збігаються, отже, тотожність доведена.

3. За допомогою тотожних перетворень

Приклад. Довести, що А È А = А.

Доведення

А È А = È А) Ç U= (А È А) Ç È )= А È Ç ) = А ÈÆ = А.

З комутативності та асоціативності операцій об’єднання слідує, що об’єднання декількох множин можна виконати послідовно, об’єднуючи ці множини, причому порядок слідування множин не впливає на результат. Так, для множин А, В, С можна записати А È В È С=(А È В) È С=(В È С) È А.

Отже, сукупність множин можна позначити відношенням

.

Теж саме можна записати і для перетину сукупності множин

.

Тотожні перетворення. Алгебра множин являє собою теоретико-множинний аналог звичайної алгебри дійсних чисел та основана на властивостях операцій над множинами. За допомогою тотожних перетворень можна спрощувати або перетворювати у зручний вигляд вирази, що містять множини, при цьому застосовують властивості операцій.

Приклад 1. Виконати тотожні перетворення.

Приклад 2

.



Поделиться:


Последнее изменение этой страницы: 2017-02-21; просмотров: 611; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.226.254.255 (0.015 с.)