1.4 Утверждение о представлении двоичной функции в виде полинома Жегалкина .

Для любой булевой функции существует представление в виде полинома Жегалкина и это представление единственно.

Доказательство:

Пример 1:

x1	x2	x3
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	0

Первая часть теоремы следует из теоремы о представлении булевой функции в виде СДНФ. А именно рассмотрим для булевой функции ее СДНФ. Далее операцию выразим через операцию по правилу Де Моргана .

После чего операцию выразим через операцию и приведем полученную формулу к нормальному виду полинома Жегалкина раскрыв скобки в полученном выражении, используя дистрибутивность конъюнкции по отношению к сумме по модулю два. Для функции из примера1 СДНФ имеет вид :

Покажем, что полученный полином единственен с точностью до перестановки слагаемых и множителей в слагаемых полинома.

Допустим противное : , которая имеет два различных полинома Жегалкина:

Из этих равенств следует,что

прибавим к обеим частям равенства :

В силу того, что и различные полиномы Жегалкина, либо в есть слагаемое, которого нет в , либо наоборот. Поэтому приведенный полином отличен по форме от нуля , т.е. в этом полиноме присутствуют слагаемые, не тождественно равные нулю, и полином тождественно равен константе ноль : .

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

Упражнение: найдите полином Жегалкина следующих функций :

1) 4)

2) 5)

3) 6)

Упражнение

Покажите справедливость формулы для любой двоичной функции f справедливо разложение

л

Т.е в формуле представления функции в виде СДНФ можно заменить логическое суммирование на суммирование по модуля 2.

Определение

Пусть – конечное множество. Отношением на данном множестве будем называть любое подмножество его декартового произведения .

Рассмотрим декартово произведение на себя: . Т.е. это множество всевозможных слов из двух букв в алфавите .

Определение

Отношением эквивалентности называется подмножество декартового произведения, которое удовлетворяет следующих трем свойствам:

1. Рефлексивность. .

2. Симметричность. .

3. Транзитивность. .

Примеры отношения эквивалентности.

Пример 1. Рассмотрим в качестве множества X множество натуральных чисел: . Для него рассмотрим обычное равенство натуральных чисел. Скажем, что два натуральных числа эквивалентны, если они равны в обычном смысле. Очевидно, что это есть отношение эквивалентности.

Пример 2. Рассмотрим произвольное натуральное число . Числа x и y назовем эквивалентными , если они дают один и тот же остаток при делении на . Очевидно, что это есть отношение эквивалентности.

Пример 3. Введем отношение эквивалентности на множестве слов, длина которых не меньше числа . Рассмотрим множество этих слов в алфавите . Скажем, что пара слов и эквивалентны, если совпадают их первые букв. Убедитесь сами, что все три свойства эквивалентности выполнены.

Утверждение. Пусть – множество, – отношение эквивалентности на нем. Тогда разбивает все элементы на классы эквивалентных элементов (Любая пара различных классов не пересекается между собой- , и их объединение совпадает с множеством ; ; количество классов может быть бесконечным). Любая пара элементов одного класса эквивалентна, а любая пара элементов различных классов не эквивалентна. Данное разбиение однозначно определяется отношением эквивалентности .

Доказательство данного утвнрждения предлагается в качестве самостоятельного упражнения.

Определение: суперпозицией булевых функции

называется функция

, полученная путем подстановки

функции в функцию вместо некоторой переменной: .

Замечание 1

Множества переменных подставляемых функций могут пересекаться.

Замечание 2

Переименование переменных есть частный случай суперпозиций : , в которой вместо подставлена функция , то есть переименованна в .

Определение

Будем различать переименование двух видов:

переименование с отождествлением, как в предыдущем примере (переменная переименуется в другую переменную этойже функции );

переименование без отождествления (когда переменная получает наименование, которого нет среди переменных функции).

Определение

Две функции назовем эквивалентными, если одну из другой можно получить переименованием переменных без отождествления.

Например эквивалентны и .

Функции и не эквивалентны, так как эквивалентные функции имеют одинаковое число существенных переменных.

Утверждение Двойственная суперпозиции функций- есть суперпозиция двойственных.

Доказательство

Тогда утверждение о представлении функции в виде СКНФ непосредственно следует из аналогичного утверждения о представлении функции в виде СДНФ.

Теорема о представлении любой булевой функции в виде СКНФ.

Теорема о представлении любой булевой функции в виде СДНФ : для любой булевой функции справедлива следующая формула :

Чтобы провести это сведение возьмем двойственную функцию

и представим ее в виде СДНФ:

, тогда справедливы выкладки:

Последнее равенство справедливо в силу того, что противоположные наборы к нулям функции - есть единицы двойственной функции . Используя ранее полученное тождество = , получаем требуемое разложение.

Замечание 3

Введеное отношение между функциями является отношением эквивалентности, и поэтому по основному утверждению разбивает все множество функций на классы эквивалентных функций- любая пара функций из одного и тогоже класса эквивалентны между собой, а любая пара функций из разных классов между собой не эквивалентны.

Замечание 3

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

Определение: замыканием системы функций называется множество функций , полученных из функций всевозможными суперпозициями.

Пример 1:

Здесь принимается обозначение: слева от стрелки стоит исходная функция, над стрелкой – какая функция и вместо какой переменной исходной фукции производится подстановка, справа от стрелки результат подстановки.

Пример 2:

Упражнение

Покажите, что остальные подстановки не дают новых функций в указанных примерах.

Определение : замкнутой системой функции называют систему, замыкание которой совпадает с самой системой .

Пример 3:

Определение: система функций называется полной, если ее замыкание совпадает с классом всех булевых функций.(По другому говоря, с помощью суперпозиций функций из системы можно получить любую булевую функцию.)