18276

ОПЕРАЦІЯ НАД МНОЖИНАМИ

Лекция

Математика и математический анализ

Лекція 3 ОПЕРАЦІЯ НАД МНОЖИНАМИ Поняття про операції. Операції перерізу об’єднання доповнення підмножини до множини і доповнення. Зображення результатів операцій за допомогою кругів Ейлера. Закони операції над множинами. Число елементів у об’єднанні ...

Украинкский

2013-07-07

256.5 KB

90 чел.

Лекція 3

ОПЕРАЦІЯ НАД МНОЖИНАМИ

  1.  Поняття про операції.
  2.  Операції перерізу, об’єднання, доповнення підмножини до множини і доповнення. Зображення результатів операцій за допомогою кругів Ейлера.
  3.  Закони операції над множинами.
  4.  Число елементів у об’єднанні кількох скінченних множин.
  5.  Поняття про розбиття множини на підмножини, які попарно не перетинаються (розбиття множини на класи). Розбиття множини на класи за допомогою однієї, двох і трьох властивостей її елементів.
  6.  Картеж та його основні характеристики. Впорядкована пара.
  7.  Декартів добуток множин. Закони декартового множення множин.
  8.  Число елементів в декартовому добутку кількох скінченних множин.

Питання на самостійне опрацювання

  1.  Поняття про операції та їх види.
    1.  Властивості операцій над множинами.
    2.  Вираження результатів парних операцій через (n≥3) бінарні операції


1
. Поняття про операції.

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

Під nарною (nмісною) операцією розуміють правило, за яким n об'єктам, взятим у певному порядку, ставиться у відповідність не більше як один об'єкт, що називається результатом операції. Самі ж об'єкти, яким ставиться у відповідність результат, називаються компонентами операції. У випадку, коли компонента одна, операція називається унарною (одномісною), якщо їх дві – бінарною (двомісною), три – терарною (тримісною) і т. д. За домовленістю бінарні операції часто називають операціями.

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

1) з усіх значень сполучника "і" вибране таке – властивість з'єднувати два твердження, утворюючи нове твердження, яке має місце тоді і тільки тоді, коли мають місце обидва твердження;

2) з усіх значень сполучника "або" виділене його так зване нероздільне значення, – властивість з'єднувати два твердження, утворюючи нове твердження, яке має місце тоді і тільки тоді, коли має місце хоч одне з них.

Якщо ж твердження, що утворене з двох тверджень, має місце лише тоді, коли має місце тільки одне з них, то вживають "або ... або".

  1.  Операції перерізу, об’єднання, доповнення підмножини до множини і доповнення. Зображення результатів операцій

за допомогою кругів Ейлера.

Перерізом (перетином) двох довільних множин називається множина, елементами якої є ті і тільки ті елементи, що належать обом цим множинам.

Переріз множин X і Y позначається X Ç Y і читається: "X переріз із Y". Символічно означення перерізу множин X і Y запишеться:

X Ç := {x | x Î X і x Î Y}.

Правило, за яким двом довільним множинам X і Y ставиться у відповідність їх переріз X Ç Y, називається операцією перерізу множин.

Поняття перерізу двох множин можна узагальнити на довільну скінченну або нескінченну сукупність множин.

Перерізом довільних множин X1, X2, ..., Xn, ... називається множина, елементами якої є ті і тільки ті елементи, що належать кожній з цих множин і позначається

X1 Ç X2 Ç ... Ç Xn Ç ... або Xі.

Графічно зображення перерізів двох і трьох множин за допомогою кругів Ейлера дано на мал. 1, де результати цих операцій заштриховано.

X  Ç Y

X Ç Y Ç Z

Мал. 1.

Об'єднанням довільних двох множин називається множина, елементами якої є ті і тільки ті елементи, що належать принаймні одній з них. Об'єднання множин X і Y позначається X È Y і читається: "X об'єднання з Y". Символічно означення об'єднання множин X і Y запишеться:

X È Y:= {x | x Î X або x Î Y}.

Правило, за яким довільним двом множинам X і Y ставиться у відповідність їх об'єднання X È Y, називається операцією об'єднання множин.

Поняття об'єднання множин можна узагальнити на довільну скінченну або нескінченну сукупність множин. Об'єднанням довільних множин X1, X2, ..., Xn, ... називається множина, елементами якої є ті і тільки ті елементи, що належать принаймні одній із цих множин. Об'єднання множин X1, X2, ... , Xn, ... позначається

X1 È X2 È ...  È Xn È... або Xі.

Графічне зображення об'єднання двох і трьох множин за допомогою кругів Ейлера дано на мал. 2, де результати цих операцій заштриховано.

