18276

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

Лекция

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

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

Украинкский

2013-07-07

256.5 KB

96 чел.

Лекція 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)    і    =È.   ◄


 

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

48393. ПРИНЦИПЫ ПРОЗЫ ХХ ВЕКА 24.76 KB
  Иллюзия реальность; 2. Основные понятия: Неомифологизм иллюзия реальность текст в тексте бриколаж обэриут приоритет стиля над сюжетом;уничтожение фабулы; синтаксис а не лексика; прагматика а не семантика; наблюдатель; нарушение принципов связности текста; аутестизм. Иллюзия реальность. чрезвычайно характерна игра на границе между вымыслом и реальностью.
48394. Фінанси. Конспект лекцій 1.67 MB
  В загальному вигляді фінанси відображають відносини, які виникають між людьми, підприємствами, фірмами, банками, державними органами з приводу отримання, передавання один одному грошових коштів, взаємних платежів, боргових та інших зобовязань.
48395. Випромінювання оптичного діапазону 315.59 KB
  Серед органів чуття людини природа не передбачила апарат який би сигналізував про наявність радіації її рівні і степені небезпеки. Контакт з іонізуючими випромінюваннями має велику небезпеку для здоровя і життя людини. Гамапромені мають велику проникаючу здатність вони вільно проходять через тіло людини та інші матеріали і мають малу іонізуючу дію. При опроміненні людини дозою 02505 Гр можливі зміни в крові понад 1 Гр розвивається враження всього організму при 2 4 Гр без лікування можлива смерть вище 6 ...
48396. МАРКЕТИНГ. КОНСПЕКТ ЛЕКЦІЙ 115.93 KB
  СУТНІСТЬ ОСНОВНИХ ПОНЯТЬ МАРКЕТИНГУ ТА РОЗВИТОК ЙОГО КОНЦЕПЦІЇ Система маркетингу. Принципи цілі задачі та функції маркетингу. Характеристика видів маркетингу.
48397. Основи локальних мереж 1.54 MB
  Але наглядно переваги мережі виявляються в тому випадку коли всі користувачі працюють з єдиною базою даних запитуючи в неї та заносячи в неї нову наприклад в банку магазині на складі. Використання локальної для організації сумісної роботи компютерів Без мережі також неможна обійтися в тому випадку коли необхідно забезпечити узгоджену роботу декількох компютерів. Визначення локальної мережі Способи і засоби обміну інформацією за останній час запропоновано численність: від най простішого переносу файлів за допомогою дискети до...
48398. Основи охорони праці. Конспект лекцій 3.61 MB
  Основи охорони праці. Конспект лекцій містить лекції з курсу Основи охорони праці Історія охорони праці.
48399. Основи стандартизації та сертифікації 3.7 MB
  Основними її видами є стандарти і технічні умови документи що містять обовязкові для продуцентів норми якості виробу і засоби їх досягнення набір показників якості рівень кожного з них методи і засоби вимірювання випробувань маркування упаковки транспортування і зберігання продукції. Найбільш жорсткі вимоги щодо якості містяться у міжнародних стандартах які розроблюються Міжнародною організацією стандартизації ІСО і використовуються для сертифікації виробів що експортуються у інші країни і реалізуються на світовому...
48400. Психологія праці 89.5 KB
  Ергатична система — (грец. erg справа робота)— це взаємодія людини з обєктивною реальністю, система субєкт праці — людина (трудовий колектив) -предмет праці — засоби праці — виробниче середовище. Ергатична функція - будь яка трудова функція засобів праці що характеризує ергатичну систему.
48401. Професійне спілкування. Вимоги до професійного спілкування 367.5 KB
  Професійне спілкування сприймається як усний мовний контакт між людьми, що зв’язані інтересами справи і мають повноваження для встановлення ділових контактів, вирішення ділових проблем і здійснення конкретних підходів до їх вирішення. Тобто ділова розмова – це «дракон із чотирма головами»