RUS  ENG
Полная версия
ЖУРНАЛЫ // Интеллектуальные системы. Теория и приложения // Архив

Интеллектуальные системы. Теория и приложения, 2019, том 23, выпуск 3, страницы 41–55 (Mi ista237)

Часть 2. Специальные вопросы теории интеллектуальных систем

О весе функций, заданных бесповторными И/ИЛИ формулами

А. Р. Еременко, А. Д. Яшунский


Аннотация: Рассматривается множество функций, заданных бесповторными формулами с бинарными операциями конъюнкции (логического И) и дизъюнкции (логического ИЛИ). Для функций, заданных формулами с фиксированным числом операций, исследуются значения весов — числа наборов, на которых функция принимает значение 1. Найдены асимптотические оценки для числа бесповторных формул, задающих функции с весом из определенных диапазонов, в частности, — числа формул, задающих функции, у которых доля единиц среди значений не превышает четверти.

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



© МИАН, 2024