X È Y

X È Y È Z

Мал. 2.

Різницею довільних множин X і Y називається множина, елементами якої є ті і тільки ті елементи множини X, що не належать множині Y.

Різниця множин X і Y позначається X \ Y і читається: "X мінус Y", або "X без Y", або "від X відняти Y". Символічно означення різниці множин X і Y запишеться:

X \ := {x | x Î X і x Ï Y}.

Правило, за яким кожній парі множин X і Y ставиться у відповідність їх різниця X \ Y, називається операцією віднімання множин, або відніманням множин.

Якщо множина Y є підмножиною множини X, то різниця множин X \ Y називається доповненням підмножини Y до множини X і позначається .

Різниця між універсальною множиною U і довільною її підмножиною X називається доповненням множини X і позначається . Очевидно, що означення доповнення можна сформулювати і без поняття різниці множин, а саме: якщо U – універсальна множина і X – її підмножина, то доповненням множини X називається множина, елементами якої є ті і тільки ті елементи універсальної множини U, що не належать множині X. Символічно це означення запишеться:

 := {x | x Î U і x Ï X}.

Правило, за яким кожній підмножині X універсальної множини U ставиться у відповідність її доповнення , називається операцією доповнення множини.

Графічне зображення результатів операцій віднімання множин, доповнення підмножини до множини і доповнення множини за допомогою кругів Ейлера дано на мал. 3, де результати цих операцій заштриховано.

X \ Y

x

Мал. 3.

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

  1.  Закони операції над множинами.

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

Теорема 1. Для довільних множин A, B і C мають місце:

1. Властивості порожньої множини для перерізу і об'єднання:

A Ç Æ  = Æ,  A È Æ  = A.

2. Властивості універсальної множини для перерізу і об'єднання:

a Ç U = a,  A È U = U.

3. Комутативні закони операцій перерізу і об'єднання:

A Ç B = B Ç A,  A È B = B È A.

4. Асоціативні закони операцій перерізу і об'єднання:

(a Ç B) Ç C = A Ç (B Ç C),  (A È B) È C = A È (B È C).

5. Закони ідемпотентності операцій перерізу і об'єднання:

A Ç A = A,   A È A = A.

6. Дистрибутивні закони, які пов'язують операції перерізу і об'єднання:

A Ç (B È C) = (A Ç B) È (A Ç C) – дистрибутивність перерізу відносно об'єднання;

A È (B Ç C) = (A È B) Ç (A È C) – дистрибутивність об'єднання відносно перерізу.

7. Закон подвійного доповнення:  = A.

8. Закони де Моргана, які пов'язують операції перерізу, об'єднання і доповнення:

Зауваження. Іноді замість речень виду "З твердження A на підставі твердження C випливає твердження B", що часто зустрічається при доведеннях, користуються їх символічним записом:

A Þ B на підставі твердження C.

► Властивості 1, 2, 3, 4, 5 і 7 безпосередньо випливають з означень операцій над множинами.

I. Доведемо дистрибутивність об'єднання множин відносно перерізу, тобто, що для довільних множин A, B і C має місце рівність:

A È (B Ç C) = (A È B) Ç (A È C).

(1)

1. Нехай x – будь-який елемент такий, що

x Î A È (B Ç C) Þ за означенням об'єднання множин

x Î A  або  x Î B Ç C, що означає можливість трьох таких випадків:

1) x Î A,   2) x Î B Ç C,   3) x Î A  і  x Î B Ç C.

Оскільки третій випадок є підвипадком перших двох, то достатньо розглянути лише їх.

Нехай

x Î A

Þ за означенням об'єднання множин

x Î A È B  і  x Î A È C

Þ за означенням перерізу множин

x Î (A È B) Ç (A È C).

Нехай тепер

x Î B Ç C

Þ за означенням перерізу множин

x Î B  і  x Î C

Þ за означенням об'єднання множин

x Î A È B  і  x Î A È C

Þ за означенням перерізу множин

x Î (A È B) Ç (A È C).

Отже, в обох випадках довільний елемент множини A È (B Ç C) є елементом множини (A È B) Ç (A È C), тоді за означенням підмножини множини має місце включення

A È (B Ç C) Ì (A È B) Ç (A È C).

(2)

2. Нехай тепер x – будь-який елемент, такий, що

x Î (A È B) Ç (A È C) Þ за означенням перерізу множин

x Î A È B  і  x Î A È C Þ за означенням об'єднання множин

(x Î A або x Î B) і (x Î A або x Î C), що означає можливість таких чотирьох випадків:

