|
Известия Иркутского государственного университета. Серия «Математика», 2016, том 15, страницы 92–107
(Mi iigum255)
|
|
|
|
Об одной серии базисов для множества булевых функций
И. К. Шаранхаев Бурятский государственный университет
Аннотация:
Рассматривается проблема сравнения булевых базисов. В данном случае базисы сравниваются по сложности представлений булевых функций термами (формулами).
На множестве всех базисов
вводится определенным образом частичный порядок, относительно которого получается структура классов эквивалентности базисов.
Известно, что критерием эквивалентности двух базисов является взаимная бесповторная выразимость функций одного базиса через функции другого,
а добавление к базису слабоповторной в нем функции
позволяет не только расширить его, увеличивая возможности по реализации
булевых функций термами, но и делает расширение минимальным, позволяя
исследовать базисы по сложности представлений булевых функций термами.
Таким образом, задача описания структуры классов эквивалентности базисов свелась к нахождению слабоповторных функций в конкретных базисах.
Базис $\{\vee,\cdot,-,0,1\}$ является наибольшим элементом при этом частичном порядке, а класс эквивалентности этого базиса образует нулевой ярус структуры.
Усилиями нескольких авторов были получены описание базисов первого яруса и частичное описание базисов второго.
В этой статье дано описание слабоповторных булевых функций в одной базисе в терминах обобщенной однотипности,
которое завершает описание базисов второго яруса.
Ключевые слова:
булева функция, терм, бесповторная функция, слабоповторная функция, базис.
Образец цитирования:
И. К. Шаранхаев, “Об одной серии базисов для множества булевых функций”, Известия Иркутского государственного университета. Серия Математика, 15 (2016), 92–107
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/iigum255 https://www.mathnet.ru/rus/iigum/v15/p92
|
Статистика просмотров: |
Страница аннотации: | 213 | PDF полного текста: | 279 | Список литературы: | 69 |
|