Телефон: 8-800-350-22-65
WhatsApp: 8-800-350-22-65
Telegram: sibac
Прием заявок круглосуточно
График работы офиса: с 9.00 до 18.00 Нск (5.00 - 14.00 Мск)

Статья опубликована в рамках: LVIII Международной научно-практической конференции «Вопросы технических и физико-математических наук в свете современных исследований» (Россия, г. Новосибирск, 21 декабря 2022 г.)

Наука: Математика

Секция: Дискретная математика и математическая кибернетика

Скачать книгу(-и): Сборник статей конференции

Библиографическое описание:
Дусанова А., Мухамедова Г.Р. ИНТЕРЕСНЕЙШИЙ МЕТОД ПРЕДСТАВЛЕНИЯ БУЛЕВЫХ ФУНКЦИЙ В ВИДЕ ПОЛИНОМА ЖЕГАЛКИНА // Вопросы технических и физико-математических наук в свете современных исследований: сб. ст. по матер. LVIII междунар. науч.-практ. конф. № 12(49). – Новосибирск: СибАК, 2022. – С. 59-65.
Проголосовать за статью
Дипломы участников
У данной статьи нет
дипломов

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

Дусанова Азиза

студент 3- курса, физико -математического факультета, Ташкентского государственного педагогического университета им. Низами,

Республика Узбекистан, г. Ташкент

Мухамедова Гулчехра Рихсибаевна

канд. пед. наук, доц. кафедры «Общая математика», Ташкентского государственного педагогического университета им. Низами,

Республика Узбекистан, г. Ташкент

АННОТАЦИЯ

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

 

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

 

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

, где  – полиномиальные коэффициенты (принимают значение равное 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.
Проголосовать за статью
Дипломы участников
У данной статьи нет
дипломов

Комментарии (1)

# Аида 28.04.2023 20:49
супер

Оставить комментарий

Форма обратной связи о взаимодействии с сайтом
CAPTCHA
Этот вопрос задается для того, чтобы выяснить, являетесь ли Вы человеком или представляете из себя автоматическую спам-рассылку.