1) x Î A,   2) x Î A і x Î C,   3) x Î B  і  x Î A,   4) x Î B  і  x Î C.

Випадки 2) і 3) зводяться до випадку 1), а тому достатньо розглянути лише випадки 1) і 4).

Нехай

x Î A Þ за означенням об'єднання множин

x Î A È (B Ç C).

Нехай тепер

x Î B  і  x Î C Þ за означенням перерізу множин

x Î B Ç C Þ за означенням об'єднання множин

x Î A È (B Ç C).

Значить, у всіх випадках довільний елемент множини (A È B) Ç (A È C) є елементом множини A È (B Ç C), тоді за означенням підмножини множини має місце включення

A È (B Ç C) É (A È B) Ç (A È C).

(3)

На основі (2) і (3) за антисиметричною властивістю відношення включення має місце доводжувана рівність (1).

II. Доведемо тепер один із законів де Моргана, наприклад,

.

(4)

Нехай x – будь-який елемент такий, що

x Î  Þ за означенням доповнення множини

x Ï A È B Þ за означенням об'єднання множин

x Ï A  і  x Ï B Þ за означенням доповнення

x Î   і  x Î  Þ за означенням перерізу множин

x Î Ç.

Отже, довільний елемент множини  є елементом множини Ç, тоді за означенням підмножини множини має місце включення

.

(5)

Нехай тепер x – будь-який елемент такий, що

x Î  Ç  Þ за означенням перерізу множин

x Î   і  x Î   Þ за означенням доповнення множини

x Ï A  і  x Ï B Þ за означенням об'єднання множин

x Ï A È B Þ за означенням доповнення множини

x Î .

Отже, довільний елемент множини  є елементом множини , тоді за означенням підмножини множини має місце включення

 É  Ç .

(6)

На основі (5) і (6) за антисиметричною властивістю відношення включення множин має місце доводжувана рівність (4). Аналогічно доводяться рівності

A Ç (B È C) = (A Ç BÈ (A Ç C)    і    =È.   ◄

  1.  Число елементів у об’єднанні кількох скінченних множин.

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

Знайдемо спочатку число елементів в об'єднанні двох довільних скінченних множин X і Y. Позначимо число елементів у множинах X, Y, X È Y і X Ç Y відповідно |X|, |Y|, |X È Y| і |X Ç Y|. У сумі |X| + |Y| спільні елементи множин X і Y, тобто елементи, що належать X Ç Y, враховуються двічі, а в |X È Y|, у силу того, що елементи не повторюються у множині, вони враховуються один раз, а тому матиме місце рівність

|X È Y| = |X| + |Y| – |X Ç Y|.

Рівність можна одержати також, скориставшись кругами Ейлера і вважаючи, що число елементів у множині є площею фігури, якою зображено дані множини (мал. 13).

Мал. 13.

Одержуємо теорему про число елементів в об'єднанні двох скінченних множин.

Теорема 2. Для довільних скінченних множин X і Y має місце рівність

|X È Y| = |X| + |Y| – |X Ç Y|.

Коли множини X і Y не перетинаються, тобто X Ç Y = Æ, то з теореми 2 одержується наслідок.

Наслідок 1. Якщо множини X і Y – скінченні і не перетинаються, то має місце рівність

|X È Y| = |x| + |y|.

Для довільних множин X і Y, коли множина Y є підмножиною множини X, тобто Y Ì X, то мають місце рівності

(X \ YÈ Y = X  і  (X \ YÇ Y = Æ.

Звідси за наслідком 1 одержуємо, що для довільних скінченних множин X i Y, якщо Y Ì X, то має місце рівність

|x \ y| + |y| = |x|.

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

Теорема 3. Для довільних скінченних множин X і Y, якщо Y Ì X, то має місце рівність

|| = |X| – |Y|,

або, що те саме,

|X \ Y| = |X| – |Y|.

За допомогою теореми 2 і властивостей операцій над множинами можна довести теорему про число елементів у об'єднанні трьох скінченних множин.

Теорема 4. Для довільних скінченних множин X, Y і Z має місце рівність

|X È Y È Z| = |X| + |Y| + |Z| – |X Ç Y| – |X Ç Z| – |Y Ç Z| + |X Ç Y Ç Z|.

Для того, щоб узагальнити наслідок 1 для кількох довільних скінченних множин, введемо деякі відношення між множинами. Говорять, що множини X1, X2, ... , Xn, ...

1) перетинаються, якщо вони мають спільні елементи, тобто існує принаймні один елемент, який належить усім цим множинам, отже,

X1 Ç X2 Ç ... Ç Xn Ç ... ≠ Æ;

2) не перетинаються, якщо вони не мають спільних елементів, тобто не існує елемента, який належав би всім цим множинам, отже,

X1 Ç X2 Ç ... Ç Xn Ç ... = Æ;

3) попарно не перетинаються, якщо Xi Ç Xj = Æ для всіх i та j таких, що i ≠ j, ij = 1, 2, 3, ... .

