Изменения

Перейти к: навигация, поиск

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

4420 байт добавлено, 18:12, 27 декабря 2017
Нет описания правки
Пусть даны <tex>n</tex> логических аргументов {{Определение|definition =Булева функция <tex>f(A_1,A_2,...\ldots,A_n)</tex>. Поставим в соответствие этим аргументам натуральные числа <tex>a_1,a_2,...,a_n</tex>, называемые весами, и зададим некоторое неотрицательное число <tex>T</tex>, которое будем называть называется '''порогомпороговой'''(англ. Условимся считать''threshold function''), что если на каком-либо наборе ее можно представить в виде <tex>f(A_1 a_1+,A_2 a_2+...+,\ldots,A_n a_n) =[\sum_sum\limits_{i=1}^n A_i a_i>\geqslant T]</tex>, где знак <tex>"+"a_i</tex> обозначает арифметическое сложение, то булева функция <tex>f{{---}} '''вес''' (A_1,A_2,англ...,A_n''weight'')</tex> принимает единичное значение на этом наборе. Если же на каком-либо наборе аргумента <tex>\sum_{i=1}^n A_i a_i \le T</tex>, то функция а <tex>f(A_1,A_2,...,A_n)T</tex> на этом наборе принимает нулевое значение. Функцию, представленную описанным способом, будем называть {{---}} '''пороговой функциейпорог'''(англ.''threshold'') функции <tex>f</tex>; <tex>a_i, T \in R</tex>}}
Обычно пороговую функцию записывают в следующим виде: <tex>f = [a_1,a_2,a_3,\ldots,a_n;T]</tex>.
Обычно пороговую функцию записывают в следующим виде: <tex>f = [a_1,a_2,a_3,...,a_n;T]</tex>.= Пример == Для примера рассмотрим Рассмотрим функцию трёх аргументов <tex>f(A_1,A_2,A_3)=[3,4,6;5]</tex>.
Согласно этой записи имеем
:<tex>a_1=3; a_2=4; a_3=6; T=5</tex>.
Все наборы значений аргументов <tex>A_1, A_2, A_3</tex> , на которых функция принимает единичное (либо нулевое) значение, можно получить из соотношения вида <tex>A_1 33A_1+A_2 44A_2+A_36>6A_3 \geqslant 5</tex>.
:Если <tex>A_1=0;,A_2=0;,A_3=0</tex>, то <tex>0<5 и \Rightarrow f=0</tex>. :Если <tex>A_1=0;,A_2=0;,A_3=1</tex>, то <tex>6>\geqslant 5 и \Rightarrow f=1</tex>. :Если <tex>A_1=0;,A_2=1;,A_3=0</tex>, то <tex>4<5 и \Rightarrow f=0</tex>.:Если <tex>A_1=0;,A_2=1;,A_3=1</tex>, то <tex>10>\geqslant 5 и \Rightarrow f=1</tex>. :Если <tex>A_1=1;,A_2=0;,A_3=0</tex>, то <tex>3<5 и \Rightarrow f=0</tex>. :Если <tex>A_1=1;,A_2=0;,A_3=1</tex>, то <tex>9>\geqslant 5 и \Rightarrow f=1</tex>.:Если <tex>A_1=1;,A_2=1;,A_3=0</tex>, то <tex>7>\geqslant 5 и \Rightarrow f=1</tex>.:Если <tex>A_1=1;,A_2=1;,A_3=1</tex>, то <tex>13>\geqslant 5 и \Rightarrow f=1</tex>.
Таким образом, заданная функция принимает единичное значение на наборах <tex>001</tex>, <tex>011</tex>, <tex>101</tex>, <tex>110</tex>, <tex>111</tex>. Её [[Сокращенная и минимальная ДНФ|минимальная форма ]] имеет вид
:<tex>f=A_1 A_2 + A_3</tex>.
{{Утверждение|statement=Для всякой пороговой функции справедливо:<tex>[a_1,a_2,a_3,...\ldots,a_n;T]=[ka_1,ka_2,ka_3,...\ldots,ka_n;kT]</tex>,где <tex>k </tex> натуральное положительное вещественное число. |proof=Чтобы убедиться в этом достаточно записать: <tex>ka_1 A_1+ka_2 A_2+...\ldots+ka_n A_n>\geqslant kT</tex>: <tex>ka_1 A_1+ka_2 A_2+...\ldots+ka_n A_n \le < kT</tex>
и разделить обе части неравенства на <tex>k</tex>.
}}
 
== Примеры пороговых функций ==
 
Примерами пороговых функций служат функции <tex> \operatorname{AND} </tex> и <tex> \operatorname{OR} </tex>. Представим функцию <tex> \operatorname{AND} </tex> в виде <tex>[1,1;2]</tex>.
Докажем, что это именно пороговая функция, подставив все возможные значения аргументов:
:<tex>A_1=0,A_2=0</tex>, то <tex>0<2 \Rightarrow f=0</tex>.
:<tex>A_1=0,A_2=1</tex>, то <tex>1<2 \Rightarrow f=0</tex>.
:<tex>A_1=1,A_2=0</tex>, то <tex>1<2 \Rightarrow f=0</tex>.
:<tex>A_1=1,A_2=1</tex>, то <tex>2 \geqslant 2 \Rightarrow f=1</tex>.
Таблица значений совпадает с таблицей истинности функции <tex> \operatorname{AND} </tex>, следовательно <tex> \operatorname{AND} </tex> {{---}} пороговая функция.
 
