Материал: Полиномы Жегалкина для логических операций
Ответ: полином Жегалкина для данной таблицы
истинности имеет следующее значение: .
ПОСТРОЕНИЕ ПОЛИНОМОВ ЖЕГАЛКИНА С ПОМОЩЬЮ
ЭКВИВАЛЕНТНЫХ ПРЕОБРАЗОВАНИЙ ДНФ И КНФ, СДНФ И СКНФ
В тех случаях, когда функция задана логической
формулой, иногда удобнее использовать не громоздкий метод неопределенных
коэффициентов, а компактный метод эквивалентных преобразований. Для этого
необходимо уметь привести функцию в ДНФ или СДНФ, не прибегая к использованию
таблиц истинности. Чаще всего используются следующие тождества
а также закон ДеМоргана. Далее следует раскрыть скобки по самым обычным правилам.
Пример 1: построить полином Жегалкина для
функции, заданной в виде СДНФ -
Решение:
. Избавимся от дизъюнкции с помощью
закона ДеМоргана
= 
2. Избавимся от отрицаний
= =
=
Ответ: полином Жегалкина имеет вид 
)
= .
Пример 2: построить полином Жегалкина для
функции, представленной в ДНФ - 
Решение:
. Заменим дизъюнкцию конъюнкцией и суммой
по модулю два
(
∨
) (
∨
)
= (
⊕
⊕
) (
⊕
⊕
)
. Избавимся от отрицаний
( ∨
) (
∨
)
= (
⊕
⊕
) (⊕
⊕
)
= 
⊕
⊕
⊕
⊕
⊕
⊕
⊕
= 0 ⊕
⊕
0 ⊕
0 ⊕
⊕
0⊕
⊕
⊕
=
⊕
⊕
⊕
⊕
= ⊕
⊕
Ответ: полином Жегалкина имеет вид
) = ⊕
⊕
МЕТОД ТРЕУГОЛЬНИКА
Метод треугольника позволяет преобразовать таблицу истинности в полином Жегалкина с помощью построения вспомогательной треугольной таблицы в соответствии со следующими правилами:
. Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от 000…00 до 111…11.
. Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
. Ячейка в каждом последующем столбце получается путём суммирования по модулю 2 двух ячеек предыдущего столбца - стоящей в той же строке и строкой ниже.
. Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
. Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке 111 соответствует член ABC, ячейке 101 - член AC, ячейке 010 - член B, ячейке 000 - член 1 и т. д.
. Если в верхней строке какого-либо
столбца стоит единица, то соответствующий член присутствует в полиноме
Жегалкина.
Заключение
Математика - наука очень точная, однако в ней можно проявить фантазию, решая задачи различными способами. Дискретная математика не является в этом исключением.
В своей курсовой работе я рассмотрела несколько самых распространенных способов решения поставленной мне задачи: приведения логических функций к полиномам Жегалкина. Каждый из рассмотренных мной способов имеет свои особенности применения, но все они требуют безусловной внимательности и сосредоточенности.
В заключение хочется сказать, что Иван Иванович
Жегалкин оказал большую услугу человечеству, когда вывел полином, названный
впоследствии его именем. Полином, члены которого связываются только двумя
операциями и единицей, оказался невероятно полезен и очень широко применяется
человеком в процессе его жизни и деятельности.
Список использованной
литературы
1. Яблонский С. В. Введение в дискретную математику: Учеб. пособие для вуов . - 2-е изд., перераб. и доп. - М.: Наука. Гл. ред. физ.-мат. лит. - 1986.- 384 с.
2. Марченков С. С. Замкнутые классы булевых функций. - М.: Физ.-мат. лит. - 2000. - 126 с.
. Дунаев С. Д., Золотарев С. Н. Цифровая схемотехника: Учебное пособие для техникумов и колледжей ж.-д. транспорта. - М.: ГОУ «Учебно-методический центр по образованию на железнодорожном транспорте», 2007. - 238 с.
4. Супрун В.П. Табличный метод полиномиального разложения булевых функций - М.: Кибернетика. - 1987. - № 1
5. Логачёв О.А, Сальников А.А., Ященко В.В. Булевы функции в теории кодирования и криптологии - МЦНМО, 2004. - 470с.
. Е.Л Рабкин, Ю.Б. Фарфоровская, дискретная математика - электронное издание.