УДК 519.718.7

Нижняя оценка длины полного проверяющего теста в базисе \{x|y\} / Ю. В. Бородина. // Вестн. Моск. ун-та. Сер. 1, Математика. Механика. 2015. № 4. С. 49-51.

Доказывается, что для любой схемы в базисе "штрих Шеффера", реализующей функцию x_1\vee x_2\vee \ldots \vee x_n, длина полного проверяющего теста в случае константных неисправностей типа "1" не меньше n+1 (n\ge 2). Приводится пример схемы, реализующей упомянутую функцию в указанном базисе, для которой длина полного проверяющего теста равна n+1.

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

Илл. 2. Библиогр. 5.

К оглавлению номера  Go!