Программные продукты и системы : международный научно-практический журнал. - Тверь : НИИ Центрпрограммсистем, 2023. - Т. 36, № 3. - 504 с. - ISSN 0236-235X. - Текст : электронный. - URL: https://znanium.ru/catalog/product/2113360 (дата обращения: 30.04.2024)

Скопировать запись

Экспорт списка

Excel

RUSMARC .iso

win-1251

UTF-8

RUSMARC .txt

win-1251

UTF-8

IRBIS .txt

win-1251

UTF-8

Фрагмент текстового слоя документа размещен для индексирующих роботов. Для полноценной работы с документом, пожалуйста, перейдите в ридер.

Научно-исследовательский институт «Центрпрограммсистем»



Программные продукты и системы


НАУЧНЫЙ ЖУРНАЛ



            2023, том 36, № 3



(год издания тридцать шестой)



Главный редактор
Г.И. САВИН, академик РАН







SOFTWARE & SYSTEMS




Research Journal



            2023, vol. 36, no. 3



Editor-in-Chief
G.I. SAVIN, Academician of the Russian Academy of Sciences





Research Institute CENTERPROGRAMSYSTEM

стр. 1

© ПРОГРАММНЫЕ ПРОДУКТЫ И СИСТЕМЫ
Научный журнал

2023. Т. 36. № 3
DOI: 10.15827/0236-235X.142

Главный редактор
Г.И. САВИН, академик РАН

Научные редакторы номера:
Н.А. СЕМЕНОВ, д.т.н., профессор
А.Н. СОТНИКОВ, д.ф.-м.н., профессор

Издатель НИИ «Центрпрограммсистем»
(г. Тверь, Россия)
Учредитель В.П. Куприянов
        Журнал зарегистрирован в Роскомнадзоре 3 марта 2020 г.
Регистрационное свидетельство ПИ № ФС 77-77843

Подписной индекс в каталоге
Урал-Пресс 70799

                     ISSN 0236-235X (печатн.) ISSN 2311-2735 (онлайн)



            РЕДАКЦИОННАЯ КОЛЛЕГИЯ


Семенов Н.А. - заместитель главного редактора, д.т.н., профессор Тверского государственного технического университета (г. Тверь, Россия)
Сотников А.Н. - заместитель главного редактора, д.ф.-м.н., профессор, заместитель директора
Межведомственного суперкомпьютерного центра РАН (г. Москва, Россия)
Афанасьев А.П. - д.ф.-м.н., профессор Московского физико-технического института (технического университета), заведующий Центром распределенных вычислений Института проблем передачи информации РАН (г. Москва, Россия) Баламетов А.Б. - д.т.н., профессор Азербайджанского научно-исследовательского и проектно-изыскательского института энергетики (г. Баку, Азербайджан)
Батыршин И.З. - д.т.н., профессор Мексиканского института нефти (г. Мехико, Мексика)
Борисов В.В. - д.т.н., профессор филиала Национального исследовательского университета «МЭИ» в г. Смоленске (г. Смоленск, Россия)
Голенков В.В. - д.т.н., профессор Белорусского государственного университета информатики и радиоэлектроники
(г. Минск, Беларусь)
Елизаров А.М. - д.ф.-м.н., профессор Института математики и механики им. Н.И. Лобачевского Казанского федерального университета (г. Казань, Россия)
Еремеев А.П. - д.т.н., профессор Национального исследовательского университета «МЭИ» (г. Москва, Россия)
Кузнецов О.П. - д.т.н., профессор Института проблем управления РАН (г. Москва, Россия)
Курейчик В.М. - д.т.н., профессор Инженерно-технологической академии Южного федерального университета (г. Таганрог, Россия)
Лисецкий Ю.М. - д.т.н., генеральный директор «S&T Ukraine» (г. Киев, Украина)
Мамросенко К.А. - к.т.н., доцент Московского авиационного института (национального исследовательского университета), руководитель Центра визуализации и спутниковых информационных технологий НИИСИ РАН (г. Москва, Россия)
Мейер Б. - доктор наук, профессор, заведующий кафедрой Высшей политехнической школы - ETH (г. Цюрих, Швейцария)
Палюх Б.В. - д.т.н., профессор Тверского государственного технического университета (г. Тверь, Россия)
Серов В. С. - д.ф.-м.н., профессор Университета прикладных наук Оулу (г. Оулу, Финляндия)
Сулейманов Д.Ш. - академик АН Республики Татарстан, д.т.н., профессор Казанского государственного технического университета (г. Казань, Республика Татарстан, Россия)
Татарникова Т.М. - д.т.н., доцент, профессор Санкт-Петербургского государственного
электротехнического университета «ЛЭТИ» им. В.И. Ульянова (Ленина) (г. Санкт-Петербург, Россия)
Ульянов С.В. - д.ф.-м.н., профессор, ведущий научный сотрудник Объединенного института ядерных исследований
(г. Дубна, Россия)
Хорошевский В. Ф. - д.т.н., профессор Московского физико-технического института (технического университета)
(г. Москва, Россия)
Шабанов Б.М. - д.т.н., чл.-корр. РАН, директор Межведомственного суперкомпьютерного центра РАН (г. Москва, Россия)
Язенин А.В. - д.ф.-м.н., профессор Тверского государственного университета (г. Тверь, Россия)


