ИНТЕРЕСНЕЙШИЙ МЕТОД ПРЕДСТАВЛЕНИЯ БУЛЕВЫХ ФУНКЦИЙ В ВИДЕ ПОЛИНОМА ЖЕГАЛКИНА

​АННОТАЦИЯ

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

Ключевые слова: Булевы полиномы, полином Жегалкина, таблица истинности, карта Карно.

Полиномом Жегалкина, или алгебраической нормальной формой (АНФ), булевой функции  называется дизъюнкция с исключением различных положительных конъюнкций переменных из множества , то есть формула вида

, где  – полиномиальные коэффициенты (принимают значение равное 0 или 1). Всего здесь  слагаемых. операция сложение по модулю 2.

Отметим основные свойства операции сложения по модулю 2:

 – коммутативность

 – ассоциативность

 – дистрибутивность

 –Связь между дизъюнкцией и суммой по модулю 2. [1]

Логическая функция трёх переменных {\displaystyle P(A,B,C)} представленная в виде карты Карно, преобразуется в полином Жегалкина следующими шагами:

1. Рассматриваем все ячейки карты Карно в порядке возрастания количества единиц в их кодах. Для функции трёх переменных последовательность ячеек будет . Каждой ячейке карты Карно сопоставляем член полинома Жегалкина в зависимости от позиций кода, в которых стоят единицы. Например, ячейке  соответствует член , ячейке  член , ячейке  член , ячейке член 1.

2. Если в рассматриваемой ячейке находится 0, переходим к следующей ячейке.

3. Если в рассматриваемой ячейке находится 1, добавляем в полином Жегалкина соответствующий член, инвертируем в карте Карно все ячейки, где этот член равен 1, и переходим к следующей ячейке. Например, если при рассмотрении ячейки 110 в ней оказывается единица, то в полином Жегалкина добавляется член  и инвертируются все ячейки карты Карно, где  и . Если единице равна ячейка , то в полином Жегалкина добавляется член 1 и инвертируется вся карта Карно.

4. Процесс преобразования можно считать законченным, когда после очередной инверсии все ячейки карты Карно становятся нулевыми [3].

Пример №1. Представить функцию   в виде полинома Жегалкина с помощью карты Карно.

Решение: Составляем таблицу истинности (1-таблица).

Таблица 1.

Таблица истинности функции

Пользуясь таблицей истинности, строим карту Карно. (2-таблица).

Таблица 2.

Таблица Карно №1.

Если ячейка 000 равна единице, то в полином Жегалкина добавляется член 1 и инвертируется вся карта Карно (3-таблица).

Таблица 3.

Таблица Карно №2.

Следующая единица расположено в ячейке 001, берём член  затем инвертируем ячейки, где  (4-таблица).

Таблица 4.

Таблица Карно №3.

Надо обратить внимание единицы, которые расположены в ячейках смотрим по возрастании. После того как взяли член из ячейки 001 смотрим в ячейку 010. Добавляем член  и инвертируем все ячейки, где  (5-таблица).

Таблица 5.

Таблица Карно №4.

Берём член  и инвертируем ячейки равные  (6-таблица).

Таблица 6.

Таблица Карно №5.

Так как значение ячейки 100 равен нулю смотрим на следующую ячейку. Из ячейки 101 берём следующий член  и инвертируем все ячейки равные (7-таблица).

Таблица 7.

Таблица Карно №6.

После ячейки 101 по возрастании смотрим в ячейку 110 которое значение равна 1. Добавляем в полином следующий член  и инвертируем ячейки, где   и  (8-таблица).

Таблица 8.

Таблица Карно №7 (окончательная)

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

Ответ:

Пример №2. Представим функцию    в виде полинома Жегалкина с помощью карты Карно.

Таблица 9.

Таблица истинности и Карта Карно функции 

Рассматриваем все ячейки карты Карно в порядке возрастания. По карте Карно первое значение единицы стоит в ячейке 011, где откуда берётся первый член полинома Жегалкина yz и инвертируются все ячейки, где y=1 и z=1 (10-таблица).

Таблица 10.

Карта Карно №1 функции

После инвертирование находим следующий член, который находится в ячейке 100 то есть x и где x=1 все ячейки карты Карно инвертируются (11-таблица).

Таблица 11.

Карта Карно №2 функции

Так как в ячейке 101 находится ноль, следующий член берём из ячейки 110 которое равен xy. Таким образом нахождение членов полинома Жегалкина можно считать оконченным так как все ячейки карты Карно аннулированы (12-таблица).

Таблица 12.

Карта Карно №3 функции

Ответ:.

Разработанный в начале ХХ века русским математиком Иваном Ивановичем Жегалкиным вид логического многочлена сейчас широко применяется в самых различных сферах человеческой деятельности - начиная от криптографии и заканчивая применением в сумматорах - аналого-цифровых устройствах, которые реализуют логическую операцию «исключающее ИЛИ», которую также называют суммой по модулю 2, сумматоры являются обязательной частью любого аналого-цифрового устройства, любого без исключений процессора.

Список литературы:

1. To’rayev H.T., O’rinboyev E. «Diskret matematika va matematik mantiq» fanidan o’quv – uslubiy majmua («5480100 - Amaliy matematika va informatika» ta’lim yo’nalishi bakalavr talabalari uchun). O’quv-uslubiy majmua. – Samarqand: SamDU nashri, 2010.-264 б.
2. Яблонский С. В. Введение в дискретную математику: Учеб. пособие для вуов . - 2-е изд., перераб. и доп. - М.: Наука. Гл. ред. физ.-мат. лит. - 1986.- 384 с.
3. Супрун В.П. Табличный метод полиномиального разложения булевых функций - М.: Кибернетика. - 1987. - № 1
4. Юнусов А.С. Математик мантиқ ва алгоритмлар назарияси элементлари. Т., “Янги аср авлоди”. 2006.