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

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

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



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






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


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

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

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

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

Аннотация: Рассматривается проблема сравнения булевых базисов. В данном случае базисы сравниваются по сложности представлений булевых функций термами (формулами). На множестве всех базисов вводится определенным образом частичный порядок, относительно которого получается структура классов эквивалентности базисов. Известно, что критерием эквивалентности двух базисов является взаимная бесповторная выразимость функций одного базиса через функции другого, а добавление к базису слабоповторной в нем функции позволяет не только расширить его, увеличивая возможности по реализации булевых функций термами, но и делает расширение минимальным, позволяя исследовать базисы по сложности представлений булевых функций термами. Таким образом, задача описания структуры классов эквивалентности базисов свелась к нахождению слабоповторных функций в конкретных базисах.
Базис $\{\vee,\cdot,-,0,1\}$ является наибольшим элементом при этом частичном порядке, а класс эквивалентности этого базиса образует нулевой ярус структуры. Усилиями нескольких авторов были получены описание базисов первого яруса и частичное описание базисов второго. В этой статье дано описание слабоповторных булевых функций в одной базисе в терминах обобщенной однотипности, которое завершает описание базисов второго яруса.

Ключевые слова: булева функция, терм, бесповторная функция, слабоповторная функция, базис.

Полный текст: PDF файл (312 kB)
Список литературы: PDF файл   HTML файл

Тип публикации: Статья
УДК: 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}


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

    ОТПРАВИТЬ: 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
  • Просмотров:
    Эта страница:60
    Полный текст:25
    Литература:31

     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2019