Очевидно, якщо множини попарно не перетинаються, то вони не перетинаються, але коли множини не перетинаються, то не обов'язково вони попарно не перетинаються. Це видно для випадку трьох множин X, Y і Z, які зображено за допомогою кругів Ейлера на мал. 14.

Мал. 14.

Теорема 5 (правило суми). Якщо множини X1, X2, ..., Xn – скінченні і попарно не перетинаються, то число елементів у їх об'єднанні дорівнює сумі числа елементів у цих множинах, тобто

|X1 È X2 È ... È Xn| = |X1| + |X2| + ... + |Xn|.

  1.  Поняття про розбиття множини на підмножини, які попарно не перетинаються (розбиття множини на класи).

Розбиття множини на класи за допомогою однієї, двох і трьох властивостей її елементів.

Відношення між множинами та операції над ними дають змогу ввести поняття розбиття множини на класи, яким широко користуються, наприклад, при проведенні класифікацій. Система непорожніх підмножин множини M називається розбиттям множини M на підмножини, які попарно не перетинаються, якщо кожний елемент множини M належить одній і тільки одній із підмножин системи, при цьому кожна підмножина системи називається класом розбиття.

У більшості випадків замість терміну "розбиття множини на підмножини, які попарно не перетинаються" користуються терміном "розбиття множини на класи".

Якщо система підмножин M1, M2, ... , Mn, ... множини M є розбиттям її на класи, то виконуються умови:

1) всі підмножини системи є непорожніми множинами;

2) підмножини системи попарно не перетинаються;

3) об'єднання всіх підмножин системи дорівнює множині M.

Навпаки, якщо для системи підмножин множини M виконуються вказані три умови, то вона є розбиттям множини M на класи.

Отже, доведено теорему.

Теорема 9. Система підмножин є розбиттям множини на класи тоді і тільки тоді, коли виконуються умови:

1) кожна із підмножин системи непорожня,

2) підмножини системи попарно не перетинаються,

3) об'єднання всіх підмножин системи дорівнює множині M.

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

Нехай M – непорожня множина і задано властивість A. Кожний елемент множини M або має властивість A, або її не має. Зважаючи на це, у множині M можна виділити такі дві підмножини:

1) множину A тих елементів, які мають властивість A:

A = {x Î M | A(x)};

2) множину B тих елементів, які не мають властивості A:

B = {x Î M | (x)},

де (x) означає, що елемент x множини M не має властивості A.

Очевидно, що множина B є доповненням множини A, тобто B = . Маємо, що A Ç  = Æ і A È  = M. Звідси одержуємо, якщо множини A і  непорожні, то вони і є класами розбиття множини M за допомогою однієї властивості. Але може трапитися, що одна із множин або A або  є порожньою (коли всі елементи множини M або мають властивість A або не мають властивості A). У цьому випадку розбиття множини M за однією властивістю складається з одного класу.

Отже, за допомогою однієї властивості довільна множина може бути розбита не більше як на 2 = 21 класи.

Розглянемо тепер випадок розбиття множини M на класи за допомогою трьох властивостей A, B, C.

Скористаємося позначеннями, прийнятими при розбитті множини на класи за допомогою однієї властивості:

A = {x Î M | A(x)},  B = {x Î M | B(x)},  C = {x Î M | C(x)},

 = {x Î M | (x)},   = {x Î M | (x)},   = {x Î M | (x)}.

Логічно можливі лише такі види підмножин множини M, які зручно записати як результати операцій над множинами A, B, C, , , :

1) Множина елементів, які мають всі три властивості

A Ç B Ç C.

(1)

2) Множини елементів, що мають тільки дві властивості з трьох

A Ç B Ç ,

(2)

A Ç  Ç C,

(3)

 Ç B Ç C.

(4)

3) Множини елементів, що мають тільки одну властивість з трьох

A Ç  Ç ,

(5)

 Ç B Ç ,

(6)

 Ç  Ç C.

(7)

4) Множина елементів, що не мають жодної з трьох властивостей

 Ç  Ç .

(8)