АССОЦИИРОВАННЫЕ ЧЛЕНЫ РЕДАКЦИИ

Национальный исследовательский университет «МЭИ», г Москва, Россия
Технологический институт Южного федерального университета, г. Таганрог, Россия
Тверской, государственный технический университет, г. Тверь, Россия

АДРЕС ИЗДАТЕЛЯ И РЕДАКЦИИ
Россия, 170024,
г. Тверь, просп. Николая Корыткова, д. 3а
Телефон (482-2) 39-91-49
Факс (482-2) 39-91-00
E-mail: red@cps.tver.ru
Сайт: www.swsys.ru

Дата выхода в свет 16.09.2023 г.
Отпечатано ИПП «Фактор и К»
Россия, 170100, г. Тверь, ул. Крылова, д. 26
Выпускается один раз в квартал Год издания тридцать шестой Формат 60x84 1/8. Объем 160 стр. Заказ № 15. Тираж 1000 экз. Цена 550,00 руб

стр. 2

© SOFTWARE & SYSTEMS
Research journal
2023, vol. 36, no. 3
DOI: 10.15827/0236-235X.142

Editor-in-chief
G.I. SAVIN, Academician of RAS

Science editors of the issue:
N.A. Semenov, Dr.Sc. (Engineering), Professor
A.N. Sotnikov, Dr.Sc. (Physics and Mathematics), Professor

Publisher Research Institute
CENTERPROGRAMSYSTEM (Tver, Russian Federation)

Founder V.P. Kupriyanov

The journal is registered with the Federal Service for Supervision of Communications, Information Technology and Mass Communications (Roskomnadzor) March 3rd, 2020

            Registration certificate ПИ № ФС 77-77843 ISSN 0236-235X (print) ISSN 2311-2735 (online)


EDITORIAL BOARD

Semenov N.A. - Deputy Editor-in-Chief, Dr.Sc. (Engineering), Professor of the Tver State Technical University (Tver, Russian Federation)
Sotnikov A.N. - Deputy Editor-in-Chief, Dr.Sc. (Physics and Mathematics), Professor, Deputy Director of the Joint Supercomputer Center of the Russian Academy of Sciences (Moscow, Russian Federation) Afanasiev A.P. - Dr.Sc. (Physics and Mathematics), Professor of the Moscow Institute of Physics and Technology, Head of Centre for Distributed Computing of Institute for Information Transmission Problems (Moscow, Russian Federation)
Balametov A.B. - Dr.Sc. (Engineering), Professor of the Azerbaijan Scientific-Research & Design-Prospecting Power Engineering Institute (Baku, Azerbaijan)
Batyrshin I.Z. - Dr.Sc. (Engineering), Professor of the Mexican Petroleum Institute (Mexico City, Mexico)
Borisov V.V. - Dr.Sc. (Engineering), Professor of the MPEI Branch in Smolensk (Smolensk, Russian Federation)
Golenkov V.V. - Dr.Sc. (Engineering), Professor of the Belarusian State University of Informatics and Radioelectronics (Minsk, Republic of Belarus)
Elizarov A.M. - Dr.Sc. (Physics and Mathematics), Professor of the N.I. Lobachevsky Institute of Mathematics and Mechanics of the Kazan Federal University (Kazan, Russian Federation)
Eremeev A.P. - Dr.Sc. (Engineering), Professor of the National Research University "Moscow Power Engineering
Institute" (Moscow, Russian Federation)
Kuznetsov O.P. - Dr.Sc. (Engineering), Professor of the Institute of Control Sciences of the Russian Academy of Sciences (Moscow, Russian Federation)
Kureichik V.M. - Dr.Sc. (Engineering), Professor of the Academy of Engineering and Technology of the Southern
Federal University (Taganrog, Russian Federation)
Lisetsky Yu.M. - Dr.Sc. (Engineering), CEO of "S&T Ukraine" (Kiev, Ukraine)
Mamrosenko K.A. - Ph.D. (Engineering), Associate Professor of the Moscow Aviation Institute (National Research University), Head of the Center of Visualization and Satellite Information Technologies SRISA RAS (Moscow, Russian Federation)
Meyer B. - Dr.Sc., Professor, Head of Department in the Swiss Federal Institute of Technology in Zurich, ETH
(Zurich, Switzerland)
Palyukh B. V. - Dr.Sc. (Engineering), Professor of the Tver State Technical University (Tver, Russian Federation)
Serov V.S. - Dr.Sc. (Physics and Mathematics), Professor of the Oulu University of Applied Sciences (Oulu, Finland) Suleimanov D.Sh. - Academician of TAS, Dr.Sc. (Engineering), Professor of the Kazan State Technical University (Kazan, Republic of Tatarstan, Russian Federation)
Tatarnikova T.M. - Dr.Sc. (Engineering), Associate Professor, Professor of the St. Petersburg Electrotechnical
University "LETI" (St. Petersburg, Russian Federation)
Ulyanov S.V. - Dr.Sc. (Physics and Mathematics), Professor of the Dubna International University for Nature, Society and Man (Dubna, Russian Federation)
Khoroshevsky V.F. - Dr.Sc. (Engineering), Professor of the Moscow Institute of Physics and Technology
(Moscow, Russian Federation)
Shabanov B.M. - Dr.Sc. (Engineering), Corresponding Member of the RAS, Director of the Joint Supercomputer Center of the Russian Academy of Sciences (Moscow, Russian Federation)
Yazenin A.V. - Dr.Sc. (Physics and Mathematics), Professor of the Tver State University (Tver, Russian Federation)


