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

/

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

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

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

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

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

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

x+1=x, x^1=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.