Характеристична функція

Тривимірний графік індикаторної функції, який відображає серповидну двовимірну підмножину $A$ двовимірного квадрата — множина $X$, де точки $x\in A$ мають координату z=1 (колір охри), а точки $x\notin A$ квадрата мають координату z=0 (червоний' колір').

Характеристична функція (індикаторна функція, індикатор) підмножини $A\subseteq X$ — функція, визначена на множині $X$, яка визначає належність елемента $x\in X$ підмножині $A$.

Означення

Нехай $A\subseteq X$ — деяка підмножина довільної множини $X$. Функцію ${\mathrm{𝟏}}_A:X\to \{0,1\}$, означену таким чином:

${\mathrm{𝟏}}_A(x)=\{\begin{array}{cc}1,& x\in A,\\ 0,& x\notin A,\end{array}$

називають характеристичною функцією або індикатором множини $A$.

Альтернативними позначеннями індикатора множини $A$ є: ${\chi }_A$ або ${𝐈}_A$, а іноді навіть $A(x)$. Нотація Айверсона дозволяє позначення $[x\in A]$.

(Грецька літера $\chi$ походить від початкової букви грецького написання слова характеристика.)

Замітка. Позначення ${\mathrm{𝟏}}_A$ може означати тотожну функцію.

Основні властивості

Відображення, яке пов'язує підмножину $A\subseteq X$ з її індикатором ${\mathrm{𝟏}}_A$, є ін'єкцією. Якщо $A$ і $B$ — дві підмножини $X$, то

${\mathrm{𝟏}}_{A\cap B}=\min \{{\mathrm{𝟏}}_A,{\mathrm{𝟏}}_B\}={\mathrm{𝟏}}_A{\mathrm{𝟏}}_B,$

${\mathrm{𝟏}}_{A\cup B}=\max \{{\mathrm{𝟏}}_A,{\mathrm{𝟏}}_B\}={\mathrm{𝟏}}_A+{\mathrm{𝟏}}_B-{\mathrm{𝟏}}_A{\mathrm{𝟏}}_B,$

${\mathrm{𝟏}}_{A\mathrm{△}B}={\mathrm{𝟏}}_A+{\mathrm{𝟏}}_B-2({\mathrm{𝟏}}_{A\cap B}),$

${\mathrm{𝟏}}_{A^c}=1-{\mathrm{𝟏}}_A.$

Загальніше, нехай $A_1,\dots ,A_n$ — множина підмножин $X$. Тоді для довільного $x\in X$

$\prod _{k\in I}(1-{\mathrm{𝟏}}_{A_k}(x))$ — добуток нулів та одиниць. Цей добуток набуває значення 1 для тих $x\in X$, які не належать жодній множині $A_k$, і 0 в іншому разі. Тому

$\prod _{k\in I}(1-{\mathrm{𝟏}}_{A_k})={\mathrm{𝟏}}_{X-\bigcup _k{A}_k}=1-{\mathrm{𝟏}}_{\bigcup _k{A}_k}.$

Розкладаючи ліву частину, отримуємо

${\mathrm{𝟏}}_{\bigcup _k{A}_k}=1-\sum _{F\subseteq \{1,2,\dots ,n\}}(-1{)}^{|F|}{\mathrm{𝟏}}_{\bigcap _F{A}_k}=\sum _{\mathrm{\varnothing }\ne F\subseteq \{1,2,\dots ,n\}}(-1{)}^{|F|+1}{\mathrm{𝟏}}_{\bigcap _F{A}_k},$

де $|F|$ — потужність $F$. Це — одна з форм запису принципу включення-виключення. Отже, індикатор — корисне позначення в комбінаториці, яке використовують також і в інших областях, наприклад в теорії ймовірностей: якщо $X$ — ймовірнісний простір з ймовірнісною мірою $𝐏$, а $A$ — вимірна множина, то індикатор ${\mathrm{𝟏}}_A$ стає випадковою величиною, чиє математичне очікування дорівнює ймовірності $A:$

$E({\mathrm{𝟏}}_A)=\underset{X}{\int }{\mathrm{𝟏}}_A(x)d𝐏=\underset{A}{\int }d𝐏=𝐏(A).$

Дисперсія та коваріація для цієї випадкової змінної визначаються за формулами:

$\mathrm{Var}({\mathrm{𝟏}}_A(\omega ))=\mathrm{P}(A)(1-\mathrm{P}(A))$

$\mathrm{Cov}({\mathrm{𝟏}}_A(\omega ),{\mathrm{𝟏}}_B(\omega ))=\mathrm{P}(A\cap B)-\mathrm{P}(A)\mathrm{P}(B)$

Зауваження щодо позначення та термінології

Позначення $A$ також використовують для позначення ${𝐗}_A$, Шаблон:Нп в опуклому аналізі, яку означують як обернене до стандартного означення характеристичної функції.

Термін «характеристична функція» має незалежне значення в класичній теорії ймовірностей. З цієї причини Шаблон:Нп використовують термін індикаторна функція майже ексклюзивно, тоді як математики в інших областях для опису функції, що вказує на приналежність до множини, використовують скоріше термін характеристична функція.

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

Середнє значення, дисперсія та коваріація

Для заданого ймовірнісного простору $(\mathrm{\Omega },ℱ,\mathrm{P})$, та $A\in ℱ$, індикаторну випадкову змінну ${\mathrm{𝟏}}_A:\mathrm{\Omega }\to ℝ$ означують як ${\mathrm{𝟏}}_A(\omega )=1$, якщо $\omega \in A,$, інакше ${\mathrm{𝟏}}_A(\omega )=0.$

Середнє значення

$\mathrm{E}({\mathrm{𝟏}}_A(\omega ))=\mathrm{P}(A)$.

Дисперсія

$\mathrm{Var}({\mathrm{𝟏}}_A(\omega ))=\mathrm{P}(A)(1-\mathrm{P}(A))$.

Коваріація

$\mathrm{Cov}({\mathrm{𝟏}}_A(\omega ),{\mathrm{𝟏}}_B(\omega ))=\mathrm{P}(A\cap B)-\mathrm{P}(A)\mathrm{P}(B)$.

Характеристична функція в теорії рекурсії, представляльна функція Геделя та Кліні

Курт Гедель описав представляльну функцію (Шаблон:Lang-en) у своїй праці 1934 року «Про нерозв'язні твердження формальних математичних систем» (цю працю опубліковано на стор. 41-74 книжки «Нерозв'язне», «The Undecidable», під редагуванням Мартіна Девіса):

