Материал: Полиномы Жегалкина для логических операций

Рассмотрим функции двух переменных (считать f(x)) :

Функции f1 и f16 называют константами 0 и 1 соответственно. Функции f4 = х1, f6= х2, f11= f13, то есть f4, f6, f11, f13 зависят лишь от одной переменной, в отличие от остальных функций

Функции f3 и f5 называются функциями запрета.

алгебра булевый логический таблица

СВОЙСТВА ЭЛЕМЕНТАРНЫХ БУЛЕВЫХ ФУНКЦИЙ, ЗАДАВАЕМЫХ ЛОГИЧЕСКИМИ ОПЕРАЦИЯМИ

.        Дизъюнкция, конъюнкция, эквивалентность, сумма по модулю 2, штрих Шеффера, стрелка Пирса обладают свойством коммутативности, то есть замена переменных местами в выражении не играет роли.

.        Дизъюнкция, конъюнкция, сумма по модулю 2 имеют свойства ассоциативности (когда результат вычисления не зависит от порядка выполнения операций между несколькими переменными (расстановки скобок), потому позволительно опускать скобки в записи), которую также называют сочетательным законом, и дистрибутивности, называемую также распределительным законом.

.        Закон ДеМоргана

=⋁

=

4.      Закон двойного отрицания

=х

5.      Выражение дизъюнкции через конъюнкцию и сумму по модулю 2

⊕ ⊕

.        Выражение конъюнкции через импликацию

.        Выражение отрицания через штрих Шеффера, стрелку Пирса, сумму по модулю 2 и эквивалентность

8.      Выражение конъюнкции через штрих Шеффера

.        Выражение дизъюнкции через стрелку Пирса

10.    Закон поглощения

11.    Закон склеивания

Для конъюнкции, дизъюнкции и суммы по модулю 2 существует несколько справедливых тождеств

ПОЛИНОМЫ ЖЕГАЛКИНА ДЛЯ ЛОГИЧЕСКИХ ОПЕРАЦИЙ

Полином (многочлен) Жегалкина от n переменных - это функция вида

 (1)

где  - коэффициенты, принимающие значение либо нуля, либо единицы, или в более общем виде

 (2)

где  - элементарная конъюнкция, то есть полином Жегалкина есть многочлен, представляющий собой сумму по модулю 2 n элементарных конъюнкций.

Любую булеву функцию возможно представить в виде многочлена Жегалкина, и при том только единственным образом. Это утверждение также называют теоремой Жегалкина.

По сути, операция приведения логической функции представляет собой выражение логических операций через конъюнкцию и сумму по модулю 2.

СВОЙСТВА АЛГЕБРЫ ЖЕГАЛКИНА

Множество булевых функций, в которых могут быть задействованы только операции конъюнкции и суммы по модулю 2 и единица (также говорят, что эти булевы функции заданы в базисе Жегалкина S ={⊕, ⋀, 1}), называется алгеброй Жегалкина.

Основные свойства алгебры Жегалкина

.        Коммутативность

.        Ассоциативность

.        Дистрибутивность

.        Свойства констант

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

⊕ X

СПОСОБЫ ПОСТРОЕНИЯ ПОЛИНОМОВ ЖЕГАЛКИНА

Существует несколько способов построения полиномов Жегалкина, каждый из которых удобен по-своему в определенных случаях.

ПОСТРОЕНИЕ ПОЛИНОМОВ ЖЕГАЛКИНА С ПОМОЩЬЮ ТАБЛИЦ ИСТИННОСТИ (МЕТОД НЕОПРЕДЕЛЕННЫХ КОЭФФИЦИЕНТОВ)

Построение полиномов Жегалкина с помощью таблиц истинности или, как еще говорят, методом неопределенных коэффициентов - процесс кропотливый, требующий внимания и определенной сноровки, а также полного осознания того, что надо делать.

Этот способ можно применять и тогда, когда функция задана таблицей истинности, и тогда, когда функция представлена логической формулой.

Пример 1: построить полином Жегалкина для функции

Составим таблицу истинности для функции

1.      Теперь, используя формулу (1), построим полином Жегалкина для нашей функции в общем виде (для трёх переменных):

 . (3)

2.   Найдем значения коэффициентов

Так как то  .

3.      Составим полином Жегалкина, подставив полученные значения коэффициентов в формулу (3)

Ответ: полином Жегалкина, построенный для функции, будет равен

Пример 2: построить многочлен Жегалкина, используя данную таблицу истинности

Решение:

.        Запишем общий вид полинома Жегалкина (с неопределенными коэффициентами), то есть формулу (1) для 3 переменных

.        Найдём коэффициенты

Так как то  .

.        Подставим найденные коэффициенты в формулу (3) и найдем таким образом многочлен Жегалкина