Дискретна математика для програмістів

лекция

1.3 Способи опису множин

Множини можуть задаватися наступними способами:

1) Перерахуванням, тобто списком всіх своїх елементів. Такий спосіб завдання прийнятний тільки при завданні кінцевих множин. Позначення списку - у фігурних дужках. Порядок запису елементів множини при цьому позначенні є неістотним.

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

.

Слід пікреслити, що однією з основних ідей канторівської теорії множин був розгляд множини як нового самостійного обєкта математичного дослідження. Тому необхідно розрізняти такі два різні обєкти, як елемент a і множина {a}, яка складається з єдиного елемента a. Зокрема, множини можуть виступати в ролі елементів якоїсь іншої множини. Наприклад, множина всіх можливих невпорядкованих пар з елементів a, b і c (елементи в парі не співпадають) D = {{a,b},{a,c},{b,c}} складається з трьох елементів і задана цілком коректно.

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

У загальному випадку задання множини M має вигляд: M = {a | F(a)}.

Цей вираз читається так: "множина M - це множина всіх таких елементів a, для яких виконується властивість F", де через F(a) позначено властивість, яку мають елементи множини M і тільки вони.

Приклад.

S = { n | n - непарне число } або S = { n | n = 2k+1, kZ },

X = { x | x = k, kZ },

F = { fi | fi+2 = fi+1 + fi, iN, f1 = f2 = 1 }.

Другий спосіб є більш загальним способом задання множин. Наприклад, введену вище множину D всіх невпорядкованих пар з елементів a, b і c можна задати так:

D = { {x,y} | x{a,b,c}, y{a,b,c} і x y}.

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

Якщо припустити, що існує кілька множин опису алгоритмів, а в дійсності ситуація виглядає саме так, то повинна бути множина модифікацій для цього способу задання множин.

3) Описом характеристичних властивостей, якими повинні володіти елементи множини. Так, множину , що складається з таких елементів , які мають властивість , позначимо в такий спосіб:

.

Так, розглянута вище множина всіх цілих чисел, що є степенями числа 2 може бути записана як . До А ще треба додати 1.

Третій спосіб задання множин дуже важливий, тому що дозволяє повязати поняття "властивість" і "множина" і тим самим за допомогою останнього формалізувати перше для компютера. Наприклад, властивість предмета мати червоний колір для компютера можна задати включенням предмета в певну множину, з елементами якої звязуються всі наслідки того, що вони мають червоний колір.

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

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

Надалі будемо використовувати такі загальноприйняті позначення для числових множин, з якими часто зустрічаємось:

N={1,2,3,…} - множина натуральних чисел;

Z={…,-2,-1,0,1,2,…} - множина цілих чисел;

Q - множина раціональних чисел;

R - множина дійсних чисел;

C - множина комплексних чисел.

Визначення. Множина називається підмножиною (або включенням) множини , якщо кожен елемент множини є елементом множини , тобто, якщо , то .

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

Визначення. Дві множини рівні , якщо всі їхні елементи збігаються. Множини і рівні, якщо і .

Множина, яка містить скінченну кількість елементів, називається скінченною, у протилежному випадку - нескінченною. Кількість елементів у скінченій множині називається потужністю множини і позначається .

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

Приклад.

S = {x | x - непарне число, що ділиться на 2} = ;

K = {x | x R, x2 + 1 = 0} = .

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

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

Визначення. Універсальна множина - це множина, що володіє такою властивістю, що всі розглянуті множини є її підмножинами.

Варто розрізняти поняття належності елементів множини і включення! Так, наприклад, якщо множина , то , , але , у той час як .

Приклад. Які з наведених визначень множин є коректними:

а) , б) , в) , г)?

Чи належить число 6 множині ?

Розвязання:

а) визначення множини перерахуванням елементів коректно.

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

в) визначення множини описом характеристичної властивості коректно.

г) визначення списком множини коректно: елементами множини є множини і , . Однак , тому що даний елемент не перерахований у списку.

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

Приклад. Нехай . Визначити булеан множини . Яка потужність множини ?

Розвязання:

.

Потужність .

Делись добром ;)