Конструктивне поняття безлічі в інформатиці

Головна | Про нас | Зворотній зв'язок

Безлічі: антиномія Рассела, породження, інтерпретації, операції, відносини, n-парні відносини, функції. Функції алгебри логіки, алгебра Буля, предикати.

Г. Кантор - «безліч - єдине ім'я для сукупності всіх об'єктів, що володіють даними властивістю» або «безліч є багато, мислиме як єдине».

У 1903 році англійський математик Бертран Рассел запропонував антиномию в рамках мови класичної ( «наївною») теорії множин Георга Кантора:

Нехай K - безліч всіх множин, які не містять самі себе в якості свого подмножества.Ответ на питання «чи містить K саме себе як підмножини?» Не може бути дано в принципі. Якщо відповіддю є «так», то, за визначенням, таку силу-силенну не повинно бути елементом K. Якщо ж «ні», то, знову ж таки за визначенням, воно повинно бути елементом самого себе.

Дана антиномія (більш відома під назвою «парадокс Рассела») похитнула основи математики і формальної логіки, що змусило провідних математиків того часу почати пошук методів її дозволу.

Пізніше австрійський філософ Курт Гедель показав, що «для досить складних формальних систем завжди знайдуться формули, які неможливо вивести (довести) в рамках даної формальної системи»-перша теорема Геделя про неповноту.

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

Найкраще пояснення природи безлічі все ж належить засновнику теорії множин Георгу Кантор:

Під безліччю ми розуміємо будь-яке з'єднання A в одне ціле певних цілком розрізняються об'єктів a, які існують в

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

Конструктивне поняття безлічі в інформатиці

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

Безлічі в інформатиці вимагають уточнення конструктивного характеру.

1. Породжує механізм для кожного елемента множини.

2. Кожен елемент безлічі повинен відрізнятися від іншого елемента.

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

Два способи породження множин:

а) для кінцевих множин - перерахування елементів;

б) для нескінченних множин - алгоритм або правила породження.

Зазвичай для опису відмінних один від одного елементів застосовується спосіб кодування, такий, що код кожного елемента унікальний.

У сучасних мовах програмування (особливо в об'єктно орієнтованих і функціональних мовах) механізм кодування об'єктів, що становлять безлічі, і операцій над об'єктами визначає сутність мови.

Операції над множинами та їх властивості

всі елементи беруться з деякого «універсального» безлічі, або універсуму, що позначається U або 1.

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

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

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

* Порожня множина - безліч, що не містить жодного елемента.

* Універсальне безліч - безліч, що містить всі мислимі об'єкти.

* Впорядковане безліч - безліч, на якому задано відношення порядку.

Булевой алгеброю називається непорожня безліч M з двома бінарними операціями

∩ (аналог кон'юнкції), ∪ (аналог диз'юнкції), унарною операцією (аналог заперечення)

і двома виділеними елементами: 0 (порожня множина або Брехня) 1 (універсум або Істина) такими, що для всіх A, B і C з безлічі вірні аксіоми: