Дискуссионный математический форумМатематический форум

Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

Часовой пояс: UTC + 4 часа [ Летнее время ]


Теорема Поста и классы

Теорема Поста и классы


В силу теоремы о представлении любой булевой функции дизъюнктивной или конъюнктивной нормальной формой стандартный базис [math]\{\lor,\cdot,\overline{\phantom{A}}\}[/math] является полным множеством. Поскольку, согласно законам де Моргана, можно выразить конъюнкцию через дизъюнкцию и отрицание, равно как и дизъюнкцию можно выразить через конъюнкцию и отрицание, то при удалении из стандартного базиса одной функции, дизъюнкции или конъюнкции, при сохранении отрицания, получим снова полное множество.


Прежде чем рассматривать другие примеры полных множеств, установим один важный факт.


Теорема 6.3. Пусть [math]F[/math] и [math]G[/math] — некоторые множества булевых функций, причем [math]F[/math] — полное множество. Тогда, если каждая функция из [math]F[/math] может быть представлена некоторой формулой над множеством [math]G[/math], то [math]G[/math] — полное множество.


Из условия теоремы следует, что каждая функция [math]f\in F[/math] может быть представлена некоторой формулой [math]\Psi[/math] над [math]G[/math], т.е.


[math]f(x_1,\ldots,x_n)=\Psi(x_1,\ldots,x_n).[/math]
(6.17)

Докажем, что всякая формула над [math]F[/math] эквивалентна некоторой формуле над [math]G[/math], т.е. всякая функция [math]\varphi[/math], представляемая формулой над [math]F[/math], может быть представлена также и некоторой формулой над [math]G[/math]. Доказательство проведем по такой схеме: сначала убедимся в справедливости утверждения для "базисных" формул, т.е. для переменных и констант из [math]F[/math], а затем в предположении, что оно уже доказано для формул [math]\Phi_1,\ldots,\Phi_n[/math], где [math]n\geqslant1[/math], докажем его для любой формулы вида [math]f(\Phi_1,\ldots,\Phi_n)[/math], где [math]f\in F[/math]. Такой метод доказательства называют доказательством индукцией по построению формулы.


Пусть [math]\varphi[/math] — какая-то формула над [math]F[/math]. Если [math]\varphi=x[/math], где [math]x[/math] — булево переменное из множества [math]X[/math], то, поскольку каждое переменное есть, по определению, и формула над [math]G[/math], функция [math]\varphi[/math] представляется формулой над [math]G[/math].


Если [math]\varphi[/math] есть константа из [math]F[/math], то представляющая [math]\varphi[/math] формула над [math]G[/math] существует ввиду (6.17).


Рассмотрим формулу над [math]F[/math] вида [math]f(\Phi_1,\ldots,\Phi_n)[/math], где [math]n>0,~f\in F[/math], а [math]\Phi_1,\ldots,\Phi_n[/math] — формулы над [math]F[/math]. Согласно предположению индукции, каждая формула [math]\Phi_1,~i=\overline{1,n}[/math], может быть заменена эквивалентной ей формулой [math]\Theta_i[/math] над [math]G[/math] (т.е. имеет место тождество [math]\Phi_1=\Theta_i[/math] над [math]F\cup G[/math]). Тогда, используя правила эквивалентных преобразований формул (см. теорему 6.1), получим тождество


[math]f(\Phi_1,\ldots,\Phi_n)= f(\Theta_1,\ldots,\Theta_n),[/math]
а в соответствии с (6.17) будем иметь
[math]f(\Theta_1,\ldots,\Theta_n)= \Psi(\Theta_1,\ldots,\Theta_n).[/math]
(6.18)

Правая часть тождества (6.18) и есть формула над [math]G[/math], эквивалентная исходной формуле над [math]F[/math].


Поскольку в силу полноты множества [math]F[/math] любая булева функция может быть представлена некоторой формулой над [math]F[/math], а любая такая формула, как мы только что доказали, эквивалентна некоторой формуле над [math]G[/math], то любая булева функция может быть представлена некоторой формулой над [math]G[/math], что и доказывает полноту множества [math]G[/math].


Пример 6.17. Рассмотрим базис Жегалкина [math]\{\oplus,\cdot,1\}[/math]. Чтобы доказать полноту этого множества, заметим, что


[math]x\lor y=x\cdot y\oplus x\oplus y,\qquad \overline{x}=x\oplus1,[/math]

