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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Пример непороговой функции)
Строка 39: Строка 39:
 
Примером непороговой функции может служить Сложение по модулю 2 (<tex>XOR</tex>).
 
Примером непороговой функции может служить Сложение по модулю 2 (<tex>XOR</tex>).
  
Предположим, что <tex>XOR</tex> {{---}} пороговая функция. При аргументах <tex>(0, 0)</tex> значение функции <tex>XOR</tex> равно 0. Тогда, по определению пороговой функции неравенство <tex>A_1 x_1+A_2 x_2 \ge T</tex> не должно выполняться. Подставляя значение аргументов, получаем, что <tex>T>0</tex>. При аргументах <tex>(0, 1)</tex> и <tex>(1, 0)</tex> значение функции <tex>XOR</tex> равно 1. Тогда, по определению выполняется неравенство <tex>A_1 x_1+A_2 x_2 \ge T</tex>, подставляя  в которое значения соответствующих аргументов, получаем <tex>A_1 \ge T, A_2 \ge T</tex>. Отсюда следует, что <tex>A_1>0, A_2>0</tex> и <tex>A_1+A_2 \ge 2T</tex>. При аргументах <tex>(1, 1)</tex> значение функции <tex>XOR</tex> равно 0, следовательно неравенство <tex>A_1 x_1+A_2 x_2 \ge T</tex> выполняться  не должно, то есть <tex>A_1+A_2 < T</tex>. Но неравенства <tex>A_1+A_2 \ge 2T</tex> и <tex>A_1+A_2 < T</tex> при положительных <tex>A_1,A_2</tex> и <tex>T</tex> одновременно выполняться не могут. Получили противоречие и, значит, функция <tex>XOR</tex> непороговая.
+
Предположим, что <tex>XOR</tex> {{---}} пороговая функция. При аргументах <tex>(0, 0)</tex> значение функции <tex>XOR</tex> равно 0. Тогда, по определению пороговой функции неравенство <tex>A_1 x_1+A_2 x_2 \ge T</tex> не должно выполняться. Подставляя значение аргументов, получаем, что <tex>T>0</tex>. При аргументах <tex>(0, 1)</tex> и <tex>(1, 0)</tex> значение функции <tex>XOR</tex> равно 1. Тогда, по определению выполняется неравенство <tex>A_1 x_1+A_2 x_2 \ge T</tex>, подставляя  в которое значения соответствующих аргументов, получаем <tex>A_1 \ge T, A_2 \ge T</tex>. Отсюда следует, что <tex>A_1>0, A_2>0</tex> и <tex>A_1+A_2 \ge 2T</tex>. При аргументах <tex>(1, 1)</tex> значение функции <tex>XOR</tex> равно 0, следовательно неравенство <tex>A_1 x_1+A_2 x_2 \ge T</tex> выполняться  не должно, то есть <tex>A_1+A_2 < T</tex>. Но неравенства <tex>A_1+A_2 \ge 2T</tex> и <tex>A_1+A_2 < T</tex> при положительных <tex>A_1,A_2</tex> и <tex>T</tex> одновременно выполняться не могут. Получили противоречие, следовательно, функция <tex>XOR</tex> {{---}} непороговая.
  
 
== Источники ==
 
== Источники ==
 
* [http://www.simvol.biz/uploadfiles/File/sostav/books/Diskret_mat1.pdf пороговая функция]
 
* [http://www.simvol.biz/uploadfiles/File/sostav/books/Diskret_mat1.pdf пороговая функция]

Версия 02:22, 13 октября 2011

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


Обычно пороговую функцию записывают в следующим виде: [math]f = [a_1,a_2,a_3,...,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\ge5[/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\ge5 \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\ge5 \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\ge5 \Rightarrow f=1[/math].
Если [math]A_1=1,A_2=1,A_3=0[/math], то [math]7\ge5 \Rightarrow f=1[/math].
Если [math]A_1=1,A_2=1,A_3=1[/math], то [math]13\ge5 \Rightarrow f=1[/math].

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

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

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

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

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

Примером непороговой функции может служить Сложение по модулю 2 ([math]XOR[/math]).

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

Источники