2.5. Полнота, примеры полных систем

3. Система {X1ÚX2, } – полна в P2.

Возьмем в качестве полной в Р2 системы U={X1ÚX2, , X1&X2}, B={X1ÚX2, }. Надо показать, что x1&X2 представляется формулой над B. Действительно, по правилу Де Моргана получим: X1&X2= .

С помощью этой леммы докажем полноту еще ряда систем.

4. Система {X1&X2, } – полна в Р2.

5. Система {X1|X2} полна в Р2. Для доказательства возьмем в качестве полной в Р2 системы U = {X1&X2, } и выразим Х1&Х2 и через Х1|X2 :

= X1 | X1, X1 & X2 = = (X1|X2)|(X1|X2).

6. Система {X1 X2} полна в Р2. U = {X1ÚX2, }, = X1 X1, X1ÚX2 = = (X1 X2) (X1 X2).

7. Система {X1&X2, X1ÅX2, 0, 1}, U = {X1&X2, }, = X1Å1.

Следствие. Полином Жегалкина.

F(X1, ..., XN) Î P2, представим ее в виде формулы через конъюнкцию и сумму по модулю два, используя числа 0 и 1. Это можно сделать, так как {X1&X2, X1ÅX2, 0, 1} полна в Р2. В силу свойства X & (YÅZ) = Xy Å Xz можно раскрыть все скобки, привести подобные члены, и получится полином от N переменных, состоящий из членов вида Х Х ...Х , соединенных знаком Å. Такой полином называется полиномом Жегалкина.

Общий вид полинома Жегалкина:

Где , S = 0, 1, ..., N, причем при S = 0 получаем свободный член А0.

Представление функции в виде полинома Жегалкина

1. Представим любую функцию формулой над {X1&X2, } и сделаем замену =XÅ1. Этот способ удобен, если функция задана формулой.

Пример 2. (X1 (X2 X3))(X1 Ú X2) X3 = (X1 Ú X2 Ú X3)(X1 Ú X2) X3 = (`X1X2 Ú X1X3 Ú X1X2 Ú X2 Ú X2X3)X3 = (`X1X3 Ú X2)X3 = X1X3 X2 X3 = ((X1X3Å1)X2Å1)X3 = X1X2X3ÅX2X3ÅX3.

Надо помнить, что четное число одинаковых слагаемых в сумме по Mod2 дает 0.

2. Метод неопределенных коэффициентов. Он удобен, если функция задана таблицей.

Пример 3. Запишем с неопределенными коэффициентами полином Жегалкина для функции трех переменных F(X1, X2, X3) = (01101001) = А0 Å А1Х1Å Å А2Х2 Å А3Х3 Å B1X1X2 Å B2X2X3 Å B3X1X3 Å Cx1X2X3. Затем находим коэффициенты, используя значения функции на всех наборах. На наборе (0, 0, 0) F(0, 0, 0) = 0, с другой стороны, подставив этот набор в полином, получим F(0, 0, 0) = А0, отсюда А0 = 0. F(0, 0, 1) = 1, подставив набор (0, 0, 1) в полином, получим: F(0, 0, 1) = А0 Å А3, т. к. А0 = 0, отсюда А3 = 1. Аналогично, F(0, 1, 0) = 1 = А2, f(0, 1, 1) = 0 = А2 Å А3 Å B2 = B2 = 0; А1 = 1; 0 = А1 Å А3 Å B3 = B3 = 0; 0 = А1 Å А2 Å B1 = B1 = 0; 1 = 1 Å 1 Å 1 Å C; C = 0; F(X1, X2, X3) = X1 Å X2 Å X3.

3. Многочлен Жегалкина можно получить также с помощью треугольника Паскаля по единицам его левой стороны по таблице следующим образом. Построим многочлен Жегалкина для функции F = (10011110). Верхняя сторона треугольника есть функция F. Любой другой элемент треугольника есть сумма по модулю для двух соседних элементов предыдущей строки. Левая сторона треугольника для функции F содержит шесть единиц. Многочлен Жегалкина будет содержать шесть слагаемых. Первая единица треугольника соответствует набору (000). Первое слагаемое многочлена есть 1. Третья снизу единица в левой стороне треугольника соответсвует набору (101). В качестве слагаемого многочлена берем X1X3. Аналогично для других единиц треугольника. Слева от наборов показаны слагаемые многочлена Жегалкина.

Тогда

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

Каждая функция из может быть представлена в виде полинома Жегалкина единственным образом.

Здесь единственность понимается с точностью до порядка слагаемых в сумме и порядка сомножителей в конъюнкциях:

, S = 0, 1, ..., N. Доказательство. Любая функция из Р2 может быть представлена формулой над {X1 & X2, X1Å X2, 0, 1}, а эта формула после раскрытия всех скобок и приведения подобных членов дает полином Жегалкина. Докажем единственность представления. Рассмотрим функции F(X1, ..., Xn) от N переменных. Мы знаем, что всего таких функций, т. е. их таблиц истинности, 2N. Подсчитаем число различных полиномов Жегалкина от N переменных, т. е. число вариаций вида: . Число наборов равно числу всех подмножеств множества { X1, ..., Xn }, сюда входит и пустое множество (если S = 0). Число подмножеств множества из n элементов равно 2N , а так как каждый набор входит с коэффициентом , принимающим два значения: 0 или 1, то число всевозможных полиномов будет . Так как каждому полиному соответствует единственная функция, число функций от N переменных равно числу полиномов, то каждой функции будет соответствовать единственный полином.

Определение. Функция F(X1, ..., Xn), полином Жегалкина для которой имеет следующий линейный относительно переменных вид: F = А0 Å А1Х1 Å А2Х2 Å ... Å Аnхn, называется линейной.

Лемма О нелинейной функции. Суперпозицией нелинейной функции, отрицания и константы 1 можно получить конъюнкцию.

Доказательство. Пусть F(X1, ..., Xn) – нелинейная функция. Тогда полином Жегалкина содержит для нее слагаемое, в котором присутствует произведение Xixj. Будем считать для простоты, что X1X2 в многочлене Жегалкина является этим произведением. Произведя группировку слагаемых, функцию F представим в виде

Функция H0 не есть тождественный нуль, иначе в полиноме Жегалкина отсутствует слагаемое с произведением X1X2. Тогда существует набор (A3, …, AN) из 0 и 1, для которого H0(A3, …, AN) = 1. Пусть H1(A3, …, AN) = A, H2(A3, …, AN) = B, H3(A3, …, AN) = C. Тогда

Построим функцию:

где D = Ab Å C. Если D = 0, то H(X1, X2) = X1X2. Если D = 1, то H(X1, X2) = X1X2 Å 1 и тогда Лемма доказана.

Функция F(X1, ..., XN) сохраняет константу A Î {0, 1}, если F(A, …, A) = A.

Пример 4. Функция Xy сохраняет 0, сохраняет 1. Функция X®Y сохраняет 1 и не сохраняет 0.