т.е. каждый элемент стандартного базиса может быть представлен формулой над базисом Жегалкина. Отсюда и следует (ввиду полноты стандартного базиса и теоремы 6.3) полнота базиса Жегалкина.



Любую формулу над базисом Жегалкина называют полиномом Жегалкина. Полином Жегалкина от [math]n[/math] переменных может быть записан в виде


[math]P(x_1,\ldots,x_n)= \bigoplus\limits_{\{i_1,i_2,\ldots,i_m \}\subseteq\{1,2,\ldots,n\}} (\operatorname{mod}2)a_{i_1i_2\ldots i_m} x_{i_1}x_{i_2}\ldots x_{i_m},[/math]

где коэффициенты полинома [math]a_{i_1i_2\ldots i_m}\in\{0;1\}[/math] индексированы всеми возможными подмножествами множества [math]\{1,2,\ldots,n\}[/math] (коэффициент [math]a_0[/math] соответствует пустому множеству). В частности, при [math]n=3[/math] будем иметь:


[math]a_{123}x_1x_2x_3\oplus a_{12}x_1x_2\oplus a_{13}x_1x_3\oplus a_{23}x_2x_3\oplus a_1x_1\oplus a_2x_2\oplus a_3x_3\oplus a_0[/math]
(6.19)

(общий вид полинома Жегалкина от трех переменных). Формула вида

[math]\bigoplus\limits_{i=1}^{n}(\operatorname{mod}2)a_ix_i\oplus a_0[/math]
(6.20)

называется полиномом Жегалкина первой степени от переменных. В таком полиноме отсутствуют "нелинейные" слагаемые, т.е. все коэффициенты, индексированные более чем одноэлементными подмножествами, равны 0 (и вместе с ними равны 0 все слагаемые, содержащие конъюнкции переменных).

Можно доказать следующее достаточно простое, но важное утверждение.


Теорема 6.4. Полином Жегалкина для любой булевой функции определен однозначно.


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


Пример 6.18. Пусть вектор значений булевой функции [math]f[/math] равен [math]11001011[/math]. Найдем полином Жегалкина, представляющий [math]f[/math]. Поскольку размерность вектора значений [math]f[/math] равна [math]2^3=8[/math], то [math]f[/math] задана как функция от трех переменных. Тогда она представляется некоторым полиномом Жегалкина третьей степени, общий вид которого дает формула (6.19). Наша задача — найти такие значения коэффициентов этого полинома, при которых он представляет функцию [math]f[/math]. Ясно, что значение функции [math]f[/math] на наборе [math]000[/math] равно коэффициенту [math]a_0[/math] в формуле (6.19). Но, согласно заданному вектору значений, оно равно 1. Следовательно, [math]a_0=1[/math]. Далее,


[math]f(0,0,1)=a_3\oplus a_0=a_3\oplus 1=1,[/math]

откуда, решая уравнение относительно [math]a_3[/math] в поле [math]\mathbb{Z}_2[/math], получим [math]a_3=0[/math];


[math]f(0,1,0)=a_2\oplus1=0[/math], то есть [math]a_2=1[/math] и [math]f(1,0,0)= a_1\oplus 1=1[/math] и [math]a_1=0[/math].

Чтобы найти коэффициенты [math]a_{12},\,a_{13}[/math] и [math]a_{23}[/math], нужно рассмотреть значения функции на наборах [math]110,\,101[/math] и [math]011[/math] соответственно. Так, для первого набора получим


[math]f(1,1,0)=a_{12}x_1x_2\oplus a_1x_1\oplus a_2x_2\oplus a_0= a_{12}\oplus a_{2}\oplus a_0=a_{12}\oplus1\oplus1=a_{12}[/math]

(сумма по модулю 2 любого четного числа равных слагаемых равна 0). Поскольку в то же время [math]f(1,1,0)=1[/math], то [math]a_0=1[/math]. Аналогично [math]f(1,0,1)=a_{13}\oplus a_0=0[/math], откуда [math]a_{13}=1[/math]; [math]f(0,1,1)=a_{23}\oplus a_2\oplus a_0=0[/math], и, так как [math]a_2=a_0=1,~a_{23}=0[/math]. Наконец,


[math]f(1,1,1)=a_{123}\oplus a_{12}\oplus a_{13}\oplus a_2\oplus a_0=a_{123}=1.[/math]

Итак, окончательно имеем [math]f=x_1x_2x_3\oplus x_1x_2\oplus x_1x_3\oplus x_2\oplus 1[/math].




