Изменения

Предположим, что [[ДНФ]] <tex>C</tex> распознает язык <tex>\oplus</tex>. Каждый [[ДНФ|конъюнкт]] <tex>C</tex> зависит от всех входных значений. В противном случае допустим, что некоторый конъюнкт <tex>C</tex> не зависит от значения <tex>x_i</tex>. Тогда можно подобрать такие входные значения, при которых значение этого конъюнкта (а значит и <tex>C</tex>) будет равно <tex>1</tex> и не зависить от значения <tex>x_i</tex>. Однако при различных значениях <tex>x_i</tex> значение <tex>C</tex> должно изменяться, так как <tex>C</tex> распознает <tex>\oplus</tex>. Значит, предположение неверно, поэтому каждый конъюнкт <tex>C</tex> зависит от всех входных значений. Пусть <tex>C</tex> состоит из конъюнктов <tex>A_1</tex>, ..., <tex>A_t</tex>. Тогда для случайного входа <tex>x \sim \left\{ 0, 1 \right\} ^n</tex> верно, что <tex>P\left[C(x)=1\right] \le \sum\limits^{t}_{i=1} {P\left[ A_i(x) = 1 \right]} \le t\cdot2^{-n}</tex>. Поскольку <tex>P\left[ x \in \oplus(x) = 1\right] = \frac{1}{2}</tex>, то <tex>t \ge 2^{n - 1}</tex>. Аналогичный результат можно получить и для [[КНФ]].

Пусть функция <tex>f(x_1, ...,x_n)</tex> представима в виде <tex>k</tex>-[[ДНФ]], а <tex>p~-</tex> случайное назначение <tex>t</tex> случайно выбранным аргументам случайных значений. Тогда при <tex>s \ge 2</tex> верно, что: <br><tex>P[f|_p</tex> не представима в виде <tex>s</tex>-[[КНФ]]<tex>]\le\left(\frac{(n - t)k^{10}}{n}\right) ^ {s/2}</tex>, где <tex>f|_p</tex> получено при подстановке в функцию <tex>f</tex> значений из <tex>p</tex>.