Всього одержано 8 = 23 підмножин множини M. Із самого задання множин (1) – (8) видно, що кожний елемент множини M належить одній і тільки одній з них, тобто множини (1) – (8) у випадку, коли всі вони непорожні, є класами розбиття множини M за допомогою трьох властивостей. Коли ж деякі із підмножин (1) – (8) виявляться порожніми, то множина M буде розбита на менше, ніж 8 класів.

Аналогічно міркуючи, можна довести теорему.

Теорема 10. Довільну непорожню множину можна розбити не більше як на 2n класів за допомогою n властивостей.

При проведенні міркувань про розбиття множини на класи зручно користуватися кругами Ейлера.

Задача 9. Розбити множину всіх трикутників на класи за допомогою двох властивостей:

Р – "трикутник рівнобедрений",

R – "трикутник рівносторонній".

► Позначимо T – множина всіх трикутників.

Нехай Р = {x Î Т | Р(x)}  i  R = {x Î Т | R(x)}.

Оскільки кожний рівносторонній трикутник є рівнобедреним, але не кожний рівнобедрений трикутник є рівностороннім, то множина R є власною підмножиною множини Р. Зображення множин Т, Р і R кругами Ейлера буде таким, як показано на мал. 17.

Мал. 17.

З його допомогою робимо висновок, що за вказаними властивостями множина Т розіб'ється на три класи:

(1) R – множина рівносторонніх трикутників;

(2) Р Ç  – множина рівнобедрених, але не рівносторонніх трикутників;

(3)  Ç  =  – множина нерівнобедрених трикутників. На мал. 17 ці множини заштриховано:

R ,   Р Ç  – ,    – .  ◄

  1.  Картеж та його основні характеристики. Впорядкована пара.

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

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

Об'єкти, з яких складається кортеж, називаються його компонентами, а число компонент кортежу – його довжиною.

Кортеж довжиною n, перша компонента якого a1, друга – a2, ..., n–та компонента – an, записується (a1, a2, ..., an) або <a1, a2, ..., an>. Іноді розглядається кортеж довжиною 0, який називається порожнім і позначається ( ) або < > .

Два кортежі називаються рівними, якщо вони мають рівні довжини і відповідні їх компоненти збігаються. Кортежі довжиною два називаються впорядкованими парами або парами.

  1.  Декартів добуток множин. Закони декартового множення множин.

Декартовим добутком довільних множин X і Y називається множина всіх упорядкованих пар, перша компонента яких належить множині X, а друга – Y, позначається X × Y.

Символічно означення декартового добутку множин X і Y запишеться

X × Y: = {(xy) | x Î X і y Î Y}.

Задача 6. Знайти X × Y і Y × X, якщо X = {1, 2, 3} і Y = {aб}.

► Користуючись означенням декартового добутку двох множин, дістанемо

X × Y = {(1, a), (1, б), (2, a), (2, б), (3, a), (3, б)};

Y × X = {(a, 1), (a, 2), (a, 3), (б, 1), (б, 2), (б, 3)}.  ◄

Множину пар декартового добутку двох множин називають його графіком. Взагалі, у математиці прийнято називати довільну множину пар графіком.

Правило, за яким кожній парі множин X і Y ставиться у відповідність їх декартів добуток X × Y, називається операцією декартового множення.

На основі означення декартового добутку множин для довільної множини X має місце рівність

X × Æ = Æ × X = Æ.

Аналіз задачі 6 показує, що операція декартового множення множин некомутативна, тобто, що для довільних множин X i Y

X × Y ≠ Y × X.

Очевидно, що операція декартового множення множин неасоціативна, тобто для довільних множин X, Y і Z

(X × Y) × Z ≠ X × (Y × Z).

Операція декартового множення множин пов'язана з операціями перерізу, об'єднання і віднімання множин дистрибутивними законами, причому, зважаючи на її некомутативність, потрібно розглядати два їх види.

Теорема 6. Для довільних множин A, B і C мають місце рівності

