Многочлен Жигалкина

Краткие теоретические сведения о многочлене Жигалкина

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

Причем для системы Жигалкина {+,^, 1} используются следующие тождества:

x+x=0, x^x=x,

x+x=1, x^x=0,

x+0=x, x⁰=0,

x+1=x, x¹=x,

Замечание: Знак конъюнкции «^» будем заменять невидимой точкой — умножением.

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

Многочлен Жигалкина константы равен самой константе:

Многочлен Жигалкина функции одной переменной:

Многочлен Жигалкина функции двух переменных:

.

Многочлен Жигалкина функции трех переменных:

.

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

Пример решения заданий:

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

.

Решение. 1 Способ (метод цепочки).

Избавимся от операций «~» и «>» по формулам алгебры логики

A~B=AB?AB, A>B=A?B.

далее используем законы де Моргана.

A?B=A B, AB=A?B;

=xy (y?z) xy (y?z)?x?yz=

=(xy?(y?z))(xy?y?z)?x?yz=

=(x?y?y?z)(xy?y?z)?x?yz=

В обеих скобках применяем закон полного поглощения A? AB=A;

=(x?y)(y?z)?x?yz=

раскроем скобки;

=xy?xz?yy?yz?x?yz=

Первое и второе слагаемое поглотит-x, третье слагаемое yy=0 (закон противоречия), в четвертом и шестом слагаемых вынесем общий множитель z-за скобки;

=x?z (y?y) = x? z=

В скобках (y?y) = 1 (закон исключения третьего), z· 1=z;

Полученный результат подводим под систему Жигалкина и раскрываем скобки;

=xz = x (z+1)+1 = xz+z+1.

Полученное выражение — есть Многочлен Жигалкина.

Решение. 2 способ (метод неопределенных коэффициентов).

Построим таблицу истинности для

f (x, y, z)=(xy~(y?z))>(x?yz)

Построим ещё одну таблицу, в «шапке» которой входящие переменные x, y, z, результирующее f, найденное в предыдущей таблице и стандартное выражение многочлена Жигалкина для трех переменных.

На каждом наборе переменных подставляем в выражение многочлена вместо x, y, z соответствующие значения, учитываем значение f на данном наборе и, используя свойство 1+1=0, последовательно делаем вывод о каждом числовом коэффициенте a.

жигалкин тождество многочлен

Таким образом, получим f (x, y, z) = 1+x+xz.

Результаты, полученные 1 и 2 способами одинаковы.

Пример решения задач.

Привести к виду многочлен Жигалкина S= (x ~ y) > xz.

1 способ решения.

S=(x ~ y) > xz = xy? xy? xz = xy xy xz =

= ((xy+1)((x+1)(y+1)+1)+1) (xz+1)+1=

= ((xy+1)(xy + x + y + 1 +1) +1)(xz + 1)-+ 1 =

xy + xy + xy + xy + x + y + 1) (xz +1) + 1 =

= xz + x + xyz + y + xz + 1 + 1 = x + y +xyz

2 способ решения.

S = x + y + xyz

Результаты, полученные 1 и 2 способами, одинаковы.

1. Акимов О. Е. Дискретная математика: логика, группы, графы. — М: Лаборатория базовых знаний, 2003.

2. Аляев Ю. А., Тюрин С. Ф. Дискретная математика и математическая логика. — М: Финансы и статистика, 2006.

3. Блиялкина Г. Н. Дискретная математика: Методические рекомендации к курсу. — Орск: Издательство ОГТИ, 2004.

4. Галушкина Ю. И., Марьямов А. Н. Конспект лекций по дискретной математике. — М: Айрис — пресс, 2007.

5. Горбатов В. А., Горбатов А. В., Горбатова М. В. Дискретная математика: Учебник для студентов вузов. — М: ООО «Издательство АСТ», ООО «Издательство Астрель», 2003.

6. Канцедал С. А. Дискретная математика: учебное пособие. — М: НД «Форум»: ИНФРА — М, 2007.

7. Нефедов В. Н., Осипова В. А. Курс дискретной математики. — М: Издательство МАИ, 1992.

8. Новиков Ф. А. Дискретная математика для программистов. Учебник для вузов. — СПб: Питер, 2005.