«Кожному класові чи відношенню $R$ повинна відповідати представляльна функція $\phi (x_1,\dots ,x_n)=0$ , якщо $R(x_1,\dots ,x_n)$ та $\phi (x_1,\dots ,x_n)=1$, якщо $\sim R(x_1,\dots ,x_n)$.» (стор. 42; «~» позначує логічне обернення, тобто «НЕ»).

Стівен Кліні (1952) (стор. 227) запропонував таке саме означення в контексті примітивно-рекурсивних функцій як функції $\phi$ від предикату $R$, що набуває значення $0$, якщо предикат є істинним, та $1$, якщо предикат є хибним.

Наприклад, оскільки добуток характеристичних функцій ${\phi }_1{\phi }_2\cdots {\phi }_n=0$, якщо будь-яка з ціх функцій дорівнює $0$, то вона відіграє роль логічного АБО: ЯКЩО ${\phi }_1=0$ АБО ${\phi }_2=0$ АБО . . . АБО ${\phi }_n=0$ ТОДІ їх добуток дорівнює $0$. Те, що видається сучасному читачеві як логічне обернення представляльної функції, тобто, що представляльна функція дорівнює $0$, коли функція $R$ є «істинною» чи «вдоволеною», відіграє корисну роль в означенні Кліні логічних функцій «OR», «AND», та «IMPLY» (стор. 228), обмежених (стор. 228) та необмежених (стор. 279 і далі) μ-операторів (Кліні, 1952), та функції «CASE» (стор. 229).

Характеристична функція в теорії нечітких множин

В класичній математиці характеристичні функції множин набувають лише значень 1 (елемент) та 0 (не елемент). В теорії нечітких множин характеристичні функції узагальнюють до набування значень з дійсного одиничного проміжку [0, 1], або, загальніше, з деякої алгебри або Шаблон:Нп (яка зазвичай повинна бути щонайменше частково впорядкованою множиною або ґраткою). Такі узагальнені характеристичні функції частіше називають функціями належності, а відповідні «множини» називаються нечіткими множинами. Нечіткі множини моделюють поступову зміну Шаблон:Нп, що спостерігається у багатьох предикатів реального світу, таких як «високий», «теплий» тощо.

Див. також

• Характеристична функція випадкової величини
• Характеристична функція (теорія ігор)
• Вільні і зв'язані змінні
• Функція належності
• Проста функція
• Шаблон:Нп
• Лапласіан індикатора
• Дельта-функція Дірака
• Розширення логіки предикатів
• Функція Гевісайда
• Дужка Айверсона
• Символ Кронекера, функція, яку можна розглядати як індикатор для відношення рівності
• Шаблон:Нп
• Мультимножина
• Шаблон:Нп
• Задача класифікації
• Функція втрат 0-1

Джерела

• Шаблон:Cite book Шаблон:Ref-en
• Шаблон:CLRS
• Шаблон:Cite book Шаблон:Ref-en
• Шаблон:Cite book Шаблон:Ref-en