Juk_Ilyenko_Moklyachuk_Orlovskiy_DM_praktikum

№ 1.7. За допомогою таблицi iстинностi перевiрити, чи будуть наступнi вирази тавтологiями або суперечностями:

№ 1.8. За допомогою перетворень довести, що наступнi формули є тавтологiями:

№ 1.9. За допомогою таблиць iстинностi та перетворень довести, що наступнi формули є суперечностями:

№1.10. Визначити, котра еквiвалентнiсть є правильною:

1.→ ≡ чи → ≡ ;

2.(( → ) → ) ≡ чи ( → ( → ) ≡ ;

30

3.( → ) ≡ ( ) чи ( → ) ≡ ( ) ;

4.→ ( → ) ( ) → чи → ( → ) ≡ → .

31

ЗАНЯТТЯ 2

Алгебра множин

Навчальнi задачi

№ 2.1. Для унiверсальної множини = {−5, −4, −3, −2, −1, 1, 2, 3, 4, 5}, множини = {1, −2, 3, −4} та множини всiх розв’язкiв рiвняння

4 − 7 3 + 6 2 + 32 − 32 = 0 знайти

1., ∩ , , , , , = ( ) ;

2.Визначити, котра з п’яти можливостей виконана для множин та

: , , = , ∩ = ?;

3.Виписати множину всiх пiдмножин та знайти її потужнiсть.

Розв’язок. Перш за все, знайдемо множину розв’язкiв заданого рiвняння. Зрозумiло, що його розв’язки мають мiститися в унiверсальнiй множинi . Пробуємо вгадати розв’язок. Пiдставляючи {1}, бачимо, що даний елемент є розв’язком рiвняння. Для спрощення задачi, подiлимо вихiдний многочлен на ( − 1).

32

−6 3 + 6 2

−6 3 + 6 2

32 − 32

32 − 32

0.

Продовжуючи перебор, бачимо, що коренем рiвняння 3 − 6 2 + 32 = 0

є {−2}. Повторюємо операцiю дiлення.

−8 2 + 0

−8 2 − 16

16 + 32

16 + 32

0.

Отриманий тричлен є квадратом рiзницi: 2 − 8 + 16 = ( − 4)2. Отже, множина всiх розв’язкiв заданого в умовi рiвняння складається з елементiв {−2, 1, 4}.

Для розв’язку рiвнянь такого типу також можна використовувати схему Горнера, теорему Вiєта, метод Декарта-Ейлера, метод Феррарi, тощо.

Визначивши множину , перейдемо до пункту 1 нашого завдання. Випишемо необхiднi нам множини, користуючись означеннями перетину,

33

об’єднання, рiзницi, симетричної рiзницi та доповнення.

= {−4, −2, 1, 3, 4}; ∩ = {−2, 1}; = {−4, 3}; = {4};

= {−4, 3, 4}; = {−5, −4, −3, −1, 2, 3, 5};

= ( ) = {−4, 3, 4} {1, −2, 3, −4} = {−2, 1, 4}.

Розв’яжемо тепер пункт 2. Так як в мiститься елемент {3}, котрий не входить в , то не включається в . Так як в мiститься елемент

{4}, котрий не входить в , то не включається в . Звiдси можна зробити висновок, що вони не спiвпадають, адже кожна множина мiстить елемент, що не належить iншiй. Оскiльки i в множинi , i в множинi мiстяться елементи {−2, 1}, то перетин їх непорожнiй.

Множина всiх пiдмножин множини буде мiстити порожню множину, оскiльки ця множина завжди входить у будь-яку множину. Також, ця множина буде мiстити саму множину , i, крiм того, всi можливi комбiнацiї елементiв :

( ) = {?, {−2}, {1}, {4}, {−2, 1}, {−2, 4}, {1, 4}, {−2, 1, 4}}.

Так як потужнiсть множини - це кiлькiсть її елементiв, то, порахувавши кiлькiсть пiдмножин множини , можна записати, що | ( )| = 8.

№ 2.2. Нехай , , - множини точок площини, заданi наступним чином:

= {( , )| +2 > }, = {( , )| 2+ 2 ≤ 4}, = {( , )| | | ≤ 2, | | ≤ 2}.

Зобразити в декартовiй системi координат множину = ( ).

Розв’язок. Перш за все, побудуємо множини , , . Перша множина являє собою пiвплощину знизу вiд прямої, заданої рiвнянням +2 = ,

34

причому сама пряма не включається в область. Множина - це внутрiшнiсть кола радiусом 2, включаючи саме коло. Третя множина, - це перетин промiжкiв | | ≤ 2 та | | ≤ 2, тобто квадрат зi стороною 4 та центром у початку координат. Данi множини зображено на Рис. 2.1.

Симетрична рiзниця множин та буде являти собою зони ззовнi кола та всерединi квадрата, чотири криволiнiйнi трикутника. Якщо ж вiдняти симетричну рiзницю вiд , то отримаємо пiвплощину, з якої вирiзано три таких криволiнiйних трикутника, окрiм того, що знаходиться в другому квадрантi системи координат. Контури криволiнiйних трикутникiв включатися в результат не будуть. Результат даних операцiй зображено на Рис. 2.2.

№ 2.3. Чи iснують непорожнi , , - пiдмножини унiверсальної множини , для яких виконуються умови: = , = , ̸= ?

35

Розв’язок. Зобразимо множини , , , на дiаграмi Венна як множини, що знаходяться у загальному положеннi (Рис. 2.3.). Позначимо кожну область, на якi розбиває площину дiаграма, символами з певним iндексом: 4, наприклад, означає множину тих елементiв, що належать перетину та , проте не належать при цьому перетину та .

Складемо тепер iз множин , 1, ..., 8 вихiднi множини:

= { 1, 2, 3, 4, 5, 6, 7, 8}, = { 1, 2, 4, 5},

= { 2, 3, 5, 6}, = { 4, 5, 6, 7}.

U

1 2 3

A B

4 5 6

C

7

8

Рис. 2.3

Змiнимо множини , , та таким чином, щоб вони задовольняли умовам завдання. З умови = випливає, що множина ( )

не має мiстити жодних елементiв. Так як ( ) = { 7, 8}, то 7 =

та 8 = . Щоб виконати умову = , потрiбно, щоб множини

1, 2, 6, 7 були порожнiми. Виключивши порожнi пiдмножини iз вихiдних множин, отримаємо, що

= { 3, 4, 5}, = { 4, 5}, = { 3, 5}, = { 4, 5}.

36

Для таких множин = { 3} ≠ .

Якщо замiнити , 1, ..., 8 на вiдповiднi 1, ..., 8, отримаємо конкретний приклад множин, якi задовольняють вихiднi умови: =

{3, 4, 5}, = = {4, 5}, = {3, 5}.

№ 2.4. З’ясувати взаємне розташування множин , , , для яких виконуються умови: = ( ) ( ), = ( ( )), = , якщо , , - пiдмножини унiверсальної множини .

Розв’язок.Вiзьмемо множини , , та та розiб’ємо їх на пiдмножини аналогiчним до попередньої задачi чином:

= { 1, 2, 3, 4, 5, 6, 7, 8}, = { 1, 2, 4, 5},

= { 2, 3, 5, 6}, = { 4, 5, 6, 7}.

Тодi

= { 2, 3}, = { 1, 4}, ( ( )) = { 1, 4, 5},

= { 1, 2, 3, 4, 5, 6}, ( ) ( ) = { 1, 2, 3, 4}.

Отже, маємо, що

= { 1, 2, 3, 4}, = { 1, 4, 5}, = { 1, 2, 3, 4, 5, 6}.

Як видно, для таких множин , , виконуються включення ,

для довiльних , , . Крiм того, так як 2 i 2 / ,

5 i 52 / та 1 i 1 , то множини та знаходяться в загальному положеннi.

№ 2.5. Розв’язати систему спiввiдношень вiдносно множини та вказати умови сумiсностi системи

37

Розв’язок. Побудуємо множини , , в загальному положеннi

та множину ∩ (Рис. 2.4). Символом 1 позначимо пiдмножину

множини , елементи якої не потрапили нi в одну з множин , , ;

символом 5 - множину, утворену перетином множин , , , i т.д.

Будемо мати:

= { 1, 2, 4, 5, 6, 7}, = { 2, 3, 4, 5, 7, 8},

= { 4, 5}, = { 5, 6, 7, 8, 9}.

X

9

Рис. 2.4

Розглянемо першу рiвнiсть системи. = { 2, 3, 7, 8}, ∩ =

{ 5, 7, 8}. Щоб данi множини спiвпадали, потрiбно щоб 2, 3, 5 = . Вiдповiдно, отримаємо, що = { 1, 4, 6, 7}, = { 4, 7, 8}, = { 4},

= { 6, 7, 8, 9}.

38

Розглянемо другу рiвнiсть системи. = { 6, 7, 8, 9}, ∩ =

{ 4, 7}. Щоб цi множини спiвпадали необхiдно, щоб 4, 6, 8, 9 = . Тодi

= { 1, 7}, = { 7}, = , = { 7}.

Бачимо, що = , , = .

Перевiримо, чищо множина є розв’язком вихiдної системи. Якщо = та , то ∩ , i тодi для довiльних спискiв елементiв , можна записати = { }, = { , }.

Нехай = { } = . Тодi = = { }, = { }, ∩ =

{ } = , ∩ = { } = .

Бачимо, що всi вiдношення системи задовольняються, тобто множина

= є розв’язком вихидної системи рiвнянь за умови , = .

№ 2.6. Розв’язати систему рiвнянь вiдносно множини та вказати умови сумiсностi:

=

∩ =

=

Розв’язок. Побудуємо множини , , , , якi перебувають у загальному положеннi та є пiдмножинами унiверсальної множини . Для цього випишемо усi 16 рiзних двiйкових наборiв розмiрностi 4. Нехай розряди цих наборiв вiдповiдають належностi до множин , , , вiдповiдно. Позначимо цi набори символами , = 1, 2, . . . , 16.

39