RUS  ENG
Полная версия
ЖУРНАЛЫ // Дискретная математика // Архив

Дискрет. матем., 2024, том 36, выпуск 2, страницы 3–10 (Mi dm1817)

Оценка длин тестов в базисе Жегалкина при константных неисправностях типа «1» на выходах элементов

Ю. В. Бородина

ИПМ им. М.В. Келдыша РАН

Аннотация: Для булевых функций $f$ специального вида получена оценка сверху длины $D(f)$ полного проверяющего теста при их реализации схемами из функциональных элементов в базисе Жегалкина в случае константных неисправностей типа «1» на выходах элементов. Как следствие получается оценка $D(f)\le \frac{n^{k-1}}{(k-2)!}+1$ для функций $f$ от $n\ge k$ переменных, у которых многочлен Жегалкина имеет степень не выше $k$.

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

УДК: 519.718.7

Статья поступила: 16.02.2024

DOI: 10.4213/dm1817



© МИАН, 2025