Головна Головна -> Підручники -> Підручник Вступ до сучасної логіки (Конспект лекцій) скачати онлайн-> § 3. Теорія множин

§ 3. Теорія множин


Необхідна для проектування кіл алгебра множин багато в чому відмінна від традиційних алгебраїчних систем. Річ у тім, що ряд законів звичайної алгебри втрачає силу під час переходу до алгебри множин. У зв’язку з цим операції над множинами часто називають не сумою чи добутком множин, а об’єднанням і перетином. Позначають ці операції спеціальними символами u та п, що не підказують аналогій з операціями над числами.
Алгебраїчні системи, подібні до алгебри множин, називають алгебрами Буля (булевими алгебрами), іменем математика, який уперше їх розглянув.
Джордж Буль (1815- 1864) – автор всесвітньо відомих праць «Математичний аналіз логіки» (1847) та «Вивчення законів мислення, на яких ґрунтуються математичні теорії логіки і ймовірностей» (1854).
З історії булевої алгебри логіки довідуємося, що з розвитком алгебри виявилась очевидною аналогія між правилами формальної логіки й правилами алгебри. Ця аналогія базується на тій спільній для обох наук властивості, що полягає в орієнтації логічного й алгебраїчного аналізів на невизначені об’єкти, від природи яких можна абстрагуватися.
Основна теоретична ідея Буля полягає в тому, що в логіці треба мати справу не з конкретними значеннями висловлень, а з абстрактними множинами об’єктів неви-значеної природи як «смисловим» змістом математичних або логічних виразів. Внаслідок цього форма висловлень втрачає свою специфіку, зумовлену, наприклад, використанням виразів природної мови, і набуває алгебраїчного вигляду.
Поняття множини використовувалося в логіці здавна, хоча й не було зроблено точного його аналізу. Обсяги термінів (понять у традиційній логіці) — це множина предметів, позначених цими термінами, що підпадають під дані поняття. Відношення між обсягами термінів — це відношення між множинами.
Відомо, що логіки використовують такі базисні для своєї науки поняття, як «усі», «жоден» тощо. За допомогою слова «усі» побудуємо висловлення: «Усі х, для яких визначена функція/(х) (наприклад, «хуміє фати в покер»), утворюють множину». У даному разі стверджується, що існує область визначення так званої пропозиційної функції (функції висловлення) f. Вчені вважають, що саме так математичне поняття множини входить у логіку.
Виникнення й розвиток теорії множин пов’язані з дослідженням нескінченних множин, засновником яких був видатний німецький математик Георг Кантор (1845— 1918). Перші праці вченого зустріли опір з боку багатьох сучасних йому математиків, оскільки вважалося, що «нескінченність» ніколи не увійде до складу математичних понять. Проте канторова теорія множин розвивалася й невдовзі стала основною математичною дисципліною, яка широко застосовується в різних розділах математики.
Зазначимо, що виникненню й розвиткові канторової теорії множин передувала розробка Булем деяких теоре-тико-множинних понять.
За допомогою булевої алгебри здійснюється опис операцій над множинами висловлень. Зіставлення операцій Буля над висловленнями з операціями Кантора над множинами показує: операції над висловленнями й множинами мають спільні властивості, до яких належать к о м у-тативність (переміщення), асоціативність (сполучення), дистрибутивність (розподілення). При цьому деякі властивості таких операцій не схожі на властивості операцій над числами. До речі, Буль першим висловив думку стосовно того, що операції з числами або величинами не характеризують сутності математики. Він вважав, що в математиці можливі такі розділи, які не мають справи з числами й величинами, наприклад теорія множин, що розроблялася як своєрідна алгебра, де змінні не вказують ні на числа, ні на величини. Проте такі цікаві ідеї не були до кінця реалізовані їхнім автором, оскільки Буль розробляв свою алгебру логіки у формі, традиційній для алгебри того часу, а не у формі продуманої дедуктивної системи.
Сучасні математики поділяють погляди Буля. Помилково вважається, зазначають вони, що обчислення є головним, чим займається математика. Насправді ж у чистій ‘математиці обчислення трапляються дуже рідко. Зазвичай вони здійснюються тоді, коли власне математичну роботу закінчено й ідеться лише про те, щоб, керуючися відомими правилами, виконати певний обсяг суто механічної роботи.
Отже, елементами булевої алгебри множин є не числа, а певні об’єкти, природа яких ігнорується. Істотним при цьому є лише те, що всі елементи алгебри, які називаються множинами, являють собою частини однієї і тієї самої множини. Цю вихідну множину називають універсальною й часто позначають великою латинською літерою U (перша літера латинського слова universalis — загальний), що читається як «всі», «всякий», «будь-який», «ніякий».
Різні науки мають власні універсальні множини предметів, що вивчаються. Так, у арифметиці натуральних чисел універсальною множиною є множина всіх натуральних чисел.
Оскільки множина може містити будь-яку кількість членів, то вона може складатися й з одного елемента. Така множина називається одиничною.
Визначаючи множину, неможливо знати наперед, чи містить вона хоча б один елемент. Тому корисно розглядати й множини, що не мають жодного елемента, тобто порожні множини. Зауважимо, що множина, кожному членові якої не притаманна певна властивість, є множиною, де немає членів, яким притаманна дана властивість. Така множина називається нульовою, або порожньою, і позначається символом 0 (або «0»). Ця множина може містити такі неіснуючі об’єкти, як «круглі квадрати», «жонаті парубки», «зелені ідеї» тощо.
Існують різні способи вилучення підмножин з універсальної множини, число елементів якої може бути як скінченним, так і нескінченним. Одним із таких способів є повний перелік членів множини. Можна також виділяти певну множину як сукупність усіх об’єктів, що відповідають якійсь певній вимозі.
Множину вважають визначеною, якщо можна сказати стосовно будь-якого предмета, належить чи не належить він до цієї множини.
Зазвичай множини позначають великими літерами латинського алфавіту (А, В, С, D, …), а їхні члени — малими літерами того самого алфавіту (а, Ь, с, сі, …).
Над елементами булевої алгебри можна виконувати певні операції. Результатом кожної такої операції, що виконується над множинами (елементами алгебри), буде також множина (елемент алгебри). Ця обставина визначає назву булевої алгебри — алгебра множин.
утворюють множину». У даному разі стверджується, що існує область визначення так званої пропозиційної функції (функції висловлення) f. Вчені вважають, що саме так математичне поняття множини входить у логіку.
Виникнення й розвиток теорії множин пов’язані з дослідженням нескінченних множин, засновником яких був видатний німецький математик Георг Кантор (1845— 1918). Перші праці вченого зустріли опір з боку багатьох сучасних йому математиків, оскільки вважалося, що «нескінченність» ніколи не увійде до складу математичних понять. Проте канторова теорія множин розвивалася й невдовзі стала основною математичною дисципліною, яка широко застосовується в різних розділах математики.
Зазначимо, що виникненню й розвиткові канторової теорії множин передувала розробка Булем деяких теоре-тико-множинних понять.
За допомогою булевої алгебри здійснюється опис операцій над множинами висловлень. Зіставлення операцій Буля над висловленнями з операціями Кантора над множинами показує: операції над висловленнями й множинами мають спільні властивості, до яких належать к о м у-тативність (переміщення), асоціативність (сполучення), дистрибутивність (розподілення). При цьому деякі властивості таких операцій не схожі на властивості операцій над числами. До речі, Буль першим висловив думку стосовно того, що операції з числами або величинами не характеризують сутності математики. Він вважав, що в математиці можливі такі розділи, які не мають справи з числами й величинами, наприклад теорія множин, що розроблялася як своєрідна алгебра, де змінні не вказують ні на числа, ні на величини. Проте такі цікаві ідеї не були до кінця реалізовані їхнім автором, оскільки Буль розробляв свою алгебру логіки у формі, традиційній для алгебри того часу, а не у формі продуманої дедуктивної системи.
Сучасні математики поділяють погляди Буля. Помилково вважається, зазначають вони, що обчислення є головним, чим займається математика. Насправді ж у чистій математиці обчислення трапляються дуже рідко. Зазвичай вони здійснюються тоді, коли власне математичну роботу закінчено й ідеться лише про те, щоб, керуючися відомими правилами, виконати певний обсяг суто механічної роботи.
Отже, елементами булевої алгебри множин є не числа, а певні об’єкти, природа яких ігнорується. Істотним при цьому є лише те, що всі елементи алгебри, які називаються множинами, являють собою частини однієї і тієї самої множини. Цю вихідну множину називають універсальною й часто позначають великою латинською літерою U (перша літера латинського слова universalis — загальний), що читається як «всі», «всякий», «будь-який», «ніякий».
Різні науки мають власні універсальні множини предметів, що вивчаються. Так, у арифметиці натуральних чисел універсальною множиною є множина всіх натуральних чисел.
Оскільки множина може містити будь-яку кількість членів, то вона може складатися й з одного елемента. Така множина називається одиничною.
Визначаючи множину, неможливо знати наперед, чи містить вона хоча б один елемент. Тому корисно розглядати й множини, що не мають жодного елемента, тобто порожні множини. Зауважимо, що множина, кожному членові якої не притаманна певна властивість, є множиною, де немає членів, яким притаманна дана властивість. Така множина називається нульовою, або порожньою, і позначається символом 0 (або «0»). Ця множина може містити такі неіснуючі об’єкти, як «круглі квадрати», «жонаті парубки», «зелені ідеї» тощо.
Існують різні способи вилучення підмножин з універсальної множини, число елементів якої може бути як скінченним, так і нескінченним. Одним із таких способів є повний перелік членів множини. Можна також виділяти певну множину як сукупність усіх об’єктів, що відповідають якійсь певній вимозі.
Множину вважають визначеною, якщо можна сказати стосовно будь-якого предмета, належить чи не належить він до цієї множини.
Зазвичай множини позначають великими літерами латинського алфавіту (А, В, С, D, …), а їхні члени — малими літерами того самого алфавіту (а, Ь, с, сі, …).
Над елементами булевої алгебри можна виконувати певні операції. Результатом кожної такої операції, що виконується над множинами (елементами алгебри), буде також множина (елемент алгебри). Ця обставина визначає назву булевої алгебри — алгебра множин.
Правильне розуміння зв’язків між множинами є базою всіх логічних операцій.
Основним поняттям теорії множин є поняття належності елемента множині. Наприклад, кажуть: «Число 2 належить множині всіх натуральних чисел». Для позначення того, що предмет а належить множині А, пишуть
а є А,
де є — символ належності.
Іноді ця формула читається так: «Множина А містить елемент а».
Замість виразів «а не є елементом А», «множина А не містить елемент а», «елемент а не належить множині А» пишуть
at А,
де г — символ відсутності належності.
Іншим важливим відношенням є відношення «бути включеним у», або «міститися в», або «бути підмножиною». Наприклад, множина всіх українських письменників міститься в множині (або включається в множину, або є підмножиною множини) всіх письменників світу.
Відношення між множинами, коли члени однієї множини одночасно є членами іншої множини, називається включенням. Для включення не обов’язково, щоб одна множина була більшою (меншою) за іншу, оскільки тотожні множини також можуть включатися одна в одну або включати одна одну.
Поняття включення множин є фундаментальним принципом усіх відношень між такими множинами.
Є п’ять можливих типів включення множин:
■ Взаємне включення, або тотожність.
■ Повне включення меншої множини в більшу.
■ Часткове включення однієї множини в іншу.
■ Повне включення двох або більше множин в одну велику множину, тобто сума двох чи більше множин утворює одну множину.
■ Повне взаємне виключення множин.
Для інженерів особливий інтерес становить часткове включення. На рис. 8 зображено круги, які перетинаються.
Якщо вважати, що один круг позначає множину А, а другий — множину В, то очевидно, що існує область, яка включає елементи множин А і В. Це свідчить про існування хоча б одного елемента, що належить одночасно множині А і множині В. Елементи, які входять одночасно до обох множин А і В, являють собою так званий добуток А і В, що необхідно враховувати під час вибору структури електричного контура.
Логіки записують часткове включення однієї множини в іншу так: А & В (читається: «А і 5»), де & — символ кон’юнкції. Математики віддають перевагу виразові А П В, де п – символ перетину множин. Інженери зазвичай мають справу з виразами А x В або А х В, де •, х — символ множення.
Добуток двох множин розуміють як формалізацію уявлень про класифікацію предметів відповідно до однієї або кількох ознак.
Часткове включення двох або більше множин на прикладі з кругами показує, що два або більше кругів, які перетинаються, можуть утворювати нову множину, що включає елементи як множини А, так і множини В.
Вираз «Множина А міститься у множині В» (або «А включається у В») позначається як А с В, де с — символ включення. Вираз «Множина А не належить до множини В» (або «А не включається у В») позначається якА Вираз Ас В означає, що кожний елемент а, який належить множині А, належить і множині В. Інакше кажучи, для кожного а з ає А випливає а є В.
Якщо А с В, але АФ В, то А називають власною підмножиною В.
Відомо, що вираз А и В є результатом спільного розгляду двох множин як однієї множини, а вираз An В є спільною частиною даних множин. Що ж стосується виразу А\В, то це є результат вилучення з множини А елементів, що належать до множини В, оскільки \ — символ різниці.
Отже, за допомогою певних операцій із двох множин А і В можна утворювати такі їх комбінації:
а) об’єднання (А и В);
б) перетин (An В);
в) різницю (А\В).
Операції и і п здійснюються за певними законами:
Зазначимо, що за законом асоціативності у виразах вигляду /4иВиС і ЛпВлС розміщення дужок не має значення, тому їх можна пропускати. І навпаки, у таких
виразах, як (ЛиЯ)пС або Ли(/?пС), розміщення дужок відіграє суттєву роль.
Зауважимо, що перші два з названих законів схожі на звичайні закони арифметики, які стосуються операцій додавання (замість u пишеться +) і множення (замість п пишеться • або х). Лише закон дистрибутивності не має аналога в арифметиці.
Важлива роль у теорії множин належить поняттю «відображення», яке є узагальненням поняття «функція».
Розглянемо дві числові множини X і К За законом, кожному числу х, що належить множині X, ставиться у відповідність певне число у, що належить множині Y. Таку відповідність називають функціональною залежністю між незалежною змінною х і залежною змінною у і записують у вигляді формули
У=/(х),
де/—функціональна залежність.
Величина/(х) змінюється, як і залежна змінна, відповідно до змінної х Інакше кажучи, величина/(х) позначає той елементу множини Y, який поставлено у відповідність до елемента х множини X за умов даної функціональної залежності /
Літера/сама по собі не означає певної функціональної залежності. Лише однозначно визначивши відповідність між значеннями незалежної змінної х та залежної змінної У, позначеної як/, ця літера набуває певного змісту.
Для узагальнення сказаного використаємо поняття «відображення», розглянувши такий приклад.
Нехай А — множина всіх велосипедів, В — множина всіх людей, f — відповідність між кожним велосипедом і його власником. Під відображенням f множини А в множину В розуміють певне правило, за допомогою якого кожному елементові а множини А ставиться у відповідність єдиний для нього елемент b множини В. Це відношення позначають так:
Вт Г{а).
Відображення / множини А в множину В називається відображенням множини А в множину В (або покривним відображенням), якщо кожен елемент В є образом якогось елемента з А. Інакше кажучи,/є покриттям, якщо кожний елемент множини В має хоча б один прообраз у множині А.
Відображення/множини А у множину В називається взаємно-однозначним (або одно-однозначним) відображен-Л ням, якщо з різними елементами множини А зіставляються] різні образи множини В, тобто / взаємно-однозначне,! якщо кожен елемент множини В має не більше одного! прообразу у множині А.
Слід підкреслити, що строго формальний опис булевої алгебри має аксіоматичний характер. Тобто йдеться про дедуктивну систему. Про те, що таке дедуктивна система й дедуктивний метод, буде відомо з наступних глав, а поки корисно знати, що для досягнення основної мети — відкриття істинних теорем — математика користується дедуктивним методом. За цим методом математики виво-, дять нові теореми суто логічним шляхом, тобто шляхом; правильних послідовних міркувань.
Закони логіки — це принципи, якими належить керуватися при умовиводах (висновках). Подальшому аналізові ці закони не підлягають, на відміну від математичних аксіом.
Математичні теореми формулюють у вигляді умовних висловлень («Якщо …, то …»), в яких вихідне припущення називається умовою теореми, а висновок — твердженням теореми. Користуючись логічними й математичними аксіомами, будують міцний ланцюжок логічних висновків так, щоб остання ланка збігалася з твердженням теореми. При і цьому говорять, що теорему доведено. Єдиним методом побудови такого ланцюжка (методом виведення) у мате-] матиці є дедукція. Ось чому найхарактернішою рисою ма-\ тематики слід вважати метод дедукції.
Зауважимо, що алгебра Буля має інтерпретацію в багатьох різних теоріях. На думку вчених, це й становить ЇЇ] найбільшу теоретичну і практичну цінність.
Значення виразу «якась теорія має інтерпретацію в іншій теорії» розглянемо на прикладі.
Нехай Х|, …’, х, — усі вихідні терміни якоїсь теорії Х,\ ay,, …, уп — вихідні терміни теорії У. Якщо аксіоми теорії X внаслідок заміни в них символів хь …,хп символами і уи …, уп стають аксіомами чи теоремами У, то це означає, що теорія X має інтерпретацію в теорії У. Інакше кажучи, теорія X має інтерпретацію в теорії У, якщо аксіоми теорії А” залишаться
істинними висловленнями, а вихідним термінам, що містяться в них, надається зміст термінів теорії У.
Отже, якщо теорія X має інтерпретацію в теорії У, то всяка теорема теорії X має аналог серед теорем теорії У. Результати, здобуті в X, можна автоматично переносити в будь-яку теорію, в якій X має інтерпретацію. Що стосується алгебри Буля, то в світлі сказаного можна стверджувати: у будь-якій теорії, в якій може бути інтерпретована дана алгебра, існує фрагмент, що формально не відрізняється від цієї алгебри.
Яскравим прикладом інтерпретації булевої алгебри, яка має велике практичне значення, є теорія електричних кіл.
Викладений матеріал може здатися надто абстрактним, таким, що стосується швидше техніки, а не природничих чи гуманітарних наук. У наступних главах зроблено спробу спростувати таке уявлення.



Популярні глави цього підручника:



Всі глави цього підручника:

Вступ до сучасної логіки (Конспект лекцій)