Лекція1

МОДУЛЬ 1. ТЕОРІЯ ЧІТКИХ МНОЖИН

ЛЕКЦІЯ 1. ОСНОВНІ ПОНЯТТЯ МНОЖИН ЗМІСТ ЛЕКЦІЇ

1.1.Основні означення.

1.2.Операції над множинами.

1.3.Універсальна множина і доповнення множин.

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

1.5.Список літератури.

1.1. Основні поняття теорії множин. Основні означення

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

які розглядаються як єдине ціле.

Можна говорити про множину стільців у кімнаті, множини людей, що живуть у м.

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

До речі, оскільки "множина" (set) в українській мові як би натякає на "багато",

а поняття "багато" (many) y кожного з нас своє, то, у запобігання суперечки між україномовними людьми, ми будемо слово"множина" використовувати для будь-якої кількості елементів, як і англомовний Захід. Навіть для одного елемента. Навіть у випадках, коли в множині немає жодного елемента - така множина називається пустою! Це, зокрема, дозволить розповідати своїм друзям коректний, з погляду теорії множин, анекдот про "множину ветеранів Полтавської битви, які зараз живуть"...

Крім поняття множини є ще лише одне вихідне базове поняття - і все. Інші поняття в цій теорії похідні. Отож, друге базове поняття - це ПРИНАЛЕЖНІСТЬ (або

"відношення приналежності"). Тобто "елемент належить множині". Тут, тим більше,

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

1

та берізка "знаходиться" в цьому лісі,

Петренко "значиться" в студентах.

Будемо передбачати те, що ми завжди чітко знаємо, що належить даній множині, а що ні! Інше вважаємо неіснуючим узагалі!

Загальним позначенням множини служать пари фігурних дужок { },

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

множина містить кілька елементів, то ми просто записуємо всі її елементи. Наприклад,

якщо ми визначимо як множину усіх цілих чисел строго між 6 і 10, то це можна записати в такий спосіб:

={7, 8, 9}

іпрочитати як « — множина, що містить елементи 7, 8, 9».

Тут символ «=» використовується у визначеному змісті: дорівнює множині... Далі

буде використовуватися висловлення «чи рівне ». Тому запропонуємо процедуру

встановлення справедливості цього твердження. Іншими словами, множину можна

охарактеризувати визначеними властивостями, і, отже, множину можна визначити як

A = { : — ціле число і 6 < < 10} і прочитати як

« є множина усіх таких, що 6 < <10 ».

Множині належать тільки ті елементи, що є цілими числами, більшими 6 і меншими

10, тобто 7, 8 і 9, і, отже, ми маємо 7, 8, 9, як і раніше.

Множини часто розглядають як «неупорядковані сукупності елементів», хоча іноді корисно підкреслити, що, наприклад,

{7, 8, 9} = {8, 9, 7} = {9, 8, 7} = ...;

ми не робимо ніякого застереження про порядок, у якому розглядаються елементи,

тому було б неправильним допускати який-небудь визначений порядок.

Якщо ми хочемо сказати, що всі берізки, що знаходяться в даному лісі, належать і всьому лісовому багатству нашої країни, a всі студенти, що числяться в

2

університеті, числяться і студентами України, то для скор очення фраз використовуються терміни ПІДМНОЖИНА .

Для будь-якого заданого об'єкта можна визначити, чи належить він множині .

Зокрема, якщо число належить множині , то будемо говорити, що «воно є елементом множини». Так, наприклад, якщо 7 с елементом множини , то це твердження може бути записане в такий спосіб: «7 А».

Твердження «6 не є елементом А» будемо позначати як

«».

Дотепер нам зустрічалися символи{:},{,,,}, і , їхнє застосування здається досить простим, однак воно вимагає додатних навичок, які будуть проілюстровані на наступних прикладах. При застосуванні термінів НАЛЕЖИТЬ або ВКЛЮЧЕНА можуть бути очевидні синоніми. Але щоб у них не заплутатися і просто не переплутати з "належить", потрібно пам'ятати одну просту річ: "належить"

відноситься до випадку, коли "ЕЛЕМЕНТ належить МНОЖИНІ". a "включена" - коли

"МНОЖИНА включена в МНОЖИНУ".

Наприклад, множина студентів університету “включена” в множину студентів країни.

Тобто множина студентів університету “є підмножиною” множини студентів країни. У