ASSOCIATED EDITORIAL BOARD MEMBERS

National Research University "Moscow Power Engineering Institute", Moscow, Russian Federation Technology Institute at Southern Federal University, Taganrog, Russian Federation
Tver State Technical University, Tver, Russian Federation

EDITORIAL BOARD AND PUBLISHER OFFICE ADDRESS
Nikolay Korytkov Ave, 3а, Tver, 170024, Russian Federation
Phone: (482-2) 39-91-49 Fax: (482-2) 39-91-00
E-mail: red@cps.tver.ru
Website: www.swsys.ru

Release date 16.09.2023
Printed in printing-office "Faktor i K" Krylova St. 26, Tver, 170100, Russian Federation Published quarterly. 36 th year of publication Format 60x84 1/8. Circulation 1000 copies Prod. order № 15. Wordage 160 pages. Price 550,00 rub.

стр. 3

Вниманию авторов

Журнал «Программные продукты и системы» публикует материалы научного и научно-практического характера по новым информационным технологиям, результаты академических и отраслевых исследований в области использования средств вычислительной техники. Практикуются выпуски тематических номеров по искусственному интеллекту, системам автоматизированного проектирования, по технологиям разработки программных средств и системам защиты, а также специализированные выпуски, посвященные научным исследованиям и разработкам отдельных вузов, НИИ, научных организаций.
Журнал «Программные продукты и системы» внесен в Перечень ведущих рецензируемых научных журналов и изданий, в которых должны быть опубликованы основные научные результаты диссертаций на соискание ученых степеней кандидата и доктора наук.
Информация об опубликованных статьях по установленной форме регулярно предоставляется в систему РИНЦ, в CrossRef и в другие базы и электронные библиотеки.
Журнал «Программные продукты и системы» включен в ядро коллекции РИНЦ, размещенное на платформе Web of Science в виде базы данных RSCI.
Автор статьи отвечает за подбор, оригинальность и точность приводимого фактического материала. При перепечатке ссылка на журнал обязательна. Статьи публикуются бесплатно.
Условия публикации
К рассмотрению принимаются оригинальные материалы, отвечающие редакционным требованиям и соответствующие тематике журнала. Группы научных специальностей:
1.2. Компьютерные науки и информатика
1.2.1. Искусственный интеллект и машинное обучение (физико-математические науки).
1.2.2. Математическое моделирование, численные методы и комплексы программ (физико-математические науки, технические науки)
2.3. Информационные технологии и телекоммуникации
2.3.1. Системный анализ, управление и обработка информации, статистика (технические науки, физикоматематические науки).
2.3.2. Вычислительные системы и их элементы (технические науки).
2.3.3. Автоматизация и управление технологическими процессами и производствами (технические науки).
2.3.5. Математическое и программное обеспечение вычислительных систем, комплексов и компьютерных сетей (технические науки, физико-математические науки).
2.3.6. Методы и системы защиты информации (технические науки, физико-математические науки).
2.3.7. Компьютерное моделирование и автоматизация (технические науки, физико-математические науки).
2.3.8. Информатика и информационные процессы (технические науки).
Работа представляется в электронном виде в формате Word. Объем статьи вместе с иллюстрациями - не менее 10 000 знаков. Диаграммы, схемы, графики должны быть доступными для редактирования (Word, Visio, Excel). Заголовок должен быть информативным; сокращения, а также терминологию узкой тематики желательно в нем не использовать. Количество авторов на одну статью - не более 4, количество статей одного автора в номере, включая соавторство, - не более 2. Список литературы, наличие которого обязательно, должен включать не менее 10 пунктов.
Необходимы также содержательная структурированная аннотация (не менее 250 слов), ключевые слова (7-10) и индекс УДК. Название статьи, аннотация и ключевые слова должны быть переведены на английский язык (машинный перевод недопустим), а фамилии авторов, названия и юридические адреса организаций (если нет официального перевода) - транслитерированы по стандарту BGN/PCGN.
Вместе со статьей следует прислать экспертное заключение о возможности открытого опубликования материала и авторскую справку. Обзательно соблюдение автором договора (публичной оферты).
Порядок рецензирования
Все статьи, поступающие в редакцию (соответствующие тематике и оформленные согласно требованиям к публикации), подлежат двойному слепому рецензированию в течение месяца с момента поступления, рецензия отправляется авторам.
В редакции сформирован устоявшийся коллектив рецензентов, среди которых члены редколлегии журнала, эксперты из числа крупных специалистов в области информатики и вычислительной техники ведущих вузов страны, а также ученые и специалисты НИИСИ РАН, МСЦ РАН (г. Москва) и НИИ «Центрпрограмм-систем» (г. Тверь).
Редакция журнала «Программные продукты и системы» в своей работе руководствуется сводом правил Кодекса этики научных публикаций, разработанным и утвержденным Комитетом по этике научных публикаций (Committee on Publication Ethics - COPE).

