![](/user_photo/2706_HbeT2.jpg)
4-
.pdf![](/html/2706/44/html_KNOEb38cwA.2l_1/htmlconvd-JBeGK11x1.jpg)
Монотонные функции Самодвойственные функции
Монотонные функции
IНабор (x1; x2; : : : ; xn) 2 Bn меньше или равен набору
(y1; y2; : : : ; yn) 2 Bn, (x1; x2; : : : ; xn) (y1; y2; : : : ; yn), если
x1 y1; x2 y2; : : : ; xn yn:
![](/html/2706/44/html_KNOEb38cwA.2l_1/htmlconvd-JBeGK12x1.jpg)
Монотонные функции Самодвойственные функции
Монотонные функции
IНабор (x1; x2; : : : ; xn) 2 Bn меньше или равен набору
(y1; y2; : : : ; yn) 2 Bn, (x1; x2; : : : ; xn) (y1; y2; : : : ; yn), если
x1 y1; x2 y2; : : : ; xn yn:
IФункция f : Bn ! B называется монотонной, если
(x1; : : : ; xn) (y1; : : : ; yn) =) f (x1; : : : ; xn) f (y1; : : : ; yn)
для всех (x1; x2; : : : ; xn); (y1; y2; : : : ; yn) 2 Bn.
![](/html/2706/44/html_KNOEb38cwA.2l_1/htmlconvd-JBeGK13x1.jpg)
Монотонные функции Самодвойственные функции
Примеры
I Функции 0, 1; x & y и x _ y монотонны.
![](/html/2706/44/html_KNOEb38cwA.2l_1/htmlconvd-JBeGK14x1.jpg)
Монотонные функции Самодвойственные функции
Примеры
IФункции 0, 1; x & y и x _ y монотонны.
IФункция f (x; y; z) = x + y + z не монотонна,
![](/html/2706/44/html_KNOEb38cwA.2l_1/htmlconvd-JBeGK15x1.jpg)
Монотонные функции Самодвойственные функции
Примеры
IФункции 0, 1; x & y и x _ y монотонны.
IФункция f (x; y; z) = x + y + z не монотонна, так как
(0; 1; 0) (1; 1; 0);
но 1 = f (0; 1; 0) > f (1; 1; 0) = 0:
![](/html/2706/44/html_KNOEb38cwA.2l_1/htmlconvd-JBeGK16x1.jpg)
Монотонные функции Самодвойственные функции
Суперпозиция монотонных функций
Теорема. Если f ; g1; g2; : : : ; gm монотонные функции, то функция
h(x1; : : : ; xn) = f (g1(x1; : : : ; xn); : : : ; gm(x1; : : : ; xn))
также является монотонной.
![](/html/2706/44/html_KNOEb38cwA.2l_1/htmlconvd-JBeGK17x1.jpg)
Монотонные функции Самодвойственные функции
Суперпозиция монотонных функций
Теорема. Если f ; g1; g2; : : : ; gm монотонные функции, то функция
h(x1; : : : ; xn) = f (g1(x1; : : : ; xn); : : : ; gm(x1; : : : ; xn))
также является монотонной.
Доказательство. Пусть ~x = (x1; : : : ; xn) ~y = (y1; : : : ; yn).
![](/html/2706/44/html_KNOEb38cwA.2l_1/htmlconvd-JBeGK18x1.jpg)
Монотонные функции Самодвойственные функции
Суперпозиция монотонных функций
Теорема. Если f ; g1; g2; : : : ; gm монотонные функции, то функция
h(x1; : : : ; xn) = f (g1(x1; : : : ; xn); : : : ; gm(x1; : : : ; xn))
также является монотонной.
Доказательство. Пусть ~x = (x1; : : : ; xn) ~y = (y1; : : : ; yn). Так как функции g1; : : : gm монотонны
(g1(~x); : : : ; gm(~x)) (g1(~y); : : : ; gm(~y)):
![](/html/2706/44/html_KNOEb38cwA.2l_1/htmlconvd-JBeGK19x1.jpg)
Монотонные функции Самодвойственные функции
Суперпозиция монотонных функций
Теорема. Если f ; g1; g2; : : : ; gm монотонные функции, то функция
h(x1; : : : ; xn) = f (g1(x1; : : : ; xn); : : : ; gm(x1; : : : ; xn))
также является монотонной.
Доказательство. Пусть ~x = (x1; : : : ; xn) ~y = (y1; : : : ; yn). Так как функции g1; : : : gm монотонны
(g1(~x); : : : ; gm(~x)) (g1(~y); : : : ; gm(~y)):
Так как функция f монтонна,
h(~x) = f (g1(~x); : : : ; gm(~x)) f (g1(~y); : : : ; gm(~y)) = h(~y).
![](/html/2706/44/html_KNOEb38cwA.2l_1/htmlconvd-JBeGK110x1.jpg)
Монотонные функции Самодвойственные функции
Простые импликанты монотонных функций
Теорема. Простые импликанты монотонных функций не содержат отрицаний.