Как видно из примера 6.18, суть метода неопределенных коэффициентов состоит в следующем. Записывая полином Жегалкина сначала в общем виде, с неопределенными коэффициентами, мы выражаем значение полинома на фиксированных наборах через коэффициенты и приравниваем его заданному значению функции. Начинаем с нулевого набора и находим коэффициент [math]a_0[/math], равный значению заданной функции на нулевом наборе. Зная его, из рассмотрения значений функции на наборах, содержащих в точности одну единицу, находим коэффициенты а,- при "одиночных" переменных (коэффициенты "линейной части" полинома). Зная их, из рассмотрения значений функции на наборах, содержащих в точности две единицы, находим коэффициенты при конъюнкциях двух переменных и т.д. При этом выполняются вычисления и решаются простейшие линейные уравнения в поле вычетов по модулю 2.


Пример 6.19. а. Рассмотрим множество [math]\{\mid\}[/math], состоящее из единственной функции (штриха Шеффера). Полнота этого множества следует из легко проверяемых тождеств


[math]x\cdot y=(x|y)|(x|y),\qquad \overline{x}=(x|x).[/math]

б. Полнота множества [math]\{\downarrow\}[/math], единственным элементом которого является стрелка Пирса, проверяется аналогично.


Теперь мы сформулируем и докажем критерий (необходимое и достаточное условие) полноты для произвольного множества булевых функций. Для этого нам потребуется сначала рассмотреть некоторые специальные множества функций.