стр. 4

Программные продукты и системы /Software & Systems

36(3), 2023

УДК 004.42 doi: 10.15827/0236-235X.142.349-360 2023. Т. 36. № 3. С. 349-360

Построение совершенных нормальных форм булевых функций для схемотехнических реализаций протоколов аутентификации с использованием Maple

А.А. Оленев
И.А. Калмыков
К.А. Киричек
Ссылка для цитирования
Оленев А.А., Калмыков И.А., Киричек К.А. Построение совершенных нормальных форм булевых функций для схемотехнических реализаций протоколов аутентификации с использованием Maple // Программные продукты и системы. 2023. Т. 36. № 3. С. 349-360. doi: 10.15827/0236-235X.142.349-360
Информация о статье
Поступила в редакцию: 15.03.2023 После доработки: 02.05.2023 Принята к публикации: 17.05.2023

Аннотация. Одной из перспективных областей применения дискретной математики являются протоколы аутентификации с нулевым разглашением знаний, построенные на основе модулярных кодов класса вычетов. Использование этих кодов позволяет заменить вычислительное устройство, реализующее операцию возведения в степень по модулю, на кодопреобразователь. В результате сложная вычислительная операция будет выполнена за один такт. Эффективность работы кодопреобразователей во многом зависит от правильности перехода от таблицы истинности к совершенным нормальным формам булевых функций. Авторами данной статьи разработаны программный код и графическое интерактивное приложение для ЭВМ, которое позволяет получать совершенные дизъюнктивные и (или) совершенные конъюнктивные нормальные формы согласно описанному пользователем содержанию таблиц истинности и выводить результат в соответствующем поле с использованием логических функций библиотеки Logic или в виде формулы. Совершенные формы можно получить с использованием описания таблицы истинности в виде минтермов (макстермов) булевой функции, а также номеров наборов минтермов (макстермов). В разработанном приложении существует возможность выбора типа получаемой совершенной формы, и оно содержит справочные данные по использованию. Программный код и весь графический интерфейс написаны с помощью встроенного языка и библиотек системы компьютерной алгебры Maple. Созданное интерактивное приложение интуитивно понятно и доступно даже непрофессиональным программистам (преподавателям математики, студентам). Для удобства программный код оформлен в виде графического приложения, требующего для работы установленной на компьютере системы Maple. Разработанное приложение может быть использовано образовательными организациями, в которых преподаются математическая логика, дискретная математика или их разделы.
Ключевые слова: математическая логика, булевы функции, совершенные дизъюнктивные и конъюнктивные нормальные формы, системы компьютерной алгебры, Maple
Благодарности. Исследование выполнено за счет гранта РНФ № 23-21-00036

Появление низкоорбитальных систем спутникового Интернета делает достаточно актуальной проблему аутентификации космических аппаратов. Это связано с тем, что увеличение числа их группировок (например, Starlink содержит более 2 000 спутников) приводит к повышению вероятности навязывания неавторизованного контента чужим спутником. Для предотвращения такого деструктивного воздействия в работах [1, 2] предлагается использовать систему опознавания космических аппаратов, построенную на основе протокола аутентификации с нулевым разглашением знаний. В этом протоколе проверяющий (запросчик) генерирует сигнал-вопрос, который передается претенденту (ответчику). В зависимости от полученного сигнала-вопроса претендент вычисляет ответ и передает его проверяющему. Запросчик проверяет данный ответ. Если он правильный, претендент считается авторизованным абонентом. Для обеспечения

