Пусть $% f(x_{1}, x_{2}, \dots, x_{n}) $% - $%n$%-местная булева функция (то есть $% f: \{0, 1\}^{n} \rightarrow \{0, 1\}$%) и $% x^{\sigma} = x$%, если $% \sigma = 1$%, и $% x^{\sigma} = \overline{x} $%, если $%\sigma = 0$%.

Требуется доказать следующую теорему о дизъюнктивном разложении булевой функции:

Любую $%n$%-местную булеву функцию $%f(x_{1}, x_{2}, \dots, x_{n})$% можно представить в виде формулы $$ f(x_{1}, x_{2}, \dots, x_{n}) = \bigvee_{ \langle \sigma_{1}, \sigma_{2}, \dots, \sigma_{s} \rangle \in \{0, 1\}^{s}} x_{i_{1}}^{\sigma_{1}} x_{i_{2}}^{\sigma_{2}} \dots x_{i_{s}}^{\sigma_{s}} f \left( x_{1}, x_{2}, \dots, x_{i_{1} - 1}, \sigma_{1}, \dots, x_{i_{s} - 1}, \sigma_{s}, x_{i_{s} + 1}, \dots, x_{n} \right) .$$

задан 10 Дек '18 0:15

1

Тут сами формулы дольше писать, чем доказывать :) Тем более, что в таком виде разложение мало кому может потребоваться.

Доказательство простое словесное. Фиксируем значения "иксов". Дизъюнктивные члены, равные нулю, можно не рассматривать. Не ноль будет только при условии, когда x^s=1, что равносильно s=x. Тогда член дизъюнкции только один, где "сигмы" равны "иксам". Тогда сомножители в начале равны 1, и остаётся значение f на том же наборе, что и слева.

(10 Дек '18 1:12) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×170
×99

задан
10 Дек '18 0:15

показан
293 раза

обновлен
10 Дек '18 1:12

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru