Характеристична функція
Характеристична функція (індикаторна функція, індикатор) підмножини — функція, визначена на множині , яка визначає належність елемента підмножині .
Означення
Нехай — деяка підмножина довільної множини . Функцію , означену таким чином:
називають характеристичною функцією або індикатором множини .
Альтернативними позначеннями індикатора множини є: або , а іноді навіть . Нотація Айверсона дозволяє позначення .
(Грецька літера походить від початкової букви грецького написання слова характеристика.)
Замітка. Позначення може означати тотожну функцію.
Основні властивості
Відображення, яке пов'язує підмножину з її індикатором , є ін'єкцією. Якщо і — дві підмножини , то
Загальніше, нехай — множина підмножин . Тоді для довільного
- — добуток нулів та одиниць. Цей добуток набуває значення 1 для тих , які не належать жодній множині , і 0 в іншому разі. Тому
Розкладаючи ліву частину, отримуємо
де — потужність . Це — одна з форм запису принципу включення-виключення. Отже, індикатор — корисне позначення в комбінаториці, яке використовують також і в інших областях, наприклад в теорії ймовірностей: якщо — ймовірнісний простір з ймовірнісною мірою , а — вимірна множина, то індикатор стає випадковою величиною, чиє математичне очікування дорівнює ймовірності
Дисперсія та коваріація для цієї випадкової змінної визначаються за формулами:
Зауваження щодо позначення та термінології
Позначення також використовують для позначення , характеристичної функції в опуклому аналізі, яку означують як обернене до стандартного означення характеристичної функції.
Термін «характеристична функція» має незалежне значення в класичній теорії ймовірностей. З цієї причини традиційні ймовірнісники використовують термін індикаторна функція майже ексклюзивно, тоді як математики в інших областях для опису функції, що вказує на приналежність до множини, використовують скоріше термін характеристична функція.
У нечіткій логіці та сучасній багатозначній логіці предикати є характеристичними функціями розподілу ймовірності. Тобто, строгу істинну/хибну оцінку предикату замінюють величиною, що інтерпретують як степінь істинності.
Середнє значення, дисперсія та коваріація
Для заданого ймовірнісного простору , та , індикаторну випадкову змінну означують як , якщо , інакше
Характеристична функція в теорії рекурсії, представляльна функція Геделя та Кліні
Курт Гедель описав представляльну функцію[1][2][3] (англ. representing function) у своїй праці 1934 року «Про нерозв'язні твердження формальних математичних систем» (цю працю опубліковано на стор. 41-74 книжки «Нерозв'язне», «The Undecidable», під редагуванням Мартіна Девіса):
- «Кожному класові чи відношенню повинна відповідати представляльна функція , якщо та , якщо .» (стор. 42; «~» позначує логічне обернення, тобто «НЕ»).
Стівен Кліні (1952) (стор. 227) запропонував таке саме означення в контексті примітивно-рекурсивних функцій як функції від предикату , що набуває значення , якщо предикат є істинним, та , якщо предикат є хибним.
Наприклад, оскільки добуток характеристичних функцій , якщо будь-яка з ціх функцій дорівнює , то вона відіграє роль логічного АБО: ЯКЩО АБО АБО . . . АБО ТОДІ їх добуток дорівнює . Те, що видається сучасному читачеві як логічне обернення представляльної функції, тобто, що представляльна функція дорівнює , коли функція є «істинною» чи «вдоволеною», відіграє корисну роль в означенні Кліні логічних функцій «OR», «AND», та «IMPLY» (стор. 228), обмежених (стор. 228) та необмежених (стор. 279 і далі) μ-операторів (Кліні, 1952), та функції «CASE» (стор. 229).
Характеристична функція в теорії нечітких множин
В класичній математиці характеристичні функції множин набувають лише значень 1 (елемент) та 0 (не елемент). В теорії нечітких множин характеристичні функції узагальнюють до набування значень з дійсного одиничного проміжку [0, 1], або, загальніше, з деякої алгебри або структури (яка зазвичай повинна бути щонайменше частково впорядкованою множиною або ґраткою). Такі узагальнені характеристичні функції частіше називають функціями належності, а відповідні «множини» називаються нечіткими множинами. Нечіткі множини моделюють поступову зміну ступеня істинності, що спостерігається у багатьох предикатів реального світу, таких як «високий», «теплий» тощо.
Примітки
- representing // Англійсько-український словник з математики та інформатики / уклад. Є. Мейнарович, М. Кратко. — 2010.
- representing // Англійсько-українсько-англійський словник наукової мови (фізика та споріднені науки). Частина І англійсько-українська / уклад. О. Кочерга, Є. Мейнарович. — 2010.
- представляльний // Англійсько-українсько-англійський словник наукової мови (фізика та споріднені науки). Частина ІІ українсько-англійська / уклад. О. Кочерга, Є. Мейнарович. — 2010.
Див. також
- Характеристична функція випадкової величини
- Характеристична функція (теорія ігор)
- Вільні і зв'язані змінні
- Функція належності
- Проста функція
- Міра Дірака
- Лапласіан індикатора
- Дельта-функція Дірака
- Розширення логіки предикатів
- Функція Гевісайда
- Дужка Айверсона
- Символ Кронекера, функція, яку можна розглядати як індикатор для відношення рівності
- Дужки Маколея
- Мультимножина
- Фіктивна змінна (статистика)
- Задача класифікації
- Функція втрат 0-1
Джерела
- Folland, G.B. (1999). Real Analysis: Modern Techniques and Their Applications (вид. Second). John Wiley & Sons, Inc. ISBN 978-0-471-31716-6. (англ.)
- Томас Кормен; Чарльз Лейзерсон, Рональд Рівест, Кліфорд Стайн (2001) [1990]. Section 5.2: Indicator random variables. Вступ до алгоритмів (вид. 2nd). MIT Press і McGraw-Hill. ISBN 0-262-03293-7.
- Davis, Martin, ред. (1965). The Undecidable. New York: Raven Press Books, Ltd. (англ.)
- Kleene, Stephen (1971) [1952]. Introduction to Metamathematics (Sixth Reprint with corrections). Netherlands: Wolters-Noordhoff Publishing and North Holland Publishing Company. (англ.)