высокой имитостойкости к подбору правильного ответа в этих протоколах применяются операции возведения в степень по модулю Q. Так как в качестве модуля используются большие простые числа, на выполнение операций с ними требуются значительные временные затраты. В результате увеличивается интервал, в течение которого злоумышленник может подбирать правильный ответ. Уменьшить временные затраты на опознание спутника можно за счет использования модулярных кодов классов вычетов (МККВ), являющихся арифметическими [3-5]. Для построения МККВ выбираются простые числа p 1, p 2, ..., pn, для которых справедливо
Р1 < p 2< ...< Pn. (1)
Это основания модулярного кода. Их произведение определяет диапазон МККВ: п
Рп = П Pi. (2)
i=1

349

стр. 5

Программные продукты и системы / Software & Systems

36(3), 2023

    Тогда любое целое число A < Pn можно однозначно представить в виде набора остатков, получаемых при делении числа А на основания МККВ,
    A = (ai, a2, ..., an),                (3)
где ai = A mod pi, i = 1, ..., n.
    В МККВ модульные операции можно свести к соответствующим операциям над остатками. Пусть заданы два простых числа: A = = (ai, a2, ..., an) и W = (w 1, w2, ..., wₙ). Тогда для операций сложения, вычитания и умножения

справедливо
   А + W = ((а + w )modpT,...,
   ⁽ап + wn )mod Pn ),

    А - W = ((а - w )modpₓ,..., ⁽ап — wn ⁾mod Pn ),

(4)

(5)

   А■W =⁽⁽а ■ wi⁾modд,...,              ,,ч
   z     .  .  .                        ⁽⁶⁾
   ⁽an ■ wn ⁾mod Pn ),
где wi = Wmod p,, i = 1, ..., n.
   Использование модулярного кода классов вычетов позволяет повысить скорость выполнения модульных операций. Анализ выражений (4)-(6) показывает, что в МККВ вычисления выполняются параллельно по основаниям кода. Рассмотрим это на примере. Пусть заданы основания МККВ p 1 = 2, p 2 = 3, p 3 = 5. Рабочий диапазон равен 30. Выполним операцию умножения двух чисел:
   A = 4 = (0, 1, 4) и W = 7= (1, 1, 2).
   Получаем
   A ■ W = ((0 ■ 1)mod2, (1 ■ 1)mod3, (4 ■ 2)mod5) = = (0, 1, 3) = 28.
   Разрядность операндов-остатков a 1, a 2, ..., an значительно меньше самого числа А, что

также позволяет повысить скорость вычислений. Например, если в качестве оснований МККВ взять шестиразрядные простые числа p 1 = 37, p 2 = 41, p 3 = 43, p 4 = 47, p 5 = 53, p 6 = 59, p7 = 61, то рабочий диапазон МККВ Pn = = 584803025179. Тогда число A = 584803025170 можно представить в виде набора остатков МККВ: A = (28, 32, 34, 38, 44, 50, 52). В этом случае 40-разрядное число представляется в виде набора шестиразрядных остатков. Очевидно, что использование МККВ позволяет повысить скорость выполнения модульных операций.
   Тогда, подобрав основания МККВ так, чтобы выполнилось условие Pn > Q, операцию вычисления истинного статуса спутника в протоколе аутентификации [2]
   C = gUgS [ j] gT[ j ]mod Q         (7)

можно заменить на n параллельных вычислений в МККВ:
     С = g U¹ g S¹[j ] g T1[j ] mod Pi,
    < С2 = gU²gS²[j]gT²[j] modp₂,


     ч С = g Un g Sn [j ] gTn [j ] mod Pn,

