18276

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

Лекция

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

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

Украинкский

2013-07-07

256.5 KB

95 чел.

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


 

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

29760. Цільова підготовка педагога до уроку 20.07 KB
  Безпосередня підготовка педагога до уроку передбачає, насамперед, створення поурочного плану-конспекту, який допомагає цілеспрямовано провести урок. Системний підхід до планування уроку вимагає дотримуватися такої послідовності дій
29761. Основные понятия химической термодинамики. Первый закон термодинамики. Закон Гесса. Теплоёмкость 26.25 KB
  Часть системы с присущей ей химическим составом и макроскопическими свойствами называется фазой. В каждый момент времени состояние системы характеризуется параметрами состояния которые разделяются на экстенсивные и интенсивные параметры. Интенсивные определяются лишь специфической природой системы: давление температура химический потенциал и т. Термодинамическими параметрами состояния называются параметры которые измеряются непосредственно и выражают интенсивные свойства системы.
29762. Второй и третий закон термодинамики. Энтропия. Термодинамический потенциал 21.3 KB
  Второй закон термодинамики Все процесс в которых один вид энергии превращается в другой строго подчиняются первому закону термодинамики. Критерий осуществимости процесса в том или ином направлении и устанавливаются вторым законом термодинамики. Математическое выражение второго закона термодинамики Следствием второго закона термодинамики является существование особой функции состояния.
29763. Химический потенциал. Химическое равновесие. Закон действующих масс. Константы равновесия 21.55 KB
  Химическое равновесие Эксперименты показывают что химические реакции одновременно протекают в двух направлениях. Таким образом химическое равновесие помимо равенства скоростей прямой и обратной реакции и постоянства концентраций при неизменных внешних условиях обладают ещё следующими свойствами: Подвижностью т. Возможностью достижения равновесия как со стороны исходных веществ так и со стороны продуктов реакции. С термодинамической точки зрения они необратимы и работа их не является максимальной однако можно мысленно представить...
29764. Фазовое равновесие в гетерогенных системах. Правило фаз Гиббса. Диаграммы состояния 32.71 KB
  Правило фаз Гиббса. Фазовое равновесие в гетерогенных системах. Правило фаз Гиббса. При рассмотрении фазовых равновесий в системах необходимо различать фазы компоненты соединения твёрдые растворы и механические смеси.
29765. Классификация проводящих материалов, особенности тонкоплёночных металлов, проводящие материалы в микроэлектронике 52.44 KB
  Удельное сопротивление алюминия в 16 раза больше удельного сопротивления меди но алюминий в 35 раза легче меди. Недостатками меди являются её подверженность атмосферной коррозии с образованием оксидных и сульфидных плёнок. Например электропроводность меди очень чувствительна к наличию примеси. Содержание в меди 05 никеля олова или алюминия снижает электропроводность меди от 25 до 40.
29766. Классификация полупроводниковых материалов. Собственные и примесные полупроводники. Примеси в полупроводниках 29.49 KB
  Примеси в полупроводниках. Преднамеренное введение примеси называется легированием соответствующие примеси легирующие а полупроводник легированным или примесным. Кроме легирующих примесей существуют случайные или фоновые примеси непреднамеренно вводимые в полупроводник в процессе его производства и обработки. Фоновые примеси как правило ухудшают основные свойства материала и затрудняют управление ими.
29767. Монокристаллический кремний. Его применение, получение и свойства 36.46 KB
  Применение полупроводникового кремния. тонн кремния ежегодно Япония США Германия. Это базовый материал микроэлектроники который потребляет 80 полупроводникового кремния. Более 90 всех солнечных элементов изготавливаются из кристаллического кремния.
29768. Поликристаллический кремний. Применение, свойства, получение 26.53 KB
  Применение поликристаллического кремния Поликристаллический кремний весьма распространённый материал в технологии полупроводниковых приборов и интегральных схем. Возможность получения поликристаллического кремния с электрическим сопротивлением отличающимся на несколько порядков а также простота технологии привели к тому что он используется в технологии интегральных схем с одной стороны в качестве высокоомного материала затворов нагрузочных резисторов а с другой в качестве низкоомного материала межсоединений. Достоинства разводки на основе...