A × (B Ç C) = (A × BÇ (A × C)  і  (B Ç C) × A = (B × AÇ (C × A);

A × (B È C) = (A × BÈ (A × C)  і  (B È C) × A = (B × AÈ (C × A);

A × (B \ C) = (A × B) \ (A × C)  і  (B \ C) × A = (B × A) \ (C × A).

► Доведемо рівність

A × (B \ C) = (A × B) \ (A × C).

(1)

1. Нехай (xy) – довільна пара така, що

(xyΠA × (B \ C) Þ за означенням декартового добутку множин

x Î A  і  y Î B \ C Þ за означенням різниці множин

x Î A  і  y Î B  і  y Ï C Þ за означенням декартового добутку множин

(xyΠA × B  і  (xyÏ A × C Þ за означенням різниці множин

(xyΠ(A × B) \ (A × C).

Таким чином, довільна пара множини A × (B \ C) належить множині (A × B) \ (A × C), тобто за означенням підмножини множини має місце включення

A × (B \ CÌ (A × B) \ (A × C).

(2)

2. Нехай тепер (xy) – довільна пара така, що

(xyΠ(A × B) \ (A × C) Þ за означенням різниці множин

(xyΠ(A × B)  і  (xyÏ (A × C) Þ за означенням декартового добутку множин

x Î A  і  y Î B  і  y Ï C Þ за означенням різниці множин

x Î A  і  y Î B \ C Þ за означенням декартового добутку множин

(xyΠA × (B \ C).

Значить, довільна пара множини (A × B) \ (A × C) належить множині A × (B \ C), тобто за означенням підмножини множини має місце включення

A × (B \ CÉ (A × B) \ (A × C).

(3)

На основі (2) і (3) за антисиметричною властивістю відношення включення має місце доводжувана рівність (1).

Усі інші дистрибутивні закони доводяться аналогічно.  ◄

Поняття декартового добутку двох множин можна узагальнити на довільну скінченну сукупність множин. Декартовим добутком довільних множин X1, X2, ..., Xn, де n ≥ 2, називається множина всіх кортежів довжиною n, перша компонента яких належить множині X1, друга – X2 і т. д., n–та компонента – множині Xn, позначається

X1 × X2 × ... × Xn.

Якщо множини такі, що X1 = X2 = ... = Xn = X, то їх декартів добуток називається декартовим nтим степенем множини X і позначається Xn.

При n = 2 множина X2 називається декартовим квадратом множини X, а при n = 3 множина X3 – декартовим кубом множини X. За означенням покладають X1:= X  і  X0:= {( )}.

  1.  Число елементів в декартовому добутку кількох

скінченних множин.

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

Розглянемо випадок двох множин. Коли множина A – скінченна і B – порожня, то за властивістю декартового добутку множин одержуємо

|A × Æ| = |Æ| = 0 = |A|·|Æ| = |A|·|B|.

Коли ж множина A – скінченна, а B – одинична, то очевидно, що

|A × B| = |A| = |A|·1 = |A|·|B|.

Розглянемо тепер випадок, коли A і B є скінченними непорожніми і неодиничними множинами. Нехай |A| = k > 1 і |B| = m > 1.

Отже, A = {x1, x2, ..., xk} і B = {y1, y2, ..., ym}.

Розмістимо пари декартового добутку A × B у вигляді такої таблиці:

(x1y1), (x1y2), ... (x1ym),

(x2y1), (x2y2), ... (x2ym),

.........................................

(xky1), (xky2), ..., (xkym).

У кожному її рядку є m пар, всього таких рядків є k. А тому всього пар у даній таблиці буде

.

Ці міркування і є доведенням теореми.

Теорема 7. Число елементів у декартовому добутку двох скінченних множин A і B дорівнює добутку числа елементів у кожній з них, тобто

|A × B| = |A|·|B|.

Теорему 7 можна узагальнити на випадок кількох скінченних множин, її називають правилом добутку.

Теорема 8 (правило добутку). Число елементів у декартовому добутку скінченних множин A1, A2, ..., An дорівнює добутку числа елементів у кожній з них, тобто

|A1 × A2 × ... × An| = |A1|·|A2|·...·|An|.

Наслідок 2. Для довільних скінченної множини A і натурального числа n має місце рівність:

|An| = |A|n.

Задача 7. Скільки можна записати різних чотирицифрових чисел за допомогою цифр 0, 1, 2, 3 і 4?

► Кожне чотирицифрове число, записане за допомогою вказаних цифр, є кортежем довжиною 4, компонентами якого є елементи множини A = {0, 1, 2, 3, 4}. Всього кортежів довжиною 4 з елементів множини A буде

|A4| = |A|4 = 54.

З них треба вилучити ті кортежі, які починаються цифрою 0, їх буде стільки, скільки є кортежів довжиною 3 з елементів A, тобто

|A3| = |A|3 = 53.

Отже, всього чотирицифрових чисел за допомогою цифр 0, 1, 2, 3 і 4 можна записати

54 – 53 = 4·53 = 4·125 = 500.

Задачу можна розв'язати і по-іншому.

Множину всіх чотирицифрових чисел, які записані за допомогою цифр 0, 1, 2, 3 і 4, можна розглядати як декартів добуток чотирьох множин, з яких перша {1, 2, 3, 4}, а всі інші {0, 1, 2, 3, 4}. І тоді на основі правила добутку добуток всіх чисел знаходиться як

· 5 · 5 · 5 = 500.

Відповідь: 500.  ◄


НА САМОСТІЙНЕ ОПРАЦЮВАННЯ

  1.  Поняття про операції та їх види

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

Під nарною (nмісною) операцією розуміють правило, за яким n об'єктам, взятим у певному порядку, ставиться у відповідність не більше як один об'єкт, що називається результатом операції. Самі ж об'єкти, яким ставиться у відповідність результат, називаються компонентами операції. У випадку, коли компонента одна, операція називається унарною (одномісною), якщо їх дві – бінарною (двомісною), три – терарною (тримісною) і т. д. За домовленістю бінарні операції часто називають операціями.

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

1) з усіх значень сполучника "і" вибране таке – властивість з'єднувати два твердження, утворюючи нове твердження, яке має місце тоді і тільки тоді, коли мають місце обидва твердження;

2) з усіх значень сполучника "або" виділене його так зване нероздільне значення, – властивість з'єднувати два твердження, утворюючи нове твердження, яке має місце тоді і тільки тоді, коли має місце хоч одне з них.

Якщо ж твердження, що утворене з двох тверджень, має місце лише тоді, коли має місце тільки одне з них, то вживають "або ... або".

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

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

Теорема 1. Для довільних множин A, B і C мають місце:

1. Властивості порожньої множини для перерізу і об'єднання:

A Ç Æ  = Æ,  A È Æ  = A.

2. Властивості універсальної множини для перерізу і об'єднання:

a Ç U = a,  A È U = U.

3. Комутативні закони операцій перерізу і об'єднання:

A Ç B = B Ç A,  A È B = B È A.

4. Асоціативні закони операцій перерізу і об'єднання:

(a Ç B) Ç C = A Ç (B Ç C),  (A È B) È C = A È (B È C).

5. Закони ідемпотентності операцій перерізу і об'єднання:

A Ç A = A,   A È A = A.

6. Дистрибутивні закони, які пов'язують операції перерізу і об'єднання:

A Ç (B È C) = (A Ç B) È (A Ç C) – дистрибутивність перерізу відносно об'єднання;

A È (B Ç C) = (A È B) Ç (A È C) – дистрибутивність об'єднання відносно перерізу.

7. Закон подвійного доповнення:  = A.

8. Закони де Моргана, які пов'язують операції перерізу, об'єднання і доповнення:

Зауваження. Іноді замість речень виду "З твердження A на підставі твердження C випливає твердження B", що часто зустрічається при доведеннях, користуються їх символічним записом:

A Þ B на підставі твердження C.

► Властивості 1, 2, 3, 4, 5 і 7 безпосередньо випливають з означень операцій над множинами.

I. Доведемо дистрибутивність об'єднання множин відносно перерізу, тобто, що для довільних множин A, B і C має місце рівність:

A È (B Ç C) = (A È B) Ç (A È C).

(1)

1. Нехай x – будь-який елемент такий, що

x Î A È (B Ç C) Þ за означенням об'єднання множин

x Î A  або  x Î B Ç C, що означає можливість трьох таких випадків:

1) x Î A,   2) x Î B Ç C,   3) x Î A  і  x Î B Ç C.

Оскільки третій випадок є підвипадком перших двох, то достатньо розглянути лише їх.

Нехай

x Î A

Þ за означенням об'єднання множин

x Î A È B  і  x Î A È C

Þ за означенням перерізу множин

x Î (A È B) Ç (A È C).

Нехай тепер

x Î B Ç C

Þ за означенням перерізу множин

x Î B  і  x Î C

Þ за означенням об'єднання множин

x Î A È B  і  x Î A È C

Þ за означенням перерізу множин

x Î (A È B) Ç (A È C).

Отже, в обох випадках довільний елемент множини A È (B Ç C) є елементом множини (A È B) Ç (A È C), тоді за означенням підмножини множини має місце включення

A È (B Ç C) Ì (A È B) Ç (A È C).

(2)

2. Нехай тепер x – будь-який елемент, такий, що

x Î (A È B) Ç (A È C) Þ за означенням перерізу множин

x Î A È B  і  x Î A È C Þ за означенням об'єднання множин

(x Î A або x Î B) і (x Î A або x Î C), що означає можливість таких чотирьох випадків:

1) x Î A,   2) x Î A і x Î C,   3) x Î B  і  x Î A,   4) x Î B  і  x Î C.

Випадки 2) і 3) зводяться до випадку 1), а тому достатньо розглянути лише випадки 1) і 4).