Функцию <tex> \operatorname{OR} </tex> представим в виде <tex>[1,1;1]</tex>.
Аналогично докажем, что это пороговая функция:
:<tex>A_1=0,A_2=0</tex>, то <tex>0<1 \Rightarrow f=0</tex>.
:<tex>A_1=0,A_2=1</tex>, то <tex>1 \geqslant 1 \Rightarrow f=1</tex>.
:<tex>A_1=1,A_2=0</tex>, то <tex>1 \geqslant 1 \Rightarrow f=1</tex>.
:<tex>A_1=1,A_2=1</tex>, то <tex>2 \geqslant 1 \Rightarrow f=1</tex>.
Таблица значений совпадает с таблицей истинности функции <tex> \operatorname{OR} </tex>, следовательно <tex> \operatorname{OR} </tex> {{---}} пороговая функция.
== Пример непороговой функции ==
{{Утверждение
|statement=
Функция <tex> \operatorname{XOR} </tex> {{---}} непороговая.
|proof=
Предположим, что <tex> \operatorname{XOR} </tex> {{---}} пороговая функция. При аргументах <tex>(0, 0)</tex> значение функции <tex> \operatorname{XOR} </tex> равно <tex>0</tex>. Тогда по определению пороговой функции неравенство <tex>A_1 x_1+A_2 x_2 \geqslant T</tex> не должно выполняться. Подставляя значение аргументов, получаем, что <tex>T>0</tex>. При аргументах <tex>(0, 1)</tex> и <tex>(1, 0)</tex> значение функции <tex> \operatorname{XOR} </tex> равно <tex>1</tex>. Тогда по определению выполняется неравенство <tex>A_1 x_1+A_2 x_2 \geqslant T</tex>, подставляя в которое значения соответствующих аргументов, получаем <tex>A_1 \geqslant T, A_2 \geqslant T</tex>. Отсюда следует, что <tex>A_1>0, A_2>0</tex> и <tex>A_1+A_2 \geqslant 2T</tex>. При аргументах <tex>(1, 1)</tex> значение функции <tex> \operatorname{XOR} </tex> равно 0, следовательно неравенство <tex>A_1 x_1+A_2 x_2 \geqslant T</tex> выполняться не должно, то есть <tex>A_1+A_2 < T</tex>. Но неравенства <tex>A_1+A_2 \geqslant 2T</tex> и <tex>A_1+A_2 < T</tex> при положительных <tex>A_1,A_2</tex> и <tex>T</tex> одновременно выполняться не могут. Получили противоречие, следовательно, функция <tex> \operatorname{XOR} </tex> {{---}} непороговая.
}}
 
== Значимость пороговых функций ==
 
Пороговые функции алгебры логики представляют интерес в связи с простотой технической реализации, в связи со своими вычислительными возможностями, а также благодаря возможности их обучения. Последнее свойство с успехом применяется на практике при решении плохо формализуемых задач. Пороговые функции применяются в качестве передаточных функций в искусственных нейронах, из которых состоят искусственные нейронные сети. А так как искусственный нейрон полностью характеризуется своей передаточной функцией, то пороговые функции являются математической моделью нейронов.
 
== См. также ==
* [[Определение_булевой_функции|Булевы функции]]
* [[Полные_системы_функций._Теорема_Поста_о_полной_системе_функций#.D0.97.D0.B0.D0.BC.D0.BA.D0.BD.D1.83.D1.82.D1.8B.D0.B5_.D0.BA.D0.BB.D0.B0.D1.81.D1.81.D1.8B_.D0.B1.D1.83.D0.BB.D0.B5.D0.B2.D1.8B.D1.85_.D1.84.D1.83.D0.BD.D0.BA.D1.86.D0.B8.D0.B9|Замкнутые классы булевых функций]]
 
== Источники информации ==
Примером непороговой функции может служить Сложение по модулю 2 (<tex>XOR<* [http:/tex>)/www.simvol.biz/uploadfiles/File/sostav/books/Diskret_mat1.pdf Пороговая функция]* [http://ru.wikipedia.org/wiki/Искусственный_нейрон Википедия — Искусственный нейрон]
При аргументах (0, 1) значение функции <tex>XOR</tex> равно 1. Тогда, по определению пороговой функции выполняется неравенство <tex>A_1 x+A_2 x>T</tex>, подставляя значения аргументов, получаем <tex>A_2>T</tex>. Аналогично, при аргументах (1, 0) получаем <tex>A_1>T</tex>. Отсюда следует, что <tex>A_1+A_2>T</tex>. Но это неравенстово не выполняется при аргументах (1, 1). Значит, функция <tex>XOR</tex> непороговая.[[Категория: Дискретная математика и алгоритмы]]
== Источники ==* [http[Категория://www.simvol.biz/uploadfiles/File/sostav/books/Diskret_mat1.pdf пороговая функцияБулевы функции ]]
Анонимный участник

Навигация