Определение 6.8. Функцию [math]f[/math] называют функцией, сохраняющей константу 0 (соответственно константу 1), если [math]f(\widetilde{0})=0[/math] (соответственно: [math]f(\widetilde{1})=1[/math], где [math]\widetilde{0}[/math] — нулевой, а [math]\widetilde{1}[/math] — единичный наборы значений переменных функции [math]f[/math].


Например, мажоритарная функция является функцией, сохраняющей и константу 0, и константу 1. Отрицание не сохраняет ни 0, ни 1, а эквивалентность сохраняет 1, но не сохраняет 0. Множество всех функций, сохраняющих константу 0 (константу 1), обозначается [math]T_0[/math] (соответственно [math]T_1[/math]).


Наборы [math]\widetilde{\alpha}[/math] и [math]\overline{\widetilde{\alpha}}[/math] из булева куба [math]\mathbb{B}^n=\{0;1\}^n[/math] (для произвольного фиксированного [math]n[/math]) будем называть взаимно противоположными, говоря при этом также, что набор [math]\overline{\widetilde{\alpha}}[/math] есть инверсия (или отрицание) набора [math]\widetilde{\alpha}[/math] (в силу единственности дополнения любого элемента булевой алгебры набор [math]\widetilde{\alpha}[/math] будет, очевидно, инверсией набора [math]\overline{\widetilde{\alpha}}[/math]).


Определение 6.9. Функцию [math]g\in\mathcal{P}_{2,n}[/math] называют двойственной к функции [math]f\in\mathcal{P}_{2,n}[/math], если для всякого [math]\widetilde{\alpha}\in \{0;1\}^n[/math] имеет место [math]g(\widetilde{\alpha})= \overline{f} (\overline{\widetilde{\alpha}})[/math].


Полагаем также, что константа 0 является двойственной к константе 1 и наоборот.


Пример 6.20. а. Стрелка Пирса есть функция, двойственная к штриху Шеффера, так как


[math]x\downarrow y=\overline{x\lor y}= \overline{\overline{\overline{x}\cdot \overline{y}}}= \overline{\overline{x}|\overline{y}}.[/math]

б. Сумма по модулю 2 двойственна к эквивалентности, так как [math]x\sim y=\overline{x\oplus y}=\overline{\overline{x}\oplus \overline{y}}[/math].


Эти две функции являются и отрицанием друг друга, но неверно в общем случае, что функция д, будучи отрицанием функции [math]f[/math], двойственна к [math]f:[/math] штрих Шеффера не есть функция, двойственная к конъюнкции, а стрелка Пирса не есть функция, двойственная к дизъюнкции, но конъюнкция двойственна к дизъюнкции и наоборот, а стрелка Пирса двойственна к штриху Шеффера и наоборот.




В общем случае в силу уже упомянутого свойства единственности дополнения в булевой алгебре функция [math]h[/math], двойственная к функции [math]g[/math], которая двойственна к [math]f[/math], равна [math]f[/math].


Определение 6.10. Функцию [math]f\in\mathcal{P}_{2,n}[/math] называют самодвойственной, если она двойственна к себе самой, т.е.


[math]\bigl(\forall\widetilde{\alpha}\in\{0;1\}^n\bigr)\bigl(f(\widetilde{\alpha})= \overline{f}(\overline{\widetilde{\alpha}})\bigr)[/math], или [math]\bigl(\forall \widetilde{\alpha}\in\{0;1\}^n\bigr)\bigl(f(\overline{\widetilde{\alpha}})= \overline{f}(\widetilde{\alpha})\bigr).[/math]

Таким образом, функция самодвойственна тогда и только тогда, когда на взаимно противоположных наборах она принимает взаимно противоположные значения. Следовательно, для того чтобы убедиться в несамодвойственности заданной функции [math]f[/math], достаточно найти хотя бы одну пару взаимно противоположных наборов [math]\widetilde{\alpha}[/math] и [math]\overline{\widetilde{\alpha}}[/math], таких, что значения функции на них совпадают, т.е. [math]f(\widetilde{\alpha})=f(\overline{\widetilde{\alpha}})[/math]. Так, мажоритарная функция является самодвойственной, а эквивалентность — нет, поскольку при [math]\widetilde{\alpha}=(0;0)[/math] имеем [math]0\sim0=1[/math] и [math]1\sim1=1[/math].


Множество всех самодвойственных функций (при всех [math]n\geqslant1[/math]) обозначим [math]S[/math].


Определение 6.11. Функцию [math]f\in\mathcal{P}_{2,n}[/math] называют монотонной, если для любых наборов [math]\widetilde{\alpha},\widetilde{\beta}\in\mathcal{B}^n[/math], таких, что [math]\widetilde{\alpha}\leqslant \widetilde{\beta}[/math], имеет место [math]f(\widetilde{\alpha})\leqslant f(\widetilde{\beta})[/math].


Другими словами, функция монотонна тогда и только тогда, когда для любого набора [math]\widetilde{\alpha}[/math] имеет место следующее свойство: если значение функции на наборе [math]\widetilde{\alpha}[/math] равно 1, то оно равно 1 и на всех наборах, строго больших (по отношению булева порядка на [math]\mathbb{B}^n[/math]) набора [math]\widetilde{\alpha}[/math]. Любой минимальный (относительно того же порядка) набор [math]\widetilde{\alpha}[/math], для которого значение [math]f(\widetilde{\alpha})[/math] монотонной функции [math]f[/math] равно 1, называют нижней единицей функции [math]f[/math]. Очевидно, что вектор значений монотонной булевой функции полностью определяется множеством ее нижних единиц*. Мажоритарная функция монотонна, и множество ее нижних единиц есть [math]\{011,101,110\}[/math]. Штрих Шеффера — немонотонная функция, так как [math]00<11[/math], но [math]0|0=1[/math], а [math]1|1=0[/math]. Множество всех монотонных функций принято обозначать через [math]M[/math].


*Нетрудно понять, что множество нижних единиц монотонной функции [math]f[/math] есть множество всех минимальных элементов множества [math]C_f^1[/math] — конституент единицы функции [math]f[/math].


Определение 6.12. Функцию [math]f\in\mathcal{P}_{2,n}[/math] называют линейной, если она может быть представлена полиномом Жегалкина первой степени от п переменных, т.е. формулой вида (6.20).


Множество всех линейных функций принято обозначать через [math]L[/math].


Любая булева константа и любая проектирующая функция х являются линейными функциями. Такова, разумеется, сумма по модулю 2. Отрицание также линейно, ибо [math]\overline{x}= x\oplus1[/math]. Конъюнкция и дизъюнкция не являются линейными функциями, так как не могут быть представлены полиномом Жегалкина первой степени (см. теорему 6.4).


Определение 6.13. Множества функций [math]T_0,\,T_1,\,S,\,M,\,L[/math] называются классами Поста.


Замечание 6.9. Каждый класс Поста состоит из функций с соответствующим свойством для любого числа переменных. Можно доказать также, что если функция [math]f[/math] принадлежит какому-то классу Поста [math]C[/math], то и любая функция, равная функции [math]f[/math], принадлежит этому же классу. Другими словами, добавление или удаление фиктивных переменных не выводит за пределы любого из классов Поста.


Полезно еще заметить, что любая проектирующая функция х принадлежит одновременно всем пяти классам Поста. Действительно, если [math]f(x)=x[/math], то [math]f(0)=0[/math] и [math]f(1)=1[/math], то есть [math]f\in T_0\cap T_1[/math]. Отсюда же вытекает и самодвойственность функции [math]x[/math]. Монотонность следует из того, что [math]0<1[/math] и [math]f(0)=0<f(1)=1[/math]. Линейность очевидна.


В то же время существуют функции, не принадлежащие ни одному из классов Поста. Таков, например, штрих Шеффера. Все свойства, кроме нелинейности, следуют прямо из таблицы этой функции. Нелинейность же доказывается выводом полинома Жегалкина для штриха Шеффера: [math]x|y=\overline{x\cdot y}=x\cdot y\oplus1[/math], что не есть полином Жегалкина первой степени.


Фундаментальным свойством каждого класса Поста является его замкнутость (в смысле определения 6.3). Это означает для любого из классов Поста [math]C[/math], что всякая суперпозиция над [math]C[/math] снова есть элемент [math]C[/math].




Теорема о замкнутости классов Поста


Теорема 6.5. Каждый класс Поста замкнут.


Нужно для каждого класса Поста [math]C\in\{T_0,T_1,S,M,L\}[/math] доказать, что замыкание [math][ C][/math] множества булевых функций [math]C[/math] совпадает с [math]C[/math]. Пусть [math]f(g_1,\ldots,g_n)[/math] — какая-то суперпозиция над [math]C[/math]. Обозначим ее через [math]\varphi[/math]. Без ограничения общности можно считать, что все функции [math]f,g_1,\ldots, g_n\in \mathcal{P}_{2,n}[/math] (для некоторого [math]n[/math]).


Рассуждаем, используя индукцию по определению суперпозиции. Если для каждого [math]i=\overline{1,n}[/math] функция [math]g_i=x_i[/math], где [math]x_i[/math] — переменное, то [math]\varphi=f(x_1,\ldots,x_n)\in C[/math]. Предположим, что в суперпозиции [math]\varphi[/math] все функции [math]g_i[/math] есть элементы класса Поста [math]C[/math] (в частности, это может быть и соответствующая проектирующая функция, которая ввиду замечания 6.9 принадлежит всем классам Поста). Докажем, что и [math]\varphi=f(g_1,\ldots,g_n)\in C[/math].


1. Если [math]C=T_0[/math], то [math]\varphi(\widetilde{0})= f(g_1(\widetilde{0}),\ldots, g_2(\widetilde{0}))= f(0,\ldots,0)=0[/math], так как [math]f,g_1,\ldots,g_n\in T_0[/math]. Следовательно, [math]\varphi\in T_0[/math].


2. При [math]C=T_1[/math] рассуждаем точно так же.


3. Пусть [math]C=S[/math]. Фиксируем произвольно набор [math]\widetilde{\alpha}\in \{0;1\}^n[/math]. Вычислим (используя само двойственность всех функций):


[math]\varphi\bigl(\overline{\widetilde{\alpha}}\bigr)= f\bigl(g_1(\overline{\widetilde{\alpha}}), \ldots, g_2(\overline{\widetilde{\alpha}})\bigr)= f\bigl(\overline{g_1}(\widetilde{\alpha}),\ldots, \overline{g_n}(\widetilde{\alpha})\bigr)= \overline{f}\bigl(g_1(\widetilde{\alpha}), \ldots g_n(\widetilde{\alpha})\bigr)= \overline{\varphi}(\widetilde{\alpha}).[/math]

Следовательно, [math]\varphi\in S[/math].


4. [math]C=M[/math]. Берем произвольно наборы [math]\widetilde{\alpha}[/math] и [math]\widetilde{\beta}[/math] так, что [math]\widetilde{\alpha}\leqslant \widetilde{\beta}[/math]. Докажем, что [math]\varphi\in M[/math]. Имеем


[math]\varphi(\widetilde{\alpha})= f\bigl(g_1(\widetilde{\alpha}), \ldots g_n(\widetilde{\alpha}) \bigr)\leqslant f\bigl(g_1(\widetilde{\beta}), \ldots g_n(\widetilde{\beta})\bigr)= \varphi(\widetilde{\beta}).[/math]

так как все функции [math]g_i,~i=\overline{1,n}[/math], монотонны и тем самым вектор [math](g_1(\widetilde{\alpha}), \ldots g_n(\widetilde{\alpha}))[/math] не больше вектора [math](g_1(\widetilde{\beta}), \ldots g_n(\widetilde{\beta}))[/math], а функция [math]f[/math] также монотонна. Тогда ясно, что [math]\varphi\in M[/math].


5. Если же [math]C=L[/math], то очевидно, что при подстановке в линейную функцию (полином Жегалкина первой степени) вместо ее переменных произвольных линейных функций получится снова линейная функция. Итак, мы доказали замкнутость каждого класса Поста.




Докажем теперь теорему, характеризующую одно важное свойство немонотонных функций.


Теорема 6.6. Если функция [math]f[/math] не является монотонной, т.е. [math]f\in M[/math], то найдутся два таких набора [math]\widetilde{\alpha},\widetilde{\beta}[/math], что


[math]\begin{aligned}\widetilde{\alpha}&= (\alpha_1,\ldots, \alpha_{i-1},0, \alpha_{i+1},\ldots, \alpha_n),\\ \widetilde{\beta}&= (\alpha_1,\ldots, \alpha_{i-1},1, \alpha_{i+1},\ldots, \alpha_n), \end{aligned}[/math]

и [math]f(\widetilde{\alpha})=1,~f(\widetilde{\beta})=0[/math], т.е. эти два набора различаются значениями в точности одной компоненты, а значение функции равно О на большем наборе и равно 1 на меньшем.


Так как функция [math]f[/math] не является монотонной, то найдутся такие два набора [math]\widetilde{\gamma}[/math] и [math]\widetilde{\delta}[/math], что [math]\widetilde{\gamma}<\widetilde{\delta}[/math], но [math]f(\widetilde{\gamma})=1,~ f(\widetilde{\delta})=0[/math]. Строгое неравенство [math]\widetilde{\gamma}< \widetilde{\delta}[/math] означает, что найдутся такие номера (не меньше одного) [math]1\leqslant i_1<i_2<\ldots< i_k\leqslant n[/math], что


[math]\begin{aligned}\widetilde{\gamma}&=\bigl(\gamma_1,\ldots, \gamma_{i_1-1}, 0, \gamma_{i_1+1},\ldots, \gamma_{i_2-1},0,\ldots, \gamma_{i_2+1},\ldots, \gamma_{i_k-1},0, \gamma_{i_k+1},\ldots, \gamma_n \bigr),\\[2pt] \widetilde{\delta}&=\bigl(\gamma_1,\ldots, \gamma_{i_1-1}, 1, \gamma_{i_1+1},\ldots, \gamma_{i_2-1},1,\ldots, \gamma_{i_2+1},\ldots, \gamma_{i_k-1},1, \gamma_{i_k+1},\ldots, \gamma_n \bigr).\end{aligned}[/math]

т.е. все компоненты наборов, кроме выделенных, с номерами [math]i_1,i_2,\ldots,i_k[/math] соответственно совпадают, а все компоненты с выделенными номерами у меньшего набора равны 0, а у большего равны 1. Построим монотонно возрастающую последовательность наборов


[math]\widetilde{\gamma}=\widetilde{\gamma}_0<\widetilde{\gamma}_1<\widetilde{\gamma}_2<\ldots <\widetilde{\gamma}_k=\widetilde{\delta}.[/math]

так что для каждого [math]s\in\{1,2,\ldots,k\}[/math] набор [math]\widetilde{\gamma}_s[/math] получается из набора [math]\widetilde{\gamma}_{s-1}[/math] заменой нулевого значения компоненты с номером [math]i_s[/math] единичным. Поскольку [math]f(\widetilde{\gamma})=1[/math], а [math]f(\widetilde{\delta})=0[/math], то обязательно найдется такое [math]s\in\{1,2,\ldots,k\}[/math], что [math]f(\widetilde{\gamma}_{s-1})=1[/math], а [math]f(\widetilde{\gamma}_s)=0[/math] (на наборе [math]\widetilde{\gamma}_{s-1}[/math] значение функции еще равно 1, а на наборе [math]\widetilde{\gamma}_{s}[/math] оно уже равно 0). Полагая [math]\widetilde{\alpha}= \widetilde{\gamma}_{s-1}[/math] и [math]\widetilde{\beta}= \widetilde{\gamma}_{s}[/math] получим доказываемое.


Часовой пояс: UTC + 4 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2016 MathHelpPlanet.com. All rights reserved