Нехай

x Î A Þ за означенням об'єднання множин

x Î A È (B Ç C).

Нехай тепер

x Î B  і  x Î C Þ за означенням перерізу множин

x Î B Ç C Þ за означенням об'єднання множин

x Î A È (B Ç C).

Значить, у всіх випадках довільний елемент множини (A È B) Ç (A È C) є елементом множини A È (B Ç C), тоді за означенням підмножини множини має місце включення

A È (B Ç C) É (A È B) Ç (A È C).

(3)

На основі (2) і (3) за антисиметричною властивістю відношення включення має місце доводжувана рівність (1).

II. Доведемо тепер один із законів де Моргана, наприклад,

.

(4)

Нехай x – будь-який елемент такий, що

x Î  Þ за означенням доповнення множини

x Ï A È B Þ за означенням об'єднання множин

x Ï A  і  x Ï B Þ за означенням доповнення

x Î   і  x Î  Þ за означенням перерізу множин

x Î Ç.

Отже, довільний елемент множини  є елементом множини Ç, тоді за означенням підмножини множини має місце включення

.

(5)

Нехай тепер x – будь-який елемент такий, що

x Î  Ç  Þ за означенням перерізу множин

x Î   і  x Î   Þ за означенням доповнення множини

x Ï A  і  x Ï B Þ за означенням об'єднання множин

