| Назва: | Елементи комбінаторики |
| Тип: | Реферати |
| Мова: | Українська |
| Розмiр: | 4,18 KB |
| Скачувань: | 10 |
Елементи комбінаторики
§ 1. Поняття множини. Операції над множинами
Поняття множини належить до первісних понять математики, якому не дається означення Множину можна уявити собі як су¬купність деяких предметів, об'єднаних за довільною характерис¬тичною ознакою Наприклад, множина учнів класу, множина цифр десяткової нумерації (0, 1, 2, 3, 4, 5, 6, 7, 8, 9), множина натуральних чисел, множина зернин у даному колосі, множина букв українського алфавіту, множина точок на прямій
Предмети, з яких складається множина, називаються її елементами і позначаються малими буквами латинського алфавіту. Наприклад, а = 5 - елемент множини цифр десяткової нумерації Для позначення множин використовують великі букви латинсь¬кого алфавіту або фігурні дужки, всередині яких записуються елементи множини При цьому порядок запису елементів не має значення Наприклад, множину цифр десяткової нумерації мож¬на позначити буквою М (чи будь-якою великою буквою латин¬ського алфавіту) або записати так {1, 3, 5, 2, 4, 6, 8, 7, 9, 0}
Належність предмета даній множині позначається символом , а неналежність - символом (інколи ) Наприклад, число 7 А, де А - множина чисел першого десятка, а число 12 A.
Множини бувають скінченні і нескінченні. У скінченній множині міститься певна кількість елементів, тобто кількість елементів скінченної множини виражається натуральним чис¬лом Наприклад, множина М цифр десяткової нумерації скінчен¬на і містить десять елементів. У нескінченній множині - нескін¬ченна кількість елементів. Наприклад, множина натуральних чисел, множина точок прямої - нескінченні множини.
Множина, в якій немає жодного елемента, називається порож¬ньою і позначається символом . Наприклад, множина точок перетину двох паралельних прямих - порожня множина
Якщо множина В складається з деяких елементів даної мно¬жини А (і тільки з них), то множина В називається підмножиною множини А. У такому разі співвідношення між множинами А і В позначається так В А (читається "В міститься в А" або "В - підмножина А"). Якщо В може й дорівнювати А, то вживається символ В А. Знак називається знаком нестрогого включення, а знак - знаком строгого включення.
Порожня множина є підмножиною будь-якої множини, тобто А.
Саму множину А можна розглядати як підмножину А, тобто А А.
Множину задають двома основними способами:
1) переліченням всіх її елементів;
2) описанням характеристичної властивості її елементів. Наприклад: а) В = {o,,¡} - множина, задана переліченням елементів; б) X - множина коренів квадратного рівняння х2 = 25. Множина X задана характеристичною властивістю елементів - бути коренем рівняння х2 = 25". Цю саму множину можна зада¬ти і переліченням її елементів: X = {-5; 5}.
Дві множини називаються рівними, якщо вони складаються з тих самих елементів. Наприклад, множини коренів рівняння х2 = 25 і |x| = 5 рівні між собою. Справді, X = {-5; 5} і Y = {-5; 5}, де Y - множина розв'язків рівняння |x|-5. Отже, X = Y.
Над множинами виконуються певні операції (дії). Зазначимо три з них.
Переріз множин. Перерізом множин А і В називається множина С, яка складається з усіх тих і тільки тих елемен¬тів, які належать коленій з даних множин А і В.
Приклад 1. Нехай А - множина всіх дільників числа 32, тобто А = {І, 2, 4, 8, 16, 32), а В - множина всіх дільників чис¬ла 24, тобто В = {1, 2, 3, 4, 6, 8, 12, 24}. Тоді перерізом множин А і В є множина С = {1, 2, 4, 8}, яка складається зі спільних дільників чисел 32 і 24.
Схематично переріз множин А і В можна зобразити за допо¬могою фігур. Символічно позначається так: С = А В і читається: "С є перерізом А і В".
Приклад 2. Нехай М - множина прямокутників, N - множина ромбів, тоді Р = М N - множина квадратів.
Об'єднання множин. Об'єднанням (або сумою) двох мно¬жин А і В називається така множина С, яка складається з усіх елементів множин А і В, і тільки з них.
Позначається це так: С = А В і читається: "С є об'єднанням А і В".
Якщо множини А і В мають спільні елементи, тобто А В 0, то кожний з цих спільних елементів береться в множину С тільки один раз.
Приклад 3. А ={1,2, 3,4}, В = {3, 4, 5, 6}, тоді С = {1,2,3,4,5,6}.
Приклад 4. Q - множина раціональних чисел, І - мно¬жина ірраціональних чисел. Тоді множиною R всіх дійсних чисел буде об'єднання множин Q і І, тобто R = Q І.
Операції над множинами широко використовуються в мате¬матиці та інших науках, а також у практиці. Наприклад, розв'яз¬ками системи рівнянь є переріз множин розв'язків кожного рів¬няння, а об'єднання їх є множиною розв'язків сукупності рів¬нянь.
Віднімання множин. Доповнення множини. Різницею двох множин А і В називається така множина С, яка складається з усіх елементів множини А, що не належать множині В.
Позначається це так: С = А \ В і читається: "С є різницею А і В".
Приклад 5. а) А= {5,6, 8, 12}, В= {5, 6}, тобто В А, тоді С = А \ В= {8, 12};
б) А = {5, 6, 8, 12}, В = {8, 12, 1, 2}, тоді С = А\ В = {5, 6};
в) А = {5, 6, 12}, В = {1, 2}, тоді С = А \ В = {5, 6, 12};
§ 1. Поняття множини. Операції над множинами
Поняття множини належить до первісних понять математики, якому не дається означення Множину можна уявити собі як су¬купність деяких предметів, об'єднаних за довільною характерис¬тичною ознакою Наприклад, множина учнів класу, множина цифр десяткової нумерації (0, 1, 2, 3, 4, 5, 6, 7, 8, 9), множина натуральних чисел, множина зернин у даному колосі, множина букв українського алфавіту, множина точок на прямій
Предмети, з яких складається множина, називаються її елементами і позначаються малими буквами латинського алфавіту. Наприклад, а = 5 - елемент множини цифр десяткової нумерації Для позначення множин використовують великі букви латинсь¬кого алфавіту або фігурні дужки, всередині яких записуються елементи множини При цьому порядок запису елементів не має значення Наприклад, множину цифр десяткової нумерації мож¬на позначити буквою М (чи будь-якою великою буквою латин¬ського алфавіту) або записати так {1, 3, 5, 2, 4, 6, 8, 7, 9, 0}
Належність предмета даній множині позначається символом , а неналежність - символом (інколи ) Наприклад, число 7 А, де А - множина чисел першого десятка, а число 12 A.
Множини бувають скінченні і нескінченні. У скінченній множині міститься певна кількість елементів, тобто кількість елементів скінченної множини виражається натуральним чис¬лом Наприклад, множина М цифр десяткової нумерації скінчен¬на і містить десять елементів. У нескінченній множині - нескін¬ченна кількість елементів. Наприклад, множина натуральних чисел, множина точок прямої - нескінченні множини.
Множина, в якій немає жодного елемента, називається порож¬ньою і позначається символом . Наприклад, множина точок перетину двох паралельних прямих - порожня множина
Якщо множина В складається з деяких елементів даної мно¬жини А (і тільки з них), то множина В називається підмножиною множини А. У такому разі співвідношення між множинами А і В позначається так В А (читається "В міститься в А" або "В - підмножина А"). Якщо В може й дорівнювати А, то вживається символ В А. Знак називається знаком нестрогого включення, а знак - знаком строгого включення.
Порожня множина є підмножиною будь-якої множини, тобто А.
Саму множину А можна розглядати як підмножину А, тобто А А.
Множину задають двома основними способами:
1) переліченням всіх її елементів;
2) описанням характеристичної властивості її елементів. Наприклад: а) В = {o,,¡} - множина, задана переліченням елементів; б) X - множина коренів квадратного рівняння х2 = 25. Множина X задана характеристичною властивістю елементів - бути коренем рівняння х2 = 25". Цю саму множину можна зада¬ти і переліченням її елементів: X = {-5; 5}.
Дві множини називаються рівними, якщо вони складаються з тих самих елементів. Наприклад, множини коренів рівняння х2 = 25 і |x| = 5 рівні між собою. Справді, X = {-5; 5} і Y = {-5; 5}, де Y - множина розв'язків рівняння |x|-5. Отже, X = Y.
Над множинами виконуються певні операції (дії). Зазначимо три з них.
Переріз множин. Перерізом множин А і В називається множина С, яка складається з усіх тих і тільки тих елемен¬тів, які належать коленій з даних множин А і В.
Приклад 1. Нехай А - множина всіх дільників числа 32, тобто А = {І, 2, 4, 8, 16, 32), а В - множина всіх дільників чис¬ла 24, тобто В = {1, 2, 3, 4, 6, 8, 12, 24}. Тоді перерізом множин А і В є множина С = {1, 2, 4, 8}, яка складається зі спільних дільників чисел 32 і 24.
Схематично переріз множин А і В можна зобразити за допо¬могою фігур. Символічно позначається так: С = А В і читається: "С є перерізом А і В".
Приклад 2. Нехай М - множина прямокутників, N - множина ромбів, тоді Р = М N - множина квадратів.
Об'єднання множин. Об'єднанням (або сумою) двох мно¬жин А і В називається така множина С, яка складається з усіх елементів множин А і В, і тільки з них.
Позначається це так: С = А В і читається: "С є об'єднанням А і В".
Якщо множини А і В мають спільні елементи, тобто А В 0, то кожний з цих спільних елементів береться в множину С тільки один раз.
Приклад 3. А ={1,2, 3,4}, В = {3, 4, 5, 6}, тоді С = {1,2,3,4,5,6}.
Приклад 4. Q - множина раціональних чисел, І - мно¬жина ірраціональних чисел. Тоді множиною R всіх дійсних чисел буде об'єднання множин Q і І, тобто R = Q І.
Операції над множинами широко використовуються в мате¬матиці та інших науках, а також у практиці. Наприклад, розв'яз¬ками системи рівнянь є переріз множин розв'язків кожного рів¬няння, а об'єднання їх є множиною розв'язків сукупності рів¬нянь.
Віднімання множин. Доповнення множини. Різницею двох множин А і В називається така множина С, яка складається з усіх елементів множини А, що не належать множині В.
Позначається це так: С = А \ В і читається: "С є різницею А і В".
Приклад 5. а) А= {5,6, 8, 12}, В= {5, 6}, тобто В А, тоді С = А \ В= {8, 12};
б) А = {5, 6, 8, 12}, В = {8, 12, 1, 2}, тоді С = А\ В = {5, 6};
в) А = {5, 6, 12}, В = {1, 2}, тоді С = А \ В = {5, 6, 12};