Задача Дана булевая функция f x
 Скачать 77.06 Kb.
|
|
Задача: Дана булевая функция f(x 1 , . . . x n ) , причем она существенно зависит от всех своих переменных. Тогда ?k:0 ? k ? n ? такие номера n 1 , . . . ,n l , что вместо переменных под этими номерами можно подставить 0 или 1 так, чтбы функция существенно зависела от k переменных. Доказательство: Докажем по индукции следующее: найдутся n ? k мест, что в них можно поставить 0 или 1 так, что полученная функция будет зависеть от остальных k переменных. База: для k = 0 всј верно. Шаг: пусть доказано для k. Докажем для k+1. Пусть это не так. Так как для k доказано, то найдутся такие n ? k мест, в которые можно по- ставить 0 или 1 так, что функция будет существенно зависеть от k пере- менных (пусть это функция f(? 1 , . . . ,? n?k , x n?k+1 , . . . ,x n ) ). Без ограни- чения общности представим, что все эти переменные стоят на последних k местах и назовем эту функцию g. Возьмем и уберет фиксированное значение у n ? k-й переменной (полученную функцию назовем h). По предположению одна из переменных у полученной функции фиктивная. Докажем, что это n ? k-я переменная, а другие существенные. Это понятно, ведь другие переменные были существенными в предыдущей функции g, значит существовала такая расстановка 0 и 1 на местах дру- гих переменных, что значение функции зависела от n?k+i, где 1 ? i ? k. Этот же набор возможен в h, значит она тоже существенна зависит от этих переменных, а по предположению k + 1 существенных переменных мы получить не можем, значит n ? k-я - фиктивная для h, значит ее значение не зависит от n ? k-й переменной. Аналогичные рассуждения можно провести для остальных несущественных для g переменных. Мо- жем ли мы утверждать, что какая-то из них фиктивная для f? Будем доказывать, что первая переменная - фиктивная для f. То есть мы должны доказать, что для любых ? 2 , . . . ,? n f (0,? 2 , . . . ,? n ) = f (1,? 2 , . . . ,? n ) . Пойдем по следующему алгоритму от n?k до 1: если ? j = ? j , уменьшим j на 1, иначе уберем фиксированное значение с этой пере- менной и докажем, что эта переменная фиктивная. В самом деле, осталь- ные k переменных являются существенными (аналогичные рассужде- ния), а по предположению индукции тогда оставшаяся переменная явля- ется фиктивной, поэтому f(? 1 , . . . ,? j?1 ? j ,? j+1 , . . . ,? n?k ,x n?k+1 . . . x n ) = f (? 1 , . . . ,? j?1 ? j ,? j+1 , . . . ,? n?k ,x n?k+1 . . . x n ) , в частности это будет верно для той комбинации значений переменных, при которых значение функ- ции будет зависеть от значения конкретной существенной переменной. Итого мы получим f(0,? 2 , . . . ,? n ) = f (1,? 2 , . . . ,? n ) , то есть противоречие с тем, что фиктивных переменных нет. 1 |