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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
Пусть даны <tex>n</tex> логических аргументов <tex>A_1,A_2,...,A_n</tex>. Поставим в соответствие этим аргументам натуральные числа <tex>a_1,a_2,...,a_n</tex>, называемые весами, и зададим некоторое неотрицательное число <tex>T</tex>, которое будем называть '''порогом'''. Условимся считать, что если на каком-либо наборе <tex>A_1 a_1+A_2 a_2+...+A_n a_n=\sum_{i=1}^n A_i a_i>T</tex>, где знак <tex>"+"</tex> обозначает арифметическое сложение, то булева функция <tex>f(A_1,A_2,...,A_n)</tex> принимает единичное значение на этом наборе. Если же на каком-либо наборе <tex>\sum_{i=1}^n A_i a_i \le T</tex>, то функция <tex>f(A_1,A_2,...,A_n)</tex> на этом наборе принимает нулевое значение. Функцию, представленную описанным способом, будем называть '''пороговой функцией'''.
+
{{Определение
 +
|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>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,...,a_n;T]</tex>.
Строка 24: Строка 28:
 
:<tex>[a_1,a_2,a_3,...,a_n;T]=[ka_1,ka_2,ka_3,...,ka_n;kT]</tex>,
 
:<tex>[a_1,a_2,a_3,...,a_n;T]=[ka_1,ka_2,ka_3,...,ka_n;kT]</tex>,
 
где k — натуральное число. Чтобы убедиться в этом достаточно записать
 
где k — натуральное число. Чтобы убедиться в этом достаточно записать
: <tex>ka_1 A_1+ka_2 A_2+...+ka_n A_n>kT</tex>
+
: <tex>ka_1 A_1+ka_2 A_2+...+ka_n A_n \ge kT</tex>
: <tex>ka_1 A_1+ka_2 A_2+...+ka_n A_n \le kT</tex>
+
: <tex>ka_1 A_1+ka_2 A_2+...+ka_n A_n < kT</tex>
 
и разделить обе части неравенства на <tex>k</tex>.
 
и разделить обе части неравенства на <tex>k</tex>.
  

Версия 22:05, 10 октября 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_{i=1}^n A_i a_i \ge T][/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]A_1 3+A_2 4+A_36\gt 5[/math].

Если [math]A_1=0;A_2=0;A_3=0, то 0\lt 5 и f=0[/math].
Если [math]A_1=0;A_2=0;A_3=1, то 6\gt 5 и f=1[/math].
Если [math]A_1=0;A_2=1;A_3=0, то 4\lt 5 и f=0[/math].
Если [math]A_1=0;A_2=1;A_3=1, то 10\gt 5 и f=1[/math].
Если [math]A_1=1;A_2=0;A_3=0, то 3\lt 5 и f=0[/math].
Если [math]A_1=1;A_2=0;A_3=1, то 9\gt 5 и f=1[/math].
Если [math]A_1=1;A_2=1;A_3=0, то 7\gt 5 и f=1[/math].
Если [math]A_1=1;A_2=1;A_3=1, то 13\gt 5 и 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]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].

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

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

При аргументах (0, 1) значение функции [math]XOR[/math] равно 1. Тогда, по определению пороговой функции выполняется неравенство [math]A_1 x+A_2 x\gt T[/math], подставляя значения аргументов, получаем [math]A_2\gt T[/math]. Аналогично, при аргументах (1, 0) получаем [math]A_1\gt T[/math]. Отсюда следует, что [math]A_1+A_2\gt T[/math]. Но это неравенстово не выполняется при аргументах (1, 1). Значит, функция [math]XOR[/math] непороговая.

Источники