Теорема Жегалкина

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 22:05, 14 мая 2016.
TemplateTheoremIcon.svg Теорема Теорема Жегалкина

Любая булева функция может быть однозначно представлена в виде АНФ (полинома Жегалкина).

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


Для функции заданной таблицей истиности, найдем АНФ:

000 0
001 1
010 1
011 0
100 1
101 0
110 1
111 0

Нахождение вида АНФ

1 способ - СДНФ

СДНФ булевой функции:

;

просто заменим на .

2 способ - Метод неопределенных коэффициентов

Метод неопределенных коэффициентов дает АНФ:

;

Решение составляемой системы уравнений единственна (по теореме Жегалкина), что и дает, в итоге, однозначный вид полинома.

3 способ - Метод сумм

Таким образом:

где - грань.

TemplateExampleIcon.svg Пример Пример:

Возьмем грань в 7-ми мерном пространстве

;

.


TemplateDifinitionIcon.svg Определение «Определение - Характеристическая сумма»

Если - это булева функция от переменных, - некоторое множество, то характеристическая ("проверочная") сумма:

где - сужение функции на множество

Ссылки

  1. "СДНФ" материал из Википедии — свободной энциклопедии
  2. "СКНФ" материал из Википедии — свободной энциклопедии
  3. "АНФ" материал из Википедии — свободной энциклопедии
  4. Полином "Жегалкина" материал из Википедии — свободной энциклопедии
  5. "Булева функция" материал из Википедии — свободной энциклопедии
  6. "Метод неопределенных коэффициентов" материал из Википедии — свободной энциклопедии
  7. Метод неопределенных коэффициентов и его универсальность