В работе рассматривается вопрос сложности проверяющих тестов относительно бесповторной альтернативы для бесповторных булевых функций, существенно зависящих от своих переменных. Известно, что большинство неисправностей в схемах функциональных элементов, реализующих бесповторные булевы функции, приводит к новой схеме, реализующей также бесповторную функцию. Построение проверяющих тестов относительно бесповторной альтернативы для бесповторных булевых функций осуществляется на основе квадратов существенности. В работе получено точное значение функции Шеннона для тестов относительно бесповторной альтернативы в базисе {¬, ∨, &, ⊕}. Также представлен алгоритм получения проверяющего теста для любой бесповторной булевой функции, имеющий сложность O(n₃).

1. ВороненкоА.A. Опроверяющихтестахдлябесповторныхфункций/ А.A. Вороненко // Математические вопросы кибернетики. — 2002. — Вып 11. — С. 163–176.

2. Вороненко А. А. О длине проверяющего теста для бесповторных функций в базисе {0,1, &,;∨, ¬} /А.А. Вороненко// Дискретнаяматематика. —2005. — Том 17. Выпуск 2. — С. 139–143.

3. Избранные вопросы теории булевых функций: Монография / А. С. Балюк,С. Ф. Винокуров, А. И. Гайдуков и др. Под ред. С. Ф. Винокурова, Н. А. Перязева. — М.: Физматлит, 2001. — 192 с.

4. Редькин Н. П. Надежностьидиагностикасхем/ Н. П.Редькин. — М.: Изд-во Моск. ун-та, 1992. — 192 с.

5. Рябец Л. В. Тестирование бесповторных булевых функций / А. С. Балюк, Л. В. Рябец // Вестник Томского государственного университета. Приложение.— 2006. — Вып 17. — С. 10–14.