где U, S[7'], T[j'] - секретные параметры протокола на j-м сеансе аутентификации; g - порождающий элемент мультипликативной группы по модулю pi; Ui = Umod pi, S [j' ] = S [j' ]mod pi, T[j' ] = T[j' ]mod pi, i = 1, ..., n.
   Дальнейшего снижения временных затрат на аутентификацию космического аппарата можно достичь за счет использования вместо вычислительного устройства, выполняющего операцию возведения в степень по модулю pi, кодопреобразователя. Если на его вход подать значение показателя степени, например Si [j'], то на выходе получим значение gSⁱ [j] mod p,, где i = 1, ..., n. Пусть в качестве основания МККВ выбрано число p 1 = 11. Для данного модуля порождающим элементом мультипликативной группы можно взять g = 2. Пусть S 1 [j' ] = 5. Используя вычислительное устройство, получаем gS¹ [ j] mod p = 25 modi 1 = 10.
   Эту мультипликативную операцию можно выполнить с помощью кода преобразователя. Если на его вход подать число 5, то на выходе кодопреобразователя появится число 10. В данном случае операция возведения в степень по модулю выполнится за один такт.
   Однако для разработки такого преобразователя необходимо грамотно использовать методы дискретной математики. Освоение разделов дискретной математики и математической логики предполагает изучение таких тем, как множества, математическая индукция, математическая логика, отношения, функции, анализ алгоритмов, теория графов, комбинаторика, теория вероятностей, рекуррентные соотношения [6-8]. Усвоение этих разделов позволяет понять и решить задачу синтеза кодопреобразователя, которая состоит в построении схемы для заданной булевой функции или системы булевых функций на основе определенной системы логических элементов. Как правило, исходное описание для синтеза схемы задается либо в виде таблицы истинности, либо в аналитической форме в виде формулы [9]. При решении задачи синтеза комбинационной схемы, реализующей заданную булеву функцию, предварительно производятся минимизация

350

стр. 6

Программные продукты и системы /Software & Systems

36(3), 2023

булевой функции и дальнейшее упрощение минимальной формы путем факторизации и декомпозиции [10, 11]. Комбинационная схема строится в заданном базисе [12]. Вопросы построения и оптимизации функциональноструктурных описаний цифровых устройств рассмотрены в [13]. Методы, алгоритмы и программы решения задач минимизации дизъюнктивных нормальных форм (ДНФ) представлений булевых функций, которые широко используются при проектировании цифровых систем для уменьшения сложности (площади кристаллов) функциональных комбинационных блоков, рассмотрены, например, в [14, 15].
   Анализ источников и задачи синтеза кодопреобразователя (комбинационной схемы) показывает необходимость построения совершенных дизъюнктивных нормальных форм (СДНФ) или совершенных конъюнктивных нормальных форм (СКНФ) по таблицам истинности, являющихся одним из наиболее наглядных элементов формальной логики и одной из возможных форм представления функционирования комбинационного аппарата.
   То есть необходимо получить ДНФ (КНФ), называемую канонической или совершенной, причем все ее элементарные конъюнкции (дизъюнкции) являются конституентами единицы (нуля). При этом элементарные конъюнкции (дизъюнкции) называются конституентами единицы (нуля), если содержат в прямом или инверсном виде все переменные, являющиеся аргументами булевой функции [9].
   Для решения задач дискретной математики и математической логики можно использовать средства вычислительной техники: так, вопросы использования методов дискретной математики и описания важнейших алгоритмов на дискретных структурах изложены в [16-18].
   Для работы с элементами логики и булевой алгебры и их изучения можно использовать систему компьютерной алгебры Maple [8, 19, 20]. Эта система универсальна, гибка в использовании, одна из немногих, имеющих свою библиотеку для работы с булевыми функциями Logic, которая позволяет наглядно представить построение таблиц истинности (соответствия) и исследовать логическую эквивалентность составных высказываний. Однако библиотека Logic не имеет встроенных функций, позволяющих описать минтерм или макстерм и, соответственно, получить СДНФ или СКНФ согласно запросу пользователя.
   Таким образом, несмотря на очевидную полезность и необходимость функций библио

теки Logic, система не предусматривает описания таблицы истинности, а результаты преобразований составных высказываний выдает в упрощенном виде, который не всегда совпадает с совершенными формами.
   В связи с этим предлагается программное решение, позволяющее развить систему Maple, а точнее - ее библиотеку Logic. Его использование в процессе обучения будет способствовать улучшению понимания обучающимися построения для булевых функций СДНФ и СКНФ, а также позволит изучать дискретную математику, математическую логику и другие дисциплины с использованием системы компьютерной алгебры.
   Исследования по созданию программных кодов для изучения математической логики проводят как отечественные [21, 22], так и зарубежные [23-25] специалисты. В работе [22] представлены исходные коды для изучения различных разделов дискретной математики в виде программных рабочих листов, в том числе и булевой алгебры, и исследованы основные тенденции использования системы компьютерной алгебры Maple по компьютерному экспериментированию в дискретной математике. Описаны методы доказательств законов теории множеств, получения СДНФ и СКНФ, а также предложена программная реализация этих и других методов, используемых в дискретной математике. В работе [24] представлена модификация программного исходного кода для построения СДНФ и СКНФ без упрощений. Программный код реализован на языке программирования универсальной системы компьютерной алгебры Mathematica. Это сделано, чтобы помочь студентам, изучающим дискретную математику, лучше понять процесс построения и использования булевых функций.
   Сегодня существуют приложения для получения СДНФ и СКНФ, написанные практически на всех популярных языках программирования, однако получение СДНФ и СКНФ по таблице истинности или в числовой форме для создания различных схемотехнических решений, в том числе и кодопребразователей, не рассматривается. В данной статье представлен способ создания исходного кода программы и интерактивного приложения для построения СДНФ и СКНФ [21, 26], полностью написанного в среде системы Maple с помощью библиотеки Maplet.
   Разработанное в Maple приложение для персонального компьютера может помочь полу

