Изменения
Нет описания правки
{{Определение
|definition =
Булева функция <tex>f(A_1,A_2,...,A_n)</tex> называется '''пороговой''', если ее можно представить в виде <tex>f(A_1,A_2,...,A_n) = [\sum\limits_{i=1}^n A_i a_i \ge geqslant T]</tex>, где <tex>a_i</tex> {{---}} '''вес''' аргумента <tex>A_i</tex>, а <tex>T</tex> {{---}} '''порог''' функции <tex>f</tex>; <tex>a_i, T \in R</tex>
}}
Согласно этой записи имеем
:<tex>a_1=3; a_2=4; a_3=6; T=5</tex>.
Все наборы значений аргументов <tex>A_1, A_2, A_3</tex>, на которых функция принимает единичное (либо нулевое) значение, можно получить из соотношения вида <tex>3A_1+4A_2+6A_3\ge5geqslant 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\ge5 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\ge5 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\ge5 geqslant 5 \Rightarrow f=1</tex>.:Если <tex>A_1=1,A_2=1,A_3=0</tex>, то <tex>7\ge5 geqslant 5 \Rightarrow f=1</tex>.:Если <tex>A_1=1,A_2=1,A_3=1</tex>, то <tex>13\ge5 geqslant 5 \Rightarrow f=1</tex>.
Таким образом, заданная функция принимает единичное значение на наборах <tex>001</tex>, <tex>011</tex>, <tex>101</tex>, <tex>110</tex>, <tex>111</tex>. Её [[Сокращенная и минимальная ДНФ|минимальная форма]] имеет вид
где k — положительное вещественное число.
|proof=Чтобы убедиться в этом достаточно записать
: <tex>ka_1 A_1+ka_2 A_2+...+ka_n A_n \ge geqslant kT</tex>
: <tex>ka_1 A_1+ka_2 A_2+...+ka_n A_n < kT</tex>
и разделить обе части неравенства на <tex>k</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\ge2 geqslant 2 \Rightarrow f=1</tex>.
Таблица значений совпадает с таблицей истинности функции <tex> \operatorname{AND} </tex>, следовательно <tex> \operatorname{AND} </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\ge1 geqslant 1 \Rightarrow f=1</tex>. :<tex>A_1=1,A_2=0</tex>, то <tex>1\ge1 geqslant 1 \Rightarrow f=1</tex>.:<tex>A_1=1,A_2=1</tex>, то <tex>2\ge1 geqslant 1 \Rightarrow f=1</tex>.
Таблица значений совпадает с таблицей истинности функции <tex> \operatorname{OR} </tex>, следовательно <tex> \operatorname{OR} </tex> {{---}} пороговая функция.
Функция <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 \ge 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 \ge geqslant T</tex>, подставляя в которое значения соответствующих аргументов, получаем <tex>A_1 \ge geqslant T, A_2 \ge geqslant T</tex>. Отсюда следует, что <tex>A_1>0, A_2>0</tex> и <tex>A_1+A_2 \ge geqslant 2T</tex>. При аргументах <tex>(1, 1)</tex> значение функции <tex> \operatorname{XOR} </tex> равно 0, следовательно неравенство <tex>A_1 x_1+A_2 x_2 \ge geqslant T</tex> выполняться не должно, то есть <tex>A_1+A_2 < T</tex>. Но неравенства <tex>A_1+A_2 \ge geqslant 2T</tex> и <tex>A_1+A_2 < T</tex> при положительных <tex>A_1,A_2</tex> и <tex>T</tex> одновременно выполняться не могут. Получили противоречие, следовательно, функция <tex> \operatorname{XOR} </tex> {{---}} непороговая.
}}
