О единичных проверяющих тестах для формул в некоторых базисах при константных неисправностях на выходах функциональных элементов

Аннотация

В работе исследуется длина единичного проверяющего теста при константных неисправностях на выходах элементов в булевых формулах. Для трёх базисов, близких к стандартному, установлена асимптотическая верхняя оценка функции Шеннона. Для базисов «стрелка Пирса» и «штрих Шеффера» получены растущая нижняя оценка этой функции, а также выраженная через ранг формулы верхняя оценка длины минимального теста. Показано, что не всякая булева функция допускает неизбыточную реализацию над последними двумя базисами.

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

BibTeX
@article{IS-Cui-Romanov2026,
  author  = {Цуй, Чжэнюй and Романов, Дмитрий Сергеевич},
  title   = {{О единичных проверяющих тестах для формул в некоторых базисах при константных неисправностях на выходах функциональных элементов}},
  journal = {Интеллектуальные системы. Теория и приложения},
  year    = {2026},
  volume  = {30},
  number  = {4},
  pages   = {232--235},
}
AMSBIB
\RBibitem{IS-Cui-Romanov2026}
\by Ч.~Цуй, Д.\,С.~Романов
\paper О единичных проверяющих тестах для формул в некоторых базисах при константных неисправностях на выходах функциональных элементов
\jour Интеллектуальные системы. Теория и приложения
\yr 2026
\vol 30
\issue 4
\pages 232--235
Опубликовано на условиях лицензии Creative Commons Attribution 4.0 International (CC BY 4.0)

← К номеру журнала

× Issue cover