Основні поняття алгебри множин
Алгебра множин лежить в основі багатьох розділів сучасної математики. Для неї практично неможливо встановити точну дату відкриття і назвати ім'я першовідкривача. Алгебра множин поступово розвивалася на тлі численних спроб знайти строгий математичний підставу для Арістотелевої логіки. Деякі передумови цієї алгебри містяться в працях Лейбніца. У розробку основ цієї алгебри внесли значний вклад багато відомих логіки і математики (Ж. Д. Жергонн, А. де Морган, Дж. Венн та ін.) Але особлива заслуга в її розвитку і поширенні належить Леонарду Ейлера.
У 1736 р. в "Листах до німецької принцесі про різних фізичних і філософські матерії" Л. Ейлер в популярній формі виклав своє розуміння Арістотелевой силлогистики. При цьому він використовував наочні схеми, які згодом отримали назву "круги Ейлера". Надалі круги Ейлера стали використовувати не тільки в навчальних курсах за логікою, але також і при викладі азів багатьох основних розділів сучасної математики, в яких використовується алгебра множин. Тут скористаємося цими наочними відображеннями, що дозволяють досить швидко опанувати абстрактними поняттями алгебри множин.
Ідеї Ейлера були розвинені в роботах французького астронома і математика Ж. Д. Жергонна. Жергонну вдалося в опублікованій в 1817 р. роботі "Основи раціональної діалектики" представити всі класи суджень, виділених Аристотелем, за допомогою співвідношень між множинами. Ці співвідношення отримали в математиці і логіці назву "жергоннових відносин". Розглянемо їх більш докладно.
В основі силлогистики лежать прості судження, представлені чотирма типами: A - общеутвердітельное (все X є Y); E - общеотріцательное (усі X не є Y); I - частноутвердітельное (деякі X є Y); O - частноотріцательное (деякі X не є Y). Відзначимо, що в працях Аристотеля сенс суджень відрізняється від загальноприйнятого - цей сенс разом з позначеннями утвердився в логіці після робіт відомого схоласта Петра Іспанського. Сам Аристотель не вживав у судженнях двозначну зв'язку "є" і формулював судження наступним чином:
A: Y притаманне всім X
E: Y не властиво всім X
I: Y притаманне деяким X
O: Y не властиво деяким X
Терміни X і Y можна представити як деякі сукупності (множини, класи) у вигляді кіл Ейлера. Жергонн виділив 5 можливих співвідношень між ними (рис. 1).
Рис. 1
Кожен тип Жергоннових відносин має власну назву:
G 1 - збіг або рівнозначність;
G 2 - лівосторонній включення;
G 3 - приватне збіг;
G 4 - правосторонній включення;
G 5 - несумісність.
Жергонн показав, що кожен тип арістотелівського судження відповідає деяким типам цих відносин, зокрема:
типу A відповідає G 1 або G 2;
типу E відповідає G 5;
типу I: відповідає G 1 або G 2 або G 3 або G 4;
типу O: відповідає G 3 або G 4 або G 5.
Наприклад, судження типу I означає, що деяка частина непорожній безлічі або класу X міститься в Y. Подивившись на малюнок, неважко переконатися, що цій умові задовольняють всі типи Жергоннових відносин крім G 5. У логіці слово "деякі" використовується в широкому сенсі: "хоча б один, але не виключено, що і все". Жергоннови відносини часто використовувалися для суворого обгрунтування не тільки правил виводу для простого категоричного силогізму, в якому як посилок використовуються тільки два судження, але і для більш складних умовиводів, коли в якості посилок допускається довільне число суджень. Вершиною аналізу такого роду можна вважати роботи англійського логіка і філософа Дж. Венна (1834-1923).
Однак застосування жергоннових відносин в логіці пов'язано з рядом труднощів. Головною з них є те, що практично для всіх типів суджень (за винятком типу E) можна використовувати кілька варіантів Жергоннових відносин, і при збільшенні кількості вихідних суджень число можливих варіантів аналізу зростає в статечної залежності. Якщо допустимо, розглядаємо складне міркування, що містить багато суджень, то повинні для кожного судження переглянути всі відповідні йому варіанти Жергоннових відносин. Проте роботи Ейлера, Жергонна, Венна і багатьох інших стали своєрідною "затравкою" для створення алгебри множин.
З точки зору сучасної математики алгебра множин відноситься до класу алгебраїчних систем, тобто структур, в яких є (дані):
носій - деяка сукупність об'єктів (наприклад, числа, геометричні фігури, слова, числа й т.д.);
сукупність відносин (наприклад, більше, менше, рівно і т.д);
сукупність операцій (наприклад, додавання, множення, те що і т. д).
Зауважимо, що смислова різниця між ставленням і операцією полягає в наступному: якщо задано деяке відношення між об'єктами, то про нього можна тільки сказати, істинно воно для даних об'єктів чи ні (наприклад, "2> 3" є помилковим ставленням), в той час як в результаті деякої операції з об'єктами виходить деякий новий об'єкт (наприклад, "2 +3 = 5").
В алгебрі множин носієм є деяка сукупність множин. Основними поняттями алгебри множин вважаються поняття безліч і елемент. Співвідношення між ними називається ставленням приналежності і позначається знаком "Î". Запис
b Î A
перекладається з символічного мови як "b є елементом множини A" або "елемент b належить безлічі A". Якщо відомі всі елементи множини (наприклад, a, b і c), то загальноприйнятою є такий запис безлічі:
A = {a, b, c}.
У цьому випадку елементи безлічі прийнято укладати в фігурні дужки. Крім того, при перерахуванні елементів порядок неістотний, тобто A = {a, b, c} = {c, b, a} = {a, c, b} і т.д.
Безлічі можуть бути задані двома способами: за допомогою формулювання характерних ознак (наприклад, безліч K цифр, що позначають парні числа) або за допомогою перерахування елементів (наприклад, K = {0, 2, 4, 6, 8})
У сучасній математиці поки що немає чіткого визначення ставлення приналежності. В алгебрі множин цієї невизначеності можна уникнути, якщо вважати, що це ставлення пов'язує два різних типи об'єктів ("елемент" Î "безліч"), але ні в якому разі не повинно бути зв'язку типу "безліч" Î "безліч".
Між множинами встановлюється інше начебто схоже, але в той же час принципово відрізняється ставлення - включення, структурні властивості якого в сучасній математиці визначені досить чітко і однозначно. Розглянемо його детальніше. Допускаються два відмінних варіанти цього відношення:
"Ì" - строго включено;
"Í" - включено або дорівнює.
Запис A Ì B означає, що множина A включено в безліч B, тобто всі елементи множини A є одночасно елементами множини B, але при цьому неможливо рівність цих множин. Запис A Í B означає, що множина A включено в безліч B, але при цьому не виключається, що вони можуть бути рівними. Зображення відношення включення за допомогою кіл Ейлера показано на малюнку 2. В даному випадку не обов'язково використовувати правильні кола. Для зображення безлічі може підійти будь-яка замкнута фігура.
Рис. 2
Якщо безлічі задані за допомогою перерахування елементів, то відношення включення (або невключення) одного безлічі в інше безліч можна легко встановити, якщо порівняти елементи цих множин. Наприклад, якщо задані безлічі
P = {a, b, c, d, e}; Q = {b, d, a}; R = {a, c, f},
то можна легко встановити, що Q Ì P, але в той же час відношення R Ì P для цих множин невірно, так як елемент f з безлічі R не є елементом множини P.
Порядок перерахування елементів для множин неістотний. Наприклад, множини {b, d, a}; {a, b, d}; {d, a, b} - це по суті одне і те ж кількість. Якщо ж порядок перерахування множин є істотним, то в цьому випадку маємо справу не з множинами, а з послідовностями або з впорядкованими множинами (деякі відомості про них наведені нижче). Математичні властивості послідовностей істотно відрізняються від математичних властивостей множин.
Зауважимо, що несхожість відносин належності та включення можна ілюструвати таким прикладом. Припустимо, a Î P, з чого випливає, що a є елементом, а P - множиною. Чи можна в цьому випадку записати a Í P? Виявляється, не можна, тому що ставлення включення застосовується лише для двох множин. Правильною в цьому випадку є запис {a} Í P, в якій зліва записаний не елемент, а одноелементні безліч.
Розглянемо ще одне відношення між множинами - відношення рівності. Безлічі рівні, якщо у них одні й ті ж елементи. Для доказу рівності двох множин, особливо в тих випадках, коли у них велике чи нескінченне число елементів, використовується наступне визначення.
Визначення 1. Безлічі A і B рівні, якщо справедливо як A Í B, так і B Í A.
Якщо безлічі пов'язані відносинами A Ì B або A Í B, то в цьому випадку множина A називають підмножиною множини B. Серед усіх можливих підмножин довільного безлічі A обов'язково міститься також і саме безліч A. Іншими словами, для будь-якого безлічі A завжди справедливо A Í A.
В алгебрі множин особливо виділяється і часто використовується безліч, яке називається "порожнє безліч" (позначається "Æ"). Інтуїтивно пусте безліч означає безліч, не містить жодних елементів. Але це інтуїтивне визначення не розкриває повністю його суті і ролі в алгебрі множин. Більшою мірою його суть розкривається в наступному реченні, яке можна віднести до однієї з аксіом алгебри множин:
Пусте безліч включено в будь безліч.
Для пояснення сенсу цієї пропозиції розглянемо наступний приклад. Нехай A - безліч крокодилів. Ясно, що це безліч може мати якісь підмножини. Наприклад, безліч C крокодилів, які живуть в зоопарках. Тоді відношення між A і C можна записати як C Ì A. Розглянемо ще одне підмножина безлічі A: підмножина крокодилів, які розмовляють російською мовою. Ясно, що це пусте безліч і, тим не менше, можемо його вважати підмножиною множини A. У математичних міркуваннях, коли нам треба довести, що дане безліч X не існує (або існує), зводимо доказ існування до доведення відносини X = Æ (або X ¹ Æ). Часто такий метод дозволяє набагато спростити доказ.
Якщо безліч задано перерахуванням елементів, то часто інтерес представляє сукупність всіх підмножин цієї множини. Наприклад, для безлічі A = {a, b, c} така сукупність складається з восьми підмножин:
Æ, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}.
Саме безліч А є підмножиною самого себе. Відомо також просте співвідношення, що дозволяє відразу ж дізнатися загальне число всіх можливих підмножин множини, що містить рівно N елементів. Виявляється, що для будь-якого N таке число дорівнює 2 N. Наприклад, для нашого безлічі A = {a, b, c} число всіх можливих підмножин дорівнює 2 3.
Зазвичай у багатьох міркуваннях використовується певний набір множин. Такий набір називається в алгебрі множин системою множин. У систему множин при цьому крім порожнього безлічі включається і універсум, тобто безліч, для якого все безлічі системи множин є підмножинами. Іншими словами, системою множин є деяка сукупність підмножин деякої множини, прийнятого за універсум. Наприклад, для множин планет, комет, зірок і т.д. в якості універсуму можна прийняти безліч астрономічних об'єктів.
Для універсуму немає загальноприйнятих позначень. Далі будемо позначати його символом U.
Перейдемо до операцій. Почнемо з операції доповнення, яка може бути визначена тільки тоді, коли для системи множин заданий універсум.
Визначення 2. Доповненням безлічі A називається безліч , Що містить всі елементи універсуму, які не є елементами множини A.
У логіці додатком безлічі відповідає зв'язка "не". Наприклад "не червоний" - будь-який можливий колір крім червоного. Зазвичай додаток безлічі позначається за допомогою риси, розташованої над символьним позначенням цієї множини. Наприклад, є позначенням додатки безлічі
.
Приклад 1. Нехай U = {a, b, c, d} і P = {a, c}. Тоді = {B, d}.
Визначимо ще дві основні операції - перетин і об'єднання множин.
Визначення 3. Перетином множин A і B називається множина C, всі елементи якого є одночасно елементами множин A і B.
Операція перетину множин позначається символом "Ç". Символічно визначення 3 можна записати як формулу
C = A Ç B.
Наприклад, перетином безлічі всіх студентів даного вузу і безлічі всіх учасників КВН, є безліч студентів даного вузу, що беруть участь у КВК. Інший приклад: перетином безлічі всіх чисел, що діляться на 2, і безлічі всіх чисел, що діляться на 3, є безліч всіх чисел, що діляться на 6.
У логіці операції перетину відповідає логічна зв'язка "І" (позначається як Ù або &). Якщо мова йде про об'єкти з властивостями P або Q, то логічна формула P Ù Q означає, що мова йде тільки про об'єкти, яким притаманні обидва цих властивості. Якщо, припустимо, властивостям P і Q відповідають деякі безлічі S P і S Q, то перетин цих множин S P Ç S Q, буде складатися з елементів, кожному з яких одночасно властиві властивості P і Q
Приклад 2. Нехай A = {a, b, c, d} і P = {a, c, f}. Тоді A Ç P = {a, c}.
Визначення 4. Об'єднанням множин A і B називається множина C, всі елементи якого є елементами принаймні одного з цих множин.
Операція об'єднання множин позначається символом "È". Символічно визначення 4 можна записати як формулу
C = A È B
У логіці операції об'єднання відповідає логічна зв'язка "АБО" (позначається "Ú"). Якщо мова йде про об'єкти з властивостями P або Q, то логічна формула P Ú Q означає, що мова йде тільки про об'єкти, яким властиве хоча б одне з цих властивостей. При цьому допускається, що об'єкти, яким притаманні обидва цих властивості, також належать до цього класу об'єктів.
Приклад 3. Нехай A = {a, b, c, d} і P = {a, c, f}. Тоді A È P = {a, b, c, d, f}.
Зверніть увагу, що в прикладі 3 елементи a і c, які містяться в кожному з множин A і B, в об'єднанні C не подвоюються, а містяться як одноразові. У математиці і її додатках іноді використовують безлічі з кратними елементами (вони називаються мультимножинами), але нам такі множини не знадобляться. У таких множинах порушуються деяких законів звичайної алгебри множин.
Операції доповнення, перетину та об'єднання є основними операціями алгебри множин.
Визначення 5. Різницею множин A і B називається множина C = A \ B, яке містить лише ті елементи множини A, які не є одночасно елементами безлічі B.
Приклад 4. Нехай A = {a, b, c, d} і B = {a, c, f}. Тоді A \ B = {b, d}.
Важливо відзначити, що різниця множин є похідною операцією. Це означає, що її можна виразити за допомогою інших основних операцій - для різниці множин справедливо наступне співвідношення:
A \ B = A Ç .
Якщо в прикладі 4 задати універсум, наприклад, U = {a, b, c, d, e, f}, то неважко переконатися в справедливості цієї рівності:
= {B, d, e}; тоді A \ B = A Ç
= {B, d}.
У той же час операцію доповнення можна виразити за допомогою операції різниці: = U \ A. У деяких версіях алгебри множин операція різниці множин представлена як основна операція, а операція доповнення - як похідна операція. Однак основні співвідношення (або закони) алгебри множин при цьому залишаються незмінними.
На малюнку 3 відповідні операції над множинами зображені за допомогою "кіл Ейлера". Сірим кольором показані результати операцій.
Рис. 3
Тут хотілося б звернути увагу на наступну важливу обставину. Для множин A і B, у яких немає спільних елементів, справедливі наступні співвідношення:
A Ç B = Æ; A Í ; B Í
.
Ситуацію, що відповідає цим співвідношенням, можна наочно відобразити за допомогою діаграми Ейлера (рис. 4).
Рис. 4
Тепер у нас цілком достатньо понять для того, щоб відобразити у вигляді математичного формулювання задані судження. Наприклад, судження "Усі члени палати лордів носять титул пера" то розчленовується на суб'єкт "члени палати лордів" (A) і предикат "носять титул пера" (B). Тоді математичною формулою даного судження буде
A Í B.
Це означає, що всі члени палати лордів включені в безліч тих, хто носить титул пера. Більш складне судження, наприклад, "Усі члени палати лордів носять титул пера і знаходяться в здоровому глузді" можна виразити, використовуючи два предиката: "носять титул пера" (B) і "перебувають у здоровому глузді" (С). Тоді отримаємо таку математичну формулювання:
A Í (B Ç C). (1)
У випадку, коли в судженні є предикати з запереченнями, використовуємо в математичного запису операцію доповнення. Наприклад, судження "Усі члени палати лордів носять титул пера і не беруть участі у перегонах на мулах", можна записати як
A Í (B Ç ), (2)
де D - предикат "беруть участь у скачках на мулах".
Якщо використовувати діаграми Ейлера, то отримаємо наочне зображення формул (1) і (2) (малюнки 5 і 6).
Рис. 5
Рис. 6
Кількісні співвідношення в діаграмах Ейлера (тобто в даному випадку - площі фігур) не беруться до уваги. Серед наших знань чимало таких, коли не знаємо, чому одно число елементів множини, але це не заважає нам знати про те, що деякі з таких множин суворо включені в деякі інші множини, або що деякі з таких множин точно не містять загальних елементів з деякими іншими множинами. Кількісний аналіз множин в багатьох випадках є складовою частиною наших знань.
В математичну форму суджень можна перевести багато пропозицій природної мови.
Закони алгебри множин - це по суті теореми, які виводяться з основних визначень і аксіом. Часто наводяться 26 або 28 законів алгебри множин. Наведемо без доведення лише деякі з них, необхідні для ясного розуміння подальшого. Нехай A, B, C - деякі довільні множини в універсумі U. Тоді законами алгебри множин є наступні співвідношення між ними.
1. = A.
Приклад 5. Нехай U = {a, b, c, d} і P = {a, c}. Тоді = {B, d} і
= {A, c} = P.
В алгебрі множин це співвідношення (подвійне доповнення) носить назву закон інволюції. У логіці цей закон відомий під назвою закон заперечення заперечення (або закон подвійного заперечення): не (не-A) - те ж саме, що і A.
2. A Ç = Æ (безліч і його доповнення не мають спільних елементів)
У логіці цього закону відповідає закон непротиріччя (затвердження та його повне заперечення логічно несумісні).
3. A È = U.
У логіці цього закону відповідає закон виключеного третього (суміщення будь-якого затвердження та його повного заперечення не допускає присутності будь-якої третьої проміжного варіанту).
Наступні співвідношення характеризують більш детально властивості порожнього множини і універсуму:
4. = U;
5. = Æ
6. A ÇÆ = Æ;
7. A ÈÆ = A;
8. A Ç U = A;
9. A È U = U.
Наступні закони алгебри множин зв'язують один з одним відносини включення і рівності:
10. З A Í B слід:
10 a. A Ç B = A;
10 b. A È B = B;
10 c. È B = U;
10 d. A Ç = Æ.
Співвідношення 10d можна виразити також за допомогою операції різниці множин:
10e. З A Í B слід A \ B = Æ.
Наступні закони в логіці і алгебрі множин називаються законами де Моргана:
11a. =
È
;
11b =
Ç
.
І, нарешті, наведемо два закони, які визначають основні властивості відношення включення. Їх використовують в подальшому в правилах логічного висновку.
12a. Якщо A Í B і B Í C, то A Í C (закон транзитивності включення);
12b. Якщо A Í B, то справедливо також і Í
(Закон контрапозиции).
В математичній літературі наводяться різні способи обгрунтування цих законів. Багато з них досить складні для розуміння. Тут розглянемо відносно простий спосіб, який називається комбінаторним.
Нехай нам необхідно вивести деякі закони для двох множин X та Y. Розглянемо діаграму Ейлера (рисунок 7), на якій зображені ці множини і осяжний їх універсум (U).
Рис. 7
Виділимо на діаграмі ділянки a, b, c і d, які не мають внутрішніх кордонів, тобто виконаємо розбиття нашого універсуму на непересічні один з одним множини. Таке розбиття дозволяє нам представити ці множини як елементи, з яких складаються універсум U і безлічі X і Y. Тоді для них справедливі співвідношення:
U = {a, b, c, d}; X = {a, b}; Y = {b, c}.
Приймемо ці співвідношення в якості вихідних даних і доведемо для цього загального представлення даної системи з двох множин один із законів де Моргана =
È
. Тоді отримаємо:
X Ç Y = {b};
= {A, c, d};
= {C, d};
= {A, d};
порівнюючи 2 і 5 укладаємо, що
Закон транзитивності (12 a) інтуїтивно зрозумілий. Розглянемо обгрунтування закону контрапозиции (12 b). Оскільки він дійсний тільки в тому випадку, коли X Í Y, то доведеться трохи змінити нашу вихідну систему. Для цього приймемо, що безліч, представлене в системі елементом a, так само порожньому безлічі, і тому його можна виключити з універсуму. Тоді отримаємо такі вихідні дані:
U = {b, c, d}; X = {b}; Y = {b, c}.
Ясно, що в цій системі співвідношення X Í Y дотримується. Приступимо до доказу.
порівнюючи
Література
Алгебра та початок аналізу - Вища школа - М. 2003
Алгебра - під ред. Бутинець К.К. - К. - 2000 р.