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

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

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



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






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


Известия Иркутского государственного университета. Серия «Математика», 2016, том 15, страницы 92–107 (Mi iigum255)  

Об одной серии базисов для множества булевых функций

И. К. Шаранхаев

Бурятский государственный университет
Список литературы:
Аннотация: Рассматривается проблема сравнения булевых базисов. В данном случае базисы сравниваются по сложности представлений булевых функций термами (формулами). На множестве всех базисов вводится определенным образом частичный порядок, относительно которого получается структура классов эквивалентности базисов. Известно, что критерием эквивалентности двух базисов является взаимная бесповторная выразимость функций одного базиса через функции другого, а добавление к базису слабоповторной в нем функции позволяет не только расширить его, увеличивая возможности по реализации булевых функций термами, но и делает расширение минимальным, позволяя исследовать базисы по сложности представлений булевых функций термами. Таким образом, задача описания структуры классов эквивалентности базисов свелась к нахождению слабоповторных функций в конкретных базисах.
Базис $\{\vee,\cdot,-,0,1\}$ является наибольшим элементом при этом частичном порядке, а класс эквивалентности этого базиса образует нулевой ярус структуры. Усилиями нескольких авторов были получены описание базисов первого яруса и частичное описание базисов второго. В этой статье дано описание слабоповторных булевых функций в одной базисе в терминах обобщенной однотипности, которое завершает описание базисов второго яруса.
Ключевые слова: булева функция, терм, бесповторная функция, слабоповторная функция, базис.
Тип публикации: Статья
УДК: 519.71
MSC: 06E30
Образец цитирования: И. К. Шаранхаев, “Об одной серии базисов для множества булевых функций”, Известия Иркутского государственного университета. Серия Математика, 15 (2016), 92–107
Цитирование в формате AMSBIB
\RBibitem{Sha16}
\by И.~К.~Шаранхаев
\paper Об одной серии базисов для множества булевых функций
\jour Известия Иркутского государственного университета. Серия Математика
\yr 2016
\vol 15
\pages 92--107
\mathnet{http://mi.mathnet.ru/iigum255}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/iigum255
  • https://www.mathnet.ru/rus/iigum/v15/p92
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Статистика просмотров:
    Страница аннотации:213
    PDF полного текста:279
    Список литературы:69
     
      Обратная связь:
     Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025