додати матеріал


Основні поняття алгебри множин

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

Основні поняття алгебри множин

Алгебра множин лежить в основі багатьох розділів сучасної математики. Для неї практично неможливо встановити точну дату відкриття і назвати ім'я першовідкривача. Алгебра множин поступово розвивалася на тлі численних спроб знайти строгий математичний підставу для Арістотелевої логіки. Деякі передумови цієї алгебри містяться в працях Лейбніца. У розробку основ цієї алгебри внесли значний вклад багато відомих логіки і математики (Ж. Д. Жергонн, А. де Морган, Дж. Венн та ін.) Але особлива заслуга в її розвитку і поширенні належить Леонарду Ейлера.

У 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) можна використовувати кілька варіантів Жергоннових відносин, і при збільшенні кількості вихідних суджень число можливих варіантів аналізу зростає в статечної залежності. Якщо допустимо, розглядаємо складне міркування, що містить багато суджень, то повинні для кожного судження переглянути всі відповідні йому варіанти Жергоннових відносин. Проте роботи Ейлера, Жергонна, Венна і багатьох інших стали своєрідною "затравкою" для створення алгебри множин.

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

  1. носій - деяка сукупність об'єктів (наприклад, числа, геометричні фігури, слова, числа й т.д.);

  2. сукупність відносин (наприклад, більше, менше, рівно і т.д);

  3. сукупність операцій (наприклад, додавання, множення, те що і т. д).

Зауважимо, що смислова різниця між ставленням і операцією полягає в наступному: якщо задано деяке відношення між об'єктами, то про нього можна тільки сказати, істинно воно для даних об'єктів чи ні (наприклад, "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}.

Приймемо ці співвідношення в якості вихідних даних і доведемо для цього загального представлення даної системи з двох множин один із законів де Моргана = È . Тоді отримаємо:

  1. X Ç Y = {b};

  2. = {A, c, d};

  3. = {C, d};

  4. = {A, d};

  5. È = {A, c, d};

  6. порівнюючи 2 і 5 укладаємо, що = È , Що й потрібно було довести.

Закон транзитивності (12 a) інтуїтивно зрозумілий. Розглянемо обгрунтування закону контрапозиции (12 b). Оскільки він дійсний тільки в тому випадку, коли X Í Y, то доведеться трохи змінити нашу вихідну систему. Для цього приймемо, що безліч, представлене в системі елементом a, так само порожньому безлічі, і тому його можна виключити з універсуму. Тоді отримаємо такі вихідні дані:

U = {b, c, d}; X = {b}; Y = {b, c}.

Ясно, що в цій системі співвідношення X Í Y дотримується. Приступимо до доказу.

  1. = {C, d};

  2. = {D};

  3. порівнюючи і , Переконаємося, що Í , Що й потрібно було довести.

Література

  1. Алгебра та початок аналізу - Вища школа - М. 2003

  2. Алгебра - під ред. Бутинець К.К. - К. - 2000 р.

Додати в блог або на сайт

Цей текст може містити помилки.

Математика | Контрольна робота
70.5кб. | скачати


Схожі роботи:
Розвиток функціональної лінії в курсі алгебри 7-9 класів на прикладі підручників з алгебри під ред
Розвиток функціональної лінії в курсі алгебри 9 липня класів на прикладі підручників з алгебри під ред
Основні аксіоми і тотожності алгебри логіки Аналітична форма подання булевих функцій
Завдання лінійної алгебри Поняття матриці Види матриць Операції з матрицями Рішення задач на перетворення
Основні теорії праворозуміння Основні причини і закономірності появи права Поняття соціального
Побудова скінченних множин
Про категорії множин
Деякі способи розбиття множин
Розмірність кінцевих впорядкованих множин
© Усі права захищені
написати до нас
Рейтинг@Mail.ru