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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
Строка 1: Строка 1:
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 
|+
 
|-align="center"
 
|'''НЕТ ВОЙНЕ'''
 
|-style="font-size: 16px;"
 
|
 
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 
 
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 
 
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 
 
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 
 
''Антивоенный комитет России''
 
|-style="font-size: 16px;"
 
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 
|-style="font-size: 16px;"
 
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 
|}
 
 
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =

Текущая версия на 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]

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

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

См. также

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