Вступ до сучасної логіки
§ 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 В або А х В, де •, х — символ множення.
Добуток двох множин розуміють як формалізацію уявлень про класифікацію предметів відповідно до однієї або кількох ознак.
Часткове включення двох або більше множин на прикладі з кругами показує, що два або більше кругів, які перетинаються, можуть утворювати нову множину, що включає елементи як множини А, так і множини В.
Вираз «Множина А міститься у множині В» (або «А включається у В») позначається як А с В, де с — символ включення. Вираз «Множина А не належить до множини В» (або «А не включається у В») позначається якА
Алгебраїчні системи, подібні до алгебри множин, називають алгебрами Буля (булевими алгебрами), іменем математика, який уперше їх розглянув.
Джордж Буль (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 В або А х В, де •, х — символ множення.
Добуток двох множин розуміють як формалізацію уявлень про класифікацію предметів відповідно до однієї або кількох ознак.
Часткове включення двох або більше множин на прикладі з кругами показує, що два або більше кругів, які перетинаються, можуть утворювати нову множину, що включає елементи як множини А, так і множини В.
Вираз «Множина А міститься у множині В» (або «А включається у В») позначається як А с В, де с — символ включення. Вираз «Множина А не належить до множини В» (або «А не включається у В») позначається якА
