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

 

Функции f1(x) и f4(x) называются константами нуля и единицы соответственно. Функция f2(x) совпадает по своим значениям с переменной х и называется тождественной переменной х. Функция f3(x) совпадает с инвертированной переменной х. Исходя из этого, можно построить таблицу истинности, которая будет более краткой в написании (это совершенно необязательно, однако подобное представление таблиц истинности часто используется в литературе):

 

х	0	х		1
0	0	0	1	1
1	0	1	0	1

 

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

 

х1	х2	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15	f16
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

 

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

 

 

 

 

 

 

 

 

 

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

 

 

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

 

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

 =⋁

=

 

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

     =х

 

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

  ⊕ ⊕

 

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

 

 

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

  

 

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

 

 

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

  

 

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

 

 

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

  

 

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

 

 

 

 

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

 

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

 

                     (1)

 

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

или в более общем виде

                                                                       (2)

 

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

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

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

 

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

 

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

 

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

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

 

 

 

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

 

start="3"

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

 

   

 

start="4"

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

 

   
 
 

 

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

⊕ X

 

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

 

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

 

ПОСТРОЕНИЕ ПОЛИНОМОВ ЖЕГАЛКИНА С ПОМОЩЬЮ

ТАБЛИЦ ИСТИННОСТИ

(МЕТОД НЕОПРЕДЕЛЕННЫХ КОЭФФИЦИЕНТОВ)

 

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

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

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

Решение:

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

 

0	0	0	1	0	0
0	0	1	0	0	0
0	1	0	1	1	1
0	1	1	0	0	0
1	0	0	1	0	1
1	0	1	0	0	1
1	1	0	1	1	1
1	1	1	0	0	1

 

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

 

 

    .                                                                                              (3)

 

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

Так как   то .

 

 

 

 

 

 

 

 

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

 

 

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

 

 

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

 

0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	0

 

Решение:

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

 

 

 

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

Так как   то .

 

 

 

 

 

 

 

 

 

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

 

  

 

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

 

 

 

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

 

В тех случаях, когда функция задана логической формулой, иногда удобнее использовать не громоздкий метод неопределенных коэффициентов, а компактный метод эквивалентных преобразований. Для этого необходимо уметь привести функцию в ДНФ или СДНФ, не прибегая к использованию таблиц истинности. Чаще всего используются следующие тождества

 

 

 

а также закон ДеМоргана. Далее следует раскрыть скобки по самым обычным правилам.

Пример 1: построить полином Жегалкина для функции, заданной в виде СДНФ –   

Решение:

1. Избавимся от дизъюнкции с помощью закона ДеМоргана

=    

 

2. Избавимся от отрицаний

= = =

 

Ответ: полином Жегалкина имеет вид ) = .

Пример 2:  построить полином Жегалкина для функции, представленной в ДНФ -

Решение:

1. Заменим дизъюнкцию конъюнкцией и  суммой по модулю два

( ∨ ) ( ∨ ) = (  ⊕   ⊕ ) (⊕ ⊕ )

 

2. Избавимся от отрицаний

( ∨ ) ( ∨ ) = (  ⊕   ⊕ ) (⊕ ⊕ ) = ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ ⊕ = 0 ⊕    ⊕ 0 ⊕ 0  ⊕   ⊕  0⊕ ⊕ ⊕ =   ⊕   ⊕   ⊕ ⊕ = ⊕   ⊕

 

Ответ: полином Жегалкина имеет вид

) = ⊕   ⊕

 

 

 

МЕТОД ТРЕУГОЛЬНИКА

 

Метод треугольника позволяет преобразовать таблицу истинности в полином Жегалкина с помощью построения вспомогательной треугольной таблицы в соответствии со следующими правилами:

1. Строится полная таблица истинности, в которой строки идут в порядке возрастания двоичных кодов от 000…00 до 111…11.
2. Строится вспомогательная треугольная таблица, в которой первый столбец совпадает со столбцом значений функции в таблице истинности.
3. Ячейка в каждом последующем столбце получается путём суммирования по модулю 2 двух ячеек предыдущего столбца — стоящей в той же строке и строкой ниже.
4. Столбцы вспомогательной таблицы нумеруются двоичными кодами в том же порядке, что и строки таблицы истинности.
5. Каждому двоичному коду ставится в соответствие один из членов полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке 111 соответствует член ABC, ячейке 101 — член AC, ячейке 010 — член B, ячейке 000 — член 1 и т. д.
6. Если в верхней строке какого-либо столбца стоит единица, то соответствующий член присутствует в полиноме Жегалкина.