RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Известия Иркутского государственного университета. Серия Математика:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Известия Иркутского государственного университета. Серия Математика, 2016, том 16, страницы 30–42 (Mi iigum259)  

Эта публикация цитируется в 1 научной статье (всего в 1 статье)

Сложность представлений многовыходных функций алгебры логики

С. Ф. Винокуров, А. С. Францева

Иркутский государственный университет

Аннотация: В работе исследуется вопрос сложности логических схем, реализующих функции алгебры логики. Реализация функций алгебры логики рассматривается в классе логических схем, называемых обратимыми. Для построения обратимых схем используются элементарные обратимые схемы, известные под названием элементов Тоффоли. За исключением двух функций одного аргумента, все функции алгебры логики не являются обратимыми. Однако их можно моделировать так называемыми многовыходными функциями, у которых число выходов совпадает с числом аргументов и которые являются перестановками на множестве наборов аргументов. В работе использовано представление функций алгебры логики многовыходными функциями. Многовыходные функции, в свою очередь, реализованы обратимыми схемами в базисе Тоффоли. Для функции схема, ее реализующая, не определена однозначно. Это позволяет определить сложность функции, как сложность минимальной схемы, реализующей эту функцию. В представленных результатах решена задача нахождения сложности самой сложной функции или функции Шеннона для класса всех функций алгебры логики в классе обратимых схем в подмножестве базиса Тоффоли. Решение этой задачи сведено к решению задачи нахождения функции Шеннона для класса булевых функций в классе полиномиальных форм, называемых расширенными полиномами Жегалкина. Для решения задачи нахождения функции Шеннона для класса булевых функций в классе расширенных полиномов Жегалкина построены последовательности множеств функций по количеству аргументов. Для функций в этих множествах найдена сложность их полиномиальных представлений и доказано, что эти функции имеют максимальную сложность среди всех функций в классе расширенных полиномов Жегалкина.

Ключевые слова: функции алгебры логики, многовыходные функции, обратимые функции, элементы Тоффоли, обратимые схемы, сложность, полином Жегалкина.

Финансовая поддержка Номер гранта
Министерство образования и науки Российской Федерации RFMEFI57914X0092
Работа выполнена в рамках проекта 14.579.21.0092 ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технического комплекса России на 2014–2020 годы, № RFMEFI57914X0092.


Полный текст: PDF файл (267 kB)
Список литературы: PDF файл   HTML файл
Тип публикации: Статья
УДК: 519.673
MSC: 94C10

Образец цитирования: С. Ф. Винокуров, А. С. Францева, “Сложность представлений многовыходных функций алгебры логики”, Известия Иркутского государственного университета. Серия Математика, 16 (2016), 30–42

Цитирование в формате AMSBIB
\RBibitem{VinFra16}
\by С.~Ф.~Винокуров, А.~С.~Францева
\paper Сложность представлений многовыходных функций алгебры логики
\jour Известия Иркутского государственного университета. Серия Математика
\yr 2016
\vol 16
\pages 30--42
\mathnet{http://mi.mathnet.ru/iigum259}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/iigum259
  • http://mi.mathnet.ru/rus/iigum/v16/p30

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles

    Эта публикация цитируется в следующих статьяx:
    1. А. С. Францева, “Алгоритм минимизации функций алгебры логики в классе обратимых схем Тоффоли”, Известия Иркутского государственного университета. Серия Математика, 25 (2018), 144–158  mathnet  crossref
  • Просмотров:
    Эта страница:104
    Полный текст:29
    Литература:15
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019