351

стр. 7

Программные продукты и системы / Software & Systems

36(3), 2023

чить СДНФ и СКНФ по таблице истинности двумя способами:
   -    с помощью первоначального описания макстермов или минтермов в виде набора логических констант true или false;
   -    используя десятичные номера макстермов или минтермов (в числовой форме).
   Таким образом, цифровизация всех сфер жизни, в частности, образования, обусловливает актуальность создания исходного кода программы и интерактивных приложений с простым и понятным интерфейсом для выполнения разнообразных задач.

Разработка процедур нахождения СДНФ и СКНФ

   Для получения СДНФ или СКНФ в системе Maple были созданы функции для описания минтерма или макстерма в выбранной форме, входящих в СДНФ или СКНФ соответственно, а затем выполнены дизъюнкция или конъюнкция описанных макстермов или минтермов соответственно. Рассмотрим порядок нахождения СДНФ.
   1. Описание макстерма или минтерма с использованием констант true или false.
   Процедура Описание_таблицы_истинно-ctu_SDNF позволяет выполнять нахождение СДНФ по предъявленному условию - описание минтермов с использованием констант true или false.
   Данная процедура состоит из двух частей: непосредственно нахождения минтерма и объединения полученных макстермов.
   Аргументами для процедуры нахождения минтерма являются описание строки таблицы истинности (представленной с использованием констант true или false), принимающей значение true, и наименования используемых переменных. Чтобы создать minterm, связанный с элементом таблицы истинности, сначала инициализируется minterm, равный NULL. Затем в цикле for с переменной цикла i и диапазоном для всех используемых переменных проверяется, принимает ли описываемая переменная истинностное значение true или false. Если переменная имеет значение true, то minterm обновляется, объединяясь с именем соответствующей переменной. Если запись имеет значение false, то minterm обновляется, формируя конъюнкцию с отрицанием переменной. Итогом работы цикла является соответствующий minterm:
   Описание_минтерма:=ргос(row::
::list(truefalse),nep::list(symbol))% получение минтерма

   local минтерм, i; % используемые пе-
ременные
   uses Logic;
     if nops(row) <> nops(пер) then error "Проверьте правильность указания количества переменных";
     end if;
   минтерм := NULL;  % получение описан-
ного минтерма
      for i from 1 to nops(row) do if row[i] then
        минтерм:= минтерм &and пер[±]; else
        минтерм:= минтерм &and &not (перШ);
      end if; end do; return минтерм; end proc:

   Для завершения разработки СДНФ необходимо сформировать дизъюнкцию minterm, созданную процедурой Описание_минтерма. Вторая часть процедуры - Описание_таб-лицы_истинности_SDNF - использует в качестве аргументов описание строк таблицы истинности, принимающих значения true и описанных с использованием констант true или false, и наименования используемых переменных. Сначала проверяется, не был ли переданный набор пустым. Если да, то возвращается выражение false. Если аргументы заданы правильно, то инициализируется результат NULL. Для каждого необходимого элемента таблицы истинности вызывается процедура Описа-ние_минтерма и с помощью оператора &or (операция «или») выходные данные этой процедуры добавляются к имеющемуся результату:

   > Описание_таблицы_истинности_SDNF:= proc(T::set(list(true-
false)),переменные::list(symbol))
   local Накопление, значения, форма; % используемые переменные
    if T =  {} then % проверка наличия
описания функции return false;
    end if;
   Накопление:= NULL; %    формирование
СДНФ
     for значения in T do
       форма:= Описание_минтерма(значе-ния,переменные);
       Накопление:= Накопление &or форма; end do; return Накопление;
    end proc:

   Разработанная процедура нахождения СКНФ отличается только порядком нахождения макстерма (используется операция дизъ

352

стр. 8

Программные продукты и системы /Software & Systems

36(3), 2023

юнкции в системе Maple - &or) и операцией накопления результатов макстермов, то есть необходимо произвести замену операции дизъюнкции (в системе Maple - &or) на операцию конъюнкции (в системе Maple - &and).
   2.   Описание макстерма или минтерма в форме номера набора.
   Для нахождения СКНФ или СДНФ по номерам наборов дополнительно используется перевод в вид описания минтермов или макстермов с использованием констант true или false, рассмотренный ранее. Приведем фрагмент программного кода, отвечающего за данный перевод:

   > число:= ListTools:-Reverse(con-vert(x,base,2));
       m:= nops(число); % определение необходимого числа разрядов в минтерме (макстерме)
       k:= nops(пер); % определение числа используемых переменных
         if m > k then error "Требуется %d цифр", m end if;  % определение необ-
