100
правок
Изменения
Нет описания правки
<tex>\oplus~-</tex> [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками|язык]] над [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками|алфавитом]] <tex>\left\{0, 1\right\}</tex>, состоящий из [[Основные определения: алфавит, слово, язык, конкатенация, свободный моноид слов; операции над языками|слов]], содержащих нечетное число <tex>1.</tex>
}}
Предположим, что [[ДНФ]] <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^{t}_{i=1} {P\left[ A_i(x) = 1 \right]} \le t\cdot2^{-n}</tex>.
===Теорема===