x Ï A È B Þ за означенням доповнення множини

x Î .

Отже, довільний елемент множини  є елементом множини , тоді за означенням підмножини множини має місце включення

 É  Ç .

(6)

На основі (5) і (6) за антисиметричною властивістю відношення включення множин має місце доводжувана рівність (4). Аналогічно доводяться рівності

A Ç (B È C) = (A Ç BÈ (A Ç C)    і    =È.   ◄


 

А также другие работы, которые могут Вас заинтересовать

11822. Проектирование программ линейной структуры 261 KB
  Лабораторная работа №2. Проектирование программ линейной структуры 1 Цель и порядок работы Цель работы – изучить структуру программы на языке C операторы присваивания ввода и вывода данных используемые при составлении программ линейной структуры. Порядок вып...
11823. Операторы ветвления и выбора 148.5 KB
  Лабораторная работа №3. Операторы ветвления и выбора 1 Цель и порядок работы Цель работы – изучить операторы используемые для организации ветвления в программе. Познакомится с логическими выражениями и операциями. Порядок выполнения работы: ознакомиться с...
11824. Операторы цикла и передачи управления 110 KB
  Лабораторная работа №4. Операторы цикла и передачи управления 1 Цель и порядок работы Цель работы – изучить операторы используемые при организации программ циклических вычислительных процессов получить практические навыки в составлении программ. Порядок выпо...
11825. Итерационные и арифметические циклы. Вложенные циклы 297 KB
  Лабораторная работа №5. Итерационные и арифметические циклы. Вложенные циклы 1 Цель и порядок работы Цель работы – изучить операторы используемые при организации программ циклических вычислительных процессов получить практические навыки в составлении программ...
11826. Лабораторная работа №6. Массивы 164.5 KB
  Лабораторная работа №6. Массивы 1 Цель и порядок работы Цель работы – получение практических навыков алгоритмизации и программирования вычислительных процессов с использованием массивов. Порядок выполнения работы: ознакомиться с описанием лабораторной раб
11827. Указатели и ссылки. Имя массива как указатель. Динамические массивы 220.5 KB
  Лабораторная работа №7. Указатели и ссылки. Имя массива как указатель. Динамические массивы 1 Цель и порядок работы Цель работы – изучить работу с указателями ссылками получить навыки программирования с использованием динамических массивов. Порядок выполнения ра...
11828. Лабораторная работа №8. Функции 175.5 KB
  Лабораторная работа №8. Функции 1 Цель и порядок работы Цель работы – изучить возможности языка по организации функций получить практические навыки в составлении программ с их использованием. Порядок выполнения работы: ознакомиться с описанием лабораторной ...
11829. Отладка программ в интегрированной среде Microsoft Visual C++ 2008 189.5 KB
  Лабораторная работа №9. Отладка программ в интегрированной среде Microsoft Visual C 2008 1 Цель и порядок работы Цель работы – изучить инструментальные средства и возможности отладки программ в интегрированной среде Microsoft Visual C 2008 Visual Studio 2008. Порядок выполнения работы...
11830. Типы данных, определяемые пользователем. Структуры и объединения 189.5 KB
  Лабораторная работа №10. Типы данных определяемые пользователем. Структуры и объединения 1 Цель и порядок работы Цель работы – ознакомиться с типами данных определяемыми пользователем и их применением в процессе программирования. Порядок выполнения работы: ...