ходимого числа разрядов
           A: = [0 $ (k-m), op(число)]; %
заполнение значением «нуль» избыточных разрядов
         for j to nops (A) do % представление числа с использованием констант true, false
            if A[j]=1 then A:=subsop (j=true,A) else A:=subsop(j=false,A); end if;
         end do:

   Данная процедура обеспечивает следующие преобразования:
   -    перевод десятичного числа (номера набора) в двоичный вид;
   -    проверка соответствия необходимого числа разрядов (строк в таблице истинности) и количества разрядов полученного числа; в случае несоответствия (меньшего числа разрядов при представлении числа в двоичном виде) заполнение недостающих позиций значениями «нуль»;
   -    представление двоичного числа с применением констант true или false, используя цикл for.
   Таким образом, процедура, приведенная выше, позволяет преобразовать десятичное число в описание двоичного числа, представленного с использованием констант true или false. Полученные значения могут применяться в качестве первого аргумента процедуры Опи-сание_таблицы_истинности_SDNF, а значит, можно получить и СДНФ, порядок получения которой описан выше.


        Среда разработки

   Современные компьютерные технологии, в том числе и система Maple, позволяют решать разнообразные задачи как дискретной математики, так и математической логики. В большинстве случаев демонстрацию решения конкретной задачи можно упростить, используя windows-приложения оконной, а не консольной категории. Система Maple позволяет создавать такие оконные приложения, поскольку имеет широкий спектр компонентов, направленных на создание графического интерфейса, обладающего функциональными возможностями, аналогичными системам визуального программирования. Эти возможности обеспечиваются использованием библиотеки Maplet. Встроенный высокоуровневый язык математических расчетов Maple дает возможность применять встроенные решения для создания новых приложений. Задачей авторов данного исследования являлось написание интерактивного приложения, полностью созданного в рамках этой программной среды, с графическим интерфейсом, выдающим СДНФ или СКНФ по выбору пользователя при вводе данных, описывающих таблицу истинности (соответствия).
   Эта задача была успешно решена. Программный код написан на языке Maple с использованием библиотеки Maplet и представляет собой отдельное приложение в формате Maplets. Процедура получения СДНФ или СКНФ выглядит следующим образом. После запуска программного кода появляется графический интерфейс, обеспечивающий выбор описания исследуемой таблицы истинности, то есть окно графического интерфейса, в котором нужно выбрать форму описания таблицы истинности (соответствия). Исходное положение представлено на рисунке 1. Нажатие кнопки «Описание наборов» или «Номера наборов» обеспечивает выбор формы описания таблицы истинности. Далее производится переход на один из выбранных Maplets, позволяющих внести данные из таблицы истинности (соответствия) и выбрать представляемую форму (рис. 2). Генерация самой формы производится по нажатии кнопки «Получить». Интерфейс пользователя имеет максимально удобный минималистичный вид. Пользователь вводит в соответствующее поле необходимые данные описания минтерма или макстерма, количество переменных, от которых зависит булева функция, а также выбирает вид представляемой


353

стр. 9

Программные продукты и системы / Software & Systems

36(3), 2023

Рис. 1. Общий вид Maplets для получения СДНФ или СКНФ по таблице истинности

Fig. 1. General view of maplets for obtaining SDNF or SKNF according to the truth table

Рис. 2. Пример получения СДНФ для таблицы истинности булевой функции двух переменных для случая 1

Fig. 2. An example of obtaining SDNF for the truth table of a Boolean function of two variables for the case 1

функции. Далее нажимает кнопку «Получить». В итоге появляется представление выбранной формы.
В таблице 1 показан пример ввода данных.

Таблица 1
Таблица истинности
Table 1

A truth table

№ набора а b F(a, b )
0 false false false
1 false true true
2 true false true
3 true true false

Значения для ввода формируются следующим образом.
Для первого случая (получение СДНФ с использованием описания минтерма в виде логи

ческих переменных true, false) используемые переменные a и b представляются в виде логических констант: первый набор - [false, true], второй набор - [true, false]. Итог выполнения программного кода представлен на рисунке 2.
Для второго случая (получение СДНФ по номерам наборов) используемые переменные остаются прежними - a и b, номера наборов -[1, 2]. Итог выполнения программного кода представлен на рисунке 3.
Итоговые значения совпадают, что подтверждает правильность разработанных функций. Получение СКНФ осуществляется аналогичным способом.
Опишем подробнее применяемые команды для выбора необходимого представления.
Нажатием кнопки «Описание наборов» открывается Maplet «Maplet построения СКНФ или СДНФ по таблице истинности (по описанию наборов в виде true или false)».

354

стр. 10