Архитектура Аудит Военная наука Иностранные языки Медицина Металлургия Метрология
Образование Политология Производство Психология Стандартизация Технологии


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



 

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. Аналогично для других единиц треугольника. Слева от наборов показаны слагаемые многочлена Жегалкина.

  N x1x2x3 f Треугольник Паскаля
x3 x2 x2x3 x1 x1x3 x1x2 x1x2x3 1 0 0 1 1 1 1 0 1 0 1 0 0 0 1 1 1 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 1 0  
                 

 

Тогда

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

 

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

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

, 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.


Поделиться:



Популярное:

Последнее изменение этой страницы: 2016-04-09; Просмотров: 1018; Нарушение авторского права страницы


lektsia.com 2007 - 2024 год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! (0.012 с.)
Главная | Случайная страница | Обратная связь