Пороговая функция

Определение:

Булева функция $f(A_1,A_2,...,A_n)$ называется пороговой, если ее можно представить в виде $f(A_1,A_2,...,A_n) = [\sum\limits_{i=1}^n A_i a_i \ge T]$, где $a_i$ — вес аргумента $A_i$, а $T$ — порог функции $f$; $a_i, T \in R$

Обычно пороговую функцию записывают в следующим виде: $f = [a_1,a_2,a_3,...,a_n;T]$.

Пример

Рассмотрим функцию трёх аргументов $f(A_1,A_2,A_3)=[3,4,6;5]$. Согласно этой записи имеем

$a_1=3; a_2=4; a_3=6; T=5$.

Все наборы значений аргументов $A_1, A_2, A_3$, на которых функция принимает единичное (либо нулевое) значение, можно получить из соотношения вида $3A_1+4A_2+6A_3\ge5$.

Если $A_1=0,A_2=0,A_3=0$, то $0\lt 5 \Rightarrow f=0$.

Если $A_1=0,A_2=0,A_3=1$, то $6\ge5 \Rightarrow f=1$.

Если $A_1=0,A_2=1,A_3=0$, то $4\lt 5 \Rightarrow f=0$.

Если $A_1=0,A_2=1,A_3=1$, то $10\ge5 \Rightarrow f=1$.

Если $A_1=1,A_2=0,A_3=0$, то $3\lt 5 \Rightarrow f=0$.

Если $A_1=1,A_2=0,A_3=1$, то $9\ge5 \Rightarrow f=1$.

Если $A_1=1,A_2=1,A_3=0$, то $7\ge5 \Rightarrow f=1$.

Если $A_1=1,A_2=1,A_3=1$, то $13\ge5 \Rightarrow f=1$.

Таким образом, заданная функция принимает единичное значение на наборах 001, 011, 101, 110, 111. Её минимальная форма имеет вид

$f=A_1 A_2 + A_3$.

Утверждение:

Для всякой пороговой функции справедливо $[a_1,a_2,a_3,...,a_n;T]=[ka_1,ka_2,ka_3,...,ka_n;kT]$, где k — положительное вещественное число.

$\triangleright$

Чтобы убедиться в этом достаточно записать $ka_1 A_1+ka_2 A_2+...+ka_n A_n \ge kT$ $ka_1 A_1+ka_2 A_2+...+ka_n A_n \lt kT$ и разделить обе части неравенства на $k$.

$\triangleleft$

Примеры пороговых функций

Примерами пороговых функций служат функции $\operatorname{AND}$ и $\operatorname{OR}$. Представим функцию $\operatorname{AND}$ в виде $[1,1;2]$. Докажем, что это именно пороговая функция, подставив все возможные значения аргументов:

$A_1=0,A_2=0$, то $0\lt 2 \Rightarrow f=0$.

$A_1=0,A_2=1$, то $1\lt 2 \Rightarrow f=0$.

$A_1=1,A_2=0$, то $1\lt 2 \Rightarrow f=0$.

$A_1=1,A_2=1$, то $2\ge2 \Rightarrow f=1$.

Таблица значений совпадает с таблицей истинности функции $\operatorname{AND}$, следовательно $\operatorname{AND}$ — пороговая функция.

Функцию $\operatorname{OR}$ представим в виде $[1,1;1]$. Аналогично докажем, что это пороговая функция:

$A_1=0,A_2=0$, то $0\lt 1 \Rightarrow f=0$.

$A_1=0,A_2=1$, то $1\ge1 \Rightarrow f=1$.

$A_1=1,A_2=0$, то $1\ge1 \Rightarrow f=1$.

$A_1=1,A_2=1$, то $2\ge1 \Rightarrow f=1$.

Таблица значений совпадает с таблицей истинности функции $\operatorname{OR}$, следовательно $\operatorname{OR}$ — пороговая функция.

Пример непороговой функции

Утверждение:

Функция $\operatorname{XOR}$ — непороговая.

$\triangleright$

Предположим, что $\operatorname{XOR}$ — пороговая функция. При аргументах $(0, 0)$ значение функции $\operatorname{XOR}$ равно 0. Тогда по определению пороговой функции неравенство $A_1 x_1+A_2 x_2 \ge T$ не должно выполняться. Подставляя значение аргументов, получаем, что $T\gt 0$. При аргументах $(0, 1)$ и $(1, 0)$ значение функции $\operatorname{XOR}$ равно 1. Тогда по определению выполняется неравенство $A_1 x_1+A_2 x_2 \ge T$, подставляя в которое значения соответствующих аргументов, получаем $A_1 \ge T, A_2 \ge T$. Отсюда следует, что $A_1\gt 0, A_2\gt 0$ и $A_1+A_2 \ge 2T$. При аргументах $(1, 1)$ значение функции $\operatorname{XOR}$ равно 0, следовательно неравенство $A_1 x_1+A_2 x_2 \ge T$ выполняться не должно, то есть $A_1+A_2 \lt T$. Но неравенства $A_1+A_2 \ge 2T$ и $A_1+A_2 \lt T$ при положительных $A_1,A_2$ и $T$ одновременно выполняться не могут. Получили противоречие, следовательно, функция $\operatorname{XOR}$ — непороговая.

$\triangleleft$

Значимость пороговых функций

Пороговые функции алгебры логики представляют интерес в связи с простотой технической реализации, в связи со своими вычислительными возможностями, а также благодаря возможности их обучения. Последнее свойство с успехом применяется на практике при решении плохо формализуемых задач. Пороговые функции применяются в качестве передаточных функций в искусственных нейронах, из которых состоят искусственные нейронные сети. А так как искусственный нейрон полностью характеризуется своей передаточной функцией, то пороговые функции являются математической моделью нейронов.

Источники

• Пороговая функция
• Искусственный нейрон — Википедия