Пороговая функция — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 36 промежуточных версий 8 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
Булева функция <tex>f(A_1,A_2,...,A_n)</tex> называется '''пороговой''', если ее можно представить в виде <tex>f(A_1,A_2,...,A_n) = [A_1 a_1+A_2 a_2+...+A_n a_n=\sum_{i=1}^n A_i a_i \ge T]</tex>,
+
Булева функция <tex>f(A_1,A_2,\ldots,A_n)</tex> называется '''пороговой''' (англ. ''threshold function''), если ее можно представить в виде <tex>f(A_1,A_2,\ldots,A_n) = [\sum\limits_{i=1}^n A_i a_i \geqslant T]</tex>, где <tex>a_i</tex> {{---}} '''вес''' (англ. ''weight'') аргумента <tex>A_i</tex>, а <tex>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>a_i, T \in R</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>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=3; a_2=4; a_3=6; T=5</tex>.
Все  наборы  значений  аргументов  <tex>A_1, A_2, A_3</tex>  на  которых  функция  принимает  единичное (либо  нулевое)  значение, можно получить из соотношения вида <tex>A_1 3+A_2 4+A_36>5</tex>.
+
Все  наборы  значений  аргументов  <tex>A_1, A_2, A_3</tex>, на  которых  функция  принимает  единичное (либо  нулевое)  значение, можно получить из соотношения вида <tex>3A_1+4A_2+6A_3 \geqslant 5</tex>.
  
:Если <tex>A_1=0;A_2=0;A_3=0, то 0<5 и f=0</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, то 6>5 и f=1</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, то 4<5 и f=0</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, то 10>5 и f=1</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, то 3<5 и f=0</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, то 9>5 и f=1</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, то 7>5 и 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, то 13>5 и f=1</tex>.
+
:Если <tex>A_1=1,A_2=1,A_3=1</tex>, то <tex>13 \geqslant 5 \Rightarrow f=1</tex>.
 
   
 
   
Таким  образом,  заданная  функция  принимает  единичное  значение  на  наборах 001, 011, 101, 110, 111.  Её минимальная форма имеет вид  
+
Таким  образом,  заданная  функция  принимает  единичное  значение  на  наборах <tex>001</tex>, <tex>011</tex>, <tex>101</tex>, <tex>110</tex>, <tex>111</tex>.  Её [[Сокращенная и минимальная ДНФ|минимальная форма]] имеет вид  
 
:<tex>f=A_1 A_2 + A_3</tex>.  
 
:<tex>f=A_1 A_2 + A_3</tex>.  
  
Для  всякой  пороговой  функции  справедливо
+
{{Утверждение
:<tex>[a_1,a_2,a_3,...,a_n;T]=[ka_1,ka_2,ka_3,...,ka_n;kT]</tex>,
+
|statement=Для  всякой  пороговой  функции  справедливо
где k — натуральное число. Чтобы убедиться в этом достаточно записать
+
:<tex>[a_1,a_2,a_3,\ldots,a_n;T]=[ka_1,ka_2,ka_3,\ldots,ka_n;kT]</tex>,
: <tex>ka_1 A_1+ka_2 A_2+...+ka_n A_n \ge kT</tex>
+
где <tex>k</tex> положительное вещественное число.
: <tex>ka_1 A_1+ka_2 A_2+...+ka_n A_n < kT</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 < kT</tex>
 
и разделить обе части неравенства на <tex>k</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</tex>).
+
* [http://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 пороговая функция]
 

Текущая версия на 19:36, 4 сентября 2022

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


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

Пример

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

[math]a_1=3; a_2=4; a_3=6; T=5[/math].

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

Если [math]A_1=0,A_2=0,A_3=0[/math], то [math]0\lt 5 \Rightarrow f=0[/math].
Если [math]A_1=0,A_2=0,A_3=1[/math], то [math]6 \geqslant 5 \Rightarrow f=1[/math].
Если [math]A_1=0,A_2=1,A_3=0[/math], то [math]4\lt 5 \Rightarrow f=0[/math].
Если [math]A_1=0,A_2=1,A_3=1[/math], то [math]10 \geqslant 5 \Rightarrow f=1[/math].
Если [math]A_1=1,A_2=0,A_3=0[/math], то [math]3\lt 5 \Rightarrow f=0[/math].
Если [math]A_1=1,A_2=0,A_3=1[/math], то [math]9 \geqslant 5 \Rightarrow f=1[/math].
Если [math]A_1=1,A_2=1,A_3=0[/math], то [math]7 \geqslant 5 \Rightarrow f=1[/math].
Если [math]A_1=1,A_2=1,A_3=1[/math], то [math]13 \geqslant 5 \Rightarrow f=1[/math].

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

[math]f=A_1 A_2 + A_3[/math].
Утверждение:
Для всякой пороговой функции справедливо
[math][a_1,a_2,a_3,\ldots,a_n;T]=[ka_1,ka_2,ka_3,\ldots,ka_n;kT][/math],
где [math]k[/math] — положительное вещественное число.
[math]\triangleright[/math]

Чтобы убедиться в этом достаточно записать

[math]ka_1 A_1+ka_2 A_2+\ldots+ka_n A_n \geqslant kT[/math]
[math]ka_1 A_1+ka_2 A_2+\ldots+ka_n A_n \lt kT[/math]
и разделить обе части неравенства на [math]k[/math].
[math]\triangleleft[/math]

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

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

[math]A_1=0,A_2=0[/math], то [math]0\lt 2 \Rightarrow f=0[/math].
[math]A_1=0,A_2=1[/math], то [math]1\lt 2 \Rightarrow f=0[/math].
[math]A_1=1,A_2=0[/math], то [math]1\lt 2 \Rightarrow f=0[/math].
[math]A_1=1,A_2=1[/math], то [math]2 \geqslant 2 \Rightarrow f=1[/math].

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

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

[math]A_1=0,A_2=0[/math], то [math]0\lt 1 \Rightarrow f=0[/math].
[math]A_1=0,A_2=1[/math], то [math]1 \geqslant 1 \Rightarrow f=1[/math].
[math]A_1=1,A_2=0[/math], то [math]1 \geqslant 1 \Rightarrow f=1[/math].
[math]A_1=1,A_2=1[/math], то [math]2 \geqslant 1 \Rightarrow f=1[/math].

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

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

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

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

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

См. также

Источники информации