відношення включення ( ряд цікавих властивостей. Вони можуть бути виявлені будь-

яким дослідником, якщо він "пограє" з цим відношенням. Наприклад, можна сказати,

що множина студентів групи К-001 включена в множину студентів університету,

оскільки така група в університеті мислиться. Те, що з групи відраховані усі студенти,

для математики ніякої ролі не грає. Оскільки, НЕМАЄ жодного студента, що числиться в цій групі, який би не числився в університеті. Такого роду міркування зовсім коректно можна застосувати до будь-якої пустої множини і зробити узагальнюючий висновок, що пуста множина є включена в будь-яку множину, у тому числі й у себе. Любий елемент, що належить множині, яка не містить ні одного елемента, належить і будь-якій іншій множині, яка не містить жодного елемента. Будь-

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

називаються УНІВЕРСУМОМ.

3

Візьмемо, наприклад, множину = {«Введення в теорію систем», «Основи структури даних», «Введення в теорію систем»}.

Це - множина назв двох книг з одним елементом, яка через неуважність записана двічі,

або ж це — множина трьох книг, дві з яких мають ту саму назву? Якщо вірно останнє,

то дві книги «Введення в теорію систем» варто розділити яким-небудь способом.

З даної інформації не можна з'ясувати правильну відповідь, тому в даному випадку варто бути обережним.

Способи задання множин. Множина може бути задана перерахуванням

(списком своїх елементів), породжуючою процедурою або описом характеристичних властивостей, якими повинні володіти ії елементи.

Списком можна задавати лише кінцеві множини. Завдання типу =1, 2, 3 ... — це не список, а умовна позначка, припустима лише тоді, коли вона свідомо не викликає різночитань. Як ми уже відзначали, список зазвичай заключають у фігурні дужки.

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

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

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

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

а породжуючею процедурою - числення, яке описується формулою π/2±k. Інший приклад — множина 2 =1,2,

4, 8, 16 ..., породжуюча процедура для якого визначається наступними двома правилами:

(Правила, які описані таким чином, називаються індуктивними або рекурсивними; про них мова буде іти далі.).

Третій приклад — множина Мπ , задана в такий спосіб. Нехай є процедура обчислення цифр розкладання числа у нескінченний десятковий дріб: π=3,1415926536... У міру

4

обчислення будемо утворювати з послідовно слідуючих цифр трьохрозрядні числа: 314, 159, 265 і т.д. Множину усіх таких чисел позначимо Мπ.

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

Задання множини описом властивостей її елементів, мабуть, найбільше доречне. У

прикладі, який розглянуто вище, задання множини можна інтерпретувати, як опис властивостей його елементів, що полягає в можливості представити їх у виді π/2±πk.

Множину 2 можна задати фразою « 2 — множина усіх цілих чисел, що є степєнями двійки». У випадку, коли властивість елементів М може бути описано

коротким виразом Р(х) (що означає «має властивість Р»), М задається за допомогою иозначення М—{х | Р(х)}, що читається так: «М — це множина х, які мають властивість Р».

Наприклад,

2 ={х | х=2k}, k N,

Мπ={х | х=π/2±πk}, де k N.

До опису властивостей природно висунути вимогу точності і недвозначності.

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

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

Наприклад, для 2 , тобто для властивості «бути степенем двійки»,

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

5

Пустою множиною називається множина, що не містить жодного елемента. Пуста множина позначається 0 . Наприклад, {х С | х2-х+1=0}= .

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

відмінники. Пусту множину будемо умовно відносити до кінцевих множин.

Розглянемо тепер питання про рівність множин. Дві множини називаються рівними,

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

Множини X і Y не рівні (Х≠Y), якщо або в множині X є елементи, що не належить Y,

або в множині Y є елементи, що не належать X Символ рівності множин має властивості:

X=X- рефлексивність;

Якщо Х=Y, to Y=X — симетричність;

Якщо Х=Y і Y=Z, тo X=Z — транзитивність.

3 визначення рівності множин випливає, що порядок елементів у множин не є суттєвим. Так, наприклад, множини {3, 4, 5, 6} і {4, 5, 6, 3} являють собою ту саму множину.

3 визначення множини випливає, що в ній не повинно бути невідзрізнених елементів.

Тому в множині не може бути однакових елементів. Запис {2, 2, 3, 5}, як ми вже знаємо, варто розглядати як некоректну і замінити її на {2, 3, 5}. Так, множина простих дільників числа 60 дорівнює {2, 3, 5}.

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

Мова множин — це універсальна мова математики. Будь-яке математичне твердження можна сформулювати як твердження про деяке співвідношення між множинами: про рівність двох множин, про непустоту деякої множини («існує безперервна функція,

яка ніде не диференціюється»), про неприналежності елемента множини («за

6

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

Поняття підмножини

Множина X є підмножиною множини Y, якщо будь-який елемент множини X

належить і множині Y. Нехай Y — множина студентів групи, a X — множина відмінників цієї ж групи. Так як кожен відмінник групи є в той же час студентом цієї групи, то множина Х є підмножиною множини Y.

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

— символ, який називають квантором і означаючий «будь-який», «який би не був», «для всіх»;

- символ наслідку (імплікації), що означає «спричиняє».

Визначення підмножини, що може бути сформульоване у вигляді: для будь-якого х твердження «jc належить X» спричиняє твердження «х належить 7» запишеться так:

x[x X x Y]

Більш коротким записом виразу «X є підмножиною У» буде запис

X Y

що читається як «Y містить X». Використовуваний тут символ означає включення.

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

X Y.

Зв'язок між символами і дається виразом

X У Х Y X Y.

Туг використано символ , що означає еквівалентність (у змісті «те ж саме, що»).

Відзначимо деякі властивості підмножини, що випливають з її визначення:

X Y( рефлективність);

[X Y i Y Z] X Z (транзитивність).

7

Трохи важче бачити, що для будь-якої множини М

M

Дійсно, пуста множина не містить елементів. Отже, додаючи до М пусту множину,

ми фактично нічого не додаємо. Тому завжди можна вважати, що будь-яка множина М містить у собі пусту множину як підмножину.

Верхня і нижня границі множини Маючи справу з множиною дійсних чисел, можна порівнювати елементи цієї множини

по їхньому значенню і, зокрема, знаходити найбільший і найменший елемент множини. Для кінцевих множин, заданих перерахуванням, ця задача не представляє труднощів. Так, для множини Т={4, 3, 5, 6} маємо max Т=6, mi Т=3. Однак якщо множина задана описовим способом, наприклад, зазначено лише правило обчислення числових значень її елементів, то задача визначення найбільшого і найменшого елементів стає досить важкою.

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

Нехай S— множина дійсних чисел. Верхньої і нижньою границею S є число С таке, що для будь-якого x S має місце х С. Чисел, які можуть розглядатися в якості верхньої границі множини, може бути нескінченно багато, а може і не бути взагалі. Так, в

множині m<S< любе С М є верхньою границею. Множина усіх цілих чисел не має

верхньої границі.

Точною верхньою границею або супремумом множини S, позначаємою sup S,

називається верхня границя, що не перевершує будь-яку іншу верхню границю. У

приведеному вище прикладі sup S= . Множина може мати тільки одну точну верхню границю, тому що якщо С1 і С2 — дві такі границі, то С1 С2 і С2 С1, і отже,

C1=C2.

Нижньою границею множини S є число с, таке, що для будь-якого х S має місце х с.

Точною нижньою границею або інфінумом множини S, позначаємою i f S,

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

що приводиться, i f S=m.

8

Теорема (теорема про нижню і верхню границі підмножини). Якщо B А, то i f В i f А ; sup В sup А.

Доведення. Позначимо через b' елемент множини В, що має найменше значення, тобто b' В і b’=i f В. Але В А, тобто b' А. Нехай а' - елемент множини А, що має найменше значення, тобто а' А і a’= i f А. При цьому якщо b'=а', то b'= i f А, якщо b'≠а', то Ь'>а’=i f А. Таким чином, b' i fA або

i f В i f А. Друга частина теореми доводиться аналогічно.

1.2. Операції над множинами.

Існують три основні операції над множинами:

ОБ'ЄДНАННЯ, ПЕРЕТИН і РІЗНИЦЯ.

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

Принципова відмінність об'єднання множин від шкільного додавання не тільки в тім, що студенти - це не числа і ми їх не перераховуємо (!), але й

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

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

Ясно, що пересічення цих множин дасть двох студентів, які одночасно і відмінники, і

спортсмени. Коли в нас з’являються в руках об'єкти, а ми можемо брати будь-які об'єкти, і операції - а ми основну трійку цих операцій теж визначили, то будемо говорити про АЛГЕБРУ.

Щоб краще розібратися в діях над множинами, необхідно згадати закони, що існують в елементарній алгебрі. Алгебра множин дуже відрізняється від елементарної, хоча є деякі аналогії. В алгебрі множин є ті ж назви законів: КОМУТАТИВНИЙ,

АСОЦІАТИВНИЙ і ДИСТРИБУТИВНИЙ (перемістительний, сполучний і розподільний). Перші два схожі з елементарною алгеброю. А от дистрибутивний закон має й аналог у елементарній алгебрі (виражаючись "по-шкільному" добуток суми є

9

сума добутків), але має й відмінну версію. У теорії множин пересічення з об'єднанням дорівнює об'єднаню пересічень (!) об'єднання з пересіченням дорівнює пересіченню об'єднань. Друге не має аналогії в елементарній алгебрі: "Сума з добутком не дорівнює добуткові сум".

Проілюструємо сказане спочатку словесно:

Комутативний закон: об'єднання (пересічення) відмінників і спортсменів дорівнює об'єднанню (пересіченню) спортсменів і відмінників.

Асоціативний закон: від зміни порядку об'єднання (пересічення) спортсменів,

відмінників і дівчат результат не міняється.

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

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

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

Є ще закон, який варто віднести до найважливіших законів (властивостям). Це закон ІДЕМПОТЕНТНОСТІ, який звучить так (на прикладі спортсменів): об'єднання

(пересічення) множини спортсменів з множиною спортсменів дає множину спортсменів.

Приведемо ще один дуже важливий закон - ЗАКОН Де Моргана: доповнення об'єднання відмінників зі спортсменами дорівнює пересіченню доповнення множини спортсменів з доповненням множини відмінників. І другий варіант.

Доповнення пересічення відмінників зі спортсменами дорівнює об'єднанню доповнення множині спортсменів з доповненням множини відмінників. За універсум

(для доповнення) можна взяти множину студентів групи (або університету, або світу -

ролі не грає).

Дуже простий закон ПОДВІЙНОГО ДОПОВНЕННЯ.

10